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