Mercurial > cpython-lru_cache-weakref

annotate Include/setobject.h @ 64121:2a4ceebdfcfb 3.1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged revisions 84146-84147,84150 via svnmerge from svn+ssh://pythondev@svn.python.org/python/branches/py3k ........ r84146 | antoine.pitrou | 2010-08-17 19:55:07 +0200 (mar., 17 août 2010) | 4 lines Issue #9612: The set object is now 64-bit clean under Windows. ........ r84147 | antoine.pitrou | 2010-08-17 20:30:06 +0200 (mar., 17 août 2010) | 3 lines Fix <deque iterator>.__length_hint__() under 64-bit Windows. ........ r84150 | antoine.pitrou | 2010-08-17 21:33:30 +0200 (mar., 17 août 2010) | 3 lines Clean some 64-bit issues. Also, always spell "ssize_t" "Py_ssize_t". ........
author Antoine Pitrou <solipsis@pitrou.net>
date Tue, 17 Aug 2010 19:39:39 +0000
parents f197407bdba2
children e8969fb822fc
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 */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
21
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 {
64121
2a4ceebdfcfb Merged revisions 84146-84147,84150 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 61467
diff changeset
25 /* Cached hash code of the key. Note that hash codes are C longs.
2a4ceebdfcfb Merged revisions 84146-84147,84150 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 61467
diff changeset
26 * We have to use Py_ssize_t instead because set_pop() abuses
2a4ceebdfcfb Merged revisions 84146-84147,84150 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 61467
diff changeset
27 * the hash field to hold a search finger.
2a4ceebdfcfb Merged revisions 84146-84147,84150 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 61467
diff changeset
28 */
2a4ceebdfcfb Merged revisions 84146-84147,84150 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 61467
diff changeset
29 Py_ssize_t hash;
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
30 PyObject *key;
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
31 } setentry;
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
32
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
33
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
34 /*
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
35 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
36 */
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
37
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
38 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
39 struct _setobject {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
40 PyObject_HEAD
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
41
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
42 Py_ssize_t fill; /* # Active + # Dummy */
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
43 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
44
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
45 /* The table contains mask + 1 slots, and that's a power of 2.
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
46 * We store the mask instead of the size because the mask is more
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
47 * frequently needed.
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
48 */
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
49 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
50
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
51 /* table points to smalltable for small tables, else to
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
52 * additional malloc'ed memory. table is never NULL! This rule
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
53 * saves repeated runtime null-tests.
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
54 */
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
55 setentry *table;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
56 setentry *(*lookup)(PySetObject *so, PyObject *key, long hash);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
57 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
58
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
59 long hash; /* only used by frozenset objects */
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
60 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
61 };
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
62
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
63 PyAPI_DATA(PyTypeObject) PySet_Type;
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
64 PyAPI_DATA(PyTypeObject) PyFrozenSet_Type;
44061
0cc552ab76bd Added all PyTypeObjects to the appropriate header files.
Christian Heimes <christian@cheimes.de>
parents: 42334
diff changeset
65 PyAPI_DATA(PyTypeObject) PySetIter_Type;
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
66
35321
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
67 /* 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
68 * data is immutable.
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
69 * 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
70 * Invariants for sets:
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
71 * 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
72 */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
73
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
74 #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
75 #define PyAnySet_CheckExact(ob) \
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
76 (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
77 #define PyAnySet_Check(ob) \
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
78 (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type || \
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
79 PyType_IsSubtype(Py_TYPE(ob), &PySet_Type) || \
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
80 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
81 #define PySet_Check(ob) \
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
82 (Py_TYPE(ob) == &PySet_Type || \
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
83 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
84 #define PyFrozenSet_Check(ob) \
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
85 (Py_TYPE(ob) == &PyFrozenSet_Type || \
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 45145
diff changeset
86 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
87
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
88 PyAPI_FUNC(PyObject *) PySet_New(PyObject *);
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
89 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
90 PyAPI_FUNC(Py_ssize_t) PySet_Size(PyObject *anyset);
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
91 #define PySet_GET_SIZE(so) (((PySetObject *)(so))->used)
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);
41554
06145fbc7ab9 Merged revisions 53952-54987 via svnmerge from
Guido van Rossum <guido@python.org>
parents: 39442
diff changeset
96 PyAPI_FUNC(int) _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash);
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
97 PyAPI_FUNC(PyObject *) PySet_Pop(PyObject *set);
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
98 PyAPI_FUNC(int) _PySet_Update(PyObject *set, PyObject *iterable);
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
99
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
100 #ifdef __cplusplus
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
101 }
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
102 #endif
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
103 #endif /* !Py_SETOBJECT_H */