Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 1 | /* Set object interface */ |
| 2 | |
| 3 | #ifndef Py_SETOBJECT_H |
| 4 | #define Py_SETOBJECT_H |
| 5 | #ifdef __cplusplus |
| 6 | extern "C" { |
| 7 | #endif |
| 8 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 9 | #ifndef Py_LIMITED_API |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 10 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 11 | /* There are three kinds of entries in the table: |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 12 | |
Raymond Hettinger | 9344bd8 | 2015-08-01 15:21:41 -0700 | [diff] [blame] | 13 | 1. Unused: key == NULL and hash == 0 |
| 14 | 2. Dummy: key == dummy and hash == -1 |
| 15 | 3. Active: key != NULL and key != dummy and hash != -1 |
Raymond Hettinger | 67962ab | 2005-08-02 03:45:16 +0000 | [diff] [blame] | 16 | |
Raymond Hettinger | 9344bd8 | 2015-08-01 15:21:41 -0700 | [diff] [blame] | 17 | The hash field of Unused slots is always zero. |
| 18 | |
| 19 | The hash field of Dummy slots are set to -1 |
Raymond Hettinger | a5ebbf6 | 2015-01-26 21:54:35 -0800 | [diff] [blame] | 20 | meaning that dummy entries can be detected by |
| 21 | either entry->key==dummy or by entry->hash==-1. |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 22 | */ |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 23 | |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 24 | #define PySet_MINSIZE 8 |
| 25 | |
| 26 | typedef struct { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 27 | PyObject *key; |
Raymond Hettinger | 3f063a5 | 2014-12-28 17:15:12 -0800 | [diff] [blame] | 28 | Py_hash_t hash; /* Cached hash code of the key */ |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 29 | } setentry; |
| 30 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 31 | /* The SetObject data structure is shared by set and frozenset objects. |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 32 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 33 | Invariant for sets: |
| 34 | - hash is -1 |
| 35 | |
| 36 | Invariants for frozensets: |
| 37 | - data is immutable. |
| 38 | - hash is the hash of the frozenset or -1 if not computed yet. |
| 39 | |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 40 | */ |
| 41 | |
Raymond Hettinger | 93035c4 | 2015-01-25 16:12:49 -0800 | [diff] [blame] | 42 | typedef struct { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 43 | PyObject_HEAD |
Armin Rigo | 89a3946 | 2004-10-28 16:32:00 +0000 | [diff] [blame] | 44 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 45 | Py_ssize_t fill; /* Number active and dummy entries*/ |
| 46 | Py_ssize_t used; /* Number active entries */ |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 47 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 48 | /* The table contains mask + 1 slots, and that's a power of 2. |
| 49 | * We store the mask instead of the size because the mask is more |
| 50 | * frequently needed. |
| 51 | */ |
| 52 | Py_ssize_t mask; |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 53 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 54 | /* The table points to a fixed-size smalltable for small tables |
| 55 | * or to additional malloc'ed memory for bigger tables. |
| 56 | * The table pointer is never NULL which saves us from repeated |
| 57 | * runtime null-tests. |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 58 | */ |
| 59 | setentry *table; |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 60 | Py_hash_t hash; /* Only used by frozenset objects */ |
Raymond Hettinger | 1202a47 | 2015-01-18 13:12:42 -0800 | [diff] [blame] | 61 | Py_ssize_t finger; /* Search finger for pop() */ |
Raymond Hettinger | c564412 | 2015-01-29 22:00:32 -0800 | [diff] [blame] | 62 | |
| 63 | setentry smalltable[PySet_MINSIZE]; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 64 | PyObject *weakreflist; /* List of weak references */ |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 65 | } PySetObject; |
| 66 | |
Serhiy Storchaka | 1a5856b | 2017-04-22 02:48:11 +0300 | [diff] [blame] | 67 | #define PySet_GET_SIZE(so) (assert(PyAnySet_Check(so)),(((PySetObject *)(so))->used)) |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 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 | PyAPI_FUNC(int) PySet_ClearFreeList(void); |
| 74 | |
| 75 | #endif /* Section excluded by Py_LIMITED_API */ |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 76 | |
| 77 | PyAPI_DATA(PyTypeObject) PySet_Type; |
| 78 | PyAPI_DATA(PyTypeObject) PyFrozenSet_Type; |
Christian Heimes | a22e8bd | 2007-11-29 22:35:39 +0000 | [diff] [blame] | 79 | PyAPI_DATA(PyTypeObject) PySetIter_Type; |
Antoine Pitrou | 9d95254 | 2013-08-24 21:07:07 +0200 | [diff] [blame] | 80 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 81 | PyAPI_FUNC(PyObject *) PySet_New(PyObject *); |
| 82 | PyAPI_FUNC(PyObject *) PyFrozenSet_New(PyObject *); |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 83 | |
Raymond Hettinger | 404a45d | 2014-12-26 17:28:16 -0800 | [diff] [blame] | 84 | PyAPI_FUNC(int) PySet_Add(PyObject *set, PyObject *key); |
| 85 | PyAPI_FUNC(int) PySet_Clear(PyObject *set); |
| 86 | PyAPI_FUNC(int) PySet_Contains(PyObject *anyset, PyObject *key); |
| 87 | PyAPI_FUNC(int) PySet_Discard(PyObject *set, PyObject *key); |
| 88 | PyAPI_FUNC(PyObject *) PySet_Pop(PyObject *set); |
| 89 | PyAPI_FUNC(Py_ssize_t) PySet_Size(PyObject *anyset); |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 90 | |
Christian Heimes | 90aa764 | 2007-12-19 02:45:37 +0000 | [diff] [blame] | 91 | #define PyFrozenSet_CheckExact(ob) (Py_TYPE(ob) == &PyFrozenSet_Type) |
Raymond Hettinger | bc841a1 | 2005-08-07 13:02:53 +0000 | [diff] [blame] | 92 | #define PyAnySet_CheckExact(ob) \ |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 93 | (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type) |
Raymond Hettinger | 50a4bb3 | 2003-11-17 16:42:33 +0000 | [diff] [blame] | 94 | #define PyAnySet_Check(ob) \ |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 95 | (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type || \ |
| 96 | PyType_IsSubtype(Py_TYPE(ob), &PySet_Type) || \ |
| 97 | PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type)) |
Christian Heimes | fd66e51 | 2008-01-29 12:18:50 +0000 | [diff] [blame] | 98 | #define PySet_Check(ob) \ |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 99 | (Py_TYPE(ob) == &PySet_Type || \ |
| 100 | PyType_IsSubtype(Py_TYPE(ob), &PySet_Type)) |
Christian Heimes | 15ebc88 | 2008-02-04 18:48:49 +0000 | [diff] [blame] | 101 | #define PyFrozenSet_Check(ob) \ |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 102 | (Py_TYPE(ob) == &PyFrozenSet_Type || \ |
| 103 | PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type)) |
Raymond Hettinger | 50a4bb3 | 2003-11-17 16:42:33 +0000 | [diff] [blame] | 104 | |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 105 | #ifdef __cplusplus |
| 106 | } |
| 107 | #endif |
| 108 | #endif /* !Py_SETOBJECT_H */ |