/*
* dnsutl - utilities to make DNS easier to configure
* Copyright (C) 1990-1994, 1996, 1999, 2000, 2006, 2007 Peter Miller
*
* This program 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.
*
* This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <error.h>
#include <mem.h>
#include <strlist.h>
#include <symtab.h>
symtab_ty *
symtab_alloc(str_hash_ty size)
{
symtab_ty *stp;
str_hash_ty j;
stp = mem_alloc(sizeof(symtab_ty));
stp->chain = 0;
stp->reap = 0;
stp->hash_modulus = 1 << 2; /* MUST be a power of 2 */
while (stp->hash_modulus < size)
stp->hash_modulus <<= 1;
stp->hash_cutover = stp->hash_modulus;
stp->hash_split = stp->hash_modulus - stp->hash_cutover;
stp->hash_cutover_mask = stp->hash_cutover - 1;
stp->hash_cutover_split_mask = (stp->hash_cutover * 2) - 1;
stp->hash_load = 0;
stp->hash_table = mem_alloc(stp->hash_modulus * sizeof(symtab_row_ty *));
for (j = 0; j < stp->hash_modulus; ++j)
stp->hash_table[j] = 0;
return stp;
}
void
symtab_free(symtab_ty *stp)
{
str_hash_ty j;
for (j = 0; j < stp->hash_modulus; ++j)
{
symtab_row_ty **rpp;
rpp = &stp->hash_table[j];
while (*rpp)
{
symtab_row_ty *rp;
rp = *rpp;
*rpp = rp->overflow;
if (stp->reap)
stp->reap(rp->data);
str_free(rp->key);
mem_free(rp);
}
}
mem_free(stp->hash_table);
mem_free(stp);
}
/*
* NAME
* split - reduce symbol table load
*
* SYNOPSIS
* void split(symtab_ty);
*
* DESCRIPTION
* The split function is used to split symbols in the bucket indicated by
* the split point. The symbols are split between that bucket and the one
* after the current end of the table.
*
* CAVEAT
* It is only sensable to do this when the symbol table load exceeds some
* reasonable threshold. A threshold of 80% is suggested.
*/
static void
split(symtab_ty *stp)
{
symtab_row_ty *p;
symtab_row_ty **ipp;
symtab_row_ty *p2;
str_hash_ty index;
/*
* get the list to be split across buckets
*/
p = stp->hash_table[stp->hash_split];
stp->hash_table[stp->hash_split] = 0;
/*
* increase the modulus by one
*/
stp->hash_modulus++;
stp->hash_table =
mem_change_size
(
stp->hash_table,
stp->hash_modulus * sizeof(symtab_row_ty *)
);
stp->hash_table[stp->hash_modulus - 1] = 0;
stp->hash_split = stp->hash_modulus - stp->hash_cutover;
if (stp->hash_split >= stp->hash_cutover)
{
stp->hash_cutover = stp->hash_modulus;
stp->hash_split = 0;
stp->hash_cutover_mask = stp->hash_cutover - 1;
stp->hash_cutover_split_mask = (stp->hash_cutover * 2) - 1;
}
/*
* now redistribute the list elements
*
* It is important to preserve the order of the links because
* they can be push-down stacks, and to simply add them to the
* head of the list will reverse the order of the stack!
*/
while (p)
{
p2 = p;
p = p2->overflow;
p2->overflow = 0;
index = p2->key->str_hash & stp->hash_cutover_mask;
if (index < stp->hash_split)
{
index =
(
p2->key->str_hash
&
stp->hash_cutover_split_mask
);
}
for
(
ipp = &stp->hash_table[index];
*ipp;
ipp = &(*ipp)->overflow
)
;
*ipp = p2;
}
}
/*
* NAME
* symtab_query - search for a variable
*
* SYNOPSIS
* int symtab_query(symtab_ty *, string_ty *key);
*
* DESCRIPTION
* The symtab_query function is used to reference a variable.
*
* RETURNS
* If the variable has been defined, the function returns a non-zero value
* and the value is returned through the 'value' pointer.
* If the variable has not been defined, it returns zero,
* and 'value' is unaltered.
*/
void *
symtab_query(symtab_ty *stp, string_ty *key)
{
str_hash_ty index;
symtab_row_ty *p;
void *result;
result = 0;
while (stp)
{
index = key->str_hash & stp->hash_cutover_mask;
if (index < stp->hash_split)
index = key->str_hash & stp->hash_cutover_split_mask;
for (p = stp->hash_table[index]; p; p = p->overflow)
{
if (str_equal(key, p->key))
{
result = p->data;
goto done;
}
}
stp = stp->chain;
}
done:
return result;
}
/*
* NAME
* symtab_assign - assign a variable
*
* SYNOPSIS
* void symtab_assign(symtab_ty *, string_ty *key, void *data);
*
* DESCRIPTION
* The symtab_assign function is used to assign
* a value to a given variable.
*
* CAVEAT
* The name is copied, the data is not.
*/
void
symtab_assign(symtab_ty *stp, string_ty *key, void *data)
{
str_hash_ty index;
symtab_row_ty *p;
index = key->str_hash & stp->hash_cutover_mask;
if (index < stp->hash_split)
index = key->str_hash & stp->hash_cutover_split_mask;
for (p = stp->hash_table[index]; p; p = p->overflow)
{
if (str_equal(key, p->key))
{
if (stp->reap)
stp->reap(p->data);
p->data = data;
goto done;
}
}
p = mem_alloc(sizeof(symtab_row_ty));
p->key = str_copy(key);
p->overflow = stp->hash_table[index];
p->data = data;
stp->hash_table[index] = p;
stp->hash_load++;
while (stp->hash_load * 10 >= stp->hash_modulus * 8)
split(stp);
done:;
}
/*
* NAME
* symtab_assign_push - assign a variable
*
* SYNOPSIS
* void symtab_assign_push(symtab_ty *, string_ty *key, void *data);
*
* DESCRIPTION
* The symtab_assign function is used to assign
* a value to a given variable.
* Any previous value will be obscured until this one
* is deleted with symtab_delete.
*
* CAVEAT
* The name is copied, the data is not.
*/
void
symtab_assign_push(symtab_ty *stp, string_ty *key, void *data)
{
str_hash_ty index;
symtab_row_ty *p;
index = key->str_hash & stp->hash_cutover_mask;
if (index < stp->hash_split)
index = key->str_hash & stp->hash_cutover_split_mask;
p = mem_alloc(sizeof(symtab_row_ty));
p->key = str_copy(key);
p->overflow = stp->hash_table[index];
p->data = data;
stp->hash_table[index] = p;
stp->hash_load++;
while (stp->hash_load * 10 >= stp->hash_modulus * 8)
split(stp);
}
/*
* NAME
* symtab_delete - delete a variable
*
* SYNOPSIS
* void symtab_delete(string_ty *name, symtab_class_ty class);
*
* DESCRIPTION
* The symtab_delete function is used to delete variables.
*
* CAVEAT
* The name is freed, the data is reaped.
* (By default, reap does nothing.)
*/
void
symtab_delete(symtab_ty *stp, string_ty *key)
{
str_hash_ty index;
symtab_row_ty **pp;
index = key->str_hash & stp->hash_cutover_mask;
if (index < stp->hash_split)
index = key->str_hash & stp->hash_cutover_split_mask;
pp = &stp->hash_table[index];
for (;;)
{
symtab_row_ty *p;
p = *pp;
if (!p)
break;
if (str_equal(key, p->key))
{
if (stp->reap)
stp->reap(p->data);
str_free(p->key);
*pp = p->overflow;
mem_free(p);
stp->hash_load--;
break;
}
pp = &p->overflow;
}
}
/*
* NAME
* symtab_dump - dump symbol table
*
* SYNOPSIS
* void symtab_dump(symtab_ty *stp, char *caption);
*
* DESCRIPTION
* The symtab_dump function is used to dump the contents of the
* symbol table. The caption will be used to indicate why the
* symbol table was dumped.
*
* CAVEAT
* This function is only available when symbol DEBUG is defined.
*/
#ifdef DEBUG
void
symtab_dump(symtab_ty *stp, char *caption)
{
str_hash_ty j;
symtab_row_ty *p;
error("symbol table %s = {", caption);
for (j = 0; j < stp->hash_modulus; ++j)
{
for (p = stp->hash_table[j]; p; p = p->overflow)
{
error
(
"key = \"%s\", data = %08lX",
p->key->str_text,
(long)p->data
);
}
}
error("}");
}
#endif
void
symtab_walk(symtab_ty *stp, void (*func)(symtab_ty *, string_ty *, void *,
void *), void *arg)
{
str_hash_ty j;
symtab_row_ty *rp;
for (j = 0; j < stp->hash_modulus; ++j)
for (rp = stp->hash_table[j]; rp; rp = rp->overflow)
func(stp, rp->key, rp->data, arg);
}
int
symtab_keys(symtab_ty *stp, strlist_ty *slp)
{
int n;
size_t j;
symtab_row_ty *rp;
strlist_zero(slp);
n = 0;
for (j = 0; j < stp->hash_modulus; ++j)
{
for (rp = stp->hash_table[j]; rp; rp = rp->overflow)
{
++n;
if (slp)
strlist_append_unique(slp, rp->key);
}
}
return n;
}
void
symtab_assign_downcase(symtab_ty *stp, string_ty *key, void *data)
{
string_ty *key2;
key2 = str_downcase(key);
symtab_assign(stp, key2, data);
str_free(key2);
}
void *
symtab_query_downcase(symtab_ty *stp, string_ty *key)
{
string_ty *key2;
void *data;
key2 = str_downcase(key);
data = symtab_query(stp, key2);
str_free(key2);
return data;
}
syntax highlighted by Code2HTML, v. 0.9.1