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