hash.c

linuxFedure4环境下串口编程后台运行状态机

#include"hash.h"
#include<stdlib.h>
#include<string.h>
#include<strings.h>
#include<stdio.h>

#ifndef DEBUG
#define ifdbg if(0)
#else
#define ifdbg if(1)
#endif

static void outofmemory()
{
	ifdbg printf("out of memory!\n");
}

/**
 * hash unsigned char[] into unsigned int % bucket_num
 * modified based on linux's dentry hash function
 */
static unsigned int 
hash(const unsigned char *key, unsigned int bucket_num)
{
	unsigned int i, hash=0;
	for(i=0; i<MAX_KEY_LEN && key[i]!='\0'; ++i)
		hash+=((key[i]>>4)+(key[i]<<4))*11u;
	hash=hash ^ ((hash ^ 0x9e370001u)/bucket_num);
	hash%=bucket_num;
	ifdbg printf("hash value for %s: %d\n", key, hash);
	return hash;
}

struct hash_table *
hash_table_create(int bucket_num)
{
	struct hash_table *table=malloc(sizeof(struct hash_table));
	if(table==NULL){
		outofmemory();
		return NULL;
	}
	table->n=bucket_num;
	table->buckets=malloc(bucket_num*sizeof(struct list_head));
	if(table->buckets==NULL){
		outofmemory();
		free(table);
		return NULL;
	}

	/* initialize all the buckets */
	while(bucket_num-->0)
		INIT_LIST_HEAD(&table->buckets[bucket_num]);

	INIT_LIST_HEAD(&table->all);

	ifdbg printf("hash table with %d buckets created\n", table->n);
	return table;
}

void 
hash_table_add(struct hash_table *table, struct hash_table_entry* entry)
{
	/* add the entry to the RIGHT bucket, and that's it */
	list_add(&entry->bucket, &table->buckets[hash(entry->key, table->n)]);
	list_add(&entry->all, &table->all);
	ifdbg printf("hash entry with key %s added\n", entry->key);
}

struct hash_table_entry *
hash_table_get(struct hash_table *table, const unsigned char *key)
{
	struct hash_table_entry *entry;
	/* find the right bucket, iterate all entries in it and look
	 * for the exact match of the key */
	struct list_head *head=&table->buckets[hash(key, table->n)], *pos;
	list_for_each(pos, head){
		entry=list_entry(pos, struct hash_table_entry, bucket);
		if(strcasecmp(key, entry->key)==0){
			ifdbg printf("hash entry with key %s retrieved\n", 
					entry->key);
			return entry;
		}
	}

	ifdbg printf("retriving hash entry with key %s failed\n", key);
	return NULL;
}

void
hash_table_free(struct hash_table *table)
{
	free(table->buckets);
	free(table);
	ifdbg printf("hash table with %d buckets freed\n", table->n);
}