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