home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 22 gnu
/
22-gnu.zip
/
gnurx.zip
/
rx
/
rxhash.c
< prev
next >
Wrap
C/C++ Source or Header
|
1995-12-31
|
9KB
|
402 lines
/***********************************************************
Copyright 1995 by Tom Lord
All Rights Reserved
Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in
supporting documentation, and that the name of the copyright holder not be
used in advertising or publicity pertaining to distribution of the
software without specific, written prior permission.
Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.
******************************************************************/
/*
* Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
*/
#include "rxall.h"
#include "rxhash.h"
#ifdef __STDC__
static struct rx_hash *
default_hash_alloc (struct rx_hash_rules * rules)
#else
static struct rx_hash *
default_hash_alloc (rules)
struct rx_hash_rules * rules;
#endif
{
return (struct rx_hash *)malloc (sizeof (struct rx_hash));
}
#ifdef __STDC__
static struct rx_hash_item *
default_hash_item_alloc (struct rx_hash_rules * rules, void * value)
#else
static struct rx_hash_item *
default_hash_item_alloc (rules, value)
struct rx_hash_rules * rules;
void * value;
#endif
{
struct rx_hash_item * it;
it = (struct rx_hash_item *)malloc (sizeof (*it));
if (it)
{
it->data = value;
it->binding = 0;
}
return it;
}
#ifdef __STDC__
static void
default_free_hash (struct rx_hash * tab,
struct rx_hash_rules * rules)
#else
static void
default_free_hash (tab, rules)
struct rx_hash * tab;
struct rx_hash_rules * rules;
#endif
{
free ((char *)tab);
}
#ifdef __STDC__
static void
default_free_hash_item (struct rx_hash_item * item,
struct rx_hash_rules * rules)
#else
static void
default_free_hash_item (item, rules)
struct rx_hash_item * item;
struct rx_hash_rules * rules;
#endif
{
free ((char *)item);
}
#ifdef __STDC__
static int
default_eq (void * va, void * vb)
#else
static int
default_eq (va, vb)
void * va;
void * vb;
#endif
{
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)
static unsigned long rx_hash_masks[4] =
{
0x12488421,
0x96699669,
0xbe7dd7eb,
0xffffffff
};
/* hash to bucket */
#define JOIN_BYTE(H, B) (((H) + ((H) << 3) + (B)) & 0xf)
#define H2B(X) JOIN_BYTE (JOIN_BYTE (JOIN_BYTE ((X & 0xf), ((X>>8) & 0xf)), ((X>>16) & 0xf)), ((X>>24) & 0xf))
#define BKTS 16
/* Hash tables */
#ifdef __STDC__
struct rx_hash_item *
rx_hash_find (struct rx_hash * table,
unsigned long hash,
void * value,
struct rx_hash_rules * rules)
#else
struct rx_hash_item *
rx_hash_find (table, hash, value, rules)
struct rx_hash * table;
unsigned long hash;
void * value;
struct rx_hash_rules * rules;
#endif
{
rx_hash_eq eq = EQ (rules);
int maskc = 0;
long mask = rx_hash_masks [0];
int bucket = H2B(hash & mask);
while (RX_bitset_member (&table->nested_p, bucket))
{
table = (struct rx_hash *)(table->children [bucket]);
++maskc;
mask = rx_hash_masks[maskc];
bucket = H2B (hash & mask);
}
{
struct rx_hash_item * it;
it = (struct rx_hash_item *)(table->children[bucket]);
while (it)
if (eq (it->data, value))
return it;
else
it = it->next_same_hash;
}
return 0;
}
#ifdef __STDC__
static int
listlen (struct rx_hash_item * bucket)
#else
static int
listlen (bucket)
struct rx_hash_item * bucket;
#endif
{
int i;
for (i = 0; bucket; ++i, bucket = bucket->next_same_hash)
;
return i;
}
#ifdef __STDC__
static int
overflows (struct rx_hash_item * bucket)
#else
static int
overflows (bucket)
struct rx_hash_item * bucket;
#endif
{
return !( bucket
&& bucket->next_same_hash
&& bucket->next_same_hash->next_same_hash
&& bucket->next_same_hash->next_same_hash->next_same_hash);
}
#ifdef __STDC__
struct rx_hash_item *
rx_hash_store (struct rx_hash * table,
unsigned long hash,
void * value,
struct rx_hash_rules * rules)
#else
struct rx_hash_item *
rx_hash_store (table, hash, value, rules)
struct rx_hash * table;
unsigned long hash;
void * value;
struct rx_hash_rules * rules;
#endif
{
rx_hash_eq eq = EQ (rules);
int maskc = 0;
long mask = rx_hash_masks [0];
int bucket = H2B(hash & mask);
int depth = 0;
while (RX_bitset_member (&table->nested_p, bucket))
{
table = (struct rx_hash *)(table->children [bucket]);
++maskc;
mask = rx_hash_masks[maskc];
bucket = H2B(hash & mask);
++depth;
}
{
struct rx_hash_item * it;
it = (struct rx_hash_item *)(table->children[bucket]);
while (it)
if (eq (it->data, value))
return it;
else
it = it->next_same_hash;
}
{
if ( (depth < 3)
&& (overflows ((struct rx_hash_item *)table->children [bucket])))
{
struct rx_hash * newtab;
newtab = (struct rx_hash *) HASH_ALLOC(rules) (rules);
if (!newtab)
goto add_to_bucket;
bzero (newtab, sizeof (*newtab));
newtab->parent = table;
{
int old_bucket_size;
struct rx_hash_item * them;
unsigned long newmask;
them = (struct rx_hash_item *)table->children[bucket];
newmask = rx_hash_masks[maskc + 1];
while (them)
{
struct rx_hash_item * save = them->next_same_hash;
int new_buck = H2B(them->hash & newmask);
them->next_same_hash = ((struct rx_hash_item *)
newtab->children[new_buck]);
((struct rx_hash_item **)newtab->children)[new_buck] = them;
them->table = newtab;
them = save;
++newtab->refs;
--table->refs;
}
((struct rx_hash **)table->children)[bucket] = newtab;
RX_bitset_enjoin (&table->nested_p, bucket);
++table->refs;
table = newtab;
bucket = H2B(hash & newmask);
}
}
}
add_to_bucket:
{
struct rx_hash_item * it = ((struct rx_hash_item *)
ITEM_ALLOC(rules) (rules, value));
if (!it)
return 0;
it->hash = hash;
it->table = table;
/* DATA and BINDING are to be set in hash_item_alloc */
it->next_same_hash = (struct rx_hash_item *)table->children [bucket];
((struct rx_hash_item **)table->children)[bucket] = it;
++table->refs;
return it;
}
}
#ifdef __STDC__
void
rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules)
#else
void
rx_hash_free (it, rules)
struct rx_hash_item * it;
struct rx_hash_rules * rules;
#endif
{
if (it)
{
struct rx_hash * table = it->table;
unsigned long hash = it->hash;
int depth = (table->parent
? (table->parent->parent
? (table->parent->parent->parent
? 3
: 2)
: 1)
: 0);
int bucket = H2B (hash & rx_hash_masks [depth]);
struct rx_hash_item ** pos
= (struct rx_hash_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 rx_hash * save = table;
table = table->parent;
--depth;
bucket = H2B(hash & rx_hash_masks [depth]);
--table->refs;
table->children[bucket] = 0;
RX_bitset_remove (&table->nested_p, bucket);
FREE_HASH (rules) (save, rules);
}
}
}
#ifdef __STDC__
void
rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn,
struct rx_hash_rules * rules)
#else
void
rx_free_hash_table (tab, freefn, rules)
struct rx_hash * tab;
rx_hash_freefn freefn;
struct rx_hash_rules * rules;
#endif
{
int x;
for (x = 0; x < BKTS; ++x)
if (RX_bitset_member (&tab->nested_p, x))
{
rx_free_hash_table ((struct rx_hash *)tab->children[x],
freefn, rules);
FREE_HASH (rules) ((struct rx_hash *)tab->children[x], rules);
}
else
{
struct rx_hash_item * them = (struct rx_hash_item *)tab->children[x];
while (them)
{
struct rx_hash_item * that = them;
them = that->next_same_hash;
freefn (that);
FREE_HASH_ITEM (rules) (that, rules);
}
}
}
#ifdef __STDC__
int
rx_count_hash_nodes (struct rx_hash * st)
#else
int
rx_count_hash_nodes (st)
struct rx_hash * st;
#endif
{
int x;
int count = 0;
for (x = 0; x < BKTS; ++x)
count += ((RX_bitset_member (&st->nested_p, x))
? rx_count_hash_nodes ((struct rx_hash *)st->children[x])
: listlen ((struct rx_hash_item *)(st->children[x])));
return count;
}