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 #define _Py_HAMT_MAX_TREE_DEPTH 7 9 10 11 #define PyHamt_Check(o) Py_IS_TYPE(o, &_PyHamt_Type) 12 13 14 /* Abstract tree node. */ 15 typedef struct { 16 PyObject_HEAD 17 } PyHamtNode; 18 19 20 /* An HAMT immutable mapping collection. */ 21 typedef struct { 22 PyObject_HEAD 23 PyHamtNode *h_root; 24 PyObject *h_weakreflist; 25 Py_ssize_t h_count; 26 } PyHamtObject; 27 28 29 /* A struct to hold the state of depth-first traverse of the tree. 30 31 HAMT is an immutable collection. Iterators will hold a strong reference 32 to it, and every node in the HAMT has strong references to its children. 33 34 So for iterators, we can implement zero allocations and zero reference 35 inc/dec depth-first iteration. 36 37 - i_nodes: an array of seven pointers to tree nodes 38 - i_level: the current node in i_nodes 39 - i_pos: an array of positions within nodes in i_nodes. 40 */ 41 typedef struct { 42 PyHamtNode *i_nodes[_Py_HAMT_MAX_TREE_DEPTH]; 43 Py_ssize_t i_pos[_Py_HAMT_MAX_TREE_DEPTH]; 44 int8_t i_level; 45 } PyHamtIteratorState; 46 47 48 /* Base iterator object. 49 50 Contains the iteration state, a pointer to the HAMT tree, 51 and a pointer to the 'yield function'. The latter is a simple 52 function that returns a key/value tuple for the 'Items' iterator, 53 just a key for the 'Keys' iterator, and a value for the 'Values' 54 iterator. 55 */ 56 typedef struct { 57 PyObject_HEAD 58 PyHamtObject *hi_obj; 59 PyHamtIteratorState hi_iter; 60 binaryfunc hi_yield; 61 } PyHamtIterator; 62 63 64 PyAPI_DATA(PyTypeObject) _PyHamt_Type; 65 PyAPI_DATA(PyTypeObject) _PyHamt_ArrayNode_Type; 66 PyAPI_DATA(PyTypeObject) _PyHamt_BitmapNode_Type; 67 PyAPI_DATA(PyTypeObject) _PyHamt_CollisionNode_Type; 68 PyAPI_DATA(PyTypeObject) _PyHamtKeys_Type; 69 PyAPI_DATA(PyTypeObject) _PyHamtValues_Type; 70 PyAPI_DATA(PyTypeObject) _PyHamtItems_Type; 71 72 73 /* Create a new HAMT immutable mapping. */ 74 PyHamtObject * _PyHamt_New(void); 75 76 /* Return a new collection based on "o", but with an additional 77 key/val pair. */ 78 PyHamtObject * _PyHamt_Assoc(PyHamtObject *o, PyObject *key, PyObject *val); 79 80 /* Return a new collection based on "o", but without "key". */ 81 PyHamtObject * _PyHamt_Without(PyHamtObject *o, PyObject *key); 82 83 /* Find "key" in the "o" collection. 84 85 Return: 86 - -1: An error occurred. 87 - 0: "key" wasn't found in "o". 88 - 1: "key" is in "o"; "*val" is set to its value (a borrowed ref). 89 */ 90 int _PyHamt_Find(PyHamtObject *o, PyObject *key, PyObject **val); 91 92 /* Check if "v" is equal to "w". 93 94 Return: 95 - 0: v != w 96 - 1: v == w 97 - -1: An error occurred. 98 */ 99 int _PyHamt_Eq(PyHamtObject *v, PyHamtObject *w); 100 101 /* Return the size of "o"; equivalent of "len(o)". */ 102 Py_ssize_t _PyHamt_Len(PyHamtObject *o); 103 104 /* Return a Keys iterator over "o". */ 105 PyObject * _PyHamt_NewIterKeys(PyHamtObject *o); 106 107 /* Return a Values iterator over "o". */ 108 PyObject * _PyHamt_NewIterValues(PyHamtObject *o); 109 110 /* Return a Items iterator over "o". */ 111 PyObject * _PyHamt_NewIterItems(PyHamtObject *o); 112 113 int _PyHamt_Init(void); 114 void _PyHamt_Fini(void); 115 116 #endif /* !Py_INTERNAL_HAMT_H */ 117