sub generate_hash_function()

in tools/PerfectHash.pm [95:173]

• 64 lines of code
• 14 McCabe index (conditional complexity)

sub generate_hash_function
{
	my ($keys_ref, $funcname, %options) = @_;

	# It's not worth passing this around as a parameter; just use a global.
	$case_fold = $options{case_fold} || 0;

	# Try different hash function parameters until we find a set that works
	# for these keys.  The multipliers are chosen to be primes that are cheap
	# to calculate via shift-and-add, so don't change them without care.
	# (Commonly, random seeds are tried, but we want reproducible results
	# from this program so we don't do that.)
	my $hash_mult1 = 31;
	my $hash_mult2;
	my $hash_seed1;
	my $hash_seed2;
	my @subresult;
  FIND_PARAMS:
	foreach (127, 257, 521, 1033, 2053)
	{
		$hash_mult2 = $_;    # "foreach $hash_mult2" doesn't work
		for ($hash_seed1 = 0; $hash_seed1 < 10; $hash_seed1++)
		{
			for ($hash_seed2 = 0; $hash_seed2 < 10; $hash_seed2++)
			{
				@subresult = _construct_hash_table(
					$keys_ref,   $hash_mult1, $hash_mult2,
					$hash_seed1, $hash_seed2);
				last FIND_PARAMS if @subresult;
			}
		}
	}

	# Choke if we couldn't find a workable set of parameters.
	die "failed to generate perfect hash" if !@subresult;

	# Extract info from _construct_hash_table's result array.
	my $elemtype = $subresult[0];
	my @hashtab  = @{ $subresult[1] };
	my $nhash    = scalar(@hashtab);

	# OK, construct the hash function definition including the hash table.
	my $f = '';
	$f .= sprintf "int\n";
	if (defined $options{fixed_key_length})
	{
		$f .= sprintf "%s(const void *key)\n{\n", $funcname;
	}
	else
	{
		$f .= sprintf "%s(const void *key, size_t keylen)\n{\n", $funcname;
	}
	$f .= sprintf "\tstatic const %s h[%d] = {\n", $elemtype, $nhash;
	for (my $i = 0; $i < $nhash; $i++)
	{
		$f .= sprintf "%s%6d,%s",
		  ($i % 8 == 0 ? "\t\t" : " "),
		  $hashtab[$i],
		  ($i % 8 == 7 ? "\n" : "");
	}
	$f .= sprintf "\n" if ($nhash % 8 != 0);
	$f .= sprintf "\t};\n\n";
	$f .= sprintf "\tconst unsigned char *k = (const unsigned char *) key;\n";
	$f .= sprintf "\tsize_t\t\tkeylen = %d;\n", $options{fixed_key_length}
	  if (defined $options{fixed_key_length});
	$f .= sprintf "\tuint32\t\ta = %d;\n",   $hash_seed1;
	$f .= sprintf "\tuint32\t\tb = %d;\n\n", $hash_seed2;
	$f .= sprintf "\twhile (keylen--)\n\t{\n";
	$f .= sprintf "\t\tunsigned char c = *k++";
	$f .= sprintf " | 0x20" if $case_fold;    # see comment below
	$f .= sprintf ";\n\n";
	$f .= sprintf "\t\ta = a * %d + c;\n", $hash_mult1;
	$f .= sprintf "\t\tb = b * %d + c;\n", $hash_mult2;
	$f .= sprintf "\t}\n";
	$f .= sprintf "\treturn h[a %% %d] + h[b %% %d];\n", $nhash, $nhash;
	$f .= sprintf "}\n";

	return $f;
}