Mercurial > cpython-lru_cache-weakref

annotate Include/setobject.h @ 51749:1408feec0084 3.0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged revisions 69798 via svnmerge from svn+ssh://pythondev@svn.python.org/python/branches/py3k ................ r69798 | benjamin.peterson | 2009-02-19 22:02:38 -0600 (Thu, 19 Feb 2009) | 13 lines Merged revisions 69769,69776 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r69769 | georg.brandl | 2009-02-19 02:30:06 -0600 (Thu, 19 Feb 2009) | 1 line #5310, #3558: fix operator precedence table. ........ r69776 | georg.brandl | 2009-02-19 10:34:51 -0600 (Thu, 19 Feb 2009) | 2 lines #5317: update IronPython URL. ........ ................
author Benjamin Peterson <benjamin@python.org>
date Fri, 20 Feb 2009 04:05:32 +0000
parents 3d7b84daa34a
children cab14be0ada1
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 {
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
25 long hash; /* cached hash code for the entry key */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
26 PyObject *key;
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
27 } setentry;
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
28
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
29
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
30 /*
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
31 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
32 */
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
33
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
34 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
35 struct _setobject {
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
36 PyObject_HEAD
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
37
39442
654c380cf8b9 Merged revisions 46753-51188 via svnmerge from
Thomas Wouters <thomas@python.org>
parents: 37879
diff changeset
38 Py_ssize_t fill; /* # Active + # Dummy */
654c380cf8b9 Merged revisions 46753-51188 via svnmerge from
Thomas Wouters <thomas@python.org>
parents: 37879
diff changeset
39 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
40
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
41 /* The table contains mask + 1 slots, and that's a power of 2.
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
42 * We store the mask instead of the size because the mask is more
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
43 * frequently needed.
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
44 */
39442
654c380cf8b9 Merged revisions 46753-51188 via svnmerge from
Thomas Wouters <thomas@python.org>
parents: 37879
diff changeset
45 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
46
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
47 /* table points to smalltable for small tables, else to
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
48 * additional malloc'ed memory. table is never NULL! This rule
35297
26bf6c27e9ce * Improve code for the empty frozenset singleton:
Raymond Hettinger <python@rcn.com>
parents: 35292
diff changeset
49 * saves repeated runtime null-tests.
33856
60c60dc75c77 Wrote down the invariants of some common objects whose structure is
Armin Rigo <arigo@tunes.org>
parents: 32158
diff changeset
50 */
35292
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
51 setentry *table;
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
52 setentry *(*lookup)(PySetObject *so, PyObject *key, long hash);
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
53 setentry smalltable[PySet_MINSIZE];
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
54
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
55 long hash; /* only used by frozenset objects */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
56 PyObject *weakreflist; /* List of weak references */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
57 };
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
58
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
59 PyAPI_DATA(PyTypeObject) PySet_Type;
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
60 PyAPI_DATA(PyTypeObject) PyFrozenSet_Type;
44061
0cc552ab76bd Added all PyTypeObjects to the appropriate header files.
Christian Heimes <christian@cheimes.de>
parents: 42334
diff changeset
61 PyAPI_DATA(PyTypeObject) PySetIter_Type;
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
62
35321
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
63 /* 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
64 * data is immutable.
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
65 * 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
66 * Invariants for sets:
bdcb01a9b60c * Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
Raymond Hettinger <python@rcn.com>
parents: 35301
diff changeset
67 * 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
68 */
35a698302c63 Revised the set() and frozenset() implementaion to use its own internal
Raymond Hettinger <python@rcn.com>
parents: 33856
diff changeset
69
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
70 #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
71 #define PyAnySet_CheckExact(ob) \
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 (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
73 #define PyAnySet_Check(ob) \
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 (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type || \
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
75 PyType_IsSubtype(Py_TYPE(ob), &PySet_Type) || \
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 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
77 #define PySet_Check(ob) \
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
78 (Py_TYPE(ob) == &PySet_Type || \
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
79 PyType_IsSubtype(Py_TYPE(ob), &PySet_Type))
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
80 #define PyFrozenSet_Check(ob) \
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
81 (Py_TYPE(ob) == &PyFrozenSet_Type || \
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 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
83
35346
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
84 PyAPI_FUNC(PyObject *) PySet_New(PyObject *);
dd2357953fe3 Add a C API for sets and frozensets.
Raymond Hettinger <python@rcn.com>
parents: 35321
diff changeset
85 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
86 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
87 #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
88 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
89 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
90 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
91 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
92 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
93 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
94 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
95
30929
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
96 #ifdef __cplusplus
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
97 }
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
98 #endif
54ff68e973ee * Migrate set() and frozenset() from the sandbox.
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
99 #endif /* !Py_SETOBJECT_H */