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

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Left Patch Set: Created 6 years, 9 months ago
Right Patch Set: Created 4 years, 3 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
5 #ifdef WITH_THREAD
6 #include "pythread.h"
7 #endif
8 4
9 /* _functools module written and maintained 5 /* _functools module written and maintained
10 by Hye-Shik Chang <perky@FreeBSD.org> 6 by Hye-Shik Chang <perky@FreeBSD.org>
11 with adaptations by Raymond Hettinger <python@rcn.com> 7 with adaptations by Raymond Hettinger <python@rcn.com>
12 Copyright (c) 2004, 2005, 2006 Python Software Foundation. 8 Copyright (c) 2004, 2005, 2006 Python Software Foundation.
13 All rights reserved. 9 All rights reserved.
14 */ 10 */
15 11
16 /* partial object **********************************************************/ 12 /* partial object **********************************************************/
17 13
18 typedef struct { 14 typedef struct {
19 PyObject_HEAD 15 PyObject_HEAD
20 PyObject *fn; 16 PyObject *fn;
21 PyObject *args; 17 PyObject *args;
22 PyObject *kw; 18 PyObject *kw;
23 PyObject *dict; 19 PyObject *dict;
24 PyObject *weakreflist; /* List of weak references */ 20 PyObject *weakreflist; /* List of weak references */
25 } partialobject; 21 } partialobject;
26 22
27 static PyTypeObject partial_type; 23 static PyTypeObject partial_type;
28 24
29 static PyObject * 25 static PyObject *
30 partial_new(PyTypeObject *type, PyObject *args, PyObject *kw) 26 partial_new(PyTypeObject *type, PyObject *args, PyObject *kw)
31 { 27 {
32 PyObject *func; 28 PyObject *func, *pargs, *nargs, *pkw;
33 partialobject *pto; 29 partialobject *pto;
34 30
35 if (PyTuple_GET_SIZE(args) < 1) { 31 if (PyTuple_GET_SIZE(args) < 1) {
36 PyErr_SetString(PyExc_TypeError, 32 PyErr_SetString(PyExc_TypeError,
37 "type 'partial' takes at least one argument"); 33 "type 'partial' takes at least one argument");
38 return NULL; 34 return NULL;
39 } 35 }
40 36
37 pargs = pkw = Py_None;
41 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 }
42 if (!PyCallable_Check(func)) { 47 if (!PyCallable_Check(func)) {
43 PyErr_SetString(PyExc_TypeError, 48 PyErr_SetString(PyExc_TypeError,
44 "the first argument must be callable"); 49 "the first argument must be callable");
45 return NULL; 50 return NULL;
46 } 51 }
47 52
48 /* create partialobject structure */ 53 /* create partialobject structure */
49 pto = (partialobject *)type->tp_alloc(type, 0); 54 pto = (partialobject *)type->tp_alloc(type, 0);
50 if (pto == NULL) 55 if (pto == NULL)
51 return NULL; 56 return NULL;
52 57
53 pto->fn = func; 58 pto->fn = func;
54 Py_INCREF(func); 59 Py_INCREF(func);
55 pto->args = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX); 60
56 if (pto->args == NULL) { 61 nargs = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX);
62 if (nargs == NULL) {
63 pto->args = NULL;
57 pto->kw = NULL; 64 pto->kw = NULL;
58 Py_DECREF(pto); 65 Py_DECREF(pto);
59 return NULL; 66 return NULL;
60 } 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
61 if (kw != NULL) { 86 if (kw != NULL) {
62 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 }
63 if (pto->kw == NULL) { 99 if (pto->kw == NULL) {
64 Py_DECREF(pto); 100 Py_DECREF(pto);
65 return NULL; 101 return NULL;
66 } 102 }
67 } else { 103 }
68 pto->kw = Py_None; 104 else {
69 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 }
70 } 116 }
71 117
72 pto->weakreflist = NULL; 118 pto->weakreflist = NULL;
73 pto->dict = NULL; 119 pto->dict = NULL;
74 120
75 return (PyObject *)pto; 121 return (PyObject *)pto;
76 } 122 }
77 123
78 static void 124 static void
79 partial_dealloc(partialobject *pto) 125 partial_dealloc(partialobject *pto)
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after
215 261
216 static PyObject * 262 static PyObject *
217 partial_reduce(partialobject *pto, PyObject *unused) 263 partial_reduce(partialobject *pto, PyObject *unused)
218 { 264 {
219 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,
220 pto->args, pto->kw, 266 pto->args, pto->kw,
221 pto->dict ? pto->dict : Py_None); 267 pto->dict ? pto->dict : Py_None);
222 } 268 }
223 269
224 static PyObject * 270 static PyObject *
225 partial_setstate(partialobject *pto, PyObject *args) 271 partial_setstate(partialobject *pto, PyObject *state)
226 { 272 {
227 PyObject *fn, *fnargs, *kw, *dict; 273 PyObject *fn, *fnargs, *kw, *dict;
228 if (!PyArg_ParseTuple(args, "(OOOO):__setstate__", 274 if (!PyArg_ParseTuple(state, "OOOO",
229 &fn, &fnargs, &kw, &dict)) 275 &fn, &fnargs, &kw, &dict))
230 return NULL; 276 return NULL;
231 Py_XDECREF(pto->fn); 277 Py_XDECREF(pto->fn);
232 Py_XDECREF(pto->args); 278 Py_XDECREF(pto->args);
233 Py_XDECREF(pto->kw); 279 Py_XDECREF(pto->kw);
234 Py_XDECREF(pto->dict); 280 Py_XDECREF(pto->dict);
235 pto->fn = fn; 281 pto->fn = fn;
236 pto->args = fnargs; 282 pto->args = fnargs;
237 pto->kw = kw; 283 pto->kw = kw;
238 if (dict != Py_None) { 284 if (dict != Py_None) {
239 pto->dict = dict; 285 pto->dict = dict;
240 Py_INCREF(dict); 286 Py_INCREF(dict);
241 } else { 287 } else {
242 pto->dict = NULL; 288 pto->dict = NULL;
243 } 289 }
244 Py_INCREF(fn); 290 Py_INCREF(fn);
245 Py_INCREF(fnargs); 291 Py_INCREF(fnargs);
246 Py_INCREF(kw); 292 Py_INCREF(kw);
247 Py_RETURN_NONE; 293 Py_RETURN_NONE;
248 } 294 }
249 295
250 static PyMethodDef partial_methods[] = { 296 static PyMethodDef partial_methods[] = {
251 {"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS}, 297 {"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS},
252 {"__setstate__", (PyCFunction)partial_setstate, METH_VARARGS}, 298 {"__setstate__", (PyCFunction)partial_setstate, METH_O},
253 {NULL, NULL} /* sentinel */ 299 {NULL, NULL} /* sentinel */
254 }; 300 };
255 301
256 static PyTypeObject partial_type = { 302 static PyTypeObject partial_type = {
257 PyVarObject_HEAD_INIT(NULL, 0) 303 PyVarObject_HEAD_INIT(NULL, 0)
258 "functools.partial", /* tp_name */ 304 "functools.partial", /* tp_name */
259 sizeof(partialobject), /* tp_basicsize */ 305 sizeof(partialobject), /* tp_basicsize */
260 0, /* tp_itemsize */ 306 0, /* tp_itemsize */
261 /* methods */ 307 /* methods */
262 (destructor)partial_dealloc, /* tp_dealloc */ 308 (destructor)partial_dealloc, /* tp_dealloc */
(...skipping 277 matching lines...) Expand 10 before | Expand all | Expand 10 after
540 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\
541 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\
542 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\
543 ((((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\
544 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\
545 sequence is empty."); 591 sequence is empty.");
546 592
547 /* lru_cache object **********************************************************/ 593 /* lru_cache object **********************************************************/
548 594
549 /* 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 */
550 static PyObject *kwd_mark; 596 static PyObject *kwd_mark = NULL;
551 597
552 struct lru_list_elem; 598 struct lru_list_elem;
553 struct lru_cache_object; 599 struct lru_cache_object;
554 600
555 typedef struct lru_list_elem { 601 typedef struct lru_list_elem {
556 struct lru_list_elem *prev, *next; 602 PyObject_HEAD
603 struct lru_list_elem *prev, *next; /* borrowed links */
557 PyObject *key, *result; 604 PyObject *key, *result;
558 } lru_list_elem; 605 } lru_list_elem;
559 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
560 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *); 660 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *);
561 661
562 typedef struct lru_cache_object { 662 typedef struct lru_cache_object {
563 PyObject_HEAD 663 lru_list_elem root; /* includes PyObject_HEAD */
564 Py_ssize_t maxsize; 664 Py_ssize_t maxsize;
565 PyObject *maxsize_O; 665 PyObject *maxsize_O;
566 PyObject *func; 666 PyObject *func;
567 lru_cache_ternaryfunc wrapper; 667 lru_cache_ternaryfunc wrapper;
568 PyObject *cache; 668 PyObject *cache;
569 PyObject *cache_info_type; 669 PyObject *cache_info_type;
570 Py_ssize_t misses, hits; 670 Py_ssize_t misses, hits;
571 lru_list_elem root;
572 int typed; 671 int typed;
573 PyObject *dict; 672 PyObject *dict;
574 #ifdef WITH_THREAD 673 int full;
575 PyThread_type_lock lock;
576 #endif
577 } lru_cache_object; 674 } lru_cache_object;
578 675
579 static PyTypeObject lru_cache_type; 676 static PyTypeObject lru_cache_type;
580 677
581 static PyObject * 678 static PyObject *
582 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed) 679 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
583 { 680 {
584 PyObject *key, *sorted_items; 681 PyObject *key, *sorted_items;
585 Py_ssize_t key_size, pos, key_pos; 682 Py_ssize_t key_size, pos, key_pos;
586 683
587 /* short path, key will match args anyway, which is a tuple */ 684 /* short path, key will match args anyway, which is a tuple */
588 if (!typed && !kwds) { 685 if (!typed && !kwds) {
589 Py_INCREF(args); 686 Py_INCREF(args);
590 return args; 687 return args;
591 } 688 }
592 689
593 if (kwds && PyDict_Size(kwds) > 0) { 690 if (kwds && PyDict_Size(kwds) > 0) {
594 sorted_items = PyDict_Items(kwds); 691 sorted_items = PyDict_Items(kwds);
595 if (!sorted_items) 692 if (!sorted_items)
596 return NULL; 693 return NULL;
597 if (PyList_Sort(sorted_items) < 0) { 694 if (PyList_Sort(sorted_items) < 0) {
598 Py_DECREF(sorted_items); 695 Py_DECREF(sorted_items);
599 return NULL; 696 return NULL;
600 } 697 }
601 } else 698 } else
602 sorted_items = NULL; 699 sorted_items = NULL;
603 700
604 key_size = PyTuple_GET_SIZE(args); 701 key_size = PyTuple_GET_SIZE(args);
605 if (kwds) 702 if (sorted_items)
storchaka 2012/12/30 18:09:43 Now you should check sorted_items instead of kwds.
606 key_size += PyList_GET_SIZE(sorted_items); 703 key_size += PyList_GET_SIZE(sorted_items);
607 if (typed) 704 if (typed)
608 key_size *= 2; 705 key_size *= 2;
609 if (kwds) 706 if (sorted_items)
610 key_size++; 707 key_size++;
611 708
612 key = PyTuple_New(key_size); 709 key = PyTuple_New(key_size);
710 if (key == NULL)
711 goto done;
712
613 key_pos = 0; 713 key_pos = 0;
614
615 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 714 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
616 PyObject *item = PyTuple_GET_ITEM(args, pos); 715 PyObject *item = PyTuple_GET_ITEM(args, pos);
617 Py_INCREF(item); 716 Py_INCREF(item);
618 PyTuple_SET_ITEM(key, key_pos++, item); 717 PyTuple_SET_ITEM(key, key_pos++, item);
619 } 718 }
620 if (kwds) { 719 if (sorted_items) {
621 Py_INCREF(kwd_mark); 720 Py_INCREF(kwd_mark);
622 PyTuple_SET_ITEM(key, key_pos++, kwd_mark); 721 PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
623 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 722 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
624 PyObject *item = PyList_GET_ITEM(sorted_items, pos); 723 PyObject *item = PyList_GET_ITEM(sorted_items, pos);
625 Py_INCREF(item); 724 Py_INCREF(item);
626 PyTuple_SET_ITEM(key, key_pos++, item); 725 PyTuple_SET_ITEM(key, key_pos++, item);
627 } 726 }
628 } 727 }
629 if (typed) { 728 if (typed) {
630 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 729 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
631 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos)); 730 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
632 Py_INCREF(item); 731 Py_INCREF(item);
633 PyTuple_SET_ITEM(key, key_pos++, item); 732 PyTuple_SET_ITEM(key, key_pos++, item);
634 } 733 }
635 if (kwds) { 734 if (sorted_items) {
636 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 735 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
637 PyObject *tp_items = PyList_GET_ITEM(sorted_items, pos); 736 PyObject *tp_items = PyList_GET_ITEM(sorted_items, pos);
638 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(tp_items, 1)); 737 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(tp_items, 1));
639 Py_INCREF(item); 738 Py_INCREF(item);
640 PyTuple_SET_ITEM(key, key_pos++, item); 739 PyTuple_SET_ITEM(key, key_pos++, item);
641 } 740 }
642 } 741 }
643 } 742 }
644 assert(key_pos == key_size); 743 assert(key_pos == key_size);
645 744
646 if (kwds) 745 done:
746 if (sorted_items)
647 Py_DECREF(sorted_items); 747 Py_DECREF(sorted_items);
648 return key; 748 return key;
649 } 749 }
650 750
651 static PyObject * 751 static PyObject *
652 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)
653 { 753 {
654 PyObject *result = PyObject_Call(self->func, args, kwds); 754 PyObject *result = PyObject_Call(self->func, args, kwds);
655 if (!result) 755 if (!result)
656 return NULL; 756 return NULL;
(...skipping 28 matching lines...) Expand all
685 Py_DECREF(result); 785 Py_DECREF(result);
686 Py_DECREF(key); 786 Py_DECREF(key);
687 return NULL; 787 return NULL;
688 } 788 }
689 Py_DECREF(key); 789 Py_DECREF(key);
690 self->misses++; 790 self->misses++;
691 return result; 791 return result;
692 } 792 }
693 793
694 static void 794 static void
695 lru_cache_list_extricate(lru_list_elem *link) 795 lru_cache_extricate_link(lru_list_elem *link)
696 { 796 {
697 link->prev->next = link->next; 797 link->prev->next = link->next;
698 link->next->prev = link->prev; 798 link->next->prev = link->prev;
699 } 799 }
700 800
701 static void 801 static void
702 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)
703 { 803 {
804 lru_list_elem *root = &self->root;
704 lru_list_elem *last = root->prev; 805 lru_list_elem *last = root->prev;
705 last->next = root->prev = link; 806 last->next = root->prev = link;
706 link->prev = last; 807 link->prev = last;
707 link->next = root; 808 link->next = root;
708 } 809 }
709 810
710 static PyObject * 811 static PyObject *
711 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 )
712 { 813 {
713 lru_list_elem *link; 814 lru_list_elem *link;
714 PyObject *key, *value, *result; 815 PyObject *key, *result;
715 816
716 key = lru_cache_make_key(args, kwds, self->typed); 817 key = lru_cache_make_key(args, kwds, self->typed);
717 if (!key) 818 if (!key)
718 return NULL; 819 return NULL;
719 value = PyDict_GetItemWithError(self->cache, key); 820 link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
720 if (value) { 821 if (link) {
721 lru_list_elem *link = PyCapsule_GetPointer(value, NULL); 822 lru_cache_extricate_link(link);
722 lru_cache_list_extricate(link); 823 lru_cache_append_link(self, link);
723 lru_cache_list_append(&self->root, link);
724 self->hits++; 824 self->hits++;
825 result = link->result;
826 Py_INCREF(result);
725 Py_DECREF(key); 827 Py_DECREF(key);
726 Py_INCREF(link->result); 828 return result;
727 return link->result;
728 } 829 }
729 if (PyErr_Occurred()) { 830 if (PyErr_Occurred()) {
730 Py_DECREF(key); 831 Py_DECREF(key);
731 return NULL; 832 return NULL;
732 } 833 }
733 result = PyObject_Call(self->func, args, kwds); 834 result = PyObject_Call(self->func, args, kwds);
734 if (!result) { 835 if (!result) {
735 Py_DECREF(key); 836 Py_DECREF(key);
736 return NULL; 837 return NULL;
737 } 838 }
738 if (PyDict_Size(self->cache) == self->maxsize) { 839 if (self->full && self->root.next != &self->root) {
739 /* 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. */
740 link = self->root.next; 843 link = self->root.next;
741 lru_cache_list_extricate(link); 844 lru_cache_extricate_link(link);
742 /* grab its capsule */ 845 /* Remove it from the cache.
743 value = PyDict_GetItem(self->cache, link->key); 846 The cache dict holds one reference to the link,
744 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);
745 Py_DECREF(key); 850 Py_DECREF(key);
746 return NULL; 851 Py_DECREF(result);
747 } 852 return NULL;
748 Py_INCREF(value); 853 }
749 /* remove its key from the cache */ 854 /* Keep a reference to the old key and old result to
750 if (PyDict_DelItem(self->cache, link->key) < 0) { 855 prevent their ref counts from going to zero during the
751 Py_DECREF(value); 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) {
752 Py_DECREF(key); 879 Py_DECREF(key);
753 return NULL; 880 Py_DECREF(result);
754 } 881 return NULL;
755 /* scrub the result from the link */ 882 }
756 Py_DECREF(link->result); 883
757 } else { 884 link->key = key;
758 link = PyMem_New(lru_list_elem, 1); 885 link->result = result;
759 if (link == NULL) { 886 _PyObject_GC_TRACK(link);
760 PyErr_NoMemory(); 887 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
761 return NULL; 888 Py_DECREF(link);
762 } 889 return NULL;
763 value = PyCapsule_New(link, NULL, NULL); 890 }
764 if (value == NULL) 891 lru_cache_append_link(self, link);
765 return NULL; 892 Py_INCREF(result); /* for return */
storchaka 2012/12/30 18:09:43 Don't forget release the "link".
766 } 893 self->full = (PyDict_Size(self->cache) >= self->maxsize);
767 lru_cache_list_append(&self->root, link); 894 }
768 link->key = key;
769 Py_INCREF(result);
770 link->result = result;
771 if (PyDict_SetItem(self->cache, key, value) < 0) {
772 return NULL;
773 }
774 Py_DECREF(key);
775 Py_DECREF(value);
776 self->misses++; 895 self->misses++;
777 return result; 896 return result;
778 } 897 }
779 898
780 static PyObject * 899 static PyObject *
781 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) 900 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
782 { 901 {
783 PyObject *func, *maxsize_O, *cache_info_type; 902 PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
784 int typed; 903 int typed;
785 lru_cache_object *obj; 904 lru_cache_object *obj;
786 Py_ssize_t maxsize; 905 Py_ssize_t maxsize;
787 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *); 906 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
788 static char *keywords[] = {"user_function", "maxsize", "typed", 907 static char *keywords[] = {"user_function", "maxsize", "typed",
789 "cache_info_type", NULL}; 908 "cache_info_type", NULL};
790 909
791 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords, 910 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
792 &func, &maxsize_O, &typed, 911 &func, &maxsize_O, &typed,
793 &cache_info_type)) { 912 &cache_info_type)) {
794 return NULL; 913 return NULL;
795 } 914 }
796 915
797 if (!PyCallable_Check(func)) { 916 if (!PyCallable_Check(func)) {
798 PyErr_SetString(PyExc_TypeError, 917 PyErr_SetString(PyExc_TypeError,
799 "the first argument must be callable"); 918 "the first argument must be callable");
800 return NULL; 919 return NULL;
801 } 920 }
802 921
803 /* select the caching function, and make/inc maxsize_O */ 922 /* select the caching function, and make/inc maxsize_O */
804 if (maxsize_O == Py_None) { 923 if (maxsize_O == Py_None) {
805 wrapper = infinite_lru_cache_wrapper; 924 wrapper = infinite_lru_cache_wrapper;
806 /* use this only to initialize lru_cache_object attribute maxsize */ 925 /* use this only to initialize lru_cache_object attribute maxsize */
807 maxsize = -1; 926 maxsize = -1;
808 } else if (PyNumber_Check(maxsize_O)) { 927 } else if (PyIndex_Check(maxsize_O)) {
809 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError); 928 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
810 if (maxsize == -1 && PyErr_Occurred()) 929 if (maxsize == -1 && PyErr_Occurred())
811 return NULL; 930 return NULL;
812 if (maxsize == 0) 931 if (maxsize == 0)
813 wrapper = uncached_lru_cache_wrapper; 932 wrapper = uncached_lru_cache_wrapper;
814 else 933 else
815 wrapper = bounded_lru_cache_wrapper; 934 wrapper = bounded_lru_cache_wrapper;
816 } else { 935 } else {
817 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None"); 936 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
818 return NULL; 937 return NULL;
819 } 938 }
820 939
940 if (!(cachedict = PyDict_New()))
941 return NULL;
942
821 obj = (lru_cache_object *)type->tp_alloc(type, 0); 943 obj = (lru_cache_object *)type->tp_alloc(type, 0);
822 if (obj == NULL) 944 if (obj == NULL) {
823 return NULL; 945 Py_DECREF(cachedict);
824 946 return NULL;
947 }
948
949 obj->cache = cachedict;
825 obj->root.prev = &obj->root; 950 obj->root.prev = &obj->root;
826 obj->root.next = &obj->root; 951 obj->root.next = &obj->root;
827 obj->maxsize = maxsize; 952 obj->maxsize = maxsize;
828 Py_INCREF(maxsize_O); 953 Py_INCREF(maxsize_O);
829 obj->maxsize_O = maxsize_O; 954 obj->maxsize_O = maxsize_O;
830 if (!(obj->cache = PyDict_New())) {
831 Py_DECREF(obj);
832 Py_DECREF(maxsize_O);
833 return NULL;
834 }
835 Py_INCREF(func); 955 Py_INCREF(func);
836 obj->func = func; 956 obj->func = func;
837 obj->wrapper = wrapper; 957 obj->wrapper = wrapper;
838 obj->misses = obj->hits = 0; 958 obj->misses = obj->hits = 0;
839 obj->typed = typed; 959 obj->typed = typed;
840 Py_INCREF(cache_info_type); 960 Py_INCREF(cache_info_type);
841 obj->cache_info_type = cache_info_type; 961 obj->cache_info_type = cache_info_type;
842 962
843 #ifdef WITH_THREAD
844 obj->lock = PyThread_allocate_lock();
845 if (obj->lock == NULL) {
846 PyErr_SetString(PyExc_MemoryError, "Unable to allocate lock");
847 return NULL;
storchaka 2012/12/30 18:09:43 Some objects leak here.
848 }
849 #endif
850
851 return (PyObject *)obj; 963 return (PyObject *)obj;
852 } 964 }
853 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
854 static void 978 static void
855 lru_cache_clear_list(lru_list_elem *root) 979 lru_cache_clear_list(lru_list_elem *link)
856 { 980 {
857 lru_list_elem *link = root->next; 981 while (link != NULL) {
858 while (link != root) {
859 lru_list_elem *next = link->next; 982 lru_list_elem *next = link->next;
860 Py_DECREF(link->result); 983 Py_DECREF(link);
861 PyMem_Free(link);
862 link = next; 984 link = next;
863 } 985 }
864 } 986 }
865 987
866 static void 988 static void
867 lru_cache_dealloc(lru_cache_object *obj) 989 lru_cache_dealloc(lru_cache_object *obj)
868 { 990 {
991 lru_list_elem *list = lru_cache_unlink_list(obj);
869 Py_XDECREF(obj->maxsize_O); 992 Py_XDECREF(obj->maxsize_O);
870 Py_XDECREF(obj->func); 993 Py_XDECREF(obj->func);
871 Py_XDECREF(obj->cache); 994 Py_XDECREF(obj->cache);
872 Py_XDECREF(obj->dict); 995 Py_XDECREF(obj->dict);
873 Py_XDECREF(obj->cache_info_type); 996 Py_XDECREF(obj->cache_info_type);
874 #ifdef WITH_THREAD 997 lru_cache_clear_list(list);
875 do {
876 if (!PyThread_acquire_lock(obj->lock, 0)) {
877 Py_BEGIN_ALLOW_THREADS;
878 PyThread_acquire_lock(obj->lock, 1);
879 Py_END_ALLOW_THREADS;
880 }
881 } while (0);
882 #endif
883 lru_cache_clear_list(&obj->root);
884 #ifdef WITH_THREAD
885 PyThread_release_lock(obj->lock);
886 PyThread_free_lock(obj->lock);
887 Py_XDECREF(obj->lock);
888 #endif
889 Py_TYPE(obj)->tp_free(obj); 998 Py_TYPE(obj)->tp_free(obj);
890 } 999 }
891 1000
892 static PyObject * 1001 static PyObject *
893 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) 1002 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
894 { 1003 {
895 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);
896 } 1015 }
897 1016
898 static PyObject * 1017 static PyObject *
899 lru_cache_cache_info(lru_cache_object *self, PyObject *unused) 1018 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
900 { 1019 {
901 return PyObject_CallFunction(self->cache_info_type, "nnOn", 1020 return PyObject_CallFunction(self->cache_info_type, "nnOn",
902 self->hits, self->misses, self->maxsize_O, 1021 self->hits, self->misses, self->maxsize_O,
903 PyDict_Size(self->cache)); 1022 PyDict_Size(self->cache));
904 } 1023 }
905 1024
906 static PyObject * 1025 static PyObject *
907 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) 1026 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
908 { 1027 {
909 #ifdef WITH_THREAD 1028 lru_list_elem *list = lru_cache_unlink_list(self);
910 do {
911 if (!PyThread_acquire_lock(self->lock, 0)) {
912 Py_BEGIN_ALLOW_THREADS;
913 PyThread_acquire_lock(self->lock, 1);
914 Py_END_ALLOW_THREADS;
915 }
916 } while (0);
storchaka 2012/12/30 18:09:43 What's the point of this?
917 #endif
918 PyDict_Clear(self->cache);
919 self->hits = self->misses = 0; 1029 self->hits = self->misses = 0;
920 lru_cache_clear_list(&self->root); 1030 self->full = 0;
921 self->root.next = self->root.prev = &self->root; 1031 PyDict_Clear(self->cache);
922 #ifdef WITH_THREAD 1032 lru_cache_clear_list(list);
923 PyThread_release_lock(self->lock);
924 #endif
925 Py_RETURN_NONE; 1033 Py_RETURN_NONE;
926 } 1034 }
927 1035
928 static int 1036 static int
929 lru_cache_traverse(lru_cache_object *self, visitproc visit, void *arg) 1037 lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
930 { 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 }
931 Py_VISIT(self->maxsize_O); 1045 Py_VISIT(self->maxsize_O);
932 Py_VISIT(self->func); 1046 Py_VISIT(self->func);
933 Py_VISIT(self->cache); 1047 Py_VISIT(self->cache);
934 Py_VISIT(self->cache_info_type); 1048 Py_VISIT(self->cache_info_type);
935 Py_VISIT(self->dict); 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);
936 return 0; 1063 return 0;
937 } 1064 }
938 1065
939 1066
940 PyDoc_STRVAR(lru_cache_doc, 1067 PyDoc_STRVAR(lru_cache_doc,
941 "Create a cached callable that wraps another function.\n\ 1068 "Create a cached callable that wraps another function.\n\
942 \n\ 1069 \n\
943 user_function: the function being cached\n\ 1070 user_function: the function being cached\n\
944 \n\ 1071 \n\
945 maxsize: 0 for no caching\n\ 1072 maxsize: 0 for no caching\n\
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after
981 0, /* tp_as_mapping */ 1108 0, /* tp_as_mapping */
982 0, /* tp_hash */ 1109 0, /* tp_hash */
983 (ternaryfunc)lru_cache_call, /* tp_call */ 1110 (ternaryfunc)lru_cache_call, /* tp_call */
984 0, /* tp_str */ 1111 0, /* tp_str */
985 0, /* tp_getattro */ 1112 0, /* tp_getattro */
986 0, /* tp_setattro */ 1113 0, /* tp_setattro */
987 0, /* tp_as_buffer */ 1114 0, /* tp_as_buffer */
988 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC, 1115 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC,
989 /* tp_flags */ 1116 /* tp_flags */
990 lru_cache_doc, /* tp_doc */ 1117 lru_cache_doc, /* tp_doc */
991 (traverseproc)lru_cache_traverse, /* tp_traverse */ 1118 (traverseproc)lru_cache_tp_traverse,/* tp_traverse */
992 0, /* tp_clear */ 1119 (inquiry)lru_cache_tp_clear, /* tp_clear */
storchaka 2012/12/30 18:09:43 Shouldn't tp_clear be defined for GC-enabled types
993 0, /* tp_richcompare */ 1120 0, /* tp_richcompare */
994 0, /* tp_weaklistoffset */ 1121 0, /* tp_weaklistoffset */
995 0, /* tp_iter */ 1122 0, /* tp_iter */
996 0, /* tp_iternext */ 1123 0, /* tp_iternext */
997 lru_cache_methods, /* tp_methods */ 1124 lru_cache_methods, /* tp_methods */
998 0, /* tp_members */ 1125 0, /* tp_members */
999 lru_cache_getsetlist, /* tp_getset */ 1126 lru_cache_getsetlist, /* tp_getset */
1000 0, /* tp_base */ 1127 0, /* tp_base */
1001 0, /* tp_dict */ 1128 0, /* tp_dict */
1002 0, /* tp_descr_get */ 1129 lru_cache_descr_get, /* tp_descr_get */
1003 0, /* tp_descr_set */ 1130 0, /* tp_descr_set */
1004 offsetof(lru_cache_object, dict), /* tp_dictoffset */ 1131 offsetof(lru_cache_object, dict), /* tp_dictoffset */
1005 0, /* tp_init */ 1132 0, /* tp_init */
1006 0, /* tp_alloc */ 1133 0, /* tp_alloc */
1007 lru_cache_new, /* tp_new */ 1134 lru_cache_new, /* tp_new */
1008 }; 1135 };
1009 1136
1010 /* module level code ********************************************************/ 1137 /* module level code ********************************************************/
1011 1138
1012 PyDoc_STRVAR(module_doc, 1139 PyDoc_STRVAR(module_doc,
1013 "Tools that operate on functions."); 1140 "Tools that operate on functions.");
1014 1141
1015 static PyMethodDef module_methods[] = { 1142 static PyMethodDef module_methods[] = {
1016 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 1143 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
1017 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 1144 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
1018 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 1145 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
1019 {NULL, NULL} /* sentinel */ 1146 {NULL, NULL} /* sentinel */
1020 }; 1147 };
1021 1148
1022 static void 1149 static void
1023 module_free(void *m) 1150 module_free(void *m)
1024 { 1151 {
1025 Py_DECREF(kwd_mark); 1152 Py_CLEAR(kwd_mark);
1026 } 1153 }
1027 1154
1028 static struct PyModuleDef _functoolsmodule = { 1155 static struct PyModuleDef _functoolsmodule = {
1029 PyModuleDef_HEAD_INIT, 1156 PyModuleDef_HEAD_INIT,
1030 "_functools", 1157 "_functools",
1031 module_doc, 1158 module_doc,
1032 -1, 1159 -1,
1033 module_methods, 1160 module_methods,
1034 NULL, 1161 NULL,
1035 NULL, 1162 NULL,
(...skipping 28 matching lines...) Expand all
1064 Py_DECREF(m); 1191 Py_DECREF(m);
1065 return NULL; 1192 return NULL;
1066 } 1193 }
1067 name = strchr(typelist[i]->tp_name, '.'); 1194 name = strchr(typelist[i]->tp_name, '.');
1068 assert (name != NULL); 1195 assert (name != NULL);
1069 Py_INCREF(typelist[i]); 1196 Py_INCREF(typelist[i]);
1070 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1197 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
1071 } 1198 }
1072 return m; 1199 return m;
1073 } 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+