Mercurial > cpython-lru_cache-weakref

annotate Include/setobject.h @ 87690:66c1c9f32567 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add use_weakref option to functools.lru_cache The use_weakref option makes lru_cache create weak references to the function arguments when creating the cache key, which prevents them from staying in the memory forever even after all other references to them are gone. This is a proof of concept for http://bugs.python.org/issue19859
author Radomir Dopieralski <devel@sheep.art.pl>
date Tue, 03 Dec 2013 16:02:48 +0100
parents 36f3f58fddce
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
1 /* Set object interface */
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
2
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
3 #ifndef Py_SETOBJECT_H
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
4 #define Py_SETOBJECT_H
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
5 #ifdef __cplusplus
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
6 extern "C" {
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
7 #endif
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
8
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
9
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
10 /*
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
11 There are three kinds of slots in the table:
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
12
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
13 1. Unused: key == NULL
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
14 2. Active: key != NULL and key != dummy
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
15 3. Dummy: key == dummy
35301
3086620db46b Model set.pop() after dict.popitem().
Raymond Hettinger <python@rcn.com>
parents: 35297
diff changeset
16
3086620db46b Model set.pop() after dict.popitem().
Raymond Hettinger <python@rcn.com>
parents: 35297
diff changeset
17 Note: .pop() abuses the hash field of an Unused or Dummy slot to
3086620db46b Model set.pop() after dict.popitem().
Raymond Hettinger <python@rcn.com>
parents: 35297
diff changeset
18 hold a search finger. The hash field of Unused or Dummy slots has
3086620db46b Model set.pop() after dict.popitem().
Raymond Hettinger <python@rcn.com>
parents: 35297
diff changeset
19 no meaning otherwise.
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
20 */
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
21 #ifndef Py_LIMITED_API
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
22 #define PySet_MINSIZE 8
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
23
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
24 typedef struct {
65494
e8969fb822fc make hashes always the size of pointers; introduce Py_hash_t #9778
Benjamin Peterson <benjamin@python.org>
parents: 64116
diff changeset
25 /* Cached hash code of the key. */
85049
20557286cc35 Put the most important and most frequency accessed struct member first.
Raymond Hettinger <python@rcn.com>
parents: 77577
diff changeset
26 PyObject *key;
65494
e8969fb822fc make hashes always the size of pointers; introduce Py_hash_t #9778
Benjamin Peterson <benjamin@python.org>
parents: 64116
diff changeset
27 Py_hash_t hash;
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
28 } setentry;
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
29
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
30
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
31 /*
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
32 This data structure is shared by set and frozenset objects.
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
33 */
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
34
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
35 typedef struct _setobject PySetObject;
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
36 struct _setobject {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
37 PyObject_HEAD
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
38
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
39 Py_ssize_t fill; /* # Active + # Dummy */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
40 Py_ssize_t used; /* # Active */
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
41
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
42 /* The table contains mask + 1 slots, and that's a power of 2.
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
43 * We store the mask instead of the size because the mask is more
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
44 * frequently needed.
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
45 */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
46 Py_ssize_t mask;
33856
60c60dc75c77 Wrote down the invariants of some common objects whose structure is
Armin Rigo <arigo@tunes.org>
parents: 32158
diff changeset
47
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
48 /* table points to smalltable for small tables, else to
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
49 * additional malloc'ed memory. table is never NULL! This rule
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
50 * saves repeated runtime null-tests.
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
51 */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
52 setentry *table;
65494
e8969fb822fc make hashes always the size of pointers; introduce Py_hash_t #9778
Benjamin Peterson <benjamin@python.org>
parents: 64116
diff changeset
53 setentry *(*lookup)(PySetObject *so, PyObject *key, Py_hash_t hash);
85262
a887596b841f Issue18771: Reduce the cost of hash collisions for set objects.
Raymond Hettinger <python@rcn.com>
parents: 85049
diff changeset
54 Py_hash_t hash; /* only used by frozenset objects */
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
55 setentry smalltable[PySet_MINSIZE];
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
56
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
57 PyObject *weakreflist; /* List of weak references */
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
58 };
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
59 #endif /* Py_LIMITED_API */
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
60
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
61 PyAPI_DATA(PyTypeObject) PySet_Type;
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
62 PyAPI_DATA(PyTypeObject) PyFrozenSet_Type;
44061
0cc552ab76bd Added all PyTypeObjects to the appropriate header files.
Christian Heimes <christian@cheimes.de>
parents: 42334
diff changeset
63 PyAPI_DATA(PyTypeObject) PySetIter_Type;
85366
2f1bac39565a Issue #18772: fix the gdb plugin after the set implementation changes
Antoine Pitrou <solipsis@pitrou.net>
parents: 85262
diff changeset
64 #ifndef Py_LIMITED_API
2f1bac39565a Issue #18772: fix the gdb plugin after the set implementation changes
Antoine Pitrou <solipsis@pitrou.net>
parents: 85262
diff changeset
65 PyAPI_DATA(PyObject *) _PySet_Dummy;
2f1bac39565a Issue #18772: fix the gdb plugin after the set implementation changes
Antoine Pitrou <solipsis@pitrou.net>
parents: 85262
diff changeset
66 #endif
2f1bac39565a Issue #18772: fix the gdb plugin after the set implementation changes
Antoine Pitrou <solipsis@pitrou.net>
parents: 85262
diff changeset
67
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
68
35321
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
69 /* Invariants for frozensets:
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
70 * data is immutable.
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
71 * hash is the hash of the frozenset or -1 if not computed yet.
35321
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
72 * Invariants for sets:
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
73 * hash is -1
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
74 */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
75
44351
86a2679dca46 #1629: Renamed Py_Size, Py_Type and Py_Refcnt to Py_SIZE, Py_TYPE and Py_REFCNT.
Christian Heimes <christian@cheimes.de>
parents: 44061
diff changeset
76 #define PyFrozenSet_CheckExact(ob) (Py_TYPE(ob) == &PyFrozenSet_Type)
35321
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
77 #define PyAnySet_CheckExact(ob) \
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
78 (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type)
30931
fa6e8d4f88c6 Various fixups (most suggested by Armin Rigo).
Raymond Hettinger <python@rcn.com>
parents: 30929
diff changeset
79 #define PyAnySet_Check(ob) \
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
80 (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type || \
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
81 PyType_IsSubtype(Py_TYPE(ob), &PySet_Type) || \
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
82 PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type))
45044
c3b38a85989f Merged revisions 60383-60407 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 44351
diff changeset
83 #define PySet_Check(ob) \
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
84 (Py_TYPE(ob) == &PySet_Type || \
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
85 PyType_IsSubtype(Py_TYPE(ob), &PySet_Type))
45145
3d7b84daa34a Merged revisions 60481,60485,60489-60492,60494-60496,60498-60499,60501-60503,60505-60506,60508-60509,60523-60524,60532,60543,60545,60547-60548,60552-60567 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 45066
diff changeset
86 #define PyFrozenSet_Check(ob) \
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
87 (Py_TYPE(ob) == &PyFrozenSet_Type || \
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
88 PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type))
30931
fa6e8d4f88c6 Various fixups (most suggested by Armin Rigo).
Raymond Hettinger <python@rcn.com>
parents: 30929
diff changeset
89
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
90 PyAPI_FUNC(PyObject *) PySet_New(PyObject *);
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
91 PyAPI_FUNC(PyObject *) PyFrozenSet_New(PyObject *);
36833
9e81788b0d4b Use Py_ssize_t for PySet_Size() like all the other Py*_Size() functions.
Neal Norwitz <nnorwitz@gmail.com>
parents: 35348
diff changeset
92 PyAPI_FUNC(Py_ssize_t) PySet_Size(PyObject *anyset);
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
93 #ifndef Py_LIMITED_API
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
94 #define PySet_GET_SIZE(so) (((PySetObject *)(so))->used)
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
95 #endif
37315
19059df45cfe SF patch #1458476 with modifications based on discussions in python-dev. This
Barry Warsaw <barry@python.org>
parents: 36833
diff changeset
96 PyAPI_FUNC(int) PySet_Clear(PyObject *set);
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
97 PyAPI_FUNC(int) PySet_Contains(PyObject *anyset, PyObject *key);
35348
2f1bf64b837e Numerous fix-ups to C API and docs. Added tests for C API.
Raymond Hettinger <python@rcn.com>
parents: 35346
diff changeset
98 PyAPI_FUNC(int) PySet_Discard(PyObject *set, PyObject *key);
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
99 PyAPI_FUNC(int) PySet_Add(PyObject *set, PyObject *key);
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
100 #ifndef Py_LIMITED_API
65494
e8969fb822fc make hashes always the size of pointers; introduce Py_hash_t #9778
Benjamin Peterson <benjamin@python.org>
parents: 64116
diff changeset
101 PyAPI_FUNC(int) _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash);
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
102 #endif
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
103 PyAPI_FUNC(PyObject *) PySet_Pop(PyObject *set);
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
104 #ifndef Py_LIMITED_API
37315
19059df45cfe SF patch #1458476 with modifications based on discussions in python-dev. This
Barry Warsaw <barry@python.org>
parents: 36833
diff changeset
105 PyAPI_FUNC(int) _PySet_Update(PyObject *set, PyObject *iterable);
73994
57f0af61da53 Issue #6695: Full garbage collection runs now clear the freelist of set objects.
Antoine Pitrou <solipsis@pitrou.net>
parents: 66664
diff changeset
106
57f0af61da53 Issue #6695: Full garbage collection runs now clear the freelist of set objects.
Antoine Pitrou <solipsis@pitrou.net>
parents: 66664
diff changeset
107 PyAPI_FUNC(int) PySet_ClearFreeList(void);
66664
62b61abd02b8 Merge branches/pep-0384.
Martin v. Löwis <martin@v.loewis.de>
parents: 65494
diff changeset
108 #endif
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
109
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
110 #ifdef __cplusplus
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
111 }
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
112 #endif
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
113 #endif /* !Py_SETOBJECT_H */