URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [tags/] [LINUX_2_4_26_OR32/] [linux/] [linux-2.4/] [include/] [linux/] [ghash.h] - Blame information for rev 1275

Go to most recent revision | Details | Compare with Previous | View Log


/*
 * 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

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [tags/] [LINUX_2_4_26_OR32/] [linux/] [linux-2.4/] [include/] [linux/] [ghash.h] - Blame information for rev 1275

Line No.	Rev	Author	Line
1	1275	phoenix	`/*`
2			`* include/linux/ghash.h -- generic hashing with fuzzy retrieval`
3			`*`
4			`* (C) 1997 Thomas Schoebel-Theuer`
5			`*`
6			`* The algorithms implemented here seem to be a completely new invention,`
7			`* and I'll publish the fundamentals in a paper.`
8			`*/`
9
10			`#ifndef _GHASH_H`
11			`#define _GHASH_H`
12			`/* HASHSIZE _must_ be a power of two!!! */`
13
14
15			`#define DEF_HASH_FUZZY_STRUCTS(NAME,HASHSIZE,TYPE) \`
16			`\`
17			`struct NAME##_table {\`
18			`TYPE * hashtable[HASHSIZE];\`
19			`TYPE * sorted_list;\`
20			`int nr_entries;\`
21			`};\`
22			`\`
23			`struct NAME##_ptrs {\`
24			`TYPE * next_hash;\`
25			`TYPE * prev_hash;\`
26			`TYPE * next_sorted;\`
27			`TYPE * prev_sorted;\`
28			`};`
29
30			`#define DEF_HASH_FUZZY(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\`
31			`\`
32			`LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\`
33			`{\`
34			`int ix = HASHFN(elem->KEY);\`
35			`TYPE ** base = &tbl->hashtable[ix];\`
36			`TYPE * ptr = *base;\`
37			`TYPE * prev = NULL;\`
38			`\`
39			`tbl->nr_entries++;\`
40			`while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\`
41			`base = &ptr->PTRS.next_hash;\`
42			`prev = ptr;\`
43			`ptr = *base;\`
44			`}\`
45			`elem->PTRS.next_hash = ptr;\`
46			`elem->PTRS.prev_hash = prev;\`
47			`if(ptr) {\`
48			`ptr->PTRS.prev_hash = elem;\`
49			`}\`
50			`*base = elem;\`
51			`\`
52			`ptr = prev;\`
53			`if(!ptr) {\`
54			`ptr = tbl->sorted_list;\`
55			`prev = NULL;\`
56			`} else {\`
57			`prev = ptr->PTRS.prev_sorted;\`
58			`}\`
59			`while(ptr) {\`
60			`TYPE * next = ptr->PTRS.next_hash;\`
61			`if(next && KEYCMP(next->KEY, elem->KEY)) {\`
62			`prev = ptr;\`
63			`ptr = next;\`
64			`} else if(KEYCMP(ptr->KEY, elem->KEY)) {\`
65			`prev = ptr;\`
66			`ptr = ptr->PTRS.next_sorted;\`
67			`} else\`
68			`break;\`
69			`}\`
70			`elem->PTRS.next_sorted = ptr;\`
71			`elem->PTRS.prev_sorted = prev;\`
72			`if(ptr) {\`
73			`ptr->PTRS.prev_sorted = elem;\`
74			`}\`
75			`if(prev) {\`
76			`prev->PTRS.next_sorted = elem;\`
77			`} else {\`
78			`tbl->sorted_list = elem;\`
79			`}\`
80			`}\`
81			`\`
82			`LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\`
83			`{\`
84			`TYPE * next = elem->PTRS.next_hash;\`
85			`TYPE * prev = elem->PTRS.prev_hash;\`
86			`\`
87			`tbl->nr_entries--;\`
88			`if(next)\`
89			`next->PTRS.prev_hash = prev;\`
90			`if(prev)\`
91			`prev->PTRS.next_hash = next;\`
92			`else {\`
93			`int ix = HASHFN(elem->KEY);\`
94			`tbl->hashtable[ix] = next;\`
95			`}\`
96			`\`
97			`next = elem->PTRS.next_sorted;\`
98			`prev = elem->PTRS.prev_sorted;\`
99			`if(next)\`
100			`next->PTRS.prev_sorted = prev;\`
101			`if(prev)\`
102			`prev->PTRS.next_sorted = next;\`
103			`else\`
104			`tbl->sorted_list = next;\`
105			`}\`
106			`\`
107			`LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\`
108			`{\`
109			`int ix = hashfn(pos);\`
110			`TYPE * ptr = tbl->hashtable[ix];\`
111			`while(ptr && KEYCMP(ptr->KEY, pos))\`
112			`ptr = ptr->PTRS.next_hash;\`
113			`if(ptr && !KEYEQ(ptr->KEY, pos))\`
114			`ptr = NULL;\`
115			`return ptr;\`
116			`}\`
117			`\`
118			`LINKAGE TYPE * find_##NAME##_hash_fuzzy(struct NAME##_table * tbl, KEYTYPE pos)\`
119			`{\`
120			`int ix;\`
121			`int offset;\`
122			`TYPE * ptr;\`
123			`TYPE * next;\`
124			`\`
125			`ptr = tbl->sorted_list;\`
126			`if(!ptr \|\| KEYCMP(pos, ptr->KEY))\`
127			`return NULL;\`
128			`ix = HASHFN(pos);\`
129			`offset = HASHSIZE;\`
130			`do {\`
131			`offset >>= 1;\`
132			`next = tbl->hashtable[(ix+offset) & ((HASHSIZE)-1)];\`
133			`if(next && (KEYCMP(next->KEY, pos) \|\| KEYEQ(next->KEY, pos))\`
134			`&& KEYCMP(ptr->KEY, next->KEY))\`
135			`ptr = next;\`
136			`} while(offset);\`
137			`\`
138			`for(;;) {\`
139			`next = ptr->PTRS.next_hash;\`
140			`if(next) {\`
141			`if(KEYCMP(next->KEY, pos)) {\`
142			`ptr = next;\`
143			`continue;\`
144			`}\`
145			`}\`
146			`next = ptr->PTRS.next_sorted;\`
147			`if(next && KEYCMP(next->KEY, pos)) {\`
148			`ptr = next;\`
149			`continue;\`
150			`}\`
151			`return ptr;\`
152			`}\`
153			`return NULL;\`
154			`}`
155
156			`#define DEF_HASH_STRUCTS(NAME,HASHSIZE,TYPE) \`
157			`\`
158			`struct NAME##_table {\`
159			`TYPE * hashtable[HASHSIZE];\`
160			`int nr_entries;\`
161			`};\`
162			`\`
163			`struct NAME##_ptrs {\`
164			`TYPE * next_hash;\`
165			`TYPE * prev_hash;\`
166			`};`
167
168			`#define DEF_HASH(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\`
169			`\`
170			`LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\`
171			`{\`
172			`int ix = HASHFN(elem->KEY);\`
173			`TYPE ** base = &tbl->hashtable[ix];\`
174			`TYPE * ptr = *base;\`
175			`TYPE * prev = NULL;\`
176			`\`
177			`tbl->nr_entries++;\`
178			`while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\`
179			`base = &ptr->PTRS.next_hash;\`
180			`prev = ptr;\`
181			`ptr = *base;\`
182			`}\`
183			`elem->PTRS.next_hash = ptr;\`
184			`elem->PTRS.prev_hash = prev;\`
185			`if(ptr) {\`
186			`ptr->PTRS.prev_hash = elem;\`
187			`}\`
188			`*base = elem;\`
189			`}\`
190			`\`
191			`LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\`
192			`{\`
193			`TYPE * next = elem->PTRS.next_hash;\`
194			`TYPE * prev = elem->PTRS.prev_hash;\`
195			`\`
196			`tbl->nr_entries--;\`
197			`if(next)\`
198			`next->PTRS.prev_hash = prev;\`
199			`if(prev)\`
200			`prev->PTRS.next_hash = next;\`
201			`else {\`
202			`int ix = HASHFN(elem->KEY);\`
203			`tbl->hashtable[ix] = next;\`
204			`}\`
205			`}\`
206			`\`
207			`LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\`
208			`{\`
209			`int ix = hashfn(pos);\`
210			`TYPE * ptr = tbl->hashtable[ix];\`
211			`while(ptr && KEYCMP(ptr->KEY, pos))\`
212			`ptr = ptr->PTRS.next_hash;\`
213			`if(ptr && !KEYEQ(ptr->KEY, pos))\`
214			`ptr = NULL;\`
215			`return ptr;\`
216			`}`
217
218			`#endif`