1 | ////////////////////////////////////////////////////////////////////////////////
|
---|
2 | // NTL Nonstandard Template Library for C++
|
---|
3 | // Copyright (c) 2003 by Miroslav Fidler, Tomas Rylek
|
---|
4 | //
|
---|
5 | // Created by Miroslav Fidler, Tomas Rylek, cxl@volny.cz
|
---|
6 | //
|
---|
7 | // Permission to use, copy, modify, distribute and sell this software for any
|
---|
8 | // purpose is hereby granted without fee, provided that the above copyright
|
---|
9 | // notice appear in all copies and that both that copyright notice and this
|
---|
10 | // permission notice appear in supporting documentation.
|
---|
11 | // The author makes no representations about the suitability of this software
|
---|
12 | // for any purpose. It is provided "as is"
|
---|
13 | // without express or implied warranty.
|
---|
14 | ////////////////////////////////////////////////////////////////////////////////
|
---|
15 |
|
---|
16 | #include <ntl.h>
|
---|
17 |
|
---|
18 | #ifdef _MSC_VER
|
---|
19 | #pragma inline_depth(255)
|
---|
20 | #pragma optimize("t", on)
|
---|
21 | #endif
|
---|
22 |
|
---|
23 | int Pow2Bound(int i)
|
---|
24 | {
|
---|
25 | int n = 1;
|
---|
26 | while(n < i) {
|
---|
27 | n <<= 1;
|
---|
28 | ASSERT(n);
|
---|
29 | }
|
---|
30 | return n;
|
---|
31 | }
|
---|
32 |
|
---|
33 | void HashBase::Free() const
|
---|
34 | {
|
---|
35 | if(map)
|
---|
36 | NTL_RAW_FREE(map, mask + 1, sizeof(int));
|
---|
37 | map = NULL;
|
---|
38 | mask = 0;
|
---|
39 | }
|
---|
40 |
|
---|
41 | void HashBase::ClearIndex() const
|
---|
42 | {
|
---|
43 | link.Clear();
|
---|
44 | unlinked = -1;
|
---|
45 | Free();
|
---|
46 | }
|
---|
47 |
|
---|
48 | HashBase::HashBase()
|
---|
49 | {
|
---|
50 | unlinked = -1;
|
---|
51 | map = NULL;
|
---|
52 | mask = 0;
|
---|
53 | }
|
---|
54 |
|
---|
55 | HashBase::HashBase(pick_ HashBase& b)
|
---|
56 | : hash(b.hash),
|
---|
57 | link(b.link)
|
---|
58 | {
|
---|
59 | map = b.map;
|
---|
60 | mask = b.mask;
|
---|
61 | unlinked = b.unlinked;
|
---|
62 | b.map = NULL;
|
---|
63 | }
|
---|
64 |
|
---|
65 | void HashBase::operator=(pick_ HashBase& b)
|
---|
66 | {
|
---|
67 | hash = b.hash;
|
---|
68 | link = b.link;
|
---|
69 | Free();
|
---|
70 | map = b.map;
|
---|
71 | mask = b.mask;
|
---|
72 | unlinked = b.unlinked;
|
---|
73 | b.map = NULL;
|
---|
74 | }
|
---|
75 |
|
---|
76 | HashBase::HashBase(const HashBase& b, int)
|
---|
77 | : hash(b.hash, 0)
|
---|
78 | {
|
---|
79 | unlinked = -1;
|
---|
80 | map = NULL;
|
---|
81 | mask = 0;
|
---|
82 | }
|
---|
83 |
|
---|
84 | void HashBase::operator<<=(const HashBase& b)
|
---|
85 | {
|
---|
86 | ClearIndex();
|
---|
87 | hash <<= b.hash;
|
---|
88 | }
|
---|
89 |
|
---|
90 | HashBase::~HashBase()
|
---|
91 | {
|
---|
92 | Free();
|
---|
93 | }
|
---|
94 |
|
---|
95 | inline void HashBase::LinkBefore(int i, Link& l, int bi) const
|
---|
96 | {
|
---|
97 | Link& bl = link[bi];
|
---|
98 | l.next = bi;
|
---|
99 | l.prev = bl.prev;
|
---|
100 | bl.prev = i;
|
---|
101 | link[l.prev].next = i;
|
---|
102 | }
|
---|
103 |
|
---|
104 | void HashBase::Trim(int count)
|
---|
105 | {
|
---|
106 | ASSERT(count <= hash.GetCount() && count >= 0);
|
---|
107 | if(map) {
|
---|
108 | for(int i = count; i < link.GetCount(); i++)
|
---|
109 | Unlink(i, link[i]);
|
---|
110 | link.SetCount(count);
|
---|
111 | }
|
---|
112 | hash.SetCount(count);
|
---|
113 | }
|
---|
114 |
|
---|
115 | void HashBase::Drop(int n)
|
---|
116 | {
|
---|
117 | Trim(hash.GetCount() - n);
|
---|
118 | }
|
---|
119 |
|
---|
120 | //inline //!! Fidler: either inline or .cpp
|
---|
121 | void HashBase::FinishIndex() const
|
---|
122 | {
|
---|
123 | int q = link.GetCount();
|
---|
124 | link.Reserve(hash.GetAlloc());
|
---|
125 | link.AddN(hash.GetCount() - q);
|
---|
126 | for(int i = q; i < hash.GetCount(); i++)
|
---|
127 | LinkTo(i, link[i], hash[i] & UNSIGNED_HIBIT ? unlinked : Mapi(i));
|
---|
128 | }
|
---|
129 |
|
---|
130 | void HashBase::Reindex(int n) const
|
---|
131 | {
|
---|
132 | ClearIndex();
|
---|
133 | Free();
|
---|
134 | n = ntl_max(16, Pow2Bound(n));
|
---|
135 | map = (int *)NTL_RAW_ALLOC(n * sizeof(int));
|
---|
136 | Fill(map, map + n, -1);
|
---|
137 | mask = n - 1;
|
---|
138 | FinishIndex();
|
---|
139 | }
|
---|
140 |
|
---|
141 | void HashBase::Reindex() const
|
---|
142 | {
|
---|
143 | Reindex(hash.GetCount());
|
---|
144 | }
|
---|
145 |
|
---|
146 | void HashBase::Add(unsigned _hash)
|
---|
147 | {
|
---|
148 | hash.Add(_hash & ~UNSIGNED_HIBIT);
|
---|
149 | }
|
---|
150 |
|
---|
151 | void HashBase::SetUn(int i, unsigned _hash)
|
---|
152 | {
|
---|
153 | if(map) {
|
---|
154 | if(link.GetCount() < hash.GetCount())
|
---|
155 | DoIndex();
|
---|
156 | Link& lnk = link[i];
|
---|
157 | Unlink(i, lnk);
|
---|
158 | LinkTo(i, lnk, Maph(_hash & ~UNSIGNED_HIBIT));
|
---|
159 | }
|
---|
160 | hash[i] = _hash & ~UNSIGNED_HIBIT;
|
---|
161 | }
|
---|
162 |
|
---|
163 | Vector<int> HashBase::GetUnlinked() const
|
---|
164 | {
|
---|
165 | if(link.GetCount() < hash.GetCount())
|
---|
166 | DoIndex();
|
---|
167 | Vector<int> r;
|
---|
168 | int q = unlinked;
|
---|
169 | if(q >= 0) {
|
---|
170 | do {
|
---|
171 | r.Add(q);
|
---|
172 | q = link[q].next;
|
---|
173 | }
|
---|
174 | while(q != unlinked);
|
---|
175 | }
|
---|
176 | return r;
|
---|
177 | }
|
---|
178 |
|
---|
179 | int HashBase::Put(unsigned _hash)
|
---|
180 | {
|
---|
181 | if(unlinked < 0) return -1;
|
---|
182 | if(link.GetCount() < hash.GetCount())
|
---|
183 | DoIndex();
|
---|
184 | Link& l = link[unlinked];
|
---|
185 | int i = unlinked;
|
---|
186 | unlinked = link[unlinked].next;
|
---|
187 | if(i == unlinked)
|
---|
188 | unlinked = -1;
|
---|
189 | else {
|
---|
190 | link[l.next].prev = l.prev;
|
---|
191 | link[l.prev].next = l.next;
|
---|
192 | }
|
---|
193 | LinkTo(i, l, Maph(_hash & ~UNSIGNED_HIBIT));
|
---|
194 | hash[i] = _hash & ~UNSIGNED_HIBIT;
|
---|
195 | return i;
|
---|
196 | }
|
---|
197 |
|
---|
198 | void HashBase::Set(int i, unsigned _hash) {
|
---|
199 | if(map) {
|
---|
200 | if(link.GetCount() < hash.GetCount())
|
---|
201 | DoIndex();
|
---|
202 | Link& lnk = link[i];
|
---|
203 | Unlink(i, lnk);
|
---|
204 | int& mi = Maph(_hash & ~UNSIGNED_HIBIT);
|
---|
205 | int ii = mi;
|
---|
206 | if(ii < 0)
|
---|
207 | mi = lnk.prev = lnk.next = i;
|
---|
208 | else
|
---|
209 | if(i < ii) {
|
---|
210 | LinkBefore(i, lnk, ii);
|
---|
211 | mi = i;
|
---|
212 | }
|
---|
213 | else {
|
---|
214 | int l = ii;
|
---|
215 | int h = link[ii].prev;
|
---|
216 | if(h - i < i - l) {
|
---|
217 | while(i < h) {
|
---|
218 | h = link[h].prev;
|
---|
219 | }
|
---|
220 | LinkBefore(i, lnk, link[h].next);
|
---|
221 | }
|
---|
222 | else {
|
---|
223 | l = link[l].next;
|
---|
224 | while(i > l && l != ii) {
|
---|
225 | l = link[l].next;
|
---|
226 | }
|
---|
227 | LinkBefore(i, lnk, l);
|
---|
228 | }
|
---|
229 | }
|
---|
230 | }
|
---|
231 | hash[i] = _hash & ~UNSIGNED_HIBIT;
|
---|
232 | }
|
---|
233 |
|
---|
234 | void HashBase::Shrink() {
|
---|
235 | hash.Shrink();
|
---|
236 | if(Pow2Bound(hash.GetCount()) != mask + 1)
|
---|
237 | ClearIndex();
|
---|
238 | else
|
---|
239 | link.Shrink();
|
---|
240 | }
|
---|
241 |
|
---|
242 | void HashBase::Reserve(int n)
|
---|
243 | {
|
---|
244 | hash.Reserve(n);
|
---|
245 | link.Reserve(n);
|
---|
246 | n = Pow2Bound(n);
|
---|
247 | if(n > mask + 1)
|
---|
248 | Reindex(n);
|
---|
249 | }
|
---|
250 |
|
---|
251 | void HashBase::Remove(int i)
|
---|
252 | {
|
---|
253 | hash.Remove(i);
|
---|
254 | ClearIndex();
|
---|
255 | }
|
---|
256 |
|
---|
257 | void HashBase::Remove(const int *sorted_list, int count)
|
---|
258 | {
|
---|
259 | hash.Remove(sorted_list, count);
|
---|
260 | ClearIndex();
|
---|
261 | }
|
---|
262 |
|
---|
263 | void HashBase::Insert(int i, unsigned _hash) {
|
---|
264 | hash.Insert(i, _hash & ~UNSIGNED_HIBIT);
|
---|
265 | ClearIndex();
|
---|
266 | }
|
---|
267 |
|
---|
268 | #ifdef UPP
|
---|
269 | void HashBase::Serialize(Stream& s) {
|
---|
270 | int version = 0;
|
---|
271 | s / version;
|
---|
272 | if(s.IsLoading())
|
---|
273 | ClearIndex();
|
---|
274 | hash.Serialize(s);
|
---|
275 | }
|
---|
276 | #endif
|
---|
277 |
|
---|
278 | void HashBase::Swap(HashBase& b) {
|
---|
279 | ::Swap(hash, b.hash);
|
---|
280 | ::Swap(link, b.link);
|
---|
281 | ::Swap(map, b.map);
|
---|
282 | ::Swap(mask, b.mask);
|
---|
283 | ::Swap(unlinked, b.unlinked);
|
---|
284 | }
|
---|
285 |
|
---|
286 |
|
---|
287 | #ifdef CPU_IA32
|
---|
288 |
|
---|
289 | unsigned memhash(const void *ptr, size_t count)
|
---|
290 | {
|
---|
291 | unsigned hash = 1234567890U;
|
---|
292 |
|
---|
293 | const unsigned *ds = (unsigned *)ptr;
|
---|
294 | const unsigned *de = ds + (count >> 2);
|
---|
295 | while(ds < de)
|
---|
296 | hash = ((hash << 5) - hash) ^ *ds++;
|
---|
297 |
|
---|
298 | const byte *s = (byte *)ds;
|
---|
299 | const byte *e = s + (count & 3);
|
---|
300 | while(s < e)
|
---|
301 | hash = ((hash << 5) - hash) ^ *s++;
|
---|
302 |
|
---|
303 | return hash;
|
---|
304 | }
|
---|
305 |
|
---|
306 | #else
|
---|
307 |
|
---|
308 | unsigned memhash(const void *ptr, size_t count)
|
---|
309 | {
|
---|
310 | unsigned hash = 1234567890U;
|
---|
311 |
|
---|
312 | const byte *s = (byte *)ptr;
|
---|
313 | const byte *e = s + count;
|
---|
314 | while(s < e)
|
---|
315 | hash = ((hash << 5) - hash) ^ *s++;
|
---|
316 |
|
---|
317 | return hash;
|
---|
318 | }
|
---|
319 |
|
---|
320 | #endif
|
---|
321 |
|
---|
322 | unsigned GetHashValue0(const double& d)
|
---|
323 | {
|
---|
324 | return memhash(&d, sizeof(double));
|
---|
325 | }
|
---|