/*
dict.c - dictionary functions
This file is part of the nss-pam-ldapd library.
Copyright (C) 2007, 2008, 2009, 2010, 2012, 2013 Arthur de Jong
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
#include "config.h"
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif /* HAVE_STDINT_H */
#include "dict.h"
/*
This module uses a hashtable to store its key to value mappings. The
structure is basically as follows:
[struct dictionary]
\- holds an array of pointers to a linked list of [struct dict_entry]
\- each entry has a key/value mapping
The hashmap can be resized when the total number of elements in the hashmap
exceeds a certain load factor.
All the keys are copied in a separate linked list of buffers where each new
buffer that is allocated is larger than the previous one. The first buffer
in the linked list is always the current one.
*/
/* an entry stores one key/value pair */
struct dict_entry {
uint32_t hash; /* used for quick matching and rehashing */
const char *key; /* a reference to a copy of the key */
void *value; /* the stored value */
struct dict_entry *next;
};
/* the initial size of the hashtable */
#define DICT_INITSIZE 7
/* load factor at which point to grow hashtable */
#define DICT_LOADPERCENTAGE 400
/* the dictionary is a hashtable */
struct dictionary {
int size; /* size of the hashtable */
int num; /* total number of keys stored */
struct dict_entry **table; /* the hashtable */
};
/* Simple hash function that computes the hash value of a string. */
static uint32_t stringhash(const char *str)
{
uint32_t hash = 5381;
uint32_t c;
while ((c = *str++) != '\0')
hash = 33 * hash + c;
return hash;
}
/* Grow the hashtable. */
static void growhashtable(DICT *dict)
{
int i;
int newsize;
struct dict_entry **newtable;
struct dict_entry *entry, *tmp;
newsize = dict->size * 3 + 1;
/* allocate room for new hashtable */
newtable = (struct dict_entry **)malloc(newsize * sizeof(struct dict_entry *));
if (newtable == NULL)
return; /* allocating memory failed continue to fill the existing table */
/* clear new table */
for (i = 0; i < newsize; i++)
newtable[i] = NULL;
/* copy old hashtable into new table */
for (i = 0; i < dict->size; i++)
{
/* go over elements in linked list */
entry = dict->table[i];
while (entry != NULL)
{
tmp = entry;
entry = entry->next;
/* put in new position */
tmp->next = newtable[tmp->hash % newsize];
newtable[tmp->hash % newsize] = tmp;
}
}
/* free the old hashtable */
free(dict->table);
/* put new hashtable in place */
dict->size = newsize;
dict->table = newtable;
}
DICT *dict_new(void)
{
struct dictionary *dict;
int i;
/* allocate room for dictionary information */
dict = (struct dictionary *)malloc(sizeof(struct dictionary));
if (dict == NULL)
return NULL;
dict->size = DICT_INITSIZE;
dict->num = 0;
/* allocate initial hashtable */
dict->table = (struct dict_entry **)malloc(DICT_INITSIZE * sizeof(struct dict_entry *));
if (dict->table == NULL)
{
free(dict);
return NULL;
}
/* clear the hashtable */
for (i = 0; i < DICT_INITSIZE; i++)
dict->table[i] = NULL;
/* we're done */
return dict;
}
void dict_free(DICT *dict)
{
struct dict_entry *entry, *etmp;
int i;
/* free hashtable entries */
for (i = 0; i < dict->size; i++)
{
entry = dict->table[i];
while (entry != NULL)
{
etmp = entry;
entry = entry->next;
free(etmp);
}
}
/* free the hashtable */
free(dict->table);
/* free dictionary struct itself */
free(dict);
}
void *dict_get(DICT *dict, const char *key)
{
uint32_t hash;
struct dict_entry *entry;
/* calculate the hash */
hash = stringhash(key);
/* loop over the linked list in the hashtable */
for (entry = dict->table[hash % dict->size]; entry != NULL; entry = entry->next)
{
if ((entry->hash == hash) && (strcmp(entry->key, key) == 0))
return entry->value;
}
/* no matches found */
return NULL;
}
const char *dict_getany(DICT *dict)
{
int i;
/* loop over the linked list in the hashtable */
for (i = 0; i < dict->size; i++)
if (dict->table[i])
return dict->table[i]->key;
/* no matches found */
return NULL;
}
int dict_put(DICT *dict, const char *key, void *value)
{
uint32_t hash;
int l;
char *buf;
int idx;
struct dict_entry *entry, *prev;
/* check if we should grow the hashtable */
if (dict->num >= ((dict->size * DICT_LOADPERCENTAGE) / 100))
growhashtable(dict);
/* calculate the hash and position in the hashtable */
hash = stringhash(key);
idx = hash % dict->size;
/* check if the entry is already present */
for (entry = dict->table[idx], prev = NULL; entry != NULL; prev = entry, entry = entry->next)
{
if ((entry->hash == hash) && (strcmp(entry->key, key) == 0))
{
/* check if we should unset the entry */
if (value == NULL)
{
/* remove from linked list */
if (prev == NULL)
dict->table[idx] = entry->next;
else
prev->next = entry->next;
/* free entry memory and register removal */
free(entry);
dict->num--;
return 0;
}
/* just set the new value */
entry->value = value;
return 0;
}
}
/* if entry should be unset we're done */
if (value == NULL)
return 0;
/* entry is not present, make new entry */
l = strlen(key) + 1;
buf = (char *)malloc(sizeof(struct dict_entry) + l);
if (buf == NULL)
return -1;
entry = (struct dict_entry *)(void *)buf;
buf += sizeof(struct dict_entry);
strcpy(buf, key);
entry->hash = hash;
entry->key = buf;
entry->value = value;
/* insert into hashtable/linked list */
entry->next = dict->table[idx];
dict->table[idx] = entry;
/* increment number of stored items */
dict->num++;
return 0;
}
const char **dict_keys(DICT *dict)
{
int i;
struct dict_entry *entry;
char *buf;
const char **values;
size_t sz;
int num;
/* figure out how much memory to allocate */
num = 0;
sz = 0;
for (i = 0; i < dict->size; i++)
{
entry = dict->table[i];
while (entry != NULL)
{
num++;
sz += strlen(entry->key) + 1;
entry = entry->next;
}
}
/* allocate the needed memory */
buf = (char *)malloc((num + 1) * sizeof(char *) + sz);
if (buf == NULL)
return NULL;
values = (const char **)(void *)buf;
buf += (num + 1) * sizeof(char *);
/* fill the array with the keys */
num = 0;
for (i = 0; i < dict->size; i++)
{
entry = dict->table[i];
while (entry != NULL)
{
strcpy(buf, entry->key);
values[num++] = buf;
buf += strlen(buf) + 1;
entry = entry->next;
}
}
values[num] = NULL;
/* done */
return values;
}