BGI/soap_src/soap_builder/dictionary.c

   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 #include "inistrlib.h"
  29
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <unistd.h>
  34
  35
  36 /** Maximum value size for integers and doubles. */
  37 #define MAXVALSZ        1024
  38
  39 /** Minimal allocated number of entries in a dictionary */
  40 #define DICTMINSZ       128
  41
  42 /** Invalid key token */
  43 #define DICT_INVALID_KEY    ((char*)-1)
  44
  45
  46 /*---------------------------------------------------------------------------
  47                                                         Private functions
  48  ---------------------------------------------------------------------------*/
  49
  50 /* Doubles the allocated size associated to a pointer */
  51 /* 'size' is the current allocated size. */
  52 static void * mem_double(void * ptr, int size)
  53 {
  54     void    *   newptr ;
  55
  56     newptr = calloc(2*size, 1);
  57     memcpy(newptr, ptr, size);
  58     free(ptr);
  59     return newptr ;
  60 }
  61
  62
  63 /*---------------------------------------------------------------------------
  64                                                         Function codes
  65  ---------------------------------------------------------------------------*/
  66
  67 /*-------------------------------------------------------------------------*/
  68 /**
  69   @brief        Compute the hash key for a string.
  70   @param        key             Character string to use for key.
  71   @return       1 unsigned int on at least 32 bits.
  72
  73   This hash function has been taken from an Article in Dr Dobbs Journal.
  74   This is normally a collision-free function, distributing keys evenly.
  75   The key is stored anyway in the struct so that collision can be avoided
  76   by comparing the key itself in last resort.
  77  */
  78 /*--------------------------------------------------------------------------*/
  79
  80 unsigned dictionary_hash(char * key)
  81 {
  82         int                     len ;
  83         unsigned        hash ;
  84         int                     i ;
  85
  86         len = (int)strlen(key);
  87         for (hash=0, i=0 ; i<len ; i++) {
  88                 hash += (unsigned)key[i] ;
  89                 hash += (hash<<10);
  90                 hash ^= (hash>>6) ;
  91         }
  92         hash += (hash <<3);
  93         hash ^= (hash >>11);
  94         hash += (hash <<15);
  95         return hash ;
  96 }
  97
  98
  99 /*-------------------------------------------------------------------------*/
 100 /**
 101   @brief        Create a new dictionary object.
 102   @param        size    Optional initial size of the dictionary.
 103   @return       1 newly allocated dictionary objet.
 104
 105   This function allocates a new dictionary object of given size and returns
 106   it. If you do not know in advance (roughly) the number of entries in the
 107   dictionary, give size=0.
 108  */
 109 /*--------------------------------------------------------------------------*/
 110
 111 dictionary * dictionary_new(int size, int caseSensitive)
 112 {
 113         dictionary      *       d ;
 114
 115         /* If no size was specified, allocate space for DICTMINSZ */
 116         if (size<DICTMINSZ) size=DICTMINSZ ;
 117
 118         d = calloc(1, sizeof(dictionary));
 119         d->size = size ;
 120         d->caseSensitive = caseSensitive;
 121         d->val  = calloc(size, sizeof(char*));
 122         d->key  = calloc(size, sizeof(char*));
 123         d->hash = 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 ? inistrdup(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  = mem_double(d->val,  d->size * sizeof(char*)) ;
 322                 d->key  = mem_double(d->key,  d->size * sizeof(char*)) ;
 323                 d->hash = 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]  = inistrdup(key);
 338     d->val[i]  = val ? inistrdup(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         hash = dictionary_hash(key);
 361         for (i=0 ; i<d->size ; i++) {
 362         if (d->key[i]==NULL)
 363             continue ;
 364         /* Compare hash */
 365                 if (hash==d->hash[i]) {
 366             /* Compare string, to avoid hash collisions */
 367             if (!strcmp(key, d->key[i])) {
 368                 /* Found key */
 369                 break ;
 370                         }
 371                 }
 372         }
 373     if (i>=d->size)
 374         /* Key not found */
 375         return ;
 376
 377     free(d->key[i]);
 378     d->key[i] = NULL ;
 379     if (d->val[i]!=NULL) {
 380         free(d->val[i]);
 381         d->val[i] = NULL ;
 382     }
 383     d->hash[i] = 0 ;
 384     d->n -- ;
 385     return ;
 386 }
 387
 388
 389 /*-------------------------------------------------------------------------*/
 390 /**
 391   @brief        Set a key in a dictionary, providing an int.
 392   @param        d               Dictionary to update.
 393   @param        key             Key to modify or add
 394   @param        val             Integer value to store (will be stored as a string).
 395   @return       void
 396
 397   This helper function calls dictionary_set() with the provided integer
 398   converted to a string using %d.
 399  */
 400 /*--------------------------------------------------------------------------*/
 401
 402
 403 void dictionary_setint(dictionary * d, char * key, int val)
 404 {
 405         char    sval[MAXVALSZ];
 406         sprintf(sval, "%d", val);
 407         dictionary_set(d, key, sval);
 408 }
 409
 410
 411 /*-------------------------------------------------------------------------*/
 412 /**
 413   @brief        Set a key in a dictionary, providing a double.
 414   @param        d               Dictionary to update.
 415   @param        key             Key to modify or add
 416   @param        val             Double value to store (will be stored as a string).
 417   @return       void
 418
 419   This helper function calls dictionary_set() with the provided double
 420   converted to a string using %g.
 421  */
 422 /*--------------------------------------------------------------------------*/
 423
 424
 425 void dictionary_setdouble(dictionary * d, char * key, double val)
 426 {
 427         char    sval[MAXVALSZ];
 428         sprintf(sval, "%g", val);
 429         dictionary_set(d, key, sval);
 430 }
 431
 432
 433
 434 /*-------------------------------------------------------------------------*/
 435 /**
 436   @brief        Dump a dictionary to an opened file pointer.
 437   @param        d       Dictionary to dump
 438   @param        f       Opened file pointer.
 439   @return       void
 440
 441   Dumps a dictionary onto an opened file pointer. Key pairs are printed out
 442   as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as
 443   output file pointers.
 444  */
 445 /*--------------------------------------------------------------------------*/
 446
 447 void dictionary_dump(dictionary * d, FILE * out)
 448 {
 449         int             i ;
 450
 451         if (d==NULL || out==NULL) return ;
 452         if (d->n<1) {
 453                 fprintf(out, "empty dictionary\n");
 454                 return ;
 455         }
 456         for (i=0 ; i<d->size ; i++) {
 457         if (d->key[i]) {
 458             fprintf(out, "%20s\t[%s]\n",
 459                     d->key[i],
 460                     d->val[i] ? d->val[i] : "UNDEF");
 461         }
 462         }
 463         return ;
 464 }
 465
 466
 467
 468 /* Example code */
 469 #ifdef TESTDIC
 470 #define NVALS 20000
 471 int main(int argc, char *argv[])
 472 {
 473         dictionary      *       d ;
 474         char    *       val ;
 475         int                     i ;
 476         char            cval[90] ;
 477
 478         /* allocate blackboard */
 479         printf("allocating...\n");
 480         d = dictionary_new(0);
 481
 482         /* Set values in blackboard */
 483         printf("setting %d values...\n", NVALS);
 484         for (i=0 ; i<NVALS ; i++) {
 485                 sprintf(cval, "%04d", i);
 486                 dictionary_set(d, cval, "salut");
 487         }
 488         printf("getting %d values...\n", NVALS);
 489         for (i=0 ; i<NVALS ; i++) {
 490                 sprintf(cval, "%04d", i);
 491                 val = dictionary_get(d, cval, DICT_INVALID_KEY);
 492                 if (val==DICT_INVALID_KEY) {
 493                         printf("cannot get value for key [%s]\n", cval);
 494                 }
 495         }
 496     printf("unsetting %d values...\n", NVALS);
 497         for (i=0 ; i<NVALS ; i++) {
 498                 sprintf(cval, "%04d", i);
 499                 dictionary_unset(d, cval);
 500         }
 501     if (d->n != 0) {
 502         printf("error deleting values\n");
 503     }
 504
 505         printf("deallocating...\n");
 506         dictionary_del(d);
 507         return 0 ;
 508 }
 509 #endif
 510 /* vim: set ts=4 et sw=4 tw=75 */