OLD | NEW |
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 Loading... |
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 } |
OLD | NEW |