447f8eec40bec49ceab42e8ddf88f412ac8aebb2
[ccan] / ccan / intmap / intmap.c
1 /* CC0 license (public domain) - see LICENSE file for details */
2 /* This code is based on ccan/strmap.c. */
3 #include <ccan/intmap/intmap.h>
4 #include <ccan/short_types/short_types.h>
5 #include <ccan/str/str.h>
6 #include <ccan/ilog/ilog.h>
7 #include <assert.h>
8 #include <stdlib.h>
9 #include <errno.h>
10
11 struct node {
12         /* These point to strings or nodes. */
13         struct intmap child[2];
14         /* The bit where these children differ (0 == lsb) */
15         u8 bit_num;
16 };
17
18 /* Closest member to this in a non-empty map. */
19 static struct intmap *closest(struct intmap *n, intmap_index_t index)
20 {
21         /* Anything with NULL value is a node. */
22         while (!n->v) {
23                 u8 direction = (index >> n->u.n->bit_num) & 1;
24                 n = &n->u.n->child[direction];
25         }
26         return n;
27 }
28
29 void *intmap_get_(const struct intmap *map, intmap_index_t index)
30 {
31         struct intmap *n;
32
33         /* Not empty map? */
34         if (!intmap_empty_(map)) {
35                 n = closest((struct intmap *)map, index);
36                 if (index == n->u.i)
37                         return n->v;
38         }
39         errno = ENOENT;
40         return NULL;
41 }
42
43 bool intmap_add_(struct intmap *map, intmap_index_t index, const void *value)
44 {
45         struct intmap *n;
46         struct node *newn;
47         u8 bit_num, new_dir;
48
49         assert(value);
50
51         /* Empty map? */
52         if (intmap_empty_(map)) {
53                 map->u.i = index;
54                 map->v = (void *)value;
55                 return true;
56         }
57
58         /* Find closest existing member. */
59         n = closest(map, index);
60
61         /* Find highest bit where they differ. */
62         bit_num = ilog64(n->u.i ^ index);
63         if (bit_num == 0) {
64                 errno = EEXIST;
65                 return false;
66         }
67         bit_num--;
68
69         assert(bit_num < CHAR_BIT*sizeof(index));
70
71         /* Which direction do we go at this bit? */
72         new_dir = (index >> bit_num) & 1;
73
74         /* Allocate new node. */
75         newn = malloc(sizeof(*newn));
76         if (!newn) {
77                 errno = ENOMEM;
78                 return false;
79         }
80         newn->bit_num = bit_num;
81         newn->child[new_dir].v = (void *)value;
82         newn->child[new_dir].u.i = index;
83
84         /* Find where to insert: not closest, but first which differs! */
85         n = map;
86         while (!n->v) {
87                 u8 direction;
88
89                 /* Subtle: bit numbers are "backwards" for comparison */
90                 if (n->u.n->bit_num < bit_num)
91                         break;
92
93                 direction = (index >> n->u.n->bit_num) & 1;
94                 n = &n->u.n->child[direction];
95         }
96
97         newn->child[!new_dir] = *n;
98         n->u.n = newn;
99         n->v = NULL;
100         return true;
101 }
102
103 void *intmap_del_(struct intmap *map, intmap_index_t index)
104 {
105         struct intmap *parent = NULL, *n;
106         u8 direction;
107         void *value;
108
109         /* Empty map? */
110         if (intmap_empty_(map)) {
111                 errno = ENOENT;
112                 return NULL;
113         }
114
115         /* Find closest, but keep track of parent. */
116         n = map;
117         /* Anything with NULL value is a node. */
118         while (!n->v) {
119                 parent = n;
120                 direction = (index >> n->u.n->bit_num) & 1;
121                 n = &n->u.n->child[direction];
122         }
123
124         /* Did we find it? */
125         if (index != n->u.i) {
126                 errno = ENOENT;
127                 return NULL;
128         }
129
130         value = n->v;
131
132         if (!parent) {
133                 /* We deleted last node. */
134                 intmap_init_(map);
135         } else {
136                 struct node *old = parent->u.n;
137                 /* Raise other node to parent. */
138                 *parent = old->child[!direction];
139                 free(old);
140         }
141         errno = 0;
142         return value;
143 }
144
145 void *intmap_first_(const struct intmap *map, intmap_index_t *indexp)
146 {
147         const struct intmap *n;
148
149         if (intmap_empty_(map)) {
150                 errno = ENOENT;
151                 return NULL;
152         }
153         
154         n = map;
155         /* Anything with NULL value is a node. */
156         while (!n->v)
157                 n = &n->u.n->child[0];
158         errno = 0;
159         *indexp = n->u.i;
160         return n->v;
161 }
162                 
163 void *intmap_after_(const struct intmap *map, intmap_index_t *indexp)
164 {
165         const struct intmap *n, *prev = NULL;
166
167         /* Special case of empty map */
168         if (intmap_empty_(map)) {
169                 errno = ENOENT;
170                 return NULL;
171         }
172
173         /* Follow down, track the last place where we could have set a bit
174          * instead of clearing it: this is the higher alternative tree. */
175         n = map;
176         while (!n->v) {
177                 u8 direction = (*indexp >> n->u.n->bit_num) & 1;
178                 if (!direction)
179                         prev = n;
180                 n = &n->u.n->child[direction];
181         }
182
183         /* Found a successor? */
184         if (n->u.i > *indexp) {
185                 errno = 0;
186                 *indexp = n->u.i;
187                 return n->v;
188         }
189
190         /* Nowhere to go back up to? */
191         if (!prev) {
192                 errno = ENOENT;
193                 return NULL;
194         }
195
196         /* Get first one from that other branch. */
197         return intmap_first_(&prev->u.n->child[1], indexp);
198 }
199
200 void *intmap_last_(const struct intmap *map, intmap_index_t *indexp)
201 {
202         const struct intmap *n;
203
204         if (intmap_empty_(map)) {
205                 errno = ENOENT;
206                 return NULL;
207         }
208
209         n = map;
210         /* Anything with NULL value is a node. */
211         while (!n->v)
212                 n = &n->u.n->child[1];
213         errno = 0;
214         *indexp = n->u.i;
215         return n->v;
216 }
217
218 static void clear(struct intmap n)
219 {
220         if (!n.v) {
221                 clear(n.u.n->child[0]);
222                 clear(n.u.n->child[1]);
223                 free(n.u.n);
224         }
225 }
226
227 void intmap_clear_(struct intmap *map)
228 {
229         if (!intmap_empty_(map))
230                 clear(*map);
231         intmap_init_(map);
232 }