[1526] | 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 | }
|
---|