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

Side by Side Diff: Modules/_functoolsmodule.c

Issue 14373: C implementation of functools.lru_cache
Patch Set: Created 7 years, 8 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 typedef struct lru_list_elem lru_list_elem;
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;
556
557 typedef PyObject *(*lru_cache_ternaryfunc)(lru_cache_object *, PyObject *, PyObj ect *);
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 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 if (!(sorted_items = PyDict_Items(kwds)))
589 return NULL;
590 if (0 > PyList_Sort(sorted_items)) {
591 Py_DECREF(sorted_items);
592 return NULL;
593 }
594 } else
595 sorted_items = NULL;
596
597 key_size = PyTuple_GET_SIZE(args);
598 if (kwds)
599 key_size += PyList_GET_SIZE(sorted_items);
600 if (typed)
601 key_size *= 2;
602 if (kwds)
603 key_size++;
604
605 key = PyTuple_New(key_size);
606 key_pos = 0;
607
608 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
609 PyObject *item = PyTuple_GET_ITEM(args, pos);
610 Py_INCREF(item);
611 PyTuple_SET_ITEM(key, key_pos++, item);
612 }
613 if (kwds) {
614 Py_INCREF(kwd_mark);
615 PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
616 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
617 PyObject *item = PyList_GET_ITEM(sorted_items, pos);
618 Py_INCREF(item);
619 PyTuple_SET_ITEM(key, key_pos++, item);
620 }
621 }
622 if (typed) {
623 for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
624 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
625 Py_INCREF(item);
626 PyTuple_SET_ITEM(key, key_pos++, item);
627 }
628 if (kwds) {
629 for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
630 PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(PyList_GET _ITEM(sorted_items, pos), 1));
631 Py_INCREF(item);
632 PyTuple_SET_ITEM(key, key_pos++, item);
633 }
634 }
635 }
636 assert(key_pos == key_size);
637 if (kwds)
638 Py_DECREF(sorted_items);
639 return key;
640 }
641
642 static PyObject *
643 uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s)
644 {
645 PyObject *result = PyObject_Call(self->func, args, kwds);
646 if (!result)
647 return NULL;
648 self->misses++;
649 return result;
650 }
651
652 static PyObject *
653 infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwd s)
654 {
655 PyObject *result;
656 PyObject *key = lru_cache_make_key(args, kwds, self->typed);
657 if (!key)
658 return NULL;
659 result = PyDict_GetItemWithError(self->cache, key);
660 if (result) {
661 Py_INCREF(result);
662 self->hits++;
663 Py_DECREF(key);
664 return result;
665 }
666 if (PyErr_Occurred()) {
667 Py_DECREF(key);
668 return NULL;
669 }
670 result = PyObject_Call(self->func, args, kwds);
671 if (!result) {
672 Py_DECREF(key);
673 return NULL;
674 }
675 if (PyDict_SetItem(self->cache, key, result) < 0) {
676 Py_DECREF(result);
677 Py_DECREF(key);
678 return NULL;
679 }
680 Py_DECREF(key);
681 self->misses++;
682 return result;
683 }
684
685 static void
686 lru_cache_list_extricate(lru_list_elem *link)
687 {
688 link->prev->next = link->next;
689 link->next->prev = link->prev;
690 }
691
692 static void
693 lru_cache_list_append(lru_list_elem *root, lru_list_elem *link)
694 {
695 lru_list_elem *last = root->prev;
696 last->next = root->prev = link;
697 link->prev = last;
698 link->next = root;
699 }
700
701 static PyObject *
702 bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds )
703 {
704 PyObject *key = lru_cache_make_key(args, kwds, self->typed);
705 if (!key)
706 return NULL;
707 PyObject *value = PyDict_GetItemWithError(self->cache, key);
708 if (value) {
709 lru_list_elem *link = PyCapsule_GetPointer(value, NULL);
710 lru_cache_list_extricate(link);
711 lru_cache_list_append(&self->root, link);
712 self->hits++;
713 Py_DECREF(key);
714 Py_INCREF(link->result);
715 return link->result;
716 }
717 if (PyErr_Occurred()) {
718 Py_DECREF(key);
719 return NULL;
720 }
721 PyObject *result = PyObject_Call(self->func, args, kwds);
722 if (!result) {
723 Py_DECREF(key);
724 return NULL;
725 }
726 lru_list_elem *link;
727 if (PyDict_Size(self->cache) == self->maxsize) {
728 /* extricate the oldest item */
729 link = self->root.next;
730 lru_cache_list_extricate(link);
731 /* grab its capsule */
732 value = PyDict_GetItem(self->cache, link->key);
733 Py_INCREF(value);
734 /* remove its key from the cache */
735 if (0 > PyDict_DelItem(self->cache, link->key))
736 abort();
737 /* scrub the result from the link */
738 Py_DECREF(link->result);
739 } else {
740 link = PyMem_New(lru_list_elem, 1);
741 value = PyCapsule_New(link, NULL, NULL);
742 }
743 lru_cache_list_append(&self->root, link);
744 link->key = key;
745 link->result = result;
746 Py_INCREF(result);
747 if (0 > PyDict_SetItem(self->cache, key, value)) abort();
748 Py_DECREF(key);
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;
758 PyObject *maxsize_O = NULL;
759 PyObject *typed_O = NULL;
760 int typed;
761 lru_cache_object *obj;
762 Py_ssize_t maxsize = 100;
763 PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
764 static char *keywords[] = {"func", "maxsize", "typed", NULL};
765
766 if (!PyArg_ParseTupleAndKeywords(args, kw, "O|OO:lru_cache", keywords,
767 &func, &maxsize_O, &typed_O)) {
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 if (maxsize_O == NULL) {
778 maxsize_O = PyLong_FromSsize_t(maxsize);
779 wrapper = bounded_lru_cache_wrapper;
780 } else if (maxsize_O == Py_None) {
781 wrapper = infinite_lru_cache_wrapper;
782 Py_INCREF(maxsize_O);
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;
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);
824 obj->wrapper = wrapper;
825 obj->misses = obj->hits = 0;
826 obj->typed = typed;
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 lru_cache_clear_list(&obj->root);
851 Py_TYPE(obj)->tp_free(obj);
852 }
853
854 static PyObject *
855 lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
856 {
857 return self->wrapper(self, args, kwds);
858 }
859
860 static PyObject *
861 lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
862 {
863 PyObject *ret, *functools = PyImport_ImportModuleNoBlock("functools");
864 if (functools == NULL)
865 return NULL;
866 ret = PyObject_CallMethod(functools, "_CacheInfo", "nnOn",
867 self->hits, self->misses, self->maxsize_O,
868 PyDict_Size(self->cache));
869 Py_DECREF(functools);
870 return ret;
871 }
872
873 static PyObject *
874 lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
875 {
876 PyDict_Clear(self->cache);
877 self->hits = self->misses = 0;
878 lru_cache_clear_list(&self->root);
879 self->root.next = self->root.prev = &self->root;
880 Py_RETURN_NONE;
881 }
882
883 static PyMethodDef lru_cache_methods[] = {
884 {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
885 {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
886 {NULL}
887 };
888
889 static PyGetSetDef lru_cache_getsetlist[] = {
890 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
891 {NULL}
892 };
893
894 static PyTypeObject lru_cache_type = {
895 PyVarObject_HEAD_INIT(NULL, 0)
896 "functools._lru_cache", /* tp_name */
897 sizeof(lru_cache_object), /* tp_basicsize */
898 0, /* tp_itemsize */
899 /* methods */
900 (destructor)lru_cache_dealloc, /* tp_dealloc */
901 0, /* tp_print */
902 0, /* tp_getattr */
903 0, /* tp_setattr */
904 0, /* tp_reserved */
905 0, /* tp_repr */
906 0, /* tp_as_number */
907 0, /* tp_as_sequence */
908 0, /* tp_as_mapping */
909 0, /* tp_hash */
910 (ternaryfunc)lru_cache_call, /* tp_call */
911 0, /* tp_str */
912 0, /* tp_getattro */
913 0, /* tp_setattro */
914 0, /* tp_as_buffer */
915 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE,
916 /* tp_flags */
917 0, /* tp_doc */
918 0, /* tp_traverse */
919 0, /* tp_clear */
920 0, /* tp_richcompare */
921 0, /* tp_weaklistoffset */
922 0, /* tp_iter */
923 0, /* tp_iternext */
924 lru_cache_methods, /* tp_methods */
925 0, /* tp_members */
926 lru_cache_getsetlist, /* tp_getset */
927 0, /* tp_base */
928 0, /* tp_dict */
929 0, /* tp_descr_get */
930 0, /* tp_descr_set */
931 offsetof(lru_cache_object, dict), /* tp_dictoffset */
932 0, /* tp_init */
933 0, /* tp_alloc */
934 lru_cache_new, /* tp_new */
935 };
936
543 /* module level code ********************************************************/ 937 /* module level code ********************************************************/
544 938
545 PyDoc_STRVAR(module_doc, 939 PyDoc_STRVAR(module_doc,
546 "Tools that operate on functions."); 940 "Tools that operate on functions.");
547 941
548 static PyMethodDef module_methods[] = { 942 static PyMethodDef module_methods[] = {
549 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc }, 943 {"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc },
550 {"cmp_to_key", (PyCFunction)functools_cmp_to_key, 944 {"cmp_to_key", (PyCFunction)functools_cmp_to_key,
551 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc}, 945 METH_VARARGS | METH_KEYWORDS, functools_cmp_to_key_doc},
552 {NULL, NULL} /* sentinel */ 946 {NULL, NULL} /* sentinel */
553 }; 947 };
554 948
949 static void
950 module_free(void *m)
951 {
952 Py_DECREF(kwd_mark);
953 }
555 954
556 static struct PyModuleDef _functoolsmodule = { 955 static struct PyModuleDef _functoolsmodule = {
557 PyModuleDef_HEAD_INIT, 956 PyModuleDef_HEAD_INIT,
558 "_functools", 957 "_functools",
559 module_doc, 958 module_doc,
560 -1, 959 -1,
561 module_methods, 960 module_methods,
562 NULL, 961 NULL,
563 NULL, 962 NULL,
564 NULL, 963 NULL,
565 NULL 964 module_free,
566 }; 965 };
567 966
568 PyMODINIT_FUNC 967 PyMODINIT_FUNC
569 PyInit__functools(void) 968 PyInit__functools(void)
570 { 969 {
571 int i; 970 int i;
572 PyObject *m; 971 PyObject *m;
573 char *name; 972 char *name;
574 PyTypeObject *typelist[] = { 973 PyTypeObject *typelist[] = {
575 &partial_type, 974 &partial_type,
975 &lru_cache_type,
576 NULL 976 NULL
577 }; 977 };
578 978
579 m = PyModule_Create(&_functoolsmodule); 979 m = PyModule_Create(&_functoolsmodule);
580 if (m == NULL) 980 if (m == NULL)
581 return NULL; 981 return NULL;
982
983 if (!(kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL))) {
984 Py_DECREF(m);
985 return NULL;
986 }
582 987
583 for (i=0 ; typelist[i] != NULL ; i++) { 988 for (i=0 ; typelist[i] != NULL ; i++) {
584 if (PyType_Ready(typelist[i]) < 0) { 989 if (PyType_Ready(typelist[i]) < 0) {
585 Py_DECREF(m); 990 Py_DECREF(m);
586 return NULL; 991 return NULL;
587 } 992 }
588 name = strchr(typelist[i]->tp_name, '.'); 993 name = strchr(typelist[i]->tp_name, '.');
589 assert (name != NULL); 994 assert (name != NULL);
590 Py_INCREF(typelist[i]); 995 Py_INCREF(typelist[i]);
591 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]); 996 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
592 } 997 }
593 return m; 998 return m;
594 } 999 }
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+