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
saslc__dict_hashval(const char * cp)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 *
saslc__dict_hash(saslc__dict_t * dict,const char * cp)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
saslc__dict_valid_key(const char * key)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
saslc__dict_list_node_destroy(saslc__dict_node_t * node)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 *
saslc__dict_get_node_by_key(saslc__dict_t * dict,const char * key)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
saslc__dict_destroy(saslc__dict_t * dict)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
saslc__dict_remove(saslc__dict_t * dict,const char * key)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 *
saslc__dict_get(saslc__dict_t * dict,const char * key)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
saslc__dict_get_len(saslc__dict_t * dict,const char * key)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 *
saslc__dict_create(void)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
saslc__dict_insert(saslc__dict_t * dict,const char * key,const char * val)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