libatalk/iniparser/dictionary.c

   1 /*-------------------------------------------------------------------------*/
   2 /**
   3    @file        dictionary.c
   4    @author      N. Devillard
   5    @date        Sep 2007
   6    @version     $Revision: 1.27 $
   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.27 2007-11-23 21:39:18 ndevilla Exp $
  17         $Revision: 1.27 $
  18 */
  19 /*---------------------------------------------------------------------------
  20                                                                 Includes
  21  ---------------------------------------------------------------------------*/
  22 #include <atalk/dictionary.h>
  23 #include <atalk/compat.h>
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <unistd.h>
  29
  30 /** Maximum value size for integers and doubles. */
  31 #define MAXVALSZ        1024
  32
  33 /** Minimal allocated number of entries in a dictionary */
  34 #define DICTMINSZ       128
  35
  36 /** Invalid key token */
  37 #define DICT_INVALID_KEY    ((char*)-1)
  38
  39 /*---------------------------------------------------------------------------
  40                                                         Private functions
  41  ---------------------------------------------------------------------------*/
  42
  43 #define MAXKEYSIZE 1024
  44 static char *makekey(const char *section, const char *entry)
  45 {
  46     static char buf[MAXKEYSIZE];
  47
  48     strlcpy(buf, section, MAXKEYSIZE);
  49     if (entry) {
  50         strlcat(buf, ":", MAXKEYSIZE);
  51         strlcat(buf, entry, MAXKEYSIZE);
  52     }
  53
  54     return buf;
  55 }
  56
  57 /* Doubles the allocated size associated to a pointer */
  58 /* 'size' is the current allocated size. */
  59 static void * mem_double(void * ptr, int size)
  60 {
  61     void * newptr ;
  62
  63     newptr = calloc(2*size, 1);
  64     if (newptr==NULL) {
  65         return NULL ;
  66     }
  67     memcpy(newptr, ptr, size);
  68     free(ptr);
  69     return newptr ;
  70 }
  71
  72 /*-------------------------------------------------------------------------*/
  73 /**
  74   @brief    Duplicate a string
  75   @param    s String to duplicate
  76   @return   Pointer to a newly allocated string, to be freed with free()
  77
  78   This is a replacement for strdup(). This implementation is provided
  79   for systems that do not have it.
  80  */
  81 /*--------------------------------------------------------------------------*/
  82 static char * xstrdup(char * s)
  83 {
  84     char * t ;
  85     if (!s)
  86         return NULL ;
  87     t = malloc(strlen(s)+1) ;
  88     if (t) {
  89         strcpy(t,s);
  90     }
  91     return t ;
  92 }
  93
  94 /*---------------------------------------------------------------------------
  95                                                         Function codes
  96  ---------------------------------------------------------------------------*/
  97 /*-------------------------------------------------------------------------*/
  98 /**
  99   @brief        Compute the hash key for a string.
 100   @param        key             Character string to use for key.
 101   @return       1 unsigned int on at least 32 bits.
 102
 103   This hash function has been taken from an Article in Dr Dobbs Journal.
 104   This is normally a collision-free function, distributing keys evenly.
 105   The key is stored anyway in the struct so that collision can be avoided
 106   by comparing the key itself in last resort.
 107  */
 108 /*--------------------------------------------------------------------------*/
 109 unsigned dictionary_hash(char * key)
 110 {
 111         int                     len ;
 112         unsigned        hash ;
 113         int                     i ;
 114
 115         len = strlen(key);
 116         for (hash=0, i=0 ; i<len ; i++) {
 117                 hash += (unsigned)key[i] ;
 118                 hash += (hash<<10);
 119                 hash ^= (hash>>6) ;
 120         }
 121         hash += (hash <<3);
 122         hash ^= (hash >>11);
 123         hash += (hash <<15);
 124         return hash ;
 125 }
 126
 127 /*-------------------------------------------------------------------------*/
 128 /**
 129   @brief        Create a new dictionary object.
 130   @param        size    Optional initial size of the dictionary.
 131   @return       1 newly allocated dictionary objet.
 132
 133   This function allocates a new dictionary object of given size and returns
 134   it. If you do not know in advance (roughly) the number of entries in the
 135   dictionary, give size=0.
 136  */
 137 /*--------------------------------------------------------------------------*/
 138 dictionary * dictionary_new(int size)
 139 {
 140         dictionary      *       d ;
 141
 142         /* If no size was specified, allocate space for DICTMINSZ */
 143         if (size<DICTMINSZ) size=DICTMINSZ ;
 144
 145         if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) {
 146                 return NULL;
 147         }
 148         d->size = size ;
 149         d->val  = (char **)calloc(size, sizeof(char*));
 150         d->key  = (char **)calloc(size, sizeof(char*));
 151         d->hash = (unsigned int *)calloc(size, sizeof(unsigned));
 152         return d ;
 153 }
 154
 155 /*-------------------------------------------------------------------------*/
 156 /**
 157   @brief        Delete a dictionary object
 158   @param        d       dictionary object to deallocate.
 159   @return       void
 160
 161   Deallocate a dictionary object and all memory associated to it.
 162  */
 163 /*--------------------------------------------------------------------------*/
 164 void dictionary_del(dictionary * d)
 165 {
 166         int             i ;
 167
 168         if (d==NULL) return ;
 169         for (i=0 ; i<d->size ; i++) {
 170                 if (d->key[i]!=NULL)
 171                         free(d->key[i]);
 172                 if (d->val[i]!=NULL)
 173                         free(d->val[i]);
 174         }
 175         free(d->val);
 176         free(d->key);
 177         free(d->hash);
 178         free(d);
 179         return ;
 180 }
 181
 182 /*-------------------------------------------------------------------------*/
 183 /**
 184   @brief        Get a value from a dictionary.
 185   @param        d               dictionary object to search.
 186   @param        key             Key to look for in the dictionary.
 187   @param    def     Default value to return if key not found.
 188   @return       1 pointer to internally allocated character string.
 189
 190   This function locates a key in a dictionary and returns a pointer to its
 191   value, or the passed 'def' pointer if no such key can be found in
 192   dictionary. The returned character pointer points to data internal to the
 193   dictionary object, you should not try to free it or modify it.
 194  */
 195 /*--------------------------------------------------------------------------*/
 196 char * dictionary_get(dictionary * d, char *section, char * key, char * def)
 197 {
 198         unsigned        hash ;
 199         int                     i ;
 200
 201         hash = dictionary_hash(makekey(section, key));
 202         for (i=0 ; i<d->size ; i++) {
 203         if (d->key[i]==NULL)
 204             continue ;
 205         /* Compare hash */
 206                 if (hash==d->hash[i]) {
 207             /* Compare string, to avoid hash collisions */
 208             if (!strcmp(makekey(section, key), d->key[i])) {
 209                                 return d->val[i] ;
 210                         }
 211                 }
 212         }
 213         return def ;
 214 }
 215
 216 /*-------------------------------------------------------------------------*/
 217 /**
 218   @brief    Set a value in a dictionary.
 219   @param    d       dictionary object to modify.
 220   @param    key     Key to modify or add.
 221   @param    val     Value to add.
 222   @return   int     0 if Ok, anything else otherwise
 223
 224   If the given key is found in the dictionary, the associated value is
 225   replaced by the provided one. If the key cannot be found in the
 226   dictionary, it is added to it.
 227
 228   It is Ok to provide a NULL value for val, but NULL values for the dictionary
 229   or the key are considered as errors: the function will return immediately
 230   in such a case.
 231
 232   Notice that if you dictionary_set a variable to NULL, a call to
 233   dictionary_get will return a NULL value: the variable will be found, and
 234   its value (NULL) is returned. In other words, setting the variable
 235   content to NULL is equivalent to deleting the variable from the
 236   dictionary. It is not possible (in this implementation) to have a key in
 237   the dictionary without value.
 238
 239   This function returns non-zero in case of failure.
 240  */
 241 /*--------------------------------------------------------------------------*/
 242 int dictionary_set(dictionary * d, char *section, char * key, char * val)
 243 {
 244         int                     i ;
 245         unsigned        hash ;
 246
 247         if (d==NULL || key==NULL) return -1 ;
 248
 249         /* Compute hash for this key */
 250         hash = dictionary_hash(makekey(section, key));
 251         /* Find if value is already in dictionary */
 252         if (d->n>0) {
 253                 for (i=0 ; i<d->size ; i++) {
 254             if (d->key[i]==NULL)
 255                 continue ;
 256                         if (hash==d->hash[i]) { /* Same hash value */
 257                                 if (!strcmp(makekey(section, key), d->key[i])) {         /* Same key */
 258                                         /* Found a value: modify and return */
 259                                         if (d->val[i]!=NULL)
 260                                                 free(d->val[i]);
 261                     d->val[i] = val ? xstrdup(val) : NULL ;
 262                     /* Value has been modified: return */
 263                                         return 0 ;
 264                                 }
 265                         }
 266                 }
 267         }
 268         /* Add a new value */
 269         /* See if dictionary needs to grow */
 270         if (d->n==d->size) {
 271
 272                 /* Reached maximum size: reallocate dictionary */
 273                 d->val  = (char **)mem_double(d->val,  d->size * sizeof(char*)) ;
 274                 d->key  = (char **)mem_double(d->key,  d->size * sizeof(char*)) ;
 275                 d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ;
 276         if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) {
 277             /* Cannot grow dictionary */
 278             return -1 ;
 279         }
 280                 /* Double size */
 281                 d->size *= 2 ;
 282         }
 283
 284     /* Insert key in the first empty slot */
 285     for (i=0 ; i<d->size ; i++) {
 286         if (d->key[i]==NULL) {
 287             /* Add key here */
 288             break ;
 289         }
 290     }
 291         /* Copy key */
 292         d->key[i]  = xstrdup(makekey(section, key));
 293     d->val[i]  = val ? xstrdup(val) : NULL ;
 294         d->hash[i] = hash;
 295         d->n ++ ;
 296         return 0 ;
 297 }
 298
 299 /*-------------------------------------------------------------------------*/
 300 /**
 301   @brief        Delete a key in a dictionary
 302   @param        d               dictionary object to modify.
 303   @param        key             Key to remove.
 304   @return   void
 305
 306   This function deletes a key in a dictionary. Nothing is done if the
 307   key cannot be found.
 308  */
 309 /*--------------------------------------------------------------------------*/
 310 void dictionary_unset(dictionary * d, char *section, char * key)
 311 {
 312         unsigned        hash ;
 313         int                     i ;
 314
 315         if (key == NULL) {
 316                 return;
 317         }
 318
 319         hash = dictionary_hash(makekey(section, key));
 320         for (i=0 ; i<d->size ; i++) {
 321         if (d->key[i]==NULL)
 322             continue ;
 323         /* Compare hash */
 324                 if (hash==d->hash[i]) {
 325             /* Compare string, to avoid hash collisions */
 326             if (!strcmp(makekey(section, key), d->key[i])) {
 327                 /* Found key */
 328                 break ;
 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->val[i]!=NULL) {
 339         free(d->val[i]);
 340         d->val[i] = 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",
 371                     d->key[i],
 372                     d->val[i] ? d->val[i] : "UNDEF");
 373         }
 374         }
 375         return ;
 376 }