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

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Left Patch Set: Created 7 years, 8 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 typedef struct lru_list_elem lru_list_elem; 598 struct lru_list_elem;
599 struct lru_cache_object;
549 600
550 typedef struct lru_list_elem { 601 typedef struct lru_list_elem {
551 lru_list_elem *prev, *next; 602 PyObject_HEAD
603 struct lru_list_elem *prev, *next; /* borrowed links */
552 PyObject *key, *result; 604 PyObject *key, *result;
553 } lru_list_elem; 605 } lru_list_elem;
554 606
555 typedef struct lru_cache_object lru_cache_object; 607 static void
556 608 lru_list_elem_dealloc(lru_list_elem *link)
557 typedef PyObject *(*lru_cache_ternaryfunc)(lru_cache_object *, PyObject *, PyObj ect *); 609 {
610 _PyObject_GC_UNTRACK(link);
611 Py_XDECREF(link->key);
612 Py_XDECREF(link->result);
613 PyObject_GC_Del(link);
614 }
615
616 static int
617 lru_list_elem_traverse(lru_list_elem *link, visitproc visit, void *arg)
618 {
619 Py_VISIT(link->key);
620 Py_VISIT(link->result);
621 return 0;
622 }
623
624 static int
625 lru_list_elem_clear(lru_list_elem *link)
626 {
627 Py_CLEAR(link->key);
628 Py_CLEAR(link->result);
629 return 0;
630 }
631
632 static PyTypeObject lru_list_elem_type = {
633 PyVarObject_HEAD_INIT(&PyType_Type, 0)
634 "functools._lru_list_elem", /* tp_name */
635 sizeof(lru_list_elem), /* tp_basicsize */
636 0, /* tp_itemsize */
637 /* methods */
638 (destructor)lru_list_elem_dealloc, /* tp_dealloc */
639 0, /* tp_print */
640 0, /* tp_getattr */
641 0, /* tp_setattr */
642 0, /* tp_reserved */
643 0, /* tp_repr */
644 0, /* tp_as_number */
645 0, /* tp_as_sequence */
646 0, /* tp_as_mapping */
647 0, /* tp_hash */
648 0, /* tp_call */
649 0, /* tp_str */
650 0, /* tp_getattro */
651 0, /* tp_setattro */
652 0, /* tp_as_buffer */
653 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
654 0, /* tp_doc */
655 (traverseproc)lru_list_elem_traverse, /* tp_traverse */
656 (inquiry)lru_list_elem_clear, /* tp_clear */
657 };
658
659
660 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *);
558 661
559 typedef struct lru_cache_object { 662 typedef struct lru_cache_object {
560 PyObject_HEAD 663 lru_list_elem root; /* includes PyObject_HEAD */
561 Py_ssize_t maxsize; 664 Py_ssize_t maxsize;
562 PyObject *maxsize_O; 665 PyObject *maxsize_O;
563 PyObject *func; 666 PyObject *func;
564 lru_cache_ternaryfunc wrapper; 667 lru_cache_ternaryfunc wrapper;
565 PyObject *cache; 668 PyObject *cache;
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)); 691 sorted_items = PyDict_Items(kwds);
588 if (!(sorted_items = PyDict_Items(kwds))) 692 if (!sorted_items)
589 return NULL; 693 return NULL;
590 if (0 > PyList_Sort(sorted_items)) { 694 if (PyList_Sort(sorted_items) < 0) {
591 Py_DECREF(sorted_items); 695 Py_DECREF(sorted_items);
592 return NULL; 696 return NULL;
593 } 697 }
594 } else 698 } else
595 sorted_items = NULL; 699 sorted_items = NULL;
596 700
597 key_size = PyTuple_GET_SIZE(args); 701 key_size = PyTuple_GET_SIZE(args);
598 if (kwds) 702 if (sorted_items)
599 key_size += PyList_GET_SIZE(sorted_items); 703 key_size += PyList_GET_SIZE(sorted_items);
600 if (typed) 704 if (typed)
601 key_size *= 2; 705 key_size *= 2;
602 if (kwds) 706 if (sorted_items)
603 key_size++; 707 key_size++;
604 708
605 key = PyTuple_New(key_size); 709 key = PyTuple_New(key_size);
710 if (key == NULL)
711 goto done;
712
606 key_pos = 0; 713 key_pos = 0;
607
608 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 714 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
609 PyObject *item = PyTuple_GET_ITEM(args, pos); 715 PyObject *item = PyTuple_GET_ITEM(args, pos);
610 Py_INCREF(item); 716 Py_INCREF(item);
611 PyTuple_SET_ITEM(key, key_pos++, item); 717 PyTuple_SET_ITEM(key, key_pos++, item);
612 } 718 }
613 if (kwds) { 719 if (sorted_items) {
614 Py_INCREF(kwd_mark); 720 Py_INCREF(kwd_mark);
615 PyTuple_SET_ITEM(key, key_pos++, kwd_mark); 721 PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
616 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 722 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
617 PyObject *item = PyList_GET_ITEM(sorted_items, pos); 723 PyObject *item = PyList_GET_ITEM(sorted_items, pos);
618 Py_INCREF(item); 724 Py_INCREF(item);
619 PyTuple_SET_ITEM(key, key_pos++, item); 725 PyTuple_SET_ITEM(key, key_pos++, item);
620 } 726 }
621 } 727 }
622 if (typed) { 728 if (typed) {
623 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 729 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
624 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos)); 730 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
625 Py_INCREF(item); 731 Py_INCREF(item);
626 PyTuple_SET_ITEM(key, key_pos++, item); 732 PyTuple_SET_ITEM(key, key_pos++, item);
627 } 733 }
628 if (kwds) { 734 if (sorted_items) {
629 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 735 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
630 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));
631 Py_INCREF(item); 738 Py_INCREF(item);
632 PyTuple_SET_ITEM(key, key_pos++, item); 739 PyTuple_SET_ITEM(key, key_pos++, item);
633 } 740 }
634 } 741 }
635 } 742 }
636 assert(key_pos == key_size); 743 assert(key_pos == key_size);
637 if (kwds) 744
745 done:
746 if (sorted_items)
638 Py_DECREF(sorted_items); 747 Py_DECREF(sorted_items);
639 return key; 748 return key;
640 } 749 }
641 750
642 static PyObject * 751 static PyObject *
643 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)
644 { 753 {
645 PyObject *result = PyObject_Call(self->func, args, kwds); 754 PyObject *result = PyObject_Call(self->func, args, kwds);
646 if (!result) 755 if (!result)
647 return NULL; 756 return NULL;
(...skipping 28 matching lines...) Expand all
676 Py_DECREF(result); 785 Py_DECREF(result);
677 Py_DECREF(key); 786 Py_DECREF(key);
678 return NULL; 787 return NULL;
679 } 788 }
680 Py_DECREF(key); 789 Py_DECREF(key);
681 self->misses++; 790 self->misses++;
682 return result; 791 return result;
683 } 792 }
684 793
685 static void 794 static void
686 lru_cache_list_extricate(lru_list_elem *link) 795 lru_cache_extricate_link(lru_list_elem *link)
687 { 796 {
688 link->prev->next = link->next; 797 link->prev->next = link->next;
689 link->next->prev = link->prev; 798 link->next->prev = link->prev;
690 } 799 }
691 800
692 static void 801 static void
693 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)
694 { 803 {
804 lru_list_elem *root = &self->root;
695 lru_list_elem *last = root->prev; 805 lru_list_elem *last = root->prev;
696 last->next = root->prev = link; 806 last->next = root->prev = link;
697 link->prev = last; 807 link->prev = last;
698 link->next = root; 808 link->next = root;
699 } 809 }
700 810
701 static PyObject * 811 static PyObject *
702 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 )
703 { 813 {
704 PyObject *key = lru_cache_make_key(args, kwds, self->typed); 814 lru_list_elem *link;
815 PyObject *key, *result;
816
817 key = lru_cache_make_key(args, kwds, self->typed);
705 if (!key) 818 if (!key)
706 return NULL; 819 return NULL;
707 PyObject *value = PyDict_GetItemWithError(self->cache, key); 820 link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
708 if (value) { 821 if (link) {
709 lru_list_elem *link = PyCapsule_GetPointer(value, NULL); 822 lru_cache_extricate_link(link);
710 lru_cache_list_extricate(link); 823 lru_cache_append_link(self, link);
711 lru_cache_list_append(&self->root, link);
712 self->hits++; 824 self->hits++;
825 result = link->result;
826 Py_INCREF(result);
713 Py_DECREF(key); 827 Py_DECREF(key);
714 Py_INCREF(link->result); 828 return result;
715 return link->result;
716 } 829 }
717 if (PyErr_Occurred()) { 830 if (PyErr_Occurred()) {
718 Py_DECREF(key); 831 Py_DECREF(key);
719 return NULL; 832 return NULL;
720 } 833 }
721 PyObject *result = PyObject_Call(self->func, args, kwds); 834 result = PyObject_Call(self->func, args, kwds);
722 if (!result) { 835 if (!result) {
723 Py_DECREF(key); 836 Py_DECREF(key);
724 return NULL; 837 return NULL;
725 } 838 }
726 lru_list_elem *link; 839 if (self->full && self->root.next != &self->root) {
727 if (PyDict_Size(self->cache) == self->maxsize) { 840 /* Use the oldest item to store the new key and result. */
728 /* extricate the oldest item */ 841 PyObject *oldkey, *oldresult;
842 /* Extricate the oldest item. */
729 link = self->root.next; 843 link = self->root.next;
730 lru_cache_list_extricate(link); 844 lru_cache_extricate_link(link);
731 /* grab its capsule */ 845 /* Remove it from the cache.
732 value = PyDict_GetItem(self->cache, link->key); 846 The cache dict holds one reference to the link,
733 Py_INCREF(value); 847 and the linked list holds yet one reference to it. */
734 /* remove its key from the cache */ 848 if (PyDict_DelItem(self->cache, link->key) < 0) {
735 if (0 > PyDict_DelItem(self->cache, link->key)) 849 lru_cache_append_link(self, link);
736 abort(); 850 Py_DECREF(key);
737 /* scrub the result from the link */ 851 Py_DECREF(result);
738 Py_DECREF(link->result); 852 return NULL;
853 }
854 /* Keep a reference to the old key and old result to
855 prevent their ref counts from going to zero during the
856 update. That will prevent potentially arbitrary object
857 clean-up code (i.e. __del__) from running while we're
858 still adjusting the links. */
859 oldkey = link->key;
860 oldresult = link->result;
861
862 link->key = key;
863 link->result = result;
864 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
865 Py_DECREF(link);
866 Py_DECREF(oldkey);
867 Py_DECREF(oldresult);
868 return NULL;
869 }
870 lru_cache_append_link(self, link);
871 Py_INCREF(result); /* for return */
872 Py_DECREF(oldkey);
873 Py_DECREF(oldresult);
739 } else { 874 } else {
740 link = PyMem_New(lru_list_elem, 1); 875 /* Put result in a new link at the front of the queue. */
741 value = PyCapsule_New(link, NULL, NULL); 876 link = (lru_list_elem *)PyObject_GC_New(lru_list_elem,
742 } 877 &lru_list_elem_type);
743 lru_cache_list_append(&self->root, link); 878 if (link == NULL) {
744 link->key = key; 879 Py_DECREF(key);
745 link->result = result; 880 Py_DECREF(result);
746 Py_INCREF(result); 881 return NULL;
747 if (0 > PyDict_SetItem(self->cache, key, value)) abort(); 882 }
748 Py_DECREF(key); 883
749 Py_DECREF(value); 884 link->key = key;
885 link->result = result;
886 _PyObject_GC_TRACK(link);
887 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
888 Py_DECREF(link);
889 return NULL;
890 }
891 lru_cache_append_link(self, link);
892 Py_INCREF(result); /* for return */
893 self->full = (PyDict_Size(self->cache) >= self->maxsize);
894 }
750 self->misses++; 895 self->misses++;
751 return result; 896 return result;
752 } 897 }
753 898
754 static PyObject * 899 static PyObject *
755 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) 900 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
756 { 901 {
757 PyObject *func; 902 PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
758 PyObject *maxsize_O = NULL;
759 PyObject *typed_O = NULL;
760 int typed; 903 int typed;
761 lru_cache_object *obj; 904 lru_cache_object *obj;
762 Py_ssize_t maxsize = 100; 905 Py_ssize_t maxsize;
763 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *); 906 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
764 static char *keywords[] = {"func", "maxsize", "typed", NULL}; 907 static char *keywords[] = {"user_function", "maxsize", "typed",
765 908 "cache_info_type", NULL};
766 if (!PyArg_ParseTupleAndKeywords(args, kw, "O|OO:lru_cache", keywords, 909
767 &func, &maxsize_O, &typed_O)) { 910 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
911 &func, &maxsize_O, &typed,
912 &cache_info_type)) {
768 return NULL; 913 return NULL;
769 } 914 }
770 915
771 if (!PyCallable_Check(func)) { 916 if (!PyCallable_Check(func)) {
772 PyErr_SetString(PyExc_TypeError, 917 PyErr_SetString(PyExc_TypeError,
773 "the first argument must be callable"); 918 "the first argument must be callable");
774 return NULL; 919 return NULL;
775 } 920 }
776 921
777 if (maxsize_O == NULL) { 922 /* select the caching function, and make/inc maxsize_O */
778 maxsize_O = PyLong_FromSsize_t(maxsize); 923 if (maxsize_O == Py_None) {
779 wrapper = bounded_lru_cache_wrapper;
780 } else if (maxsize_O == Py_None) {
781 wrapper = infinite_lru_cache_wrapper; 924 wrapper = infinite_lru_cache_wrapper;
782 Py_INCREF(maxsize_O); 925 /* use this only to initialize lru_cache_object attribute maxsize */
783 } else if (PyNumber_Check(maxsize_O)) { 926 maxsize = -1;
927 } else if (PyIndex_Check(maxsize_O)) {
784 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError); 928 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
785 if (maxsize == -1 && PyErr_Occurred()) 929 if (maxsize == -1 && PyErr_Occurred())
786 return NULL; 930 return NULL;
787 if (maxsize == 0) 931 if (maxsize == 0)
788 wrapper = uncached_lru_cache_wrapper; 932 wrapper = uncached_lru_cache_wrapper;
789 else 933 else
790 wrapper = bounded_lru_cache_wrapper; 934 wrapper = bounded_lru_cache_wrapper;
791 Py_INCREF(maxsize_O);
792 } else { 935 } else {
793 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None"); 936 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
794 return NULL; 937 return NULL;
795 } 938 }
796 939
797 if (typed_O) { 940 if (!(cachedict = PyDict_New()))
798 int err = PyObject_IsTrue(typed_O); 941 return NULL;
799 if (err < 0) {
800 Py_DECREF(maxsize_O);
801 return NULL;
802 }
803 typed = err;
804 } else
805 typed = 0;
806 942
807 obj = (lru_cache_object *)type->tp_alloc(type, 0); 943 obj = (lru_cache_object *)type->tp_alloc(type, 0);
808 if (obj == NULL) { 944 if (obj == NULL) {
809 Py_DECREF(maxsize_O); 945 Py_DECREF(cachedict);
810 return NULL; 946 return NULL;
811 } 947 }
812 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;
953 Py_INCREF(maxsize_O);
816 obj->maxsize_O = maxsize_O; 954 obj->maxsize_O = maxsize_O;
817 if (!(obj->cache = PyDict_New())) { 955 Py_INCREF(func);
818 Py_DECREF(obj);
819 Py_DECREF(maxsize_O);
820 return NULL;
821 }
822 obj->func = func; 956 obj->func = func;
823 Py_INCREF(func);
824 obj->wrapper = wrapper; 957 obj->wrapper = wrapper;
825 obj->misses = obj->hits = 0; 958 obj->misses = obj->hits = 0;
826 obj->typed = typed; 959 obj->typed = typed;
960 Py_INCREF(cache_info_type);
961 obj->cache_info_type = cache_info_type;
827 962
828 return (PyObject *)obj; 963 return (PyObject *)obj;
829 } 964 }
830 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
831 static void 978 static void
832 lru_cache_clear_list(lru_list_elem *root) 979 lru_cache_clear_list(lru_list_elem *link)
833 { 980 {
834 lru_list_elem *link = root->next; 981 while (link != NULL) {
835 while (link != root) {
836 lru_list_elem *next = link->next; 982 lru_list_elem *next = link->next;
837 Py_DECREF(link->result); 983 Py_DECREF(link);
838 PyMem_Free(link);
839 link = next; 984 link = next;
840 } 985 }
841 } 986 }
842 987
843 static void 988 static void
844 lru_cache_dealloc(lru_cache_object *obj) 989 lru_cache_dealloc(lru_cache_object *obj)
845 { 990 {
991 lru_list_elem *list = lru_cache_unlink_list(obj);
846 Py_XDECREF(obj->maxsize_O); 992 Py_XDECREF(obj->maxsize_O);
847 Py_XDECREF(obj->func); 993 Py_XDECREF(obj->func);
848 Py_XDECREF(obj->cache); 994 Py_XDECREF(obj->cache);
849 Py_XDECREF(obj->dict); 995 Py_XDECREF(obj->dict);
850 lru_cache_clear_list(&obj->root); 996 Py_XDECREF(obj->cache_info_type);
997 lru_cache_clear_list(list);
851 Py_TYPE(obj)->tp_free(obj); 998 Py_TYPE(obj)->tp_free(obj);
852 } 999 }
853 1000
854 static PyObject * 1001 static PyObject *
855 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) 1002 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
856 { 1003 {
857 return self->wrapper(self, args, kwds); 1004 return self->wrapper(self, args, kwds);
858 } 1005 }
859 1006
860 static PyObject * 1007 static PyObject *
1008 lru_cache_descr_get(PyObject *self, PyObject *obj, PyObject *type)
1009 {
1010 if (obj == Py_None || obj == NULL) {
1011 Py_INCREF(self);
1012 return self;
1013 }
1014 return PyMethod_New(self, obj);
1015 }
1016
1017 static PyObject *
861 lru_cache_cache_info(lru_cache_object *self, PyObject *unused) 1018 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
862 { 1019 {
863 PyObject *ret, *functools = PyImport_ImportModuleNoBlock("functools"); 1020 return PyObject_CallFunction(self->cache_info_type, "nnOn",
864 if (functools == NULL) 1021 self->hits, self->misses, self->maxsize_O,
865 return NULL; 1022 PyDict_Size(self->cache));
866 ret = PyObject_CallMethod(functools, "_CacheInfo", "nnOn",
867 self->hits, self->misses, self->maxsize_O,
868 PyDict_Size(self->cache));
869 Py_DECREF(functools);
870 return ret;
871 } 1023 }
872 1024
873 static PyObject * 1025 static PyObject *
874 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) 1026 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
875 { 1027 {
1028 lru_list_elem *list = lru_cache_unlink_list(self);
1029 self->hits = self->misses = 0;
1030 self->full = 0;
876 PyDict_Clear(self->cache); 1031 PyDict_Clear(self->cache);
877 self->hits = self->misses = 0; 1032 lru_cache_clear_list(list);
878 lru_cache_clear_list(&self->root);
879 self->root.next = self->root.prev = &self->root;
880 Py_RETURN_NONE; 1033 Py_RETURN_NONE;
881 } 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
1066
1067 PyDoc_STRVAR(lru_cache_doc,
1068 "Create a cached callable that wraps another function.\n\
1069 \n\
1070 user_function: the function being cached\n\
1071 \n\
1072 maxsize: 0 for no caching\n\
1073 None for unlimited cache size\n\
1074 n for a bounded cache\n\
1075 \n\
1076 typed: False cache f(3) and f(3.0) as identical calls\n\
1077 True cache f(3) and f(3.0) as distinct calls\n\
1078 \n\
1079 cache_info_type: namedtuple class with the fields:\n\
1080 hits misses currsize maxsize\n"
1081 );
882 1082
883 static PyMethodDef lru_cache_methods[] = { 1083 static PyMethodDef lru_cache_methods[] = {
884 {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS}, 1084 {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
885 {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS}, 1085 {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
886 {NULL} 1086 {NULL}
887 }; 1087 };
888 1088
889 static PyGetSetDef lru_cache_getsetlist[] = { 1089 static PyGetSetDef lru_cache_getsetlist[] = {
890 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict}, 1090 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
891 {NULL} 1091 {NULL}
892 }; 1092 };
893 1093
894 static PyTypeObject lru_cache_type = { 1094 static PyTypeObject lru_cache_type = {
895 PyVarObject_HEAD_INIT(NULL, 0) 1095 PyVarObject_HEAD_INIT(NULL, 0)
896 "functools._lru_cache", /* tp_name */ 1096 "functools._lru_cache_wrapper", /* tp_name */
897 sizeof(lru_cache_object), /* tp_basicsize */ 1097 sizeof(lru_cache_object), /* tp_basicsize */
898 0, /* tp_itemsize */ 1098 0, /* tp_itemsize */
899 /* methods */ 1099 /* methods */
900 (destructor)lru_cache_dealloc, /* tp_dealloc */ 1100 (destructor)lru_cache_dealloc, /* tp_dealloc */
901 0, /* tp_print */ 1101 0, /* tp_print */
902 0, /* tp_getattr */ 1102 0, /* tp_getattr */
903 0, /* tp_setattr */ 1103 0, /* tp_setattr */
904 0, /* tp_reserved */ 1104 0, /* tp_reserved */
905 0, /* tp_repr */ 1105 0, /* tp_repr */
906 0, /* tp_as_number */ 1106 0, /* tp_as_number */
907 0, /* tp_as_sequence */ 1107 0, /* tp_as_sequence */
908 0, /* tp_as_mapping */ 1108 0, /* tp_as_mapping */
909 0, /* tp_hash */ 1109 0, /* tp_hash */
910 (ternaryfunc)lru_cache_call, /* tp_call */ 1110 (ternaryfunc)lru_cache_call, /* tp_call */
911 0, /* tp_str */ 1111 0, /* tp_str */
912 0, /* tp_getattro */ 1112 0, /* tp_getattro */
913 0, /* tp_setattro */ 1113 0, /* tp_setattro */
914 0, /* tp_as_buffer */ 1114 0, /* tp_as_buffer */
915 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, 1115 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC,
916 /* tp_flags */ 1116 /* tp_flags */
917 0, /* tp_doc */ 1117 lru_cache_doc, /* tp_doc */
918 0, /* tp_traverse */ 1118 (traverseproc)lru_cache_tp_traverse,/* tp_traverse */
919 0, /* tp_clear */ 1119 (inquiry)lru_cache_tp_clear, /* tp_clear */
920 0, /* tp_richcompare */ 1120 0, /* tp_richcompare */
921 0, /* tp_weaklistoffset */ 1121 0, /* tp_weaklistoffset */
922 0, /* tp_iter */ 1122 0, /* tp_iter */
923 0, /* tp_iternext */ 1123 0, /* tp_iternext */
924 lru_cache_methods, /* tp_methods */ 1124 lru_cache_methods, /* tp_methods */
925 0, /* tp_members */ 1125 0, /* tp_members */
926 lru_cache_getsetlist, /* tp_getset */ 1126 lru_cache_getsetlist, /* tp_getset */
927 0, /* tp_base */ 1127 0, /* tp_base */
928 0, /* tp_dict */ 1128 0, /* tp_dict */
929 0, /* tp_descr_get */ 1129 lru_cache_descr_get, /* tp_descr_get */
930 0, /* tp_descr_set */ 1130 0, /* tp_descr_set */
931 offsetof(lru_cache_object, dict), /* tp_dictoffset */ 1131 offsetof(lru_cache_object, dict), /* tp_dictoffset */
932 0, /* tp_init */ 1132 0, /* tp_init */
933 0, /* tp_alloc */ 1133 0, /* tp_alloc */
934 lru_cache_new, /* tp_new */ 1134 lru_cache_new, /* tp_new */
935 }; 1135 };
936 1136
937 /* module level code ********************************************************/ 1137 /* module level code ********************************************************/
938 1138
939 PyDoc_STRVAR(module_doc, 1139 PyDoc_STRVAR(module_doc,
940 "Tools that operate on functions."); 1140 "Tools that operate on functions.");
941 1141
942 static PyMethodDef module_methods[] = { 1142 static PyMethodDef module_methods[] = {
943 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 1143 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
944 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 1144 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
945 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 1145 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
946 {NULL, NULL} /* sentinel */ 1146 {NULL, NULL} /* sentinel */
947 }; 1147 };
948 1148
949 static void 1149 static void
950 module_free(void *m) 1150 module_free(void *m)
951 { 1151 {
952 Py_DECREF(kwd_mark); 1152 Py_CLEAR(kwd_mark);
953 } 1153 }
954 1154
955 static struct PyModuleDef _functoolsmodule = { 1155 static struct PyModuleDef _functoolsmodule = {
956 PyModuleDef_HEAD_INIT, 1156 PyModuleDef_HEAD_INIT,
957 "_functools", 1157 "_functools",
958 module_doc, 1158 module_doc,
959 -1, 1159 -1,
960 module_methods, 1160 module_methods,
961 NULL, 1161 NULL,
962 NULL, 1162 NULL,
(...skipping 10 matching lines...) Expand all
973 PyTypeObject *typelist[] = { 1173 PyTypeObject *typelist[] = {
974 &partial_type, 1174 &partial_type,
975 &lru_cache_type, 1175 &lru_cache_type,
976 NULL 1176 NULL
977 }; 1177 };
978 1178
979 m = PyModule_Create(&_functoolsmodule); 1179 m = PyModule_Create(&_functoolsmodule);
980 if (m == NULL) 1180 if (m == NULL)
981 return NULL; 1181 return NULL;
982 1182
983 if (!(kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL))) { 1183 kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL);
1184 if (!kwd_mark) {
984 Py_DECREF(m); 1185 Py_DECREF(m);
985 return NULL; 1186 return NULL;
986 } 1187 }
987 1188
988 for (i=0 ; typelist[i] != NULL ; i++) { 1189 for (i=0 ; typelist[i] != NULL ; i++) {
989 if (PyType_Ready(typelist[i]) < 0) { 1190 if (PyType_Ready(typelist[i]) < 0) {
990 Py_DECREF(m); 1191 Py_DECREF(m);
991 return NULL; 1192 return NULL;
992 } 1193 }
993 name = strchr(typelist[i]->tp_name, '.'); 1194 name = strchr(typelist[i]->tp_name, '.');
994 assert (name != NULL); 1195 assert (name != NULL);
995 Py_INCREF(typelist[i]); 1196 Py_INCREF(typelist[i]);
996 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1197 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
997 } 1198 }
998 return m; 1199 return m;
999 } 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+