patch-2.1.44 linux/include/linux/ghash.h

• Lines: 219
• Date: Mon Jul 7 08:24:28 1997
• Orig file: v2.1.43/linux/include/linux/ghash.h
• Orig date: Wed Dec 31 16:00:00 1969

diff -u --recursive --new-file v2.1.43/linux/include/linux/ghash.h linux/include/linux/ghash.h
@@ -0,0 +1,218 @@
+/*
+ * 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