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

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