* into proprietary software; there is no requirement for such software to
* contain a copyright notice related to this source.
*
- * $Id: hash.c,v 1.2 2009-10-14 02:24:05 didg Exp $
* $Name: $
*/
#define NDEBUG
#include "hash.h"
#ifdef KAZLIB_RCSID
-static const char rcsid[] = "$Id: hash.c,v 1.2 2009-10-14 02:24:05 didg Exp $";
#endif
-#define INIT_BITS 6
-#define INIT_SIZE (1UL << (INIT_BITS)) /* must be power of two */
-#define INIT_MASK ((INIT_SIZE) - 1)
+#define INIT_BITS 6
+#define INIT_SIZE (1UL << (INIT_BITS)) /* must be power of two */
+#define INIT_MASK ((INIT_SIZE) - 1)
#define next hash_next
#define key hash_key
static void compute_bits(void)
{
- hash_val_t val = HASH_VAL_T_MAX; /* 1 */
+ hash_val_t val = HASH_VAL_T_MAX; /* 1 */
int bits = 0;
- while (val) { /* 2 */
- bits++;
- val >>= 1;
+ while (val) { /* 2 */
+ bits++;
+ val >>= 1;
}
hash_val_t_bit = bits;
static int is_power_of_two(hash_val_t arg)
{
if (arg == 0)
- return 0;
+ return 0;
while ((arg & 1) == 0)
- arg >>= 1;
+ arg >>= 1;
return (arg == 1);
}
/*
- * Compute a shift amount from a given table size
+ * Compute a shift amount from a given table size
*/
static hash_val_t compute_mask(hashcount_t size)
hash_val_t i;
for (i = 0; i < hash->nchains; i++)
- hash->table[i] = NULL;
+ hash->table[i] = NULL;
}
/*
{
hnode_t **newtable;
- assert (2 * hash->nchains > hash->nchains); /* 1 */
+ assert (2 * hash->nchains > hash->nchains); /* 1 */
newtable = realloc(hash->table,
- sizeof *newtable * hash->nchains * 2); /* 4 */
-
- if (newtable) { /* 5 */
- hash_val_t mask = (hash->mask << 1) | 1; /* 3 */
- hash_val_t exposed_bit = mask ^ hash->mask; /* 6 */
- hash_val_t chain;
-
- assert (mask != hash->mask);
-
- for (chain = 0; chain < hash->nchains; chain++) { /* 7 */
- hnode_t *low_chain = NULL, *high_chain = NULL, *hptr, *next;
-
- for (hptr = newtable[chain]; hptr != NULL; hptr = next) {
- next = hptr->next;
-
- if (hptr->hkey & exposed_bit) {
- hptr->next = high_chain;
- high_chain = hptr;
- } else {
- hptr->next = low_chain;
- low_chain = hptr;
- }
- }
-
- newtable[chain] = low_chain; /* 8 */
- newtable[chain + hash->nchains] = high_chain;
- }
-
- hash->table = newtable; /* 9 */
- hash->mask = mask;
- hash->nchains *= 2;
- hash->lowmark *= 2;
- hash->highmark *= 2;
+ sizeof *newtable * hash->nchains * 2); /* 4 */
+
+ if (newtable) { /* 5 */
+ hash_val_t mask = (hash->mask << 1) | 1; /* 3 */
+ hash_val_t exposed_bit = mask ^ hash->mask; /* 6 */
+ hash_val_t chain;
+
+ assert (mask != hash->mask);
+
+ for (chain = 0; chain < hash->nchains; chain++) { /* 7 */
+ hnode_t *low_chain = NULL, *high_chain = NULL, *hptr, *next;
+
+ for (hptr = newtable[chain]; hptr != NULL; hptr = next) {
+ next = hptr->next;
+
+ if (hptr->hkey & exposed_bit) {
+ hptr->next = high_chain;
+ high_chain = hptr;
+ } else {
+ hptr->next = low_chain;
+ low_chain = hptr;
+ }
+ }
+
+ newtable[chain] = low_chain; /* 8 */
+ newtable[chain + hash->nchains] = high_chain;
+ }
+
+ hash->table = newtable; /* 9 */
+ hash->mask = mask;
+ hash->nchains *= 2;
+ hash->lowmark *= 2;
+ hash->highmark *= 2;
}
assert (hash_verify(hash));
}
* hash->shift is equal to hash_val_t_bit, an illegal shift value.
* Also, other things could go wrong, such as hash->lowmark becoming zero.
* 2. Looping over each pair of sister chains, the low_chain is set to
- * point to the head node of the chain in the lower half of the table,
+ * point to the head node of the chain in the lower half of the table,
* and high_chain points to the head node of the sister in the upper half.
* 3. The intent here is to compute a pointer to the last node of the
* lower chain into the low_tail variable. If this chain is empty,
hash_val_t chain, nchains;
hnode_t **newtable, *low_tail, *low_chain, *high_chain;
- assert (hash->nchains >= 2); /* 1 */
+ assert (hash->nchains >= 2); /* 1 */
nchains = hash->nchains / 2;
for (chain = 0; chain < nchains; chain++) {
- low_chain = hash->table[chain]; /* 2 */
- high_chain = hash->table[chain + nchains];
- for (low_tail = low_chain; low_tail && low_tail->next; low_tail = low_tail->next)
- ; /* 3 */
- if (low_chain != NULL) /* 4 */
- low_tail->next = high_chain;
- else if (high_chain != NULL) /* 5 */
- hash->table[chain] = high_chain;
- else
- assert (hash->table[chain] == NULL); /* 6 */
+ low_chain = hash->table[chain]; /* 2 */
+ high_chain = hash->table[chain + nchains];
+ for (low_tail = low_chain; low_tail && low_tail->next; low_tail = low_tail->next)
+ ; /* 3 */
+ if (low_chain != NULL) /* 4 */
+ low_tail->next = high_chain;
+ else if (high_chain != NULL) /* 5 */
+ hash->table[chain] = high_chain;
+ else
+ assert (hash->table[chain] == NULL); /* 6 */
}
newtable = realloc(hash->table,
- sizeof *newtable * nchains); /* 7 */
- if (newtable) /* 8 */
- hash->table = newtable;
- hash->mask >>= 1; /* 9 */
+ sizeof *newtable * nchains); /* 7 */
+ if (newtable) /* 8 */
+ hash->table = newtable;
+ hash->mask >>= 1; /* 9 */
hash->nchains = nchains;
hash->lowmark /= 2;
hash->highmark /= 2;
*/
hash_t *hash_create(hashcount_t maxcount, hash_comp_t compfun,
- hash_fun_t hashfun)
+ hash_fun_t hashfun)
{
hash_t *hash;
- if (hash_val_t_bit == 0) /* 1 */
- compute_bits();
-
- hash = malloc(sizeof *hash); /* 2 */
-
- if (hash) { /* 3 */
- hash->table = malloc(sizeof *hash->table * INIT_SIZE); /* 4 */
- if (hash->table) { /* 5 */
- hash->nchains = INIT_SIZE; /* 6 */
- hash->highmark = INIT_SIZE * 2;
- hash->lowmark = INIT_SIZE / 2;
- hash->nodecount = 0;
- hash->maxcount = maxcount;
- hash->compare = compfun ? compfun : hash_comp_default;
- hash->function = hashfun ? hashfun : hash_fun_default;
- hash->allocnode = hnode_alloc;
- hash->freenode = hnode_free;
- hash->context = NULL;
- hash->mask = INIT_MASK;
- hash->dynamic = 1; /* 7 */
- clear_table(hash); /* 8 */
- assert (hash_verify(hash));
- return hash;
- }
- free(hash);
+ if (hash_val_t_bit == 0) /* 1 */
+ compute_bits();
+
+ hash = malloc(sizeof *hash); /* 2 */
+
+ if (hash) { /* 3 */
+ hash->table = malloc(sizeof *hash->table * INIT_SIZE); /* 4 */
+ if (hash->table) { /* 5 */
+ hash->nchains = INIT_SIZE; /* 6 */
+ hash->highmark = INIT_SIZE * 2;
+ hash->lowmark = INIT_SIZE / 2;
+ hash->nodecount = 0;
+ hash->maxcount = maxcount;
+ hash->compare = compfun ? compfun : hash_comp_default;
+ hash->function = hashfun ? hashfun : hash_fun_default;
+ hash->allocnode = hnode_alloc;
+ hash->freenode = hnode_free;
+ hash->context = NULL;
+ hash->mask = INIT_MASK;
+ hash->dynamic = 1; /* 7 */
+ clear_table(hash); /* 8 */
+ assert (hash_verify(hash));
+ return hash;
+ }
+ free(hash);
}
return NULL;
*/
void hash_set_allocator(hash_t *hash, hnode_alloc_t al,
- hnode_free_t fr, void *context)
+ hnode_free_t fr, void *context)
{
assert (hash_count(hash) == 0);
assert ((al == 0 && fr == 0) || (al != 0 && fr != 0));
hnode_t *node;
hash_scan_begin(&hs, hash);
while ((node = hash_scan_next(&hs))) {
- hash_scan_delete(hash, node);
- hash->freenode(node, hash->context);
+ hash_scan_delete(hash, node);
+ hash->freenode(node, hash->context);
}
hash->nodecount = 0;
clear_table(hash);
* 2. The user supplied array of pointers hopefully contains nchains nodes.
* 3. See note 7. in hash_create().
* 4. We must dynamically compute the mask from the given power of two table
- * size.
+ * size.
* 5. The user supplied table can't be assumed to contain null pointers,
* so we reset it here.
*/
hash_t *hash_init(hash_t *hash, hashcount_t maxcount,
- hash_comp_t compfun, hash_fun_t hashfun, hnode_t **table,
- hashcount_t nchains)
+ hash_comp_t compfun, hash_fun_t hashfun, hnode_t **table,
+ hashcount_t nchains)
{
- if (hash_val_t_bit == 0) /* 1 */
- compute_bits();
+ if (hash_val_t_bit == 0) /* 1 */
+ compute_bits();
assert (is_power_of_two(nchains));
- hash->table = table; /* 2 */
+ hash->table = table; /* 2 */
hash->nchains = nchains;
hash->nodecount = 0;
hash->maxcount = maxcount;
hash->compare = compfun ? compfun : hash_comp_default;
hash->function = hashfun ? hashfun : hash_fun_default;
- hash->dynamic = 0; /* 3 */
- hash->mask = compute_mask(nchains); /* 4 */
- clear_table(hash); /* 5 */
+ hash->dynamic = 0; /* 3 */
+ hash->mask = compute_mask(nchains); /* 4 */
+ clear_table(hash); /* 5 */
assert (hash_verify(hash));
/*
* Reset the hash scanner so that the next element retrieved by
- * hash_scan_next() shall be the first element on the first non-empty chain.
+ * hash_scan_next() shall be the first element on the first non-empty chain.
* Notes:
* 1. Locate the first non empty chain.
* 2. If an empty chain is found, remember which one it is and set the next
/* 1 */
for (chain = 0; chain < nchains && hash->table[chain] == NULL; chain++)
- ;
+ ;
- if (chain < nchains) { /* 2 */
- scan->chain = chain;
- scan->next = hash->table[chain];
- } else { /* 3 */
- scan->next = NULL;
+ if (chain < nchains) { /* 2 */
+ scan->chain = chain;
+ scan->next = hash->table[chain];
+ } else { /* 3 */
+ scan->next = NULL;
}
}
/*
* Retrieve the next node from the hash table, and update the pointer
- * for the next invocation of hash_scan_next().
+ * for the next invocation of hash_scan_next().
* Notes:
* 1. Remember the next pointer in a temporary value so that it can be
* returned.
hnode_t *hash_scan_next(hscan_t *scan)
{
- hnode_t *next = scan->next; /* 1 */
+ hnode_t *next = scan->next; /* 1 */
hash_t *hash = scan->table;
hash_val_t chain = scan->chain + 1;
hash_val_t nchains = hash->nchains;
- assert (hash_val_t_bit != 0); /* 2 */
-
- if (next) { /* 3 */
- if (next->next) { /* 4 */
- scan->next = next->next;
- } else {
- while (chain < nchains && hash->table[chain] == NULL) /* 5 */
- chain++;
- if (chain < nchains) { /* 6 */
- scan->chain = chain;
- scan->next = hash->table[chain];
- } else {
- scan->next = NULL;
- }
- }
+ assert (hash_val_t_bit != 0); /* 2 */
+
+ if (next) { /* 3 */
+ if (next->next) { /* 4 */
+ scan->next = next->next;
+ } else {
+ while (chain < nchains && hash->table[chain] == NULL) /* 5 */
+ chain++;
+ if (chain < nchains) { /* 6 */
+ scan->chain = chain;
+ scan->next = hash->table[chain];
+ } else {
+ scan->next = NULL;
+ }
+ }
}
return next;
}
* 3. If the table is dynamic and the load factor is already at >= 2,
* grow the table.
* 4. We take the bottom N bits of the hash value to derive the chain index,
- * where N is the base 2 logarithm of the size of the hash table.
+ * where N is the base 2 logarithm of the size of the hash table.
*/
void hash_insert(hash_t *hash, hnode_t *node, const void *key)
assert (hash_val_t_bit != 0);
assert (node->next == NULL);
- assert (hash->nodecount < hash->maxcount); /* 1 */
- assert (hash_lookup(hash, key) == NULL); /* 2 */
+ assert (hash->nodecount < hash->maxcount); /* 1 */
+ assert (hash_lookup(hash, key) == NULL); /* 2 */
- if (hash->dynamic && hash->nodecount >= hash->highmark) /* 3 */
- grow_table(hash);
+ if (hash->dynamic && hash->nodecount >= hash->highmark) /* 3 */
+ grow_table(hash);
hkey = hash->function(key);
- chain = hkey & hash->mask; /* 4 */
+ chain = hkey & hash->mask; /* 4 */
node->key = key;
node->hkey = hkey;
* Notes:
* 1. We hash the key and keep the entire hash value. As an optimization, when
* we descend down the chain, we can compare hash values first and only if
- * hash values match do we perform a full key comparison.
+ * hash values match do we perform a full key comparison.
* 2. To locate the chain from among 2^N chains, we look at the lower N bits of
* the hash value by anding them with the current mask.
* 3. Looping through the chain, we compare the stored hash value inside each
hash_val_t hkey, chain;
hnode_t *nptr;
- hkey = hash->function(key); /* 1 */
- chain = hkey & hash->mask; /* 2 */
+ hkey = hash->function(key); /* 1 */
+ chain = hkey & hash->mask; /* 2 */
- for (nptr = hash->table[chain]; nptr; nptr = nptr->next) { /* 3 */
- if (nptr->hkey == hkey && hash->compare(nptr->key, key) == 0)
- return nptr;
+ for (nptr = hash->table[chain]; nptr; nptr = nptr->next) { /* 3 */
+ if (nptr->hkey == hkey && hash->compare(nptr->key, key) == 0)
+ return nptr;
}
return NULL;
* 1. The node must belong to this hash table, and its key must not have
* been tampered with.
* 2. If this deletion will take the node count below the low mark, we
- * shrink the table now.
+ * shrink the table now.
* 3. Determine which chain the node belongs to, and fetch the pointer
* to the first node in this chain.
* 4. If the node being deleted is the first node in the chain, then
hash_val_t chain;
hnode_t *hptr;
- assert (hash_lookup(hash, node->key) == node); /* 1 */
+ assert (hash_lookup(hash, node->key) == node); /* 1 */
assert (hash_val_t_bit != 0);
if (hash->dynamic && hash->nodecount <= hash->lowmark
- && hash->nodecount > INIT_SIZE)
- shrink_table(hash); /* 2 */
+ && hash->nodecount > INIT_SIZE)
+ shrink_table(hash); /* 2 */
- chain = node->hkey & hash->mask; /* 3 */
+ chain = node->hkey & hash->mask; /* 3 */
hptr = hash->table[chain];
- if (hptr == node) { /* 4 */
- hash->table[chain] = node->next;
+ if (hptr == node) { /* 4 */
+ hash->table[chain] = node->next;
} else {
- while (hptr->next != node) { /* 5 */
- assert (hptr != 0);
- hptr = hptr->next;
- }
- assert (hptr->next == node);
- hptr->next = node->next;
+ while (hptr->next != node) { /* 5 */
+ assert (hptr != 0);
+ hptr = hptr->next;
+ }
+ assert (hptr->next == node);
+ hptr->next = node->next;
}
-
+
hash->nodecount--;
assert (hash_verify(hash));
- node->next = NULL; /* 6 */
+ node->next = NULL; /* 6 */
return node;
}
hnode_t *node = hash->allocnode(hash->context);
if (node) {
- hnode_init(node, data);
- hash_insert(hash, node, key);
- return 1;
+ hnode_init(node, data);
+ hash_insert(hash, node, key);
+ return 1;
}
return 0;
}
hptr = hash->table[chain];
if (hptr == node) {
- hash->table[chain] = node->next;
+ hash->table[chain] = node->next;
} else {
- while (hptr->next != node)
- hptr = hptr->next;
- hptr->next = node->next;
+ while (hptr->next != node)
+ hptr = hptr->next;
+ hptr->next = node->next;
}
-
+
hash->nodecount--;
assert (hash_verify(hash));
node->next = NULL;
hash_val_t chain;
hnode_t *hptr;
- if (hash->dynamic) { /* 1 */
- if (hash->lowmark >= hash->highmark)
- return 0;
- if (!is_power_of_two(hash->highmark))
- return 0;
- if (!is_power_of_two(hash->lowmark))
- return 0;
+ if (hash->dynamic) { /* 1 */
+ if (hash->lowmark >= hash->highmark)
+ return 0;
+ if (!is_power_of_two(hash->highmark))
+ return 0;
+ if (!is_power_of_two(hash->lowmark))
+ return 0;
}
- for (chain = 0; chain < hash->nchains; chain++) { /* 2 */
- for (hptr = hash->table[chain]; hptr != NULL; hptr = hptr->next) {
- if ((hptr->hkey & hash->mask) != chain)
- return 0;
- count++;
- }
+ for (chain = 0; chain < hash->nchains; chain++) { /* 2 */
+ for (hptr = hash->table[chain]; hptr != NULL; hptr = hptr->next) {
+ if ((hptr->hkey & hash->mask) != chain)
+ return 0;
+ count++;
+ }
}
if (count != hash->nodecount)
- return 0;
+ return 0;
return 1;
}
{
hnode_t *node = malloc(sizeof *node);
if (node) {
- node->data = data;
- node->next = NULL;
+ node->data = data;
+ node->next = NULL;
}
return node;
}
/*
- * Initialize a client-supplied node
+ * Initialize a client-supplied node
*/
hnode_t *hnode_init(hnode_t *hnode, void *data)
static hash_val_t hash_fun_default(const void *key)
{
static unsigned long randbox[] = {
- 0x49848f1bU, 0xe6255dbaU, 0x36da5bdcU, 0x47bf94e9U,
- 0x8cbcce22U, 0x559fc06aU, 0xd268f536U, 0xe10af79aU,
- 0xc1af4d69U, 0x1d2917b5U, 0xec4c304dU, 0x9ee5016cU,
- 0x69232f74U, 0xfead7bb3U, 0xe9089ab6U, 0xf012f6aeU,
+ 0x49848f1bU, 0xe6255dbaU, 0x36da5bdcU, 0x47bf94e9U,
+ 0x8cbcce22U, 0x559fc06aU, 0xd268f536U, 0xe10af79aU,
+ 0xc1af4d69U, 0x1d2917b5U, 0xec4c304dU, 0x9ee5016cU,
+ 0x69232f74U, 0xfead7bb3U, 0xe9089ab6U, 0xf012f6aeU,
};
const unsigned char *str = key;
hash_val_t acc = 0;
while (*str) {
- acc ^= randbox[(*str + acc) & 0xf];
- acc = (acc << 1) | (acc >> 31);
- acc &= 0xffffffffU;
- acc ^= randbox[((*str++ >> 4) + acc) & 0xf];
- acc = (acc << 2) | (acc >> 30);
- acc &= 0xffffffffU;
+ acc ^= randbox[(*str + acc) & 0xf];
+ acc = (acc << 1) | (acc >> 31);
+ acc &= 0xffffffffU;
+ acc ^= randbox[((*str++ >> 4) + acc) & 0xf];
+ acc = (acc << 2) | (acc >> 30);
+ acc &= 0xffffffffU;
}
return acc;
}
+/* From http://www.azillionmonkeys.com/qed/hash.html */
+#undef get16bits
+#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
+ || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
+#define get16bits(d) (*((const uint16_t *) (d)))
+#endif
+
+#if !defined (get16bits)
+#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
+ +(uint32_t)(((const uint8_t *)(d))[0]) )
+#endif
+
static int hash_comp_default(const void *key1, const void *key2)
{
return strcmp(key1, key2);
#ifdef KAZLIB_TEST_MAIN
+static hash_val_t hash_fun2(const void *key)
+{
+ int len, rem;
+ const unsigned char *data = key;
+ hash_val_t hash = 0, tmp = 0;
+
+ len = strlen((char *)data);
+
+ rem = len & 3;
+ len >>= 2;
+
+ /* Main loop */
+ for (;len > 0; len--) {
+ hash += get16bits (data);
+ tmp = (get16bits (data+2) << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ data += 2*sizeof (uint16_t);
+ hash += hash >> 11;
+ }
+
+ /* Handle end cases */
+ switch (rem) {
+ case 3: hash += get16bits (data);
+ hash ^= hash << 16;
+ hash ^= data[sizeof (uint16_t)] << 18;
+ hash += hash >> 11;
+ break;
+ case 2: hash += get16bits (data);
+ hash ^= hash << 11;
+ hash += hash >> 17;
+ break;
+ case 1: hash += *data;
+ hash ^= hash << 10;
+ hash += hash >> 1;
+ }
+
+ /* Force "avalanching" of final 127 bits */
+ hash ^= hash << 3;
+ hash += hash >> 5;
+ hash ^= hash << 4;
+ hash += hash >> 17;
+ hash ^= hash << 25;
+ hash += hash >> 6;
+
+ return hash;
+}
+
#include <stdio.h>
#include <ctype.h>
#include <stdarg.h>
static int tokenize(char *string, ...)
{
- char **tokptr;
+ char **tokptr;
va_list arglist;
int tokcount = 0;
va_start(arglist, string);
tokptr = va_arg(arglist, char **);
while (tokptr) {
- while (*string && isspace((unsigned char) *string))
- string++;
- if (!*string)
- break;
- *tokptr = string;
- while (*string && !isspace((unsigned char) *string))
- string++;
- tokptr = va_arg(arglist, char **);
- tokcount++;
- if (!*string)
- break;
- *string++ = 0;
+ while (*string && isspace((unsigned char) *string))
+ string++;
+ if (!*string)
+ break;
+ *tokptr = string;
+ while (*string && !isspace((unsigned char) *string))
+ string++;
+ tokptr = va_arg(arglist, char **);
+ tokcount++;
+ if (!*string)
+ break;
+ *string++ = 0;
}
va_end(arglist);
int sz = strlen(str) + 1;
char *new = malloc(sz);
if (new)
- memcpy(new, str, sz);
+ memcpy(new, str, sz);
return new;
}
static int count;
if (count < 5)
- return few + count++;
+ return few + count++;
return NULL;
}
int main(void)
{
input_t in;
- hash_t *h = hash_create(HASHCOUNT_T_MAX, 0, 0);
+ hash_t *h = hash_create(HASHCOUNT_T_MAX, 0, hash_fun2);
hnode_t *hn;
hscan_t hs;
char *tok1, *tok2, *val;
int prompt = 0;
char *help =
- "a <key> <val> add value to hash table\n"
- "d <key> delete value from hash table\n"
- "l <key> lookup value in hash table\n"
- "n show size of hash table\n"
- "c show number of entries\n"
- "t dump whole hash table\n"
- "+ increase hash table (private func)\n"
- "- decrease hash table (private func)\n"
- "b print hash_t_bit value\n"
- "p turn prompt on\n"
- "s switch to non-functioning allocator\n"
- "q quit";
-
- if (!h)
- puts("hash_create failed");
+ "a <key> <val> add value to hash table\n"
+ "d <key> delete value from hash table\n"
+ "l <key> lookup value in hash table\n"
+ "n show size of hash table\n"
+ "c show number of entries\n"
+ "t dump whole hash table\n"
+ "+ increase hash table (private func)\n"
+ "- decrease hash table (private func)\n"
+ "b print hash_t_bit value\n"
+ "p turn prompt on\n"
+ "s switch to non-functioning allocator\n"
+ "q quit";
+
+ if (!h) {
+ puts("hash_create failed");
+ return 1;
+ }
for (;;) {
- if (prompt)
- putchar('>');
- fflush(stdout);
-
- if (!fgets(in, sizeof(input_t), stdin))
- break;
-
- switch(in[0]) {
- case '?':
- puts(help);
- break;
- case 'b':
- printf("%d\n", hash_val_t_bit);
- break;
- case 'a':
- if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
- puts("what?");
- break;
- }
- key = dupstring(tok1);
- val = dupstring(tok2);
-
- if (!key || !val) {
- puts("out of memory");
- free((void *) key);
- free(val);
- }
-
- if (!hash_alloc_insert(h, key, val)) {
- puts("hash_alloc_insert failed");
- free((void *) key);
- free(val);
- break;
- }
- break;
- case 'd':
- if (tokenize(in+1, &tok1, (char **) 0) != 1) {
- puts("what?");
- break;
- }
- hn = hash_lookup(h, tok1);
- if (!hn) {
- puts("hash_lookup failed");
- break;
- }
- val = hnode_get(hn);
- key = hnode_getkey(hn);
- hash_scan_delfree(h, hn);
- free((void *) key);
- free(val);
- break;
- case 'l':
- if (tokenize(in+1, &tok1, (char **) 0) != 1) {
- puts("what?");
- break;
- }
- hn = hash_lookup(h, tok1);
- if (!hn) {
- puts("hash_lookup failed");
- break;
- }
- val = hnode_get(hn);
- puts(val);
- break;
- case 'n':
- printf("%lu\n", (unsigned long) hash_size(h));
- break;
- case 'c':
- printf("%lu\n", (unsigned long) hash_count(h));
- break;
- case 't':
- hash_scan_begin(&hs, h);
- while ((hn = hash_scan_next(&hs)))
- printf("%s\t%s\n", (char*) hnode_getkey(hn),
- (char*) hnode_get(hn));
- break;
- case '+':
- grow_table(h); /* private function */
- break;
- case '-':
- shrink_table(h); /* private function */
- break;
- case 'q':
- exit(0);
- break;
- case '\0':
- break;
- case 'p':
- prompt = 1;
- break;
- case 's':
- hash_set_allocator(h, new_node, del_node, NULL);
- break;
- default:
- putchar('?');
- putchar('\n');
- break;
- }
+ if (prompt)
+ putchar('>');
+ fflush(stdout);
+
+ if (!fgets(in, sizeof(input_t), stdin))
+ break;
+
+ switch(in[0]) {
+ case '?':
+ puts(help);
+ break;
+ case 'b':
+ printf("%d\n", hash_val_t_bit);
+ break;
+ case 'a':
+ if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
+ puts("what?");
+ break;
+ }
+ key = dupstring(tok1);
+ val = dupstring(tok2);
+
+ if (!key || !val) {
+ puts("out of memory");
+ free((void *) key);
+ free(val);
+ break;
+ }
+
+ if (!hash_alloc_insert(h, key, val)) {
+ puts("hash_alloc_insert failed");
+ free((void *) key);
+ free(val);
+ break;
+ }
+ break;
+ case 'd':
+ if (tokenize(in+1, &tok1, (char **) 0) != 1) {
+ puts("what?");
+ break;
+ }
+ hn = hash_lookup(h, tok1);
+ if (!hn) {
+ puts("hash_lookup failed");
+ break;
+ }
+ val = hnode_get(hn);
+ key = hnode_getkey(hn);
+ hash_scan_delfree(h, hn);
+ free((void *) key);
+ free(val);
+ break;
+ case 'l':
+ if (tokenize(in+1, &tok1, (char **) 0) != 1) {
+ puts("what?");
+ break;
+ }
+ hn = hash_lookup(h, tok1);
+ if (!hn) {
+ puts("hash_lookup failed");
+ break;
+ }
+ val = hnode_get(hn);
+ puts(val);
+ break;
+ case 'n':
+ printf("%lu\n", (unsigned long) hash_size(h));
+ break;
+ case 'c':
+ printf("%lu\n", (unsigned long) hash_count(h));
+ break;
+ case 't':
+ hash_scan_begin(&hs, h);
+ while ((hn = hash_scan_next(&hs)))
+ printf("%s\t%s\n", (char*) hnode_getkey(hn),
+ (char*) hnode_get(hn));
+ break;
+ case '+':
+ grow_table(h); /* private function */
+ break;
+ case '-':
+ shrink_table(h); /* private function */
+ break;
+ case 'q':
+ exit(0);
+ break;
+ case '\0':
+ break;
+ case 'p':
+ prompt = 1;
+ break;
+ case 's':
+ hash_set_allocator(h, new_node, del_node, NULL);
+ break;
+ default:
+ putchar('?');
+ putchar('\n');
+ break;
+ }
}
return 0;