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         unsigned index;
  34
  35         PropertyMapEntry(UString::Rep* key, unsigned attributes)
  36             : key(key)
  37             , offset(0)
  38             , attributes(attributes)
  39             , index(0)
  40         {
  41         }
  42
  43         PropertyMapEntry(UString::Rep* key, unsigned offset, unsigned attributes, unsigned index)
  44             : key(key)
  45             , offset(offset)
  46             , attributes(attributes)
  47             , index(index)
  48         {
  49         }
  50     };
  51
  52     // lastIndexUsed is an ever-increasing index used to identify the order items
  53     // were inserted into the property map. It's required that getEnumerablePropertyNames
  54     // return the properties in the order they were added for compatibility with other
  55     // browsers' JavaScript implementations.
  56     struct PropertyMapHashTable {
  57         unsigned sizeMask;
  58         unsigned size;
  59         unsigned keyCount;
  60         unsigned deletedSentinelCount;
  61         unsigned lastIndexUsed;
  62         Vector<unsigned>* deletedOffsets;
  63         unsigned entryIndices[1];
  64
  65         PropertyMapEntry* entries()
  66         {
  67             // The entries vector comes after the indices vector.
  68             // The 0th item in the entries vector is not really used; it has to
  69             // have a 0 in its key to allow the hash table lookup to handle deleted
  70             // sentinels without any special-case code, but the other fields are unused.
  71             return reinterpret_cast<PropertyMapEntry*>(&entryIndices[size]);
  72         }
  73
  74         static size_t allocationSize(unsigned size)
  75         {
  76             // We never let a hash table get more than half full,
  77             // So the number of indices we need is the size of the hash table.
  78             // But the number of entries is half that (plus one for the deleted sentinel).
  79             return sizeof(PropertyMapHashTable)
  80                 + (size - 1) * sizeof(unsigned)
  81                 + (1 + size / 2) * sizeof(PropertyMapEntry);
  82         }
  83     };
  84
  85 } // namespace JSC
  86
  87 #endif // PropertyMapHashTable_h