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 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 * 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 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 * 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 * 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 * 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 * 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 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 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 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 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 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 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