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 | /* |
10 | HAMT tree is shaped by hashes of keys. Every group of 5 bits of a hash denotes |
11 | the exact position of the key in one level of the tree. Since we're using |
12 | 32 bit hashes, we can have at most 7 such levels. Although if there are |
13 | two distinct keys with equal hashes, they will have to occupy the same |
14 | cell in the 7th level of the tree -- so we'd put them in a "collision" node. |
15 | Which brings the total possible tree depth to 8. Read more about the actual |
16 | layout of the HAMT tree in `hamt.c`. |
17 | |
18 | This 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. */ |
27 | typedef struct { |
28 | PyObject_HEAD |
29 | } PyHamtNode; |
30 | |
31 | |
32 | /* An HAMT immutable mapping collection. */ |
33 | typedef 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 | */ |
53 | typedef 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 | */ |
68 | typedef struct { |
69 | PyObject_HEAD |
70 | PyHamtObject *hi_obj; |
71 | PyHamtIteratorState hi_iter; |
72 | binaryfunc hi_yield; |
73 | } PyHamtIterator; |
74 | |
75 | |
76 | PyAPI_DATA(PyTypeObject) _PyHamt_Type; |
77 | PyAPI_DATA(PyTypeObject) _PyHamt_ArrayNode_Type; |
78 | PyAPI_DATA(PyTypeObject) _PyHamt_BitmapNode_Type; |
79 | PyAPI_DATA(PyTypeObject) _PyHamt_CollisionNode_Type; |
80 | PyAPI_DATA(PyTypeObject) _PyHamtKeys_Type; |
81 | PyAPI_DATA(PyTypeObject) _PyHamtValues_Type; |
82 | PyAPI_DATA(PyTypeObject) _PyHamtItems_Type; |
83 | |
84 | |
85 | /* Create a new HAMT immutable mapping. */ |
86 | PyHamtObject * _PyHamt_New(void); |
87 | |
88 | /* Return a new collection based on "o", but with an additional |
89 | key/val pair. */ |
90 | PyHamtObject * _PyHamt_Assoc(PyHamtObject *o, PyObject *key, PyObject *val); |
91 | |
92 | /* Return a new collection based on "o", but without "key". */ |
93 | PyHamtObject * _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 | */ |
102 | int _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 | */ |
111 | int _PyHamt_Eq(PyHamtObject *v, PyHamtObject *w); |
112 | |
113 | /* Return the size of "o"; equivalent of "len(o)". */ |
114 | Py_ssize_t _PyHamt_Len(PyHamtObject *o); |
115 | |
116 | /* Return a Keys iterator over "o". */ |
117 | PyObject * _PyHamt_NewIterKeys(PyHamtObject *o); |
118 | |
119 | /* Return a Values iterator over "o". */ |
120 | PyObject * _PyHamt_NewIterValues(PyHamtObject *o); |
121 | |
122 | /* Return a Items iterator over "o". */ |
123 | PyObject * _PyHamt_NewIterItems(PyHamtObject *o); |
124 | |
125 | int _PyHamt_Init(void); |
126 | void _PyHamt_Fini(void); |
127 | |
128 | #endif /* !Py_INTERNAL_HAMT_H */ |
129 | |