/* hashtree.c - hash tables
*
****************************************************************
* Copyright (C) 1998, 2000 Thomas Lord
*
* See the file "COPYING" for further information about
* the copyright and warranty status of this work.
*/
#include "hackerlab/mem/mem.h"
#include "hackerlab/mem/must-malloc.h"
#include "hackerlab/hash/hashtree.h"
/************************************************************************
*(h1 "Hash Table Trees"
* :include ("hash/hashtree.h"))
*
* The hashtree library implements in-core hash tables that are
* automatically dynamically resized. Callers are given complete
* control over memory allocation of hash table data structures.
*/
/*(menu)
*/
/*(include-documentation "hashtree.h")
*/
#define RULES_LIMITS(R) ((R) ? (R)->limits : lim_use_must_malloc)
static struct hashtree *
default_hash_alloc (struct hashtree_rules * rules)
{
return (struct hashtree *)lim_malloc (RULES_LIMITS (rules), sizeof (struct hashtree));
}
static struct hashtree_item *
default_hash_item_alloc (void * key, struct hashtree_rules * rules)
{
struct hashtree_item * it;
it = (struct hashtree_item *)lim_malloc (RULES_LIMITS (rules), sizeof (*it));
if (!it)
return 0;
it->key = key;
it->binding = 0;
return it;
}
static void
default_free_hash (struct hashtree * tab, struct hashtree_rules * rules)
{
lim_free (RULES_LIMITS (rules), (char *)tab);
}
static void
default_free_hash_item (struct hashtree_item * item, struct hashtree_rules * rules)
{
lim_free (RULES_LIMITS (rules), (char *)item);
}
static int
default_eq (void * va, void * vb, struct hashtree_rules * rules)
{
return va == vb;
}
#define EQ(rules) ((rules && rules->eq) ? rules->eq : default_eq)
#define HASH_ALLOC(rules) ((rules && rules->hash_alloc) ? rules->hash_alloc : default_hash_alloc)
#define FREE_HASH(rules) ((rules && rules->free_hash) ? rules->free_hash : default_free_hash)
#define ITEM_ALLOC(rules) ((rules && rules->hash_item_alloc) \
? rules->hash_item_alloc : default_hash_item_alloc)
#define FREE_HASH_ITEM(rules) ((rules && rules->free_hash_item) \
? rules->free_hash_item : default_free_hash_item)
/************************************************************************
*(h2 "Creating Hashtree Rules")
*
*
*
*/
/*(c hashtree_make_rules)
* struct hashtree_rules * hashtree_make_rules (alloc_limits limits);
*
* Allocate a new `hashtree_rules' structure. (See
* xref:"hashtree_rules".)
*
* The `limits' field of the allocated structure is initialized to `limits'.
*
* The function pointers in the allocated structure point to
* default implementations. Those implementations will use `limits'
* when performing allocations.
*
* If an allocation failure occurs, this function returns 0.
*/
struct hashtree_rules *
hashtree_make_rules (alloc_limits limits)
{
struct hashtree_rules * _;
_ = (struct hashtree_rules *)lim_malloc (limits, sizeof (*_));
if (!_)
return 0;
_->eq = default_eq;
_->hash_alloc = default_hash_alloc;
_->free_hash = default_free_hash;
_->hash_item_alloc = default_hash_item_alloc;
_->free_hash_item = default_free_hash_item;
_->limits = limits;
return _;
}
/*(c hashtree_init_rules)
* void hashtree_init_rules (struct hashtree_rules * rules,
* hashtree_eq_fn eq,
* hashtree_alloc_fn hash_alloc,
* free_hashtree_fn free_hash,
* hashtree_alloc_item_fn hash_item_alloc,
* free_hashtree_item_fn free_hash_item,
* alloc_limits limits);
*
* Initialize a `struct hashtree_rules' structure.
*
* It is also possible to initialize a rules structure by filling in
* the fields directly. The advantage of using `hashtree_init_rules'
* is that all fields must be specified -- omitting a field will cause
* a compilation error.
*/
void
hashtree_init_rules (struct hashtree_rules * rules,
hashtree_eq_fn eq,
hashtree_alloc_fn hash_alloc,
free_hashtree_fn free_hash,
hashtree_alloc_item_fn hash_item_alloc,
free_hashtree_item_fn free_hash_item,
alloc_limits limits)
{
rules->eq = eq;
rules->hash_alloc = hash_alloc;
rules->free_hash = free_hash;
rules->hash_item_alloc = hash_item_alloc;
rules->free_hash_item = free_hash_item;
rules->limits = limits;
}
/*(c hashtree_free_limit_rules)
* void hashtree_free_limit_rules (struct hashtree_rules * rules);
*
* Free storage of a `struct hashtree_rules' allocated by
* `hashtree_make_rules'.
*/
void
hashtree_free_limit_rules (struct hashtree_rules * rules)
{
lim_free (rules->limits, rules);
}
/************************************************************************
*(h2 "Hash Tree Allocation")
*
*
*
*/
/*(c hashtree_new)
* struct hashtree * hashtree_new (struct hashtree_rules * rules);
*
* Allocate a new hash table.
*
* `rules' specifies how memory is allocated for this hash tree, and
* how keys are compared for equality. `rules' may be 0, in which
* case default implementations are used. See xref:"Types for
* Hashtrees".
*
* If an allocation failure occurs, this function returns 0.
*/
struct hashtree *
hashtree_alloc (struct hashtree_rules * rules)
{
struct hashtree * it;
it = HASH_ALLOC(rules) (rules);
if (!it)
return 0;
mem_set ((t_uchar *)it, 0, sizeof (*it));
return it;
}
/*(c hashtree_free)
* void hashtree_free (struct hashtree * it,
* hashtree_free_data_fn freefn,
* struct hashtree_rules * rules);
*
* Free all storage allocated to a hash table, including the `struct
* hashtree' itself. (See `hashtree_free_static'.)
*
* The `freefn' is:
*
* typedef void
* (*hashtree_free_data_fn) (struct hashtree_item * it,
* struct hashtree_rules * rules);
*
* When called, it should free any storage associated with
* the `key' and `binding' fields of `it'.
*
*/
void
hashtree_free (struct hashtree * it,
hashtree_free_data_fn freefn,
struct hashtree_rules * rules)
{
hashtree_free_static (it, freefn, rules);
FREE_HASH(rules) (it, rules);
}
/*(c hashtree_free_static)
* void hashtree_free_static (struct hashtree * tab,
* hashtree_free_data_fn freefn,
* struct hashtree_rules * rules);
*
* Free all storage allocated to a hash table, but not the `struct
* hashtree' itself. (See `hashtree_free'.)
*/
void
hashtree_free_static (struct hashtree * tab,
hashtree_free_data_fn freefn,
struct hashtree_rules * rules)
{
int x;
for (x = 0; x < 16; ++x)
if (bitset_is_member (&tab->nested_p, x))
{
hashtree_free_static ((struct hashtree *)tab->children[x], freefn, rules);
FREE_HASH (rules) ((struct hashtree *)tab->children[x], rules);
}
else
{
struct hashtree_item * them = (struct hashtree_item *)tab->children[x];
while (them)
{
struct hashtree_item * that;
that = them;
them = that->next_same_hash;
if (freefn)
freefn (that, rules);
FREE_HASH_ITEM (rules) (that, rules);
}
}
}
/************************************************************************
*(h2 "Hash Tree Access")
*
*
*
*/
static unsigned long hashtree_masks[4] =
{
0x12488421,
0x96699669,
0xbe7dd7eb,
0xffffffff
};
static int shuffled_bytes[] =
{
245, 184, 171, 36, 93, 194, 192, 143, 207, 89, 63, 175, 203, 231, 47, 238,
103, 67, 176, 102, 80, 133, 24, 155, 91, 141, 234, 58, 44, 191, 218, 157,
13, 168, 160, 113, 211, 213, 252, 236, 2, 19, 21, 148, 111, 251, 165, 74,
124, 25, 181, 210, 250, 195, 235, 97, 185, 1, 179, 198, 105, 101, 5, 220,
35, 162, 142, 41, 200, 209, 224, 71, 201, 134, 69, 48, 65, 170, 72, 167,
145, 205, 28, 88, 215, 81, 214, 78, 118, 26, 123, 84, 140, 49, 45, 8,
7, 107, 227, 60, 59, 32, 30, 82, 31, 189, 131, 17, 66, 239, 64, 10,
149, 40, 130, 146, 54, 147, 9, 114, 4, 254, 241, 116, 110, 249, 57, 233,
37, 55, 206, 100, 177, 119, 139, 158, 108, 75, 94, 23, 186, 152, 244, 27,
38, 33, 188, 87, 76, 166, 228, 52, 120, 99, 247, 174, 51, 183, 3, 161,
246, 135, 14, 178, 11, 216, 77, 172, 122, 154, 39, 253, 104, 34, 164, 230,
219, 242, 68, 151, 180, 115, 173, 73, 212, 90, 125, 29, 22, 221, 56, 121,
255, 204, 83, 169, 182, 112, 96, 187, 20, 106, 79, 15, 61, 223, 70, 85,
53, 197, 217, 232, 196, 95, 136, 150, 243, 109, 129, 202, 208, 237, 144, 156,
86, 127, 62, 248, 138, 229, 153, 226, 240, 199, 50, 12, 193, 98, 137, 126,
0, 159, 222, 18, 163, 117, 190, 46, 225, 132, 16, 43, 128, 42, 92, 6
};
/* hash to bucket */
#define H2B(X) \
(0xf & ( shuffled_bytes[X & 0xff] \
^ shuffled_bytes[((X) >> 4) & 0xff] \
^ shuffled_bytes[((X) >> 8) & 0xff] \
^ shuffled_bytes[((X) >> 12) & 0xff] \
^ shuffled_bytes[((X) >> 16) & 0xff] \
^ shuffled_bytes[((X) >> 20) & 0xff] \
^ shuffled_bytes[((X) >> 24) & 0xff] \
^ shuffled_bytes[((X) >> 28) & 0xff]))
/*(c hashtree_find)
* struct hashtree_item * hashtree_find (struct hashtree * table,
* unsigned long hash,
* void * key,
* struct hashtree_rules * rules);
*
* Search for an entry for `key' in hash table `table' and return the
* hash table item for that key (or 0). `hash' is the hash value for
* `key'.
*/
struct hashtree_item *
hashtree_find (struct hashtree * table,
unsigned long hash,
void * key,
struct hashtree_rules * rules)
{
hashtree_eq_fn eq;
int maskc;
unsigned long mask;
int bucket;
eq = EQ (rules);
maskc = 0;
mask = hashtree_masks [0];
bucket = H2B(hash & mask);
while (bitset_is_member (&table->nested_p, bucket))
{
table = (struct hashtree *)(table->children [bucket]);
++maskc;
mask = hashtree_masks[maskc];
bucket = H2B (hash & mask);
}
{
struct hashtree_item * it;
it = (struct hashtree_item *)(table->children[bucket]);
while (it)
if (eq (it->key, key, rules))
return it;
else
it = it->next_same_hash;
}
return 0;
}
static int
overflows (struct hashtree_item * bucket)
{
return ( bucket
&& bucket->next_same_hash
&& bucket->next_same_hash->next_same_hash
&& bucket->next_same_hash->next_same_hash->next_same_hash);
}
/*(c hashtree_store)
* struct hashtree_item * hashtree_store (struct hashtree * table,
* unsigned long hash,
* void * key,
* struct hashtree_rules * rules);
*
* Ensure that there is an entry for `key' in hash table `table' and
* return the hash table item for that key. `hash' is the hash value
* for `key'.
*
* If `key' is not already present in `table', this function uses
* `rules->hash_item_alloc' to create a new key/value pair.
*
* If an allocation failure occurs, this function returns 0.
*/
struct hashtree_item *
hashtree_store (struct hashtree * table,
unsigned long hash,
void * key,
struct hashtree_rules * rules)
{
hashtree_eq_fn eq;
int maskc;
long mask;
int bucket;
int depth;
eq = EQ (rules);
maskc = 0;
mask = hashtree_masks [0];
bucket = H2B(hash & mask);
depth = 0;
while (bitset_is_member (&table->nested_p, bucket))
{
table = (struct hashtree *)(table->children [bucket]);
++maskc;
mask = hashtree_masks[maskc];
bucket = H2B(hash & mask);
++depth;
}
{
struct hashtree_item * it;
it = (struct hashtree_item *)(table->children[bucket]);
while (it)
if (eq (it->key, key, rules))
return it;
else
it = it->next_same_hash;
}
{
if ( (depth < 3)
&& (overflows ((struct hashtree_item *)table->children [bucket])))
{
struct hashtree * newtab;
newtab = HASH_ALLOC(rules) (rules);
if (!newtab)
return 0;
mem_set0 ((char *)newtab, sizeof (*newtab));
newtab->parent = table;
{
struct hashtree_item * them;
unsigned long newmask;
them = (struct hashtree_item *)table->children[bucket];
newmask = hashtree_masks[maskc + 1];
while (them)
{
struct hashtree_item * save = them->next_same_hash;
int new_buck = H2B(them->hash & newmask);
them->next_same_hash = ((struct hashtree_item *)
newtab->children[new_buck]);
((struct hashtree_item **)newtab->children)[new_buck] = them;
them->table = newtab;
them = save;
++newtab->refs;
--table->refs;
}
((struct hashtree **)table->children)[bucket] = newtab;
bitset_adjoin (&table->nested_p, bucket);
++table->refs;
table = newtab;
bucket = H2B(hash & newmask);
}
}
}
{
struct hashtree_item * it;
it = ITEM_ALLOC(rules) (key, rules);
if (!it)
return 0;
it->hash = hash;
it->table = table;
/* KEY and BINDING are to be set in hash_item_alloc */
it->next_same_hash = (struct hashtree_item *)table->children [bucket];
((struct hashtree_item **)table->children)[bucket] = it;
++table->refs;
return it;
}
}
/*(c hashtree_delete)
* void hashtree_delete (struct hashtree_item * it,
* struct hashtree_rules * rules);
*
* Remove hash table item `it' from its hash table.
*
* To remove a particular key, use `hashtree_find' to retrieve
* its key/value pair, and `hashtree_delete' to remove that pair
* from the tree.
*
* This function does not free any storage assocated with
* the key or the binding.
*
* This function does call `rules->free_hash_item' to free `it'.
*/
void
hashtree_delete (struct hashtree_item * it, struct hashtree_rules * rules)
{
if (it)
{
struct hashtree * table;
unsigned long hash;
int depth;
int bucket;
struct hashtree_item ** pos;
table = it->table;
hash = it->hash;
depth = (table->parent
? (table->parent->parent
? (table->parent->parent->parent
? 3
: 2)
: 1)
: 0);
bucket = H2B (hash & hashtree_masks [depth]);
pos = (struct hashtree_item **)&table->children [bucket];
while (*pos != it)
pos = &(*pos)->next_same_hash;
*pos = it->next_same_hash;
FREE_HASH_ITEM(rules) (it, rules);
--table->refs;
while (!table->refs && depth)
{
struct hashtree * empty_table;
empty_table = table;
table = table->parent;
--depth;
bucket = H2B(hash & hashtree_masks [depth]);
--table->refs;
table->children[bucket] = 0;
bitset_remove (&table->nested_p, bucket);
FREE_HASH (rules) (empty_table, rules);
}
}
}
void
hashtree_fold (struct hashtree *table, hashtree_fold_fn foldfn,
void *user_data, struct hashtree_rules * rules)
{
int bucket;
for (bucket = 0; bucket < 16; ++bucket)
{
if (bitset_is_member (&table->nested_p, bucket))
hashtree_fold ((struct hashtree *)(table->children [bucket]),
foldfn, user_data, rules);
else
{
struct hashtree_item * them
= (struct hashtree_item *)table->children[bucket];
while (them)
{
struct hashtree_item * that;
that = them;
them = that->next_same_hash;
foldfn (that, user_data, rules);
}
}
}
}
syntax highlighted by Code2HTML, v. 0.9.1