EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-30 10:18:08
0001 #ifndef Py_INTERNAL_HAMT_H 0002 #define Py_INTERNAL_HAMT_H 0003 0004 #ifndef Py_BUILD_CORE 0005 # error "this header requires Py_BUILD_CORE define" 0006 #endif 0007 0008 0009 /* 0010 HAMT tree is shaped by hashes of keys. Every group of 5 bits of a hash denotes 0011 the exact position of the key in one level of the tree. Since we're using 0012 32 bit hashes, we can have at most 7 such levels. Although if there are 0013 two distinct keys with equal hashes, they will have to occupy the same 0014 cell in the 7th level of the tree -- so we'd put them in a "collision" node. 0015 Which brings the total possible tree depth to 8. Read more about the actual 0016 layout of the HAMT tree in `hamt.c`. 0017 0018 This constant is used to define a datastucture for storing iteration state. 0019 */ 0020 #define _Py_HAMT_MAX_TREE_DEPTH 8 0021 0022 0023 extern PyTypeObject _PyHamt_Type; 0024 extern PyTypeObject _PyHamt_ArrayNode_Type; 0025 extern PyTypeObject _PyHamt_BitmapNode_Type; 0026 extern PyTypeObject _PyHamt_CollisionNode_Type; 0027 extern PyTypeObject _PyHamtKeys_Type; 0028 extern PyTypeObject _PyHamtValues_Type; 0029 extern PyTypeObject _PyHamtItems_Type; 0030 0031 0032 /* other API */ 0033 0034 #define PyHamt_Check(o) Py_IS_TYPE((o), &_PyHamt_Type) 0035 0036 0037 /* Abstract tree node. */ 0038 typedef struct { 0039 PyObject_HEAD 0040 } PyHamtNode; 0041 0042 0043 /* An HAMT immutable mapping collection. */ 0044 typedef struct { 0045 PyObject_HEAD 0046 PyHamtNode *h_root; 0047 PyObject *h_weakreflist; 0048 Py_ssize_t h_count; 0049 } PyHamtObject; 0050 0051 0052 typedef struct { 0053 PyObject_VAR_HEAD 0054 uint32_t b_bitmap; 0055 PyObject *b_array[1]; 0056 } PyHamtNode_Bitmap; 0057 0058 0059 /* A struct to hold the state of depth-first traverse of the tree. 0060 0061 HAMT is an immutable collection. Iterators will hold a strong reference 0062 to it, and every node in the HAMT has strong references to its children. 0063 0064 So for iterators, we can implement zero allocations and zero reference 0065 inc/dec depth-first iteration. 0066 0067 - i_nodes: an array of seven pointers to tree nodes 0068 - i_level: the current node in i_nodes 0069 - i_pos: an array of positions within nodes in i_nodes. 0070 */ 0071 typedef struct { 0072 PyHamtNode *i_nodes[_Py_HAMT_MAX_TREE_DEPTH]; 0073 Py_ssize_t i_pos[_Py_HAMT_MAX_TREE_DEPTH]; 0074 int8_t i_level; 0075 } PyHamtIteratorState; 0076 0077 0078 /* Base iterator object. 0079 0080 Contains the iteration state, a pointer to the HAMT tree, 0081 and a pointer to the 'yield function'. The latter is a simple 0082 function that returns a key/value tuple for the 'Items' iterator, 0083 just a key for the 'Keys' iterator, and a value for the 'Values' 0084 iterator. 0085 */ 0086 typedef struct { 0087 PyObject_HEAD 0088 PyHamtObject *hi_obj; 0089 PyHamtIteratorState hi_iter; 0090 binaryfunc hi_yield; 0091 } PyHamtIterator; 0092 0093 0094 /* Create a new HAMT immutable mapping. */ 0095 PyHamtObject * _PyHamt_New(void); 0096 0097 /* Return a new collection based on "o", but with an additional 0098 key/val pair. */ 0099 PyHamtObject * _PyHamt_Assoc(PyHamtObject *o, PyObject *key, PyObject *val); 0100 0101 /* Return a new collection based on "o", but without "key". */ 0102 PyHamtObject * _PyHamt_Without(PyHamtObject *o, PyObject *key); 0103 0104 /* Find "key" in the "o" collection. 0105 0106 Return: 0107 - -1: An error occurred. 0108 - 0: "key" wasn't found in "o". 0109 - 1: "key" is in "o"; "*val" is set to its value (a borrowed ref). 0110 */ 0111 int _PyHamt_Find(PyHamtObject *o, PyObject *key, PyObject **val); 0112 0113 /* Check if "v" is equal to "w". 0114 0115 Return: 0116 - 0: v != w 0117 - 1: v == w 0118 - -1: An error occurred. 0119 */ 0120 int _PyHamt_Eq(PyHamtObject *v, PyHamtObject *w); 0121 0122 /* Return the size of "o"; equivalent of "len(o)". */ 0123 Py_ssize_t _PyHamt_Len(PyHamtObject *o); 0124 0125 /* Return a Keys iterator over "o". */ 0126 PyObject * _PyHamt_NewIterKeys(PyHamtObject *o); 0127 0128 /* Return a Values iterator over "o". */ 0129 PyObject * _PyHamt_NewIterValues(PyHamtObject *o); 0130 0131 /* Return a Items iterator over "o". */ 0132 PyObject * _PyHamt_NewIterItems(PyHamtObject *o); 0133 0134 #endif /* !Py_INTERNAL_HAMT_H */
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|