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

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Left Patch Set: Created 6 years, 10 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
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
(...skipping 16 matching lines...) Expand all
603 700
604 key_size = PyTuple_GET_SIZE(args); 701 key_size = PyTuple_GET_SIZE(args);
605 if (sorted_items) 702 if (sorted_items)
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 (sorted_items) 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 (sorted_items) { 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);
(...skipping 11 matching lines...) Expand all
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
745 done:
646 if (sorted_items) 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)
(...skipping 29 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;
762 }
763 value = PyCapsule_New(link, NULL, NULL);
764 if (value == NULL) {
765 Py_DECREF(link); 888 Py_DECREF(link);
766 return NULL; 889 return NULL;
767 } 890 }
768 } 891 lru_cache_append_link(self, link);
769 lru_cache_list_append(&self->root, link); 892 Py_INCREF(result); /* for return */
770 link->key = key; 893 self->full = (PyDict_Size(self->cache) >= self->maxsize);
771 Py_INCREF(result); 894 }
772 link->result = result;
773 if (PyDict_SetItem(self->cache, key, value) < 0) {
774 return NULL;
775 }
776 Py_DECREF(key);
777 Py_DECREF(value);
778 self->misses++; 895 self->misses++;
779 return result; 896 return result;
780 } 897 }
781 898
782 static PyObject * 899 static PyObject *
783 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) 900 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
784 { 901 {
785 PyObject *func, *maxsize_O, *cache_info_type; 902 PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
786 int typed; 903 int typed;
787 lru_cache_object *obj; 904 lru_cache_object *obj;
788 Py_ssize_t maxsize; 905 Py_ssize_t maxsize;
789 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *); 906 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
790 static char *keywords[] = {"user_function", "maxsize", "typed", 907 static char *keywords[] = {"user_function", "maxsize", "typed",
791 "cache_info_type", NULL}; 908 "cache_info_type", NULL};
792 909
793 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords, 910 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
794 &func, &maxsize_O, &typed, 911 &func, &maxsize_O, &typed,
795 &cache_info_type)) { 912 &cache_info_type)) {
796 return NULL; 913 return NULL;
797 } 914 }
798 915
799 if (!PyCallable_Check(func)) { 916 if (!PyCallable_Check(func)) {
800 PyErr_SetString(PyExc_TypeError, 917 PyErr_SetString(PyExc_TypeError,
801 "the first argument must be callable"); 918 "the first argument must be callable");
802 return NULL; 919 return NULL;
803 } 920 }
804 921
805 /* select the caching function, and make/inc maxsize_O */ 922 /* select the caching function, and make/inc maxsize_O */
806 if (maxsize_O == Py_None) { 923 if (maxsize_O == Py_None) {
807 wrapper = infinite_lru_cache_wrapper; 924 wrapper = infinite_lru_cache_wrapper;
808 /* use this only to initialize lru_cache_object attribute maxsize */ 925 /* use this only to initialize lru_cache_object attribute maxsize */
809 maxsize = -1; 926 maxsize = -1;
810 } else if (PyNumber_Check(maxsize_O)) { 927 } else if (PyIndex_Check(maxsize_O)) {
811 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError); 928 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
812 if (maxsize == -1 && PyErr_Occurred()) 929 if (maxsize == -1 && PyErr_Occurred())
813 return NULL; 930 return NULL;
814 if (maxsize == 0) 931 if (maxsize == 0)
815 wrapper = uncached_lru_cache_wrapper; 932 wrapper = uncached_lru_cache_wrapper;
816 else 933 else
817 wrapper = bounded_lru_cache_wrapper; 934 wrapper = bounded_lru_cache_wrapper;
818 } else { 935 } else {
819 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None"); 936 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
820 return NULL; 937 return NULL;
821 } 938 }
822 939
940 if (!(cachedict = PyDict_New()))
941 return NULL;
942
823 obj = (lru_cache_object *)type->tp_alloc(type, 0); 943 obj = (lru_cache_object *)type->tp_alloc(type, 0);
824 if (obj == NULL) 944 if (obj == NULL) {
825 return NULL; 945 Py_DECREF(cachedict);
826 946 return NULL;
827 #ifdef WITH_THREAD 947 }
828 obj->lock = PyThread_allocate_lock(); 948
829 if (obj->lock == NULL) { 949 obj->cache = cachedict;
830 PyErr_SetString(PyExc_MemoryError, "Unable to allocate lock");
831 Py_DECREF(obj);
832 return NULL;
833 }
834 #endif
835
836 if (!(obj->cache = PyDict_New())) {
837 Py_DECREF(obj);
838 return NULL;
839 }
840
841 obj->root.prev = &obj->root; 950 obj->root.prev = &obj->root;
842 obj->root.next = &obj->root; 951 obj->root.next = &obj->root;
843 obj->maxsize = maxsize; 952 obj->maxsize = maxsize;
844 Py_INCREF(maxsize_O); 953 Py_INCREF(maxsize_O);
845 obj->maxsize_O = maxsize_O; 954 obj->maxsize_O = maxsize_O;
846 Py_INCREF(func); 955 Py_INCREF(func);
847 obj->func = func; 956 obj->func = func;
848 obj->wrapper = wrapper; 957 obj->wrapper = wrapper;
849 obj->misses = obj->hits = 0; 958 obj->misses = obj->hits = 0;
850 obj->typed = typed; 959 obj->typed = typed;
851 Py_INCREF(cache_info_type); 960 Py_INCREF(cache_info_type);
852 obj->cache_info_type = cache_info_type; 961 obj->cache_info_type = cache_info_type;
853 962
854 return (PyObject *)obj; 963 return (PyObject *)obj;
855 } 964 }
856 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
857 static void 978 static void
858 lru_cache_clear_list(lru_list_elem *root) 979 lru_cache_clear_list(lru_list_elem *link)
859 { 980 {
860 lru_list_elem *link = root->next; 981 while (link != NULL) {
861 while (link != root) {
862 lru_list_elem *next = link->next; 982 lru_list_elem *next = link->next;
863 Py_DECREF(link->result); 983 Py_DECREF(link);
864 PyMem_Free(link);
865 link = next; 984 link = next;
866 } 985 }
867 } 986 }
868 987
869 static void 988 static void
870 lru_cache_dealloc(lru_cache_object *obj) 989 lru_cache_dealloc(lru_cache_object *obj)
871 { 990 {
991 lru_list_elem *list = lru_cache_unlink_list(obj);
872 Py_XDECREF(obj->maxsize_O); 992 Py_XDECREF(obj->maxsize_O);
873 Py_XDECREF(obj->func); 993 Py_XDECREF(obj->func);
874 Py_XDECREF(obj->cache); 994 Py_XDECREF(obj->cache);
875 Py_XDECREF(obj->dict); 995 Py_XDECREF(obj->dict);
876 Py_XDECREF(obj->cache_info_type); 996 Py_XDECREF(obj->cache_info_type);
877 #ifdef WITH_THREAD 997 lru_cache_clear_list(list);
878 if (!PyThread_acquire_lock(obj->lock, 0)) {
879 Py_BEGIN_ALLOW_THREADS;
880 PyThread_acquire_lock(obj->lock, 1);
881 Py_END_ALLOW_THREADS;
882 }
883 #endif
884 lru_cache_clear_list(&obj->root);
885 #ifdef WITH_THREAD
886 PyThread_release_lock(obj->lock);
887 PyThread_free_lock(obj->lock);
888 Py_XDECREF(obj->lock);
889 #endif
890 Py_TYPE(obj)->tp_free(obj); 998 Py_TYPE(obj)->tp_free(obj);
891 } 999 }
892 1000
893 static PyObject * 1001 static PyObject *
894 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) 1002 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
895 { 1003 {
896 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);
897 } 1015 }
898 1016
899 static PyObject * 1017 static PyObject *
900 lru_cache_cache_info(lru_cache_object *self, PyObject *unused) 1018 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
901 { 1019 {
902 return PyObject_CallFunction(self->cache_info_type, "nnOn", 1020 return PyObject_CallFunction(self->cache_info_type, "nnOn",
903 self->hits, self->misses, self->maxsize_O, 1021 self->hits, self->misses, self->maxsize_O,
904 PyDict_Size(self->cache)); 1022 PyDict_Size(self->cache));
905 } 1023 }
906 1024
907 static PyObject * 1025 static PyObject *
908 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) 1026 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
909 { 1027 {
910 #ifdef WITH_THREAD 1028 lru_list_elem *list = lru_cache_unlink_list(self);
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 #endif
917 PyDict_Clear(self->cache);
918 self->hits = self->misses = 0; 1029 self->hits = self->misses = 0;
919 lru_cache_clear_list(&self->root); 1030 self->full = 0;
920 self->root.next = self->root.prev = &self->root; 1031 PyDict_Clear(self->cache);
921 #ifdef WITH_THREAD 1032 lru_cache_clear_list(list);
922 PyThread_release_lock(self->lock);
923 #endif
924 Py_RETURN_NONE; 1033 Py_RETURN_NONE;
925 } 1034 }
926 1035
927 static int 1036 static int
928 lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg) 1037 lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
929 { 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 }
930 Py_VISIT(self->maxsize_O); 1045 Py_VISIT(self->maxsize_O);
931 Py_VISIT(self->func); 1046 Py_VISIT(self->func);
932 Py_VISIT(self->cache); 1047 Py_VISIT(self->cache);
933 Py_VISIT(self->cache_info_type); 1048 Py_VISIT(self->cache_info_type);
934 Py_VISIT(self->dict); 1049 Py_VISIT(self->dict);
935 return 0; 1050 return 0;
936 } 1051 }
937 1052
938 static int 1053 static int
939 lru_cache_tp_clear(lru_cache_object *self) 1054 lru_cache_tp_clear(lru_cache_object *self)
940 { 1055 {
1056 lru_list_elem *list = lru_cache_unlink_list(self);
941 Py_CLEAR(self->maxsize_O); 1057 Py_CLEAR(self->maxsize_O);
942 Py_CLEAR(self->func); 1058 Py_CLEAR(self->func);
943 Py_CLEAR(self->cache); 1059 Py_CLEAR(self->cache);
944 Py_CLEAR(self->cache_info_type); 1060 Py_CLEAR(self->cache_info_type);
945 Py_CLEAR(self->dict); 1061 Py_CLEAR(self->dict);
1062 lru_cache_clear_list(list);
946 return 0; 1063 return 0;
947 } 1064 }
948 1065
949 1066
950 PyDoc_STRVAR(lru_cache_doc, 1067 PyDoc_STRVAR(lru_cache_doc,
951 "Create a cached callable that wraps another function.\n\ 1068 "Create a cached callable that wraps another function.\n\
952 \n\ 1069 \n\
953 user_function: the function being cached\n\ 1070 user_function: the function being cached\n\
954 \n\ 1071 \n\
955 maxsize: 0 for no caching\n\ 1072 maxsize: 0 for no caching\n\
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
1002 (inquiry)lru_cache_tp_clear, /* tp_clear */ 1119 (inquiry)lru_cache_tp_clear, /* tp_clear */
1003 0, /* tp_richcompare */ 1120 0, /* tp_richcompare */
1004 0, /* tp_weaklistoffset */ 1121 0, /* tp_weaklistoffset */
1005 0, /* tp_iter */ 1122 0, /* tp_iter */
1006 0, /* tp_iternext */ 1123 0, /* tp_iternext */
1007 lru_cache_methods, /* tp_methods */ 1124 lru_cache_methods, /* tp_methods */
1008 0, /* tp_members */ 1125 0, /* tp_members */
1009 lru_cache_getsetlist, /* tp_getset */ 1126 lru_cache_getsetlist, /* tp_getset */
1010 0, /* tp_base */ 1127 0, /* tp_base */
1011 0, /* tp_dict */ 1128 0, /* tp_dict */
1012 0, /* tp_descr_get */ 1129 lru_cache_descr_get, /* tp_descr_get */
1013 0, /* tp_descr_set */ 1130 0, /* tp_descr_set */
1014 offsetof(lru_cache_object, dict), /* tp_dictoffset */ 1131 offsetof(lru_cache_object, dict), /* tp_dictoffset */
1015 0, /* tp_init */ 1132 0, /* tp_init */
1016 0, /* tp_alloc */ 1133 0, /* tp_alloc */
1017 lru_cache_new, /* tp_new */ 1134 lru_cache_new, /* tp_new */
1018 }; 1135 };
1019 1136
1020 /* module level code ********************************************************/ 1137 /* module level code ********************************************************/
1021 1138
1022 PyDoc_STRVAR(module_doc, 1139 PyDoc_STRVAR(module_doc,
1023 "Tools that operate on functions."); 1140 "Tools that operate on functions.");
1024 1141
1025 static PyMethodDef module_methods[] = { 1142 static PyMethodDef module_methods[] = {
1026 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 1143 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
1027 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 1144 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
1028 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 1145 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
1029 {NULL, NULL} /* sentinel */ 1146 {NULL, NULL} /* sentinel */
1030 }; 1147 };
1031 1148
1032 static void 1149 static void
1033 module_free(void *m) 1150 module_free(void *m)
1034 { 1151 {
1035 Py_DECREF(kwd_mark); 1152 Py_CLEAR(kwd_mark);
1036 } 1153 }
1037 1154
1038 static struct PyModuleDef _functoolsmodule = { 1155 static struct PyModuleDef _functoolsmodule = {
1039 PyModuleDef_HEAD_INIT, 1156 PyModuleDef_HEAD_INIT,
1040 "_functools", 1157 "_functools",
1041 module_doc, 1158 module_doc,
1042 -1, 1159 -1,
1043 module_methods, 1160 module_methods,
1044 NULL, 1161 NULL,
1045 NULL, 1162 NULL,
(...skipping 28 matching lines...) Expand all
1074 Py_DECREF(m); 1191 Py_DECREF(m);
1075 return NULL; 1192 return NULL;
1076 } 1193 }
1077 name = strchr(typelist[i]->tp_name, '.'); 1194 name = strchr(typelist[i]->tp_name, '.');
1078 assert (name != NULL); 1195 assert (name != NULL);
1079 Py_INCREF(typelist[i]); 1196 Py_INCREF(typelist[i]);
1080 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1197 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
1081 } 1198 }
1082 return m; 1199 return m;
1083 } 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+