/*
* Routines to provide a memory-efficient hashtable.
*
- * Copyright (C) 2007-2008 Wayne Davison
+ * Copyright (C) 2007-2009 Wayne Davison
*
* 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
struct hashtable *hashtable_create(int size, int key64)
{
+ int req = size;
struct hashtable *tbl;
int node_size = key64 ? sizeof (struct ht_int64_node)
: sizeof (struct ht_int32_node);
/* Pick a power of 2 that can hold the requested size. */
if (size & (size-1) || size < 16) {
- int req = size;
size = 16;
while (size < req)
size *= 2;
tbl->size = size;
tbl->entries = 0;
tbl->node_size = node_size;
- tbl->key64 = key64;
+ tbl->key64 = (short)key64;
+
+ if (DEBUG_GTE(HASH, 1)) {
+ char buf[32];
+ if (req != size)
+ snprintf(buf, sizeof buf, "req: %d, ", req);
+ else
+ *buf = '\0';
+ rprintf(FINFO, "[%s] created hashtable %lx (%ssize: %d, keys: %d-bit)\n",
+ who_am_i(), (long)tbl, buf, size, key64 ? 64 : 32);
+ }
return tbl;
}
void hashtable_destroy(struct hashtable *tbl)
{
+ if (DEBUG_GTE(HASH, 1)) {
+ rprintf(FINFO, "[%s] destroyed hashtable %lx (size: %d, keys: %d-bit)\n",
+ who_am_i(), (long)tbl, tbl->size, tbl->key64 ? 64 : 32);
+ }
free(tbl->nodes);
free(tbl);
}
tbl->size = size;
tbl->entries = 0;
+ if (DEBUG_GTE(HASH, 1)) {
+ rprintf(FINFO, "[%s] growing hashtable %lx (size: %d, keys: %d-bit)\n",
+ who_am_i(), (long)tbl, size, key64 ? 64 : 32);
+ }
+
for (i = size / 2; i-- > 0; ) {
struct ht_int32_node *move_node = HT_NODE(tbl, old_nodes, i);
int64 move_key = HT_KEY(move_node, key64);
a = b = c = 0xdeadbeef + (8 << 2);
#define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
+#if SIZEOF_INT64 >= 8
b += (uint32)(key >> 32);
+#endif
a += (uint32)key;
c ^= b; c -= rot(b, 14);
a ^= c; a -= rot(c, 11);
if (key64)
((struct ht_int64_node*)node)->key = key;
else
- node->key = key;
+ node->key = (int32)key;
tbl->entries++;
return node;
}