JezK
Edit File: pycore_hamt.h
#ifndef Py_INTERNAL_HAMT_H #define Py_INTERNAL_HAMT_H #ifndef Py_BUILD_CORE # error "this header requires Py_BUILD_CORE define" #endif /* HAMT tree is shaped by hashes of keys. Every group of 5 bits of a hash denotes the exact position of the key in one level of the tree. Since we're using 32 bit hashes, we can have at most 7 such levels. Although if there are two distinct keys with equal hashes, they will have to occupy the same cell in the 7th level of the tree -- so we'd put them in a "collision" node. Which brings the total possible tree depth to 8. Read more about the actual layout of the HAMT tree in `hamt.c`. This constant is used to define a datastucture for storing iteration state. */ #define _Py_HAMT_MAX_TREE_DEPTH 8 extern PyTypeObject _PyHamt_Type; extern PyTypeObject _PyHamt_ArrayNode_Type; extern PyTypeObject _PyHamt_BitmapNode_Type; extern PyTypeObject _PyHamt_CollisionNode_Type; extern PyTypeObject _PyHamtKeys_Type; extern PyTypeObject _PyHamtValues_Type; extern PyTypeObject _PyHamtItems_Type; /* runtime lifecycle */ void _PyHamt_Fini(PyInterpreterState *); /* other API */ #define PyHamt_Check(o) Py_IS_TYPE(o, &_PyHamt_Type) /* Abstract tree node. */ typedef struct { PyObject_HEAD } PyHamtNode; /* An HAMT immutable mapping collection. */ typedef struct { PyObject_HEAD PyHamtNode *h_root; PyObject *h_weakreflist; Py_ssize_t h_count; } PyHamtObject; /* A struct to hold the state of depth-first traverse of the tree. HAMT is an immutable collection. Iterators will hold a strong reference to it, and every node in the HAMT has strong references to its children. So for iterators, we can implement zero allocations and zero reference inc/dec depth-first iteration. - i_nodes: an array of seven pointers to tree nodes - i_level: the current node in i_nodes - i_pos: an array of positions within nodes in i_nodes. */ typedef struct { PyHamtNode *i_nodes[_Py_HAMT_MAX_TREE_DEPTH]; Py_ssize_t i_pos[_Py_HAMT_MAX_TREE_DEPTH]; int8_t i_level; } PyHamtIteratorState; /* Base iterator object. Contains the iteration state, a pointer to the HAMT tree, and a pointer to the 'yield function'. The latter is a simple function that returns a key/value tuple for the 'Items' iterator, just a key for the 'Keys' iterator, and a value for the 'Values' iterator. */ typedef struct { PyObject_HEAD PyHamtObject *hi_obj; PyHamtIteratorState hi_iter; binaryfunc hi_yield; } PyHamtIterator; /* Create a new HAMT immutable mapping. */ PyHamtObject * _PyHamt_New(void); /* Return a new collection based on "o", but with an additional key/val pair. */ PyHamtObject * _PyHamt_Assoc(PyHamtObject *o, PyObject *key, PyObject *val); /* Return a new collection based on "o", but without "key". */ PyHamtObject * _PyHamt_Without(PyHamtObject *o, PyObject *key); /* Find "key" in the "o" collection. Return: - -1: An error occurred. - 0: "key" wasn't found in "o". - 1: "key" is in "o"; "*val" is set to its value (a borrowed ref). */ int _PyHamt_Find(PyHamtObject *o, PyObject *key, PyObject **val); /* Check if "v" is equal to "w". Return: - 0: v != w - 1: v == w - -1: An error occurred. */ int _PyHamt_Eq(PyHamtObject *v, PyHamtObject *w); /* Return the size of "o"; equivalent of "len(o)". */ Py_ssize_t _PyHamt_Len(PyHamtObject *o); /* Return a Keys iterator over "o". */ PyObject * _PyHamt_NewIterKeys(PyHamtObject *o); /* Return a Values iterator over "o". */ PyObject * _PyHamt_NewIterValues(PyHamtObject *o); /* Return a Items iterator over "o". */ PyObject * _PyHamt_NewIterItems(PyHamtObject *o); #endif /* !Py_INTERNAL_HAMT_H */