source3/iniparser/src/dictionary.c

   1
   2 /*-------------------------------------------------------------------------*/
   3 /**
   4    @file        dictionary.c
   5    @author      N. Devillard
   6    @date        Aug 2000
   7    @version     $Revision: 1.25 $
   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.25 2007-05-27 13:03:43 ndevilla Exp $
  18         $Author: ndevilla $
  19         $Date: 2007-05-27 13:03:43 $
  20         $Revision: 1.25 $
  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. */
  51 static 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
  79 unsigned 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
 110 dictionary * 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
 138 void 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 /*--------------------------------------------------------------------------*/
 172 char * 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 /*--------------------------------------------------------------------------*/
 204 char 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 /*--------------------------------------------------------------------------*/
 229 int 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 /*--------------------------------------------------------------------------*/
 253 double 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
 290 void 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 /*--------------------------------------------------------------------------*/
 355 void 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
 407 void 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
 429 void 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
 451 void 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
 475 int 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 */