hash.c

新的radius程序

}


/*
 *	Internal find a node routine.
 */
static lrad_hash_entry_t *lrad_hash_table_find(lrad_hash_table_t *ht,
					       const void *data)
{
	uint32_t key;
	uint32_t entry;
	uint32_t reversed;

	if (!ht) return NULL;

	key = ht->hash(data);
	entry = key & ht->mask;
	reversed = reverse(key);

	if (!ht->buckets[entry]) lrad_hash_table_fixup(ht, entry);

	return list_find(ht, ht->buckets[entry], reversed, data);
}


/*
 *	Replace old data with new data, OR insert if there is no old.
 */
int lrad_hash_table_replace(lrad_hash_table_t *ht, void *data)
{
	lrad_hash_entry_t *node;

	if (!ht || !data) return 0;

	node = lrad_hash_table_find(ht, data);
	if (!node) return lrad_hash_table_insert(ht, data);

	if (ht->free) ht->free(node->data);
	node->data = data;

	return 1;
}


/*
 *	Find data from a template
 */
void *lrad_hash_table_finddata(lrad_hash_table_t *ht, const void *data)
{
	lrad_hash_entry_t *node;

	node = lrad_hash_table_find(ht, data);
	if (!node) return NULL;

	return node->data;
}



/*
 *	Yank an entry from the hash table, without freeing the data.
 */
void *lrad_hash_table_yank(lrad_hash_table_t *ht, const void *data)
{
	uint32_t key;
	uint32_t entry;
	uint32_t reversed;
	void *old;
	lrad_hash_entry_t *node;

	if (!ht) return NULL;

	key = ht->hash(data);
	entry = key & ht->mask;
	reversed = reverse(key);

	if (!ht->buckets[entry]) lrad_hash_table_fixup(ht, entry);

	node = list_find(ht, ht->buckets[entry], reversed, data);
	if (!node) return NULL;

	list_delete(ht, &ht->buckets[entry], node);
	ht->num_elements--;

	old = node->data;
	free(node);

	return old;
}


/*
 *	Delete a piece of data from the hash table.
 */
int lrad_hash_table_delete(lrad_hash_table_t *ht, const void *data)
{
	void *old;

	old = lrad_hash_table_yank(ht, data);
	if (!old) return 0;

	if (ht->free) ht->free(old);

	return 1;
}


/*
 *	Free a hash table
 */
void lrad_hash_table_free(lrad_hash_table_t *ht)
{
	int i;
	lrad_hash_entry_t *node, *next;

	if (!ht) return;

	/*
	 *	Walk over the buckets, freeing them all.
	 */
	for (i = 0; i < ht->num_buckets; i++) {
		if (ht->buckets[i]) for (node = ht->buckets[i];
					 node != &ht->null;
					 node = next) {
			next = node->next;
			
			if (!node->data) continue; /* dummy entry */
			
			if (ht->free) ht->free(node->data);
			free(node);
		}
	}

	free(ht->buckets);
	free(ht);
}


/*
 *	Count number of elements
 */
int lrad_hash_table_num_elements(lrad_hash_table_t *ht)
{
	if (!ht) return 0;

	return ht->num_elements;
}


/*
 *	Walk over the nodes, allowing deletes & inserts to happen.
 */
int lrad_hash_table_walk(lrad_hash_table_t *ht,
			 lrad_hash_table_walk_t callback,
			 void *context)
{
	int i, rcode;;

	if (!ht || !callback) return 0;

	for (i = ht->num_buckets - 1; i >= 0; i--) {
		lrad_hash_entry_t *node, *next;

		/*
		 *	Ensure that the current bucket is filled.
		 */
		if (!ht->buckets[i]) lrad_hash_table_fixup(ht, i);

		for (node = ht->buckets[i]; node != &ht->null; node = next) {
			next = node->next;

			rcode = callback(context, node->data);
			if (rcode != 0) return rcode;
		}
	}

	return 0;
}


#ifdef TESTING
/*
 *	Show what the hash table is doing.
 */
int lrad_hash_table_info(lrad_hash_table_t *ht)
{
	int i, a, collisions, uninitialized;
	int array[256];

	if (!ht) return 0;

	uninitialized = collisions = 0;
	memset(array, 0, sizeof(array));

	for (i = 0; i < ht->num_buckets; i++) {
		uint32_t key;
		int load;
		lrad_hash_entry_t *node, *next;

		/*
		 *	If we haven't inserted or looked up an entry
		 *	in a bucket, it's uninitialized.
		 */
		if (!ht->buckets[i]) {
			uninitialized++;
			continue;
		}

		load = 0;
		key = ~0;
		for (node = ht->buckets[i]; node != &ht->null; node = next) {
			if (node->reversed == key) {
				collisions++;
			} else {
				key = node->reversed;
			}
			next = node->next;
			load++;
		}

		if (load > 255) load = 255;
		array[load]++;
	}

	printf("HASH TABLE %p\tbuckets: %d\t(%d uninitialized)\n", ht,
		ht->num_buckets, uninitialized);
	printf("\tnum entries %d\thash collisions %d\n",
		ht->num_elements, collisions);

	a = 0;
	for (i = 1; i < 256; i++) {
		if (!array[i]) continue;
		printf("%d\t%d\n", i, array[i]);

		/*
		 *	Since the entries are ordered, the lookup cost
		 *	for any one element in a chain is (on average)
		 *	the cost of walking half of the chain.
		 */
		if (i > 1) {
			a += array[i] * i;
		}
	}
	a /= 2;
	a += array[1];

	printf("\texpected lookup cost = %d/%d or %f\n\n",
	       ht->num_elements, a,
	       (float) ht->num_elements / (float) a);

	return 0;
}
#endif


