blob: 623411101d5ba8506a9f07cf8a91042ab4bd3339 [file] [log] [blame]
Raymond Hettingera690a992003-11-16 16:17:49 +00001/* Set object interface */
2
3#ifndef Py_SETOBJECT_H
4#define Py_SETOBJECT_H
5#ifdef __cplusplus
6extern "C" {
7#endif
8
Raymond Hettinger9f1a6792005-07-31 01:16:36 +00009
10/*
11There are three kinds of slots in the table:
12
131. Unused: key == NULL
142. Active: key != NULL and key != dummy
153. Dummy: key == dummy
Raymond Hettinger67962ab2005-08-02 03:45:16 +000016
17Note: .pop() abuses the hash field of an Unused or Dummy slot to
18hold a search finger. The hash field of Unused or Dummy slots has
19no meaning otherwise.
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000020*/
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000021#ifndef Py_LIMITED_API
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000022#define PySet_MINSIZE 8
23
24typedef struct {
Benjamin Peterson8f67d082010-10-17 20:54:53 +000025 /* Cached hash code of the key. */
26 Py_hash_t hash;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000027 PyObject *key;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000028} setentry;
29
30
Raymond Hettingera690a992003-11-16 16:17:49 +000031/*
32This data structure is shared by set and frozenset objects.
33*/
34
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000035typedef struct _setobject PySetObject;
36struct _setobject {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000037 PyObject_HEAD
Armin Rigo89a39462004-10-28 16:32:00 +000038
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000039 Py_ssize_t fill; /* # Active + # Dummy */
40 Py_ssize_t used; /* # Active */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000041
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000042 /* 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;
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000047
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000048 /* table points to smalltable for small tables, else to
49 * additional malloc'ed memory. table is never NULL! This rule
50 * saves repeated runtime null-tests.
51 */
52 setentry *table;
Benjamin Peterson8f67d082010-10-17 20:54:53 +000053 setentry *(*lookup)(PySetObject *so, PyObject *key, Py_hash_t hash);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000054 setentry smalltable[PySet_MINSIZE];
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000055
Benjamin Peterson8f67d082010-10-17 20:54:53 +000056 Py_hash_t hash; /* only used by frozenset objects */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000057 PyObject *weakreflist; /* List of weak references */
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000058};
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000059#endif /* Py_LIMITED_API */
Raymond Hettingera690a992003-11-16 16:17:49 +000060
61PyAPI_DATA(PyTypeObject) PySet_Type;
62PyAPI_DATA(PyTypeObject) PyFrozenSet_Type;
Christian Heimesa22e8bd2007-11-29 22:35:39 +000063PyAPI_DATA(PyTypeObject) PySetIter_Type;
Raymond Hettingera690a992003-11-16 16:17:49 +000064
Raymond Hettingerbc841a12005-08-07 13:02:53 +000065/* Invariants for frozensets:
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000066 * data is immutable.
67 * hash is the hash of the frozenset or -1 if not computed yet.
Raymond Hettingerbc841a12005-08-07 13:02:53 +000068 * Invariants for sets:
69 * hash is -1
Raymond Hettinger9f1a6792005-07-31 01:16:36 +000070 */
71
Christian Heimes90aa7642007-12-19 02:45:37 +000072#define PyFrozenSet_CheckExact(ob) (Py_TYPE(ob) == &PyFrozenSet_Type)
Raymond Hettingerbc841a12005-08-07 13:02:53 +000073#define PyAnySet_CheckExact(ob) \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000074 (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type)
Raymond Hettinger50a4bb32003-11-17 16:42:33 +000075#define PyAnySet_Check(ob) \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000076 (Py_TYPE(ob) == &PySet_Type || Py_TYPE(ob) == &PyFrozenSet_Type || \
77 PyType_IsSubtype(Py_TYPE(ob), &PySet_Type) || \
78 PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type))
Christian Heimesfd66e512008-01-29 12:18:50 +000079#define PySet_Check(ob) \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000080 (Py_TYPE(ob) == &PySet_Type || \
81 PyType_IsSubtype(Py_TYPE(ob), &PySet_Type))
Christian Heimes15ebc882008-02-04 18:48:49 +000082#define PyFrozenSet_Check(ob) \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000083 (Py_TYPE(ob) == &PyFrozenSet_Type || \
84 PyType_IsSubtype(Py_TYPE(ob), &PyFrozenSet_Type))
Raymond Hettinger50a4bb32003-11-17 16:42:33 +000085
Raymond Hettingerbeb31012005-08-16 03:47:52 +000086PyAPI_FUNC(PyObject *) PySet_New(PyObject *);
87PyAPI_FUNC(PyObject *) PyFrozenSet_New(PyObject *);
Neal Norwitz8c49c822006-03-04 18:41:19 +000088PyAPI_FUNC(Py_ssize_t) PySet_Size(PyObject *anyset);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000089#ifndef Py_LIMITED_API
Raymond Hettingerbeb31012005-08-16 03:47:52 +000090#define PySet_GET_SIZE(so) (((PySetObject *)(so))->used)
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000091#endif
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000092PyAPI_FUNC(int) PySet_Clear(PyObject *set);
Raymond Hettingerbeb31012005-08-16 03:47:52 +000093PyAPI_FUNC(int) PySet_Contains(PyObject *anyset, PyObject *key);
Raymond Hettingerc47e01d2005-08-16 10:44:15 +000094PyAPI_FUNC(int) PySet_Discard(PyObject *set, PyObject *key);
Raymond Hettingerbeb31012005-08-16 03:47:52 +000095PyAPI_FUNC(int) PySet_Add(PyObject *set, PyObject *key);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000096#ifndef Py_LIMITED_API
Benjamin Peterson8f67d082010-10-17 20:54:53 +000097PyAPI_FUNC(int) _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000098#endif
Raymond Hettingerbeb31012005-08-16 03:47:52 +000099PyAPI_FUNC(PyObject *) PySet_Pop(PyObject *set);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +0000100#ifndef Py_LIMITED_API
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000101PyAPI_FUNC(int) _PySet_Update(PyObject *set, PyObject *iterable);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +0000102#endif
Raymond Hettingerbeb31012005-08-16 03:47:52 +0000103
Raymond Hettingera690a992003-11-16 16:17:49 +0000104#ifdef __cplusplus
105}
106#endif
107#endif /* !Py_SETOBJECT_H */