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