1 /* $OpenBSD: tree.c,v 1.8 2021/06/14 17:58:16 eric Exp $ */
2
3 /*
4 * Copyright (c) 2012 Eric Faurot <eric@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 #include <sys/tree.h>
20
21 #include <inttypes.h>
22 #include <stdlib.h>
23
24 #include "tree.h"
25 #include "log.h"
26
27 struct treeentry {
28 SPLAY_ENTRY(treeentry) entry;
29 uint64_t id;
30 void *data;
31 };
32
33 static int treeentry_cmp(struct treeentry *, struct treeentry *);
34
35 SPLAY_PROTOTYPE(_tree, treeentry, entry, treeentry_cmp);
36
37 int
tree_check(struct tree * t,uint64_t id)38 tree_check(struct tree *t, uint64_t id)
39 {
40 struct treeentry key;
41
42 key.id = id;
43 return (SPLAY_FIND(_tree, &t->tree, &key) != NULL);
44 }
45
46 void *
tree_set(struct tree * t,uint64_t id,void * data)47 tree_set(struct tree *t, uint64_t id, void *data)
48 {
49 struct treeentry *entry, key;
50 char *old;
51
52 key.id = id;
53 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) {
54 if ((entry = malloc(sizeof *entry)) == NULL)
55 fatal("tree_set: malloc");
56 entry->id = id;
57 SPLAY_INSERT(_tree, &t->tree, entry);
58 old = NULL;
59 t->count += 1;
60 } else
61 old = entry->data;
62
63 entry->data = data;
64
65 return (old);
66 }
67
68 void
tree_xset(struct tree * t,uint64_t id,void * data)69 tree_xset(struct tree *t, uint64_t id, void *data)
70 {
71 struct treeentry *entry;
72
73 if ((entry = malloc(sizeof *entry)) == NULL)
74 fatal("tree_xset: malloc");
75 entry->id = id;
76 entry->data = data;
77 if (SPLAY_INSERT(_tree, &t->tree, entry))
78 fatalx("tree_xset(%p, 0x%016"PRIx64 ")", t, id);
79 t->count += 1;
80 }
81
82 void *
tree_get(struct tree * t,uint64_t id)83 tree_get(struct tree *t, uint64_t id)
84 {
85 struct treeentry key, *entry;
86
87 key.id = id;
88 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
89 return (NULL);
90
91 return (entry->data);
92 }
93
94 void *
tree_xget(struct tree * t,uint64_t id)95 tree_xget(struct tree *t, uint64_t id)
96 {
97 struct treeentry key, *entry;
98
99 key.id = id;
100 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
101 fatalx("tree_get(%p, 0x%016"PRIx64 ")", t, id);
102
103 return (entry->data);
104 }
105
106 void *
tree_pop(struct tree * t,uint64_t id)107 tree_pop(struct tree *t, uint64_t id)
108 {
109 struct treeentry key, *entry;
110 void *data;
111
112 key.id = id;
113 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
114 return (NULL);
115
116 data = entry->data;
117 SPLAY_REMOVE(_tree, &t->tree, entry);
118 free(entry);
119 t->count -= 1;
120
121 return (data);
122 }
123
124 void *
tree_xpop(struct tree * t,uint64_t id)125 tree_xpop(struct tree *t, uint64_t id)
126 {
127 struct treeentry key, *entry;
128 void *data;
129
130 key.id = id;
131 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL)
132 fatalx("tree_xpop(%p, 0x%016" PRIx64 ")", t, id);
133
134 data = entry->data;
135 SPLAY_REMOVE(_tree, &t->tree, entry);
136 free(entry);
137 t->count -= 1;
138
139 return (data);
140 }
141
142 int
tree_poproot(struct tree * t,uint64_t * id,void ** data)143 tree_poproot(struct tree *t, uint64_t *id, void **data)
144 {
145 struct treeentry *entry;
146
147 entry = SPLAY_ROOT(&t->tree);
148 if (entry == NULL)
149 return (0);
150 if (id)
151 *id = entry->id;
152 if (data)
153 *data = entry->data;
154 SPLAY_REMOVE(_tree, &t->tree, entry);
155 free(entry);
156 t->count -= 1;
157
158 return (1);
159 }
160
161 int
tree_root(struct tree * t,uint64_t * id,void ** data)162 tree_root(struct tree *t, uint64_t *id, void **data)
163 {
164 struct treeentry *entry;
165
166 entry = SPLAY_ROOT(&t->tree);
167 if (entry == NULL)
168 return (0);
169 if (id)
170 *id = entry->id;
171 if (data)
172 *data = entry->data;
173 return (1);
174 }
175
176 int
tree_iter(struct tree * t,void ** hdl,uint64_t * id,void ** data)177 tree_iter(struct tree *t, void **hdl, uint64_t *id, void **data)
178 {
179 struct treeentry *curr = *hdl;
180
181 if (curr == NULL)
182 curr = SPLAY_MIN(_tree, &t->tree);
183 else
184 curr = SPLAY_NEXT(_tree, &t->tree, curr);
185
186 if (curr) {
187 *hdl = curr;
188 if (id)
189 *id = curr->id;
190 if (data)
191 *data = curr->data;
192 return (1);
193 }
194
195 return (0);
196 }
197
198 int
tree_iterfrom(struct tree * t,void ** hdl,uint64_t k,uint64_t * id,void ** data)199 tree_iterfrom(struct tree *t, void **hdl, uint64_t k, uint64_t *id, void **data)
200 {
201 struct treeentry *curr = *hdl, key;
202
203 if (curr == NULL) {
204 if (k == 0)
205 curr = SPLAY_MIN(_tree, &t->tree);
206 else {
207 key.id = k;
208 curr = SPLAY_FIND(_tree, &t->tree, &key);
209 if (curr == NULL) {
210 SPLAY_INSERT(_tree, &t->tree, &key);
211 curr = SPLAY_NEXT(_tree, &t->tree, &key);
212 SPLAY_REMOVE(_tree, &t->tree, &key);
213 }
214 }
215 } else
216 curr = SPLAY_NEXT(_tree, &t->tree, curr);
217
218 if (curr) {
219 *hdl = curr;
220 if (id)
221 *id = curr->id;
222 if (data)
223 *data = curr->data;
224 return (1);
225 }
226
227 return (0);
228 }
229
230 void
tree_merge(struct tree * dst,struct tree * src)231 tree_merge(struct tree *dst, struct tree *src)
232 {
233 struct treeentry *entry;
234
235 while (!SPLAY_EMPTY(&src->tree)) {
236 entry = SPLAY_ROOT(&src->tree);
237 SPLAY_REMOVE(_tree, &src->tree, entry);
238 if (SPLAY_INSERT(_tree, &dst->tree, entry))
239 fatalx("tree_merge: duplicate");
240 }
241 dst->count += src->count;
242 src->count = 0;
243 }
244
245 static int
treeentry_cmp(struct treeentry * a,struct treeentry * b)246 treeentry_cmp(struct treeentry *a, struct treeentry *b)
247 {
248 if (a->id < b->id)
249 return (-1);
250 if (a->id > b->id)
251 return (1);
252 return (0);
253 }
254
255 SPLAY_GENERATE(_tree, treeentry, entry, treeentry_cmp);
256