Reviewed by Adele.

        - fixed <rdar://problem/3746676> SAP WebDynpro app hangs inside JavaScript property map hash table code (deleted sentinel problem)

        * kjs/property_map.h: Added some private functions.
        * kjs/property_map.cpp:
        (KJS::PropertyMap::clear): Set sentinelCount to 0.
        (KJS::PropertyMap::put): Complete search for the element before choosing to use the deleted-element sentinel.
        Also keep sentinel count up to date when we destroy a sentinel by overwriting with a new added element.
        (KJS::PropertyMap::expand): Added. Calls rehash with a size 2x the old size, or 16.
        (KJS::PropertyMap::rehash): Added. Refactored the rehash code into a separate function.
        (KJS::PropertyMap::remove): Add one to sentinelCount, and rehash if 1/4 or more of the elements are
        deleted-element sentinels.
        (KJS::PropertyMap::checkConsistency): Check the sentinelCount.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@7281 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog
index bc7a8d09e1ebfa7f5d178d96c86313a4b09ec54e..29f9393941dd31fbfd9ac066b12b7b8955b35d26 100644 (file)
--- a/JavaScriptCore/ChangeLog
+++ b/JavaScriptCore/ChangeLog
@@ -1,3 +1,20 @@
+2004-08-17  Darin Adler  <darin@apple.com>
+
+        Reviewed by Adele.
+
+        - fixed <rdar://problem/3746676> SAP WebDynpro app hangs inside JavaScript property map hash table code (deleted sentinel problem)
+
+        * kjs/property_map.h: Added some private functions.
+        * kjs/property_map.cpp:
+        (KJS::PropertyMap::clear): Set sentinelCount to 0.
+        (KJS::PropertyMap::put): Complete search for the element before choosing to use the deleted-element sentinel.
+        Also keep sentinel count up to date when we destroy a sentinel by overwriting with a new added element.
+        (KJS::PropertyMap::expand): Added. Calls rehash with a size 2x the old size, or 16.
+        (KJS::PropertyMap::rehash): Added. Refactored the rehash code into a separate function.
+        (KJS::PropertyMap::remove): Add one to sentinelCount, and rehash if 1/4 or more of the elements are
+        deleted-element sentinels.
+        (KJS::PropertyMap::checkConsistency): Check the sentinelCount.
+
 2004-08-16  Maciej Stachowiak  <mjs@apple.com>
 
         Code change by Eric Albert, reviewd by me.

