| 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 |
#ifdef Py_GIL_DISABLED |
| 66 |
return _Py_atomic_load_ssize_relaxed(&(_PySet_CAST(so)->used)); |
| 67 |
#else |
| 68 |
return _PySet_CAST(so)->used; |
| 69 |
#endif |
| 70 |
} |
| 71 |
#define PySet_GET_SIZE(so) PySet_GET_SIZE(_PyObject_CAST(so)) |