From cfbb6bdc798b11ce9c755a5ed182a61e498f3494 Mon Sep 17 00:00:00 2001 From: Brendan Kehoe Date: Sun, 1 Feb 2009 12:23:37 +0000 Subject: regenerated --- doc/gperf_4.html | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) (limited to 'doc/gperf_4.html') diff --git a/doc/gperf_4.html b/doc/gperf_4.html index bec2f42..8d6219e 100644 --- a/doc/gperf_4.html +++ b/doc/gperf_4.html @@ -1,22 +1,23 @@ - + -Perfect Hash Function Generator - 2 Static search structures and GNU gperf + +Perfect Hash Function Generator - 3 Static search structures and GNU gperf Go to the first, previous, next, last section, table of contents.

2 Static search structures and GNU `gperf`

3 Static search structures and GNU `gperf`

-A static search structure is an Abstract Data Type with certain +A static search structure is an Abstract Data Type with certain fundamental operations, e.g., initialize, insert, and retrieve. Conceptually, all insertions occur before any retrievals. In practice, gperf generates a static array @@ -26,7 +27,7 @@ insertions. It is a useful data structure for representing static search sets. Static search sets occur frequently in software system applications. Typical static search sets include compiler reserved words, assembler instruction opcodes, and built-in shell interpreter -commands. Search set members, called keywords, are inserted into +commands. Search set members, called keywords, are inserted into the structure only once, usually during program initialization, and are not generally modified at run-time. @@ -55,13 +56,13 @@ function is defined by two properties:

It allows keyword recognition in a static search set using at most -one probe into the hash table. This represents the "perfect" +one probe into the hash table. This represents the “perfect” property.

The actual memory allocated to store the keywords is precisely large enough for the keyword set, and no larger. This is the -"minimal" property. +“minimal” property.

@@ -69,7 +70,7 @@ For most applications it is far easier to generate perfect hash functions than minimal perfect hash functions. Moreover, non-minimal perfect hash functions frequently execute faster than minimal ones in practice. This phenomena occurs since searching a -sparse keyword table increases the probability of locating a "null" +sparse keyword table increases the probability of locating a “null” entry, thereby reducing string comparisons. gperf's default behavior generates near-minimal perfect hash functions for keyword sets. However, gperf provides many options that permit -- cgit v1.2.1