source: trunk-3.0/source/iniparser/src/dictionary.c@ 101

Last change on this file since 101 was 1, checked in by Paul Smedley, 18 years ago

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