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

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Left Patch Set: Created 6 years, 11 months ago
Right Patch Set: Created 4 years, 4 months 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 277 matching lines...) Expand 10 before | Expand all | Expand 10 after
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 delimit args and keywords in the cache keys */ 595 /* this object is used delimit args and keywords in the cache keys */
546 static PyObject *kwd_mark; 596 static PyObject *kwd_mark = NULL;
547 597
548 struct lru_list_elem; 598 struct lru_list_elem;
549 struct lru_cache_object; 599 struct lru_cache_object;
550 600
551 typedef struct lru_list_elem { 601 typedef struct lru_list_elem {
552 struct 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
607 static void
608 lru_list_elem_dealloc(lru_list_elem *link)
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
556 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *); 660 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *);
557 661
558 typedef struct lru_cache_object { 662 typedef struct lru_cache_object {
559 PyObject_HEAD 663 lru_list_elem root; /* includes PyObject_HEAD */
560 Py_ssize_t maxsize; 664 Py_ssize_t maxsize;
561 PyObject *maxsize_O; 665 PyObject *maxsize_O;
562 PyObject *func; 666 PyObject *func;
563 lru_cache_ternaryfunc wrapper; 667 lru_cache_ternaryfunc wrapper;
564 PyObject *cache; 668 PyObject *cache;
565 PyObject *cache_info_type; 669 PyObject *cache_info_type;
566 Py_ssize_t misses, hits; 670 Py_ssize_t misses, hits;
567 lru_list_elem root;
568 int typed; 671 int typed;
569 PyObject *dict; 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 assert(PyDict_Size(kwds));
588 sorted_items = PyDict_Items(kwds); 691 sorted_items = PyDict_Items(kwds);
589 if (!sorted_items) 692 if (!sorted_items)
590 return NULL; 693 return NULL;
591 if (PyList_Sort(sorted_items) < 0) { 694 if (PyList_Sort(sorted_items) < 0) {
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 744
639 if (kwds) 745 done:
746 if (sorted_items)
640 Py_DECREF(sorted_items); 747 Py_DECREF(sorted_items);
641 return key; 748 return key;
642 } 749 }
643 750
644 static PyObject * 751 static PyObject *
645 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)
646 { 753 {
647 PyObject *result = PyObject_Call(self->func, args, kwds); 754 PyObject *result = PyObject_Call(self->func, args, kwds);
648 if (!result) 755 if (!result)
649 return NULL; 756 return NULL;
(...skipping 28 matching lines...) Expand all
678 Py_DECREF(result); 785 Py_DECREF(result);
679 Py_DECREF(key); 786 Py_DECREF(key);
680 return NULL; 787 return NULL;
681 } 788 }
682 Py_DECREF(key); 789 Py_DECREF(key);
683 self->misses++; 790 self->misses++;
684 return result; 791 return result;
685 } 792 }
686 793
687 static void 794 static void
688 lru_cache_list_extricate(lru_list_elem *link) 795 lru_cache_extricate_link(lru_list_elem *link)
689 { 796 {
690 link->prev->next = link->next; 797 link->prev->next = link->next;
691 link->next->prev = link->prev; 798 link->next->prev = link->prev;
692 } 799 }
693 800
694 static void 801 static void
695 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)
696 { 803 {
804 lru_list_elem *root = &self->root;
697 lru_list_elem *last = root->prev; 805 lru_list_elem *last = root->prev;
698 last->next = root->prev = link; 806 last->next = root->prev = link;
699 link->prev = last; 807 link->prev = last;
700 link->next = root; 808 link->next = root;
701 } 809 }
702 810
703 static PyObject * 811 static PyObject *
704 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 )
705 { 813 {
706 lru_list_elem *link; 814 lru_list_elem *link;
707 815 PyObject *key, *result;
708 PyObject *key = lru_cache_make_key(args, kwds, self->typed); 816
817 key = lru_cache_make_key(args, kwds, self->typed);
709 if (!key) 818 if (!key)
710 return NULL; 819 return NULL;
711 PyObject *value = PyDict_GetItemWithError(self->cache, key); 820 link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
712 if (value) { 821 if (link) {
713 lru_list_elem *link = PyCapsule_GetPointer(value, NULL); 822 lru_cache_extricate_link(link);
714 lru_cache_list_extricate(link); 823 lru_cache_append_link(self, link);
715 lru_cache_list_append(&self->root, link);
716 self->hits++; 824 self->hits++;
825 result = link->result;
826 Py_INCREF(result);
717 Py_DECREF(key); 827 Py_DECREF(key);
718 Py_INCREF(link->result); 828 return result;
719 return link->result;
720 } 829 }
721 if (PyErr_Occurred()) { 830 if (PyErr_Occurred()) {
722 Py_DECREF(key); 831 Py_DECREF(key);
723 return NULL; 832 return NULL;
724 } 833 }
725 PyObject *result = PyObject_Call(self->func, args, kwds); 834 result = PyObject_Call(self->func, args, kwds);
726 if (!result) { 835 if (!result) {
727 Py_DECREF(key); 836 Py_DECREF(key);
728 return NULL; 837 return NULL;
729 } 838 }
730 if (PyDict_Size(self->cache) == self->maxsize) { 839 if (self->full && self->root.next != &self->root) {
731 /* extricate the oldest item */ 840 /* Use the oldest item to store the new key and result. */
841 PyObject *oldkey, *oldresult;
842 /* Extricate the oldest item. */
732 link = self->root.next; 843 link = self->root.next;
733 lru_cache_list_extricate(link); 844 lru_cache_extricate_link(link);
734 /* grab its capsule */ 845 /* Remove it from the cache.
735 value = PyDict_GetItem(self->cache, link->key); 846 The cache dict holds one reference to the link,
736 if (value == NULL) { 847 and the linked list holds yet one reference to it. */
848 if (PyDict_DelItem(self->cache, link->key) < 0) {
849 lru_cache_append_link(self, link);
737 Py_DECREF(key); 850 Py_DECREF(key);
738 return NULL; 851 Py_DECREF(result);
739 } 852 return NULL;
740 Py_INCREF(value); 853 }
741 /* remove its key from the cache */ 854 /* Keep a reference to the old key and old result to
742 if (PyDict_DelItem(self->cache, link->key) < 0) { 855 prevent their ref counts from going to zero during the
storchaka 2012/12/21 22:22:09 Py_DECREF(value);
asvetlov 2012/12/21 22:44:59 Just move incref after if block, right?
storchaka 2012/12/21 22:53:21 No. If PyDict_DelItem() success then value's and k
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);
874 } else {
875 /* Put result in a new link at the front of the queue. */
876 link = (lru_list_elem *)PyObject_GC_New(lru_list_elem,
877 &lru_list_elem_type);
878 if (link == NULL) {
743 Py_DECREF(key); 879 Py_DECREF(key);
744 return NULL; 880 Py_DECREF(result);
745 } 881 return NULL;
746 /* scrub the result from the link */ 882 }
747 Py_DECREF(link->result); 883
748 } else { 884 link->key = key;
749 link = PyMem_New(lru_list_elem, 1); 885 link->result = result;
750 if (link == NULL) { 886 _PyObject_GC_TRACK(link);
751 PyErr_NoMemory(); 887 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
752 return NULL; 888 Py_DECREF(link);
753 } 889 return NULL;
754 value = PyCapsule_New(link, NULL, NULL); 890 }
755 } 891 lru_cache_append_link(self, link);
756 lru_cache_list_append(&self->root, link); 892 Py_INCREF(result); /* for return */
757 link->key = key; 893 self->full = (PyDict_Size(self->cache) >= self->maxsize);
758 Py_INCREF(result); 894 }
759 link->result = result;
760 if (PyDict_SetItem(self->cache, key, value) < 0) {
761 return NULL;
762 }
763 Py_DECREF(value);
storchaka 2012/12/21 22:22:09 It was only a question about Py_DECREF(key). On so
asvetlov 2012/12/21 22:44:59 key REF moved to link->key, right? as well as resu
storchaka 2012/12/21 22:53:21 link is not a Python object and can't own Python o
764 self->misses++; 895 self->misses++;
765 return result; 896 return result;
766 } 897 }
767 898
768 static PyObject * 899 static PyObject *
769 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) 900 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
770 { 901 {
771 PyObject *func, *maxsize_O, *cache_info_type; 902 PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
772 int typed; 903 int typed;
773 lru_cache_object *obj; 904 lru_cache_object *obj;
774 Py_ssize_t maxsize; 905 Py_ssize_t maxsize;
775 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *); 906 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
776 static char *keywords[] = {"user_function", "maxsize", "typed", 907 static char *keywords[] = {"user_function", "maxsize", "typed",
777 "cache_info_type", NULL}; 908 "cache_info_type", NULL};
778 909
779 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords, 910 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
780 &func, &maxsize_O, &typed, 911 &func, &maxsize_O, &typed,
781 &cache_info_type)) { 912 &cache_info_type)) {
782 return NULL; 913 return NULL;
783 } 914 }
784 915
785 if (!PyCallable_Check(func)) { 916 if (!PyCallable_Check(func)) {
786 PyErr_SetString(PyExc_TypeError, 917 PyErr_SetString(PyExc_TypeError,
787 "the first argument must be callable"); 918 "the first argument must be callable");
788 return NULL; 919 return NULL;
789 } 920 }
790 921
791 /* select the caching function, and make/inc maxsize_O */ 922 /* select the caching function, and make/inc maxsize_O */
792 if (maxsize_O == Py_None) { 923 if (maxsize_O == Py_None) {
793 wrapper = infinite_lru_cache_wrapper; 924 wrapper = infinite_lru_cache_wrapper;
794 /* use this only to initialize lru_cache_object attribute maxsize */ 925 /* use this only to initialize lru_cache_object attribute maxsize */
795 maxsize = -1; 926 maxsize = -1;
796 } else if (PyNumber_Check(maxsize_O)) { 927 } else if (PyIndex_Check(maxsize_O)) {
797 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError); 928 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
798 if (maxsize == -1 && PyErr_Occurred()) 929 if (maxsize == -1 && PyErr_Occurred())
799 return NULL; 930 return NULL;
800 if (maxsize == 0) 931 if (maxsize == 0)
801 wrapper = uncached_lru_cache_wrapper; 932 wrapper = uncached_lru_cache_wrapper;
802 else 933 else
803 wrapper = bounded_lru_cache_wrapper; 934 wrapper = bounded_lru_cache_wrapper;
804 } else { 935 } else {
805 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None"); 936 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
806 return NULL; 937 return NULL;
807 } 938 }
808 939
940 if (!(cachedict = PyDict_New()))
941 return NULL;
942
809 obj = (lru_cache_object *)type->tp_alloc(type, 0); 943 obj = (lru_cache_object *)type->tp_alloc(type, 0);
810 if (obj == NULL) 944 if (obj == NULL) {
811 return NULL; 945 Py_DECREF(cachedict);
812 946 return NULL;
947 }
948
949 obj->cache = cachedict;
813 obj->root.prev = &obj->root; 950 obj->root.prev = &obj->root;
814 obj->root.next = &obj->root; 951 obj->root.next = &obj->root;
815 obj->maxsize = maxsize; 952 obj->maxsize = maxsize;
816 Py_INCREF(maxsize_O); 953 Py_INCREF(maxsize_O);
817 obj->maxsize_O = maxsize_O; 954 obj->maxsize_O = maxsize_O;
818 if (!(obj->cache = PyDict_New())) {
819 Py_DECREF(obj);
820 Py_DECREF(maxsize_O);
821 return NULL;
822 }
823 Py_INCREF(func); 955 Py_INCREF(func);
824 obj->func = func; 956 obj->func = 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;
828 Py_INCREF(cache_info_type); 960 Py_INCREF(cache_info_type);
829 obj->cache_info_type = cache_info_type; 961 obj->cache_info_type = cache_info_type;
830 962
831 return (PyObject *)obj; 963 return (PyObject *)obj;
832 } 964 }
833 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
834 static void 978 static void
835 lru_cache_clear_list(lru_list_elem *root) 979 lru_cache_clear_list(lru_list_elem *link)
836 { 980 {
837 lru_list_elem *link = root->next; 981 while (link != NULL) {
838 while (link != root) {
839 lru_list_elem *next = link->next; 982 lru_list_elem *next = link->next;
840 Py_DECREF(link->result); 983 Py_DECREF(link);
841 PyMem_Free(link);
842 link = next; 984 link = next;
843 } 985 }
844 } 986 }
845 987
846 static void 988 static void
847 lru_cache_dealloc(lru_cache_object *obj) 989 lru_cache_dealloc(lru_cache_object *obj)
848 { 990 {
991 lru_list_elem *list = lru_cache_unlink_list(obj);
849 Py_XDECREF(obj->maxsize_O); 992 Py_XDECREF(obj->maxsize_O);
850 Py_XDECREF(obj->func); 993 Py_XDECREF(obj->func);
851 Py_XDECREF(obj->cache); 994 Py_XDECREF(obj->cache);
852 Py_XDECREF(obj->dict); 995 Py_XDECREF(obj->dict);
853 Py_XDECREF(obj->cache_info_type); 996 Py_XDECREF(obj->cache_info_type);
854 lru_cache_clear_list(&obj->root); 997 lru_cache_clear_list(list);
855 Py_TYPE(obj)->tp_free(obj); 998 Py_TYPE(obj)->tp_free(obj);
856 } 999 }
857 1000
858 static PyObject * 1001 static PyObject *
859 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) 1002 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
860 { 1003 {
861 return self->wrapper(self, args, kwds); 1004 return self->wrapper(self, args, kwds);
1005 }
1006
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);
862 } 1015 }
863 1016
864 static PyObject * 1017 static PyObject *
865 lru_cache_cache_info(lru_cache_object *self, PyObject *unused) 1018 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
866 { 1019 {
867 return PyObject_CallFunction(self->cache_info_type, "nnOn", 1020 return PyObject_CallFunction(self->cache_info_type, "nnOn",
868 self->hits, self->misses, self->maxsize_O, 1021 self->hits, self->misses, self->maxsize_O,
869 PyDict_Size(self->cache)); 1022 PyDict_Size(self->cache));
870 } 1023 }
871 1024
872 static PyObject * 1025 static PyObject *
873 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) 1026 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
874 { 1027 {
875 do { 1028 lru_list_elem *list = lru_cache_unlink_list(self);
876 PyDict_Clear(self->cache);
877 } while (PyDict_Size(self->cache));
878 self->hits = self->misses = 0; 1029 self->hits = self->misses = 0;
879 lru_cache_clear_list(&self->root); 1030 self->full = 0;
880 self->root.next = self->root.prev = &self->root; 1031 PyDict_Clear(self->cache);
1032 lru_cache_clear_list(list);
881 Py_RETURN_NONE; 1033 Py_RETURN_NONE;
882 } 1034 }
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
883 1066
884 PyDoc_STRVAR(lru_cache_doc, 1067 PyDoc_STRVAR(lru_cache_doc,
885 "Create a cached callable that wraps another function.\n\ 1068 "Create a cached callable that wraps another function.\n\
886 \n\ 1069 \n\
887 user_function: the function being cached\n\ 1070 user_function: the function being cached\n\
888 \n\ 1071 \n\
889 maxsize: 0 for no caching\n\ 1072 maxsize: 0 for no caching\n\
890 None for unlimited cache size\n\ 1073 None for unlimited cache size\n\
891 n for a bounded cache\n\ 1074 n for a bounded cache\n\
892 \n\ 1075 \n\
(...skipping 29 matching lines...) Expand all
922 0, /* tp_repr */ 1105 0, /* tp_repr */
923 0, /* tp_as_number */ 1106 0, /* tp_as_number */
924 0, /* tp_as_sequence */ 1107 0, /* tp_as_sequence */
925 0, /* tp_as_mapping */ 1108 0, /* tp_as_mapping */
926 0, /* tp_hash */ 1109 0, /* tp_hash */
927 (ternaryfunc)lru_cache_call, /* tp_call */ 1110 (ternaryfunc)lru_cache_call, /* tp_call */
928 0, /* tp_str */ 1111 0, /* tp_str */
929 0, /* tp_getattro */ 1112 0, /* tp_getattro */
930 0, /* tp_setattro */ 1113 0, /* tp_setattro */
931 0, /* tp_as_buffer */ 1114 0, /* tp_as_buffer */
932 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, 1115 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC,
933 /* tp_flags */ 1116 /* tp_flags */
934 lru_cache_doc, /* tp_doc */ 1117 lru_cache_doc, /* tp_doc */
935 0, /* tp_traverse */ 1118 (traverseproc)lru_cache_tp_traverse,/* tp_traverse */
936 0, /* tp_clear */ 1119 (inquiry)lru_cache_tp_clear, /* tp_clear */
937 0, /* tp_richcompare */ 1120 0, /* tp_richcompare */
938 0, /* tp_weaklistoffset */ 1121 0, /* tp_weaklistoffset */
939 0, /* tp_iter */ 1122 0, /* tp_iter */
940 0, /* tp_iternext */ 1123 0, /* tp_iternext */
941 lru_cache_methods, /* tp_methods */ 1124 lru_cache_methods, /* tp_methods */
942 0, /* tp_members */ 1125 0, /* tp_members */
943 lru_cache_getsetlist, /* tp_getset */ 1126 lru_cache_getsetlist, /* tp_getset */
944 0, /* tp_base */ 1127 0, /* tp_base */
945 0, /* tp_dict */ 1128 0, /* tp_dict */
946 0, /* tp_descr_get */ 1129 lru_cache_descr_get, /* tp_descr_get */
947 0, /* tp_descr_set */ 1130 0, /* tp_descr_set */
948 offsetof(lru_cache_object, dict), /* tp_dictoffset */ 1131 offsetof(lru_cache_object, dict), /* tp_dictoffset */
949 0, /* tp_init */ 1132 0, /* tp_init */
950 0, /* tp_alloc */ 1133 0, /* tp_alloc */
951 lru_cache_new, /* tp_new */ 1134 lru_cache_new, /* tp_new */
952 }; 1135 };
953 1136
954 /* module level code ********************************************************/ 1137 /* module level code ********************************************************/
955 1138
956 PyDoc_STRVAR(module_doc, 1139 PyDoc_STRVAR(module_doc,
957 "Tools that operate on functions."); 1140 "Tools that operate on functions.");
958 1141
959 static PyMethodDef module_methods[] = { 1142 static PyMethodDef module_methods[] = {
960 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 1143 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
961 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 1144 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
962 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 1145 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
963 {NULL, NULL} /* sentinel */ 1146 {NULL, NULL} /* sentinel */
964 }; 1147 };
965 1148
966 static void 1149 static void
967 module_free(void *m) 1150 module_free(void *m)
968 { 1151 {
969 Py_DECREF(kwd_mark); 1152 Py_CLEAR(kwd_mark);
970 } 1153 }
971 1154
972 static struct PyModuleDef _functoolsmodule = { 1155 static struct PyModuleDef _functoolsmodule = {
973 PyModuleDef_HEAD_INIT, 1156 PyModuleDef_HEAD_INIT,
974 "_functools", 1157 "_functools",
975 module_doc, 1158 module_doc,
976 -1, 1159 -1,
977 module_methods, 1160 module_methods,
978 NULL, 1161 NULL,
979 NULL, 1162 NULL,
(...skipping 28 matching lines...) Expand all
1008 Py_DECREF(m); 1191 Py_DECREF(m);
1009 return NULL; 1192 return NULL;
1010 } 1193 }
1011 name = strchr(typelist[i]->tp_name, '.'); 1194 name = strchr(typelist[i]->tp_name, '.');
1012 assert (name != NULL); 1195 assert (name != NULL);
1013 Py_INCREF(typelist[i]); 1196 Py_INCREF(typelist[i]);
1014 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1197 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
1015 } 1198 }
1016 return m; 1199 return m;
1017 } 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+