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 | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 9 | |
| 10 | /* |
| 11 | There are three kinds of slots in the table: |
| 12 | |
| 13 | 1. Unused: key == NULL |
| 14 | 2. Active: key != NULL and key != dummy |
| 15 | 3. Dummy: key == dummy |
Raymond Hettinger | 67962ab | 2005-08-02 03:45:16 +0000 | [diff] [blame] | 16 | |
| 17 | Note: .pop() abuses the hash field of an Unused or Dummy slot to |
| 18 | hold a search finger. The hash field of Unused or Dummy slots has |
| 19 | no meaning otherwise. |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 20 | */ |
| 21 | |
| 22 | #define PySet_MINSIZE 8 |
| 23 | |
| 24 | typedef struct { |
Antoine Pitrou | f72006f | 2010-08-17 19:39:39 +0000 | [diff] [blame] | 25 | /* Cached hash code of the key. Note that hash codes are C longs. |
| 26 | * We have to use Py_ssize_t instead because set_pop() abuses |
| 27 | * the hash field to hold a search finger. |
| 28 | */ |
| 29 | Py_ssize_t hash; |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 30 | PyObject *key; |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 31 | } setentry; |
| 32 | |
| 33 | |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 34 | /* |
| 35 | This data structure is shared by set and frozenset objects. |
| 36 | */ |
| 37 | |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 38 | typedef struct _setobject PySetObject; |
| 39 | struct _setobject { |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 40 | PyObject_HEAD |
Armin Rigo | 89a3946 | 2004-10-28 16:32:00 +0000 | [diff] [blame] | 41 | |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 42 | Py_ssize_t fill; /* # Active + # Dummy */ |
| 43 | Py_ssize_t used; /* # Active */ |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 44 | |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 45 | /* The table contains mask + 1 slots, and that's a power of 2. |
| 46 | * We store the mask instead of the size because the mask is more |
| 47 | * frequently needed. |
| 48 | */ |
| 49 | Py_ssize_t mask; |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 50 | |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 51 | /* table points to smalltable for small tables, else to |
| 52 | * additional malloc'ed memory. table is never NULL! This rule |
| 53 | * saves repeated runtime null-tests. |
| 54 | */ |
| 55 | setentry *table; |
| 56 | setentry *(*lookup)(PySetObject *so, PyObject *key, long hash); |
| 57 | setentry smalltable[PySet_MINSIZE]; |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 58 | |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 59 | long hash; /* only used by frozenset objects */ |
| 60 | PyObject *weakreflist; /* List of weak references */ |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 61 | }; |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 62 | |
| 63 | PyAPI_DATA(PyTypeObject) PySet_Type; |
| 64 | PyAPI_DATA(PyTypeObject) PyFrozenSet_Type; |
Christian Heimes | a22e8bd | 2007-11-29 22:35:39 +0000 | [diff] [blame] | 65 | PyAPI_DATA(PyTypeObject) PySetIter_Type; |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 66 | |
Raymond Hettinger | bc841a1 | 2005-08-07 13:02:53 +0000 | [diff] [blame] | 67 | /* Invariants for frozensets: |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 68 | * data is immutable. |
| 69 | * hash is the hash of the frozenset or -1 if not computed yet. |
Raymond Hettinger | bc841a1 | 2005-08-07 13:02:53 +0000 | [diff] [blame] | 70 | * Invariants for sets: |
| 71 | * hash is -1 |
Raymond Hettinger | 9f1a679 | 2005-07-31 01:16:36 +0000 | [diff] [blame] | 72 | */ |
| 73 | |
Christian Heimes | 90aa764 | 2007-12-19 02:45:37 +0000 | [diff] [blame] | 74 | #define PyFrozenSet_CheckExact(ob) (Py_TYPE(ob) == &PyFrozenSet_Type) |
Raymond Hettinger | bc841a1 | 2005-08-07 13:02:53 +0000 | [diff] [blame] | 75 | #define PyAnySet_CheckExact(ob) \ |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 76 | (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type) |
Raymond Hettinger | 50a4bb3 | 2003-11-17 16:42:33 +0000 | [diff] [blame] | 77 | #define PyAnySet_Check(ob) \ |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 78 | (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type || \ |
| 79 | PyType_IsSubtype(Py_TYPE(ob), &PySet_Type) || \ |
| 80 | PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type)) |
Christian Heimes | fd66e51 | 2008-01-29 12:18:50 +0000 | [diff] [blame] | 81 | #define PySet_Check(ob) \ |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 82 | (Py_TYPE(ob) == &PySet_Type || \ |
| 83 | PyType_IsSubtype(Py_TYPE(ob), &PySet_Type)) |
Christian Heimes | 15ebc88 | 2008-02-04 18:48:49 +0000 | [diff] [blame] | 84 | #define PyFrozenSet_Check(ob) \ |
Antoine Pitrou | 7f14f0d | 2010-05-09 16:14:21 +0000 | [diff] [blame] | 85 | (Py_TYPE(ob) == &PyFrozenSet_Type || \ |
| 86 | PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type)) |
Raymond Hettinger | 50a4bb3 | 2003-11-17 16:42:33 +0000 | [diff] [blame] | 87 | |
Raymond Hettinger | beb3101 | 2005-08-16 03:47:52 +0000 | [diff] [blame] | 88 | PyAPI_FUNC(PyObject *) PySet_New(PyObject *); |
| 89 | PyAPI_FUNC(PyObject *) PyFrozenSet_New(PyObject *); |
Neal Norwitz | 8c49c82 | 2006-03-04 18:41:19 +0000 | [diff] [blame] | 90 | PyAPI_FUNC(Py_ssize_t) PySet_Size(PyObject *anyset); |
Raymond Hettinger | beb3101 | 2005-08-16 03:47:52 +0000 | [diff] [blame] | 91 | #define PySet_GET_SIZE(so) (((PySetObject *)(so))->used) |
Thomas Wouters | 49fd7fa | 2006-04-21 10:40:58 +0000 | [diff] [blame] | 92 | PyAPI_FUNC(int) PySet_Clear(PyObject *set); |
Raymond Hettinger | beb3101 | 2005-08-16 03:47:52 +0000 | [diff] [blame] | 93 | PyAPI_FUNC(int) PySet_Contains(PyObject *anyset, PyObject *key); |
Raymond Hettinger | c47e01d | 2005-08-16 10:44:15 +0000 | [diff] [blame] | 94 | PyAPI_FUNC(int) PySet_Discard(PyObject *set, PyObject *key); |
Raymond Hettinger | beb3101 | 2005-08-16 03:47:52 +0000 | [diff] [blame] | 95 | PyAPI_FUNC(int) PySet_Add(PyObject *set, PyObject *key); |
Guido van Rossum | d8faa36 | 2007-04-27 19:54:29 +0000 | [diff] [blame] | 96 | PyAPI_FUNC(int) _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, long *hash); |
Raymond Hettinger | beb3101 | 2005-08-16 03:47:52 +0000 | [diff] [blame] | 97 | PyAPI_FUNC(PyObject *) PySet_Pop(PyObject *set); |
Thomas Wouters | 49fd7fa | 2006-04-21 10:40:58 +0000 | [diff] [blame] | 98 | PyAPI_FUNC(int) _PySet_Update(PyObject *set, PyObject *iterable); |
Raymond Hettinger | beb3101 | 2005-08-16 03:47:52 +0000 | [diff] [blame] | 99 | |
Raymond Hettinger | a690a99 | 2003-11-16 16:17:49 +0000 | [diff] [blame] | 100 | #ifdef __cplusplus |
| 101 | } |
| 102 | #endif |
| 103 | #endif /* !Py_SETOBJECT_H */ |