1 /*-------------------------------------------------------------------------*/
2 /**
3 @file dictionary.c
4 @author N. Devillard
5 @date Sep 2007
6 @version $Revision: 1.27 $
7 @brief Implements a dictionary for string variables.
8
9 This module implements a simple dictionary object, i.e. a list
10 of string/string associations. This object is useful to store e.g.
11 informations retrieved from a configuration file (ini files).
12 */
13 /*--------------------------------------------------------------------------*/
14
15 /*
16 $Id: dictionary.c,v 1.27 2007-11-23 21:39:18 ndevilla Exp $
17 $Revision: 1.27 $
18 */
19 /*---------------------------------------------------------------------------
20 Includes
21 ---------------------------------------------------------------------------*/
22 #include "dictionary.h"
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <unistd.h>
28
29 /** Maximum value size for integers and doubles. */
30 #define MAXVALSZ 1024
31
32 /** Minimal allocated number of entries in a dictionary */
33 #define DICTMINSZ 128
34
35 /** Invalid key token */
36 #define DICT_INVALID_KEY ((char*)-1)
37
38 /*---------------------------------------------------------------------------
39 Private functions
40 ---------------------------------------------------------------------------*/
41
42 /* Doubles the allocated size associated to a pointer */
43 /* 'size' is the current allocated size. */
mem_double(void * ptr, int size)44 static void * mem_double(void * ptr, int size)
45 {
46 void * newptr ;
47
48 newptr = calloc(2*size, 1);
49 if (newptr==NULL) {
50 return NULL ;
51 }
52 memcpy(newptr, ptr, size);
53 free(ptr);
54 return newptr ;
55 }
56
57 /*-------------------------------------------------------------------------*/
58 /**
59 @brief Duplicate a string
60 @param s String to duplicate
61 @return Pointer to a newly allocated string, to be freed with free()
62
63 This is a replacement for strdup(). This implementation is provided
64 for systems that do not have it.
65 */
66 /*--------------------------------------------------------------------------*/
xstrdup(const char * s)67 static char * xstrdup(const char * s)
68 {
69 char * t ;
70 if (!s)
71 return NULL ;
72 t = malloc(strlen(s)+1) ;
73 if (t) {
74 strcpy(t,s);
75 }
76 return t ;
77 }
78
79 /*---------------------------------------------------------------------------
80 Function codes
81 ---------------------------------------------------------------------------*/
82 /*-------------------------------------------------------------------------*/
83 /**
84 @brief Compute the hash key for a string.
85 @param key Character string to use for key.
86 @return 1 unsigned int on at least 32 bits.
87
88 This hash function has been taken from an Article in Dr Dobbs Journal.
89 This is normally a collision-free function, distributing keys evenly.
90 The key is stored anyway in the struct so that collision can be avoided
91 by comparing the key itself in last resort.
92 */
93 /*--------------------------------------------------------------------------*/
dictionary_hash(const char * key)94 unsigned dictionary_hash(const char * key)
95 {
96 size_t len ;
97 unsigned hash ;
98 size_t i ;
99
100 len = strlen(key);
101 for (hash=0, i=0 ; i<len ; i++) {
102 hash += (unsigned)key[i] ;
103 hash += (hash<<10);
104 hash ^= (hash>>6) ;
105 }
106 hash += (hash <<3);
107 hash ^= (hash >>11);
108 hash += (hash <<15);
109 return hash ;
110 }
111
112 /*-------------------------------------------------------------------------*/
113 /**
114 @brief Create a new dictionary object.
115 @param size Optional initial size of the dictionary.
116 @return 1 newly allocated dictionary objet.
117
118 This function allocates a new dictionary object of given size and returns
119 it. If you do not know in advance (roughly) the number of entries in the
120 dictionary, give size=0.
121 */
122 /*--------------------------------------------------------------------------*/
dictionary_new(int size)123 dictionary * dictionary_new(int size)
124 {
125 dictionary * d ;
126
127 /* If no size was specified, allocate space for DICTMINSZ */
128 if (size<DICTMINSZ) size=DICTMINSZ ;
129
130 if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) {
131 return NULL;
132 }
133 d->size = size ;
134 d->val = (char **)calloc(size, sizeof(char*));
135 d->key = (char **)calloc(size, sizeof(char*));
136 d->hash = (unsigned int *)calloc(size, sizeof(unsigned));
137 return d ;
138 }
139
140 /*-------------------------------------------------------------------------*/
141 /**
142 @brief Delete a dictionary object
143 @param d dictionary object to deallocate.
144 @return void
145
146 Deallocate a dictionary object and all memory associated to it.
147 */
148 /*--------------------------------------------------------------------------*/
dictionary_del(dictionary * d)149 void dictionary_del(dictionary * d)
150 {
151 int i ;
152
153 if (d==NULL) return ;
154 for (i=0 ; i<d->size ; i++) {
155 if (d->key[i]!=NULL)
156 free(d->key[i]);
157 if (d->val[i]!=NULL)
158 free(d->val[i]);
159 }
160 free(d->val);
161 free(d->key);
162 free(d->hash);
163 free(d);
164 return ;
165 }
166
167 /*-------------------------------------------------------------------------*/
168 /**
169 @brief Get a value from a dictionary.
170 @param d dictionary object to search.
171 @param key Key to look for in the dictionary.
172 @param def Default value to return if key not found.
173 @return 1 pointer to internally allocated character string.
174
175 This function locates a key in a dictionary and returns a pointer to its
176 value, or the passed 'def' pointer if no such key can be found in
177 dictionary. The returned character pointer points to data internal to the
178 dictionary object, you should not try to free it or modify it.
179 */
180 /*--------------------------------------------------------------------------*/
dictionary_get(dictionary * d, char * key, char * def)181 char * dictionary_get(dictionary * d, char * key, char * def)
182 {
183 unsigned hash ;
184 int i ;
185
186 hash = dictionary_hash(key);
187 for (i=0 ; i<d->size ; i++) {
188 if (d->key[i]==NULL)
189 continue ;
190 /* Compare hash */
191 if (hash==d->hash[i]) {
192 /* Compare string, to avoid hash collisions */
193 if (!strcmp(key, d->key[i])) {
194 return d->val[i] ;
195 }
196 }
197 }
198 return def ;
199 }
200
201 /*-------------------------------------------------------------------------*/
202 /**
203 @brief Set a value in a dictionary.
204 @param d dictionary object to modify.
205 @param key Key to modify or add.
206 @param val Value to add.
207 @return int 0 if Ok, anything else otherwise
208
209 If the given key is found in the dictionary, the associated value is
210 replaced by the provided one. If the key cannot be found in the
211 dictionary, it is added to it.
212
213 It is Ok to provide a NULL value for val, but NULL values for the dictionary
214 or the key are considered as errors: the function will return immediately
215 in such a case.
216
217 Notice that if you dictionary_set a variable to NULL, a call to
218 dictionary_get will return a NULL value: the variable will be found, and
219 its value (NULL) is returned. In other words, setting the variable
220 content to NULL is equivalent to deleting the variable from the
221 dictionary. It is not possible (in this implementation) to have a key in
222 the dictionary without value.
223
224 This function returns non-zero in case of failure.
225 */
226 /*--------------------------------------------------------------------------*/
dictionary_set(dictionary * d, const char * key, const char * val)227 int dictionary_set(dictionary * d, const char * key, const char * val)
228 {
229 int i ;
230 unsigned hash ;
231
232 if (d==NULL || key==NULL) return -1 ;
233
234 /* Compute hash for this key */
235 hash = dictionary_hash(key) ;
236 /* Find if value is already in dictionary */
237 if (d->n>0) {
238 for (i=0 ; i<d->size ; i++) {
239 if (d->key[i]==NULL)
240 continue ;
241 if (hash==d->hash[i]) { /* Same hash value */
242 if (!strcmp(key, d->key[i])) { /* Same key */
243 /* Found a value: modify and return */
244 if (d->val[i]!=NULL)
245 free(d->val[i]);
246 d->val[i] = val ? xstrdup(val) : NULL ;
247 /* Value has been modified: return */
248 return 0 ;
249 }
250 }
251 }
252 }
253 /* Add a new value */
254 /* See if dictionary needs to grow */
255 if (d->n==d->size) {
256
257 /* Reached maximum size: reallocate dictionary */
258 d->val = (char **)mem_double(d->val, d->size * sizeof(char*)) ;
259 d->key = (char **)mem_double(d->key, d->size * sizeof(char*)) ;
260 d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ;
261 if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) {
262 /* Cannot grow dictionary */
263 return -1 ;
264 }
265 /* Double size */
266 d->size *= 2 ;
267 }
268
269 /* Insert key in the first empty slot */
270 for (i=0 ; i<d->size ; i++) {
271 if (d->key[i]==NULL) {
272 /* Add key here */
273 break ;
274 }
275 }
276 /* Copy key */
277 d->key[i] = xstrdup(key);
278 d->val[i] = val ? xstrdup(val) : NULL ;
279 d->hash[i] = hash;
280 d->n ++ ;
281 return 0 ;
282 }
283
284 /*-------------------------------------------------------------------------*/
285 /**
286 @brief Delete a key in a dictionary
287 @param d dictionary object to modify.
288 @param key Key to remove.
289 @return void
290
291 This function deletes a key in a dictionary. Nothing is done if the
292 key cannot be found.
293 */
294 /*--------------------------------------------------------------------------*/
dictionary_unset(dictionary * d, char * key)295 void dictionary_unset(dictionary * d, char * key)
296 {
297 unsigned hash ;
298 int i ;
299
300 if (key == NULL) {
301 return;
302 }
303
304 hash = dictionary_hash(key);
305 for (i=0 ; i<d->size ; i++) {
306 if (d->key[i]==NULL)
307 continue ;
308 /* Compare hash */
309 if (hash==d->hash[i]) {
310 /* Compare string, to avoid hash collisions */
311 if (!strcmp(key, d->key[i])) {
312 /* Found key */
313 break ;
314 }
315 }
316 }
317 if (i>=d->size)
318 /* Key not found */
319 return ;
320
321 free(d->key[i]);
322 d->key[i] = NULL ;
323 if (d->val[i]!=NULL) {
324 free(d->val[i]);
325 d->val[i] = NULL ;
326 }
327 d->hash[i] = 0 ;
328 d->n -- ;
329 return ;
330 }
331
332 /*-------------------------------------------------------------------------*/
333 /**
334 @brief Dump a dictionary to an opened file pointer.
335 @param d Dictionary to dump
336 @param f Opened file pointer.
337 @return void
338
339 Dumps a dictionary onto an opened file pointer. Key pairs are printed out
340 as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as
341 output file pointers.
342 */
343 /*--------------------------------------------------------------------------*/
dictionary_dump(dictionary * d, FILE * out)344 void dictionary_dump(dictionary * d, FILE * out)
345 {
346 int i ;
347
348 if (d==NULL || out==NULL) return ;
349 if (d->n<1) {
350 fprintf(out, "empty dictionary\n");
351 return ;
352 }
353 for (i=0 ; i<d->size ; i++) {
354 if (d->key[i]) {
355 fprintf(out, "%20s\t[%s]\n",
356 d->key[i],
357 d->val[i] ? d->val[i] : "UNDEF");
358 }
359 }
360 return ;
361 }
362
363
364 /* Test code */
365 #ifdef TESTDIC
366 #define NVALS 20000
main(int argc, char *argv[])367 int main(int argc, char *argv[])
368 {
369 dictionary * d ;
370 char * val ;
371 int i ;
372 char cval[90] ;
373
374 /* Allocate dictionary */
375 printf("allocating...\n");
376 d = dictionary_new(0);
377
378 /* Set values in dictionary */
379 printf("setting %d values...\n", NVALS);
380 for (i=0 ; i<NVALS ; i++) {
381 sprintf(cval, "%04d", i);
382 dictionary_set(d, cval, "salut");
383 }
384 printf("getting %d values...\n", NVALS);
385 for (i=0 ; i<NVALS ; i++) {
386 sprintf(cval, "%04d", i);
387 val = dictionary_get(d, cval, DICT_INVALID_KEY);
388 if (val==DICT_INVALID_KEY) {
389 printf("cannot get value for key [%s]\n", cval);
390 }
391 }
392 printf("unsetting %d values...\n", NVALS);
393 for (i=0 ; i<NVALS ; i++) {
394 sprintf(cval, "%04d", i);
395 dictionary_unset(d, cval);
396 }
397 if (d->n != 0) {
398 printf("error deleting values\n");
399 }
400 printf("deallocating...\n");
401 dictionary_del(d);
402 return 0 ;
403 }
404 #endif
405 /* vim: set ts=4 et sw=4 tw=75 */
406