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