Diffstat (limited to 'noncore/apps/opie-reader/hash.h') (more/less context) (ignore whitespace changes)
-rwxr-xr-x | noncore/apps/opie-reader/hash.h | 201 |
1 files changed, 201 insertions, 0 deletions
diff --git a/noncore/apps/opie-reader/hash.h b/noncore/apps/opie-reader/hash.h new file mode 100755 index 0000000..4fe526a --- a/dev/null +++ b/noncore/apps/opie-reader/hash.h | |||
@@ -0,0 +1,201 @@ | |||
1 | #ifndef __HASH_H | ||
2 | #define __HASH_H | ||
3 | |||
4 | #include <stdlib.h> | ||
5 | /* Primes | ||
6 | 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 | ||
7 | 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 | ||
8 | 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 | ||
9 | 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 | ||
10 | 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 | ||
11 | 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 | ||
12 | 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 | ||
13 | 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 | ||
14 | 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 | ||
15 | 953 967 971 977 983 991 997 | ||
16 | */ | ||
17 | |||
18 | inline size_t hashfn(unsigned long l) | ||
19 | { | ||
20 | return l*0x33f3; | ||
21 | } | ||
22 | |||
23 | inline size_t hash2fn(unsigned long l) | ||
24 | { | ||
25 | return l & 7; | ||
26 | } | ||
27 | /*/ | ||
28 | template<class K>size_t hashfn(const K& l) | ||
29 | { | ||
30 | size_t s = 0; | ||
31 | unsigned char* p = (unsigned char*)&l; | ||
32 | for (int i = 0; i < sizeof(K)-1; i++) | ||
33 | { | ||
34 | s = 3*s+(255-p[i]); | ||
35 | } | ||
36 | } | ||
37 | |||
38 | template<class K>size_t hash2fn(const K& l) | ||
39 | { | ||
40 | unsigned char* p = (unsigned char*)&l; | ||
41 | return 255-p[sizeof(K)-1]; | ||
42 | } | ||
43 | */ | ||
44 | template<class K, class D> | ||
45 | class hashtable | ||
46 | { | ||
47 | public: | ||
48 | class iterator; | ||
49 | friend class hashtable::iterator; | ||
50 | #ifndef _WINDOWS | ||
51 | private: | ||
52 | #endif | ||
53 | struct keydata | ||
54 | { | ||
55 | K key; | ||
56 | D data; | ||
57 | bool inuse; | ||
58 | keydata() : inuse(false) {} | ||
59 | keydata(K k, D d) : key(k), data(d), inuse(true) {} | ||
60 | }; | ||
61 | keydata* table; | ||
62 | size_t hshsz; | ||
63 | bool notprime(size_t p) | ||
64 | { | ||
65 | size_t d; | ||
66 | if (p % 2 == 0) return true; | ||
67 | d = 3; | ||
68 | while (d*d <= p) | ||
69 | { | ||
70 | if (p % d == 0) | ||
71 | { | ||
72 | return true; | ||
73 | } | ||
74 | d += 2; | ||
75 | } | ||
76 | return false; | ||
77 | } | ||
78 | void resize() | ||
79 | { | ||
80 | size_t oldsz = hshsz; | ||
81 | hshsz = (3*hshsz)/2; | ||
82 | while (notprime(hshsz)) | ||
83 | { | ||
84 | hshsz++; | ||
85 | } | ||
86 | //printf("Size:%u\n", hshsz); | ||
87 | keydata* oldtable = table; | ||
88 | table = new keydata[hshsz]; | ||
89 | for (size_t i = 0; i < oldsz; i++) | ||
90 | { | ||
91 | if (oldtable[i].inuse) | ||
92 | { | ||
93 | //printf("Setting %u to %u\n", oldtable[i].key, oldtable[i].data); | ||
94 | (*this)[oldtable[i].key] = oldtable[i].data; | ||
95 | //printf("Now %u is %u\n", oldtable[i].key, (*this)[oldtable[i].key]); | ||
96 | } | ||
97 | } | ||
98 | delete [] oldtable; | ||
99 | } | ||
100 | size_t findkey(const K& key) // returns -1 if can't find it | ||
101 | { | ||
102 | size_t hash2 = hash2fn(key)%(hshsz-1)+1; | ||
103 | size_t hash = hashfn(key) % hshsz; | ||
104 | size_t i = hash; | ||
105 | //printf("Key:%u, hash:%u, hash2:%u\n", key, hash, hash2); | ||
106 | while (table[i].inuse) // !empty | ||
107 | { | ||
108 | if (table[i].key == key) | ||
109 | { | ||
110 | //printf("Key %u present at %u\n", key, i); | ||
111 | return i; // but its the correct one & present | ||
112 | } | ||
113 | i = (i+hash2) % hshsz; | ||
114 | if (i == hash) // Table full | ||
115 | { | ||
116 | resize(); | ||
117 | hash2 = hash2fn(key)%(hshsz-1)+1; | ||
118 | hash = hashfn(key) % hshsz; | ||
119 | i = hash; | ||
120 | //printf("(R)Key:%u, hash:%u, hash2:%u\n", key, hash, hash2); | ||
121 | } | ||
122 | } | ||
123 | //printf("Key %u absent at %u\n", key, i); | ||
124 | return i; // found & absent | ||
125 | } | ||
126 | public: | ||
127 | hashtable(int sz) : hshsz(sz) | ||
128 | { | ||
129 | while (notprime(hshsz)) | ||
130 | { | ||
131 | hshsz++; | ||
132 | } | ||
133 | //printf("Size:%u\n", hshsz); | ||
134 | table = new keydata[hshsz]; | ||
135 | } | ||
136 | ~hashtable() | ||
137 | { | ||
138 | delete [] table; | ||
139 | } | ||
140 | D& operator[](K k) | ||
141 | { | ||
142 | int i = findkey(k); | ||
143 | table[i].key = k; | ||
144 | table[i].inuse = true; | ||
145 | return table[i].data; | ||
146 | } | ||
147 | class iterator | ||
148 | { | ||
149 | friend class hashtable; | ||
150 | #ifdef _WINDOWS | ||
151 | public: | ||
152 | #endif | ||
153 | unsigned int ptr; | ||
154 | hashtable* tab; | ||
155 | iterator(int t, hashtable* _tab) : ptr(t), tab(_tab) | ||
156 | { | ||
157 | while (!tab->table[ptr].inuse && ptr < tab->hshsz) | ||
158 | { | ||
159 | ptr++; | ||
160 | } | ||
161 | } | ||
162 | public: | ||
163 | iterator() : tab(NULL) {} | ||
164 | iterator operator++() | ||
165 | { | ||
166 | while (++ptr < tab->hshsz) | ||
167 | { | ||
168 | if (tab->table[ptr].inuse) return *this; | ||
169 | } | ||
170 | return *this; | ||
171 | } | ||
172 | iterator& operator=(const iterator& r) | ||
173 | { | ||
174 | ptr = r.ptr; | ||
175 | tab = r.tab; | ||
176 | return *this; | ||
177 | } | ||
178 | bool operator!=(const iterator& r) | ||
179 | { | ||
180 | return !((ptr == r.ptr) && (tab == r.tab)); | ||
181 | } | ||
182 | bool operator==(const iterator& r) | ||
183 | { | ||
184 | return ((ptr == r.ptr) && (tab == r.tab)); | ||
185 | } | ||
186 | K first() { return tab->table[ptr].key; } | ||
187 | D second() { return tab->table[ptr].data; } | ||
188 | }; | ||
189 | iterator find(K k) | ||
190 | { | ||
191 | size_t i = findkey(k); | ||
192 | return (table[i].inuse) ? iterator(i,this) : end(); | ||
193 | } | ||
194 | D& operator[](const iterator& i) // Never call with an invalid iterator! | ||
195 | { | ||
196 | return table[i.ptr].data; | ||
197 | } | ||
198 | iterator begin() { return iterator(0, this); } | ||
199 | iterator end() { return iterator(hshsz, this); } | ||
200 | }; | ||
201 | #endif | ||