Main Page | Class Hierarchy | Alphabetical List | Class List | 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 
00025                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
00026 
00027         Written by Doug Lea with assistance from members of JCP JSR-166
00028         Expert Group and released to the public domain, as explained at
00029         http://creativecommons.org/licenses/publicdomain
00030         
00031         @version        Initial version, July 2004      
00032         @author         Doug Lea; ported/modified by Kris
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;          // jhash, fnv, or walter
00114 
00115     /*
00116      * The basic strategy is to subdivide the table among Segments,
00117      * each of which itself is a concurrently readable hash table.
00118      */
00119 
00120     /* ---------------- Constants -------------- */
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; // slightly conservative
00152 
00153 
00154     /* ---------------- Fields -------------- */
00155 
00160     private final int segmentMask;
00161 
00165     private final int segmentShift;
00166 
00170     private final Segment[] segments;
00171 
00172 
00173     /* ---------------- Small Utilities -------------- */
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         // the previous hash value
00250         c = 0;   
00251 
00252         // handle most of the key 
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         // handle the last 11 bytes 
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     /* ---------------- Inner Classes -------------- */
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          * Segments maintain a table of entry lists that are ALWAYS
00352          * kept in a consistent state, so can be read without locking.
00353          * Next fields of nodes are immutable (final).  All list
00354          * additions are performed at the front of each bin. This
00355          * makes it easy to check changes, and also fast to traverse.
00356          * When nodes would otherwise be changed, new nodes are
00357          * created to replace them. This works well for hash tables
00358          * since the bin lists tend to be short. (The average length
00359          * is less than two for the default load factor threshold.)
00360          *
00361          * Read operations can thus proceed without locking, but rely
00362          * on selected uses of volatiles to ensure that completed
00363          * write operations performed by other threads are
00364          * noticed. For most purposes, the "count" field, tracking the
00365          * number of elements, serves as that volatile variable
00366          * ensuring visibility.  This is convenient because this field
00367          * needs to be read in many read operations anyway:
00368          *
00369          *   - All (unsynchronized) read operations must first read the
00370          *     "count" field, and should not look at table entries if
00371          *     it is 0.
00372          *
00373          *   - All (synchronized) write operations should write to
00374          *     the "count" field after structurally changing any bin.
00375          *     The operations must not take any action that could even
00376          *     momentarily cause a concurrent read operation to see
00377          *     inconsistent data. This is made easier by the nature of
00378          *     the read operations in Map. For example, no operation
00379          *     can reveal that the table has grown but the threshold
00380          *     has not yet been updated, so there are no atomicity
00381          *     requirements for this with respect to reads.
00382          *
00383          * As a guide, all critical volatile reads and writes to the
00384          * count field are marked in code comments.
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         /* Specialized implementations of map methods */
00451 
00452         final V get (K key, uint hash) 
00453         {
00454             int c;
00455 
00456             // read-volatile
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             // read-volatile
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                    // write-volatile
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              * Reclassify nodes in each list to new Map.  Because we are
00565              * using power-of-two expansion, the elements from each bin
00566              * must either stay at same index, or move with a power of two
00567              * offset. We eliminate unnecessary node creation by catching
00568              * cases where old nodes can be reused because their next
00569              * fields won't change. Statistically, at the default
00570              * threshold, only about one-sixth of them need cloning when
00571              * a table doubles. The nodes they replace will be garbage
00572              * collectable as soon as they are no longer referenced by any
00573              * reader thread that may be in the midst of traversing table
00574              * right now.
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                 // We need to guarantee that any existing reads of old Map can
00584                 //  proceed. So we cannot yet null out each bin.
00585                 HashEntry e = oldTable[i];
00586 
00587                 if (e) 
00588                    {
00589                    HashEntry next = e.next;
00590                    uint idx = e.hash & sizeMask;
00591 
00592                    //  Single node on list
00593                    if (next is null)
00594                        newTable[idx] = e;
00595                    else 
00596                       {
00597                       // Reuse trailing consecutive sequence at same slot
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                       // Clone all remaining nodes
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                       // All entries following removed node can stay
00652                       // in list, but all preceding ones need to be
00653                       // cloned.                      
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                       // write-volatile
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                    // write-volatile
00678                    volatile count = 0; 
00679                }
00680         }
00681     }
00682 
00683 
00684 
00685     /* ---------------- Public operations -------------- */
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         // Find power-of-two sizes best matching arguments
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); // throws NullPointerException if key null
00772         return segmentFor(hash).get(key, hash);
00773     }
00774 
00785     public bool containsKey (K key) 
00786     {
00787         uint hash = hash(key); // throws NullPointerException if key null
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                 Iterate over all keys in hashmap
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                 Iterate over all keys in hashmap
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     /* ---------------- Iterator Support -------------- */
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 }

Generated on Sun Nov 7 19:06:51 2004 for Mango by doxygen 1.3.6