JavaScriptCore/kjs/create_hash_table

#! /usr/bin/perl -w
#
# Static Hashtable Generator
#
# (c) 2000-2002 by Harri Porten <porten@kde.org> and
#                  David Faure <faure@kde.org>
# Modified (c) 2004 by Nikolas Zimmermann <wildfox@kde.org>
# Copyright (C) 2007 Apple Inc. All rights reserved.
#
# Part of the KJS library.
#
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Lesser General Public
# License as published by the Free Software Foundation; either
# version 2 of the License, or (at your option) any later version.
#
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with this library; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
#

use strict;

my $file = $ARGV[0];
shift;
my $includelookup = 0;

# Use -i as second argument to make it include "lookup.h"
$includelookup = 1 if (defined($ARGV[0]) && $ARGV[0] eq "-i");

# Use -n as second argument to make it use the third argument as namespace parameter ie. -n KDOM
my $useNameSpace = $ARGV[1] if (defined($ARGV[0]) && $ARGV[0] eq "-n");

print STDERR "Creating hashtable for $file\n";
open(IN, $file) or die "No such file $file";

my @keys = ();
my @values = ();
my @attrs = ();
my @params = ();
my @hashes = ();
my @table = ();
my @links = ();

my $inside = 0;
my $name;
my $size;
my $hashSizeMask;
my $banner = 0;
sub calcTable();
sub output();
sub hashValue($);

while (<IN>) {
  chop;
  s/^\s*//g;
  if (/^\#|^$/) {
      # comment. do nothing
    } elsif (/^\@begin/ && !$inside) {
      if (/^\@begin\s*([:_\w]+)\s*\d*\s*$/) {
        $inside = 1;
        $name = $1;
      } else {
         printf STDERR "WARNING: \@begin without table name and hashsize, skipping $_\n";
      }
    } elsif (/^\@end\s*$/ && $inside) {

      calcTable();

      output();
      @keys = ();
      @values = ();
      @attrs = ();
      @params = ();
      @table = ();
      @links = ();
      @hashes = ();
      $inside = 0;
    } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
      my $key = $1;
      my $val = $2;
      my $att = $3;
      my $param = $4;
      push(@keys, $key);
      push(@values, $val);
      push(@hashes, hashValue($key));
      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 ceilingToPowerOf2
{
    my ($size) = @_;

    my $powerOf2 = 1;
    while ($size > $powerOf2) {
        $powerOf2 <<= 1;
    }

    return $powerOf2;
}

sub calcTable() {
  my $hashsize = ceilingToPowerOf2(2 * @keys);
  $hashSizeMask = $hashsize - 1;
  $size = $hashsize;
  my $collisions = 0;
  my $maxdepth = 0;
  my $i = 0;
  foreach my $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++;
      }
    }
    $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;
  }
}

sub leftShift($$) {
    my ($value, $distance) = @_;
    return (($value << $distance) & 0xFFFFFFFF);
}

# Paul Hsieh's SuperFastHash
# http://www.azillionmonkeys.com/qed/hash.html
# Ported from UString..
sub hashValue($) {
  my @chars = split(/ */, $_[0]);

  # This hash is designed to work on 16-bit chunks at a time. But since the normal case
  # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
  # were 16-bit chunks, which should give matching results

  my $EXP2_32 = 4294967296;

  my $hash = 0x9e3779b9;
  my $l    = scalar @chars; #I wish this was in Ruby --- Maks
  my $rem  = $l & 1;
  $l = $l >> 1;

  my $s = 0;

  # Main loop
  for (; $l > 0; $l--) {
    $hash   += ord($chars[$s]);
    my $tmp = leftShift(ord($chars[$s+1]), 11) ^ $hash;
    $hash   = (leftShift($hash, 16)% $EXP2_32) ^ $tmp;
    $s += 2;
    $hash += $hash >> 11;
    $hash %= $EXP2_32;
  }

  # Handle end case
  if ($rem !=0) {
    $hash += ord($chars[$s]);
    $hash ^= (leftShift($hash, 11)% $EXP2_32);
    $hash += $hash >> 17;
  }

  # Force "avalanching" of final 127 bits
  $hash ^= leftShift($hash, 3);
  $hash += ($hash >> 5);
  $hash = ($hash% $EXP2_32);
  $hash ^= (leftShift($hash, 2)% $EXP2_32);
  $hash += ($hash >> 15);
  $hash = $hash% $EXP2_32;
  $hash ^= (leftShift($hash, 10)% $EXP2_32);
  
  # this avoids ever returning a hash code of 0, since that is used to
  # signal "hash not computed yet", using a value that is likely to be
  # effectively the same as 0 when the low bits are masked
  $hash = 0x80000000  if ($hash == 0);

  return $hash;
}

sub output() {
  if (!$banner) {
    $banner = 1;
    print "/* Automatically generated from $file using $0. DO NOT EDIT ! */\n";
  }

  my $nameEntries = "${name}Entries";
  $nameEntries =~ s/:/_/g;

  print "\n#include \"lookup.h\"\n" if ($includelookup);
  if ($useNameSpace) {
    print "\nnamespace ${useNameSpace}\n{\n";
    print "\nusing namespace KJS;";
  } else {
    print "\nnamespace KJS {\n";
  }
  print "\nstatic const struct HashEntry ".$nameEntries."[] = {\n";
  my $i = 0;
  
    foreach my $entry (@table) {
      if (defined($entry)) {
        my $key = $keys[$entry];
        print "   \{ \"" . $key . "\"";
        print ", { (intptr_t)" . $values[$entry] . " }";
        print ", " . $attrs[$entry];
        print ", " . $params[$entry];
        print ", ";
        if (defined($links[$i])) {
          print "&" . $nameEntries . "[" . $links[$i] . "]" . " \}";
        } else {
          print "0 \}"
        }
        print "/* " . $hashes[$entry] . " */ ";
      } else {
        print "   { 0, { 0 }, 0, 0, 0 }";
      }    
      print "," unless ($i == $size - 1);
      print "\n";
      $i++;
    }

  print "};\n\n";
  print "const struct HashTable $name = ";
  print "\{ 3, $size, $nameEntries, $hashSizeMask \};\n\n";
  print "} // namespace\n";
}