File: create_hash_table

package info (click to toggle)
kdelibs 4:2.2.2-13.woody.14
  • links: PTS
  • area: main
  • in suites: woody
  • size: 36,832 kB
  • ctags: 40,077
  • sloc: cpp: 313,284; ansic: 20,558; xml: 11,448; sh: 11,318; makefile: 2,426; perl: 2,084; yacc: 1,663; java: 1,538; lex: 629; python: 300
file content (116 lines) | stat: -rwxr-xr-x 2,368 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#! /usr/bin/perl

$file = $ARGV[0];
open(IN, $file) or die "No such file $file";

@keys = ();
@values = ();
@attrs = ();

my $inside = 0;
my $name;
my $size;
my $hashsize;
my $banner = 0;

while (<IN>) {
  chop; 
  s/^\s*//g; 
  if (/^\#|^$/) {
      # comment. do nothing
    } elsif (/^\@begin\s*(\w+)\s*(\d+)\s*$/ && !$inside) {
      $inside = 1;
      $name = $1;
      $hashsize = $2;
    } elsif (/^\@end\s*$/ && $inside) {
      calcTable();
      output();
      @keys = ();
      @values = ();
      @attrs = ();
      $inside = 0;
    } elsif (/^(\w+)\s*([\w\:]+)\s*([\w\|]*)\s*$/ && $inside) {
      push(@keys, $1);
      push(@values, $2);
      push(@attrs, length($3) > 0 ? $3 : "0");
    } else {
      die "invalid data";
    }
}

die "missing closing \@end" if ($inside);

sub calcTable() {
  @table = ();
  @links = ();
  $size = $hashsize;
  my $collisions = 0;
  my $i = 0;
  foreach $key (@keys) {
    my $h = hashValue($key) % $hashsize;
    while (defined($table[$h])) {
      if (defined($links[$h])) {
	$h = $links[$h];
      } else {
	$collisions++;
	$links[$h] = $size;
	$h = $size;
	$size++;
      }
    }
    $table[$h] = $i;
    $i++;
  }

# print "// Number of collisions: $collisions\n";
#  printf "total size: $size\n";
#  my $i = 0;
#  foreach $entry (@table) {
#    print "$i " . $entry;
#    print " -> " . $links[$i] if (defined($links[$i]));
#    print "\n";
#    $i++;
#  }
}

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. DO NOT EDIT ! */\n";
  }

  print "\nnamespace KJS {\n";
  print "\nconst struct HashEntry2 ${name}Entries[] = {\n";
  my $i = 0;
  foreach $entry (@table) {
    if (defined($entry)) {
      my $key = $keys[$entry];
      print "   \{ \"" . $key . "\"";
      print ", " . $values[$entry];
      print ", " . $attrs[$entry] . ", ";
      if (defined($links[$i])) {
	print "&${name}Entries[$links[$i]]" . " \}";
      } else {
	print "0 \}"
      }
    } else {
      print "   \{ 0, 0, 0, 0 \}";
    }
    print "," unless ($i == $size - 1);
    print "\n";
    $i++;
  }
  print "};\n";
  print "\nconst struct HashTable2 $name = ";
  print "\{ 2, $size, ${name}Entries, $hashsize \};\n\n";
  print "}; // namespace\n";
}