Loading...
Searching...
No Matches
dictionary.c
Go to the documentation of this file.
/* Copyright (c) 2000-2007 by Nicolas Devillard.
* Copyright (x) 2009 by Tim Post <tinkertim@gmail.com>
* MIT License
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*/
#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define MAXVALSZ 1024
#define DICTMINSZ 128
#define DICT_INVALID_KEY ((char*)-1)
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;
}
/* The remaining exposed functions are documented in dictionary.h */
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;
}
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;
}
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;
}
const char* dictionary_get(dictionary* d, const char* key, const 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;
}
int dictionary_set(dictionary* d, const char* key, const 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;
/* Same hash value */
if (hash == d->hash[i]) {
/* Same key */
if (!strcmp(key, d->key[i])) {
/* Found a value: modify and return */
if (d->val[i] != NULL)
free(d->val[i]);
d->val[i] = val ? strdup(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] = strdup(key);
d->val[i] = val ? strdup(val) : NULL;
d->hash[i] = hash;
d->n++;
return 0;
}
void dictionary_unset(dictionary* d, const 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;
}
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;
}
dictionary.h
Implements a dictionary for string variables.
dictionary_unset
void dictionary_unset(dictionary *d, const char *key)
Delete a key in a dictionary.
Definition dictionary.c:206
dictionary
struct _dictionary_ dictionary
Dictionary object.
dictionary_dump
void dictionary_dump(dictionary *d, FILE *out)
Dump a dictionary to an opened file pointer.
Definition dictionary.c:241
dictionary_hash
unsigned dictionary_hash(const char *key)
Compute the hash key for a string.
Definition dictionary.c:74
dictionary_new
dictionary * dictionary_new(int size)
Create a new dictionary object.
Definition dictionary.c:92
dictionary_get
const char * dictionary_get(dictionary *d, const char *key, const char *def)
Get a value from a dictionary.
Definition dictionary.c:128
dictionary_del
void dictionary_del(dictionary *d)
Delete a dictionary object.
Definition dictionary.c:109
dictionary_set
int dictionary_set(dictionary *d, const char *key, const char *val)
Set a value in a dictionary.
Definition dictionary.c:147
DICTMINSZ
#define DICTMINSZ
Minimal allocated number of entries in a dictionary.
Definition dictionary.c:50