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 */ 515