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