00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 module mango.cache.HashMap;
00041
00042
00043
00044
00045
00046 extern (C)
00047 {
00048 int memcmp (char *, char *, uint);
00049 }
00050
00051
00113 class HashMap
00114 {
00115 alias void[] K;
00116 alias Object V;
00117 alias jhash hash;
00118
00119
00120
00121
00122
00123
00124
00125
00130 private const uint DEFAULT_INITIAL_CAPACITY = 16;
00131
00138 private const uint MAXIMUM_CAPACITY = 1 << 30;
00139
00144 private const float DEFAULT_LOAD_FACTOR = 0.75f;
00145
00149 private const uint DEFAULT_SEGMENTS = 16;
00150
00155 private const uint MAX_SEGMENTS = 1 << 16;
00156
00157
00158
00159
00164 private final int segmentMask;
00165
00169 private final int segmentShift;
00170
00174 private final Segment[] segments;
00175
00176
00177
00178
00185 private static final uint walter(K x)
00186 {
00187 uint h = typeid(char[]).getHash (&x);
00188 h += ~(h << 9);
00189 h ^= (h >>> 14);
00190 h += (h << 4);
00191 h ^= (h >>> 10);
00192 return h;
00193 }
00194
00201 private static final uint fnv(K x)
00202 {
00203 uint hash = 2_166_136_261;
00204
00205 foreach (ubyte c; cast(ubyte[]) x)
00206 {
00207 hash ^= c;
00208 hash *= 16_777_619;
00209 }
00210 return hash;
00211 }
00212
00213
00214
00241 static final uint jhash (K x)
00242 {
00243 ubyte* k;
00244 uint a,
00245 b,
00246 c,
00247 len;
00248
00249 len = x.length;
00250 k = cast(ubyte *) x;
00251 a = b = 0x9e3779b9;
00252
00253
00254 c = 0;
00255
00256
00257 while (len >= 12)
00258 {
00259 a += *cast(uint *)(k+0);
00260 b += *cast(uint *)(k+4);
00261 c += *cast(uint *)(k+8);
00262
00263 a -= b; a -= c; a ^= (c>>13);
00264 b -= c; b -= a; b ^= (a<<8);
00265 c -= a; c -= b; c ^= (b>>13);
00266 a -= b; a -= c; a ^= (c>>12);
00267 b -= c; b -= a; b ^= (a<<16);
00268 c -= a; c -= b; c ^= (b>>5);
00269 a -= b; a -= c; a ^= (c>>3);
00270 b -= c; b -= a; b ^= (a<<10);
00271 c -= a; c -= b; c ^= (b>>15);
00272 k += 12; len -= 12;
00273 }
00274
00275
00276 c += x.length;
00277 switch (len)
00278 {
00279 case 11: c+=(cast(uint)k[10]<<24);
00280 case 10: c+=(cast(uint)k[9]<<16);
00281 case 9 : c+=(cast(uint)k[8]<<8);
00282 case 8 : b+=(cast(uint)k[7]<<24);
00283 case 7 : b+=(cast(uint)k[6]<<16);
00284 case 6 : b+=(cast(uint)k[5]<<8);
00285 case 5 : b+=k[4];
00286 case 4 : a+=(cast(uint)k[3]<<24);
00287 case 3 : a+=(cast(uint)k[2]<<16);
00288 case 2 : a+=(cast(uint)k[1]<<8);
00289 case 1 : a+=k[0];
00290 default:
00291 }
00292
00293 a -= b; a -= c; a ^= (c>>13);
00294 b -= c; b -= a; b ^= (a<<8);
00295 c -= a; c -= b; c ^= (b>>13);
00296 a -= b; a -= c; a ^= (c>>12);
00297 b -= c; b -= a; b ^= (a<<16);
00298 c -= a; c -= b; c ^= (b>>5);
00299 a -= b; a -= c; a ^= (c>>3);
00300 b -= c; b -= a; b ^= (a<<10);
00301 c -= a; c -= b; c ^= (b>>15);
00302
00303 return c;
00304 }
00305
00306
00312 private final Segment segmentFor(uint hash)
00313 {
00314 return segments[(hash >>> segmentShift) & segmentMask];
00315 }
00316
00317
00318
00331 private static class HashEntry
00332 {
00333 final K key;
00334 final uint hash;
00335 final V value;
00336 final HashEntry next;
00337
00338 this (K key, uint hash, HashEntry next, V value)
00339 {
00340 this.key = key;
00341 this.hash = hash;
00342 this.next = next;
00343 this.value = value;
00344 }
00345 }
00346
00352 static class Segment
00353 {
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00394 int count;
00395
00401 int threshold;
00402
00407 HashEntry[] table;
00408
00415 final float loadFactor;
00416
00417 this (int initialCapacity, float lf)
00418 {
00419 loadFactor = lf;
00420 setTable (new HashEntry[initialCapacity]);
00421 }
00422
00427 private final void setTable (HashEntry[] newTable)
00428 {
00429 threshold = cast(int) (newTable.length * loadFactor);
00430 volatile table = newTable;
00431 }
00432
00436 private final HashEntry getFirst (uint hash)
00437 {
00438 HashEntry[] tab;
00439
00440 volatile tab = table;
00441 return tab [hash & (tab.length - 1)];
00442 }
00443
00447 private static final bool matchKey (K a, K b)
00448 {
00449 if (a.length == b.length)
00450 return cast(bool) (memcmp (cast(char*) a, cast(char*) b, a.length) == 0);
00451 return false;
00452 }
00453
00454
00455
00456 final V get (K key, uint hash)
00457 {
00458 int c;
00459
00460
00461 volatile c = count;
00462 if (c)
00463 {
00464 HashEntry e = getFirst (hash);
00465 while (e)
00466 {
00467 if (hash == e.hash && matchKey (key, e.key))
00468 {
00469 V v;
00470 volatile v = e.value;
00471 if (v)
00472 return v;
00473
00474 synchronized (this)
00475 return e.value;
00476 }
00477 e = e.next;
00478 }
00479 }
00480 return null;
00481 }
00482
00483
00484 final bool containsKey (K key, uint hash)
00485 {
00486 int c;
00487
00488
00489 volatile c = count;
00490 if (c)
00491 {
00492 HashEntry e = getFirst (hash);
00493 while (e)
00494 {
00495 if (e.hash == hash && matchKey (key, e.key))
00496 return true;
00497 e = e.next;
00498 }
00499 }
00500 return false;
00501 }
00502
00503
00504
00505 final synchronized V replace (K key, uint hash, V newValue)
00506 {
00507 HashEntry e = getFirst(hash);
00508 while (e && (e.hash != hash || !matchKey (key, e.key)))
00509 e = e.next;
00510
00511 V oldValue = null;
00512 if (e)
00513 volatile
00514 {
00515 oldValue = e.value;
00516 e.value = newValue;
00517 }
00518 return oldValue;
00519 }
00520
00521
00522 final synchronized V put (K key, uint hash, V value, bool onlyIfAbsent)
00523 {
00524 int c;
00525
00526 volatile c = count;
00527 if (c++ > threshold)
00528 rehash();
00529
00530 HashEntry[] tab;
00531 volatile tab = table;
00532 uint index = hash & (tab.length - 1);
00533 HashEntry first = tab[index];
00534 HashEntry e = first;
00535
00536 while (e && (e.hash != hash || !matchKey (key, e.key)))
00537 e = e.next;
00538
00539 V oldValue;
00540 if (e)
00541 {
00542 volatile oldValue = e.value;
00543 if (!onlyIfAbsent)
00544 volatile e.value = value;
00545 }
00546 else
00547 {
00548 oldValue = null;
00549 tab[index] = new HashEntry (key, hash, first, value);
00550
00551
00552 volatile count = c;
00553 }
00554 return oldValue;
00555 }
00556
00557
00558 private final void rehash ()
00559 {
00560 HashEntry[] oldTable;
00561
00562 volatile oldTable = table;
00563 int oldCapacity = oldTable.length;
00564 if (oldCapacity >= MAXIMUM_CAPACITY)
00565 return;
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578
00579
00580
00581 HashEntry[] newTable = new HashEntry[oldCapacity << 1];
00582 threshold = cast(int) (newTable.length * loadFactor);
00583 int sizeMask = newTable.length - 1;
00584
00585 for (int i = 0; i < oldCapacity ; ++i)
00586 {
00587
00588
00589 HashEntry e = oldTable[i];
00590
00591 if (e)
00592 {
00593 HashEntry next = e.next;
00594 uint idx = e.hash & sizeMask;
00595
00596
00597 if (next is null)
00598 newTable[idx] = e;
00599 else
00600 {
00601
00602 HashEntry lastRun = e;
00603 int lastIdx = idx;
00604 for (HashEntry last=next; last; last = last.next)
00605 {
00606 uint k = last.hash & sizeMask;
00607 if (k != lastIdx)
00608 {
00609 lastIdx = k;
00610 lastRun = last;
00611 }
00612 }
00613 newTable[lastIdx] = lastRun;
00614
00615
00616 for (HashEntry p = e; p !is lastRun; p = p.next)
00617 {
00618 uint k = p.hash & sizeMask;
00619 HashEntry n = newTable[k];
00620 newTable[k] = new HashEntry(p.key, p.hash, n, p.value);
00621 }
00622 }
00623 }
00624 }
00625 volatile table = newTable;
00626 }
00627
00631 final synchronized V remove (K key, uint hash, V value)
00632 {
00633 int c;
00634 HashEntry[] tab;
00635
00636 volatile c = count - 1;
00637 volatile tab = table;
00638
00639 uint index = hash & (tab.length - 1);
00640 HashEntry first = tab[index];
00641 HashEntry e = first;
00642
00643 while (e && (e.hash != hash || !matchKey (key, e.key)))
00644 e = e.next;
00645
00646 V oldValue = null;
00647 if (e)
00648 {
00649 V v;
00650 volatile v = e.value;
00651 if (value is null || value == v)
00652 {
00653 oldValue = v;
00654
00655
00656
00657
00658 HashEntry newFirst = e.next;
00659 for (HashEntry p = first; p !is e; p = p.next)
00660 newFirst = new HashEntry (p.key, p.hash, newFirst, p.value);
00661 tab[index] = newFirst;
00662
00663
00664 volatile count = c;
00665 }
00666 }
00667 return oldValue;
00668 }
00669
00670
00671 final synchronized void clear()
00672 {
00673 if (count)
00674 {
00675 HashEntry[] tab;
00676 volatile tab = table;
00677
00678 for (int i = 0; i < tab.length ; i++)
00679 tab[i] = null;
00680
00681
00682 volatile count = 0;
00683 }
00684 }
00685 }
00686
00687
00688
00689
00690
00705 public this (uint initialCapacity, float loadFactor, uint concurrencyLevel)
00706 {
00707 assert (loadFactor > 0);
00708
00709 if (concurrencyLevel > MAX_SEGMENTS)
00710 concurrencyLevel = MAX_SEGMENTS;
00711
00712
00713 int sshift = 0;
00714 int ssize = 1;
00715 while (ssize < concurrencyLevel)
00716 {
00717 ++sshift;
00718 ssize <<= 1;
00719 }
00720
00721 segmentShift = 32 - sshift;
00722 segmentMask = ssize - 1;
00723 this.segments = new Segment[ssize];
00724
00725 if (initialCapacity > MAXIMUM_CAPACITY)
00726 initialCapacity = MAXIMUM_CAPACITY;
00727
00728 int c = initialCapacity / ssize;
00729 if (c * ssize < initialCapacity)
00730 ++c;
00731
00732 int cap = 1;
00733 while (cap < c)
00734 cap <<= 1;
00735
00736 for (int i = 0; i < this.segments.length; ++i)
00737 this.segments[i] = new Segment (cap, loadFactor);
00738 }
00739
00749 public this (uint initialCapacity)
00750 {
00751 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
00752 }
00753
00758 public this ()
00759 {
00760 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
00761 }
00762
00773 public V get (K key)
00774 {
00775 uint hash = hash(key);
00776 return segmentFor(hash).get(key, hash);
00777 }
00778
00789 public bool containsKey (K key)
00790 {
00791 uint hash = hash(key);
00792 return segmentFor(hash).containsKey(key, hash);
00793 }
00794
00810 public V put (K key, V value)
00811 {
00812 assert (value);
00813
00814 uint hash = hash(key);
00815 return segmentFor(hash).put(key, hash, value, false);
00816 }
00817
00836 public V putIfAbsent (K key, V value)
00837 {
00838 assert (value);
00839
00840 uint hash = hash(key);
00841 return segmentFor(hash).put(key, hash, value, true);
00842 }
00843
00844
00855 public V remove (K key)
00856 {
00857 uint hash = hash(key);
00858 return segmentFor(hash).remove(key, hash, null);
00859 }
00860
00877 public bool remove (K key, V value)
00878 {
00879 uint hash = hash(key);
00880 return cast(bool) (segmentFor(hash).remove(key, hash, value) !is null);
00881 }
00882
00883
00900 public V replace (K key, V value)
00901 {
00902 assert (value);
00903
00904 uint hash = hash(key);
00905 return segmentFor(hash).replace(key, hash, value);
00906 }
00907
00908
00912 public void clear ()
00913 {
00914 for (int i = 0; i < segments.length; ++i)
00915 segments[i].clear();
00916 }
00917
00918
00925 public KeyIterator keys ()
00926 {
00927 return new KeyIterator (this);
00928 }
00929
00936 public ValueIterator elements ()
00937 {
00938 return new ValueIterator (this);
00939 }
00940
00941
00942
00943
00944
00945
00946
00947 int opApply (int delegate(inout char[]) dg)
00948 {
00949 int result = 0;
00950 KeyIterator iterator = keys ();
00951
00952 while (iterator.hasNext)
00953 {
00954 char[] ca = cast(char[]) iterator.next;
00955 if ((result = dg (ca)) != 0)
00956 break;
00957 }
00958 return result;
00959 }
00960
00961
00962
00963
00964
00965
00966
00967 int opApply (int delegate(inout char[], inout Object) dg)
00968 {
00969 int result = 0;
00970 KeyIterator iterator = keys ();
00971
00972 while (iterator.hasNext)
00973 {
00974 HashEntry he = iterator.nextElement;
00975 char[] ca = cast(char[]) he.key;
00976 if ((result = dg (ca, he.value)) != 0)
00977 break;
00978 }
00979 return result;
00980 }
00981
00982
00983
00984
00985 abstract static class HashIterator
00986 {
00987 int nextSegmentIndex;
00988 int nextTableIndex;
00989 HashEntry[] currentTable;
00990 HashEntry nextEntry;
00991 HashEntry lastReturned;
00992 HashMap map;
00993
00994 this (HashMap map)
00995 {
00996 this.map = map;
00997 nextSegmentIndex = map.segments.length - 1;
00998 nextTableIndex = -1;
00999 advance();
01000 }
01001
01002 final void advance ()
01003 {
01004 if (nextEntry !is null && (nextEntry = nextEntry.next) !is null)
01005 return;
01006
01007 while (nextTableIndex >= 0)
01008 {
01009 if ( (nextEntry = currentTable[nextTableIndex--]) !is null)
01010 return;
01011 }
01012
01013 while (nextSegmentIndex >= 0)
01014 {
01015 Segment seg = map.segments[nextSegmentIndex--];
01016 volatile if (seg.count)
01017 {
01018 currentTable = seg.table;
01019 for (int j = currentTable.length - 1; j >= 0; --j)
01020 {
01021 if ((nextEntry = currentTable[j]) !is null)
01022 {
01023 nextTableIndex = j - 1;
01024 return;
01025 }
01026 }
01027 }
01028 }
01029 }
01030
01031 public bool hasNext ()
01032 {
01033 return cast(bool) (nextEntry !is null);
01034 }
01035
01036 HashEntry nextElement ()
01037 {
01038 if (nextEntry is null)
01039 throw new Exception ("no such element in HashMap");
01040
01041 lastReturned = nextEntry;
01042 advance ();
01043 return lastReturned;
01044 }
01045 }
01046
01047 static class KeyIterator : HashIterator
01048 {
01049 this (HashMap map) {super (map);}
01050 public K next() { return super.nextElement().key; }
01051 }
01052
01053 static class ValueIterator : HashIterator
01054 {
01055 this (HashMap map) {super (map);}
01056 public V next() { volatile return super.nextElement().value; }
01057 }
01058
01059 }