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