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

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

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