Mercurial > cpython-lru_cache-weakref

annotate Include/setobject.h @ 70817:dd775b1561ba

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix markup.
author Georg Brandl <georg@python.org>
date Tue, 14 Jun 2011 21:09:55 +0200
parents 62b61abd02b8
children 57f0af61da53
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. */
e8969fb822fc make hashes always the size of pointers; introduce Py_hash_t #9778
Benjamin Peterson <benjamin@python.org>
parents: 64116
diff changeset
26 Py_hash_t hash;
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
27 PyObject *key;
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);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
54 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
55
65494
e8969fb822fc make hashes always the size of pointers; introduce Py_hash_t #9778
Benjamin Peterson <benjamin@python.org>
parents: 64116
diff changeset
56 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
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;
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
64
35321
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
65 /* 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
66 * data is immutable.
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
67 * 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
68 * Invariants for sets:
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
69 * 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
70 */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
71
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
72 #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
73 #define PyAnySet_CheckExact(ob) \
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
74 (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
75 #define PyAnySet_Check(ob) \
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
76 (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
77 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
78 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
79 #define PySet_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 || \
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))
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
82 #define PyFrozenSet_Check(ob) \
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
83 (Py_TYPE(ob) == &PyFrozenSet_Type || \
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
84 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
85
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
86 PyAPI_FUNC(PyObject *) PySet_New(PyObject *);
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
87 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
88 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
89 #ifndef Py_LIMITED_API
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
90 #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
91 #endif
37879
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 36833
diff changeset
92 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
93 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
94 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
95 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
96 #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
97 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
98 #endif
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
99 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
100 #ifndef Py_LIMITED_API
37879
f731859e9b3b Merge p3yk branch with the trunk up to revision 45595. This breaks a fair
Thomas Wouters <thomas@python.org>
parents: 36833
diff changeset
101 PyAPI_FUNC(int) _PySet_Update(PyObject *set, PyObject *iterable);
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
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
104 #ifdef __cplusplus
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
105 }
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
106 #endif
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
107 #endif /* !Py_SETOBJECT_H */