Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/python3.12/internal/pycore_hamt.h


$ cat -n /usr/include/python3.12/internal/pycore_hamt.h

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