Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members | Related Pages

HashMap.d

Go to the documentation of this file.
00001 /*******************************************************************************
00002 
00003         @file HashMap.d
00004         
00005         This software is provided 'as-is', without any express or implied
00006         warranty. In no event will the authors be held liable for damages
00007         of any kind arising from the use of this software.
00008         
00009         Permission is hereby granted to anyone to use this software for any 
00010         purpose, including commercial applications, and to alter it and/or 
00011         redistribute it freely, subject to the following restrictions:
00012         
00013         1. The origin of this software must not be misrepresented; you must 
00014            not claim that you wrote the original software. If you use this 
00015            software in a product, an acknowledgment within documentation of 
00016            said product would be appreciated but is not required.
00017 
00018         2. Altered source versions must be plainly marked as such, and must 
00019            not be misrepresented as being the original software.
00020 
00021         3. This notice may not be removed or altered from any distribution
00022            of the source.
00023 
00024         4. Derivative works are permitted, but they must carry this notice
00025            in full and credit the original source.
00026 
00027 
00028                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
00029 
00030 
00031         Written by Doug Lea with assistance from members of JCP JSR-166
00032         Expert Group and released to the public domain, as explained at
00033         http://creativecommons.org/licenses/publicdomain
00034         
00035         @version        Initial version, July 2004      
00036         @author         Doug Lea; ported/modified by Kris
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;          // jhash, fnv, or walter
00118 
00119     /*
00120      * The basic strategy is to subdivide the table among Segments,
00121      * each of which itself is a concurrently readable hash table.
00122      */
00123 
00124     /* ---------------- Constants -------------- */
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; // slightly conservative
00156 
00157 
00158     /* ---------------- Fields -------------- */
00159 
00164     private final int segmentMask;
00165 
00169     private final int segmentShift;
00170 
00174     private final Segment[] segments;
00175 
00176 
00177     /* ---------------- Small Utilities -------------- */
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         // the previous hash value
00254         c = 0;   
00255 
00256         // handle most of the key 
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         // handle the last 11 bytes 
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     /* ---------------- Inner Classes -------------- */
00318 
00331     private 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     class Segment
00353     {
00354         /*
00355          * Segments maintain a table of entry lists that are ALWAYS
00356          * kept in a consistent state, so can be read without locking.
00357          * Next fields of nodes are immutable (final).  All list
00358          * additions are performed at the front of each bin. This
00359          * makes it easy to check changes, and also fast to traverse.
00360          * When nodes would otherwise be changed, new nodes are
00361          * created to replace them. This works well for hash tables
00362          * since the bin lists tend to be short. (The average length
00363          * is less than two for the default load factor threshold.)
00364          *
00365          * Read operations can thus proceed without locking, but rely
00366          * on selected uses of volatiles to ensure that completed
00367          * write operations performed by other threads are
00368          * noticed. For most purposes, the "count" field, tracking the
00369          * number of elements, serves as that volatile variable
00370          * ensuring visibility.  This is convenient because this field
00371          * needs to be read in many read operations anyway:
00372          *
00373          *   - All (unsynchronized) read operations must first read the
00374          *     "count" field, and should not look at table entries if
00375          *     it is 0.
00376          *
00377          *   - All (synchronized) write operations should write to
00378          *     the "count" field after structurally changing any bin.
00379          *     The operations must not take any action that could even
00380          *     momentarily cause a concurrent read operation to see
00381          *     inconsistent data. This is made easier by the nature of
00382          *     the read operations in Map. For example, no operation
00383          *     can reveal that the table has grown but the threshold
00384          *     has not yet been updated, so there are no atomicity
00385          *     requirements for this with respect to reads.
00386          *
00387          * As a guide, all critical volatile reads and writes to the
00388          * count field are marked in code comments.
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 memcmp (cast(char*) a, cast(char*) b, a.length) == 0;
00451                 return false;
00452         }
00453 
00454         /* Specialized implementations of map methods */
00455 
00456         final V get (K key, uint hash) 
00457         {
00458             int c;
00459 
00460             // read-volatile
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             // read-volatile
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                    // write-volatile
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              * Reclassify nodes in each list to new Map.  Because we are
00569              * using power-of-two expansion, the elements from each bin
00570              * must either stay at same index, or move with a power of two
00571              * offset. We eliminate unnecessary node creation by catching
00572              * cases where old nodes can be reused because their next
00573              * fields won't change. Statistically, at the default
00574              * threshold, only about one-sixth of them need cloning when
00575              * a table doubles. The nodes they replace will be garbage
00576              * collectable as soon as they are no longer referenced by any
00577              * reader thread that may be in the midst of traversing table
00578              * right now.
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                 // We need to guarantee that any existing reads of old Map can
00588                 //  proceed. So we cannot yet null out each bin.
00589                 HashEntry e = oldTable[i];
00590 
00591                 if (e) 
00592                    {
00593                    HashEntry next = e.next;
00594                    uint idx = e.hash & sizeMask;
00595 
00596                    //  Single node on list
00597                    if (next is null)
00598                        newTable[idx] = e;
00599                    else 
00600                       {
00601                       // Reuse trailing consecutive sequence at same slot
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                       // Clone all remaining nodes
00616                       for (HashEntry p = e; p !== 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                       // All entries following removed node can stay
00656                       // in list, but all preceding ones need to be
00657                       // cloned.                      
00658                       HashEntry newFirst = e.next;                         
00659                       for (HashEntry p = first; p !== e; p = p.next)
00660                            newFirst = new HashEntry (p.key, p.hash, newFirst, p.value);
00661                       tab[index] = newFirst;
00662 
00663                       // write-volatile
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                    // write-volatile
00682                    volatile count = 0; 
00683                }
00684         }
00685     }
00686 
00687 
00688 
00689     /* ---------------- Public operations -------------- */
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         // Find power-of-two sizes best matching arguments
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); // throws NullPointerException if key null
00776         return segmentFor(hash).get(key, hash);
00777     }
00778 
00789     public bool containsKey (K key) 
00790     {
00791         uint hash = hash(key); // throws NullPointerException if key null
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 segmentFor(hash).remove(key, hash, value) !== 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                 Iterate over all keys in hashmap
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                 Iterate over all keys in hashmap
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     /* ---------------- Iterator Support -------------- */
00984 
00985     abstract 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 !== null && (nextEntry = nextEntry.next) !== null)
01005                 return;
01006 
01007             while (nextTableIndex >= 0) 
01008                   {
01009                   if ( (nextEntry = currentTable[nextTableIndex--]) !== 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]) !== null) 
01022                             {
01023                             nextTableIndex = j - 1;
01024                             return;
01025                             }
01026                          }
01027                      }
01028                   }
01029         }
01030 
01031         public bool hasNext () 
01032         { 
01033             return nextEntry !== 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     class KeyIterator : HashIterator  
01048     {
01049         this (HashMap map) {super (map);}
01050         public K next() { return super.nextElement().key; }
01051     }
01052 
01053     class ValueIterator : HashIterator 
01054     {
01055         this (HashMap map) {super (map);}
01056         public V next() { volatile return super.nextElement().value; }
01057     }
01058 
01059 }

Generated on Fri May 27 18:11:56 2005 for Mango by  doxygen 1.4.0