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