From: Christoph Hellwig <hch@lst.de>
To: akpm@osdl.org
Cc: linux-kernel@vger.kernel.org
Subject: [PATCH] move ghash.h were it does less harm
Date: Sat, 28 Aug 2004 12:55:12 +0200 [thread overview]
Message-ID: <20040828105512.GA11067@lst.de> (raw)
grmp, UML folks re-added ghash.h despite beeing told repeatedly not to
do so. At least move it to arch/um/ so people don't start to use it
again when they are on similar drugs as thge UML people.
diff -uNr linux-2.6.9-rc1-mm1/arch/um/kernel/ghash.h linux-2.6.9-rc1-mm1-hch/arch/um/kernel/ghash.h
--- linux-2.6.9-rc1-mm1/arch/um/kernel/ghash.h 1970-01-01 01:00:00.000000000 +0100
+++ linux-2.6.9-rc1-mm1-hch/arch/um/kernel/ghash.h 2004-08-28 12:17:39.033454000 +0200
@@ -0,0 +1,236 @@
+/*
+ * 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;\
+}
+
+/* LINKAGE - empty or "static", depending on whether you want the definitions to
+ * be public or not
+ * NAME - a string to stick in names to make this hash table type distinct from
+ * any others
+ * HASHSIZE - number of buckets
+ * TYPE - type of data contained in the buckets - must be a structure, one
+ * field is of type NAME_ptrs, another is the hash key
+ * PTRS - TYPE must contain a field of type NAME_ptrs, PTRS is the name of that
+ * field
+ * KEYTYPE - type of the key field within TYPE
+ * KEY - name of the key field within TYPE
+ * KEYCMP - pointer to function that compares KEYTYPEs to each other - the
+ * prototype is int KEYCMP(KEYTYPE, KEYTYPE), it returns zero for equal,
+ * non-zero for not equal
+ * HASHFN - the hash function - the prototype is int HASHFN(KEYTYPE),
+ * it returns a number in the range 0 ... HASHSIZE - 1
+ * Call DEF_HASH_STRUCTS, define your hash table as a NAME_table, then call
+ * DEF_HASH.
+ */
+
+#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,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,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;\
+ return ptr;\
+}
+
+#endif
diff -uNr linux-2.6.9-rc1-mm1/arch/um/kernel/physmem.c linux-2.6.9-rc1-mm1-hch/arch/um/kernel/physmem.c
--- linux-2.6.9-rc1-mm1/arch/um/kernel/physmem.c 2004-08-28 12:17:24.928599096 +0200
+++ linux-2.6.9-rc1-mm1-hch/arch/um/kernel/physmem.c 2004-08-28 12:26:10.152752888 +0200
@@ -4,7 +4,6 @@
*/
#include "linux/mm.h"
-#include "linux/ghash.h"
#include "linux/slab.h"
#include "linux/vmalloc.h"
#include "linux/bootmem.h"
@@ -18,6 +17,7 @@
#include "os.h"
#include "kern.h"
#include "init.h"
+#include "ghash.h"
#if 0
static pgd_t physmem_pgd[PTRS_PER_PGD];
diff -uNr linux-2.6.9-rc1-mm1/include/linux/ghash.h linux-2.6.9-rc1-mm1-hch/include/linux/ghash.h
--- linux-2.6.9-rc1-mm1/include/linux/ghash.h 2004-08-28 12:17:39.033454832 +0200
+++ linux-2.6.9-rc1-mm1-hch/include/linux/ghash.h 1970-01-01 01:00:00.000000000 +0100
@@ -1,236 +0,0 @@
-/*
- * 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;\
-}
-
-/* LINKAGE - empty or "static", depending on whether you want the definitions to
- * be public or not
- * NAME - a string to stick in names to make this hash table type distinct from
- * any others
- * HASHSIZE - number of buckets
- * TYPE - type of data contained in the buckets - must be a structure, one
- * field is of type NAME_ptrs, another is the hash key
- * PTRS - TYPE must contain a field of type NAME_ptrs, PTRS is the name of that
- * field
- * KEYTYPE - type of the key field within TYPE
- * KEY - name of the key field within TYPE
- * KEYCMP - pointer to function that compares KEYTYPEs to each other - the
- * prototype is int KEYCMP(KEYTYPE, KEYTYPE), it returns zero for equal,
- * non-zero for not equal
- * HASHFN - the hash function - the prototype is int HASHFN(KEYTYPE),
- * it returns a number in the range 0 ... HASHSIZE - 1
- * Call DEF_HASH_STRUCTS, define your hash table as a NAME_table, then call
- * DEF_HASH.
- */
-
-#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,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,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;\
- return ptr;\
-}
-
-#endif
next reply other threads:[~2004-08-28 10:55 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-08-28 10:55 Christoph Hellwig [this message]
2004-08-28 18:31 ` [PATCH] move ghash.h were it does less harm Andrew Morton
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20040828105512.GA11067@lst.de \
--to=hch@lst.de \
--cc=akpm@osdl.org \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox