git.ozlabs.org Git - ccan/blob - ccan/ciniparser/dictionary.c

   1 /* Copyright (c) 2000-2007 by Nicolas Devillard.
   2  * Copyright (x) 2009 by Tim Post <tinkertim@gmail.com>
   3  * MIT License
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in
  13  * all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 /** @addtogroup ciniparser
  25  * @{
  26  */
  27 /**
  28  * @file dictionary.c
  29  * @author N. Devillard
  30  * @date Sep 2007
  31  * @version $Revision: 1.27 $
  32  * @brief Implements a dictionary for string variables.
  33  *
  34  * This module implements a simple dictionary object, i.e. a list
  35  * of string/string associations. This object is useful to store e.g.
  36  * information retrieved from a configuration file (ini files).
  37  */
  38
  39 #include "dictionary.h"
  40
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <string.h>
  44 #include <unistd.h>
  45
  46 /** Maximum value size for integers and doubles. */
  47 #define MAXVALSZ        1024
  48
  49 /** Minimal allocated number of entries in a dictionary */
  50 #define DICTMINSZ       128
  51
  52 /** Invalid key token */
  53 #define DICT_INVALID_KEY        ((char*)-1)
  54
  55 /**
  56  * @brief Double the allocated size associated to a pointer
  57  * @param size the current allocated size
  58  * @return re-allocated pointer on success, NULL on failure
  59  */
  60 static void *mem_double(void *ptr, int size)
  61 {
  62         void *newptr;
  63
  64         newptr = calloc(2 * size, 1);
  65         if (newptr == NULL) {
  66                 return NULL;
  67         }
  68         memcpy(newptr, ptr, size);
  69         free(ptr);
  70         return newptr;
  71 }
  72
  73 /* The remaining exposed functions are documented in dictionary.h */
  74
  75 unsigned dictionary_hash(char *key)
  76 {
  77         int len;
  78         unsigned hash;
  79         int i;
  80
  81         len = strlen(key);
  82         for (hash = 0, i = 0; i < len; i++) {
  83                 hash += (unsigned) key[i];
  84                 hash += (hash << 10);
  85                 hash ^= (hash >> 6);
  86         }
  87         hash += (hash << 3);
  88         hash ^= (hash >> 11);
  89         hash += (hash << 15);
  90         return hash;
  91 }
  92
  93 dictionary *dictionary_new(int size)
  94 {
  95         dictionary *d;
  96
  97         /* If no size was specified, allocate space for DICTMINSZ */
  98         if (size<DICTMINSZ) size=DICTMINSZ;
  99
 100         if (!(d = (dictionary *) calloc(1, sizeof(dictionary)))) {
 101                 return NULL;
 102         }
 103         d->size = size;
 104         d->val  = (char **) calloc(size, sizeof(char *));
 105         d->key  = (char **) calloc(size, sizeof(char *));
 106         d->hash = (unsigned int *) calloc(size, sizeof(unsigned));
 107         return d;
 108 }
 109
 110 void dictionary_del(dictionary *d)
 111 {
 112         int i;
 113
 114         if (d == NULL)
 115                 return;
 116         for (i = 0; i < d->size; i++) {
 117                 if (d->key[i] != NULL)
 118                         free(d->key[i]);
 119                 if (d->val[i] != NULL)
 120                         free(d->val[i]);
 121         }
 122         free(d->val);
 123         free(d->key);
 124         free(d->hash);
 125         free(d);
 126         return;
 127 }
 128
 129 char *dictionary_get(dictionary *d, char *key, char *def)
 130 {
 131         unsigned hash;
 132         int i;
 133
 134         hash = dictionary_hash(key);
 135         for (i=0; i < d->size; i++) {
 136                 if (d->key[i] == NULL)
 137                         continue;
 138                 /* Compare hash */
 139                 if (hash == d->hash[i]) {
 140                         /* Compare string, to avoid hash collisions */
 141                         if (!strcmp(key, d->key[i])) {
 142                                 return d->val[i];
 143                         }
 144                 }
 145         }
 146         return def;
 147 }
 148
 149 int dictionary_set(dictionary *d, char *key, char *val)
 150 {
 151         int i;
 152         unsigned hash;
 153
 154         if (d==NULL || key==NULL)
 155                 return -1;
 156
 157         /* Compute hash for this key */
 158         hash = dictionary_hash(key);
 159         /* Find if value is already in dictionary */
 160         if (d->n > 0) {
 161                 for (i = 0; i < d->size; i++) {
 162                         if (d->key[i] == NULL)
 163                                 continue;
 164                         /* Same hash value */
 165                         if (hash == d->hash[i]) {
 166                                 /* Same key */
 167                                 if (!strcmp(key, d->key[i])) {
 168                                         /* Found a value: modify and return */
 169                                         if (d->val[i] != NULL)
 170                                                 free(d->val[i]);
 171                                         d->val[i] = val ? strdup(val) : NULL;
 172                                         /* Value has been modified: return */
 173                                         return 0;
 174                                 }
 175                         }
 176                 }
 177         }
 178
 179         /* Add a new value
 180          * See if dictionary needs to grow */
 181         if (d->n == d->size) {
 182                 /* Reached maximum size: reallocate dictionary */
 183                 d->val  = (char **) mem_double(d->val, d->size * sizeof(char *));
 184                 d->key  = (char **) mem_double(d->key, d->size * sizeof(char *));
 185                 d->hash = (unsigned int *)
 186                         mem_double(d->hash, d->size * sizeof(unsigned));
 187                 if ((d->val == NULL) || (d->key == NULL) || (d->hash == NULL))
 188                         /* Cannot grow dictionary */
 189                         return -1;
 190                 /* Double size */
 191                 d->size *= 2;
 192         }
 193
 194         /* Insert key in the first empty slot */
 195         for (i = 0; i < d->size; i++) {
 196                 if (d->key[i] == NULL) {
 197                         /* Add key here */
 198                         break;
 199                 }
 200         }
 201         /* Copy key */
 202         d->key[i] = strdup(key);
 203         d->val[i] = val ? strdup(val) : NULL;
 204         d->hash[i] = hash;
 205         d->n ++;
 206         return 0;
 207 }
 208
 209 void dictionary_unset(dictionary *d, char *key)
 210 {
 211         unsigned hash;
 212         int i;
 213
 214         if (key == NULL)
 215                 return;
 216
 217         hash = dictionary_hash(key);
 218         for (i = 0; i < d->size; i++) {
 219                 if (d->key[i] == NULL)
 220                         continue;
 221                 /* Compare hash */
 222                 if (hash == d->hash[i]) {
 223                         /* Compare string, to avoid hash collisions */
 224                         if (!strcmp(key, d->key[i])) {
 225                                 /* Found key */
 226                                 break;
 227                         }
 228                 }
 229         }
 230         if (i >= d->size)
 231                 /* Key not found */
 232                 return;
 233
 234         free(d->key[i]);
 235         d->key[i] = NULL;
 236         if (d->val[i]!=NULL) {
 237                 free(d->val[i]);
 238                 d->val[i] = NULL;
 239         }
 240         d->hash[i] = 0;
 241         d->n --;
 242         return;
 243 }
 244
 245 void dictionary_dump(dictionary *d, FILE *out)
 246 {
 247         int i;
 248
 249         if (d == NULL || out == NULL)
 250                 return;
 251         if (d->n < 1) {
 252                 fprintf(out, "empty dictionary\n");
 253                 return;
 254         }
 255         for (i = 0; i < d->size; i++) {
 256                 if (d->key[i]) {
 257                         fprintf(out, "%20s\t[%s]\n",
 258                                 d->key[i],
 259                                 d->val[i] ? d->val[i] : "UNDEF");
 260                 }
 261         }
 262         return;
 263 }
 264
 265 /** @}
 266  */