]>
Commit | Line | Data |
---|---|---|
a40f0f64 P |
1 | The sparse_array.c file contains an implementation of a sparse array that |
2 | attempts to be both space and time efficient. | |
3 | ||
4 | The sparse array is represented using a tree structure. Each node in the | |
5 | tree contains a block of pointers to either the user supplied leaf values or | |
6 | to another node. | |
7 | ||
8 | There are a number of parameters used to define the block size: | |
9 | ||
10 | OPENSSL_SA_BLOCK_BITS Specifies the number of bits covered by each block | |
11 | SA_BLOCK_MAX Specifies the number of pointers in each block | |
12 | SA_BLOCK_MASK Specifies a bit mask to perform modulo block size | |
13 | SA_BLOCK_MAX_LEVELS Indicates the maximum possible height of the tree | |
14 | ||
15 | These constants are inter-related: | |
16 | SA_BLOCK_MAX = 2 ^ OPENSSL_SA_BLOCK_BITS | |
17 | SA_BLOCK_MASK = SA_BLOCK_MAX - 1 | |
18 | SA_BLOCK_MAX_LEVELS = number of bits in size_t divided by | |
19 | OPENSSL_SA_BLOCK_BITS rounded up to the next multiple | |
20 | of OPENSSL_SA_BLOCK_BITS | |
21 | ||
22 | OPENSSL_SA_BLOCK_BITS can be defined at compile time and this overrides the | |
23 | built in setting. | |
24 | ||
25 | As a space and performance optimisation, the height of the tree is usually | |
26 | less than the maximum possible height. Only sufficient height is allocated to | |
27 | accommodate the largest index added to the data structure. | |
28 | ||
29 | The largest index used to add a value to the array determines the tree height: | |
30 | ||
31 | +----------------------+---------------------+ | |
32 | | Largest Added Index | Height of Tree | | |
33 | +----------------------+---------------------+ | |
34 | | SA_BLOCK_MAX - 1 | 1 | | |
35 | | SA_BLOCK_MAX ^ 2 - 1 | 2 | | |
36 | | SA_BLOCK_MAX ^ 3 - 1 | 3 | | |
37 | | ... | ... | | |
38 | | size_t max | SA_BLOCK_MAX_LEVELS | | |
39 | +----------------------+---------------------+ | |
40 | ||
41 | The tree height is dynamically increased as needed based on additions. | |
42 | ||
43 | An empty tree is represented by a NULL root pointer. Inserting a value at | |
44 | index 0 results in the allocation of a top level node full of null pointers | |
45 | except for the single pointer to the user's data (N = SA_BLOCK_MAX for | |
c2969ff6 | 46 | brevity): |
a40f0f64 P |
47 | |
48 | +----+ | |
49 | |Root| | |
50 | |Node| | |
51 | +-+--+ | |
52 | | | |
53 | | | |
54 | | | |
55 | v | |
56 | +-+-+---+---+---+---+ | |
57 | | 0 | 1 | 2 |...|N-1| | |
58 | | |nil|nil|...|nil| | |
59 | +-+-+---+---+---+---+ | |
60 | | | |
61 | | | |
62 | | | |
63 | v | |
64 | +-+--+ | |
65 | |User| | |
66 | |Data| | |
67 | +----+ | |
68 | Index 0 | |
69 | ||
70 | ||
71 | Inserting at element 2N+1 creates a new root node and pushes down the old root | |
72 | node. It then creates a second second level node to hold the pointer to the | |
73 | user's new data: | |
74 | ||
75 | +----+ | |
76 | |Root| | |
77 | |Node| | |
78 | +-+--+ | |
79 | | | |
80 | | | |
81 | | | |
82 | v | |
83 | +-+-+---+---+---+---+ | |
84 | | 0 | 1 | 2 |...|N-1| | |
85 | | |nil| |...|nil| | |
86 | +-+-+---+-+-+---+---+ | |
87 | | | | |
88 | | +------------------+ | |
89 | | | | |
90 | v v | |
91 | +-+-+---+---+---+---+ +-+-+---+---+---+---+ | |
92 | | 0 | 1 | 2 |...|N-1| | 0 | 1 | 2 |...|N-1| | |
93 | |nil| |nil|...|nil| |nil| |nil|...|nil| | |
94 | +-+-+---+---+---+---+ +---+-+-+---+---+---+ | |
95 | | | | |
96 | | | | |
97 | | | | |
98 | v v | |
99 | +-+--+ +-+--+ | |
100 | |User| |User| | |
101 | |Data| |Data| | |
102 | +----+ +----+ | |
103 | Index 0 Index 2N+1 | |
104 | ||
105 | ||
106 | The nodes themselves are allocated in a sparse manner. Only nodes which exist | |
107 | along a path from the root of the tree to an added leaf will be allocated. | |
108 | The complexity is hidden and nodes are allocated on an as needed basis. | |
109 | Because the data is expected to be sparse this doesn't result in a large waste | |
110 | of space. | |
111 | ||
112 | Values can be removed from the sparse array by setting their index position to | |
113 | NULL. The data structure does not attempt to reclaim nodes or reduce the | |
114 | height of the tree on removal. For example, now setting index 0 to NULL would | |
115 | result in: | |
116 | ||
117 | +----+ | |
118 | |Root| | |
119 | |Node| | |
120 | +-+--+ | |
121 | | | |
122 | | | |
123 | | | |
124 | v | |
125 | +-+-+---+---+---+---+ | |
126 | | 0 | 1 | 2 |...|N-1| | |
127 | | |nil| |...|nil| | |
128 | +-+-+---+-+-+---+---+ | |
129 | | | | |
130 | | +------------------+ | |
131 | | | | |
132 | v v | |
133 | +-+-+---+---+---+---+ +-+-+---+---+---+---+ | |
134 | | 0 | 1 | 2 |...|N-1| | 0 | 1 | 2 |...|N-1| | |
135 | |nil|nil|nil|...|nil| |nil| |nil|...|nil| | |
136 | +---+---+---+---+---+ +---+-+-+---+---+---+ | |
137 | | | |
138 | | | |
139 | | | |
140 | v | |
141 | +-+--+ | |
142 | |User| | |
143 | |Data| | |
144 | +----+ | |
145 | Index 2N+1 | |
146 | ||
147 | ||
148 | Accesses to elements in the sparse array take O(log n) time where n is the | |
149 | largest element. The base of the logarithm is SA_BLOCK_MAX, so for moderately | |
150 | small indices (e.g. NIDs), single level (constant time) access is achievable. | |
151 | Space usage is O(minimum(m, n log(n)) where m is the number of elements in the | |
152 | array. | |
153 | ||
154 | Note: sparse arrays only include pointers to types. Thus, SPARSE_ARRAY_OF(char) | |
155 | can be used to store a string. |