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

Side by Side Diff: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Patch Set: Created 7 years, 3 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/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
548 typedef struct lru_list_elem lru_list_elem;
storchaka 2012/11/24 15:02:52 Remove this line and use "struct lru_list_elem *p
549
550 typedef struct lru_list_elem {
551 lru_list_elem *prev, *next;
552 PyObject *key, *result;
553 } lru_list_elem;
554
555 typedef struct lru_cache_object lru_cache_object;
storchaka 2012/11/24 15:02:52 Same as above.
556
557 typedef PyObject *(*lru_cache_ternaryfunc)(lru_cache_object *, PyObject *, PyObj ect *);
storchaka 2012/11/24 15:02:52 Please split all lines longer than 79 characters t
558
559 typedef struct lru_cache_object {
560 PyObject_HEAD
561 Py_ssize_t maxsize;
562 PyObject *maxsize_O;
563 PyObject *func;
564 lru_cache_ternaryfunc wrapper;
565 PyObject *cache;
566 PyObject *cache_info_type;
567 Py_ssize_t misses, hits;
568 lru_list_elem root;
569 int typed;
570 PyObject *dict;
571 } lru_cache_object;
572
573 static PyTypeObject lru_cache_type;
574
575 static PyObject *
576 lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
577 {
578 PyObject *key, *sorted_items;
579 Py_ssize_t key_size, pos, key_pos;
580
581 /* short path, key will match args anyway, which is a tuple */
582 if (!typed && !kwds) {
583 Py_INCREF(args);
584 return args;
585 }
586
587 if (kwds) {
588 assert(PyDict_Size(kwds));
589 if (!(sorted_items = PyDict_Items(kwds)))
storchaka 2012/11/24 15:02:52 Assignment in expression is not needed here. You c
590 return NULL;
591 if (0 > PyList_Sort(sorted_items)) {
storchaka 2012/11/24 15:02:52 Is used somewhere in the code such reversed form o
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 PyObject *key = lru_cache_make_key(args, kwds, self->typed);
707 if (!key)
708 return NULL;
709 PyObject *value = PyDict_GetItemWithError(self->cache, key);
710 if (value) {
711 lru_list_elem *link = PyCapsule_GetPointer(value, NULL);
712 lru_cache_list_extricate(link);
713 lru_cache_list_append(&self->root, link);
714 self->hits++;
715 Py_DECREF(key);
716 Py_INCREF(link->result);
717 return link->result;
718 }
719 if (PyErr_Occurred()) {
720 Py_DECREF(key);
721 return NULL;
722 }
723 PyObject *result = PyObject_Call(self->func, args, kwds);
724 if (!result) {
725 Py_DECREF(key);
726 return NULL;
727 }
728 lru_list_elem *link;
729 if (PyDict_Size(self->cache) == self->maxsize) {
730 /* extricate the oldest item */
731 link = self->root.next;
732 lru_cache_list_extricate(link);
733 /* grab its capsule */
734 value = PyDict_GetItem(self->cache, link->key);
storchaka 2012/11/24 15:02:52 Check value for NULL.
735 Py_INCREF(value);
736 /* remove its key from the cache */
737 if (0 > PyDict_DelItem(self->cache, link->key))
storchaka 2012/11/24 15:02:52 Reversed comparison.
738 abort();
storchaka 2012/11/24 15:02:52 It should not be. Raise a SystemError. You can ge
739 /* scrub the result from the link */
740 Py_DECREF(link->result);
741 } else {
742 link = PyMem_New(lru_list_elem, 1);
storchaka 2012/11/24 15:02:52 Check for NULL.
743 value = PyCapsule_New(link, NULL, NULL);
744 }
745 lru_cache_list_append(&self->root, link);
746 link->key = key;
747 link->result = result;
748 Py_INCREF(result);
749 if (0 > PyDict_SetItem(self->cache, key, value)) abort();
storchaka 2012/11/24 15:02:52 Reversed comparison, abort(), condition and "then"
750 Py_DECREF(key);
storchaka 2012/11/24 15:02:52 Does not linked list own keys and values?
751 Py_DECREF(value);
752 self->misses++;
753 return result;
754 }
755
756 static PyObject *
757 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
758 {
759 PyObject *func, *maxsize_O, *typed_O, *cache_info_type;
760 int typed;
761 lru_cache_object *obj;
762 Py_ssize_t maxsize;
763 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
764 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};
766
767 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOOO:lru_cache", keywords,
storchaka 2012/11/24 15:02:52 Use a new format "p" for `typed`.
768 &func, &maxsize_O, &typed_O,
769 &cache_info_type)) {
770 return NULL;
771 }
772
773 if (!PyCallable_Check(func)) {
774 PyErr_SetString(PyExc_TypeError,
775 "the first argument must be callable");
776 return NULL;
777 }
778
779 // 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) {
781 wrapper = infinite_lru_cache_wrapper;
782 Py_INCREF(maxsize_O);
storchaka 2012/11/24 15:02:52 You can move all Py_INCREF(maxsize_O) down, right
783 } else if (PyNumber_Check(maxsize_O)) {
784 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
785 if (maxsize == -1 && PyErr_Occurred())
786 return NULL;
787 if (maxsize == 0)
788 wrapper = uncached_lru_cache_wrapper;
789 else
790 wrapper = bounded_lru_cache_wrapper;
791 Py_INCREF(maxsize_O);
792 } else {
793 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
794 return NULL;
795 }
796
797 if (typed_O) {
798 int err = PyObject_IsTrue(typed_O);
799 if (err < 0) {
800 Py_DECREF(maxsize_O);
801 return NULL;
802 }
803 typed = err;
804 } else
805 typed = 0;
806
807 obj = (lru_cache_object *)type->tp_alloc(type, 0);
808 if (obj == NULL) {
809 Py_DECREF(maxsize_O);
810 return NULL;
811 }
812
813 obj->root.prev = &obj->root;
814 obj->root.next = &obj->root;
815 obj->maxsize = maxsize;
storchaka 2012/11/24 15:02:52 ‘maxsize’ may be used uninitialized (when maxsize_
816 obj->maxsize_O = maxsize_O;
817 if (!(obj->cache = PyDict_New())) {
818 Py_DECREF(obj);
819 Py_DECREF(maxsize_O);
820 return NULL;
821 }
822 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;
825 obj->misses = obj->hits = 0;
826 obj->typed = typed;
827 obj->cache_info_type = cache_info_type;
828 Py_INCREF(cache_info_type);
storchaka 2012/11/24 15:02:52 Same as above.
829
830 return (PyObject *)obj;
831 }
832
833 static void
834 lru_cache_clear_list(lru_list_elem *root)
835 {
836 lru_list_elem *link = root->next;
837 while (link != root) {
838 lru_list_elem *next = link->next;
839 Py_DECREF(link->result);
840 PyMem_Free(link);
841 link = next;
842 }
843 }
844
845 static void
846 lru_cache_dealloc(lru_cache_object *obj)
847 {
848 Py_XDECREF(obj->maxsize_O);
849 Py_XDECREF(obj->func);
850 Py_XDECREF(obj->cache);
851 Py_XDECREF(obj->dict);
852 Py_XDECREF(obj->cache_info_type);
853 lru_cache_clear_list(&obj->root);
854 Py_TYPE(obj)->tp_free(obj);
855 }
856
857 static PyObject *
858 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
859 {
860 return self->wrapper(self, args, kwds);
861 }
862
863 static PyObject *
864 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
865 {
866 return PyObject_CallFunction(self->cache_info_type, "nnOn",
867 self->hits, self->misses, self->maxsize_O,
868 PyDict_Size(self->cache));
869 }
870
871 static PyObject *
872 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
873 {
874 do PyDict_Clear(self->cache); while (PyDict_Size(self->cache));
storchaka 2012/11/24 15:02:52 Please split this loop on several lines and use br
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/11/24 15:02:52 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))) {
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/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+