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