diff --git a/JavaScriptCore/kjs/property_map.cpp b/JavaScriptCore/kjs/property_map.cpp
index 16f0f2d44331079c6b23f32c4aaebda21588a071..e455ffad5f7408a46632c932495b576343a3d74d 100644 (file)
--- a/JavaScriptCore/kjs/property_map.cpp
+++ b/JavaScriptCore/kjs/property_map.cpp
@@ -1,6 +1,6 @@
 /*
  *  This file is part of the KDE libraries
- *  Copyright (C) 2003 Apple Computer, Inc.
+ *  Copyright (C) 2004 Apple Computer, Inc.
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Library General Public
@@ -76,6 +76,7 @@ struct PropertyMapHashTable
     int sizeMask;
     int size;
     int keyCount;
+    int sentinelCount;
     int lastIndexUsed;
     PropertyMapHashTableEntry entries[1];
 };
@@ -140,6 +141,7 @@ void PropertyMap::clear()
         }
     }
     _table->keyCount = 0;
+    _table->sentinelCount = 0;
 }
 
 ValueImp *PropertyMap::get(const Identifier &name, int &attributes) const
@@ -276,6 +278,8 @@ void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
     unsigned h = rep->hash();
     int i = h & _table->sizeMask;
     int k = 0;
+    bool foundDeletedElement = false;
+    int deletedElementIndex;
 #if DUMP_STATISTICS
     ++numProbes;
     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
@@ -287,10 +291,10 @@ void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
             // Attributes are intentionally not updated.
             return;
         }
-        // If we find the deleted-element sentinel, insert on top of it.
-        if (key == &UString::Rep::null) {
-            key->deref();
-            break;
+        // If we find the deleted-element sentinel, remember it for use later.
+        if (key == &UString::Rep::null && !foundDeletedElement) {
+            foundDeletedElement = true;
+            deletedElementIndex = i;
         }
         if (k == 0)
             k = 1 | (h % _table->sizeMask);
@@ -299,7 +303,14 @@ void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
         ++numRehashes;
 #endif
     }
-    
+
+    // Use either the deleted element or the 0 at the end of the chain.
+    if (foundDeletedElement) {
+        i = deletedElementIndex;
+        _table->entries[i].key->deref();
+        --_table->sentinelCount;
+    }
+
     // Create a new hash table entry.
     rep->ref();
     _table->entries[i].key = rep;
@@ -339,6 +350,20 @@ void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes, int
 }
 
 void PropertyMap::expand()
+{
+    Table *oldTable = _table;
+    int oldTableSize = oldTable ? oldTable->size : 0;    
+    rehash(oldTableSize ? oldTableSize * 2 : 16);
+}
+
+void PropertyMap::rehash()
+{
+    assert(_table);
+    assert(_table->size);
+    rehash(_table->size);
+}
+
+void PropertyMap::rehash(int newTableSize)
 {
     checkConsistency();
     
@@ -346,7 +371,6 @@ void PropertyMap::expand()
     int oldTableSize = oldTable ? oldTable->size : 0;
     int oldTableKeyCount = oldTable ? oldTable->keyCount : 0;
     
-    int newTableSize = oldTableSize ? oldTableSize * 2 : 16;
     _table = (Table *)calloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry) );
     _table->size = newTableSize;
     _table->sizeMask = newTableSize - 1;
@@ -357,8 +381,8 @@ void PropertyMap::expand()
     if (key) {
         insert(key, _singleEntry.value, _singleEntry.attributes, 0);
         _singleEntry.key = 0;
-       // update the count, because single entries don't count towards
-       // the table key count
+        // update the count, because single entries don't count towards
+        // the table key count
        ++_table->keyCount;
        assert(_table->keyCount == 1);
     }
@@ -441,7 +465,11 @@ void PropertyMap::remove(const Identifier &name)
     _table->entries[i].attributes = DontEnum;
     assert(_table->keyCount >= 1);
     --_table->keyCount;
+    ++_table->sentinelCount;
     
+    if (_table->sentinelCount * 4 >= _table->size)
+        rehash();
+
     checkConsistency();
 }
 
@@ -641,10 +669,15 @@ void PropertyMap::checkConsistency()
         return;
 
     int count = 0;
+    int sentinelCount = 0;
     for (int j = 0; j != _table->size; ++j) {
         UString::Rep *rep = _table->entries[j].key;
-        if (!rep || rep == &UString::Rep::null)
+        if (!rep)
             continue;
+        if (rep == &UString::Rep::null) {
+            ++sentinelCount;
+            continue;
+        }
         unsigned h = rep->hash();
         int i = h & _table->sizeMask;
        int k = 0;
@@ -656,9 +689,10 @@ void PropertyMap::checkConsistency()
            i = (i + k) & _table->sizeMask;
         }
         assert(i == j);
-        count++;
+        ++count;
     }
     assert(count == _table->keyCount);
+    assert(sentinelCount == _table->sentinelCount);
     assert(_table->size >= 16);
     assert(_table->sizeMask);
     assert(_table->size == _table->sizeMask + 1);

diff --git a/JavaScriptCore/kjs/property_map.h b/JavaScriptCore/kjs/property_map.h
index a63e20f6aaf077ef9d01d4e5ea73888409b333d0..b2e3399569656f56b8634b7eae4f03dcd74d0b50 100644 (file)
--- a/JavaScriptCore/kjs/property_map.h
+++ b/JavaScriptCore/kjs/property_map.h
@@ -1,7 +1,6 @@
-// -*- c-basic-offset: 2 -*-
 /*
  *  This file is part of the KDE libraries
- *  Copyright (C) 2003 Apple Computer, Inc.
+ *  Copyright (C) 2004 Apple Computer, Inc.
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Library General Public
@@ -80,6 +79,8 @@ namespace KJS {
     private:
         static bool keysMatch(const UString::Rep *, const UString::Rep *);
         void expand();
+        void rehash();
+        void rehash(int newTableSize);
         
         void insert(UString::Rep *, ValueImp *value, int attributes, int index);