Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(179383)

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Left Patch Set: Created 7 years, 4 months ago
Right Patch Set: Created 4 years ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« no previous file with change/comment | « no previous file | no next file » | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
1 1
2 #include "Python.h" 2 #include "Python.h"
3 #include "structmember.h" 3 #include "structmember.h"
4 4
5 /* _functools module written and maintained 5 /* _functools module written and maintained
6 by Hye-Shik Chang <perky@FreeBSD.org> 6 by Hye-Shik Chang <perky@FreeBSD.org>
7 with adaptations by Raymond Hettinger <python@rcn.com> 7 with adaptations by Raymond Hettinger <python@rcn.com>
8 Copyright (c) 2004, 2005, 2006 Python Software Foundation. 8 Copyright (c) 2004, 2005, 2006 Python Software Foundation.
9 All rights reserved. 9 All rights reserved.
10 */ 10 */
11 11
12 /* partial object **********************************************************/ 12 /* partial object **********************************************************/
13 13
14 typedef struct { 14 typedef struct {
15 PyObject_HEAD 15 PyObject_HEAD
16 PyObject *fn; 16 PyObject *fn;
17 PyObject *args; 17 PyObject *args;
18 PyObject *kw; 18 PyObject *kw;
19 PyObject *dict; 19 PyObject *dict;
20 PyObject *weakreflist; /* List of weak references */ 20 PyObject *weakreflist; /* List of weak references */
21 } partialobject; 21 } partialobject;
22 22
23 static PyTypeObject partial_type; 23 static PyTypeObject partial_type;
24 24
25 static PyObject * 25 static PyObject *
26 partial_new(PyTypeObject *type, PyObject *args, PyObject *kw) 26 partial_new(PyTypeObject *type, PyObject *args, PyObject *kw)
27 { 27 {
28 PyObject *func; 28 PyObject *func, *pargs, *nargs, *pkw;
29 partialobject *pto; 29 partialobject *pto;
30 30
31 if (PyTuple_GET_SIZE(args) < 1) { 31 if (PyTuple_GET_SIZE(args) < 1) {
32 PyErr_SetString(PyExc_TypeError, 32 PyErr_SetString(PyExc_TypeError,
33 "type 'partial' takes at least one argument"); 33 "type 'partial' takes at least one argument");
34 return NULL; 34 return NULL;
35 } 35 }
36 36
37 pargs = pkw = Py_None;
37 func = PyTuple_GET_ITEM(args, 0); 38 func = PyTuple_GET_ITEM(args, 0);
39 if (Py_TYPE(func) == &partial_type && type == &partial_type) {
40 partialobject *part = (partialobject *)func;
41 if (part->dict == NULL) {
42 pargs = part->args;
43 pkw = part->kw;
44 func = part->fn;
45 }
46 }
38 if (!PyCallable_Check(func)) { 47 if (!PyCallable_Check(func)) {
39 PyErr_SetString(PyExc_TypeError, 48 PyErr_SetString(PyExc_TypeError,
40 "the first argument must be callable"); 49 "the first argument must be callable");
41 return NULL; 50 return NULL;
42 } 51 }
43 52
44 /* create partialobject structure */ 53 /* create partialobject structure */
45 pto = (partialobject *)type->tp_alloc(type, 0); 54 pto = (partialobject *)type->tp_alloc(type, 0);
46 if (pto == NULL) 55 if (pto == NULL)
47 return NULL; 56 return NULL;
48 57
49 pto->fn = func; 58 pto->fn = func;
50 Py_INCREF(func); 59 Py_INCREF(func);
51 pto->args = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX); 60
52 if (pto->args == NULL) { 61 nargs = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX);
62 if (nargs == NULL) {
63 pto->args = NULL;
53 pto->kw = NULL; 64 pto->kw = NULL;
54 Py_DECREF(pto); 65 Py_DECREF(pto);
55 return NULL; 66 return NULL;
56 } 67 }
68 if (pargs == Py_None || PyTuple_GET_SIZE(pargs) == 0) {
69 pto->args = nargs;
70 Py_INCREF(nargs);
71 }
72 else if (PyTuple_GET_SIZE(nargs) == 0) {
73 pto->args = pargs;
74 Py_INCREF(pargs);
75 }
76 else {
77 pto->args = PySequence_Concat(pargs, nargs);
78 if (pto->args == NULL) {
79 pto->kw = NULL;
80 Py_DECREF(pto);
81 return NULL;
82 }
83 }
84 Py_DECREF(nargs);
85
57 if (kw != NULL) { 86 if (kw != NULL) {
58 pto->kw = PyDict_Copy(kw); 87 if (pkw == Py_None) {
88 pto->kw = PyDict_Copy(kw);
89 }
90 else {
91 pto->kw = PyDict_Copy(pkw);
92 if (pto->kw != NULL) {
93 if (PyDict_Merge(pto->kw, kw, 1) != 0) {
94 Py_DECREF(pto);
95 return NULL;
96 }
97 }
98 }
59 if (pto->kw == NULL) { 99 if (pto->kw == NULL) {
60 Py_DECREF(pto); 100 Py_DECREF(pto);
61 return NULL; 101 return NULL;
62 } 102 }
63 } else { 103 }
64 pto->kw = Py_None; 104 else {
65 Py_INCREF(Py_None); 105 if (pkw == Py_None) {
106 pto->kw = PyDict_New();
107 if (pto->kw == NULL) {
108 Py_DECREF(pto);
109 return NULL;
110 }
111 }
112 else {
113 pto->kw = pkw;
114 Py_INCREF(pkw);
115 }
66 } 116 }
67 117
68 pto->weakreflist = NULL; 118 pto->weakreflist = NULL;
69 pto->dict = NULL; 119 pto->dict = NULL;
70 120
71 return (PyObject *)pto; 121 return (PyObject *)pto;
72 } 122 }
73 123
74 static void 124 static void
75 partial_dealloc(partialobject *pto) 125 partial_dealloc(partialobject *pto)
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after
211 261
212 static PyObject * 262 static PyObject *
213 partial_reduce(partialobject *pto, PyObject *unused) 263 partial_reduce(partialobject *pto, PyObject *unused)
214 { 264 {
215 return Py_BuildValue("O(O)(OOOO)", Py_TYPE(pto), pto->fn, pto->fn, 265 return Py_BuildValue("O(O)(OOOO)", Py_TYPE(pto), pto->fn, pto->fn,
216 pto->args, pto->kw, 266 pto->args, pto->kw,
217 pto->dict ? pto->dict : Py_None); 267 pto->dict ? pto->dict : Py_None);
218 } 268 }
219 269
220 static PyObject * 270 static PyObject *
221 partial_setstate(partialobject *pto, PyObject *args) 271 partial_setstate(partialobject *pto, PyObject *state)
222 { 272 {
223 PyObject *fn, *fnargs, *kw, *dict; 273 PyObject *fn, *fnargs, *kw, *dict;
224 if (!PyArg_ParseTuple(args, "(OOOO):__setstate__", 274 if (!PyArg_ParseTuple(state, "OOOO",
225 &fn, &fnargs, &kw, &dict)) 275 &fn, &fnargs, &kw, &dict))
226 return NULL; 276 return NULL;
227 Py_XDECREF(pto->fn); 277 Py_XDECREF(pto->fn);
228 Py_XDECREF(pto->args); 278 Py_XDECREF(pto->args);
229 Py_XDECREF(pto->kw); 279 Py_XDECREF(pto->kw);
230 Py_XDECREF(pto->dict); 280 Py_XDECREF(pto->dict);
231 pto->fn = fn; 281 pto->fn = fn;
232 pto->args = fnargs; 282 pto->args = fnargs;
233 pto->kw = kw; 283 pto->kw = kw;
234 if (dict != Py_None) { 284 if (dict != Py_None) {
235 pto->dict = dict; 285 pto->dict = dict;
236 Py_INCREF(dict); 286 Py_INCREF(dict);
237 } else { 287 } else {
238 pto->dict = NULL; 288 pto->dict = NULL;
239 } 289 }
240 Py_INCREF(fn); 290 Py_INCREF(fn);
241 Py_INCREF(fnargs); 291 Py_INCREF(fnargs);
242 Py_INCREF(kw); 292 Py_INCREF(kw);
243 Py_RETURN_NONE; 293 Py_RETURN_NONE;
244 } 294 }
245 295
246 static PyMethodDef partial_methods[] = { 296 static PyMethodDef partial_methods[] = {
247 {"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS}, 297 {"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS},
248 {"__setstate__", (PyCFunction)partial_setstate, METH_VARARGS}, 298 {"__setstate__", (PyCFunction)partial_setstate, METH_O},
249 {NULL, NULL} /* sentinel */ 299 {NULL, NULL} /* sentinel */
250 }; 300 };
251 301
252 static PyTypeObject partial_type = { 302 static PyTypeObject partial_type = {
253 PyVarObject_HEAD_INIT(NULL, 0) 303 PyVarObject_HEAD_INIT(NULL, 0)
254 "functools.partial", /* tp_name */ 304 "functools.partial", /* tp_name */
255 sizeof(partialobject), /* tp_basicsize */ 305 sizeof(partialobject), /* tp_basicsize */
256 0, /* tp_itemsize */ 306 0, /* tp_itemsize */
257 /* methods */ 307 /* methods */
258 (destructor)partial_dealloc, /* tp_dealloc */ 308 (destructor)partial_dealloc, /* tp_dealloc */
(...skipping 276 matching lines...) Expand 10 before | Expand all | Expand 10 after
535 \n\ 585 \n\
536 Apply a function of two arguments cumulatively to the items of a sequence,\n\ 586 Apply a function of two arguments cumulatively to the items of a sequence,\n\
537 from left to right, so as to reduce the sequence to a single value.\n\ 587 from left to right, so as to reduce the sequence to a single value.\n\
538 For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n\ 588 For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n\
539 ((((1+2)+3)+4)+5). If initial is present, it is placed before the items\n\ 589 ((((1+2)+3)+4)+5). If initial is present, it is placed before the items\n\
540 of the sequence in the calculation, and serves as a default when the\n\ 590 of the sequence in the calculation, and serves as a default when the\n\
541 sequence is empty."); 591 sequence is empty.");
542 592
543 /* lru_cache object **********************************************************/ 593 /* lru_cache object **********************************************************/
544 594
545 // this object is used for its nonequivalency to delimit args and keywords 595 /* this object is used delimit args and keywords in the cache keys */
546 // when forming keys for the cache 596 static PyObject *kwd_mark = NULL;
547 static PyObject *kwd_mark; 597
548 598 struct lru_list_elem;
549 typedef struct lru_list_elem lru_list_elem; 599 struct lru_cache_object;
550 600
551 typedef struct lru_list_elem { 601 typedef struct lru_list_elem {
552 lru_list_elem *prev, *next; 602 PyObject_HEAD
603 struct lru_list_elem *prev, *next; /* borrowed links */
553 PyObject *key, *result; 604 PyObject *key, *result;
554 } lru_list_elem; 605 } lru_list_elem;
555 606
556 typedef struct lru_cache_object lru_cache_object; 607 static void
557 608 lru_list_elem_dealloc(lru_list_elem *link)
558 typedef PyObject *(*lru_cache_ternaryfunc)(lru_cache_object *, PyObject *, PyObj ect *); 609 {
610 _PyObject_GC_UNTRACK(link);
611 Py_XDECREF(link->key);
612 Py_XDECREF(link->result);
613 PyObject_GC_Del(link);
614 }
615
616 static int
617 lru_list_elem_traverse(lru_list_elem *link, visitproc visit, void *arg)
618 {
619 Py_VISIT(link->key);
620 Py_VISIT(link->result);
621 return 0;
622 }
623
624 static int
625 lru_list_elem_clear(lru_list_elem *link)
626 {
627 Py_CLEAR(link->key);
628 Py_CLEAR(link->result);
629 return 0;
630 }
631
632 static PyTypeObject lru_list_elem_type = {
633 PyVarObject_HEAD_INIT(&PyType_Type, 0)
634 "functools._lru_list_elem", /* tp_name */
635 sizeof(lru_list_elem), /* tp_basicsize */
636 0, /* tp_itemsize */
637 /* methods */
638 (destructor)lru_list_elem_dealloc, /* tp_dealloc */
639 0, /* tp_print */
640 0, /* tp_getattr */
641 0, /* tp_setattr */
642 0, /* tp_reserved */
643 0, /* tp_repr */
644 0, /* tp_as_number */
645 0, /* tp_as_sequence */
646 0, /* tp_as_mapping */
647 0, /* tp_hash */
648 0, /* tp_call */
649 0, /* tp_str */
650 0, /* tp_getattro */
651 0, /* tp_setattro */
652 0, /* tp_as_buffer */
653 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
654 0, /* tp_doc */
655 (traverseproc)lru_list_elem_traverse, /* tp_traverse */
656 (inquiry)lru_list_elem_clear, /* tp_clear */
657 };
658
659
660 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *);
559 661
560 typedef struct lru_cache_object { 662 typedef struct lru_cache_object {
561 PyObject_HEAD 663 lru_list_elem root; /* includes PyObject_HEAD */
562 Py_ssize_t maxsize; 664 Py_ssize_t maxsize;
563 PyObject *maxsize_O; 665 PyObject *maxsize_O;
564 PyObject *func; 666 PyObject *func;
565 lru_cache_ternaryfunc wrapper; 667 lru_cache_ternaryfunc wrapper;
566 PyObject *cache; 668 PyObject *cache;
669 PyObject *cache_info_type;
567 Py_ssize_t misses, hits; 670 Py_ssize_t misses, hits;
568 lru_list_elem root;
569 int typed; 671 int typed;
672 PyObject *dict;
673 int full;
570 } lru_cache_object; 674 } lru_cache_object;
571 675
572 static PyTypeObject lru_cache_type; 676 static PyTypeObject lru_cache_type;
573 677
574 static PyObject * 678 static PyObject *
575 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed) 679 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
576 { 680 {
577 PyObject *key, *sorted_items; 681 PyObject *key, *sorted_items;
578 Py_ssize_t key_size, pos, key_pos; 682 Py_ssize_t key_size, pos, key_pos;
579 683
580 // short path, key will match args anyway, which is a tuple 684 /* short path, key will match args anyway, which is a tuple */
581 if (!typed && !kwds) { 685 if (!typed && !kwds) {
582 Py_INCREF(args); 686 Py_INCREF(args);
583 return args; 687 return args;
584 } 688 }
585 689
586 if (kwds) { 690 if (kwds && PyDict_Size(kwds) > 0) {
587 // paranoia... 691 sorted_items = PyDict_Items(kwds);
588 assert(PyDict_Size(kwds)); 692 if (!sorted_items)
589 if (!(sorted_items = PyDict_Items(kwds))) 693 return NULL;
590 return NULL; 694 if (PyList_Sort(sorted_items) < 0) {
591 if (0 > PyList_Sort(sorted_items)) {
592 Py_DECREF(sorted_items); 695 Py_DECREF(sorted_items);
593 return NULL; 696 return NULL;
594 } 697 }
595 } else 698 } else
596 sorted_items = NULL; 699 sorted_items = NULL;
597 700
598 key_size = PyTuple_GET_SIZE(args); 701 key_size = PyTuple_GET_SIZE(args);
599 if (kwds) 702 if (sorted_items)
600 key_size += PyList_GET_SIZE(sorted_items); 703 key_size += PyList_GET_SIZE(sorted_items);
601 if (typed) 704 if (typed)
602 key_size *= 2; 705 key_size *= 2;
603 if (kwds) 706 if (sorted_items)
604 key_size++; 707 key_size++;
605 708
606 key = PyTuple_New(key_size); 709 key = PyTuple_New(key_size);
710 if (key == NULL)
711 goto done;
712
607 key_pos = 0; 713 key_pos = 0;
608
609 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 714 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
610 PyObject *item = PyTuple_GET_ITEM(args, pos); 715 PyObject *item = PyTuple_GET_ITEM(args, pos);
611 Py_INCREF(item); 716 Py_INCREF(item);
612 PyTuple_SET_ITEM(key, key_pos++, item); 717 PyTuple_SET_ITEM(key, key_pos++, item);
613 } 718 }
614 if (kwds) { 719 if (sorted_items) {
615 Py_INCREF(kwd_mark); 720 Py_INCREF(kwd_mark);
616 PyTuple_SET_ITEM(key, key_pos++, kwd_mark); 721 PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
617 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 722 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
618 PyObject *item = PyList_GET_ITEM(sorted_items, pos); 723 PyObject *item = PyList_GET_ITEM(sorted_items, pos);
619 Py_INCREF(item); 724 Py_INCREF(item);
620 PyTuple_SET_ITEM(key, key_pos++, item); 725 PyTuple_SET_ITEM(key, key_pos++, item);
621 } 726 }
622 } 727 }
623 if (typed) { 728 if (typed) {
624 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 729 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
625 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos)); 730 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
626 Py_INCREF(item); 731 Py_INCREF(item);
627 PyTuple_SET_ITEM(key, key_pos++, item); 732 PyTuple_SET_ITEM(key, key_pos++, item);
628 } 733 }
629 if (kwds) { 734 if (sorted_items) {
630 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 735 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
631 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(PyList_GET _ITEM(sorted_items, pos), 1)); 736 PyObject *tp_items = PyList_GET_ITEM(sorted_items, pos);
737 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(tp_items, 1));
632 Py_INCREF(item); 738 Py_INCREF(item);
633 PyTuple_SET_ITEM(key, key_pos++, item); 739 PyTuple_SET_ITEM(key, key_pos++, item);
634 } 740 }
635 } 741 }
636 } 742 }
637 assert(key_pos == key_size); 743 assert(key_pos == key_size);
638 if (kwds) 744
745 done:
746 if (sorted_items)
639 Py_DECREF(sorted_items); 747 Py_DECREF(sorted_items);
640 return key; 748 return key;
641 } 749 }
642 750
643 static PyObject * 751 static PyObject *
644 uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s) 752 uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s)
645 { 753 {
646 PyObject *result = PyObject_Call(self->func, args, kwds); 754 PyObject *result = PyObject_Call(self->func, args, kwds);
647 if (!result) 755 if (!result)
648 return NULL; 756 return NULL;
(...skipping 28 matching lines...) Expand all
677 Py_DECREF(result); 785 Py_DECREF(result);
678 Py_DECREF(key); 786 Py_DECREF(key);
679 return NULL; 787 return NULL;
680 } 788 }
681 Py_DECREF(key); 789 Py_DECREF(key);
682 self->misses++; 790 self->misses++;
683 return result; 791 return result;
684 } 792 }
685 793
686 static void 794 static void
687 lru_cache_list_extricate(lru_list_elem *link) 795 lru_cache_extricate_link(lru_list_elem *link)
688 { 796 {
689 link->prev->next = link->next; 797 link->prev->next = link->next;
690 link->next->prev = link->prev; 798 link->next->prev = link->prev;
691 } 799 }
692 800
693 static void 801 static void
694 lru_cache_list_append(lru_list_elem *root, lru_list_elem *link) 802 lru_cache_append_link(lru_cache_object *self, lru_list_elem *link)
695 { 803 {
804 lru_list_elem *root = &self->root;
696 lru_list_elem *last = root->prev; 805 lru_list_elem *last = root->prev;
697 last->next = root->prev = link; 806 last->next = root->prev = link;
698 link->prev = last; 807 link->prev = last;
699 link->next = root; 808 link->next = root;
700 } 809 }
701 810
702 static PyObject * 811 static PyObject *
703 bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds ) 812 bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds )
704 { 813 {
705 PyObject *key = lru_cache_make_key(args, kwds, self->typed); 814 lru_list_elem *link;
815 PyObject *key, *result;
816
817 key = lru_cache_make_key(args, kwds, self->typed);
706 if (!key) 818 if (!key)
707 return NULL; 819 return NULL;
708 PyObject *value = PyDict_GetItemWithError(self->cache, key); 820 link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
709 if (value) { 821 if (link) {
710 lru_list_elem *link = PyCapsule_GetPointer(value, NULL); 822 lru_cache_extricate_link(link);
711 lru_cache_list_extricate(link); 823 lru_cache_append_link(self, link);
712 lru_cache_list_append(&self->root, link);
713 self->hits++; 824 self->hits++;
825 result = link->result;
826 Py_INCREF(result);
714 Py_DECREF(key); 827 Py_DECREF(key);
715 Py_INCREF(link->result); 828 return result;
716 return link->result;
717 } 829 }
718 if (PyErr_Occurred()) { 830 if (PyErr_Occurred()) {
719 Py_DECREF(key); 831 Py_DECREF(key);
720 return NULL; 832 return NULL;
721 } 833 }
722 PyObject *result = PyObject_Call(self->func, args, kwds); 834 result = PyObject_Call(self->func, args, kwds);
723 if (!result) { 835 if (!result) {
724 Py_DECREF(key); 836 Py_DECREF(key);
725 return NULL; 837 return NULL;
726 } 838 }
727 lru_list_elem *link; 839 if (self->full && self->root.next != &self->root) {
728 if (PyDict_Size(self->cache) == self->maxsize) { 840 /* Use the oldest item to store the new key and result. */
729 // extricate the oldest item 841 PyObject *oldkey, *oldresult;
842 /* Extricate the oldest item. */
730 link = self->root.next; 843 link = self->root.next;
731 lru_cache_list_extricate(link); 844 lru_cache_extricate_link(link);
732 // grab its capsule 845 /* Remove it from the cache.
733 value = PyDict_GetItem(self->cache, link->key); 846 The cache dict holds one reference to the link,
734 Py_INCREF(value); 847 and the linked list holds yet one reference to it. */
735 // remove its key from the cache 848 if (PyDict_DelItem(self->cache, link->key) < 0) {
736 if (0 > PyDict_DelItem(self->cache, link->key)) 849 lru_cache_append_link(self, link);
737 abort(); 850 Py_DECREF(key);
738 // scrub the result from the link 851 Py_DECREF(result);
739 Py_DECREF(link->result); 852 return NULL;
853 }
854 /* Keep a reference to the old key and old result to
855 prevent their ref counts from going to zero during the
856 update. That will prevent potentially arbitrary object
857 clean-up code (i.e. __del__) from running while we're
858 still adjusting the links. */
859 oldkey = link->key;
860 oldresult = link->result;
861
862 link->key = key;
863 link->result = result;
864 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
865 Py_DECREF(link);
866 Py_DECREF(oldkey);
867 Py_DECREF(oldresult);
868 return NULL;
869 }
870 lru_cache_append_link(self, link);
871 Py_INCREF(result); /* for return */
872 Py_DECREF(oldkey);
873 Py_DECREF(oldresult);
740 } else { 874 } else {
741 link = PyMem_New(lru_list_elem, 1); 875 /* Put result in a new link at the front of the queue. */
742 value = PyCapsule_New(link, NULL, NULL); 876 link = (lru_list_elem *)PyObject_GC_New(lru_list_elem,
743 } 877 &lru_list_elem_type);
744 lru_cache_list_append(&self->root, link); 878 if (link == NULL) {
745 link->key = key; 879 Py_DECREF(key);
746 link->result = result; 880 Py_DECREF(result);
747 Py_INCREF(result); 881 return NULL;
748 if (0 > PyDict_SetItem(self->cache, key, value)) abort(); 882 }
749 Py_DECREF(key); 883
750 Py_DECREF(value); 884 link->key = key;
885 link->result = result;
886 _PyObject_GC_TRACK(link);
887 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
888 Py_DECREF(link);
889 return NULL;
890 }
891 lru_cache_append_link(self, link);
892 Py_INCREF(result); /* for return */
893 self->full = (PyDict_Size(self->cache) >= self->maxsize);
894 }
751 self->misses++; 895 self->misses++;
752 return result; 896 return result;
753 } 897 }
754 898
755 static PyObject * 899 static PyObject *
756 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) 900 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
757 { 901 {
758 PyObject *func; 902 PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
759 PyObject *maxsize_O = NULL;
760 PyObject *typed_O = NULL;
761 int typed; 903 int typed;
762 lru_cache_object *obj; 904 lru_cache_object *obj;
763 Py_ssize_t maxsize = 100; 905 Py_ssize_t maxsize;
764 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *); 906 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
765 static char *keywords[] = {"func", "maxsize", "typed", NULL}; 907 static char *keywords[] = {"user_function", "maxsize", "typed",
766 908 "cache_info_type", NULL};
767 if (!PyArg_ParseTupleAndKeywords(args, kw, "O|OO:lru_cache", keywords, 909
768 &func, &maxsize_O, &typed_O)) { 910 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
911 &func, &maxsize_O, &typed,
912 &cache_info_type)) {
769 return NULL; 913 return NULL;
770 } 914 }
771 915
772 if (!PyCallable_Check(func)) { 916 if (!PyCallable_Check(func)) {
773 PyErr_SetString(PyExc_TypeError, 917 PyErr_SetString(PyExc_TypeError,
774 "the first argument must be callable"); 918 "the first argument must be callable");
775 return NULL; 919 return NULL;
776 } 920 }
777 921
778 if (maxsize_O == NULL) { 922 /* select the caching function, and make/inc maxsize_O */
779 maxsize_O = PyLong_FromSsize_t(maxsize); 923 if (maxsize_O == Py_None) {
780 wrapper = bounded_lru_cache_wrapper;
781 } else if (maxsize_O == Py_None) {
782 wrapper = infinite_lru_cache_wrapper; 924 wrapper = infinite_lru_cache_wrapper;
783 Py_INCREF(maxsize_O); 925 /* use this only to initialize lru_cache_object attribute maxsize */
784 } else if (PyNumber_Check(maxsize_O)) { 926 maxsize = -1;
927 } else if (PyIndex_Check(maxsize_O)) {
785 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError); 928 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
786 if (maxsize == -1 && PyErr_Occurred()) 929 if (maxsize == -1 && PyErr_Occurred())
787 return NULL; 930 return NULL;
788 if (maxsize == 0) 931 if (maxsize == 0)
789 wrapper = uncached_lru_cache_wrapper; 932 wrapper = uncached_lru_cache_wrapper;
790 else 933 else
791 wrapper = bounded_lru_cache_wrapper; 934 wrapper = bounded_lru_cache_wrapper;
792 Py_INCREF(maxsize_O);
793 } else { 935 } else {
794 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None"); 936 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
795 return NULL; 937 return NULL;
796 } 938 }
797 939
798 if (typed_O) { 940 if (!(cachedict = PyDict_New()))
799 int err = PyObject_IsTrue(typed_O); 941 return NULL;
800 if (err < 0) {
801 Py_DECREF(maxsize_O);
802 return NULL;
803 }
804 typed = err;
805 } else
806 typed = 0;
807 942
808 obj = (lru_cache_object *)type->tp_alloc(type, 0); 943 obj = (lru_cache_object *)type->tp_alloc(type, 0);
809 if (obj == NULL) { 944 if (obj == NULL) {
810 Py_DECREF(maxsize_O); 945 Py_DECREF(cachedict);
811 return NULL; 946 return NULL;
812 } 947 }
813 948
949 obj->cache = cachedict;
814 obj->root.prev = &obj->root; 950 obj->root.prev = &obj->root;
815 obj->root.next = &obj->root; 951 obj->root.next = &obj->root;
816 obj->maxsize = maxsize; 952 obj->maxsize = maxsize;
953 Py_INCREF(maxsize_O);
817 obj->maxsize_O = maxsize_O; 954 obj->maxsize_O = maxsize_O;
818 if (!(obj->cache = PyDict_New())) { 955 Py_INCREF(func);
819 Py_DECREF(obj);
820 Py_DECREF(maxsize_O);
821 return NULL;
822 }
823 obj->func = func; 956 obj->func = func;
824 Py_INCREF(func);
825 obj->wrapper = wrapper; 957 obj->wrapper = wrapper;
826 obj->misses = obj->hits = 0; 958 obj->misses = obj->hits = 0;
827 obj->typed = typed; 959 obj->typed = typed;
960 Py_INCREF(cache_info_type);
961 obj->cache_info_type = cache_info_type;
828 962
829 return (PyObject *)obj; 963 return (PyObject *)obj;
830 } 964 }
831 965
966 static lru_list_elem *
967 lru_cache_unlink_list(lru_cache_object *self)
968 {
969 lru_list_elem *root = &self->root;
970 lru_list_elem *link = root->next;
971 if (link == root)
972 return NULL;
973 root->prev->next = NULL;
974 root->next = root->prev = root;
975 return link;
976 }
977
832 static void 978 static void
833 lru_cache_clear_list(lru_list_elem *root) 979 lru_cache_clear_list(lru_list_elem *link)
834 { 980 {
835 lru_list_elem *link = root->next; 981 while (link != NULL) {
836 while (link != root) {
837 lru_list_elem *next = link->next; 982 lru_list_elem *next = link->next;
838 Py_DECREF(link->result); 983 Py_DECREF(link);
839 PyMem_Free(link);
840 link = next; 984 link = next;
841 } 985 }
842 // prevent double dealloc problems
843 root->next = root;
844 root->prev = root;
845 } 986 }
846 987
847 static void 988 static void
848 lru_cache_dealloc(lru_cache_object *obj) 989 lru_cache_dealloc(lru_cache_object *obj)
849 { 990 {
991 lru_list_elem *list = lru_cache_unlink_list(obj);
850 Py_XDECREF(obj->maxsize_O); 992 Py_XDECREF(obj->maxsize_O);
851 Py_XDECREF(obj->func); 993 Py_XDECREF(obj->func);
852 Py_XDECREF(obj->cache); 994 Py_XDECREF(obj->cache);
853 lru_cache_clear_list(&obj->root); 995 Py_XDECREF(obj->dict);
996 Py_XDECREF(obj->cache_info_type);
997 lru_cache_clear_list(list);
854 Py_TYPE(obj)->tp_free(obj); 998 Py_TYPE(obj)->tp_free(obj);
855 } 999 }
856 1000
857 static PyObject * 1001 static PyObject *
858 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) 1002 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
859 { 1003 {
860 return self->wrapper(self, args, kwds); 1004 return self->wrapper(self, args, kwds);
861 } 1005 }
862 1006
863 static PyObject * 1007 static PyObject *
1008 lru_cache_descr_get(PyObject *self, PyObject *obj, PyObject *type)
1009 {
1010 if (obj == Py_None || obj == NULL) {
1011 Py_INCREF(self);
1012 return self;
1013 }
1014 return PyMethod_New(self, obj);
1015 }
1016
1017 static PyObject *
864 lru_cache_cache_info(lru_cache_object *self, PyObject *unused) 1018 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
865 { 1019 {
866 return Py_BuildValue("nnOn", self->hits, self->misses, 1020 return PyObject_CallFunction(self->cache_info_type, "nnOn",
867 self->maxsize_O, PyDict_Size(self->cache)); 1021 self->hits, self->misses, self->maxsize_O,
1022 PyDict_Size(self->cache));
868 } 1023 }
869 1024
870 static PyObject * 1025 static PyObject *
871 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) 1026 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
872 { 1027 {
1028 lru_list_elem *list = lru_cache_unlink_list(self);
1029 self->hits = self->misses = 0;
1030 self->full = 0;
873 PyDict_Clear(self->cache); 1031 PyDict_Clear(self->cache);
874 self->hits = self->misses = 0; 1032 lru_cache_clear_list(list);
875 lru_cache_clear_list(&self->root);
876 Py_RETURN_NONE; 1033 Py_RETURN_NONE;
877 } 1034 }
878 1035
1036 static int
1037 lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
1038 {
1039 lru_list_elem *link = self->root.next;
1040 while (link != &self->root) {
1041 lru_list_elem *next = link->next;
1042 Py_VISIT(link);
1043 link = next;
1044 }
1045 Py_VISIT(self->maxsize_O);
1046 Py_VISIT(self->func);
1047 Py_VISIT(self->cache);
1048 Py_VISIT(self->cache_info_type);
1049 Py_VISIT(self->dict);
1050 return 0;
1051 }
1052
1053 static int
1054 lru_cache_tp_clear(lru_cache_object *self)
1055 {
1056 lru_list_elem *list = lru_cache_unlink_list(self);
1057 Py_CLEAR(self->maxsize_O);
1058 Py_CLEAR(self->func);
1059 Py_CLEAR(self->cache);
1060 Py_CLEAR(self->cache_info_type);
1061 Py_CLEAR(self->dict);
1062 lru_cache_clear_list(list);
1063 return 0;
1064 }
1065
1066
1067 PyDoc_STRVAR(lru_cache_doc,
1068 "Create a cached callable that wraps another function.\n\
1069 \n\
1070 user_function: the function being cached\n\
1071 \n\
1072 maxsize: 0 for no caching\n\
1073 None for unlimited cache size\n\
1074 n for a bounded cache\n\
1075 \n\
1076 typed: False cache f(3) and f(3.0) as identical calls\n\
1077 True cache f(3) and f(3.0) as distinct calls\n\
1078 \n\
1079 cache_info_type: namedtuple class with the fields:\n\
1080 hits misses currsize maxsize\n"
1081 );
1082
879 static PyMethodDef lru_cache_methods[] = { 1083 static PyMethodDef lru_cache_methods[] = {
880 {"_cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS}, 1084 {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
881 {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS}, 1085 {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
882 {NULL, NULL} 1086 {NULL}
1087 };
1088
1089 static PyGetSetDef lru_cache_getsetlist[] = {
1090 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
1091 {NULL}
883 }; 1092 };
884 1093
885 static PyTypeObject lru_cache_type = { 1094 static PyTypeObject lru_cache_type = {
886 PyVarObject_HEAD_INIT(NULL, 0) 1095 PyVarObject_HEAD_INIT(NULL, 0)
887 "functools._LRUCache", /* tp_name */ 1096 "functools._lru_cache_wrapper", /* tp_name */
888 sizeof(lru_cache_object), /* tp_basicsize */ 1097 sizeof(lru_cache_object), /* tp_basicsize */
889 0, /* tp_itemsize */ 1098 0, /* tp_itemsize */
890 /* methods */ 1099 /* methods */
891 (destructor)lru_cache_dealloc, /* tp_dealloc */ 1100 (destructor)lru_cache_dealloc, /* tp_dealloc */
892 0, /* tp_print */ 1101 0, /* tp_print */
893 0, /* tp_getattr */ 1102 0, /* tp_getattr */
894 0, /* tp_setattr */ 1103 0, /* tp_setattr */
895 0, /* tp_reserved */ 1104 0, /* tp_reserved */
896 0, /* tp_repr */ 1105 0, /* tp_repr */
897 0, /* tp_as_number */ 1106 0, /* tp_as_number */
898 0, /* tp_as_sequence */ 1107 0, /* tp_as_sequence */
899 0, /* tp_as_mapping */ 1108 0, /* tp_as_mapping */
900 0, /* tp_hash */ 1109 0, /* tp_hash */
901 (ternaryfunc)lru_cache_call, /* tp_call */ 1110 (ternaryfunc)lru_cache_call, /* tp_call */
902 0, /* tp_str */ 1111 0, /* tp_str */
903 0, /* tp_getattro */ 1112 0, /* tp_getattro */
904 0, /* tp_setattro */ 1113 0, /* tp_setattro */
905 0, /* tp_as_buffer */ 1114 0, /* tp_as_buffer */
906 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, 1115 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC,
907 /* tp_flags */ 1116 /* tp_flags */
908 0, /* tp_doc */ 1117 lru_cache_doc, /* tp_doc */
909 0, /* tp_traverse */ 1118 (traverseproc)lru_cache_tp_traverse,/* tp_traverse */
910 0, /* tp_clear */ 1119 (inquiry)lru_cache_tp_clear, /* tp_clear */
911 0, /* tp_richcompare */ 1120 0, /* tp_richcompare */
912 0, /* tp_weaklistoffset */ 1121 0, /* tp_weaklistoffset */
913 0, /* tp_iter */ 1122 0, /* tp_iter */
914 0, /* tp_iternext */ 1123 0, /* tp_iternext */
915 lru_cache_methods, /* tp_methods */ 1124 lru_cache_methods, /* tp_methods */
916 0, /* tp_members */ 1125 0, /* tp_members */
917 0, /* tp_getset */ 1126 lru_cache_getsetlist, /* tp_getset */
918 0, /* tp_base */ 1127 0, /* tp_base */
919 0, /* tp_dict */ 1128 0, /* tp_dict */
920 0, /* tp_descr_get */ 1129 lru_cache_descr_get, /* tp_descr_get */
921 0, /* tp_descr_set */ 1130 0, /* tp_descr_set */
922 0, /* tp_dictoffset */ 1131 offsetof(lru_cache_object, dict), /* tp_dictoffset */
923 0, /* tp_init */ 1132 0, /* tp_init */
924 0, /* tp_alloc */ 1133 0, /* tp_alloc */
925 lru_cache_new, /* tp_new */ 1134 lru_cache_new, /* tp_new */
926 }; 1135 };
927 1136
928 /* module level code ********************************************************/ 1137 /* module level code ********************************************************/
929 1138
930 PyDoc_STRVAR(module_doc, 1139 PyDoc_STRVAR(module_doc,
931 "Tools that operate on functions."); 1140 "Tools that operate on functions.");
932 1141
933 static PyMethodDef module_methods[] = { 1142 static PyMethodDef module_methods[] = {
934 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 1143 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
935 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 1144 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
936 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 1145 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
937 {NULL, NULL} /* sentinel */ 1146 {NULL, NULL} /* sentinel */
938 }; 1147 };
939 1148
940 static void 1149 static void
941 module_free(void *m) 1150 module_free(void *m)
942 { 1151 {
943 Py_DECREF(kwd_mark); 1152 Py_CLEAR(kwd_mark);
944 } 1153 }
945
946 1154
947 static struct PyModuleDef _functoolsmodule = { 1155 static struct PyModuleDef _functoolsmodule = {
948 PyModuleDef_HEAD_INIT, 1156 PyModuleDef_HEAD_INIT,
949 "_functools", 1157 "_functools",
950 module_doc, 1158 module_doc,
951 -1, 1159 -1,
952 module_methods, 1160 module_methods,
953 NULL, 1161 NULL,
954 NULL, 1162 NULL,
955 NULL, 1163 NULL,
956 module_free, 1164 module_free,
957 }; 1165 };
958 1166
959 PyMODINIT_FUNC 1167 PyMODINIT_FUNC
960 PyInit__functools(void) 1168 PyInit__functools(void)
961 { 1169 {
962 int i; 1170 int i;
963 PyObject *m; 1171 PyObject *m;
964 char *name; 1172 char *name;
965 PyTypeObject *typelist[] = { 1173 PyTypeObject *typelist[] = {
966 &partial_type, 1174 &partial_type,
967 &lru_cache_type, 1175 &lru_cache_type,
968 NULL 1176 NULL
969 }; 1177 };
970 1178
971 m = PyModule_Create(&_functoolsmodule); 1179 m = PyModule_Create(&_functoolsmodule);
972 if (m == NULL) 1180 if (m == NULL)
973 return NULL; 1181 return NULL;
974 1182
975 if (!(kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL))) { 1183 kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL);
1184 if (!kwd_mark) {
976 Py_DECREF(m); 1185 Py_DECREF(m);
977 return NULL; 1186 return NULL;
978 } 1187 }
979 1188
980 for (i=0 ; typelist[i] != NULL ; i++) { 1189 for (i=0 ; typelist[i] != NULL ; i++) {
981 if (PyType_Ready(typelist[i]) < 0) { 1190 if (PyType_Ready(typelist[i]) < 0) {
982 Py_DECREF(m); 1191 Py_DECREF(m);
983 return NULL; 1192 return NULL;
984 } 1193 }
985 name = strchr(typelist[i]->tp_name, '.'); 1194 name = strchr(typelist[i]->tp_name, '.');
986 assert (name != NULL); 1195 assert (name != NULL);
987 Py_INCREF(typelist[i]); 1196 Py_INCREF(typelist[i]);
988 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1197 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
989 } 1198 }
990 return m; 1199 return m;
991 } 1200 }
LEFTRIGHT
« no previous file | no next file » | Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Toggle Comments ('s')

RSS Feeds Recent Issues | This issue
This is Rietveld 894c83f36cb7+