| 1 | #ifndef Py_CPYTHON_SETOBJECT_H |
|---|
| 2 | # error "this header file must not be included directly" |
|---|
| 3 | #endif |
|---|
| 4 | |
|---|
| 5 | /* There are three kinds of entries in the table: |
|---|
| 6 | |
|---|
| 7 | 1. Unused: key == NULL and hash == 0 |
|---|
| 8 | 2. Dummy: key == dummy and hash == -1 |
|---|
| 9 | 3. Active: key != NULL and key != dummy and hash != -1 |
|---|
| 10 | |
|---|
| 11 | The hash field of Unused slots is always zero. |
|---|
| 12 | |
|---|
| 13 | The hash field of Dummy slots are set to -1 |
|---|
| 14 | meaning that dummy entries can be detected by |
|---|
| 15 | either entry->key==dummy or by entry->hash==-1. |
|---|
| 16 | */ |
|---|
| 17 | |
|---|
| 18 | #define PySet_MINSIZE 8 |
|---|
| 19 | |
|---|
| 20 | typedef struct { |
|---|
| 21 | PyObject *key; |
|---|
| 22 | Py_hash_t hash; /* Cached hash code of the key */ |
|---|
| 23 | } setentry; |
|---|
| 24 | |
|---|
| 25 | /* The SetObject data structure is shared by set and frozenset objects. |
|---|
| 26 | |
|---|
| 27 | Invariant for sets: |
|---|
| 28 | - hash is -1 |
|---|
| 29 | |
|---|
| 30 | Invariants for frozensets: |
|---|
| 31 | - data is immutable. |
|---|
| 32 | - hash is the hash of the frozenset or -1 if not computed yet. |
|---|
| 33 | |
|---|
| 34 | */ |
|---|
| 35 | |
|---|
| 36 | typedef struct { |
|---|
| 37 | PyObject_HEAD |
|---|
| 38 | |
|---|
| 39 | Py_ssize_t fill; /* Number active and dummy entries*/ |
|---|
| 40 | Py_ssize_t used; /* Number active entries */ |
|---|
| 41 | |
|---|
| 42 | /* The table contains mask + 1 slots, and that's a power of 2. |
|---|
| 43 | * We store the mask instead of the size because the mask is more |
|---|
| 44 | * frequently needed. |
|---|
| 45 | */ |
|---|
| 46 | Py_ssize_t mask; |
|---|
| 47 | |
|---|
| 48 | /* The table points to a fixed-size smalltable for small tables |
|---|
| 49 | * or to additional malloc'ed memory for bigger tables. |
|---|
| 50 | * The table pointer is never NULL which saves us from repeated |
|---|
| 51 | * runtime null-tests. |
|---|
| 52 | */ |
|---|
| 53 | setentry *table; |
|---|
| 54 | Py_hash_t hash; /* Only used by frozenset objects */ |
|---|
| 55 | Py_ssize_t finger; /* Search finger for pop() */ |
|---|
| 56 | |
|---|
| 57 | setentry smalltable[PySet_MINSIZE]; |
|---|
| 58 | PyObject *weakreflist; /* List of weak references */ |
|---|
| 59 | } PySetObject; |
|---|
| 60 | |
|---|
| 61 | #define _PySet_CAST(so) \ |
|---|
| 62 | (assert(PyAnySet_Check(so)), _Py_CAST(PySetObject*, so)) |
|---|
| 63 | |
|---|
| 64 | static inline Py_ssize_t PySet_GET_SIZE(PyObject *so) { |
|---|
| 65 | return _PySet_CAST(so)->used; |
|---|
| 66 | } |
|---|
| 67 | #define PySet_GET_SIZE(so) PySet_GET_SIZE(_PyObject_CAST(so)) |
|---|
| 68 | |
|---|
| 69 | PyAPI_DATA(PyObject *) _PySet_Dummy; |
|---|
| 70 | |
|---|
| 71 | PyAPI_FUNC(int) _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash); |
|---|
| 72 | PyAPI_FUNC(int) _PySet_Update(PyObject *set, PyObject *iterable); |
|---|
| 73 | |
|---|