#define FNV_MAGIC_INIT (0x811c9dc5)
#define FNV_MAGIC_PRIME (0x01000193)

/*
 *	A fast hash function.  For details, see:
 *
 *	http://www.isthe.com/chongo/tech/comp/fnv/
 *
 *	Which also includes public domain source.  We've re-written
 *	it here for our purposes.
 */
uint32_t lrad_hash(const void *data, size_t size)
{
	const uint8_t *p = data;
	const uint8_t *q = p + size;
	uint32_t      hash = FNV_MAGIC_INIT;

	/*
	 *	FNV-1 hash each octet in the buffer
	 */
	while (p != q) {
		/*
		 *	Multiple by 32-bit magic FNV prime, mod 2^32
		 */
		hash *= FNV_MAGIC_PRIME;
#if 0
		/*
		 *	Potential optimization.
		 */
		hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
#endif
		/*
		 *	XOR the 8-bit quantity into the bottom of
		 *	the hash.
		 */
		hash ^= (uint32_t) (*p++);
    }

    return hash;
}

/*
 *	Continue hashing data.
 */
uint32_t lrad_hash_update(const void *data, size_t size, uint32_t hash)
{
	const uint8_t *p = data;
	const uint8_t *q = p + size;

	while (p != q) {
		hash *= FNV_MAGIC_PRIME;
		hash ^= (uint32_t) (*p++);
    }

    return hash;

}

/*
 *	Return a "folded" hash, where the lower "bits" are the
 *	hash, and the upper bits are zero.
 *
 *	If you need a non-power-of-two hash, cope.
 */
uint32_t lrad_hash_fold(uint32_t hash, int bits)
{
	int count;
	uint32_t result;

	if ((bits <= 0) || (bits >= 32)) return hash;

	result = hash;

	/*
	 *	Never use the same bits twice in an xor.
	 */
	for (count = 0; count < 32; count += bits) {
		hash >>= bits;
		result ^= hash;
	}

	return result & (((uint32_t) (1 << bits)) - 1);
}


/*
 *	Hash a C string, so we loop over it once.
 */
uint32_t lrad_hash_string(const char *p)
{
	uint32_t      hash = FNV_MAGIC_INIT;

	while (*p) {
		hash *= FNV_MAGIC_PRIME;
		hash ^= (uint32_t) (*p++);
	}

	return hash;
}


#ifdef TESTING
/*
 *  cc -g -DTESTING -I ../include hash.c -o hash
 *
 *  ./hash
 */

#include <stdio.h>
#include <stdlib.h>

static uint32_t hash_int(const void *data)
{
	return lrad_hash((int *) data, sizeof(int));
}

#define MAX 1024*1024
int main(int argc, char **argv)
{
	int i, *p, *q, k;
	lrad_hash_table_t *ht;
	int *array;

	ht = lrad_hash_table_create(hash_int, NULL, NULL);
	if (!ht) {
		fprintf(stderr, "Hash create failed\n");
		exit(1);
	}

	array = malloc(sizeof(int) * MAX);
	if (!array) exit(1);

	for (i = 0; i < MAX; i++) {
		p = array + i;
		*p = i;

		if (!lrad_hash_table_insert(ht, p)) {
			fprintf(stderr, "Failed insert %08x\n", i);
			exit(1);
		}
#ifdef TEST_INSERT
		q = lrad_hash_table_finddata(ht, p);
		if (q != p) {
			fprintf(stderr, "Bad data %d\n", i);
			exit(1);
		}
#endif
	}

	lrad_hash_table_info(ht);

	/*
	 *	Build this to see how lookups result in shortening
	 *	of the hash chains.
	 */
	if (1) {
		for (i = 0; i < MAX ; i++) {
			q = lrad_hash_table_finddata(ht, &i);
			if (!q || *q != i) {
				fprintf(stderr, "Failed finding %d\n", i);
				exit(1);
			}
			
#if 0
			if (!lrad_hash_table_delete(ht, &i)) {
				fprintf(stderr, "Failed deleting %d\n", i);
				exit(1);
			}
			q = lrad_hash_table_finddata(ht, &i);
			if (q) {
				fprintf(stderr, "Failed to delete %08x\n", i);
				exit(1);
			}
#endif
		}

		lrad_hash_table_info(ht);
	}

	lrad_hash_table_free(ht);
	free(array);

	exit(0);
}
#endif