Reviewed by Maciej
[WebKit-https.git] / JavaScriptCore / kjs / create_hash_table
1 #! /usr/bin/perl -w
2 #
3 # Static Hashtable Generator
4 #
5 # (c) 2000-2002 by Harri Porten <porten@kde.org> and
6 #                  David Faure <faure@kde.org>
7 # Modified (c) 2004 by Nikolas Zimmermann <wildfox@kde.org>
8
9 use strict;
10
11 my $file = $ARGV[0];
12 shift;
13 my $findSize = 0;
14 my $includelookup = 0;
15 # Use -s as second argument to make it try many hash sizes
16 $findSize = 1 if (defined($ARGV[0]) && $ARGV[0] eq "-s");
17 # Use -i as second argument to make it include "lookup.h"
18 $includelookup = 1 if (defined($ARGV[0]) && $ARGV[0] eq "-i");
19 # Use -n as second argument to make it use the third
20 #      argument as namespace parameter ie. -n KDOM
21 my $useNameSpace = $ARGV[1] if (defined($ARGV[0]) && $ARGV[0] eq "-n");
22
23 print STDERR "Creating hashtable for $file\n";
24 open(IN, $file) or die "No such file $file";
25
26 my @keys = ();
27 my @values = ();
28 my @attrs = ();
29 my @params = ();
30 my @hashes = ();
31 my @table = ();
32 my @links = ();
33
34 my $inside = 0;
35 my $name;
36 my $size;
37 my $hashsize;
38 my $banner = 0;
39 sub calcTable();
40 sub output();
41 sub hashValue($);
42
43 while (<IN>) {
44   chop;
45   s/^\s*//g;
46   if (/^\#|^$/) {
47       # comment. do nothing
48     } elsif (/^\@begin/ && !$inside) {
49       if (/^\@begin\s*([:_\w]+)\s*(\d+)\s*$/) {
50         $inside = 1;
51         $name = $1;
52         $hashsize = $2;
53       } else {
54          printf STDERR "WARNING: \@begin without table name and hashsize, skipping $_\n";
55       }
56     } elsif (/^\@end\s*$/ && $inside) {
57
58       if($findSize) {
59         my $entriesnum=@keys;
60         print STDERR "Table: $name   $entriesnum entries\n";
61         for( my $i=3 ; $i<79 ; ++$i) { $hashsize=$i ; calcTable(); }
62       } else {
63         calcTable();
64       }
65
66       output();
67       @keys = ();
68       @values = ();
69       @attrs = ();
70       @params = ();
71       @table = ();
72       @links = ();
73       @hashes = ();
74       $inside = 0;
75     } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
76       my $key = $1;
77       my $val = $2;
78       my $att = $3;
79       my $param = $4;
80       push(@keys, $key);
81       push(@values, $val);
82       push(@hashes, hashValue($key));
83       printf STDERR "WARNING: Number of arguments missing for $key/$val\n"
84         if ( $att =~ m/Function/ && length($param) == 0);
85       push(@attrs, length($att) > 0 ? $att : "0");
86       push(@params, length($param) > 0 ? $param : "0");
87     } elsif ($inside) {
88       die "invalid data {" . $_ . "}";
89     }
90 }
91
92 die "missing closing \@end" if ($inside);
93
94 sub calcTable() {
95   $size = $hashsize;
96   my $collisions = 0;
97   my $maxdepth = 0;
98   my $i = 0;
99   foreach my $key (@keys) {
100     my $depth = 0;
101     my $h = hashValue($key) % $hashsize;
102     while (defined($table[$h])) {
103       if (defined($links[$h])) {
104         $h = $links[$h];
105         $depth++;
106       } else {
107         $collisions++;
108         $links[$h] = $size;
109         $h = $size;
110         $size++;
111       }
112     }
113     #print STDERR "table[$h] = $i\n";
114     $table[$h] = $i;
115     $i++;
116     $maxdepth = $depth if ( $depth > $maxdepth);
117   }
118
119   # Ensure table is big enough (in case of undef entries at the end)
120   if ( $#table+1 < $size ) {
121     $#table = $size-1;
122   }
123   #print STDERR "After loop: size=$size table=".($#table+1)."\n";
124
125   if ($findSize) {
126     my $emptycount = 0;
127     foreach my $entry (@table) {
128       $emptycount++ if (!defined($entry));
129     }
130     print STDERR "Hashsize: $hashsize  Total Size: $size Empty: $emptycount MaxDepth: $maxdepth Collisions: $collisions\n";
131   }
132 #  my $debugtable = 0;
133 #  foreach my $entry (@table) {
134 #    print STDERR "$debugtable " . (defined $entry ? $entry : '<undefined>');
135 #    print STDERR " -> " . $links[$debugtable] if (defined($links[$debugtable]));
136 #    print STDERR "\n";
137 #    $debugtable++;
138 #  }
139 }
140
141 # Paul Hsieh's SuperFastHash
142 # http://www.azillionmonkeys.com/qed/hash.html
143 # Ported from UString..
144 sub hashValue($) {
145   my @chars = split(/ */, $_[0]);
146
147   # This hash is designed to work on 16-bit chunks at a time. But since the normal case
148   # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
149   # were 16-bit chunks, which should give matching results
150
151   my $EXP2_32 = 4294967296;
152
153   my $hash = 0x9e3779b9;
154   my $l    = scalar @chars; #I wish this was in Ruby --- Maks
155   my $rem  = $l & 1;
156   $l = $l >> 1;
157
158   my $s = 0;
159
160   # Main loop
161   for (; $l > 0; $l--) {
162     $hash   += ord($chars[$s]);
163     my $tmp = (ord($chars[$s+1]) << 11) ^ $hash;
164     $hash   = (($hash << 16)% $EXP2_32) ^ $tmp;
165     $s += 2;
166     $hash += $hash >> 11;
167   }
168
169   # Handle end case
170   if ($rem !=0) {
171     $hash += ord($chars[$s]);
172     $hash ^= (($hash << 11)% $EXP2_32);
173     $hash += $hash >> 17;
174   }
175
176   # Force "avalanching" of final 127 bits
177   $hash ^= ($hash << 3);
178   $hash += ($hash >> 5);
179   $hash = ($hash% $EXP2_32);
180   $hash ^= (($hash << 2)% $EXP2_32);
181   $hash += ($hash >> 15);
182   $hash = $hash% $EXP2_32;
183   $hash ^= (($hash << 10)% $EXP2_32);
184   
185   # this avoids ever returning a hash code of 0, since that is used to
186   # signal "hash not computed yet", using a value that is likely to be
187   # effectively the same as 0 when the low bits are masked
188   $hash = 0x80000000  if ($hash == 0);
189
190   return $hash;
191 }
192
193 sub output() {
194   if (!$banner) {
195     $banner = 1;
196     print "/* Automatically generated from $file using $0. DO NOT EDIT ! */\n";
197   }
198
199   my $nameEntries = "${name}Entries";
200   $nameEntries =~ s/:/_/g;
201
202   print "\n#include \"lookup.h\"\n" if ($includelookup);
203   if ($useNameSpace) {
204     print "\nnamespace ${useNameSpace}\n{\n";
205     print "\nusing namespace KJS;";
206   } else {
207     print "\nnamespace KJS {\n";
208   }
209   print "\nstatic const struct HashEntry ".$nameEntries."[] = {\n";
210   my $i = 0;
211   #print STDERR "writing out table with ".($#table+1)." entries\n";
212   
213   if ($hashsize eq 0) {
214     # To make the hash table lookup code fast, we don't allow tables of size 0.
215     # That way it can do a modulo by the size without a special case to avoid division by 0.
216     print "   \{ 0, 0, 0, 0, 0 \}\n";
217     $hashsize = 1;
218     $size = 1;
219   } else {
220     foreach my $entry (@table) {
221       if (defined($entry)) {
222         my $key = $keys[$entry];
223         print "   \{ \"" . $key . "\"";
224         print ", " . $values[$entry];
225         print ", " . $attrs[$entry];
226         print ", " . $params[$entry];
227         print ", ";
228         if (defined($links[$i])) {
229           print "&" . $nameEntries . "[" . $links[$i] . "]" . " \}";
230         } else {
231           print "0 \}"
232         }
233         print "/* " . $hashes[$entry] . " */ ";
234       } else {
235         print "   \{ 0, 0, 0, 0, 0 \}";
236       }    
237       print "," unless ($i == $size - 1);
238       print "\n";
239       $i++;
240     }
241   }
242   print "};\n\n";
243   print "const struct HashTable $name = ";
244   print "\{ 2, $size, ".$nameEntries.", $hashsize \};\n\n";
245   print "} // namespace\n";
246 }