/* $Header$ */
/*
* Copyright © 2003 Keith Packard and Bart Massey.
* All Rights Reserved. See the file COPYING in this directory
* for licensing information.
*/
#include "nickle.h"
/*
* From Knuth -- a good choice for hash/rehash values is p, p-2 where
* p and p-2 are both prime. These tables are sized to have an extra 10%
* free to avoid exponential performance degradation as the hash table fills
*/
static HashSetRec hashSets[] = {
{ 2, 5, 3 },
{ 4, 7, 5 },
{ 8, 13, 11 },
{ 16, 19, 17 },
{ 32, 43, 41 },
{ 64, 73, 71 },
{ 128, 151, 149 },
{ 256, 283, 281 },
{ 512, 571, 569 },
{ 1024, 1153, 1151 },
{ 2048, 2269, 2267 },
{ 4096, 4519, 4517 },
{ 8192, 9013, 9011 },
{ 16384, 18043, 18041 },
{ 32768, 36109, 36107 },
{ 65536, 72091, 72089 },
{ 131072, 144409, 144407 },
{ 262144, 288361, 288359 },
{ 524288, 576883, 576881 },
{ 1048576, 1153459, 1153457 },
{ 2097152, 2307163, 2307161 },
{ 4194304, 4613893, 4613891 },
{ 8388608, 9227641, 9227639 },
{ 16777216, 18455029, 18455027 },
{ 33554432, 36911011, 36911009 },
{ 67108864, 73819861, 73819859 },
{ 134217728, 147639589, 147639587 },
{ 268435456, 295279081, 295279079 },
{ 536870912, 590559793, 590559791 },
{ 1073741824, 1181116273, 1181116271},
{ 2147483648ul, 2362232233ul, 2362232231ul}
};
#define NHASHSETS (sizeof(hashSets)/sizeof(hashSets[0]))
static Value *
Find (HashTablePtr ht, Value hash, Value key)
{
HashSetPtr hs = ht->hashSet;
HashValue size = hs->size;
HashValue h = ValueInt (hash);
HashValue elt = h % size;
HashValue step = 0;
Value *elts = BoxElements (ht->elts);
Value *er, *del = 0;
for (;;)
{
er = &elts[elt * HashEltSize];
if (!HashEltKey(er))
{
/* check for a deleted entry */
if (HashEltValue (er))
{
/* save first deleted entry found */
if (!del)
del = er;
else if (er == del)
break;
}
else
{
/* pull reference as far forward on the chain as posible */
if (del)
er = del;
break;
}
}
else if (HashEltHash(er) == hash &&
Equal(HashEltKey(er), key) == TrueVal)
{
break;
}
if (!step)
{
step = h % hs->rehash;
if (!step)
step = 1;
}
elt += step;
if (elt >= size)
elt -= size;
}
return er;
}
static void
Rehash (BoxPtr old, HashTablePtr ht)
{
Value *o, *n;
HashValue h;
o = BoxElements (old);
ht->count = 0;
for (h = old->nvalues / HashEltSize; h > 0; h--)
{
if (HashEltValid (o))
{
/* XXX must rewrite references */
n = Find (ht, HashEltHash(o), HashEltKey(o));
HashEltCopy (n, o);
ht->count++;
}
HashEltStep (o);
}
}
static void
Resize (HashTablePtr ht, const HashSetPtr hs)
{
ENTER ();
BoxPtr old;
if (ht->hashSet == hs)
return;
old = ht->elts;
ht->elts = NewBox (False, False, hs->size * HashEltSize,
ht->type);
ht->hashSet = hs;
if (old)
Rehash (old, ht);
EXIT ();
}
#if HAVE_STDINT_H
typedef uint32_t crc32_t;
#else
typedef unsigned int crc32_t;
#endif
static crc32_t crc32_table[256];
static void
generate_crc32_table(void)
{
crc32_t c, p;
int n, m;
p = 0xedb88320;
for (n = 0; n < 256; n++)
{
c = n;
for (m = 0; m < 8; m++)
c = (c >> 1) ^ ((c & 1) ? p : 0);
crc32_table[n] = c;
}
}
HashValue
HashCrc32 (unsigned char *bytes, int nbytes)
{
crc32_t crc32 = ~0;
if (crc32_table[1] == 0) abort ();
while (nbytes--)
crc32 = (crc32 >> 8) ^ crc32_table[(crc32 ^ *bytes++) & 0xff];
return (HashValue) ~crc32;
}
int
HashInit (void)
{
generate_crc32_table ();
return 1;
}
static Value
HashEqual (Value av, Value bv, int expandOk)
{
HashTable *at = &av->hash;
HashTable *bt = &bv->hash;
HashValue i;
Value *ae, *be;
/* if they have different numbers of valid elements, they're not equal */
if (at->count != bt->count)
return FalseVal;
ae = BoxElements (at->elts);
for (i = 0; i < at->hashSet->size; i++)
{
if (HashEltValid (ae))
{
be = Find (bt, HashEltHash(ae), HashEltKey (ae));
if (!be || !HashEltValid (be))
return FalseVal;
if (Equal (HashEltValue (be), HashEltValue (ae)) != TrueVal)
return FalseVal;
}
HashEltStep (ae);
}
return TrueVal;
}
static Bool
HashPrint (Value f, Value av, char format, int base, int width, int prec, int fill)
{
HashTable *ht = &av->hash;
HashValue h;
Value *e;
Bool first = True;
Bool pretty = format == 'v' || format == 'g';
if (pretty)
{
FilePuts (f, "(");
FilePutBaseType (f, ht->type, False);
FilePuts (f, " ");
FilePuts (f, "[");
FilePutType (f, ht->keyType, False);
FilePuts (f, "]");
FilePutSubscriptType (f, ht->type, False);
FilePuts (f, ") {");
}
e = BoxElements (ht->elts);
for (h = ht->hashSet->size; h-- > 0; )
{
if (HashEltValid (e))
{
if (pretty)
{
if (!first)
FilePuts (f, ", ");
else
FilePuts (f, " ");
Print (f, HashEltKey (e), format, base, width, prec, fill);
FilePuts (f, " => ");
}
else if (!first)
FilePuts (f, " ");
Print (f, HashEltValue (e), format, base, width, prec, fill);
first = False;
}
HashEltStep (e);
}
if (pretty)
{
if (ht->def)
{
if (!first)
FilePuts (f, ",");
FilePuts (f, " => ");
Print (f, ht->def, format, base, width, prec, fill);
first = False;
}
if (!first)
FilePuts (f, " ");
FilePuts (f, "}");
}
return True;
}
static HashValue
HashHash (Value av)
{
HashTable *ht = &av->hash;
HashValue h;
Value *e;
HashValue hash = 0;
e = BoxElements (ht->elts);
for (h = ht->hashSet->size; h-- > 0; )
{
if (HashEltValue (e))
hash ^= ValueInt (HashEltHash (e));
HashEltStep (e);
}
return hash;
}
static void
HashMark (void *object)
{
HashTable *ht = (HashTable *) object;
MemReference (ht->type);
MemReference (ht->keyType);
MemReference (ht->elts);
MemReference (ht->def);
}
ValueRep HashRep = {
{ HashMark, 0, "HashRep" },
rep_hash,
{
0,
0,
0,
0,
0,
0,
0,
HashEqual,
0,
0,
},
{
0,
},
0,
0,
HashPrint,
0,
HashHash,
};
Value
NewHash (Bool constant, TypePtr keyType, TypePtr type)
{
ENTER ();
Value ret = ALLOCATE (&HashRep.data, sizeof (HashTable));
ret->hash.hashSet = 0;
ret->hash.count = 0;
ret->hash.type = type;
ret->hash.keyType = keyType;
ret->hash.elts = 0;
ret->hash.def = 0;
Resize (&ret->hash, &hashSets[0]);
RETURN (ret);
}
Value
HashGet (Value hv, Value key)
{
HashTablePtr ht = &hv->hash;
Value hash = ValueHash (key);
Value *he;
Value value;
he = Find (ht, hash, key);
if (!HashEltValid (he))
{
if (!ht->def)
{
RaiseStandardException (exception_uninitialized_value,
"uninitialized hash element", 0);
return (Void);
}
if (ht->count >= ht->hashSet->entries &&
ht->hashSet != &hashSets[NHASHSETS - 1])
{
Resize (ht, ht->hashSet + 1);
}
ht->count++;
HashEltHash(he) = hash;
HashEltKey(he) = key;
HashEltValue(he) = Copy(ht->def);
}
value = HashEltValue (he);
if (!value)
{
RaiseStandardException (exception_uninitialized_value,
"uninitialized hash element", 0);
return (Void);
}
return value;
}
void
HashSet (Value hv, Value key, Value value)
{
HashTablePtr ht = &hv->hash;
Value hash = ValueHash (key);
Value *he;
if (ht->count >= ht->hashSet->entries &&
ht->hashSet != &hashSets[NHASHSETS - 1])
{
Resize (ht, ht->hashSet + 1);
}
he = Find (ht, hash, key);
if (!HashEltValid (he))
ht->count++;
HashEltHash (he) = hash;
HashEltKey (he) = key;
HashEltValue (he) = value;
}
void
HashSetDef (Value hv, Value def)
{
HashTablePtr ht = &hv->hash;
ht->def = Copy(def);
}
Value
HashRef (Value hv, Value key)
{
ENTER ();
HashTablePtr ht = &hv->hash;
Value *he;
Value hash = ValueHash (key);
if (ht->count == ht->hashSet->entries &&
ht->hashSet != &hashSets[NHASHSETS - 1])
{
Resize (ht, ht->hashSet + 1);
}
he = Find (ht, hash, key);
if (!HashEltValid (he))
{
ht->count++;
HashEltHash (he) = hash;
HashEltKey (he) = key;
if (ht->def)
HashEltValue (he) = Copy(ht->def);
}
RETURN (NewRef (ht->elts,
&HashEltValue(he) - BoxElements (ht->elts)));
}
Value
HashTest (Value hv, Value key)
{
HashTablePtr ht = &hv->hash;
Value *he;
Value hash = ValueHash (key);
he = Find (ht, hash, key);
return HashEltValid (he) ? TrueVal : FalseVal;
}
void
HashDelete (Value hv, Value key)
{
HashTablePtr ht = &hv->hash;
Value *he;
Value hash = ValueHash (key);
he = Find (ht, hash, key);
if (HashEltValid (he))
{
/* mark this entry as deleted -- value Void, key NULL */
HashEltHash (he) = 0;
HashEltKey (he) = 0;
HashEltValue (he) = Void;
--ht->count;
}
}
Value
HashKeys (Value hv)
{
ENTER ();
HashTablePtr ht = &hv->hash;
int dim = ht->count;
Value keys = NewArray (False, True, ht->keyType, 1, &dim);
HashValue h;
int i = 0;
Value *e = BoxElements (ht->elts);
for (h = ht->hashSet->size; h > 0; h--)
{
if (HashEltValid (e))
{
ArrayValueSet (&keys->array, i, HashEltKey (e));
i++;
}
HashEltStep (e);
}
if (i != dim)
ArrayResize (keys, 0, i);
RETURN (keys);
}
Value
HashCopy (Value hv)
{
ENTER ();
Value new = NewHash (False, hv->hash.keyType, hv->hash.type);
new->hash.def = hv->hash.def;
Resize (&new->hash, hv->hash.hashSet);
Rehash (hv->hash.elts, &new->hash);
RETURN (new);
}
syntax highlighted by Code2HTML, v. 0.9.1