Changeset 39056 in webkit for trunk/JavaScriptCore/create_hash_table

Timestamp:

Dec 5, 2008, 5:05:06 PM (17 years ago)

Author:

[email protected]

Message:

<rdar://problem/6331749> Provide a mechanism to disable perfect hashing in the DOM at build time

Reviewed by Darin Adler.

Initial patch by Yosen Lin. Adapted for ToT WebKit by David Kilzer.

Added back the code that generates a "compact" hash (instead of a
perfect hash) as a build-time option using the
ENABLE(PERFECT_HASH_SIZE) macro as defined in Lookup.h.

JavaScriptCore:

• create_hash_table: Rename variables to differentiate perfect hash values from compact hash values. Added back code to compute compact hash tables. Generate both hash table sizes and emit conditionalized code based on ENABLE(PERFECT_HASH_SIZE).
• runtime/Lookup.cpp: (JSC::HashTable::createTable): Added version of createTable() for use with compact hash tables. (JSC::HashTable::deleteTable): Updated to work with compact hash tables.
• runtime/Lookup.h: Defined ENABLE(PERFECT_HASH_SIZE) macro here. (JSC::HashEntry::initialize): Set m_next to zero when using compact hash tables. (JSC::HashEntry::setNext): Added for compact hash tables. (JSC::HashEntry::next): Added for compact hash tables. (JSC::HashTable::entry): Added version of entry() for use with compact hash tables.
• runtime/Structure.cpp: (JSC::Structure::getEnumerablePropertyNames): Updated to work with compact hash tables.

WebCore:

• bindings/scripts/CodeGeneratorJS.pm: (GenerateImplementation): Compute the number of elements that will be stored in each hash table and pass it to GenerateHashTable(). (GenerateHashTable): Added new second parameter representing the number of elements to store in the compact hash table. Added back code to compute compact hash tables. Generate both hash table sizes and emit conditionalized code based on ENABLE(PERFECT_HASH_SIZE).

File:

• trunk/JavaScriptCore/create_hash_table (modified) (6 diffs)

trunk/JavaScriptCore/create_hash_table

@@ -47 +47 @@
 my $inside = 0;
 my $name;
-my $size;
+my $pefectHashSize;
+my $compactSize;
+my $compactHashSizeMask;
 my $banner = 0;
-sub calcSize();
+sub calcPerfectHashSize();
+sub calcCompactHashSize();
 sub output();
 sub jsc_ucfirst($);
@@ -66 +69 @@
         }
     } elsif (/^\@end\s*$/ && $inside) {
-        calcSize();
+        calcPerfectHashSize();
+        calcCompactHashSize();
         output();
 
@@ -117 +121 @@
 sub ceilingToPowerOf2
 {
-    my ($size) = @_;
+    my ($pefectHashSize) = @_;
 
     my $powerOf2 = 1;
-    while ($size > $powerOf2) {
+    while ($pefectHashSize > $powerOf2) {
         $powerOf2 <<= 1;
     }
@@ -127 +131 @@
 }
 
-sub calcSize()
+sub calcPerfectHashSize()
 {
 tableSizeLoop:
-    for ($size = ceilingToPowerOf2(scalar @keys); ; $size += $size) {
+    for ($pefectHashSize = ceilingToPowerOf2(scalar @keys); ; $pefectHashSize += $pefectHashSize) {
         my @table = ();
         foreach my $key (@keys) {
-            my $h = hashValue($key) % $size;
+            my $h = hashValue($key) % $pefectHashSize;
             next tableSizeLoop if $table[$h];
             $table[$h] = 1;
@@ -144 +148 @@
     my ($value, $distance) = @_;
     return (($value << $distance) & 0xFFFFFFFF);
+}
+
+sub calcCompactHashSize()
+{
+    my @table = ();
+    my @links = ();
+    my $compactHashSize = ceilingToPowerOf2(2 * @keys);
+    $compactHashSizeMask = $compactHashSize - 1;
+    $compactSize = $compactHashSize;
+    my $collisions = 0;
+    my $maxdepth = 0;
+    my $i = 0;
+    foreach my $key (@keys) {
+        my $depth = 0;
+        my $h = hashValue($key) % $compactHashSize;
+        while (defined($table[$h])) {
+            if (defined($links[$h])) {
+                $h = $links[$h];
+                $depth++;
+            } else {
+                $collisions++;
+                $links[$h] = $compactSize;
+                $h = $compactSize;
+                $compactSize++;
+            }
+        }
+        $table[$h] = $i;
+        $i++;
+        $maxdepth = $depth if ( $depth > $maxdepth);
+    }
 }
 
@@ -237 +271 @@
     print "   { 0, 0, 0, 0 }\n";
     print "};\n\n";
-    print "extern const struct HashTable $name = ";
-    print "\{ ", $size - 1, ", $nameEntries, 0 \};\n\n";
+    print "extern const struct HashTable $name =\n";
+    print "#if ENABLE(PERFECT_HASH_SIZE)\n";
+    print "    \{ ", $pefectHashSize - 1, ", $nameEntries, 0 \};\n";
+    print "#else\n";
+    print "    \{ $compactSize, $compactHashSizeMask, $nameEntries, 0 \};\n";
+    print "#endif\n\n";
     print "} // namespace\n";
 }