lkml.org 
[lkml]   [2004]   [Aug]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH] move ghash.h were it does less harm
    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
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/
    \
     
     \ /
      Last update: 2005-03-22 14:05    [W:0.048 / U:90.508 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site