1 /* $OpenBSD: tree.c,v 1.6 2018/12/23 16:06:24 gilles 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/types.h> 20 #include <sys/tree.h> 21 22 #include <err.h> 23 #include <inttypes.h> 24 #include <stdlib.h> 25 #include <limits.h> 26 27 #include "tree.h" 28 29 struct treeentry { 30 SPLAY_ENTRY(treeentry) entry; 31 uint64_t id; 32 void *data; 33 }; 34 35 static int treeentry_cmp(struct treeentry *, struct treeentry *); 36 37 SPLAY_PROTOTYPE(_tree, treeentry, entry, treeentry_cmp); 38 39 int 40 tree_check(struct tree *t, uint64_t id) 41 { 42 struct treeentry key; 43 44 key.id = id; 45 return (SPLAY_FIND(_tree, &t->tree, &key) != NULL); 46 } 47 48 void * 49 tree_set(struct tree *t, uint64_t id, void *data) 50 { 51 struct treeentry *entry, key; 52 char *old; 53 54 key.id = id; 55 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) { 56 if ((entry = malloc(sizeof *entry)) == NULL) 57 err(1, "tree_set: malloc"); 58 entry->id = id; 59 SPLAY_INSERT(_tree, &t->tree, entry); 60 old = NULL; 61 t->count += 1; 62 } else 63 old = entry->data; 64 65 entry->data = data; 66 67 return (old); 68 } 69 70 void 71 tree_xset(struct tree *t, uint64_t id, void *data) 72 { 73 struct treeentry *entry; 74 75 if ((entry = malloc(sizeof *entry)) == NULL) 76 err(1, "tree_xset: malloc"); 77 entry->id = id; 78 entry->data = data; 79 if (SPLAY_INSERT(_tree, &t->tree, entry)) 80 errx(1, "tree_xset(%p, 0x%016"PRIx64 ")", t, id); 81 t->count += 1; 82 } 83 84 void * 85 tree_get(struct tree *t, uint64_t id) 86 { 87 struct treeentry key, *entry; 88 89 key.id = id; 90 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) 91 return (NULL); 92 93 return (entry->data); 94 } 95 96 void * 97 tree_xget(struct tree *t, uint64_t id) 98 { 99 struct treeentry key, *entry; 100 101 key.id = id; 102 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) 103 errx(1, "tree_get(%p, 0x%016"PRIx64 ")", t, id); 104 105 return (entry->data); 106 } 107 108 void * 109 tree_pop(struct tree *t, uint64_t id) 110 { 111 struct treeentry key, *entry; 112 void *data; 113 114 key.id = id; 115 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) 116 return (NULL); 117 118 data = entry->data; 119 SPLAY_REMOVE(_tree, &t->tree, entry); 120 free(entry); 121 t->count -= 1; 122 123 return (data); 124 } 125 126 void * 127 tree_xpop(struct tree *t, uint64_t id) 128 { 129 struct treeentry key, *entry; 130 void *data; 131 132 key.id = id; 133 if ((entry = SPLAY_FIND(_tree, &t->tree, &key)) == NULL) 134 errx(1, "tree_xpop(%p, 0x%016" PRIx64 ")", t, id); 135 136 data = entry->data; 137 SPLAY_REMOVE(_tree, &t->tree, entry); 138 free(entry); 139 t->count -= 1; 140 141 return (data); 142 } 143 144 int 145 tree_poproot(struct tree *t, uint64_t *id, void **data) 146 { 147 struct treeentry *entry; 148 149 entry = SPLAY_ROOT(&t->tree); 150 if (entry == NULL) 151 return (0); 152 if (id) 153 *id = entry->id; 154 if (data) 155 *data = entry->data; 156 SPLAY_REMOVE(_tree, &t->tree, entry); 157 free(entry); 158 t->count -= 1; 159 160 return (1); 161 } 162 163 int 164 tree_root(struct tree *t, uint64_t *id, void **data) 165 { 166 struct treeentry *entry; 167 168 entry = SPLAY_ROOT(&t->tree); 169 if (entry == NULL) 170 return (0); 171 if (id) 172 *id = entry->id; 173 if (data) 174 *data = entry->data; 175 return (1); 176 } 177 178 int 179 tree_iter(struct tree *t, void **hdl, uint64_t *id, void **data) 180 { 181 struct treeentry *curr = *hdl; 182 183 if (curr == NULL) 184 curr = SPLAY_MIN(_tree, &t->tree); 185 else 186 curr = SPLAY_NEXT(_tree, &t->tree, curr); 187 188 if (curr) { 189 *hdl = curr; 190 if (id) 191 *id = curr->id; 192 if (data) 193 *data = curr->data; 194 return (1); 195 } 196 197 return (0); 198 } 199 200 int 201 tree_iterfrom(struct tree *t, void **hdl, uint64_t k, uint64_t *id, void **data) 202 { 203 struct treeentry *curr = *hdl, key; 204 205 if (curr == NULL) { 206 if (k == 0) 207 curr = SPLAY_MIN(_tree, &t->tree); 208 else { 209 key.id = k; 210 curr = SPLAY_FIND(_tree, &t->tree, &key); 211 if (curr == NULL) { 212 SPLAY_INSERT(_tree, &t->tree, &key); 213 curr = SPLAY_NEXT(_tree, &t->tree, &key); 214 SPLAY_REMOVE(_tree, &t->tree, &key); 215 } 216 } 217 } else 218 curr = SPLAY_NEXT(_tree, &t->tree, curr); 219 220 if (curr) { 221 *hdl = curr; 222 if (id) 223 *id = curr->id; 224 if (data) 225 *data = curr->data; 226 return (1); 227 } 228 229 return (0); 230 } 231 232 void 233 tree_merge(struct tree *dst, struct tree *src) 234 { 235 struct treeentry *entry; 236 237 while (!SPLAY_EMPTY(&src->tree)) { 238 entry = SPLAY_ROOT(&src->tree); 239 SPLAY_REMOVE(_tree, &src->tree, entry); 240 if (SPLAY_INSERT(_tree, &dst->tree, entry)) 241 errx(1, "tree_merge: duplicate"); 242 } 243 dst->count += src->count; 244 src->count = 0; 245 } 246 247 static int 248 treeentry_cmp(struct treeentry *a, struct treeentry *b) 249 { 250 if (a->id < b->id) 251 return (-1); 252 if (a->id > b->id) 253 return (1); 254 return (0); 255 } 256 257 SPLAY_GENERATE(_tree, treeentry, entry, treeentry_cmp); 258