1#ifndef Py_INTERNAL_HAMT_H
2#define Py_INTERNAL_HAMT_H
3
4#ifndef Py_BUILD_CORE
5# error "this header requires Py_BUILD_CORE define"
6#endif
7
8
9/*
10HAMT tree is shaped by hashes of keys. Every group of 5 bits of a hash denotes
11the exact position of the key in one level of the tree. Since we're using
1232 bit hashes, we can have at most 7 such levels. Although if there are
13two distinct keys with equal hashes, they will have to occupy the same
14cell in the 7th level of the tree -- so we'd put them in a "collision" node.
15Which brings the total possible tree depth to 8. Read more about the actual
16layout of the HAMT tree in `hamt.c`.
17
18This constant is used to define a datastucture for storing iteration state.
19*/
20#define _Py_HAMT_MAX_TREE_DEPTH 8
21
22
23#define PyHamt_Check(o) Py_IS_TYPE(o, &_PyHamt_Type)
24
25
26/* Abstract tree node. */
27typedef struct {
28 PyObject_HEAD
29} PyHamtNode;
30
31
32/* An HAMT immutable mapping collection. */
33typedef struct {
34 PyObject_HEAD
35 PyHamtNode *h_root;
36 PyObject *h_weakreflist;
37 Py_ssize_t h_count;
38} PyHamtObject;
39
40
41/* A struct to hold the state of depth-first traverse of the tree.
42
43 HAMT is an immutable collection. Iterators will hold a strong reference
44 to it, and every node in the HAMT has strong references to its children.
45
46 So for iterators, we can implement zero allocations and zero reference
47 inc/dec depth-first iteration.
48
49 - i_nodes: an array of seven pointers to tree nodes
50 - i_level: the current node in i_nodes
51 - i_pos: an array of positions within nodes in i_nodes.
52*/
53typedef struct {
54 PyHamtNode *i_nodes[_Py_HAMT_MAX_TREE_DEPTH];
55 Py_ssize_t i_pos[_Py_HAMT_MAX_TREE_DEPTH];
56 int8_t i_level;
57} PyHamtIteratorState;
58
59
60/* Base iterator object.
61
62 Contains the iteration state, a pointer to the HAMT tree,
63 and a pointer to the 'yield function'. The latter is a simple
64 function that returns a key/value tuple for the 'Items' iterator,
65 just a key for the 'Keys' iterator, and a value for the 'Values'
66 iterator.
67*/
68typedef struct {
69 PyObject_HEAD
70 PyHamtObject *hi_obj;
71 PyHamtIteratorState hi_iter;
72 binaryfunc hi_yield;
73} PyHamtIterator;
74
75
76PyAPI_DATA(PyTypeObject) _PyHamt_Type;
77PyAPI_DATA(PyTypeObject) _PyHamt_ArrayNode_Type;
78PyAPI_DATA(PyTypeObject) _PyHamt_BitmapNode_Type;
79PyAPI_DATA(PyTypeObject) _PyHamt_CollisionNode_Type;
80PyAPI_DATA(PyTypeObject) _PyHamtKeys_Type;
81PyAPI_DATA(PyTypeObject) _PyHamtValues_Type;
82PyAPI_DATA(PyTypeObject) _PyHamtItems_Type;
83
84
85/* Create a new HAMT immutable mapping. */
86PyHamtObject * _PyHamt_New(void);
87
88/* Return a new collection based on "o", but with an additional
89 key/val pair. */
90PyHamtObject * _PyHamt_Assoc(PyHamtObject *o, PyObject *key, PyObject *val);
91
92/* Return a new collection based on "o", but without "key". */
93PyHamtObject * _PyHamt_Without(PyHamtObject *o, PyObject *key);
94
95/* Find "key" in the "o" collection.
96
97 Return:
98 - -1: An error occurred.
99 - 0: "key" wasn't found in "o".
100 - 1: "key" is in "o"; "*val" is set to its value (a borrowed ref).
101*/
102int _PyHamt_Find(PyHamtObject *o, PyObject *key, PyObject **val);
103
104/* Check if "v" is equal to "w".
105
106 Return:
107 - 0: v != w
108 - 1: v == w
109 - -1: An error occurred.
110*/
111int _PyHamt_Eq(PyHamtObject *v, PyHamtObject *w);
112
113/* Return the size of "o"; equivalent of "len(o)". */
114Py_ssize_t _PyHamt_Len(PyHamtObject *o);
115
116/* Return a Keys iterator over "o". */
117PyObject * _PyHamt_NewIterKeys(PyHamtObject *o);
118
119/* Return a Values iterator over "o". */
120PyObject * _PyHamt_NewIterValues(PyHamtObject *o);
121
122/* Return a Items iterator over "o". */
123PyObject * _PyHamt_NewIterItems(PyHamtObject *o);
124
125int _PyHamt_Init(void);
126void _PyHamt_Fini(void);
127
128#endif /* !Py_INTERNAL_HAMT_H */
129