blob: 6e87c4bebbdd6508af8c805e3feadede8e4964e7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#ifndef IMMUTABLES_MAP_H
#define IMMUTABLES_MAP_H
#include <stdint.h>
#include "Python.h"
#define _Py_HAMT_MAX_TREE_DEPTH 7
#define Map_Check(o) (Py_TYPE(o) == &_Map_Type)
/* Abstract tree node. */
typedef struct {
PyObject_HEAD
} MapNode;
/* An HAMT immutable mapping collection. */
typedef struct {
PyObject_HEAD
MapNode *h_root;
PyObject *h_weakreflist;
Py_ssize_t h_count;
Py_hash_t h_hash;
} MapObject;
/* 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 {
MapNode *i_nodes[_Py_HAMT_MAX_TREE_DEPTH];
Py_ssize_t i_pos[_Py_HAMT_MAX_TREE_DEPTH];
int8_t i_level;
} MapIteratorState;
/* 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
MapObject *hi_obj;
MapIteratorState hi_iter;
binaryfunc hi_yield;
} MapIterator;
PyTypeObject _Map_Type;
PyTypeObject _Map_ArrayNode_Type;
PyTypeObject _Map_BitmapNode_Type;
PyTypeObject _Map_CollisionNode_Type;
PyTypeObject _MapKeys_Type;
PyTypeObject _MapValues_Type;
PyTypeObject _MapItems_Type;
#endif
|
