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

Side by Side Diff: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Patch Set: Created 6 years, 6 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:
View unified diff | Download patch
« no previous file with comments | « Lib/test/test_functools.py ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 */
(...skipping 522 matching lines...) Expand 10 before | Expand all | Expand 10 after
533 PyDoc_STRVAR(functools_reduce_doc, 533 PyDoc_STRVAR(functools_reduce_doc,
534 "reduce(function, sequence[, initial]) -> value\n\ 534 "reduce(function, sequence[, initial]) -> value\n\
535 \n\ 535 \n\
536 Apply a function of two arguments cumulatively to the items of a sequence,\n\ 536 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\ 537 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\ 538 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\ 539 ((((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\ 540 of the sequence in the calculation, and serves as a default when the\n\
541 sequence is empty."); 541 sequence is empty.");
542 542
543 /* lru_cache object **********************************************************/
544
545 /* this object is used delimit args and keywords in the cache keys */
546 static PyObject *kwd_mark;
547
548 struct lru_list_elem;
549 struct lru_cache_object;
550
551 typedef struct lru_list_elem {
552 struct lru_list_elem *prev, *next;
553 PyObject *key, *result;
554 } lru_list_elem;
555
556 typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject * , PyObject *);
557
558 typedef struct lru_cache_object {
559 PyObject_HEAD
560 Py_ssize_t maxsize;
561 PyObject *maxsize_O;
562 PyObject *func;
563 lru_cache_ternaryfunc wrapper;
564 PyObject *cache;
565 PyObject *cache_info_type;
566 Py_ssize_t misses, hits;
567 lru_list_elem root;
568 int typed;
569 PyObject *dict;
570 } lru_cache_object;
571
572 static PyTypeObject lru_cache_type;
573
574 static PyObject *
575 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
576 {
577 PyObject *key, *sorted_items;
578 Py_ssize_t key_size, pos, key_pos;
579
580 /* short path, key will match args anyway, which is a tuple */
581 if (!typed && !kwds) {
582 Py_INCREF(args);
583 return args;
584 }
585
586 if (kwds) {
587 assert(PyDict_Size(kwds));
588 sorted_items = PyDict_Items(kwds);
589 if (!sorted_items)
590 return NULL;
591 if (PyList_Sort(sorted_items) < 0) {
592 Py_DECREF(sorted_items);
593 return NULL;
594 }
595 } else
596 sorted_items = NULL;
597
598 key_size = PyTuple_GET_SIZE(args);
599 if (kwds)
600 key_size += PyList_GET_SIZE(sorted_items);
601 if (typed)
602 key_size *= 2;
603 if (kwds)
604 key_size++;
605
606 key = PyTuple_New(key_size);
607 key_pos = 0;
608
609 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
610 PyObject *item = PyTuple_GET_ITEM(args, pos);
611 Py_INCREF(item);
612 PyTuple_SET_ITEM(key, key_pos++, item);
613 }
614 if (kwds) {
615 Py_INCREF(kwd_mark);
616 PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
617 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
618 PyObject *item = PyList_GET_ITEM(sorted_items, pos);
619 Py_INCREF(item);
620 PyTuple_SET_ITEM(key, key_pos++, item);
621 }
622 }
623 if (typed) {
624 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
625 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
626 Py_INCREF(item);
627 PyTuple_SET_ITEM(key, key_pos++, item);
628 }
629 if (kwds) {
630 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));
632 Py_INCREF(item);
633 PyTuple_SET_ITEM(key, key_pos++, item);
634 }
635 }
636 }
637 assert(key_pos == key_size);
638
639 if (kwds)
640 Py_DECREF(sorted_items);
641 return key;
642 }
643
644 static PyObject *
645 uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s)
646 {
647 PyObject *result = PyObject_Call(self->func, args, kwds);
648 if (!result)
649 return NULL;
650 self->misses++;
651 return result;
652 }
653
654 static PyObject *
655 infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s)
656 {
657 PyObject *result;
658 PyObject *key = lru_cache_make_key(args, kwds, self->typed);
659 if (!key)
660 return NULL;
661 result = PyDict_GetItemWithError(self->cache, key);
662 if (result) {
663 Py_INCREF(result);
664 self->hits++;
665 Py_DECREF(key);
666 return result;
667 }
668 if (PyErr_Occurred()) {
669 Py_DECREF(key);
670 return NULL;
671 }
672 result = PyObject_Call(self->func, args, kwds);
673 if (!result) {
674 Py_DECREF(key);
675 return NULL;
676 }
677 if (PyDict_SetItem(self->cache, key, result) < 0) {
678 Py_DECREF(result);
679 Py_DECREF(key);
680 return NULL;
681 }
682 Py_DECREF(key);
683 self->misses++;
684 return result;
685 }
686
687 static void
688 lru_cache_list_extricate(lru_list_elem *link)
689 {
690 link->prev->next = link->next;
691 link->next->prev = link->prev;
692 }
693
694 static void
695 lru_cache_list_append(lru_list_elem *root, lru_list_elem *link)
696 {
697 lru_list_elem *last = root->prev;
698 last->next = root->prev = link;
699 link->prev = last;
700 link->next = root;
701 }
702
703 static PyObject *
704 bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds )
705 {
706 lru_list_elem *link;
707
708 PyObject *key = lru_cache_make_key(args, kwds, self->typed);
709 if (!key)
710 return NULL;
711 PyObject *value = PyDict_GetItemWithError(self->cache, key);
712 if (value) {
713 lru_list_elem *link = PyCapsule_GetPointer(value, NULL);
714 lru_cache_list_extricate(link);
715 lru_cache_list_append(&self->root, link);
716 self->hits++;
717 Py_DECREF(key);
718 Py_INCREF(link->result);
719 return link->result;
720 }
721 if (PyErr_Occurred()) {
722 Py_DECREF(key);
723 return NULL;
724 }
725 PyObject *result = PyObject_Call(self->func, args, kwds);
726 if (!result) {
727 Py_DECREF(key);
728 return NULL;
729 }
730 if (PyDict_Size(self->cache) == self->maxsize) {
731 /* extricate the oldest item */
732 link = self->root.next;
733 lru_cache_list_extricate(link);
734 /* grab its capsule */
735 value = PyDict_GetItem(self->cache, link->key);
736 if (value == NULL) {
737 Py_DECREF(key);
738 return NULL;
739 }
740 Py_INCREF(value);
741 /* remove its key from the cache */
742 if (PyDict_DelItem(self->cache, link->key) < 0) {
storchaka 2012/12/21 22:22:09 Py_DECREF(value);
asvetlov 2012/12/21 22:44:59 Just move incref after if block, right?
storchaka 2012/12/21 22:53:21 No. If PyDict_DelItem() success then value's and k
743 Py_DECREF(key);
744 return NULL;
745 }
746 /* scrub the result from the link */
747 Py_DECREF(link->result);
748 } else {
749 link = PyMem_New(lru_list_elem, 1);
750 if (link == NULL) {
751 PyErr_NoMemory();
752 return NULL;
753 }
754 value = PyCapsule_New(link, NULL, NULL);
755 }
756 lru_cache_list_append(&self->root, link);
757 link->key = key;
758 Py_INCREF(result);
759 link->result = result;
760 if (PyDict_SetItem(self->cache, key, value) < 0) {
761 return NULL;
762 }
763 Py_DECREF(value);
storchaka 2012/12/21 22:22:09 It was only a question about Py_DECREF(key). On so
asvetlov 2012/12/21 22:44:59 key REF moved to link->key, right? as well as resu
storchaka 2012/12/21 22:53:21 link is not a Python object and can't own Python o
764 self->misses++;
765 return result;
766 }
767
768 static PyObject *
769 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
770 {
771 PyObject *func, *maxsize_O, *cache_info_type;
772 int typed;
773 lru_cache_object *obj;
774 Py_ssize_t maxsize;
775 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
776 static char *keywords[] = {"user_function", "maxsize", "typed",
777 "cache_info_type", NULL};
778
779 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
780 &func, &maxsize_O, &typed,
781 &cache_info_type)) {
782 return NULL;
783 }
784
785 if (!PyCallable_Check(func)) {
786 PyErr_SetString(PyExc_TypeError,
787 "the first argument must be callable");
788 return NULL;
789 }
790
791 /* select the caching function, and make/inc maxsize_O */
792 if (maxsize_O == Py_None) {
793 wrapper = infinite_lru_cache_wrapper;
794 /* use this only to initialize lru_cache_object attribute maxsize */
795 maxsize = -1;
796 } else if (PyNumber_Check(maxsize_O)) {
797 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
798 if (maxsize == -1 && PyErr_Occurred())
799 return NULL;
800 if (maxsize == 0)
801 wrapper = uncached_lru_cache_wrapper;
802 else
803 wrapper = bounded_lru_cache_wrapper;
804 } else {
805 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
806 return NULL;
807 }
808
809 obj = (lru_cache_object *)type->tp_alloc(type, 0);
810 if (obj == NULL)
811 return NULL;
812
813 obj->root.prev = &obj->root;
814 obj->root.next = &obj->root;
815 obj->maxsize = maxsize;
816 Py_INCREF(maxsize_O);
817 obj->maxsize_O = maxsize_O;
818 if (!(obj->cache = PyDict_New())) {
819 Py_DECREF(obj);
820 Py_DECREF(maxsize_O);
821 return NULL;
822 }
823 Py_INCREF(func);
824 obj->func = func;
825 obj->wrapper = wrapper;
826 obj->misses = obj->hits = 0;
827 obj->typed = typed;
828 Py_INCREF(cache_info_type);
829 obj->cache_info_type = cache_info_type;
830
831 return (PyObject *)obj;
832 }
833
834 static void
835 lru_cache_clear_list(lru_list_elem *root)
836 {
837 lru_list_elem *link = root->next;
838 while (link != root) {
839 lru_list_elem *next = link->next;
840 Py_DECREF(link->result);
841 PyMem_Free(link);
842 link = next;
843 }
844 }
845
846 static void
847 lru_cache_dealloc(lru_cache_object *obj)
848 {
849 Py_XDECREF(obj->maxsize_O);
850 Py_XDECREF(obj->func);
851 Py_XDECREF(obj->cache);
852 Py_XDECREF(obj->dict);
853 Py_XDECREF(obj->cache_info_type);
854 lru_cache_clear_list(&obj->root);
855 Py_TYPE(obj)->tp_free(obj);
856 }
857
858 static PyObject *
859 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
860 {
861 return self->wrapper(self, args, kwds);
862 }
863
864 static PyObject *
865 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
866 {
867 return PyObject_CallFunction(self->cache_info_type, "nnOn",
868 self->hits, self->misses, self->maxsize_O,
869 PyDict_Size(self->cache));
870 }
871
872 static PyObject *
873 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
874 {
875 do {
876 PyDict_Clear(self->cache);
877 } while (PyDict_Size(self->cache));
878 self->hits = self->misses = 0;
879 lru_cache_clear_list(&self->root);
880 self->root.next = self->root.prev = &self->root;
881 Py_RETURN_NONE;
882 }
883
884 PyDoc_STRVAR(lru_cache_doc,
885 "Create a cached callable that wraps another function.\n\
886 \n\
887 user_function: the function being cached\n\
888 \n\
889 maxsize: 0 for no caching\n\
890 None for unlimited cache size\n\
891 n for a bounded cache\n\
892 \n\
893 typed: False cache f(3) and f(3.0) as identical calls\n\
894 True cache f(3) and f(3.0) as distinct calls\n\
895 \n\
896 cache_info_type: namedtuple class with the fields:\n\
897 hits misses currsize maxsize\n"
898 );
899
900 static PyMethodDef lru_cache_methods[] = {
901 {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
902 {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
903 {NULL}
904 };
905
906 static PyGetSetDef lru_cache_getsetlist[] = {
907 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
908 {NULL}
909 };
910
911 static PyTypeObject lru_cache_type = {
912 PyVarObject_HEAD_INIT(NULL, 0)
913 "functools._lru_cache_wrapper", /* tp_name */
914 sizeof(lru_cache_object), /* tp_basicsize */
915 0, /* tp_itemsize */
916 /* methods */
917 (destructor)lru_cache_dealloc, /* tp_dealloc */
918 0, /* tp_print */
919 0, /* tp_getattr */
920 0, /* tp_setattr */
921 0, /* tp_reserved */
922 0, /* tp_repr */
923 0, /* tp_as_number */
924 0, /* tp_as_sequence */
925 0, /* tp_as_mapping */
926 0, /* tp_hash */
927 (ternaryfunc)lru_cache_call, /* tp_call */
928 0, /* tp_str */
929 0, /* tp_getattro */
930 0, /* tp_setattro */
931 0, /* tp_as_buffer */
932 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE,
933 /* tp_flags */
934 lru_cache_doc, /* tp_doc */
935 0, /* tp_traverse */
936 0, /* tp_clear */
937 0, /* tp_richcompare */
938 0, /* tp_weaklistoffset */
939 0, /* tp_iter */
940 0, /* tp_iternext */
941 lru_cache_methods, /* tp_methods */
942 0, /* tp_members */
943 lru_cache_getsetlist, /* tp_getset */
944 0, /* tp_base */
945 0, /* tp_dict */
946 0, /* tp_descr_get */
947 0, /* tp_descr_set */
948 offsetof(lru_cache_object, dict), /* tp_dictoffset */
949 0, /* tp_init */
950 0, /* tp_alloc */
951 lru_cache_new, /* tp_new */
952 };
953
543 /* module level code ********************************************************/ 954 /* module level code ********************************************************/
544 955
545 PyDoc_STRVAR(module_doc, 956 PyDoc_STRVAR(module_doc,
546 "Tools that operate on functions."); 957 "Tools that operate on functions.");
547 958
548 static PyMethodDef module_methods[] = { 959 static PyMethodDef module_methods[] = {
549 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 960 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
550 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 961 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
551 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 962 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
552 {NULL, NULL} /* sentinel */ 963 {NULL, NULL} /* sentinel */
553 }; 964 };
554 965
966 static void
967 module_free(void *m)
968 {
969 Py_DECREF(kwd_mark);
970 }
555 971
556 static struct PyModuleDef _functoolsmodule = { 972 static struct PyModuleDef _functoolsmodule = {
557 PyModuleDef_HEAD_INIT, 973 PyModuleDef_HEAD_INIT,
558 "_functools", 974 "_functools",
559 module_doc, 975 module_doc,
560 -1, 976 -1,
561 module_methods, 977 module_methods,
562 NULL, 978 NULL,
563 NULL, 979 NULL,
564 NULL, 980 NULL,
565 NULL 981 module_free,
566 }; 982 };
567 983
568 PyMODINIT_FUNC 984 PyMODINIT_FUNC
569 PyInit__functools(void) 985 PyInit__functools(void)
570 { 986 {
571 int i; 987 int i;
572 PyObject *m; 988 PyObject *m;
573 char *name; 989 char *name;
574 PyTypeObject *typelist[] = { 990 PyTypeObject *typelist[] = {
575 &partial_type, 991 &partial_type,
992 &lru_cache_type,
576 NULL 993 NULL
577 }; 994 };
578 995
579 m = PyModule_Create(&_functoolsmodule); 996 m = PyModule_Create(&_functoolsmodule);
580 if (m == NULL) 997 if (m == NULL)
581 return NULL; 998 return NULL;
999
1000 kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL);
1001 if (!kwd_mark) {
1002 Py_DECREF(m);
1003 return NULL;
1004 }
582 1005
583 for (i=0 ; typelist[i] != NULL ; i++) { 1006 for (i=0 ; typelist[i] != NULL ; i++) {
584 if (PyType_Ready(typelist[i]) < 0) { 1007 if (PyType_Ready(typelist[i]) < 0) {
585 Py_DECREF(m); 1008 Py_DECREF(m);
586 return NULL; 1009 return NULL;
587 } 1010 }
588 name = strchr(typelist[i]->tp_name, '.'); 1011 name = strchr(typelist[i]->tp_name, '.');
589 assert (name != NULL); 1012 assert (name != NULL);
590 Py_INCREF(typelist[i]); 1013 Py_INCREF(typelist[i]);
591 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1014 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
592 } 1015 }
593 return m; 1016 return m;
594 } 1017 }
OLDNEW
« no previous file with comments | « Lib/test/test_functools.py ('k') | no next file » | no next file with comments »

RSS Feeds Recent Issues | This issue
This is Rietveld 894c83f36cb7+