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