blob: 08a9449925f9cd188827045f8efb963356b650a2 [file] [log] [blame]
Guido van Rossuma3309961993-07-28 09:05:47 +00001#ifndef Py_DICTOBJECT_H
2#define Py_DICTOBJECT_H
3#ifdef __cplusplus
4extern "C" {
5#endif
6
Guido van Rossumf70e43a1991-02-19 12:39:46 +00007
Guido van Rossum2ec90311997-05-13 21:23:32 +00008/* Dictionary object type -- mapping from hashable object to object */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00009
Raymond Hettinger930427b2003-05-03 06:51:59 +000010/* The distribution includes a separate file, Objects/dictnotes.txt,
Thomas Wouters4d70c3d2006-06-08 14:42:34 +000011 describing explorations into dictionary design and optimization.
Raymond Hettinger930427b2003-05-03 06:51:59 +000012 It covers typical dictionary use patterns, the parameters for
13 tuning dictionaries, and several ideas for possible optimizations.
14*/
15
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000016#ifndef Py_LIMITED_API
Tim Peters6d6c1a32001-08-02 04:15:00 +000017
Benjamin Peterson7d95e402012-04-23 11:24:50 -040018typedef struct _dictkeysobject PyDictKeysObject;
19
20/* The ma_values pointer is NULL for a combined table
21 * or points to an array of PyObject* for a split table
22 */
Tim Peters6d6c1a32001-08-02 04:15:00 +000023typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000024 PyObject_HEAD
Victor Stinnera4348cc2016-09-08 12:01:25 -070025
26 /* Number of items in the dictionary */
Benjamin Peterson7d95e402012-04-23 11:24:50 -040027 Py_ssize_t ma_used;
Victor Stinnera4348cc2016-09-08 12:01:25 -070028
Victor Stinner3b6a6b42016-09-08 12:51:24 -070029 /* Dictionary version: globally unique, value change each time
30 the dictionary is modified */
31 uint64_t ma_version_tag;
32
Benjamin Peterson7d95e402012-04-23 11:24:50 -040033 PyDictKeysObject *ma_keys;
Victor Stinnera4348cc2016-09-08 12:01:25 -070034
35 /* If ma_values is NULL, the table is "combined": keys and values
Victor Stinner611b0fa2016-09-14 15:02:01 +020036 are stored in ma_keys.
Victor Stinnera4348cc2016-09-08 12:01:25 -070037
38 If ma_values is not NULL, the table is splitted:
39 keys are stored in ma_keys and values are stored in ma_values */
Benjamin Peterson7d95e402012-04-23 11:24:50 -040040 PyObject **ma_values;
41} PyDictObject;
Tim Peters6d6c1a32001-08-02 04:15:00 +000042
Eric Snow96c6af92015-05-29 22:21:39 -060043typedef struct {
44 PyObject_HEAD
45 PyDictObject *dv_dict;
46} _PyDictViewObject;
47
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000048#endif /* Py_LIMITED_API */
Tim Peters6d6c1a32001-08-02 04:15:00 +000049
Mark Hammond91a681d2002-08-12 07:21:58 +000050PyAPI_DATA(PyTypeObject) PyDict_Type;
Christian Heimesa22e8bd2007-11-29 22:35:39 +000051PyAPI_DATA(PyTypeObject) PyDictIterKey_Type;
52PyAPI_DATA(PyTypeObject) PyDictIterValue_Type;
53PyAPI_DATA(PyTypeObject) PyDictIterItem_Type;
54PyAPI_DATA(PyTypeObject) PyDictKeys_Type;
55PyAPI_DATA(PyTypeObject) PyDictItems_Type;
56PyAPI_DATA(PyTypeObject) PyDictValues_Type;
Guido van Rossum2ec90311997-05-13 21:23:32 +000057
Thomas Wouters27d517b2007-02-25 20:39:11 +000058#define PyDict_Check(op) \
Christian Heimes90aa7642007-12-19 02:45:37 +000059 PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS)
60#define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type)
Eric Snow8c7ed012015-05-30 09:29:53 -060061#define PyDictKeys_Check(op) PyObject_TypeCheck(op, &PyDictKeys_Type)
62#define PyDictItems_Check(op) PyObject_TypeCheck(op, &PyDictItems_Type)
63#define PyDictValues_Check(op) PyObject_TypeCheck(op, &PyDictValues_Type)
Christian Heimesa22e8bd2007-11-29 22:35:39 +000064/* This excludes Values, since they are not sets. */
65# define PyDictViewSet_Check(op) \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000066 (PyDictKeys_Check(op) || PyDictItems_Check(op))
Christian Heimesa22e8bd2007-11-29 22:35:39 +000067
Guido van Rossum2ec90311997-05-13 21:23:32 +000068
Mark Hammond91a681d2002-08-12 07:21:58 +000069PyAPI_FUNC(PyObject *) PyDict_New(void);
70PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key);
Benjamin Peterson39992d32014-05-03 19:39:15 -040071#ifndef Py_LIMITED_API
Raymond Hettinger4b74fba2014-05-03 16:32:11 -070072PyAPI_FUNC(PyObject *) _PyDict_GetItem_KnownHash(PyObject *mp, PyObject *key,
73 Py_hash_t hash);
Benjamin Peterson39992d32014-05-03 19:39:15 -040074#endif
Alexandre Vassalotticb314332008-06-01 03:53:03 +000075PyAPI_FUNC(PyObject *) PyDict_GetItemWithError(PyObject *mp, PyObject *key);
Serhiy Storchaka9fab79b2016-09-11 11:03:14 +030076#ifndef Py_LIMITED_API
Brett Cannonfd074152012-04-14 14:10:13 -040077PyAPI_FUNC(PyObject *) _PyDict_GetItemIdWithError(PyObject *dp,
78 struct _Py_Identifier *key);
Benjamin Peterson00e98862013-03-07 22:16:29 -050079PyAPI_FUNC(PyObject *) PyDict_SetDefault(
80 PyObject *mp, PyObject *key, PyObject *defaultobj);
Martin v. Löwis1c0689c2014-01-03 21:36:49 +010081#endif
Mark Hammond91a681d2002-08-12 07:21:58 +000082PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item);
Benjamin Peterson39992d32014-05-03 19:39:15 -040083#ifndef Py_LIMITED_API
Raymond Hettinger4b74fba2014-05-03 16:32:11 -070084PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,
85 PyObject *item, Py_hash_t hash);
Benjamin Peterson39992d32014-05-03 19:39:15 -040086#endif
Mark Hammond91a681d2002-08-12 07:21:58 +000087PyAPI_FUNC(int) PyDict_DelItem(PyObject *mp, PyObject *key);
Serhiy Storchakab9d98d52015-10-02 12:47:11 +030088#ifndef Py_LIMITED_API
89PyAPI_FUNC(int) _PyDict_DelItem_KnownHash(PyObject *mp, PyObject *key,
90 Py_hash_t hash);
Antoine Pitroue10ca3a2016-12-27 14:19:20 +010091PyAPI_FUNC(int) _PyDict_DelItemIf(PyObject *mp, PyObject *key,
92 int (*predicate)(PyObject *value));
Serhiy Storchakab9d98d52015-10-02 12:47:11 +030093#endif
Mark Hammond91a681d2002-08-12 07:21:58 +000094PyAPI_FUNC(void) PyDict_Clear(PyObject *mp);
95PyAPI_FUNC(int) PyDict_Next(
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000096 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +000097#ifndef Py_LIMITED_API
Benjamin Peterson7d95e402012-04-23 11:24:50 -040098PyDictKeysObject *_PyDict_NewKeysForClass(void);
99PyAPI_FUNC(PyObject *) PyObject_GenericGetDict(PyObject *, void *);
Thomas Wouterscf297e42007-02-23 15:07:44 +0000100PyAPI_FUNC(int) _PyDict_Next(
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000101 PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
Eric Snow96c6af92015-05-29 22:21:39 -0600102PyObject *_PyDictView_New(PyObject *, PyTypeObject *);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +0000103#endif
Mark Hammond91a681d2002-08-12 07:21:58 +0000104PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp);
105PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp);
106PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp);
Martin v. Löwis18e16552006-02-15 17:27:45 +0000107PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp);
Mark Hammond91a681d2002-08-12 07:21:58 +0000108PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp);
Raymond Hettingerbc0f2ab2003-11-25 21:12:14 +0000109PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +0000110#ifndef Py_LIMITED_API
Serhiy Storchaka5ab81d72016-12-16 16:18:57 +0200111/* Get the number of items of a dictionary. */
112#define PyDict_GET_SIZE(mp) (assert(PyDict_Check(mp)),((PyDictObject *)mp)->ma_used)
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000113PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, Py_hash_t hash);
Christian Heimes99170a52007-12-19 02:07:34 +0000114PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000115PyAPI_FUNC(void) _PyDict_MaybeUntrack(PyObject *mp);
Benjamin Petersonfb886362010-04-24 18:21:17 +0000116PyAPI_FUNC(int) _PyDict_HasOnlyStringKeys(PyObject *mp);
Martin v. Loewis4f2f3b62012-04-24 19:13:57 +0200117Py_ssize_t _PyDict_KeysSize(PyDictKeysObject *keys);
Serhiy Storchaka0ce7a3a2015-12-22 08:16:18 +0200118Py_ssize_t _PyDict_SizeOf(PyDictObject *);
Yury Selivanov684ef2c2016-10-28 19:01:21 -0400119PyAPI_FUNC(PyObject *) _PyDict_Pop(PyObject *, PyObject *, PyObject *);
Serhiy Storchaka42e1ea92017-01-12 19:12:21 +0200120PyObject *_PyDict_Pop_KnownHash(PyObject *, PyObject *, Py_hash_t, PyObject *);
Eric Snow96c6af92015-05-29 22:21:39 -0600121PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *);
Benjamin Peterson7d95e402012-04-23 11:24:50 -0400122#define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)
Antoine Pitrou9a812cb2011-11-15 00:00:12 +0100123
124PyAPI_FUNC(int) PyDict_ClearFreeList(void);
Martin v. Löwis4d0d4712010-12-03 20:14:31 +0000125#endif
Jeremy Hyltona12c7a72000-03-30 22:27:31 +0000126
Tim Petersf582b822001-12-11 18:51:08 +0000127/* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */
Mark Hammond91a681d2002-08-12 07:21:58 +0000128PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other);
Tim Petersf582b822001-12-11 18:51:08 +0000129
130/* PyDict_Merge updates/merges from a mapping object (an object that
131 supports PyMapping_Keys() and PyObject_GetItem()). If override is true,
132 the last occurrence of a key wins, else the first. The Python
133 dict.update(other) is equivalent to PyDict_Merge(dict, other, 1).
134*/
Mark Hammond91a681d2002-08-12 07:21:58 +0000135PyAPI_FUNC(int) PyDict_Merge(PyObject *mp,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000136 PyObject *other,
137 int override);
Tim Petersf582b822001-12-11 18:51:08 +0000138
Benjamin Peterson025e9eb2015-05-05 20:16:41 -0400139#ifndef Py_LIMITED_API
Serhiy Storchakae036ef82016-10-02 11:06:43 +0300140/* Like PyDict_Merge, but override can be 0, 1 or 2. If override is 0,
141 the first occurrence of a key wins, if override is 1, the last occurrence
142 of a key wins, if override is 2, a KeyError with conflicting key as
143 argument is raised.
144*/
145PyAPI_FUNC(int) _PyDict_MergeEx(PyObject *mp, PyObject *other, int override);
Benjamin Peterson025e9eb2015-05-05 20:16:41 -0400146PyAPI_FUNC(PyObject *) _PyDictView_Intersect(PyObject* self, PyObject *other);
147#endif
148
Tim Petersf582b822001-12-11 18:51:08 +0000149/* PyDict_MergeFromSeq2 updates/merges from an iterable object producing
150 iterable objects of length 2. If override is true, the last occurrence
151 of a key wins, else the first. The Python dict constructor dict(seq2)
152 is equivalent to dict={}; PyDict_MergeFromSeq(dict, seq2, 1).
153*/
Mark Hammond91a681d2002-08-12 07:21:58 +0000154PyAPI_FUNC(int) PyDict_MergeFromSeq2(PyObject *d,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000155 PyObject *seq2,
156 int override);
Guido van Rossum2ec90311997-05-13 21:23:32 +0000157
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +0000158PyAPI_FUNC(PyObject *) PyDict_GetItemString(PyObject *dp, const char *key);
Serhiy Storchaka9fab79b2016-09-11 11:03:14 +0300159#ifndef Py_LIMITED_API
Victor Stinner3c1e4812012-03-26 22:10:51 +0200160PyAPI_FUNC(PyObject *) _PyDict_GetItemId(PyObject *dp, struct _Py_Identifier *key);
Serhiy Storchaka9fab79b2016-09-11 11:03:14 +0300161#endif /* !Py_LIMITED_API */
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +0000162PyAPI_FUNC(int) PyDict_SetItemString(PyObject *dp, const char *key, PyObject *item);
Serhiy Storchaka9fab79b2016-09-11 11:03:14 +0300163#ifndef Py_LIMITED_API
Victor Stinner3c1e4812012-03-26 22:10:51 +0200164PyAPI_FUNC(int) _PyDict_SetItemId(PyObject *dp, struct _Py_Identifier *key, PyObject *item);
Serhiy Storchaka9fab79b2016-09-11 11:03:14 +0300165#endif /* !Py_LIMITED_API */
Martin v. Löwis32b4a1b2002-12-11 13:21:12 +0000166PyAPI_FUNC(int) PyDict_DelItemString(PyObject *dp, const char *key);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000167
Benjamin Peterson7d95e402012-04-23 11:24:50 -0400168#ifndef Py_LIMITED_API
Victor Stinner8ea86502013-11-08 14:07:11 +0100169PyAPI_FUNC(int) _PyDict_DelItemId(PyObject *mp, struct _Py_Identifier *key);
170PyAPI_FUNC(void) _PyDict_DebugMallocStats(FILE *out);
171
Benjamin Peterson7d95e402012-04-23 11:24:50 -0400172int _PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr, PyObject *name, PyObject *value);
173PyObject *_PyDict_LoadGlobal(PyDictObject *, PyDictObject *, PyObject *);
174#endif
175
Guido van Rossuma3309961993-07-28 09:05:47 +0000176#ifdef __cplusplus
177}
178#endif
179#endif /* !Py_DICTOBJECT_H */