NetBSD/usr.bin/nbperf/graph3.c

/*	$NetBSD: graph3.c,v 1.6 2023/07/31 20:58:57 andvar Exp $*/

#define GRAPH_SIZE 3
#include "graph2.c"
fix RCSID. 2023-07-31 23:58:57 +03:00			`/* $NetBSD: graph3.c,v 1.6 2023/07/31 20:58:57 andvar Exp $*/`
Add nbperf(1), a minimal perfect hash function generator. Implemented are the 3-graph BDZ algorithm as well as the 2-graph and 3-graph CHM algorithms. All algorithms have expected linear run time and the smallest functions need around 2.85 bit/key. 2009-08-15 20:21:04 +04:00
Optimize nbperf - add fudge mode which gives a slightly slower hash function, but works almost always in the first iteration by avoiding degenerate edges - avoid keeping incidence lists around reducing the memory foot print by 30% - split edge processing from hashing as in the non-fudge case it is a reasonable costly part that often gets thrown away - merge graph2 and graph3 routines now that they are mostly the same 2021-01-07 19:03:08 +03:00			`#define GRAPH_SIZE 3`
			`#include "graph2.c"`