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