git.maemo.org Git - mardrone/blob - mardrone/ARDrone_SDK_Version_1_8_20110726/ARDroneLib/Soft/Lib/iniparser3.0b/src/dictionary.c

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