MMgc/GCHashtable-inlines.h

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
   2 /* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is [Open Source Virtual Machine.].
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Adobe System Incorporated.
  20  * Portions created by the Initial Developer are Copyright (C) 2004-2006
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Adobe AS3 Team
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either the GNU General Public License Version 2 or later (the "GPL"), or
  28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #ifndef __GCHashtable_inlines_
  41 #define __GCHashtable_inlines_
  42
  43 namespace MMgc
  44 {
  45     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
  46     GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::GCHashtableBase(uint32_t capacity) :
  47     table(NULL),
  48     tableSize(capacity),
  49     numValues(0),
  50     numDeleted(0)
  51     {
  52         if (tableSize > 0)
  53         {
  54             grow(false);
  55         }
  56         else
  57         {
  58             // appear as full table so grow, numValues will go to zero on rehash
  59             tableSize = 4;
  60             numValues = 4;
  61             table = EMPTY;
  62         }
  63     }
  64
  65     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
  66     GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::~GCHashtableBase()
  67     {
  68         if (table && table != EMPTY)
  69             ALLOCHANDLER::free(table);
  70         table = NULL;
  71         tableSize = 0;
  72         numValues = 0;
  73         numDeleted = 0;
  74     }
  75
  76     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
  77     void GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::clear()
  78     {
  79         if (table && table != EMPTY)
  80             ALLOCHANDLER::free(table);
  81         table = EMPTY;
  82         tableSize = 4;
  83         numValues = 4;
  84         numDeleted = 0;
  85     }
  86
  87     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
  88     uint32_t GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::find(const void* key, Entry* table, uint32_t tableSize)
  89     {
  90         GCAssert(key != DELETED);
  91
  92         uint32_t n = 0;
  93         // bitmask is defined in Symbian OS headers. changing to bitMask
  94         uint32_t const bitMask = (tableSize -1);
  95         uint32_t i = KEYHANDLER::hash(key) & bitMask;
  96         const void* k;
  97         while ((k = table[i].key) != NULL && !KEYHANDLER::equal(k, key))
  98         {
  99             i = (i +  (n += 1)) & bitMask;      // quadratic probe
 100         }
 101         GCAssert(i <= bitMask);
 102         return i;
 103     }
 104
 105     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
 106     void GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::put(const void* key, VAL value)
 107     {
 108         GCAssert(table != NULL);
 109
 110         // this is basically an inlined version of find() with one minor difference:
 111         // it notices if there are DELETED slots along the probe, and if there is one,
 112         // we recycle it rather than adding to the end of the probe chain. this allows us
 113         // to recycle deleted slots MUCH more quickly (without having to wait for a full rehash)
 114         // and can dramatically reduce the average probe depth if there are a lot of
 115         // insertions and removals.
 116         const uint32_t NO_DELINDEX = 0xffffffff;
 117         uint32_t delindex = NO_DELINDEX;
 118         // Quadratic probe: Hashtable size (S) is power of two
 119         //                  Probe function used: p(K,i) = (i*i + i)/2  [i = 0,1,2....S,....]
 120         //                  ith value in the probe sequence: [h(K) + p(K,i)] % S
 121         uint32_t n = 0;
 122         uint32_t const bitMask = (tableSize - 1);
 123         uint32_t i = KEYHANDLER::hash(key) & bitMask;
 124         const void* k;
 125         while ((k = table[i].key) != NULL && !KEYHANDLER::equal(k, key))
 126         {
 127             // note that we can't just stop at the first DELETED value we find --
 128             // we might have a matching value later in the chain. We choose
 129             // the first such entry so that subsequent searches are as short as possible
 130             // (choosing any other entry would be fine, just suboptimal)
 131             if (k == DELETED && delindex == NO_DELINDEX) delindex = i;
 132             i = (i + (n += 1)) & bitMask;       // quadratic probe
 133         }
 134         GCAssert(k == NULL || KEYHANDLER::equal(k, key));
 135         if (k == NULL)
 136         {
 137             if (delindex != NO_DELINDEX)
 138             {
 139                 // there's a deleted entry we can replace
 140                 i = delindex;
 141                 numDeleted--;
 142                 // note that we don't increment numValues here!
 143             }
 144             else
 145             {
 146                 // .75 load factor, note we don't take numDeleted into account
 147                 // numValues includes numDeleted
 148                 if (numValues * 4 >= tableSize * 3)
 149                 {
 150                     grow(false);
 151                     // grow rehashes, so no DELETED items, thus normal find() is OK
 152                     GCAssert(numDeleted == 0);
 153                     i = find(key, table, tableSize);
 154                     GCAssert(!(table[i].key));
 155                 }
 156                 numValues++;
 157             }
 158             table[i].key = key;
 159         }
 160         table[i].value = value;
 161     }
 162
 163     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
 164     VAL GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::remove(const void* key, bool allowRehash)
 165     {
 166         VAL ret = 0;
 167         uint32_t i = find(key, table, tableSize);
 168         if (table[i].key == key)
 169         {
 170             table[i].key = DELETED;
 171             ret = table[i].value;
 172             table[i].value = 0;
 173             numDeleted++;
 174             // this helps a bit on pathologic memory profiler use case, needs more investigation
 175             // 20% deleted == rehash
 176             if (allowRehash && (numValues - numDeleted) * 5 < tableSize)
 177             {
 178                 grow(true);
 179             }
 180         }
 181         return ret;
 182     }
 183
 184     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
 185     void GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::prune()
 186     {
 187         // this helps a bit on pathologic memory profiler use case, needs more investigation
 188         // 20% deleted == rehash
 189         // FIXME: Bugzilla
 190         if ((numValues - numDeleted) * 5 < tableSize)
 191         {
 192             grow(true);
 193         }
 194     }
 195
 196     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
 197     void GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::grow(bool isRemoval)
 198     {
 199         if (isRemoval)
 200         {
 201             // Bugzilla 553679: Skip table resizing in a removal situation if the heap
 202             // is in an abort state, we don't want to allocate during abort if we can
 203             // avoid it, and 'grow' is called when the collector clears its weak references.
 204             if (GCHeap::GetGCHeap()->GetStatus() == kMemAbort)
 205                 return;
 206         }
 207
 208         uint32_t newTableSize = tableSize;
 209
 210         uint32_t occupiedSlots = numValues - numDeleted;
 211         GCAssert(numValues >= numDeleted);
 212
 213         // grow or shrink as appropriate:
 214         // if we're greater than 50% full grow
 215         // if we're less than 10% shrink
 216         // else stay the same
 217         if (2 * occupiedSlots > tableSize)
 218             newTableSize <<= 1;
 219         else if (5 * occupiedSlots < tableSize && tableSize > kDefaultSize && table)
 220             newTableSize >>= 1;
 221
 222         Entry* newTable;
 223         newTable = (Entry*)ALLOCHANDLER::alloc(newTableSize*sizeof(Entry), isRemoval);
 224         if (!newTable)
 225             return;
 226
 227         VMPI_memset(newTable, 0, newTableSize*sizeof(Entry));
 228
 229         numValues = 0;
 230         numDeleted = 0;
 231
 232         if (table)
 233         {
 234             for (uint32_t i=0; i < tableSize; i++)
 235             {
 236                 const void* oldKey;
 237                 if ((oldKey=table[i].key) != NULL)
 238                 {
 239                     // inlined & simplified version of put()
 240                     if (oldKey != DELETED) {
 241                         uint32_t j = find(oldKey, newTable, newTableSize);
 242                         newTable[j].key = oldKey;
 243                         newTable[j].value = table[i].value;
 244                         numValues++;
 245                     }
 246                 }
 247             }
 248         }
 249
 250         if (table && table != EMPTY)
 251         {
 252             ALLOCHANDLER::free(table);
 253         }
 254         table = newTable;
 255         tableSize = newTableSize;
 256         GCAssert(table != NULL);
 257     }
 258
 259     template <typename VAL, class KEYHANDLER, class ALLOCHANDLER>
 260     int32_t GCHashtableBase<VAL, KEYHANDLER,ALLOCHANDLER>::nextIndex(int32_t index)
 261     {
 262         while(index < tableSize)
 263         {
 264             if (table[index].key > DELETED)
 265                 return (index + 1);
 266             index++;
 267         }
 268         return 0;
 269     }
 270
 271 }
 272
 273 #endif
 274