00001 00002 /*-------------------------------------------------------------------------*/ 00003 /** 00004 @file dictionary.c 00005 @author N. Devillard 00006 @date Aug 2000 00007 @version $Revision: 1.23 $ 00008 @brief Implements a dictionary for string variables. 00009 00010 This module implements a simple dictionary object, i.e. a list 00011 of string/string associations. This object is useful to store e.g. 00012 informations retrieved from a configuration file (ini files). 00013 */ 00014 /*--------------------------------------------------------------------------*/ 00015 00016 /* 00017 $Id: dictionary.c,v 1.23 2002/06/17 09:30:46 ndevilla Exp $ 00018 $Author: ndevilla $ 00019 $Date: 2002/06/17 09:30:46 $ 00020 $Revision: 1.23 $ 00021 */ 00022 00023 /*--------------------------------------------------------------------------- 00024 Includes 00025 ---------------------------------------------------------------------------*/ 00026 00027 #include "dictionary.h" 00028 00029 #include <stdio.h> 00030 #include <stdlib.h> 00031 #include <string.h> 00032 #include <unistd.h> 00033 00034 00035 /** Maximum value size for integers and doubles. */ 00036 #define MAXVALSZ 1024 00037 00038 /** Minimal allocated number of entries in a dictionary */ 00039 #define DICTMINSZ 128 00040 00041 /** Invalid key token */ 00042 #define DICT_INVALID_KEY ((char*)-1) 00043 00044 00045 /*--------------------------------------------------------------------------- 00046 Private functions 00047 ---------------------------------------------------------------------------*/ 00048 00049 /* Doubles the allocated size associated to a pointer */ 00050 /* 'size' is the current allocated size. */ 00051 static void * mem_double(void * ptr, int size) 00052 { 00053 void * newptr ; 00054 00055 newptr = calloc(2*size, 1); 00056 memcpy(newptr, ptr, size); 00057 free(ptr); 00058 return newptr ; 00059 } 00060 00061 00062 /*--------------------------------------------------------------------------- 00063 Function codes 00064 ---------------------------------------------------------------------------*/ 00065 00066 /*-------------------------------------------------------------------------*/ 00067 /** 00068 @brief Compute the hash key for a string. 00069 @param key Character string to use for key. 00070 @return 1 unsigned int on at least 32 bits. 00071 00072 This hash function has been taken from an Article in Dr Dobbs Journal. 00073 This is normally a collision-free function, distributing keys evenly. 00074 The key is stored anyway in the struct so that collision can be avoided 00075 by comparing the key itself in last resort. 00076 */ 00077 /*--------------------------------------------------------------------------*/ 00078 00079 unsigned dictionary_hash(char * key) 00080 { 00081 int len ; 00082 unsigned hash ; 00083 int i ; 00084 00085 len = strlen(key); 00086 for (hash=0, i=0 ; i<len ; i++) { 00087 hash += (unsigned)key[i] ; 00088 hash += (hash<<10); 00089 hash ^= (hash>>6) ; 00090 } 00091 hash += (hash <<3); 00092 hash ^= (hash >>11); 00093 hash += (hash <<15); 00094 return hash ; 00095 } 00096 00097 00098 /*-------------------------------------------------------------------------*/ 00099 /** 00100 @brief Create a new dictionary object. 00101 @param size Optional initial size of the dictionary. 00102 @return 1 newly allocated dictionary objet. 00103 00104 This function allocates a new dictionary object of given size and returns 00105 it. If you do not know in advance (roughly) the number of entries in the 00106 dictionary, give size=0. 00107 */ 00108 /*--------------------------------------------------------------------------*/ 00109 00110 dictionary * dictionary_new(int size) 00111 { 00112 dictionary * d ; 00113 00114 /* If no size was specified, allocate space for DICTMINSZ */ 00115 if (size<DICTMINSZ) size=DICTMINSZ ; 00116 00117 if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) { 00118 return NULL; 00119 } 00120 d->size = size ; 00121 d->val = (char **)calloc(size, sizeof(char*)); 00122 d->key = (char **)calloc(size, sizeof(char*)); 00123 d->hash = (unsigned int *)calloc(size, sizeof(unsigned)); 00124 return d ; 00125 } 00126 00127 00128 /*-------------------------------------------------------------------------*/ 00129 /** 00130 @brief Delete a dictionary object 00131 @param d dictionary object to deallocate. 00132 @return void 00133 00134 Deallocate a dictionary object and all memory associated to it. 00135 */ 00136 /*--------------------------------------------------------------------------*/ 00137 00138 void dictionary_del(dictionary * d) 00139 { 00140 int i ; 00141 00142 if (d==NULL) return ; 00143 for (i=0 ; i<d->size ; i++) { 00144 if (d->key[i]!=NULL) 00145 free(d->key[i]); 00146 if (d->val[i]!=NULL) 00147 free(d->val[i]); 00148 } 00149 free(d->val); 00150 free(d->key); 00151 free(d->hash); 00152 free(d); 00153 return ; 00154 } 00155 00156 00157 00158 /*-------------------------------------------------------------------------*/ 00159 /** 00160 @brief Get a value from a dictionary. 00161 @param d dictionary object to search. 00162 @param key Key to look for in the dictionary. 00163 @param def Default value to return if key not found. 00164 @return 1 pointer to internally allocated character string. 00165 00166 This function locates a key in a dictionary and returns a pointer to its 00167 value, or the passed 'def' pointer if no such key can be found in 00168 dictionary. The returned character pointer points to data internal to the 00169 dictionary object, you should not try to free it or modify it. 00170 */ 00171 /*--------------------------------------------------------------------------*/ 00172 char * dictionary_get(dictionary * d, char * key, char * def) 00173 { 00174 unsigned hash ; 00175 int i ; 00176 00177 hash = dictionary_hash(key); 00178 for (i=0 ; i<d->size ; i++) { 00179 if (d->key==NULL) 00180 continue ; 00181 /* Compare hash */ 00182 if (hash==d->hash[i]) { 00183 /* Compare string, to avoid hash collisions */ 00184 if (!strcmp(key, d->key[i])) { 00185 return d->val[i] ; 00186 } 00187 } 00188 } 00189 return def ; 00190 } 00191 00192 /*-------------------------------------------------------------------------*/ 00193 /** 00194 @brief Get a value from a dictionary, as a char. 00195 @param d dictionary object to search. 00196 @param key Key to look for in the dictionary. 00197 @param def Default value for the key if not found. 00198 @return char 00199 00200 This function locates a key in a dictionary using dictionary_get, 00201 and returns the first char of the found string. 00202 */ 00203 /*--------------------------------------------------------------------------*/ 00204 char dictionary_getchar(dictionary * d, char * key, char def) 00205 { 00206 char * v ; 00207 00208 if ((v=dictionary_get(d,key,DICT_INVALID_KEY))==DICT_INVALID_KEY) { 00209 return def ; 00210 } else { 00211 return v[0] ; 00212 } 00213 } 00214 00215 00216 /*-------------------------------------------------------------------------*/ 00217 /** 00218 @brief Get a value from a dictionary, as an int. 00219 @param d dictionary object to search. 00220 @param key Key to look for in the dictionary. 00221 @param def Default value for the key if not found. 00222 @return int 00223 00224 This function locates a key in a dictionary using dictionary_get, 00225 and applies atoi on it to return an int. If the value cannot be found 00226 in the dictionary, the default is returned. 00227 */ 00228 /*--------------------------------------------------------------------------*/ 00229 int dictionary_getint(dictionary * d, char * key, int def) 00230 { 00231 char * v ; 00232 00233 if ((v=dictionary_get(d,key,DICT_INVALID_KEY))==DICT_INVALID_KEY) { 00234 return def ; 00235 } else { 00236 return atoi(v); 00237 } 00238 } 00239 00240 /*-------------------------------------------------------------------------*/ 00241 /** 00242 @brief Get a value from a dictionary, as a double. 00243 @param d dictionary object to search. 00244 @param key Key to look for in the dictionary. 00245 @param def Default value for the key if not found. 00246 @return double 00247 00248 This function locates a key in a dictionary using dictionary_get, 00249 and applies atof on it to return a double. If the value cannot be found 00250 in the dictionary, the default is returned. 00251 */ 00252 /*--------------------------------------------------------------------------*/ 00253 double dictionary_getdouble(dictionary * d, char * key, double def) 00254 { 00255 char * v ; 00256 00257 if ((v=dictionary_get(d,key,DICT_INVALID_KEY))==DICT_INVALID_KEY) { 00258 return def ; 00259 } else { 00260 return atof(v); 00261 } 00262 } 00263 00264 00265 /*-------------------------------------------------------------------------*/ 00266 /** 00267 @brief Set a value in a dictionary. 00268 @param d dictionary object to modify. 00269 @param key Key to modify or add. 00270 @param val Value to add. 00271 @return void 00272 00273 If the given key is found in the dictionary, the associated value is 00274 replaced by the provided one. If the key cannot be found in the 00275 dictionary, it is added to it. 00276 00277 It is Ok to provide a NULL value for val, but NULL values for the dictionary 00278 or the key are considered as errors: the function will return immediately 00279 in such a case. 00280 00281 Notice that if you dictionary_set a variable to NULL, a call to 00282 dictionary_get will return a NULL value: the variable will be found, and 00283 its value (NULL) is returned. In other words, setting the variable 00284 content to NULL is equivalent to deleting the variable from the 00285 dictionary. It is not possible (in this implementation) to have a key in 00286 the dictionary without value. 00287 */ 00288 /*--------------------------------------------------------------------------*/ 00289 00290 void dictionary_set(dictionary * d, char * key, char * val) 00291 { 00292 int i ; 00293 unsigned hash ; 00294 00295 if (d==NULL || key==NULL) return ; 00296 00297 /* Compute hash for this key */ 00298 hash = dictionary_hash(key) ; 00299 /* Find if value is already in blackboard */ 00300 if (d->n>0) { 00301 for (i=0 ; i<d->size ; i++) { 00302 if (d->key[i]==NULL) 00303 continue ; 00304 if (hash==d->hash[i]) { /* Same hash value */ 00305 if (!strcmp(key, d->key[i])) { /* Same key */ 00306 /* Found a value: modify and return */ 00307 if (d->val[i]!=NULL) 00308 free(d->val[i]); 00309 d->val[i] = val ? strdup(val) : NULL ; 00310 /* Value has been modified: return */ 00311 return ; 00312 } 00313 } 00314 } 00315 } 00316 /* Add a new value */ 00317 /* See if dictionary needs to grow */ 00318 if (d->n==d->size) { 00319 00320 /* Reached maximum size: reallocate blackboard */ 00321 d->val = (char **)mem_double(d->val, d->size * sizeof(char*)) ; 00322 d->key = (char **)mem_double(d->key, d->size * sizeof(char*)) ; 00323 d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ; 00324 00325 /* Double size */ 00326 d->size *= 2 ; 00327 } 00328 00329 /* Insert key in the first empty slot */ 00330 for (i=0 ; i<d->size ; i++) { 00331 if (d->key[i]==NULL) { 00332 /* Add key here */ 00333 break ; 00334 } 00335 } 00336 /* Copy key */ 00337 d->key[i] = strdup(key); 00338 d->val[i] = val ? strdup(val) : NULL ; 00339 d->hash[i] = hash; 00340 d->n ++ ; 00341 return ; 00342 } 00343 00344 /*-------------------------------------------------------------------------*/ 00345 /** 00346 @brief Delete a key in a dictionary 00347 @param d dictionary object to modify. 00348 @param key Key to remove. 00349 @return void 00350 00351 This function deletes a key in a dictionary. Nothing is done if the 00352 key cannot be found. 00353 */ 00354 /*--------------------------------------------------------------------------*/ 00355 void dictionary_unset(dictionary * d, char * key) 00356 { 00357 unsigned hash ; 00358 int i ; 00359 00360 if (key == NULL) { 00361 return; 00362 } 00363 00364 hash = dictionary_hash(key); 00365 for (i=0 ; i<d->size ; i++) { 00366 if (d->key[i]==NULL) 00367 continue ; 00368 /* Compare hash */ 00369 if (hash==d->hash[i]) { 00370 /* Compare string, to avoid hash collisions */ 00371 if (!strcmp(key, d->key[i])) { 00372 /* Found key */ 00373 break ; 00374 } 00375 } 00376 } 00377 if (i>=d->size) 00378 /* Key not found */ 00379 return ; 00380 00381 free(d->key[i]); 00382 d->key[i] = NULL ; 00383 if (d->val[i]!=NULL) { 00384 free(d->val[i]); 00385 d->val[i] = NULL ; 00386 } 00387 d->hash[i] = 0 ; 00388 d->n -- ; 00389 return ; 00390 } 00391 00392 00393 /*-------------------------------------------------------------------------*/ 00394 /** 00395 @brief Set a key in a dictionary, providing an int. 00396 @param d Dictionary to update. 00397 @param key Key to modify or add 00398 @param val Integer value to store (will be stored as a string). 00399 @return void 00400 00401 This helper function calls dictionary_set() with the provided integer 00402 converted to a string using %d. 00403 */ 00404 /*--------------------------------------------------------------------------*/ 00405 00406 00407 void dictionary_setint(dictionary * d, char * key, int val) 00408 { 00409 char sval[MAXVALSZ]; 00410 sprintf(sval, "%d", val); 00411 dictionary_set(d, key, sval); 00412 } 00413 00414 00415 /*-------------------------------------------------------------------------*/ 00416 /** 00417 @brief Set a key in a dictionary, providing a double. 00418 @param d Dictionary to update. 00419 @param key Key to modify or add 00420 @param val Double value to store (will be stored as a string). 00421 @return void 00422 00423 This helper function calls dictionary_set() with the provided double 00424 converted to a string using %g. 00425 */ 00426 /*--------------------------------------------------------------------------*/ 00427 00428 00429 void dictionary_setdouble(dictionary * d, char * key, double val) 00430 { 00431 char sval[MAXVALSZ]; 00432 sprintf(sval, "%g", val); 00433 dictionary_set(d, key, sval); 00434 } 00435 00436 00437 00438 /*-------------------------------------------------------------------------*/ 00439 /** 00440 @brief Dump a dictionary to an opened file pointer. 00441 @param d Dictionary to dump 00442 @param f Opened file pointer. 00443 @return void 00444 00445 Dumps a dictionary onto an opened file pointer. Key pairs are printed out 00446 as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as 00447 output file pointers. 00448 */ 00449 /*--------------------------------------------------------------------------*/ 00450 00451 void dictionary_dump(dictionary * d, FILE * out) 00452 { 00453 int i ; 00454 00455 if (d==NULL || out==NULL) return ; 00456 if (d->n<1) { 00457 fprintf(out, "empty dictionary\n"); 00458 return ; 00459 } 00460 for (i=0 ; i<d->size ; i++) { 00461 if (d->key[i]) { 00462 fprintf(out, "%20s\t[%s]\n", 00463 d->key[i], 00464 d->val[i] ? d->val[i] : "UNDEF"); 00465 } 00466 } 00467 return ; 00468 } 00469 00470 00471 00472 /* Example code */ 00473 #ifdef TESTDIC 00474 #define NVALS 20000 00475 int main(int argc, char *argv[]) 00476 { 00477 dictionary * d ; 00478 char * val ; 00479 int i ; 00480 char cval[90] ; 00481 00482 /* allocate blackboard */ 00483 printf("allocating...\n"); 00484 d = dictionary_new(0); 00485 00486 /* Set values in blackboard */ 00487 printf("setting %d values...\n", NVALS); 00488 for (i=0 ; i<NVALS ; i++) { 00489 sprintf(cval, "%04d", i); 00490 dictionary_set(d, cval, "salut"); 00491 } 00492 printf("getting %d values...\n", NVALS); 00493 for (i=0 ; i<NVALS ; i++) { 00494 sprintf(cval, "%04d", i); 00495 val = dictionary_get(d, cval, DICT_INVALID_KEY); 00496 if (val==DICT_INVALID_KEY) { 00497 printf("cannot get value for key [%s]\n", cval); 00498 } 00499 } 00500 printf("unsetting %d values...\n", NVALS); 00501 for (i=0 ; i<NVALS ; i++) { 00502 sprintf(cval, "%04d", i); 00503 dictionary_unset(d, cval); 00504 } 00505 if (d->n != 0) { 00506 printf("error deleting values\n"); 00507 } 00508 00509 printf("deallocating...\n"); 00510 dictionary_del(d); 00511 return 0 ; 00512 } 00513 #endif 00514 /* vim: set ts=4 et sw=4 tw=75 */