Linux/Unix编程

开发平台：
Unix_Linux

ghash.h：源码内容
							/*
 * include/linux/ghash.h -- generic hashing with fuzzy retrieval
 *
 * (C) 1997 Thomas Schoebel-Theuer
 *
 * The algorithms implemented here seem to be a completely new invention,
 * and I'll publish the fundamentals in a paper.
 */
#ifndef _GHASH_H
#define _GHASH_H
/* HASHSIZE _must_ be a power of two!!! */
#define DEF_HASH_FUZZY_STRUCTS(NAME,HASHSIZE,TYPE) 
struct NAME##_table {
	TYPE * hashtable[HASHSIZE];
	TYPE * sorted_list;
	int nr_entries;
};
struct NAME##_ptrs {
	TYPE * next_hash;
	TYPE * prev_hash;
	TYPE * next_sorted;
	TYPE * prev_sorted;
};
#define DEF_HASH_FUZZY(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)
LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)
{
	int ix = HASHFN(elem->KEY);
	TYPE ** base = &tbl->hashtable[ix];
	TYPE * ptr = *base;
	TYPE * prev = NULL;
	tbl->nr_entries++;
	while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {
		base = &ptr->PTRS.next_hash;
		prev = ptr;
		ptr = *base;
	}
	elem->PTRS.next_hash = ptr;
	elem->PTRS.prev_hash = prev;
	if(ptr) {
		ptr->PTRS.prev_hash = elem;
	}
	*base = elem;
	ptr = prev;
	if(!ptr) {
		ptr = tbl->sorted_list;
		prev = NULL;
	} else {
		prev = ptr->PTRS.prev_sorted;
	}
	while(ptr) {
		TYPE * next = ptr->PTRS.next_hash;
		if(next && KEYCMP(next->KEY, elem->KEY)) {
			prev = ptr;
			ptr = next;
		} else if(KEYCMP(ptr->KEY, elem->KEY)) {
			prev = ptr;
			ptr = ptr->PTRS.next_sorted;
		} else
			break;
	}
	elem->PTRS.next_sorted = ptr;
	elem->PTRS.prev_sorted = prev;
	if(ptr) {
		ptr->PTRS.prev_sorted = elem;
	}
	if(prev) {
		prev->PTRS.next_sorted = elem;
	} else {
		tbl->sorted_list = elem;
	}
}
LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)
{
	TYPE * next = elem->PTRS.next_hash;
	TYPE * prev = elem->PTRS.prev_hash;
	tbl->nr_entries--;
	if(next)
		next->PTRS.prev_hash = prev;
	if(prev)
		prev->PTRS.next_hash = next;
	else {
		int ix = HASHFN(elem->KEY);
		tbl->hashtable[ix] = next;
	}
	next = elem->PTRS.next_sorted;
	prev = elem->PTRS.prev_sorted;
	if(next)
		next->PTRS.prev_sorted = prev;
	if(prev)
		prev->PTRS.next_sorted = next;
	else
		tbl->sorted_list = next;
}
LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)
{
	int ix = hashfn(pos);
	TYPE * ptr = tbl->hashtable[ix];
	while(ptr && KEYCMP(ptr->KEY, pos))
		ptr = ptr->PTRS.next_hash;
	if(ptr && !KEYEQ(ptr->KEY, pos))
		ptr = NULL;
	return ptr;
}
LINKAGE TYPE * find_##NAME##_hash_fuzzy(struct NAME##_table * tbl, KEYTYPE pos)
{
	int ix;
	int offset;
	TYPE * ptr;
	TYPE * next;
	ptr = tbl->sorted_list;
	if(!ptr || KEYCMP(pos, ptr->KEY))
		return NULL;
	ix = HASHFN(pos);
	offset = HASHSIZE;
	do {
		offset >>= 1;
		next = tbl->hashtable[(ix+offset) & ((HASHSIZE)-1)];
		if(next && (KEYCMP(next->KEY, pos) || KEYEQ(next->KEY, pos))
		   && KEYCMP(ptr->KEY, next->KEY))
			ptr = next;
	} while(offset);
	for(;;) {
		next = ptr->PTRS.next_hash;
		if(next) {
			if(KEYCMP(next->KEY, pos)) {
				ptr = next;
				continue;
			}
		}
		next = ptr->PTRS.next_sorted;
		if(next && KEYCMP(next->KEY, pos)) {
			ptr = next;
			continue;
		}
		return ptr;
	}
	return NULL;
}
#define DEF_HASH_STRUCTS(NAME,HASHSIZE,TYPE) 
struct NAME##_table {
	TYPE * hashtable[HASHSIZE];
	int nr_entries;
};
struct NAME##_ptrs {
	TYPE * next_hash;
	TYPE * prev_hash;
};
#define DEF_HASH(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)
LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)
{
	int ix = HASHFN(elem->KEY);
	TYPE ** base = &tbl->hashtable[ix];
	TYPE * ptr = *base;
	TYPE * prev = NULL;
	tbl->nr_entries++;
	while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {
		base = &ptr->PTRS.next_hash;
		prev = ptr;
		ptr = *base;
	}
	elem->PTRS.next_hash = ptr;
	elem->PTRS.prev_hash = prev;
	if(ptr) {
		ptr->PTRS.prev_hash = elem;
	}
	*base = elem;
}
LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)
{
	TYPE * next = elem->PTRS.next_hash;
	TYPE * prev = elem->PTRS.prev_hash;
	tbl->nr_entries--;
	if(next)
		next->PTRS.prev_hash = prev;
	if(prev)
		prev->PTRS.next_hash = next;
	else {
		int ix = HASHFN(elem->KEY);
		tbl->hashtable[ix] = next;
	}
}
LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)
{
	int ix = hashfn(pos);
	TYPE * ptr = tbl->hashtable[ix];
	while(ptr && KEYCMP(ptr->KEY, pos))
		ptr = ptr->PTRS.next_hash;
	if(ptr && !KEYEQ(ptr->KEY, pos))
		ptr = NULL;
	return ptr;
}
#endif

						