On Mon, Apr 12, 2010 at 10:59:11AM -0400, fo...@cfengine.com wrote:
Forum: Cfengine Help
Subject: Re: Cfengine Help: Possible bug in cfengine 2
Author: kevinmusker
Link to topic: https://cfengine.com/forum/read.php?3,16865,16866#msg-16866
The hang will occur consistently on every run as soon as it tries to parse the
file in question. We have been using cfengine quite extensively for 3 years,
and this is the first time we've had this issue. Maybe the hashing function
doesn't produce a uniform distribution, making a value of 0 less likely than
some of the others?
To further verify the problem, I wrote a short script to generate other strings
that hash to zero - trying a few of these all produced the same hang.
E.g. ADIg, ATKI, AhMB
Attached is a small perl script that will, I believe, calculate the hash value
for a given class name. It takes a list of classes on stdin, and writes
to stdout.
[becker...@mars:~]$ echo voip_group | ./cf_hash.pl
Value [voip_group] hashes to slot: 0
[becker...@mars:~]$ echo ADIg | ./cf_hash.pl
Value [ADIg] hashes to slot: 0
[becker...@mars:~]$ echo desktops | ./cf_hash.pl
Value [desktops] hashes to slot: 1040
The hashing function isn't great--two inputs located "next" to eachother
such as "classA" and "classB" will hash to neighboring slot values
3269 and 3270--but it doesn't appear to be horribly degenerate either.
I ran 300 or so classes through my script and found 8 collisions.
--
Jesse Becker
NHGRI Linux support (Digicon Contractor)
#!/usr/bin/perl -w
use strict;
my $table_size = 4969;
my $alphabet = 61;
sub cf_hash {
my $var=shift || '';
my @arr = split(//, $var);
my $slot = 0;
foreach my $letter (@arr) {
$slot = ($alphabet * $slot + ord($letter)) % $table_size;
}
return $slot;
}
while (my $var = <>) {
chomp $var;
my $slot =cf_hash($var);
print "$var -> $slot\n";
}
_______________________________________________
Help-cfengine mailing list
Help-cfengine@cfengine.org
https://cfengine.org/mailman/listinfo/help-cfengine
