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

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Left Patch Set: Created 7 years, 3 months ago
Right Patch Set: Created 4 years 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;
storchaka 2012/11/24 15:02:52 Remove this line and use "struct lru_list_elem *p
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
storchaka 2012/11/24 15:02:52 Same as above.
556 608 lru_list_elem_dealloc(lru_list_elem *link)
557 typedef PyObject *(*lru_cache_ternaryfunc)(lru_cache_object *, PyObject *, PyObj ect *); 609 {
storchaka 2012/11/24 15:02:52 Please split all lines longer than 79 characters t
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;
566 PyObject *cache_info_type; 669 PyObject *cache_info_type;
567 Py_ssize_t misses, hits; 670 Py_ssize_t misses, hits;
568 lru_list_elem root;
569 int typed; 671 int typed;
570 PyObject *dict; 672 PyObject *dict;
673 int full;
571 } lru_cache_object; 674 } lru_cache_object;
572 675
573 static PyTypeObject lru_cache_type; 676 static PyTypeObject lru_cache_type;
574 677
575 static PyObject * 678 static PyObject *
576 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed) 679 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
577 { 680 {
578 PyObject *key, *sorted_items; 681 PyObject *key, *sorted_items;
579 Py_ssize_t key_size, pos, key_pos; 682 Py_ssize_t key_size, pos, key_pos;
580 683
581 /* short path, key will match args anyway, which is a tuple */ 684 /* short path, key will match args anyway, which is a tuple */
582 if (!typed && !kwds) { 685 if (!typed && !kwds) {
583 Py_INCREF(args); 686 Py_INCREF(args);
584 return args; 687 return args;
585 } 688 }
586 689
587 if (kwds) { 690 if (kwds && PyDict_Size(kwds) > 0) {
588 assert(PyDict_Size(kwds)); 691 sorted_items = PyDict_Items(kwds);
589 if (!(sorted_items = PyDict_Items(kwds))) 692 if (!sorted_items)
storchaka 2012/11/24 15:02:52 Assignment in expression is not needed here. You c
590 return NULL; 693 return NULL;
591 if (0 > PyList_Sort(sorted_items)) { 694 if (PyList_Sort(sorted_items) < 0) {
storchaka 2012/11/24 15:02:52 Is used somewhere in the code such reversed form o
592 Py_DECREF(sorted_items); 695 Py_DECREF(sorted_items);
593 return NULL; 696 return NULL;
594 } 697 }
595 } else 698 } else
596 sorted_items = NULL; 699 sorted_items = NULL;
597 700
598 key_size = PyTuple_GET_SIZE(args); 701 key_size = PyTuple_GET_SIZE(args);
599 if (kwds) 702 if (sorted_items)
600 key_size += PyList_GET_SIZE(sorted_items); 703 key_size += PyList_GET_SIZE(sorted_items);
601 if (typed) 704 if (typed)
602 key_size *= 2; 705 key_size *= 2;
603 if (kwds) 706 if (sorted_items)
604 key_size++; 707 key_size++;
605 708
606 key = PyTuple_New(key_size); 709 key = PyTuple_New(key_size);
710 if (key == NULL)
711 goto done;
712
607 key_pos = 0; 713 key_pos = 0;
608
609 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 714 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
610 PyObject *item = PyTuple_GET_ITEM(args, pos); 715 PyObject *item = PyTuple_GET_ITEM(args, pos);
611 Py_INCREF(item); 716 Py_INCREF(item);
612 PyTuple_SET_ITEM(key, key_pos++, item); 717 PyTuple_SET_ITEM(key, key_pos++, item);
613 } 718 }
614 if (kwds) { 719 if (sorted_items) {
615 Py_INCREF(kwd_mark); 720 Py_INCREF(kwd_mark);
616 PyTuple_SET_ITEM(key, key_pos++, kwd_mark); 721 PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
617 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 722 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
618 PyObject *item = PyList_GET_ITEM(sorted_items, pos); 723 PyObject *item = PyList_GET_ITEM(sorted_items, pos);
619 Py_INCREF(item); 724 Py_INCREF(item);
620 PyTuple_SET_ITEM(key, key_pos++, item); 725 PyTuple_SET_ITEM(key, key_pos++, item);
621 } 726 }
622 } 727 }
623 if (typed) { 728 if (typed) {
624 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) { 729 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
625 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos)); 730 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
626 Py_INCREF(item); 731 Py_INCREF(item);
627 PyTuple_SET_ITEM(key, key_pos++, item); 732 PyTuple_SET_ITEM(key, key_pos++, item);
628 } 733 }
629 if (kwds) { 734 if (sorted_items) {
630 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) { 735 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
631 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(PyList_GET _ITEM(sorted_items, pos), 1)); 736 PyObject *tp_items = PyList_GET_ITEM(sorted_items, pos);
737 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(tp_items, 1));
632 Py_INCREF(item); 738 Py_INCREF(item);
633 PyTuple_SET_ITEM(key, key_pos++, item); 739 PyTuple_SET_ITEM(key, key_pos++, item);
634 } 740 }
635 } 741 }
636 } 742 }
637 assert(key_pos == key_size); 743 assert(key_pos == key_size);
638 744
639 if (kwds) 745 done:
746 if (sorted_items)
640 Py_DECREF(sorted_items); 747 Py_DECREF(sorted_items);
641 return key; 748 return key;
642 } 749 }
643 750
644 static PyObject * 751 static PyObject *
645 uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s) 752 uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s)
646 { 753 {
647 PyObject *result = PyObject_Call(self->func, args, kwds); 754 PyObject *result = PyObject_Call(self->func, args, kwds);
648 if (!result) 755 if (!result)
649 return NULL; 756 return NULL;
(...skipping 28 matching lines...) Expand all
678 Py_DECREF(result); 785 Py_DECREF(result);
679 Py_DECREF(key); 786 Py_DECREF(key);
680 return NULL; 787 return NULL;
681 } 788 }
682 Py_DECREF(key); 789 Py_DECREF(key);
683 self->misses++; 790 self->misses++;
684 return result; 791 return result;
685 } 792 }
686 793
687 static void 794 static void
688 lru_cache_list_extricate(lru_list_elem *link) 795 lru_cache_extricate_link(lru_list_elem *link)
689 { 796 {
690 link->prev->next = link->next; 797 link->prev->next = link->next;
691 link->next->prev = link->prev; 798 link->next->prev = link->prev;
692 } 799 }
693 800
694 static void 801 static void
695 lru_cache_list_append(lru_list_elem *root, lru_list_elem *link) 802 lru_cache_append_link(lru_cache_object *self, lru_list_elem *link)
696 { 803 {
804 lru_list_elem *root = &self->root;
697 lru_list_elem *last = root->prev; 805 lru_list_elem *last = root->prev;
698 last->next = root->prev = link; 806 last->next = root->prev = link;
699 link->prev = last; 807 link->prev = last;
700 link->next = root; 808 link->next = root;
701 } 809 }
702 810
703 static PyObject * 811 static PyObject *
704 bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds ) 812 bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds )
705 { 813 {
706 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);
707 if (!key) 818 if (!key)
708 return NULL; 819 return NULL;
709 PyObject *value = PyDict_GetItemWithError(self->cache, key); 820 link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
710 if (value) { 821 if (link) {
711 lru_list_elem *link = PyCapsule_GetPointer(value, NULL); 822 lru_cache_extricate_link(link);
712 lru_cache_list_extricate(link); 823 lru_cache_append_link(self, link);
713 lru_cache_list_append(&self->root, link);
714 self->hits++; 824 self->hits++;
825 result = link->result;
826 Py_INCREF(result);
715 Py_DECREF(key); 827 Py_DECREF(key);
716 Py_INCREF(link->result); 828 return result;
717 return link->result;
718 } 829 }
719 if (PyErr_Occurred()) { 830 if (PyErr_Occurred()) {
720 Py_DECREF(key); 831 Py_DECREF(key);
721 return NULL; 832 return NULL;
722 } 833 }
723 PyObject *result = PyObject_Call(self->func, args, kwds); 834 result = PyObject_Call(self->func, args, kwds);
724 if (!result) { 835 if (!result) {
725 Py_DECREF(key); 836 Py_DECREF(key);
726 return NULL; 837 return NULL;
727 } 838 }
728 lru_list_elem *link; 839 if (self->full && self->root.next != &self->root) {
729 if (PyDict_Size(self->cache) == self->maxsize) { 840 /* Use the oldest item to store the new key and result. */
730 /* extricate the oldest item */ 841 PyObject *oldkey, *oldresult;
842 /* Extricate the oldest item. */
731 link = self->root.next; 843 link = self->root.next;
732 lru_cache_list_extricate(link); 844 lru_cache_extricate_link(link);
733 /* grab its capsule */ 845 /* Remove it from the cache.
734 value = PyDict_GetItem(self->cache, link->key); 846 The cache dict holds one reference to the link,
storchaka 2012/11/24 15:02:52 Check value for NULL.
735 Py_INCREF(value); 847 and the linked list holds yet one reference to it. */
736 /* remove its key from the cache */ 848 if (PyDict_DelItem(self->cache, link->key) < 0) {
737 if (0 > PyDict_DelItem(self->cache, link->key)) 849 lru_cache_append_link(self, link);
storchaka 2012/11/24 15:02:52 Reversed comparison.
738 abort(); 850 Py_DECREF(key);
storchaka 2012/11/24 15:02:52 It should not be. Raise a SystemError. You can ge
739 /* scrub the result from the link */ 851 Py_DECREF(result);
740 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);
741 } else { 874 } else {
742 link = PyMem_New(lru_list_elem, 1); 875 /* Put result in a new link at the front of the queue. */
storchaka 2012/11/24 15:02:52 Check for NULL.
743 value = PyCapsule_New(link, NULL, NULL); 876 link = (lru_list_elem *)PyObject_GC_New(lru_list_elem,
744 } 877 &lru_list_elem_type);
745 lru_cache_list_append(&self->root, link); 878 if (link == NULL) {
746 link->key = key; 879 Py_DECREF(key);
747 link->result = result; 880 Py_DECREF(result);
748 Py_INCREF(result); 881 return NULL;
749 if (0 > PyDict_SetItem(self->cache, key, value)) abort(); 882 }
storchaka 2012/11/24 15:02:52 Reversed comparison, abort(), condition and "then"
750 Py_DECREF(key); 883
storchaka 2012/11/24 15:02:52 Does not linked list own keys and values?
751 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 }
752 self->misses++; 895 self->misses++;
753 return result; 896 return result;
754 } 897 }
755 898
756 static PyObject * 899 static PyObject *
757 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) 900 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
758 { 901 {
759 PyObject *func, *maxsize_O, *typed_O, *cache_info_type; 902 PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
760 int typed; 903 int typed;
761 lru_cache_object *obj; 904 lru_cache_object *obj;
762 Py_ssize_t maxsize; 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[] = {"user_function", "maxsize", "typed", 907 static char *keywords[] = {"user_function", "maxsize", "typed",
storchaka 2012/11/24 15:02:52 Actually keyword arguments are not needed here. Th
765 "cache_info_type", NULL}; 908 "cache_info_type", NULL};
766 909
767 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOOO:lru_cache", keywords, 910 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
storchaka 2012/11/24 15:02:52 Use a new format "p" for `typed`.
768 &func, &maxsize_O, &typed_O, 911 &func, &maxsize_O, &typed,
769 &cache_info_type)) { 912 &cache_info_type)) {
770 return NULL; 913 return NULL;
771 } 914 }
772 915
773 if (!PyCallable_Check(func)) { 916 if (!PyCallable_Check(func)) {
774 PyErr_SetString(PyExc_TypeError, 917 PyErr_SetString(PyExc_TypeError,
775 "the first argument must be callable"); 918 "the first argument must be callable");
776 return NULL; 919 return NULL;
777 } 920 }
778 921
779 // select the caching function, and make/inc maxsize_O 922 /* select the caching function, and make/inc maxsize_O */
storchaka 2012/11/24 15:02:52 Never use C++ style // one-line comments.
780 if (maxsize_O == Py_None) { 923 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 */
storchaka 2012/11/24 15:02:52 You can move all Py_INCREF(maxsize_O) down, right
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;
storchaka 2012/11/24 15:02:52 ‘maxsize’ may be used uninitialized (when 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);
storchaka 2012/11/24 15:02:52 Py_INCREF() before assignment looks more idiomatic
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);
827 obj->cache_info_type = cache_info_type; 961 obj->cache_info_type = cache_info_type;
828 Py_INCREF(cache_info_type);
storchaka 2012/11/24 15:02:52 Same as above.
829 962
830 return (PyObject *)obj; 963 return (PyObject *)obj;
831 } 964 }
832 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
833 static void 978 static void
834 lru_cache_clear_list(lru_list_elem *root) 979 lru_cache_clear_list(lru_list_elem *link)
835 { 980 {
836 lru_list_elem *link = root->next; 981 while (link != NULL) {
837 while (link != root) {
838 lru_list_elem *next = link->next; 982 lru_list_elem *next = link->next;
839 Py_DECREF(link->result); 983 Py_DECREF(link);
840 PyMem_Free(link);
841 link = next; 984 link = next;
842 } 985 }
843 } 986 }
844 987
845 static void 988 static void
846 lru_cache_dealloc(lru_cache_object *obj) 989 lru_cache_dealloc(lru_cache_object *obj)
847 { 990 {
991 lru_list_elem *list = lru_cache_unlink_list(obj);
848 Py_XDECREF(obj->maxsize_O); 992 Py_XDECREF(obj->maxsize_O);
849 Py_XDECREF(obj->func); 993 Py_XDECREF(obj->func);
850 Py_XDECREF(obj->cache); 994 Py_XDECREF(obj->cache);
851 Py_XDECREF(obj->dict); 995 Py_XDECREF(obj->dict);
852 Py_XDECREF(obj->cache_info_type); 996 Py_XDECREF(obj->cache_info_type);
853 lru_cache_clear_list(&obj->root); 997 lru_cache_clear_list(list);
854 Py_TYPE(obj)->tp_free(obj); 998 Py_TYPE(obj)->tp_free(obj);
855 } 999 }
856 1000
857 static PyObject * 1001 static PyObject *
858 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) 1002 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
859 { 1003 {
860 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);
861 } 1015 }
862 1016
863 static PyObject * 1017 static PyObject *
864 lru_cache_cache_info(lru_cache_object *self, PyObject *unused) 1018 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
865 { 1019 {
866 return PyObject_CallFunction(self->cache_info_type, "nnOn", 1020 return PyObject_CallFunction(self->cache_info_type, "nnOn",
867 self->hits, self->misses, self->maxsize_O, 1021 self->hits, self->misses, self->maxsize_O,
868 PyDict_Size(self->cache)); 1022 PyDict_Size(self->cache));
869 } 1023 }
870 1024
871 static PyObject * 1025 static PyObject *
872 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) 1026 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
873 { 1027 {
874 do PyDict_Clear(self->cache); while (PyDict_Size(self->cache)); 1028 lru_list_elem *list = lru_cache_unlink_list(self);
storchaka 2012/11/24 15:02:52 Please split this loop on several lines and use br
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/11/24 15:02:52 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);
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+