406 lines
11 KiB
C
406 lines
11 KiB
C
|
/*-------------------------------------------------------------------------*/
|
||
|
|
/**
|
||
|
|
@file dictionary.c
|
||
|
|
@author N. Devillard
|
||
|
|
@date Sep 2007
|
||
|
|
@version $Revision: 1.27 $
|
||
|
|
@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.
|
||
|
|
informations retrieved from a configuration file (ini files).
|
||
|
|
*/
|
||
|
|
/*--------------------------------------------------------------------------*/
|
||
|
|
|
||
|
|
/*
|
||
|
|
$Id: dictionary.c,v 1.27 2007-11-23 21:39:18 ndevilla Exp $
|
||
|
|
$Revision: 1.27 $
|
||
|
|
*/
|
||
|
|
/*---------------------------------------------------------------------------
|
||
|
|
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)
|
||
|
|
|
||
|
|
/*---------------------------------------------------------------------------
|
||
|
|
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
|
||
|
|
@param s String to duplicate
|
||
|
|
@return Pointer to a newly allocated string, to be freed with free()
|
||
|
|
|
||
|
|
This is a replacement for strdup(). This implementation is provided
|
||
|
|
for systems that do not have it.
|
||
|
|
*/
|
||
|
|
/*--------------------------------------------------------------------------*/
|
||
|
|
static char * xstrdup(char * s)
|
||
|
|
{
|
||
|
|
char * t ;
|
||
|
|
if (!s)
|
||
|
|
return NULL ;
|
||
|
|
t = malloc(strlen(s)+1) ;
|
||
|
|
if (t) {
|
||
|
|
strcpy(t,s);
|
||
|
|
}
|
||
|
|
return t ;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*---------------------------------------------------------------------------
|
||
|
|
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.
|
||
|
|
|
||
|
|
This hash function has been taken from an Article in Dr Dobbs Journal.
|
||
|
|
This is normally a collision-free function, distributing keys evenly.
|
||
|
|
The key is stored anyway in the struct so that collision can be avoided
|
||
|
|
by comparing the key itself in last resort.
|
||
|
|
*/
|
||
|
|
/*--------------------------------------------------------------------------*/
|
||
|
|
unsigned dictionary_hash(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 ;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*-------------------------------------------------------------------------*/
|
||
|
|
/**
|
||
|
|
@brief Create a new dictionary object.
|
||
|
|
@param size Optional initial size of the dictionary.
|
||
|
|
@return 1 newly allocated dictionary objet.
|
||
|
|
|
||
|
|
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 * 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 ;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*-------------------------------------------------------------------------*/
|
||
|
|
/**
|
||
|
|
@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 ;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*-------------------------------------------------------------------------*/
|
||
|
|
/**
|
||
|
|
@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.
|
||
|
|
|
||
|
|
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
|
||
|
|
dictionary. The returned character pointer points to data internal to the
|
||
|
|
dictionary object, you should not try to free it or modify it.
|
||
|
|
*/
|
||
|
|
/*--------------------------------------------------------------------------*/
|
||
|
|
char * dictionary_get(dictionary * d, char * key, char * def)
|
||
|
|
{
|
||
|
|
unsigned hash ;
|
||
|
|
int 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]) {
|
||
|
|
/* Compare string, to avoid hash collisions */
|
||
|
|
if (!strcmp(key, d->key[i])) {
|
||
|
|
return d->val[i] ;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return def ;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*-------------------------------------------------------------------------*/
|
||
|
|
/**
|
||
|
|
@brief Set a value in a dictionary.
|
||
|
|
@param d dictionary object to modify.
|
||
|
|
@param key Key to modify or add.
|
||
|
|
@param val Value to add.
|
||
|
|
@return int 0 if Ok, anything else otherwise
|
||
|
|
|
||
|
|
If the given key is found in the dictionary, the associated value is
|
||
|
|
replaced by the provided one. If the key cannot be found in the
|
||
|
|
dictionary, it is added to it.
|
||
|
|
|
||
|
|
It is Ok to provide a NULL value for val, but NULL values for the dictionary
|
||
|
|
or the key are considered as errors: the function will return immediately
|
||
|
|
in such a case.
|
||
|
|
|
||
|
|
Notice that if you dictionary_set a variable to NULL, a call to
|
||
|
|
dictionary_get will return a NULL value: the variable will be found, and
|
||
|
|
its value (NULL) is returned. In other words, setting the variable
|
||
|
|
content to NULL is equivalent to deleting the variable from the
|
||
|
|
dictionary. It is not possible (in this implementation) to have a key in
|
||
|
|
the dictionary without value.
|
||
|
|
|
||
|
|
This function returns non-zero in case of failure.
|
||
|
|
*/
|
||
|
|
/*--------------------------------------------------------------------------*/
|
||
|
|
int dictionary_set(dictionary * d, char * key, char * val)
|
||
|
|
{
|
||
|
|
int i ;
|
||
|
|
unsigned hash ;
|
||
|
|
|
||
|
|
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++) {
|
||
|
|
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 ;
|
||
|
|
/* 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 ;
|
||
|
|
}
|
||
|
|
/* Double size */
|
||
|
|
d->size *= 2 ;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* Insert key in the first empty slot */
|
||
|
|
for (i=0 ; i<d->size ; i++) {
|
||
|
|
if (d->key[i]==NULL) {
|
||
|
|
/* Add key here */
|
||
|
|
break ;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
/* 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.
|
||
|
|
@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)
|
||
|
|
{
|
||
|
|
unsigned hash ;
|
||
|
|
int i ;
|
||
|
|
|
||
|
|
if (key == NULL) {
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
hash = dictionary_hash(key);
|
||
|
|
for (i=0 ; i<d->size ; i++) {
|
||
|
|
if (d->key[i]==NULL)
|
||
|
|
continue ;
|
||
|
|
/* Compare hash */
|
||
|
|
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 ;
|
||
|
|
|
||
|
|
free(d->key[i]);
|
||
|
|
d->key[i] = NULL ;
|
||
|
|
if (d->val[i]!=NULL) {
|
||
|
|
free(d->val[i]);
|
||
|
|
d->val[i] = NULL ;
|
||
|
|
}
|
||
|
|
d->hash[i] = 0 ;
|
||
|
|
d->n -- ;
|
||
|
|
return ;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*-------------------------------------------------------------------------*/
|
||
|
|
/**
|
||
|
|
@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)
|
||
|
|
{
|
||
|
|
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++) {
|
||
|
|
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 ;
|
||
|
|
}
|
||
|
|
#endif
|
||
|
|
/* vim: set ts=4 et sw=4 tw=75 */
|