1 /* $NetBSD: dict.c,v 1.9 2013/08/28 17:47:07 riastradh Exp $ */ 2 3 /* Copyright (c) 2010 The NetBSD Foundation, Inc. 4 * All rights reserved. 5 * 6 * This code is derived from software contributed to The NetBSD Foundation 7 * by Mateusz Kocielski. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. All advertising materials mentioning features or use of this software 18 * must display the following acknowledgement: 19 * This product includes software developed by the NetBSD 20 * Foundation, Inc. and its contributors. 21 * 4. Neither the name of The NetBSD Foundation nor the names of its 22 * contributors may be used to endorse or promote products derived 23 * from this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 26 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 27 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 29 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 35 * POSSIBILITY OF SUCH DAMAGE. 36 */ 37 #include <sys/cdefs.h> 38 __RCSID("$NetBSD: dict.c,v 1.9 2013/08/28 17:47:07 riastradh Exp $"); 39 40 #include <sys/queue.h> 41 42 #include <ctype.h> 43 #include <errno.h> 44 #include <stdbool.h> 45 #include <stdlib.h> 46 #include <string.h> 47 48 #include "dict.h" 49 #include "msg.h" 50 51 /** dictionary */ 52 LIST_HEAD(saslc__dict_t, saslc__dict_node_t); 53 54 /** dictionary linked list */ 55 typedef struct saslc__dict_node_t { 56 LIST_ENTRY(saslc__dict_node_t) nodes; 57 char * key; /* key */ 58 char * value; /* value */ 59 size_t value_len; /* value length */ 60 } saslc__dict_node_t; 61 62 /* 63 * XXX: If you add or change property keys, please readjust these 64 * values so that saslc__dict_hashval() remains collisionless. 65 * dist/test_hash/test_hash.c can help with this. 66 */ 67 /* no collisions: hsize=18 hinit=0 shift=2 */ 68 #define HASH_SIZE 18 69 #define HASH_INIT 0 70 #define HASH_SHIFT 2 71 72 /** 73 * @brief compute the hash value for a given string. 74 * @param cp string to hash. 75 * @return the hash value. 76 * 77 * NB: The defines HASH_INIT, HASH_SHIFT, and HASH_SIZE should be 78 * adjusted to make this collisionless for the keys used. 79 */ 80 static size_t 81 saslc__dict_hashval(const char *cp) 82 { 83 size_t hval; 84 85 hval = HASH_INIT; 86 for (/*EMPTY*/; *cp != '\0'; cp++) { 87 hval <<= HASH_SHIFT; 88 hval += (size_t)*cp; 89 } 90 return hval % HASH_SIZE; 91 } 92 93 /** 94 * @brief return the hash bucket corresponding to the key string 95 * @param dict dictionary to use 96 * @param cp key to use for lookup 97 * @return the hash bucket for the key. 98 */ 99 static saslc__dict_t * 100 saslc__dict_hash(saslc__dict_t *dict, const char *cp) 101 { 102 103 return dict + saslc__dict_hashval(cp); 104 } 105 106 /** 107 * @brief checks if the key is legal. 108 * @param key node key - must not be NULL 109 * @return true if key is legal, false otherwise 110 * 111 * Note: A legal key begins with an isalpha(3) character and is 112 * followed by isalnum(3) or '_' characters. 113 */ 114 static bool 115 saslc__dict_valid_key(const char *key) 116 { 117 118 /* key is not NULL */ 119 if (!isalpha((unsigned char)*key)) 120 return false; 121 122 key++; 123 while (isalnum((unsigned char)*key) || *key == '_') 124 key++; 125 126 return *key == '\0'; 127 } 128 129 /** 130 * @brief destroys and deallocates list node 131 * @param node list node 132 */ 133 static void 134 saslc__dict_list_node_destroy(saslc__dict_node_t *node) 135 { 136 137 free(node->key); 138 /* zero value, it may contain sensitive data */ 139 explicit_memset(node->value, 0, node->value_len); 140 free(node->value); 141 LIST_REMOVE(node, nodes); 142 free(node); 143 } 144 145 /** 146 * @brief gets node from the dictionary using key 147 * @param dict dictionary 148 * @param key node key 149 * @return pointer to node if key is in the dictionary, NULL otherwise 150 */ 151 static saslc__dict_node_t * 152 saslc__dict_get_node_by_key(saslc__dict_t *dict, const char *key) 153 { 154 saslc__dict_node_t *node; 155 156 dict = saslc__dict_hash(dict, key); 157 LIST_FOREACH(node, dict, nodes) { 158 if (strcmp(node->key, key) == 0) 159 return node; 160 } 161 return NULL; 162 } 163 164 /** 165 * @brief destroys and deallocates dictionary 166 * @param dict dictionary 167 */ 168 void 169 saslc__dict_destroy(saslc__dict_t *dict) 170 { 171 size_t i; 172 173 for (i = 0; i < HASH_SIZE; i++) { 174 while (!LIST_EMPTY(dict + i)) 175 saslc__dict_list_node_destroy(LIST_FIRST(dict + i)); 176 } 177 free(dict); 178 } 179 180 /** 181 * @brief removes node from the dictionary using key 182 * @param dict dictionary 183 * @param key node key 184 * @return DICT_OK on success, DICT_KEYNOTFOUND if node was not found (key 185 * does not exist in the dictionary. 186 */ 187 saslc__dict_result_t 188 saslc__dict_remove(saslc__dict_t *dict, const char *key) 189 { 190 saslc__dict_node_t *node; 191 192 node = saslc__dict_get_node_by_key(dict, key); 193 if (node == NULL) 194 return DICT_KEYNOTFOUND; 195 196 saslc__dict_list_node_destroy(node); 197 saslc__msg_dbg("%s: removed key %s", __func__, key); 198 return DICT_OK; 199 } 200 201 /** 202 * @brief gets node value from the dictionary using key 203 * @param dict dictionary 204 * @param key node key 205 * @return pointer to the value if key was found in the dictionary, NULL 206 * otherwise. 207 */ 208 const char * 209 saslc__dict_get(saslc__dict_t *dict, const char *key) 210 { 211 saslc__dict_node_t *node; 212 213 node = saslc__dict_get_node_by_key(dict, key); 214 return node != NULL ? node->value : NULL; 215 } 216 217 /** 218 * @brief gets length of node value from the dictionary using key 219 * @param dict dictionary 220 * @param key node key 221 * @return length of the node value, 0 is returned in case when key does not 222 * exist in the dictionary. 223 * 224 * XXX: currently unused. 225 */ 226 size_t 227 saslc__dict_get_len(saslc__dict_t *dict, const char *key) 228 { 229 saslc__dict_node_t *node; 230 231 node = saslc__dict_get_node_by_key(dict, key); 232 return node != NULL ? node->value_len : 0; 233 } 234 235 /** 236 * @brief creates and allocates dictionary 237 * @return pointer to new dictionary, NULL is returned on allocation failure 238 */ 239 saslc__dict_t * 240 saslc__dict_create(void) 241 { 242 saslc__dict_t *head; 243 int i; 244 245 head = calloc(HASH_SIZE, sizeof(*head)); 246 if (head == NULL) 247 return NULL; 248 249 for (i = 0; i < HASH_SIZE; i++) 250 LIST_INIT(head + i); 251 252 return head; 253 } 254 255 /** 256 * @brief inserts node into dictionary 257 * @param dict dictionary 258 * @param key node key 259 * @param val node value 260 * @return 261 * DICT_OK - on success, 262 * DICT_KEYINVALID - if node key is illegal, 263 * DICT_VALBAD - if node value is illegal, 264 * DICT_KEYEXISTS - if node with the same key already exists in the 265 * dictionary, 266 * DICT_NOMEM - on allocation failure 267 */ 268 saslc__dict_result_t 269 saslc__dict_insert(saslc__dict_t *dict, const char *key, const char *val) 270 { 271 char *d_key, *d_val; 272 saslc__dict_node_t *node; 273 274 if (key == NULL || saslc__dict_valid_key(key) == false) { 275 saslc__msg_dbg("%s: invalid key: %s", __func__, 276 key ? key : "<null>"); 277 return DICT_KEYINVALID; 278 } 279 if (val == NULL) { 280 saslc__msg_dbg("%s: NULL value for key %s", __func__, key); 281 return DICT_VALBAD; 282 } 283 /* check if key exists in dictionary */ 284 if (saslc__dict_get(dict, key) != NULL) { 285 saslc__msg_dbg("%s: key exists (ignoring): %s", __func__, key); 286 return DICT_KEYEXISTS; 287 } 288 if ((d_key = strdup(key)) == NULL) 289 goto nomem; 290 291 if ((d_val = strdup(val)) == NULL) { 292 free(d_key); 293 goto nomem; 294 } 295 if ((node = calloc(1, sizeof(*node))) == NULL) { 296 free(d_val); 297 free(d_key); 298 goto nomem; 299 } 300 dict = saslc__dict_hash(dict, key); 301 if (!LIST_EMPTY(dict)) 302 saslc__msg_dbg("%s: hash collision: '%s' vs '%s'\n", 303 __func__, key, LIST_FIRST(dict)->key); 304 305 saslc__msg_dbg("%s: %s=\"%s\"", __func__, d_key, d_val); 306 LIST_INSERT_HEAD(dict, node, nodes); 307 node->key = d_key; 308 node->value = d_val; 309 node->value_len = strlen(node->value); 310 return DICT_OK; 311 nomem: 312 saslc__msg_dbg("%s: %s", __func__, strerror(errno)); 313 return DICT_NOMEM; 314 } 315