/* grecs - Gray's Extensible Configuration System
Copyright (C) 2007, 2008, 2009, 2010, 2011 Sergey Poznyakoff
Grecs is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version.
Grecs 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 General Public License for more details.
You should have received a copy of the GNU General Public License along
with Grecs. If not, see . */
#ifdef HAVE_CONFIG_H
# include
#endif
#include
#include
#include
#include
/* |hash_size| defines a sequence of symbol table sizes. These are prime
numbers, each of which is approximately twice its predecessor. */
static unsigned int hash_size[] = {
7, 17, 37, 101, 229, 487, 1009, 2039, 4091, 8191, 16411
};
/* |max_rehash| keeps the number of entries in |hash_size| table. */
static unsigned int max_rehash = sizeof(hash_size) / sizeof(hash_size[0]);
struct grecs_symtab {
int flags;
unsigned int hash_num; /* Index to hash_size table */
size_t elsize; /* Size of an element */
struct grecs_syment **tab;
unsigned (*hash_fun)(void *, unsigned long hash_num);
int (*cmp_fun)(const void *, const void *);
int (*copy_fun)(void *, void *);
void *(*syment_alloc_fun)(size_t size);
void (*syment_free_fun) (void *);
};
static void
syment_free(struct grecs_symtab *st, void *ptr)
{
if (st->syment_free_fun)
st->syment_free_fun(ptr);
else
free(ptr);
}
static struct grecs_syment *
syment_alloc(struct grecs_symtab *st, void *key)
{
struct grecs_syment *ent;
ent = st->syment_alloc_fun ?
st->syment_alloc_fun(st->elsize) : malloc(st->elsize);
if (ent) {
memset(ent, 0, st->elsize);
if (st->copy_fun(ent, key)) {
int ec = errno;
syment_free(st, ent);
errno = ec;
return NULL;
}
}
return ent;
}
unsigned
grecs_hash_string(const char *name, unsigned long hashsize)
{
unsigned i;
for (i = 0; *name; name++) {
i <<= 1;
i ^= *(unsigned char*) name;
}
return i % hashsize;
}
static unsigned
def_hash(void *data, unsigned long hashsize)
{
struct grecs_syment *sym = data;
return grecs_hash_string(sym->name, hashsize);
}
static int
def_cmp(const void *a, const void *b)
{
struct grecs_syment const *syma = a;
struct grecs_syment const *symb = b;
return strcmp(syma->name, symb->name);
}
static int
def_copy(void *a, void *b)
{
struct grecs_syment *syma = a;
struct grecs_syment *symb = b;
syma->name = strdup(symb->name);
return syma->name == NULL;
}
static void
def_free_fun(void *p)
{
struct grecs_syment *sym = p;
free(sym->name);
free(sym);
}
static unsigned
symtab_insert_pos(struct grecs_symtab *st, void *elt)
{
unsigned i;
unsigned pos = st->hash_fun(elt, hash_size[st->hash_num]);
for (i = pos; st->tab[i];) {
if (++i >= hash_size[st->hash_num])
i = 0;
if (i == pos)
/* FIXME: Error message? */
abort();
}
return i;
}
int
grecs_symtab_replace(struct grecs_symtab *st, void *ent, void **old_ent)
{
struct grecs_syment *entry;
unsigned i, pos = st->hash_fun(ent, hash_size[st->hash_num]);
for (i = pos; entry = st->tab[i];) {
if (st->cmp_fun(entry, ent) == 0)
break;
if (++i >= hash_size[st->hash_num])
i = 0;
if (i == pos)
return ENOENT;
}
if (old_ent)
*old_ent = entry;
st->tab[i] = ent;
return 0;
}
static int
symtab_rehash(struct grecs_symtab *st)
{
struct grecs_syment **old_tab = st->tab;
struct grecs_syment **new_tab;
unsigned int i;
unsigned int hash_num = st->hash_num + 1;
if (hash_num >= max_rehash)
return E2BIG;
new_tab = calloc(hash_size[hash_num], sizeof(*new_tab));
if (!new_tab)
return ENOMEM;
st->tab = new_tab;
if (old_tab) {
st->hash_num = hash_num;
for (i = 0; i < hash_size[hash_num-1]; i++) {
struct grecs_syment *elt = old_tab[i];
if (elt->name) {
unsigned n = symtab_insert_pos(st, elt);
new_tab[n] = elt;
}
}
free(old_tab);
}
return 0;
}
const char *
grecs_symtab_strerror(int rc)
{
switch (rc) {
case ENOENT:
return _("element not found in table");
case E2BIG:
return _("symbol table is full");
case ENOMEM:
return strerror(ENOMEM);
}
return strerror(rc);
}
int
grecs_symtab_remove(struct grecs_symtab *st, void *elt)
{
unsigned int pos, i, j, r;
struct grecs_syment *entry;
pos = st->hash_fun(elt, hash_size[st->hash_num]);
for (i = pos; entry = st->tab[i];) {
if (st->cmp_fun(entry, elt) == 0)
break;
if (++i >= hash_size[st->hash_num])
i = 0;
if (i == pos)
return ENOENT;
}
syment_free(st, entry);
for (;;) {
st->tab[i] = NULL;
j = i;
do {
if (++i >= hash_size[st->hash_num])
i = 0;
if (!st->tab[i])
return 0;
r = st->hash_fun(st->tab[i], hash_size[st->hash_num]);
}
while ((j < r && r <= i)
|| (i < j && j < r) || (r <= i && i < j));
st->tab[j] = st->tab[i];
}
return 0;
}
int
grecs_symtab_get_index(unsigned *idx, struct grecs_symtab *st,
void *key, int *install)
{
int rc;
unsigned i, pos;
struct grecs_syment *elem;
if (!st->tab) {
if (install) {
rc = symtab_rehash(st);
if (rc)
return rc;
} else
return ENOENT;
}
pos = st->hash_fun(key, hash_size[st->hash_num]);
for (i = pos; elem = st->tab[i];) {
if (st->cmp_fun(elem, key) == 0) {
if (install)
*install = 0;
*idx = i;
return 0;
}
if (++i >= hash_size[st->hash_num])
i = 0;
if (i == pos)
break;
}
if (!install)
return ENOENT;
if (!elem) {
*install = 1;
*idx = i;
return 0;
}
if ((rc = symtab_rehash(st)) != 0)
return rc;
return grecs_symtab_get_index(idx, st, key, install);
}
void *
grecs_symtab_lookup_or_install(struct grecs_symtab *st, void *key,
int *install)
{
unsigned i;
int rc = grecs_symtab_get_index(&i, st, key, install);
if (rc == 0) {
if (install && *install == 1) {
struct grecs_syment *ent = syment_alloc(st, key);
if (!ent) {
errno = ENOMEM;
return NULL;
}
st->tab[i] = ent;
return ent;
} else
return st->tab[i];
}
errno = rc;
return NULL;
}
void
grecs_symtab_clear(struct grecs_symtab *st)
{
unsigned i, hs;
if (!st || !st->tab)
return;
hs = hash_size[st->hash_num];
for (i = 0; i < hs; i++) {
struct grecs_syment *elem = st->tab[i];
if (elem) {
syment_free(st, elem);
st->tab[i] = NULL;
}
}
}
struct grecs_symtab *
grecs_symtab_create(size_t elsize,
unsigned (*hash_fun)(void *, unsigned long),
int (*cmp_fun)(const void *, const void *),
int (*copy_fun)(void *, void *),
void *(*alloc_fun)(size_t), void (*free_fun)(void *))
{
struct grecs_symtab *st = malloc(sizeof(*st));
if (st) {
memset(st, 0, sizeof(*st));
st->elsize = elsize;
st->hash_fun = hash_fun ? hash_fun : def_hash;
st->cmp_fun = cmp_fun ? cmp_fun : def_cmp;
st->copy_fun = copy_fun ? copy_fun : def_copy;
st->syment_alloc_fun = alloc_fun;
if (free_fun)
st->syment_free_fun = free_fun;
else if (!copy_fun)
st->syment_free_fun = def_free_fun;
else
st->syment_free_fun = NULL;
st->tab = calloc(hash_size[st->hash_num], sizeof(*st->tab));
if (!st->tab) {
free(st);
st = NULL;
}
}
return st;
}
struct grecs_symtab *
grecs_symtab_create_default(size_t elsize)
{
return grecs_symtab_create(elsize,
NULL, NULL, NULL, NULL, NULL);
}
void
grecs_symtab_free(struct grecs_symtab *st)
{
if (st) {
grecs_symtab_clear(st);
free(st->tab);
free(st);
}
}
size_t
grecs_symtab_count_entries(struct grecs_symtab *st)
{
unsigned i;
size_t count = 0;
for (i = 0; i < hash_size[st->hash_num]; i++)
if (st->tab[i])
count++;
return count;
}
int
grecs_symtab_enumerate(struct grecs_symtab *st, grecs_symtab_enumerator_t fun,
void *data)
{
unsigned i;
if (!st)
return 0;
for (i = 0; i < hash_size[st->hash_num]; i++) {
struct grecs_syment *ep = st->tab[i];
if (ep) {
int rc = fun(ep, data);
if (rc)
return rc;
}
}
return 0;
}