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

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;
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
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));
AntoinePitrou 2012/12/22 21:49:49 Are you sure it can't be 0?
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));
AntoinePitrou 2012/12/22 21:49:49 This is a long line, can you wrap it?
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 PyObject *key, *value, *result;
708
709 key = lru_cache_make_key(args, kwds, self->typed);
710 if (!key)
711 return NULL;
712 value = PyDict_GetItemWithError(self->cache, key);
713 if (value) {
714 lru_list_elem *link = PyCapsule_GetPointer(value, NULL);
715 lru_cache_list_extricate(link);
716 lru_cache_list_append(&self->root, link);
717 self->hits++;
718 Py_DECREF(key);
719 Py_INCREF(link->result);
720 return link->result;
721 }
722 if (PyErr_Occurred()) {
723 Py_DECREF(key);
724 return NULL;
725 }
726 result = PyObject_Call(self->func, args, kwds);
727 if (!result) {
728 Py_DECREF(key);
729 return NULL;
730 }
731 if (PyDict_Size(self->cache) == self->maxsize) {
732 /* extricate the oldest item */
733 link = self->root.next;
734 lru_cache_list_extricate(link);
735 /* grab its capsule */
736 value = PyDict_GetItem(self->cache, link->key);
737 if (value == NULL) {
738 Py_DECREF(key);
739 return NULL;
740 }
741 Py_INCREF(value);
742 /* remove its key from the cache */
743 if (PyDict_DelItem(self->cache, link->key) < 0) {
744 Py_DECREF(value);
745 Py_DECREF(key);
746 return NULL;
747 }
748 /* scrub the result from the link */
749 Py_DECREF(link->result);
750 } else {
751 link = PyMem_New(lru_list_elem, 1);
752 if (link == NULL) {
753 PyErr_NoMemory();
754 return NULL;
755 }
756 value = PyCapsule_New(link, NULL, NULL);
AntoinePitrou 2012/12/22 21:49:49 You should check value for non-NULL.
757 }
758 lru_cache_list_append(&self->root, link);
759 link->key = key;
760 Py_INCREF(result);
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++;
768 return result;
769 }
770
771 static PyObject *
772 lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
773 {
774 PyObject *func, *maxsize_O, *cache_info_type;
775 int typed;
776 lru_cache_object *obj;
777 Py_ssize_t maxsize;
778 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
779 static char *keywords[] = {"user_function", "maxsize", "typed",
780 "cache_info_type", NULL};
781
storchaka 2012/12/23 18:18:49 Trailing whitespaces.
782 if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
783 &func, &maxsize_O, &typed,
784 &cache_info_type)) {
785 return NULL;
786 }
787
788 if (!PyCallable_Check(func)) {
789 PyErr_SetString(PyExc_TypeError,
790 "the first argument must be callable");
791 return NULL;
792 }
793
794 /* select the caching function, and make/inc maxsize_O */
795 if (maxsize_O == Py_None) {
796 wrapper = infinite_lru_cache_wrapper;
797 /* use this only to initialize lru_cache_object attribute maxsize */
798 maxsize = -1;
storchaka 2012/12/23 18:18:49 Trailing whitespaces.
799 } else if (PyNumber_Check(maxsize_O)) {
800 maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
801 if (maxsize == -1 && PyErr_Occurred())
802 return NULL;
803 if (maxsize == 0)
804 wrapper = uncached_lru_cache_wrapper;
805 else
806 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 {
808 PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
809 return NULL;
810 }
811
812 obj = (lru_cache_object *)type->tp_alloc(type, 0);
813 if (obj == NULL)
814 return NULL;
815
816 obj->root.prev = &obj->root;
817 obj->root.next = &obj->root;
818 obj->maxsize = maxsize;
819 Py_INCREF(maxsize_O);
820 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);
827 obj->func = func;
828 obj->wrapper = wrapper;
829 obj->misses = obj->hits = 0;
830 obj->typed = typed;
831 Py_INCREF(cache_info_type);
832 obj->cache_info_type = cache_info_type;
833
834 return (PyObject *)obj;
835 }
836
837 static void
838 lru_cache_clear_list(lru_list_elem *root)
839 {
840 lru_list_elem *link = root->next;
841 while (link != root) {
842 lru_list_elem *next = link->next;
843 Py_DECREF(link->result);
AntoinePitrou 2012/12/22 21:49:49 This could release the GIL, and if another thread
844 PyMem_Free(link);
845 link = next;
846 }
847 }
848
849 static void
850 lru_cache_dealloc(lru_cache_object *obj)
851 {
852 Py_XDECREF(obj->maxsize_O);
853 Py_XDECREF(obj->func);
854 Py_XDECREF(obj->cache);
855 Py_XDECREF(obj->dict);
856 Py_XDECREF(obj->cache_info_type);
857 lru_cache_clear_list(&obj->root);
858 Py_TYPE(obj)->tp_free(obj);
859 }
860
861 static PyObject *
862 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
863 {
864 return self->wrapper(self, args, kwds);
865 }
866
867 static PyObject *
868 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
869 {
870 return PyObject_CallFunction(self->cache_info_type, "nnOn",
871 self->hits, self->misses, self->maxsize_O,
872 PyDict_Size(self->cache));
873 }
874
875 static PyObject *
876 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
877 {
878 do {
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;
882 lru_cache_clear_list(&self->root);
883 self->root.next = self->root.prev = &self->root;
884 Py_RETURN_NONE;
885 }
886
887 PyDoc_STRVAR(lru_cache_doc,
888 "Create a cached callable that wraps another function.\n\
889 \n\
890 user_function: the function being cached\n\
891 \n\
892 maxsize: 0 for no caching\n\
893 None for unlimited cache size\n\
894 n for a bounded cache\n\
895 \n\
896 typed: False cache f(3) and f(3.0) as identical calls\n\
897 True cache f(3) and f(3.0) as distinct calls\n\
898 \n\
899 cache_info_type: namedtuple class with the fields:\n\
900 hits misses currsize maxsize\n"
901 );
902
903 static PyMethodDef lru_cache_methods[] = {
904 {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
905 {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
906 {NULL}
907 };
908
909 static PyGetSetDef lru_cache_getsetlist[] = {
910 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
911 {NULL}
912 };
913
914 static PyTypeObject lru_cache_type = {
915 PyVarObject_HEAD_INIT(NULL, 0)
916 "functools._lru_cache_wrapper", /* tp_name */
917 sizeof(lru_cache_object), /* tp_basicsize */
918 0, /* tp_itemsize */
919 /* methods */
920 (destructor)lru_cache_dealloc, /* tp_dealloc */
921 0, /* tp_print */
922 0, /* tp_getattr */
923 0, /* tp_setattr */
924 0, /* tp_reserved */
925 0, /* tp_repr */
926 0, /* tp_as_number */
927 0, /* tp_as_sequence */
928 0, /* tp_as_mapping */
929 0, /* tp_hash */
930 (ternaryfunc)lru_cache_call, /* tp_call */
931 0, /* tp_str */
932 0, /* tp_getattro */
933 0, /* tp_setattro */
934 0, /* tp_as_buffer */
935 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE,
AntoinePitrou 2012/12/22 21:49:49 The type needs to be GC-enabled, because there can
936 /* tp_flags */
937 lru_cache_doc, /* tp_doc */
938 0, /* tp_traverse */
939 0, /* tp_clear */
940 0, /* tp_richcompare */
941 0, /* tp_weaklistoffset */
942 0, /* tp_iter */
943 0, /* tp_iternext */
944 lru_cache_methods, /* tp_methods */
945 0, /* tp_members */
946 lru_cache_getsetlist, /* tp_getset */
947 0, /* tp_base */
948 0, /* tp_dict */
949 0, /* tp_descr_get */
950 0, /* tp_descr_set */
951 offsetof(lru_cache_object, dict), /* tp_dictoffset */
952 0, /* tp_init */
953 0, /* tp_alloc */
954 lru_cache_new, /* tp_new */
955 };
956
543 /* module level code ********************************************************/ 957 /* module level code ********************************************************/
544 958
545 PyDoc_STRVAR(module_doc, 959 PyDoc_STRVAR(module_doc,
546 "Tools that operate on functions."); 960 "Tools that operate on functions.");
547 961
548 static PyMethodDef module_methods[] = { 962 static PyMethodDef module_methods[] = {
549 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 963 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
550 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 964 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
551 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 965 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
552 {NULL, NULL} /* sentinel */ 966 {NULL, NULL} /* sentinel */
553 }; 967 };
554 968
969 static void
970 module_free(void *m)
971 {
972 Py_DECREF(kwd_mark);
973 }
555 974
556 static struct PyModuleDef _functoolsmodule = { 975 static struct PyModuleDef _functoolsmodule = {
557 PyModuleDef_HEAD_INIT, 976 PyModuleDef_HEAD_INIT,
558 "_functools", 977 "_functools",
559 module_doc, 978 module_doc,
560 -1, 979 -1,
561 module_methods, 980 module_methods,
562 NULL, 981 NULL,
563 NULL, 982 NULL,
564 NULL, 983 NULL,
565 NULL 984 module_free,
566 }; 985 };
567 986
568 PyMODINIT_FUNC 987 PyMODINIT_FUNC
569 PyInit__functools(void) 988 PyInit__functools(void)
570 { 989 {
571 int i; 990 int i;
572 PyObject *m; 991 PyObject *m;
573 char *name; 992 char *name;
574 PyTypeObject *typelist[] = { 993 PyTypeObject *typelist[] = {
575 &partial_type, 994 &partial_type,
995 &lru_cache_type,
576 NULL 996 NULL
577 }; 997 };
578 998
579 m = PyModule_Create(&_functoolsmodule); 999 m = PyModule_Create(&_functoolsmodule);
580 if (m == NULL) 1000 if (m == NULL)
581 return NULL; 1001 return NULL;
1002
1003 kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL);
1004 if (!kwd_mark) {
1005 Py_DECREF(m);
1006 return NULL;
1007 }
582 1008
583 for (i=0 ; typelist[i] != NULL ; i++) { 1009 for (i=0 ; typelist[i] != NULL ; i++) {
584 if (PyType_Ready(typelist[i]) < 0) { 1010 if (PyType_Ready(typelist[i]) < 0) {
585 Py_DECREF(m); 1011 Py_DECREF(m);
586 return NULL; 1012 return NULL;
587 } 1013 }
588 name = strchr(typelist[i]->tp_name, '.'); 1014 name = strchr(typelist[i]->tp_name, '.');
589 assert (name != NULL); 1015 assert (name != NULL);
590 Py_INCREF(typelist[i]); 1016 Py_INCREF(typelist[i]);
591 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 1017 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
592 } 1018 }
593 return m; 1019 return m;
594 } 1020 }
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+