Yury Selivanov | f23746a | 2018-01-22 19:11:18 -0500 | [diff] [blame] | 1 | #ifndef Py_INTERNAL_HAMT_H |
| 2 | #define Py_INTERNAL_HAMT_H |
| 3 | |
Victor Stinner | 5c75f37 | 2019-04-17 23:02:26 +0200 | [diff] [blame] | 4 | #ifndef Py_BUILD_CORE |
| 5 | # error "this header requires Py_BUILD_CORE define" |
Victor Stinner | 130893d | 2018-11-09 13:03:37 +0100 | [diff] [blame] | 6 | #endif |
Yury Selivanov | f23746a | 2018-01-22 19:11:18 -0500 | [diff] [blame] | 7 | |
| 8 | #define _Py_HAMT_MAX_TREE_DEPTH 7 |
| 9 | |
| 10 | |
| 11 | #define PyHamt_Check(o) (Py_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: |
Ville Skyttä | 61f82e0 | 2018-04-20 23:08:45 +0300 | [diff] [blame] | 86 | - -1: An error occurred. |
Yury Selivanov | f23746a | 2018-01-22 19:11:18 -0500 | [diff] [blame] | 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 */ |