diff options
Diffstat (limited to 'kjs/create_hash_table')
| -rwxr-xr-x | kjs/create_hash_table | 203 |
1 files changed, 203 insertions, 0 deletions
diff --git a/kjs/create_hash_table b/kjs/create_hash_table new file mode 100755 index 000000000..a7df5eddf --- /dev/null +++ b/kjs/create_hash_table @@ -0,0 +1,203 @@ +#! /usr/bin/perl -w +# +# Static Hashtable Generator +# +# (c) 2000-2002 by Harri Porten <porten@kde.org> and +# David Faure <faure@kde.org> + +$file = $ARGV[0]; +shift; +my $findSize = 0; +my $includelookup = 0; +# Use -s as second argument to make it try many hash sizes +$findSize = 1 if (defined($ARGV[0]) && $ARGV[0] eq "-s"); +# Use -i as second argument to make it include "lookup.h" +$includelookup = 1 if (defined($ARGV[0]) && $ARGV[0] eq "-i"); +print STDERR "Creating hashtable for $file\n"; +open(IN, $file) or die "No such file $file"; + +@keys = (); +@values = (); +@attrs = (); +@params = (); + +my $inside = 0; +my $name; +my $size; +my $hashsize; +my $banner = 0; +my $namespace = "KJS"; + +sub calcTable(); +sub output(); +sub hashValue($); + +while (<IN>) { + chop; + s/^\s*//g; + if (/^\#|^$/) { + # comment. do nothing + } elsif (/^\@namespace\s+(\w+)/ && !$inside) { + $namespace = $1; + } elsif (/^\@begin/ && !$inside) { + if (/^\@begin\s*([:_\w]+)\s*(\d+)\s*$/) { + $inside = 1; + $name = $1; + $hashsize = $2; + } else { + printf STDERR "WARNING: \@begin without table name and hashsize, skipping $_\n"; + } + } elsif (/^\@end\s*$/ && $inside) { + + if($findSize) { + my $entriesnum=@keys; + print STDERR "Table: $name $entriesnum entries\n"; + for( $i=3 ; $i<79 ; ++$i) { $hashsize=$i ; calcTable(); } + } else { + calcTable(); + } + + output(); + @keys = (); + @values = (); + @attrs = (); + @params = (); + $inside = 0; + } elsif (/^([-:\@\w\[\=\]]+)\s*([\w\:-]+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) { + my $key = $1; + my $val = $2; + my $att = $3; + my $param = $4; + push(@keys, $key); + push(@values, $val); + printf STDERR "WARNING: Number of arguments missing for $key/$val\n" + if ( $att =~ m/Function/ && length($param) == 0); + push(@attrs, length($att) > 0 ? $att : "0"); + push(@params, length($param) > 0 ? $param : "0"); + } elsif ($inside) { + die "invalid data"; + } +} + +die "missing closing \@end" if ($inside); + +sub calcTable() { + @table = (); + @links = (); + $size = $hashsize; + my $collisions = 0; + my $maxdepth = 0; + my $i = 0; + foreach $key (@keys) { + my $depth = 0; + my $h = hashValue($key) % $hashsize; + while (defined($table[$h])) { + if (defined($links[$h])) { + $h = $links[$h]; + $depth++; + } else { + $collisions++; + $links[$h] = $size; + $h = $size; + $size++; + } + } + #print STDERR "table[$h] = $i\n"; + $table[$h] = $i; + $i++; + $maxdepth = $depth if ( $depth > $maxdepth); + } + + # Ensure table is big enough (in case of undef entries at the end) + if ( $#table+1 < $size ) { + $#table = $size-1; + } + #print STDERR "After loop: size=$size table=".($#table+1)."\n"; + + if ($findSize) { + my $emptycount = 0; + foreach $entry (@table) { + $emptycount++ if (!defined($entry)); + } + print STDERR "Hashsize: $hashsize Total Size: $size Empty: $emptycount MaxDepth: $maxdepth Collisions: $collisions\n"; + } +# my $debugtable = 0; +# foreach $entry (@table) { +# print STDERR "$debugtable " . (defined $entry ? $entry : '<undefined>'); +# print STDERR " -> " . $links[$debugtable] if (defined($links[$debugtable])); +# print STDERR "\n"; +# $debugtable++; +# } +} + +sub hashValue($) { + @chars = split(/ */, $_[0]); + my $val = 0; + foreach $c (@chars) { + $val += ord($c); + } + return $val; +} + +sub output() { + if (!$banner) { + $banner = 1; + print "/* Automatically generated from $file using $0. DO NOT EDIT ! */\n"; + } + + my $nameEntries = "${name}Entries"; + $nameEntries =~ s/:/_/g; + my $nameStringTable = "${name}Strings"; + $nameStringTable =~ y/:/_/; + + print "\n#include \"lookup.h\"\n" if ($includelookup); + print "\nusing namespace KJS;\n"; # because of DontDelete etc. + print "\nnamespace $namespace {\n"; + + # first, build the string table + my %soffset = (); + print "\nstatic const char $nameStringTable\[\] = {\n"; + my $s = "\0"; + print " \"\\0\"\n"; + for my $k (sort { length $b <=> length $a || $a cmp $b } @keys) { + if ($s =~ /^(.*)\Q$k\E\0/) { + $soffset{$k} = length $1; + } else { + $soffset{$k} = length $s; + print " \"$k\\0\"\n"; + $s .= $k; + $s .= "\0"; + } + } + print "};\n\n"; + + # now, dump the hash table + + print "\nstatic const struct HashEntry ".$nameEntries."[] = {\n"; + my $i = 0; + #print STDERR "writing out table with ".($#table+1)." entries\n"; + foreach $entry (@table) { + if (defined($entry)) { + my $key = $keys[$entry]; + print " \{ " . $soffset{$key}; + print ", " . $values[$entry]; + print ", " . $attrs[$entry]; + print ", " . $params[$entry]; + print ", "; + if (defined($links[$i])) { + print $links[$i] . " \}"; + } else { + print "-1 \}" + } + } else { + print " \{ 0, 0, 0, 0, -1 \}"; + } + print "," unless ($i == $size - 1); + print "\n"; + $i++; + } + print "};\n\n"; + print "const struct HashTable $name = "; + print "\{ 2, $size, ".$nameEntries.", $hashsize, ".$nameStringTable."\};\n\n"; + print "} // namespace\n"; +} |