aboutsummaryrefslogtreecommitdiff
path: root/lib/dictionary.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/dictionary.c')
-rw-r--r--lib/dictionary.c428
1 files changed, 203 insertions, 225 deletions
diff --git a/lib/dictionary.c b/lib/dictionary.c
index f4b7468..85dfdc0 100644
--- a/lib/dictionary.c
+++ b/lib/dictionary.c
@@ -1,10 +1,8 @@
/*-------------------------------------------------------------------------*/
/**
- @file dictionary.c
- @author N. Devillard
- @date Sep 2007
- @version $Revision: 1.27 $
- @brief Implements a dictionary for string variables.
+ @file dictionary.c
+ @author N. Devillard
+ @brief Implements a dictionary for string variables.
This module implements a simple dictionary object, i.e. a list
of string/string associations. This object is useful to store e.g.
@@ -12,48 +10,22 @@
*/
/*--------------------------------------------------------------------------*/
-/*
- $Id: dictionary.c,v 1.27 2007-11-23 21:39:18 ndevilla Exp $
- $Revision: 1.27 $
-*/
/*---------------------------------------------------------------------------
- Includes
+ Includes
---------------------------------------------------------------------------*/
#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
-#include <unistd.h>
-
-/** Maximum value size for integers and doubles. */
-#define MAXVALSZ 1024
/** Minimal allocated number of entries in a dictionary */
-#define DICTMINSZ 128
-
-/** Invalid key token */
-#define DICT_INVALID_KEY ((char*)-1)
+#define DICTMINSZ 128
/*---------------------------------------------------------------------------
- Private functions
+ Private functions
---------------------------------------------------------------------------*/
-/* Doubles the allocated size associated to a pointer */
-/* 'size' is the current allocated size. */
-static void * mem_double(void * ptr, int size)
-{
- void * newptr ;
-
- newptr = calloc(2*size, 1);
- if (newptr==NULL) {
- return NULL ;
- }
- memcpy(newptr, ptr, size);
- free(ptr);
- return newptr ;
-}
-
/*-------------------------------------------------------------------------*/
/**
@brief Duplicate a string
@@ -64,26 +36,71 @@ static void * mem_double(void * ptr, int size)
for systems that do not have it.
*/
/*--------------------------------------------------------------------------*/
-static char * xstrdup(char * s)
+static char * xstrdup(const char * s)
{
char * t ;
+ size_t len ;
if (!s)
return NULL ;
- t = malloc(strlen(s)+1) ;
+
+ len = strlen(s) + 1 ;
+ t = (char*) malloc(len) ;
if (t) {
- strcpy(t,s);
+ memcpy(t, s, len) ;
}
return t ;
}
+/*-------------------------------------------------------------------------*/
+/**
+ @brief Double the size of the dictionary
+ @param d Dictionary to grow
+ @return This function returns non-zero in case of failure
+ */
+/*--------------------------------------------------------------------------*/
+static int dictionary_grow(dictionary * d)
+{
+ char ** new_val ;
+ char ** new_key ;
+ unsigned * new_hash ;
+
+ new_val = (char**) calloc(d->size * 2, sizeof *d->val);
+ new_key = (char**) calloc(d->size * 2, sizeof *d->key);
+ new_hash = (unsigned*) calloc(d->size * 2, sizeof *d->hash);
+ if (!new_val || !new_key || !new_hash) {
+ /* An allocation failed, leave the dictionary unchanged */
+ if (new_val)
+ free(new_val);
+ if (new_key)
+ free(new_key);
+ if (new_hash)
+ free(new_hash);
+ return -1 ;
+ }
+ /* Initialize the newly allocated space */
+ memcpy(new_val, d->val, d->size * sizeof(char *));
+ memcpy(new_key, d->key, d->size * sizeof(char *));
+ memcpy(new_hash, d->hash, d->size * sizeof(unsigned));
+ /* Delete previous data */
+ free(d->val);
+ free(d->key);
+ free(d->hash);
+ /* Actually update the dictionary */
+ d->size *= 2 ;
+ d->val = new_val;
+ d->key = new_key;
+ d->hash = new_hash;
+ return 0 ;
+}
+
/*---------------------------------------------------------------------------
- Function codes
+ Function codes
---------------------------------------------------------------------------*/
/*-------------------------------------------------------------------------*/
/**
- @brief Compute the hash key for a string.
- @param key Character string to use for key.
- @return 1 unsigned int on at least 32 bits.
+ @brief Compute the hash key for a string.
+ @param key Character string to use for key.
+ @return 1 unsigned int on at least 32 bits.
This hash function has been taken from an Article in Dr Dobbs Journal.
This is normally a collision-free function, distributing keys evenly.
@@ -91,86 +108,97 @@ static char * xstrdup(char * s)
by comparing the key itself in last resort.
*/
/*--------------------------------------------------------------------------*/
-unsigned dictionary_hash(char * key)
+unsigned dictionary_hash(const char * key)
{
- int len ;
- unsigned hash ;
- int i ;
-
- len = strlen(key);
- for (hash=0, i=0 ; i<len ; i++) {
- hash += (unsigned)key[i] ;
- hash += (hash<<10);
- hash ^= (hash>>6) ;
- }
- hash += (hash <<3);
- hash ^= (hash >>11);
- hash += (hash <<15);
- return hash ;
+ size_t len ;
+ unsigned hash ;
+ size_t i ;
+
+ if (!key)
+ return 0 ;
+
+ len = strlen(key);
+ for (hash=0, i=0 ; i<len ; i++) {
+ hash += (unsigned)key[i] ;
+ hash += (hash<<10);
+ hash ^= (hash>>6) ;
+ }
+ hash += (hash <<3);
+ hash ^= (hash >>11);
+ hash += (hash <<15);
+ return hash ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Create a new dictionary object.
- @param size Optional initial size of the dictionary.
- @return 1 newly allocated dictionary objet.
+ @brief Create a new dictionary object.
+ @param size Optional initial size of the dictionary.
+ @return 1 newly allocated dictionary object.
This function allocates a new dictionary object of given size and returns
it. If you do not know in advance (roughly) the number of entries in the
dictionary, give size=0.
*/
-/*--------------------------------------------------------------------------*/
-dictionary * dictionary_new(int size)
+/*-------------------------------------------------------------------------*/
+dictionary * dictionary_new(size_t size)
{
- dictionary * d ;
-
- /* If no size was specified, allocate space for DICTMINSZ */
- if (size<DICTMINSZ) size=DICTMINSZ ;
-
- if (!(d = (dictionary *)calloc(1, sizeof(dictionary)))) {
- return NULL;
- }
- d->size = size ;
- d->val = (char **)calloc(size, sizeof(char*));
- d->key = (char **)calloc(size, sizeof(char*));
- d->hash = (unsigned int *)calloc(size, sizeof(unsigned));
- return d ;
+ dictionary * d ;
+
+ /* If no size was specified, allocate space for DICTMINSZ */
+ if (size<DICTMINSZ) size=DICTMINSZ ;
+
+ d = (dictionary*) calloc(1, sizeof *d) ;
+
+ if (d) {
+ d->size = size ;
+ d->val = (char**) calloc(size, sizeof *d->val);
+ d->key = (char**) calloc(size, sizeof *d->key);
+ d->hash = (unsigned*) calloc(size, sizeof *d->hash);
+ if (!d->size || !d->val || !d->hash) {
+ free((void *) d->size);
+ free((void *) d->val);
+ free((void *) d->hash);
+ free(d);
+ d = NULL;
+ }
+ }
+ return d ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Delete a dictionary object
- @param d dictionary object to deallocate.
- @return void
+ @brief Delete a dictionary object
+ @param d dictionary object to deallocate.
+ @return void
Deallocate a dictionary object and all memory associated to it.
*/
/*--------------------------------------------------------------------------*/
void dictionary_del(dictionary * d)
{
- int i ;
-
- if (d==NULL) return ;
- for (i=0 ; i<d->size ; i++) {
- if (d->key[i]!=NULL)
- free(d->key[i]);
- if (d->val[i]!=NULL)
- free(d->val[i]);
- }
- free(d->val);
- free(d->key);
- free(d->hash);
- free(d);
- return ;
+ size_t i ;
+
+ if (d==NULL) return ;
+ for (i=0 ; i<d->size ; i++) {
+ if (d->key[i]!=NULL)
+ free(d->key[i]);
+ if (d->val[i]!=NULL)
+ free(d->val[i]);
+ }
+ free(d->val);
+ free(d->key);
+ free(d->hash);
+ free(d);
+ return ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Get a value from a dictionary.
- @param d dictionary object to search.
- @param key Key to look for in the dictionary.
+ @brief Get a value from a dictionary.
+ @param d dictionary object to search.
+ @param key Key to look for in the dictionary.
@param def Default value to return if key not found.
- @return 1 pointer to internally allocated character string.
+ @return 1 pointer to internally allocated character string.
This function locates a key in a dictionary and returns a pointer to its
value, or the passed 'def' pointer if no such key can be found in
@@ -178,24 +206,27 @@ void dictionary_del(dictionary * d)
dictionary object, you should not try to free it or modify it.
*/
/*--------------------------------------------------------------------------*/
-char * dictionary_get(dictionary * d, char * key, char * def)
+const char * dictionary_get(const dictionary * d, const char * key, const char * def)
{
- unsigned hash ;
- int i ;
+ unsigned hash ;
+ size_t i ;
- hash = dictionary_hash(key);
- for (i=0 ; i<d->size ; i++) {
+ if(d == NULL || key == NULL)
+ return def ;
+
+ hash = dictionary_hash(key);
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]==NULL)
continue ;
/* Compare hash */
- if (hash==d->hash[i]) {
+ if (hash==d->hash[i]) {
/* Compare string, to avoid hash collisions */
if (!strcmp(key, d->key[i])) {
- return d->val[i] ;
- }
- }
- }
- return def ;
+ return d->val[i] ;
+ }
+ }
+ }
+ return def ;
}
/*-------------------------------------------------------------------------*/
@@ -224,96 +255,87 @@ char * dictionary_get(dictionary * d, char * key, char * def)
This function returns non-zero in case of failure.
*/
/*--------------------------------------------------------------------------*/
-int dictionary_set(dictionary * d, char * key, char * val)
+int dictionary_set(dictionary * d, const char * key, const char * val)
{
- int i ;
- unsigned hash ;
+ size_t i ;
+ unsigned hash ;
- if (d==NULL || key==NULL) return -1 ;
+ if (d==NULL || key==NULL) return -1 ;
- /* Compute hash for this key */
- hash = dictionary_hash(key) ;
- /* Find if value is already in dictionary */
- if (d->n>0) {
- for (i=0 ; i<d->size ; i++) {
+ /* Compute hash for this key */
+ hash = dictionary_hash(key) ;
+ /* Find if value is already in dictionary */
+ if (d->n>0) {
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]==NULL)
continue ;
- if (hash==d->hash[i]) { /* Same hash value */
- if (!strcmp(key, d->key[i])) { /* Same key */
- /* Found a value: modify and return */
- if (d->val[i]!=NULL)
- free(d->val[i]);
- d->val[i] = val ? xstrdup(val) : NULL ;
+ if (hash==d->hash[i]) { /* Same hash value */
+ if (!strcmp(key, d->key[i])) { /* Same key */
+ /* Found a value: modify and return */
+ if (d->val[i]!=NULL)
+ free(d->val[i]);
+ d->val[i] = (val ? xstrdup(val) : NULL);
/* Value has been modified: return */
- return 0 ;
- }
- }
- }
- }
- /* Add a new value */
- /* See if dictionary needs to grow */
- if (d->n==d->size) {
-
- /* Reached maximum size: reallocate dictionary */
- d->val = (char **)mem_double(d->val, d->size * sizeof(char*)) ;
- d->key = (char **)mem_double(d->key, d->size * sizeof(char*)) ;
- d->hash = (unsigned int *)mem_double(d->hash, d->size * sizeof(unsigned)) ;
- if ((d->val==NULL) || (d->key==NULL) || (d->hash==NULL)) {
- /* Cannot grow dictionary */
- return -1 ;
+ return 0 ;
+ }
+ }
}
- /* Double size */
- d->size *= 2 ;
- }
+ }
+ /* Add a new value */
+ /* See if dictionary needs to grow */
+ if (d->n==d->size) {
+ /* Reached maximum size: reallocate dictionary */
+ if (dictionary_grow(d) != 0)
+ return -1;
+ }
- /* Insert key in the first empty slot */
- for (i=0 ; i<d->size ; i++) {
- if (d->key[i]==NULL) {
- /* Add key here */
- break ;
- }
+ /* Insert key in the first empty slot. Start at d->n and wrap at
+ d->size. Because d->n < d->size this will necessarily
+ terminate. */
+ for (i=d->n ; d->key[i] ; ) {
+ if(++i == d->size) i = 0;
}
- /* Copy key */
- d->key[i] = xstrdup(key);
- d->val[i] = val ? xstrdup(val) : NULL ;
- d->hash[i] = hash;
- d->n ++ ;
- return 0 ;
+ /* Copy key */
+ d->key[i] = xstrdup(key);
+ d->val[i] = (val ? xstrdup(val) : NULL) ;
+ d->hash[i] = hash;
+ d->n ++ ;
+ return 0 ;
}
/*-------------------------------------------------------------------------*/
/**
- @brief Delete a key in a dictionary
- @param d dictionary object to modify.
- @param key Key to remove.
+ @brief Delete a key in a dictionary
+ @param d dictionary object to modify.
+ @param key Key to remove.
@return void
This function deletes a key in a dictionary. Nothing is done if the
key cannot be found.
*/
/*--------------------------------------------------------------------------*/
-void dictionary_unset(dictionary * d, char * key)
+void dictionary_unset(dictionary * d, const char * key)
{
- unsigned hash ;
- int i ;
+ unsigned hash ;
+ size_t i ;
- if (key == NULL) {
- return;
- }
+ if (key == NULL || d == NULL) {
+ return;
+ }
- hash = dictionary_hash(key);
- for (i=0 ; i<d->size ; i++) {
+ hash = dictionary_hash(key);
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]==NULL)
continue ;
/* Compare hash */
- if (hash==d->hash[i]) {
+ if (hash==d->hash[i]) {
/* Compare string, to avoid hash collisions */
if (!strcmp(key, d->key[i])) {
/* Found key */
break ;
- }
- }
- }
+ }
+ }
+ }
if (i>=d->size)
/* Key not found */
return ;
@@ -331,75 +353,31 @@ void dictionary_unset(dictionary * d, char * key)
/*-------------------------------------------------------------------------*/
/**
- @brief Dump a dictionary to an opened file pointer.
- @param d Dictionary to dump
- @param f Opened file pointer.
- @return void
+ @brief Dump a dictionary to an opened file pointer.
+ @param d Dictionary to dump
+ @param f Opened file pointer.
+ @return void
Dumps a dictionary onto an opened file pointer. Key pairs are printed out
as @c [Key]=[Value], one per line. It is Ok to provide stdout or stderr as
output file pointers.
*/
/*--------------------------------------------------------------------------*/
-void dictionary_dump(dictionary * d, FILE * out)
+void dictionary_dump(const dictionary * d, FILE * out)
{
- int i ;
-
- if (d==NULL || out==NULL) return ;
- if (d->n<1) {
- fprintf(out, "empty dictionary\n");
- return ;
- }
- for (i=0 ; i<d->size ; i++) {
+ size_t i ;
+
+ if (d==NULL || out==NULL) return ;
+ if (d->n<1) {
+ fprintf(out, "empty dictionary\n");
+ return ;
+ }
+ for (i=0 ; i<d->size ; i++) {
if (d->key[i]) {
fprintf(out, "%20s\t[%s]\n",
d->key[i],
d->val[i] ? d->val[i] : "UNDEF");
}
- }
- return ;
-}
-
-
-/* Test code */
-#ifdef TESTDIC
-#define NVALS 20000
-int main(int argc, char *argv[])
-{
- dictionary * d ;
- char * val ;
- int i ;
- char cval[90] ;
-
- /* Allocate dictionary */
- printf("allocating...\n");
- d = dictionary_new(0);
-
- /* Set values in dictionary */
- printf("setting %d values...\n", NVALS);
- for (i=0 ; i<NVALS ; i++) {
- sprintf(cval, "%04d", i);
- dictionary_set(d, cval, "salut");
- }
- printf("getting %d values...\n", NVALS);
- for (i=0 ; i<NVALS ; i++) {
- sprintf(cval, "%04d", i);
- val = dictionary_get(d, cval, DICT_INVALID_KEY);
- if (val==DICT_INVALID_KEY) {
- printf("cannot get value for key [%s]\n", cval);
- }
- }
- printf("unsetting %d values...\n", NVALS);
- for (i=0 ; i<NVALS ; i++) {
- sprintf(cval, "%04d", i);
- dictionary_unset(d, cval);
- }
- if (d->n != 0) {
- printf("error deleting values\n");
}
- printf("deallocating...\n");
- dictionary_del(d);
- return 0 ;
+ return ;
}
-#endif
-/* vim: set ts=4 et sw=4 tw=75 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 23:31:27 +0000