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

Delta Between Two Patch Sets: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Left Patch Set: Created 6 years, 7 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 struct lru_list_elem; 598 struct lru_list_elem;
549 struct lru_cache_object; 599 struct lru_cache_object;
550 600
551 typedef struct lru_list_elem { 601 typedef struct lru_list_elem {
552 struct lru_list_elem *prev, *next; 602 PyObject_HEAD
603 struct lru_list_elem *prev, *next; /* borrowed links */
553 PyObject *key, *result; 604 PyObject *key, *result;
554 } lru_list_elem; 605 } lru_list_elem;
AntoinePitrou 2012/12/22 21:49:49 Why not make this a regular PyObject? It will make
storchaka 2012/12/22 22:43:39 I think all links should be "weak" even if lru_lis
555 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
556 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *); 660 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *);
557 661
558 typedef struct lru_cache_object { 662 typedef struct lru_cache_object {
559 PyObject_HEAD 663 lru_list_elem root; /* includes PyObject_HEAD */
560 Py_ssize_t maxsize; 664 Py_ssize_t maxsize;
561 PyObject *maxsize_O; 665 PyObject *maxsize_O;
562 PyObject *func; 666 PyObject *func;
563 lru_cache_ternaryfunc wrapper; 667 lru_cache_ternaryfunc wrapper;
564 PyObject *cache; 668 PyObject *cache;
565 PyObject *cache_info_type; 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));
AntoinePitrou 2012/12/22 21:49:49 Are you sure it can't be 0?
588 sorted_items = PyDict_Items(kwds); 691 sorted_items = PyDict_Items(kwds);
589 if (!sorted_items) 692 if (!sorted_items)
590 return NULL; 693 return NULL;
591 if (PyList_Sort(sorted_items) < 0) { 694 if (PyList_Sort(sorted_items) < 0) {
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);
AntoinePitrou 2012/12/22 21:49:49 This is a long line, can you wrap it?
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 lru_list_elem *link; 814 lru_list_elem *link;
707 PyObject *key, *value, *result; 815 PyObject *key, *result;
708 816
709 key = lru_cache_make_key(args, kwds, self->typed); 817 key = lru_cache_make_key(args, kwds, self->typed);
710 if (!key) 818 if (!key)
711 return NULL; 819 return NULL;
712 value = PyDict_GetItemWithError(self->cache, key); 820 link = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
713 if (value) { 821 if (link) {
714 lru_list_elem *link = PyCapsule_GetPointer(value, NULL); 822 lru_cache_extricate_link(link);
715 lru_cache_list_extricate(link); 823 lru_cache_append_link(self, link);
716 lru_cache_list_append(&self->root, link);
717 self->hits++; 824 self->hits++;
825 result = link->result;
826 Py_INCREF(result);
718 Py_DECREF(key); 827 Py_DECREF(key);
719 Py_INCREF(link->result); 828 return result;
720 return link->result;
721 } 829 }
722 if (PyErr_Occurred()) { 830 if (PyErr_Occurred()) {
723 Py_DECREF(key); 831 Py_DECREF(key);
724 return NULL; 832 return NULL;
725 } 833 }
726 result = PyObject_Call(self->func, args, kwds); 834 result = PyObject_Call(self->func, args, kwds);
727 if (!result) { 835 if (!result) {
728 Py_DECREF(key); 836 Py_DECREF(key);
729 return NULL; 837 return NULL;
730 } 838 }
731 if (PyDict_Size(self->cache) == self->maxsize) { 839 if (self->full && self->root.next != &self->root) {
732 /* extricate the oldest item */ 840 /* Use the oldest item to store the new key and result. */
841 PyObject *oldkey, *oldresult;
842 /* Extricate the oldest item. */
733 link = self->root.next; 843 link = self->root.next;
734 lru_cache_list_extricate(link); 844 lru_cache_extricate_link(link);
735 /* grab its capsule */ 845 /* Remove it from the cache.
736 value = PyDict_GetItem(self->cache, link->key); 846 The cache dict holds one reference to the link,
737 if (value == NULL) { 847 and the linked list holds yet one reference to it. */
848 if (PyDict_DelItem(self->cache, link->key) < 0) {
849 lru_cache_append_link(self, link);
738 Py_DECREF(key); 850 Py_DECREF(key);
739 return NULL; 851 Py_DECREF(result);
740 } 852 return NULL;
741 Py_INCREF(value); 853 }
742 /* remove its key from the cache */ 854 /* Keep a reference to the old key and old result to
743 if (PyDict_DelItem(self->cache, link->key) < 0) { 855 prevent their ref counts from going to zero during the
744 Py_DECREF(value); 856 update. That will prevent potentially arbitrary object
857 clean-up code (i.e. __del__) from running while we're
858 still adjusting the links. */
859 oldkey = link->key;
860 oldresult = link->result;
861
862 link->key = key;
863 link->result = result;
864 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
865 Py_DECREF(link);
866 Py_DECREF(oldkey);
867 Py_DECREF(oldresult);
868 return NULL;
869 }
870 lru_cache_append_link(self, link);
871 Py_INCREF(result); /* for return */
872 Py_DECREF(oldkey);
873 Py_DECREF(oldresult);
874 } else {
875 /* Put result in a new link at the front of the queue. */
876 link = (lru_list_elem *)PyObject_GC_New(lru_list_elem,
877 &lru_list_elem_type);
878 if (link == NULL) {
745 Py_DECREF(key); 879 Py_DECREF(key);
746 return NULL; 880 Py_DECREF(result);
747 } 881 return NULL;
748 /* scrub the result from the link */ 882 }
749 Py_DECREF(link->result); 883
750 } else { 884 link->key = key;
751 link = PyMem_New(lru_list_elem, 1); 885 link->result = result;
752 if (link == NULL) { 886 _PyObject_GC_TRACK(link);
753 PyErr_NoMemory(); 887 if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
754 return NULL; 888 Py_DECREF(link);
755 } 889 return NULL;
756 value = PyCapsule_New(link, NULL, NULL); 890 }
AntoinePitrou 2012/12/22 21:49:49 You should check value for non-NULL.
757 } 891 lru_cache_append_link(self, link);
758 lru_cache_list_append(&self->root, link); 892 Py_INCREF(result); /* for return */
759 link->key = key; 893 self->full = (PyDict_Size(self->cache) >= self->maxsize);
760 Py_INCREF(result); 894 }
761 link->result = result;
762 if (PyDict_SetItem(self->cache, key, value) < 0) {
763 return NULL;
764 }
765 Py_DECREF(key);
766 Py_DECREF(value);
767 self->misses++; 895 self->misses++;
768 return result; 896 return result;
769 } 897 }
770 898
771 static PyObject * 899 static PyObject *
772 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw) 900 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
773 { 901 {
774 PyObject *func, *maxsize_O, *cache_info_type; 902 PyObject *func, *maxsize_O, *cache_info_type, *cachedict;
775 int typed; 903 int typed;
776 lru_cache_object *obj; 904 lru_cache_object *obj;
777 Py_ssize_t maxsize; 905 Py_ssize_t maxsize;
778 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *); 906 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
779 static char *keywords[] = {"user_function", "maxsize", "typed", 907 static char *keywords[] = {"user_function", "maxsize", "typed",
780 "cache_info_type", NULL}; 908 "cache_info_type", NULL};
781 909
storchaka 2012/12/23 18:18:49 Trailing whitespaces.
782 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords, 910 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
783 &func, &maxsize_O, &typed, 911 &func, &maxsize_O, &typed,
784 &cache_info_type)) { 912 &cache_info_type)) {
785 return NULL; 913 return NULL;
786 } 914 }
787 915
788 if (!PyCallable_Check(func)) { 916 if (!PyCallable_Check(func)) {
789 PyErr_SetString(PyExc_TypeError, 917 PyErr_SetString(PyExc_TypeError,
790 "the first argument must be callable"); 918 "the first argument must be callable");
791 return NULL; 919 return NULL;
792 } 920 }
793 921
794 /* select the caching function, and make/inc maxsize_O */ 922 /* select the caching function, and make/inc maxsize_O */
795 if (maxsize_O == Py_None) { 923 if (maxsize_O == Py_None) {
796 wrapper = infinite_lru_cache_wrapper; 924 wrapper = infinite_lru_cache_wrapper;
797 /* use this only to initialize lru_cache_object attribute maxsize */ 925 /* use this only to initialize lru_cache_object attribute maxsize */
798 maxsize = -1; 926 maxsize = -1;
storchaka 2012/12/23 18:18:49 Trailing whitespaces.
799 } else if (PyNumber_Check(maxsize_O)) { 927 } else if (PyIndex_Check(maxsize_O)) {
800 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError); 928 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
801 if (maxsize == -1 && PyErr_Occurred()) 929 if (maxsize == -1 && PyErr_Occurred())
802 return NULL; 930 return NULL;
803 if (maxsize == 0) 931 if (maxsize == 0)
804 wrapper = uncached_lru_cache_wrapper; 932 wrapper = uncached_lru_cache_wrapper;
805 else 933 else
806 wrapper = bounded_lru_cache_wrapper; 934 wrapper = bounded_lru_cache_wrapper;
AntoinePitrou 2012/12/22 21:49:49 Shouldn't you guard against negative numbers?
storchaka 2012/12/22 22:43:39 Indeed. With negative number it works as ineffecti
807 } else { 935 } else {
808 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None"); 936 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
809 return NULL; 937 return NULL;
810 } 938 }
811 939
940 if (!(cachedict = PyDict_New()))
941 return NULL;
942
812 obj = (lru_cache_object *)type->tp_alloc(type, 0); 943 obj = (lru_cache_object *)type->tp_alloc(type, 0);
813 if (obj == NULL) 944 if (obj == NULL) {
814 return NULL; 945 Py_DECREF(cachedict);
815 946 return NULL;
947 }
948
949 obj->cache = cachedict;
816 obj->root.prev = &obj->root; 950 obj->root.prev = &obj->root;
817 obj->root.next = &obj->root; 951 obj->root.next = &obj->root;
818 obj->maxsize = maxsize; 952 obj->maxsize = maxsize;
819 Py_INCREF(maxsize_O); 953 Py_INCREF(maxsize_O);
820 obj->maxsize_O = maxsize_O; 954 obj->maxsize_O = maxsize_O;
821 if (!(obj->cache = PyDict_New())) {
822 Py_DECREF(obj);
823 Py_DECREF(maxsize_O);
824 return NULL;
825 }
826 Py_INCREF(func); 955 Py_INCREF(func);
827 obj->func = func; 956 obj->func = func;
828 obj->wrapper = wrapper; 957 obj->wrapper = wrapper;
829 obj->misses = obj->hits = 0; 958 obj->misses = obj->hits = 0;
830 obj->typed = typed; 959 obj->typed = typed;
831 Py_INCREF(cache_info_type); 960 Py_INCREF(cache_info_type);
832 obj->cache_info_type = cache_info_type; 961 obj->cache_info_type = cache_info_type;
833 962
834 return (PyObject *)obj; 963 return (PyObject *)obj;
835 } 964 }
836 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
837 static void 978 static void
838 lru_cache_clear_list(lru_list_elem *root) 979 lru_cache_clear_list(lru_list_elem *link)
839 { 980 {
840 lru_list_elem *link = root->next; 981 while (link != NULL) {
841 while (link != root) {
842 lru_list_elem *next = link->next; 982 lru_list_elem *next = link->next;
843 Py_DECREF(link->result); 983 Py_DECREF(link);
AntoinePitrou 2012/12/22 21:49:49 This could release the GIL, and if another thread
844 PyMem_Free(link);
845 link = next; 984 link = next;
846 } 985 }
847 } 986 }
848 987
849 static void 988 static void
850 lru_cache_dealloc(lru_cache_object *obj) 989 lru_cache_dealloc(lru_cache_object *obj)
851 { 990 {
991 lru_list_elem *list = lru_cache_unlink_list(obj);
852 Py_XDECREF(obj->maxsize_O); 992 Py_XDECREF(obj->maxsize_O);
853 Py_XDECREF(obj->func); 993 Py_XDECREF(obj->func);
854 Py_XDECREF(obj->cache); 994 Py_XDECREF(obj->cache);
855 Py_XDECREF(obj->dict); 995 Py_XDECREF(obj->dict);
856 Py_XDECREF(obj->cache_info_type); 996 Py_XDECREF(obj->cache_info_type);
857 lru_cache_clear_list(&obj->root); 997 lru_cache_clear_list(list);
858 Py_TYPE(obj)->tp_free(obj); 998 Py_TYPE(obj)->tp_free(obj);
859 } 999 }
860 1000
861 static PyObject * 1001 static PyObject *
862 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds) 1002 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
863 { 1003 {
864 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);
865 } 1015 }
866 1016
867 static PyObject * 1017 static PyObject *
868 lru_cache_cache_info(lru_cache_object *self, PyObject *unused) 1018 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
869 { 1019 {
870 return PyObject_CallFunction(self->cache_info_type, "nnOn", 1020 return PyObject_CallFunction(self->cache_info_type, "nnOn",
871 self->hits, self->misses, self->maxsize_O, 1021 self->hits, self->misses, self->maxsize_O,
872 PyDict_Size(self->cache)); 1022 PyDict_Size(self->cache));
873 } 1023 }
874 1024
875 static PyObject * 1025 static PyObject *
876 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused) 1026 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
877 { 1027 {
878 do { 1028 lru_list_elem *list = lru_cache_unlink_list(self);
879 PyDict_Clear(self->cache);
storchaka 2012/12/23 18:18:49 Trailing whitespaces.
880 } while (PyDict_Size(self->cache));
AntoinePitrou 2012/12/22 21:49:49 What's the point of this?
881 self->hits = self->misses = 0; 1029 self->hits = self->misses = 0;
882 lru_cache_clear_list(&self->root); 1030 self->full = 0;
883 self->root.next = self->root.prev = &self->root; 1031 PyDict_Clear(self->cache);
1032 lru_cache_clear_list(list);
884 Py_RETURN_NONE; 1033 Py_RETURN_NONE;
885 } 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
886 1066
887 PyDoc_STRVAR(lru_cache_doc, 1067 PyDoc_STRVAR(lru_cache_doc,
888 "Create a cached callable that wraps another function.\n\ 1068 "Create a cached callable that wraps another function.\n\
889 \n\ 1069 \n\
890 user_function: the function being cached\n\ 1070 user_function: the function being cached\n\
891 \n\ 1071 \n\
892 maxsize: 0 for no caching\n\ 1072 maxsize: 0 for no caching\n\
893 None for unlimited cache size\n\ 1073 None for unlimited cache size\n\
894 n for a bounded cache\n\ 1074 n for a bounded cache\n\
895 \n\ 1075 \n\
(...skipping 29 matching lines...) Expand all
925 0, /* tp_repr */ 1105 0, /* tp_repr */
926 0, /* tp_as_number */ 1106 0, /* tp_as_number */
927 0, /* tp_as_sequence */ 1107 0, /* tp_as_sequence */
928 0, /* tp_as_mapping */ 1108 0, /* tp_as_mapping */
929 0, /* tp_hash */ 1109 0, /* tp_hash */
930 (ternaryfunc)lru_cache_call, /* tp_call */ 1110 (ternaryfunc)lru_cache_call, /* tp_call */
931 0, /* tp_str */ 1111 0, /* tp_str */
932 0, /* tp_getattro */ 1112 0, /* tp_getattro */
933 0, /* tp_setattro */ 1113 0, /* tp_setattro */
934 0, /* tp_as_buffer */ 1114 0, /* tp_as_buffer */
935 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, 1115 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC,
AntoinePitrou 2012/12/22 21:49:49 The type needs to be GC-enabled, because there can
936 /* tp_flags */ 1116 /* tp_flags */
937 lru_cache_doc, /* tp_doc */ 1117 lru_cache_doc, /* tp_doc */
938 0, /* tp_traverse */ 1118 (traverseproc)lru_cache_tp_traverse,/* tp_traverse */
939 0, /* tp_clear */ 1119 (inquiry)lru_cache_tp_clear, /* tp_clear */
940 0, /* tp_richcompare */ 1120 0, /* tp_richcompare */
941 0, /* tp_weaklistoffset */ 1121 0, /* tp_weaklistoffset */
942 0, /* tp_iter */ 1122 0, /* tp_iter */
943 0, /* tp_iternext */ 1123 0, /* tp_iternext */
944 lru_cache_methods, /* tp_methods */ 1124 lru_cache_methods, /* tp_methods */
945 0, /* tp_members */ 1125 0, /* tp_members */
946 lru_cache_getsetlist, /* tp_getset */ 1126 lru_cache_getsetlist, /* tp_getset */
947 0, /* tp_base */ 1127 0, /* tp_base */
948 0, /* tp_dict */ 1128 0, /* tp_dict */
949 0, /* tp_descr_get */ 1129 lru_cache_descr_get, /* tp_descr_get */
950 0, /* tp_descr_set */ 1130 0, /* tp_descr_set */
951 offsetof(lru_cache_object, dict), /* tp_dictoffset */ 1131 offsetof(lru_cache_object, dict), /* tp_dictoffset */
952 0, /* tp_init */ 1132 0, /* tp_init */
953 0, /* tp_alloc */ 1133 0, /* tp_alloc */
954 lru_cache_new, /* tp_new */ 1134 lru_cache_new, /* tp_new */
955 }; 1135 };
956 1136
957 /* module level code ********************************************************/ 1137 /* module level code ********************************************************/
958 1138
959 PyDoc_STRVAR(module_doc, 1139 PyDoc_STRVAR(module_doc,
960 "Tools that operate on functions."); 1140 "Tools that operate on functions.");
961 1141
962 static PyMethodDef module_methods[] = { 1142 static PyMethodDef module_methods[] = {
963 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 1143 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
964 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 1144 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
965 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 1145 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
966 {NULL, NULL} /* sentinel */ 1146 {NULL, NULL} /* sentinel */
967 }; 1147 };
968 1148
969 static void 1149 static void
970 module_free(void *m) 1150 module_free(void *m)
971 { 1151 {
972 Py_DECREF(kwd_mark); 1152 Py_CLEAR(kwd_mark);
973 } 1153 }
974 1154
975 static struct PyModuleDef _functoolsmodule = { 1155 static struct PyModuleDef _functoolsmodule = {
976 PyModuleDef_HEAD_INIT, 1156 PyModuleDef_HEAD_INIT,
977 "_functools", 1157 "_functools",
978 module_doc, 1158 module_doc,
979 -1, 1159 -1,
980 module_methods, 1160 module_methods,
981 NULL, 1161 NULL,
982 NULL, 1162 NULL,
(...skipping 28 matching lines...) Expand all
1011 Py_DECREF(m); 1191 Py_DECREF(m);
1012 return NULL; 1192 return NULL;
1013 } 1193 }
1014 name = strchr(typelist[i]->tp_name, '.'); 1194 name = strchr(typelist[i]->tp_name, '.');
1015 assert (name != NULL); 1195 assert (name != NULL);
1016 Py_INCREF(typelist[i]); 1196 Py_INCREF(typelist[i]);
1017 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1197 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
1018 } 1198 }
1019 return m; 1199 return m;
1020 } 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+