runtime/PropertyMapHashTable.h

   1 /*
   2  *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU Library General Public
   6  *  License as published by the Free Software Foundation; either
   7  *  version 2 of the License, or (at your option) any later version.
   8  *
   9  *  This library is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  Library General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU Library General Public License
  15  *  along with this library; see the file COPYING.LIB.  If not, write to
  16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  *  Boston, MA 02110-1301, USA.
  18  *
  19  */
  20
  21 #ifndef PropertyMapHashTable_h
  22 #define PropertyMapHashTable_h
  23
  24 #include "UString.h"
  25 #include <wtf/Vector.h>
  26
  27 namespace JSC {
  28
  29     struct PropertyMapEntry {
  30         UString::Rep* key;
  31         unsigned offset;
  32         unsigned attributes;
  33         JSCell* specificValue;
  34         unsigned index;
  35
  36         PropertyMapEntry(UString::Rep* key, unsigned attributes, JSCell* specificValue)
  37             : key(key)
  38             , offset(0)
  39             , attributes(attributes)
  40             , specificValue(specificValue)
  41             , index(0)
  42         {
  43         }
  44
  45         PropertyMapEntry(UString::Rep* key, unsigned offset, unsigned attributes, JSCell* specificValue, unsigned index)
  46             : key(key)
  47             , offset(offset)
  48             , attributes(attributes)
  49             , specificValue(specificValue)
  50             , index(index)
  51         {
  52         }
  53     };
  54
  55     // lastIndexUsed is an ever-increasing index used to identify the order items
  56     // were inserted into the property map. It's required that getEnumerablePropertyNames
  57     // return the properties in the order they were added for compatibility with other
  58     // browsers' JavaScript implementations.
  59     struct PropertyMapHashTable {
  60         unsigned sizeMask;
  61         unsigned size;
  62         unsigned keyCount;
  63         unsigned deletedSentinelCount;
  64         unsigned lastIndexUsed;
  65         Vector<unsigned>* deletedOffsets;
  66         unsigned entryIndices[1];
  67
  68         PropertyMapEntry* entries()
  69         {
  70             // The entries vector comes after the indices vector.
  71             // The 0th item in the entries vector is not really used; it has to
  72             // have a 0 in its key to allow the hash table lookup to handle deleted
  73             // sentinels without any special-case code, but the other fields are unused.
  74             return reinterpret_cast<PropertyMapEntry*>(&entryIndices[size]);
  75         }
  76
  77         static size_t allocationSize(unsigned size)
  78         {
  79             // We never let a hash table get more than half full,
  80             // So the number of indices we need is the size of the hash table.
  81             // But the number of entries is half that (plus one for the deleted sentinel).
  82             return sizeof(PropertyMapHashTable)
  83                 + (size - 1) * sizeof(unsigned)
  84                 + (1 + size / 2) * sizeof(PropertyMapEntry);
  85         }
  86     };
  87
  88 } // namespace JSC
  89
  90 #endif // PropertyMapHashTable_h