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 module mango.cache.HashMap;
00037
00038
00039
00040
00041
00042 extern (C)
00043 {
00044 int memcmp (char *, char *, uint);
00045 }
00046
00047
00109 class HashMap
00110 {
00111 alias void[] K;
00112 alias Object V;
00113 alias jhash hash;
00114
00115
00116
00117
00118
00119
00120
00121
00126 private const uint DEFAULT_INITIAL_CAPACITY = 16;
00127
00134 private const uint MAXIMUM_CAPACITY = 1 << 30;
00135
00140 private const float DEFAULT_LOAD_FACTOR = 0.75f;
00141
00145 private const uint DEFAULT_SEGMENTS = 16;
00146
00151 private const uint MAX_SEGMENTS = 1 << 16;
00152
00153
00154
00155
00160 private final int segmentMask;
00161
00165 private final int segmentShift;
00166
00170 private final Segment[] segments;
00171
00172
00173
00174
00181 private static final uint walter(K x)
00182 {
00183 uint h = typeid(char[]).getHash (&x);
00184 h += ~(h << 9);
00185 h ^= (h >>> 14);
00186 h += (h << 4);
00187 h ^= (h >>> 10);
00188 return h;
00189 }
00190
00197 private static final uint fnv(K x)
00198 {
00199 uint hash = 2_166_136_261;
00200
00201 foreach (ubyte c; cast(ubyte[]) x)
00202 {
00203 hash ^= c;
00204 hash *= 16_777_619;
00205 }
00206 return hash;
00207 }
00208
00209
00210
00237 static final uint jhash (K x)
00238 {
00239 ubyte* k;
00240 uint a,
00241 b,
00242 c,
00243 len;
00244
00245 len = x.length;
00246 k = cast(ubyte *) x;
00247 a = b = 0x9e3779b9;
00248
00249
00250 c = 0;
00251
00252
00253 while (len >= 12)
00254 {
00255 a += *cast(uint *)(k+0);
00256 b += *cast(uint *)(k+4);
00257 c += *cast(uint *)(k+8);
00258
00259 a -= b; a -= c; a ^= (c>>13);
00260 b -= c; b -= a; b ^= (a<<8);
00261 c -= a; c -= b; c ^= (b>>13);
00262 a -= b; a -= c; a ^= (c>>12);
00263 b -= c; b -= a; b ^= (a<<16);
00264 c -= a; c -= b; c ^= (b>>5);
00265 a -= b; a -= c; a ^= (c>>3);
00266 b -= c; b -= a; b ^= (a<<10);
00267 c -= a; c -= b; c ^= (b>>15);
00268 k += 12; len -= 12;
00269 }
00270
00271
00272 c += x.length;
00273 switch (len)
00274 {
00275 case 11: c+=(cast(uint)k[10]<<24);
00276 case 10: c+=(cast(uint)k[9]<<16);
00277 case 9 : c+=(cast(uint)k[8]<<8);
00278 case 8 : b+=(cast(uint)k[7]<<24);
00279 case 7 : b+=(cast(uint)k[6]<<16);
00280 case 6 : b+=(cast(uint)k[5]<<8);
00281 case 5 : b+=k[4];
00282 case 4 : a+=(cast(uint)k[3]<<24);
00283 case 3 : a+=(cast(uint)k[2]<<16);
00284 case 2 : a+=(cast(uint)k[1]<<8);
00285 case 1 : a+=k[0];
00286 default:
00287 }
00288
00289 a -= b; a -= c; a ^= (c>>13);
00290 b -= c; b -= a; b ^= (a<<8);
00291 c -= a; c -= b; c ^= (b>>13);
00292 a -= b; a -= c; a ^= (c>>12);
00293 b -= c; b -= a; b ^= (a<<16);
00294 c -= a; c -= b; c ^= (b>>5);
00295 a -= b; a -= c; a ^= (c>>3);
00296 b -= c; b -= a; b ^= (a<<10);
00297 c -= a; c -= b; c ^= (b>>15);
00298
00299 return c;
00300 }
00301
00302
00308 private final Segment segmentFor(uint hash)
00309 {
00310 return segments[(hash >>> segmentShift) & segmentMask];
00311 }
00312
00313
00314
00327 private class HashEntry
00328 {
00329 final K key;
00330 final uint hash;
00331 final V value;
00332 final HashEntry next;
00333
00334 this (K key, uint hash, HashEntry next, V value)
00335 {
00336 this.key = key;
00337 this.hash = hash;
00338 this.next = next;
00339 this.value = value;
00340 }
00341 }
00342
00348 class Segment
00349 {
00350
00351
00352
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
00390 int count;
00391
00397 int threshold;
00398
00403 HashEntry[] table;
00404
00411 final float loadFactor;
00412
00413 this (int initialCapacity, float lf)
00414 {
00415 loadFactor = lf;
00416 setTable (new HashEntry[initialCapacity]);
00417 }
00418
00423 private final void setTable (HashEntry[] newTable)
00424 {
00425 threshold = cast(int) (newTable.length * loadFactor);
00426 volatile table = newTable;
00427 }
00428
00432 private final HashEntry getFirst (uint hash)
00433 {
00434 HashEntry[] tab;
00435
00436 volatile tab = table;
00437 return tab [hash & (tab.length - 1)];
00438 }
00439
00443 private static final bool matchKey (K a, K b)
00444 {
00445 if (a.length == b.length)
00446 return memcmp (cast(char*) a, cast(char*) b, a.length) == 0;
00447 return false;
00448 }
00449
00450
00451
00452 final V get (K key, uint hash)
00453 {
00454 int c;
00455
00456
00457 volatile c = count;
00458 if (c)
00459 {
00460 HashEntry e = getFirst (hash);
00461 while (e)
00462 {
00463 if (hash == e.hash && matchKey (key, e.key))
00464 {
00465 V v;
00466 volatile v = e.value;
00467 if (v)
00468 return v;
00469
00470 synchronized (this)
00471 return e.value;
00472 }
00473 e = e.next;
00474 }
00475 }
00476 return null;
00477 }
00478
00479
00480 final bool containsKey (K key, uint hash)
00481 {
00482 int c;
00483
00484
00485 volatile c = count;
00486 if (c)
00487 {
00488 HashEntry e = getFirst (hash);
00489 while (e)
00490 {
00491 if (e.hash == hash && matchKey (key, e.key))
00492 return true;
00493 e = e.next;
00494 }
00495 }
00496 return false;
00497 }
00498
00499
00500
00501 final synchronized V replace (K key, uint hash, V newValue)
00502 {
00503 HashEntry e = getFirst(hash);
00504 while (e && (e.hash != hash || !matchKey (key, e.key)))
00505 e = e.next;
00506
00507 V oldValue = null;
00508 if (e)
00509 volatile
00510 {
00511 oldValue = e.value;
00512 e.value = newValue;
00513 }
00514 return oldValue;
00515 }
00516
00517
00518 final synchronized V put (K key, uint hash, V value, bool onlyIfAbsent)
00519 {
00520 int c;
00521
00522 volatile c = count;
00523 if (c++ > threshold)
00524 rehash();
00525
00526 HashEntry[] tab;
00527 volatile tab = table;
00528 uint index = hash & (tab.length - 1);
00529 HashEntry first = tab[index];
00530 HashEntry e = first;
00531
00532 while (e && (e.hash != hash || !matchKey (key, e.key)))
00533 e = e.next;
00534
00535 V oldValue;
00536 if (e)
00537 {
00538 volatile oldValue = e.value;
00539 if (!onlyIfAbsent)
00540 volatile e.value = value;
00541 }
00542 else
00543 {
00544 oldValue = null;
00545 tab[index] = new HashEntry (key, hash, first, value);
00546
00547
00548 volatile count = c;
00549 }
00550 return oldValue;
00551 }
00552
00553
00554 private final void rehash ()
00555 {
00556 HashEntry[] oldTable;
00557
00558 volatile oldTable = table;
00559 int oldCapacity = oldTable.length;
00560 if (oldCapacity >= MAXIMUM_CAPACITY)
00561 return;
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577 HashEntry[] newTable = new HashEntry[oldCapacity << 1];
00578 threshold = cast(int) (newTable.length * loadFactor);
00579 int sizeMask = newTable.length - 1;
00580
00581 for (int i = 0; i < oldCapacity ; ++i)
00582 {
00583
00584
00585 HashEntry e = oldTable[i];
00586
00587 if (e)
00588 {
00589 HashEntry next = e.next;
00590 uint idx = e.hash & sizeMask;
00591
00592
00593 if (next is null)
00594 newTable[idx] = e;
00595 else
00596 {
00597
00598 HashEntry lastRun = e;
00599 int lastIdx = idx;
00600 for (HashEntry last=next; last; last = last.next)
00601 {
00602 uint k = last.hash & sizeMask;
00603 if (k != lastIdx)
00604 {
00605 lastIdx = k;
00606 lastRun = last;
00607 }
00608 }
00609 newTable[lastIdx] = lastRun;
00610
00611
00612 for (HashEntry p = e; p !== lastRun; p = p.next)
00613 {
00614 uint k = p.hash & sizeMask;
00615 HashEntry n = newTable[k];
00616 newTable[k] = new HashEntry(p.key, p.hash, n, p.value);
00617 }
00618 }
00619 }
00620 }
00621 volatile table = newTable;
00622 }
00623
00627 final synchronized V remove (K key, uint hash, V value)
00628 {
00629 int c;
00630 HashEntry[] tab;
00631
00632 volatile c = count - 1;
00633 volatile tab = table;
00634
00635 uint index = hash & (tab.length - 1);
00636 HashEntry first = tab[index];
00637 HashEntry e = first;
00638
00639 while (e && (e.hash != hash || !matchKey (key, e.key)))
00640 e = e.next;
00641
00642 V oldValue = null;
00643 if (e)
00644 {
00645 V v;
00646 volatile v = e.value;
00647 if (value is null || value == v)
00648 {
00649 oldValue = v;
00650
00651
00652
00653
00654 HashEntry newFirst = e.next;
00655 for (HashEntry p = first; p !== e; p = p.next)
00656 newFirst = new HashEntry (p.key, p.hash, newFirst, p.value);
00657 tab[index] = newFirst;
00658
00659
00660 volatile count = c;
00661 }
00662 }
00663 return oldValue;
00664 }
00665
00666
00667 final synchronized void clear()
00668 {
00669 if (count)
00670 {
00671 HashEntry[] tab;
00672 volatile tab = table;
00673
00674 for (int i = 0; i < tab.length ; i++)
00675 tab[i] = null;
00676
00677
00678 volatile count = 0;
00679 }
00680 }
00681 }
00682
00683
00684
00685
00686
00701 public this (uint initialCapacity, float loadFactor, uint concurrencyLevel)
00702 {
00703 assert (loadFactor > 0);
00704
00705 if (concurrencyLevel > MAX_SEGMENTS)
00706 concurrencyLevel = MAX_SEGMENTS;
00707
00708
00709 int sshift = 0;
00710 int ssize = 1;
00711 while (ssize < concurrencyLevel)
00712 {
00713 ++sshift;
00714 ssize <<= 1;
00715 }
00716
00717 segmentShift = 32 - sshift;
00718 segmentMask = ssize - 1;
00719 this.segments = new Segment[ssize];
00720
00721 if (initialCapacity > MAXIMUM_CAPACITY)
00722 initialCapacity = MAXIMUM_CAPACITY;
00723
00724 int c = initialCapacity / ssize;
00725 if (c * ssize < initialCapacity)
00726 ++c;
00727
00728 int cap = 1;
00729 while (cap < c)
00730 cap <<= 1;
00731
00732 for (int i = 0; i < this.segments.length; ++i)
00733 this.segments[i] = new Segment (cap, loadFactor);
00734 }
00735
00745 public this (uint initialCapacity)
00746 {
00747 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
00748 }
00749
00754 public this ()
00755 {
00756 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
00757 }
00758
00769 public V get (K key)
00770 {
00771 uint hash = hash(key);
00772 return segmentFor(hash).get(key, hash);
00773 }
00774
00785 public bool containsKey (K key)
00786 {
00787 uint hash = hash(key);
00788 return segmentFor(hash).containsKey(key, hash);
00789 }
00790
00806 public V put (K key, V value)
00807 {
00808 assert (value);
00809
00810 uint hash = hash(key);
00811 return segmentFor(hash).put(key, hash, value, false);
00812 }
00813
00832 public V putIfAbsent (K key, V value)
00833 {
00834 assert (value);
00835
00836 uint hash = hash(key);
00837 return segmentFor(hash).put(key, hash, value, true);
00838 }
00839
00840
00851 public V remove (K key)
00852 {
00853 uint hash = hash(key);
00854 return segmentFor(hash).remove(key, hash, null);
00855 }
00856
00873 public bool remove (K key, V value)
00874 {
00875 uint hash = hash(key);
00876 return segmentFor(hash).remove(key, hash, value) !== null;
00877 }
00878
00879
00896 public V replace (K key, V value)
00897 {
00898 assert (value);
00899
00900 uint hash = hash(key);
00901 return segmentFor(hash).replace(key, hash, value);
00902 }
00903
00904
00908 public void clear ()
00909 {
00910 for (int i = 0; i < segments.length; ++i)
00911 segments[i].clear();
00912 }
00913
00914
00921 public KeyIterator keys ()
00922 {
00923 return new KeyIterator (this);
00924 }
00925
00932 public ValueIterator elements ()
00933 {
00934 return new ValueIterator (this);
00935 }
00936
00937
00938
00939
00940
00941
00942
00943 int opApply (int delegate(inout char[]) dg)
00944 {
00945 int result = 0;
00946 KeyIterator iterator = keys ();
00947
00948 while (iterator.hasNext)
00949 {
00950 char[] ca = cast(char[]) iterator.next;
00951 if ((result = dg (ca)) != 0)
00952 break;
00953 }
00954 return result;
00955 }
00956
00957
00958
00959
00960
00961
00962
00963 int opApply (int delegate(inout char[], inout Object) dg)
00964 {
00965 int result = 0;
00966 KeyIterator iterator = keys ();
00967
00968 while (iterator.hasNext)
00969 {
00970 HashEntry he = iterator.nextElement;
00971 char[] ca = cast(char[]) he.key;
00972 if ((result = dg (ca, he.value)) != 0)
00973 break;
00974 }
00975 return result;
00976 }
00977
00978
00979
00980
00981 abstract class HashIterator
00982 {
00983 int nextSegmentIndex;
00984 int nextTableIndex;
00985 HashEntry[] currentTable;
00986 HashEntry nextEntry;
00987 HashEntry lastReturned;
00988 HashMap map;
00989
00990 this (HashMap map)
00991 {
00992 this.map = map;
00993 nextSegmentIndex = map.segments.length - 1;
00994 nextTableIndex = -1;
00995 advance();
00996 }
00997
00998 final void advance ()
00999 {
01000 if (nextEntry !== null && (nextEntry = nextEntry.next) !== null)
01001 return;
01002
01003 while (nextTableIndex >= 0)
01004 {
01005 if ( (nextEntry = currentTable[nextTableIndex--]) !== null)
01006 return;
01007 }
01008
01009 while (nextSegmentIndex >= 0)
01010 {
01011 Segment seg = map.segments[nextSegmentIndex--];
01012 volatile if (seg.count)
01013 {
01014 currentTable = seg.table;
01015 for (int j = currentTable.length - 1; j >= 0; --j)
01016 {
01017 if ((nextEntry = currentTable[j]) !== null)
01018 {
01019 nextTableIndex = j - 1;
01020 return;
01021 }
01022 }
01023 }
01024 }
01025 }
01026
01027 public bool hasNext ()
01028 {
01029 return nextEntry !== null;
01030 }
01031
01032 HashEntry nextElement ()
01033 {
01034 if (nextEntry is null)
01035 throw new Exception ("no such element in HashMap");
01036
01037 lastReturned = nextEntry;
01038 advance ();
01039 return lastReturned;
01040 }
01041 }
01042
01043 class KeyIterator : HashIterator
01044 {
01045 this (HashMap map) {super (map);}
01046 public K next() { return super.nextElement().key; }
01047 }
01048
01049 class ValueIterator : HashIterator
01050 {
01051 this (HashMap map) {super (map);}
01052 public V next() { volatile return super.nextElement().value; }
01053 }
01054
01055 }