hash.c

一些常用的数据结构库

{
    hash_val_t hkey, chain;

    assert (hash_val_t_bit != 0);
    assert (node->next == NULL);
    assert (hash->nodecount < hash->maxcount);	/* 1 */
    assert (hash_lookup(hash, key) == NULL);	/* 2 */

    if (hash->dynamic && hash->nodecount >= hash->highmark)	/* 3 */
	grow_table(hash);

    hkey = hash->function(key);
    chain = hkey & hash->mask;	/* 4 */

    node->key = key;
    node->hkey = hkey;
    node->next = hash->table[chain];
    hash->table[chain] = node;
    hash->nodecount++;

    assert (hash_verify(hash));
}

/*
 * Find a node in the hash table and return a pointer to it.
 * 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. 
 * 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
 *    node against our computed hash. If they match, then we do a full
 *    comparison between the unhashed keys. If these match, we have located the
 *    entry.
 */

hnode_t *hash_lookup(hash_t *hash, const void *key)
{
    hash_val_t hkey, chain;
    hnode_t *nptr;

    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;
    }

    return NULL;
}

/*
 * Delete the given node from the hash table.  Since the chains
 * are singly linked, we must locate the start of the node's chain
 * and traverse.
 * Notes:
 * 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. 
 * 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
 *    simply update the chain head pointer.
 * 5. Otherwise advance to the node's predecessor, and splice out
 *    by updating the predecessor's next pointer.
 * 6. Indicate that the node is no longer in a hash table.
 */

hnode_t *hash_delete(hash_t *hash, hnode_t *node)
{
    hash_val_t chain;
    hnode_t *hptr;

    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 */

    chain = node->hkey & hash->mask;			/* 3 */
    hptr = hash->table[chain];

    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;
    }
	
    hash->nodecount--;
    assert (hash_verify(hash));

    node->next = NULL;					/* 6 */
    return node;
}

int hash_alloc_insert(hash_t *hash, const void *key, void *data)
{
    hnode_t *node = hash->allocnode(hash->context);

    if (node) {
	hnode_init(node, data);
	hash_insert(hash, node, key);
	return 1;
    }
    return 0;
}

void hash_delete_free(hash_t *hash, hnode_t *node)
{
    hash_delete(hash, node);
    hash->freenode(node, hash->context);
}

/*
 *  Exactly like hash_delete, except does not trigger table shrinkage. This is to be
 *  used from within a hash table scan operation. See notes for hash_delete.
 */

hnode_t *hash_scan_delete(hash_t *hash, hnode_t *node)
{
    hash_val_t chain;
    hnode_t *hptr;

    assert (hash_lookup(hash, node->key) == node);
    assert (hash_val_t_bit != 0);

    chain = node->hkey & hash->mask;
    hptr = hash->table[chain];

    if (hptr == node) {
	hash->table[chain] = node->next;
    } else {
	while (hptr->next != node) 
	    hptr = hptr->next;
	hptr->next = node->next;
    }
	
    hash->nodecount--;
    assert (hash_verify(hash));
    node->next = NULL;

    return node;
}

/*
 * Like hash_delete_free but based on hash_scan_delete.
 */

void hash_scan_delfree(hash_t *hash, hnode_t *node)
{
    hash_scan_delete(hash, node);
    hash->freenode(node, hash->context);
}

/*
 * Verify whether the given object is a valid hash table. This means
 * Notes:
 * 1. If the hash table is dynamic, verify whether the high and
 *    low expansion/shrinkage thresholds are powers of two.
 * 2. Count all nodes in the table, and test each hash value
 *    to see whether it is correct for the node's chain.
 */

int hash_verify(hash_t *hash)
{
    hashcount_t count = 0;
    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;
    }

    for (chain = 0; chain < hash->nchains; chain++) {	/* 2 */
	for (hptr = hash->table[chain]; hptr != 0; hptr = hptr->next) {
	    if ((hptr->hkey & hash->mask) != chain)
		return 0;
	    count++;
	}
    }

    if (count != hash->nodecount)
	return 0;

    return 1;
}

/*
 * Test whether the hash table is full and return 1 if this is true,
 * 0 if it is false.
 */

#undef hash_isfull
int hash_isfull(hash_t *hash)
{
    return hash->nodecount == hash->maxcount;
}

/*
 * Test whether the hash table is empty and return 1 if this is true,
 * 0 if it is false.
 */

#undef hash_isempty
int hash_isempty(hash_t *hash)
{
    return hash->nodecount == 0;
}

static hnode_t *hnode_alloc(void *context)
{
    return malloc(sizeof *hnode_alloc(NULL));
}

static void hnode_free(hnode_t *node, void *context)
{
    free(node);
}


/*
 * Create a hash table node dynamically and assign it the given data.
 */

hnode_t *hnode_create(void *data)
{
    hnode_t *node = malloc(sizeof *node);
    if (node) {
	node->data = data;
	node->next = NULL;
    }
    return node;
}

/*
 * Initialize a client-supplied node 
 */

hnode_t *hnode_init(hnode_t *hnode, void *data)
{
    hnode->data = data;
    hnode->next = NULL;
    return hnode;
}

/*
 * Destroy a dynamically allocated node.
 */

void hnode_destroy(hnode_t *hnode)
{
    free(hnode);
}

#undef hnode_put
void hnode_put(hnode_t *node, void *data)
{
    node->data = data;
}

#undef hnode_get
void *hnode_get(hnode_t *node)
{
    return node->data;
}

#undef hnode_getkey
const void *hnode_getkey(hnode_t *node)
{
    return node->key;
}

#undef hash_count
hashcount_t hash_count(hash_t *hash)
{
    return hash->nodecount;
}

#undef hash_size
hashcount_t hash_size(hash_t *hash)
{
    return hash->nchains;
}

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,
    };

    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;
    }
    return acc;
}

static int hash_comp_default(const void *key1, const void *key2)
{
    return strcmp(key1, key2);
}

#ifdef KAZLIB_TEST_MAIN

#include <stdio.h>
#include <ctype.h>
#include <stdarg.h>

typedef char input_t[256];

static int tokenize(char *string, ...)
{
    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;
    }
    va_end(arglist);

    return tokcount;
}

static char *dupstring(char *str)
{
    int sz = strlen(str) + 1;
    char *new = malloc(sz);
    if (new)
	memcpy(new, str, sz);
    return new;
}

static hnode_t *new_node(void *c)
{
    static hnode_t few[5];
    static int count;

    if (count < 5)
	return few + count++;

    return NULL;
}

static void del_node(hnode_t *n, void *c)
{
}

int main(void)
{
    input_t in;
    hash_t *h = hash_create(HASHCOUNT_T_MAX, 0, 0);
    hnode_t *hn;
    hscan_t hs;
    char *tok1, *tok2, *val;
    const char *key;
    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");

    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;
	}
    }

    return 0;
}

#endif