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

Side by Side Diff: Modules/_functoolsmodule.c

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

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