Cross Reference: /src/usr.bin/nbperf/graph2.c

History log of /src/usr.bin/nbperf/graph2.c
Revision	Date	Author	Comments
1.6	28-Jan-2021	joerg	Fix sanity check to match the fixed off-by-one logic in the sizing logic.
1.5	07-Jan-2021	joerg	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
1.4	21-Oct-2011	joerg	Add support for build as part of the toolchain. Add option for deterministic output (-p), which replaces the random seed with a incremental counter.
1.3	03-Mar-2010	joerg	Add a check for duplicate keys. The check is run once and quadratic in the hash collision chain length, which is expected to be fairly low.
1.2	22-Aug-2009	joerg	GCC's propolice complains about dynamic stack arrays to bite the bullet and introduce a compile constant that limits the number of hash results. Verify that the choosen hash function is not beyond that limit and just the upper limit as static size in the graph tree functions.
1.1	15-Aug-2009	joerg	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.

OpenGrok