hashgen.html

产生哈希函数的代码

are protected members of the lookup class.

<br><dt><code>--no-include-string-h</code>
<dt><code>-i-</code>
<dd>By default the generated code will include &lt;string.h&gt;
(or &lt;cstring&gt; for C++), which is needed to declare <code>strcmp()</code>
(or <code>memcmp()</code>), and <code>NULL</code> (for C.)

<p>If the option is disabled, it becomes you responsibility.

<br><dt><code>--size=SIZE</code>
<dt><code>-N SIZE</code>
<dd><code>SIZE</code> must be between 0 and 9, the default value is 0. 
Affects the size of the generated hash table, the larger is the
value, the larger will be the hash table (this is true
only for large keysets).

<p>Larger hash tables will decrease time necessary to decide that a
key does not belong to the set (there will be more empty slots in the
hash table; when we hit an empty slot there is no need to compare
keys).  At the same time, very large hash tables may increase time of
successful searches a negligible amount because of worse locality
(more CPU cache misses.)

<br><dt><code>--min-expected-char=MINCHARCODE</code>
<dt><code>--max-expected-char=MAXCHARCODE</code>
<dt><code>-m MINCHARCODE</code>
<dt><code>-M MAXCHARCODE</code>
<dd><code>M??CHARCODE</code> is decimal, hexadecimal (0xnn),
or octal (0nnn) character code. 
The default values are 0x01 and 0xff respectively.

<p>More likely than not the keys you are going to look up are not
random byte arrays but rather the result of some kind of parsing. 
E.g., a C keyword is going to consist of nothing but lower case
letters.

<p>Narrowing the range of expected characters will result in smaller
lookup tables. But be warned that <strong>if the character range
is violated at runtime, the results may be disastrous</strong>.

<p>If <code>min-expected-char</code> is 0, the <code>zero-term</code> option
is turned off (a zero terminated string cannot contain zeroes).

<br><dt><code>--no-zero-term</code>
<dt><code>-z-</code>
<dd>By default <code>hashgen</code> assumes that the input keys are standard
zero terminated C strings and the generated code will use
<code>strcmp()</code> for key comparison.

<p>If the option is disabled, <code>memcmp()</code> will be used instead,
the keys at runtime don't have to be zero terminated and may
contain NUL characters.

<p>The option is automattically disabled when a NUL character is
encountered in one of the input keys, or the <code>min-expected-char</code>
option is set to 0.

<br><dt><code>--no-length-switch</code>
<dt><code>-S-</code>
<dd>The program tries to make the output code that calculates the hash
values of the keys of varying length as efficient as possible. 
Some compilers (including GCC) can compile switch statements
that branch on consequtive values into very efficient jump tables.

<p>If you know that the target compiler cannot do that, disable the option,
in this case <code>if</code>/<code>goto</code> pairs will be generated instead.

<br><dt><code>--optimize-hits</code>
<dt><code>-H</code>
<dd>By default, <code>hashgen</code> will try to minimize the time
of both successful searches and failures. When the option
is enabled, successful searches may become a couple of cycles
faster at the cost of failures, which will become a bit
slower.

<p>This option affects only the generated lookup code, not the algorithm
(the generated hash table will be the same.)

<p>You may want to enable this option if you know that the lookup function
is going to be called much more often for valid keys (in this case it
also makes sense to try to generate a smaller hash table).

<br><dt><code>--random</code>
<dt><code>-r</code>
<dd>Use pseudo-random initial values. For large keysets the hash table
will usually grow in size, but <code>hashgen</code> execution time will decrease.

<br><dt><code>--randimize</code>
<dt><code>-R</code>
<dd>By default, if the program is invoked twice with the same keyset
and the same options, the output will be the same. If this option
is enabled, the output will become non-deterministic. Implies
<code>--random</code> option.

<br><dt><code>--debug</code>
<dt><code>--D</code>
<dd>Enables verbose output useful only for debugging.

<br><dt><code>--version</code>
<dd>Show the program's version.

<br><dt><code>--help</code>
<dd>Prints a very short usage summary.

</dl>

<p><hr>
Node:<a name="Input">Input</a>,
Next:<a rel=next href="#%5boptions%5d">[options]</a>,
Previous:<a rel=previous href="#Options">Options</a>,
Up:<a rel=up href="#Top">Top</a>
<br>

<h2>The Input File Format</h2>

<p>The input file format is similar to that of MS Windows (R) <code>.ini</code> files. 
An input file is divided into sections. Every section starts with a section
header line (e.g. <code>[options]</code>) and
terminates at the beginning of the next section or end of file.

<p>There are three kinds of sections: <code>[options]</code>,
<code>[declarations]</code>, and <code>[entries]</code>. 
The order of sections does not matter.

<p>Empty lines, and lines starting with "#" are ignored (except for
the <code>[definitions]</code> section, which contains C/C++ declarations, and
is inserted into the generated source verbatim.)

<p>All sections except <code>[entries]</code> are optional. The <code>[entries]</code>
section header may be omitted if this section is first in the file. 
Thus, a minimal valid input file contains just a list of keywords,
each starting on a new line.

<ul>
<li><a href="#%5boptions%5d">[options]</a>:       The <code>[options]</code> Section
<li><a href="#%5bdeclarations%5d">[declarations]</a>:  The <code>[declarations]</code> Section
<li><a href="#%5bentries%5d">[entries]</a>:       The <code>[entries]</code> Section
</ul>

<p><hr>
Node:<a name="%5boptions%5d">[options]</a>,
Next:<a rel=next href="#%5bdeclarations%5d">[declarations]</a>,
Previous:<a rel=previous href="#Input">Input</a>,
Up:<a rel=up href="#Input">Input</a>
<br>

<h3>The <code>[options]</code> Section</h3>

<p>The <code>[options]</code> section contains all the program's options. 
This section is optional, and if it's omitted, all the options
will get their default values, or values specified on the command
line.

<p>Each option starts on a new line, and has <code>name=value</code> format. 
Empty lines and lines starting with the hash sign ("#") are
ignored.

<p>For detailed description of the program's options
see the Invoking Chapter (<a href="#Invoking">Invoking</a>.)

<p><hr>
Node:<a name="%5bdeclarations%5d">[declarations]</a>,
Next:<a rel=next href="#%5bentries%5d">[entries]</a>,
Previous:<a rel=previous href="#%5boptions%5d">[options]</a>,
Up:<a rel=up href="#Input">Input</a>
<br>

<h3>The <code>[declarations]</code> Section</h3>

<p>The <code>[declaration]</code> section contains arbitrary C/C++ declarations
that are copied verbatim into the generated code.

<p>Within the <code>[declarations]</code> section, lines starting with "#"
and empty lines are <em>not</em> ignored. If you need to comment
something, use C/C++ comments instead. No line may start with the
"[" character.

<p>One thing that <em>must</em> be present in the <code>[definitions]</code>
section is declaration of the structure of the key table entry. 
It must be a struct with the same name as specified by the
<code>entry-struct-name</code> option (the default value is <code>entry</code>). 
The first field of the struct must be <code>name</code> (or the name
specified with the <code>key-name</code> option), and be of type
<code>char*</code> (<code>const char*</code>) or <code>char[]</code>.

<p>Instead of defining the entry structure in the input file, you can do it
in some other file and just #include it in the <code>[declarations]</code>
section.

<p>If the <code>[declarations]</code> section is empty, the following entry
declaration will be generated:

<br><pre>struct entry {
  char* name;
};
</pre>

<p>(the names <code>entry</code> and <code>name</code> may be different, as specified
by <code>entry-struct-name</code> and <code>key-name</code> options.)

<p>If the <code>[declarations]</code> section is not empty, the entry
structure <strong>will not</strong> be defined automatically.

<p>Example:

<br><pre>[options]
entry-struct-name = TokenEntry

[declarations]
struct TokenEntry {
  const char* name;
  int token;
  int flags;
};

[entries]
"for",   1, 0
"while", 2, 0
"do",    3, 0
</pre>

<p>Also see the Example Chapter (<a href="#Example">Example</a>).

<p><hr>
Node:<a name="%5bentries%5d">[entries]</a>,
Next:<a rel=next href="#Example">Example</a>,
Previous:<a rel=previous href="#%5bdeclarations%5d">[declarations]</a>,
Up:<a rel=up href="#Input">Input</a>
<br>

<h3>The <code>[entries]</code> Section</h3>

<p>Each line of the <code>[entries]</code> section contains a key and
attributes associated with that key separated with commas. The
first field is the key itself, the attributes are optional. Empty
lines and lines starting with "#" are ignored.

<p>The syntax of each line must be suitable for C structure initializer
(without the enclosing braces).  It will be used to initialize an
entry in the key table, the structure of the entry is defined in
the <code>[declarations]</code> section (see <a href="#%5bdeclarations%5d">[declarations]</a>).

<p>The <code>[entries]</code> section is assumed by default when the parsing begins,
so a minimal valid input file may contain just a list of keywords,
each starting on a new line.

<p>Example:

<br><pre>[declarations]
struct entry {
  char* name;
  int id;
};

[entries]
"foo", 1
"bar", 2
"baz", 3
</pre>

<p>Within the key field C backslash escapes are allowed.  If the key
does not contain double quotes, commas, spaces, backslash escapes,
and does not start with "[", the surrounding double quotes may
be omitted:

<br><pre>[entries]
foo, 1
bar, 2
baz, 3
</pre>

<p>The attributes (after the first comma and up to the following newline
character) are not parsed at all, just included in the generated initializer
as is. It's your responsibility to ensure their syntax is correct.

<p>For instance, for entries like these

<br><pre>key1, 1 /* one */, 2, something
key2
key3, 3
<small>...</small>
</pre>

<p>the following initializers will be generated

<br><pre>{ "key1", 1 /* one */, 2, something },
{ "key2" },
{ "key3", 3 },
<small>...</small>
</pre>

<p><hr>
Node:<a name="Example">Example</a>,
Next:<a rel=next href="#Example%20Input">Example Input</a>,
Previous:<a rel=previous href="#%5bentries%5d">[entries]</a>,
Up:<a rel=up href="#Top">Top</a>
<br>

<h2>Example</h2>

<p>The following sections show an example of the input file
and lookup sources generated from it.

<ul>
<li><a href="#Example%20Input">Example Input</a>: 
<li><a href="#Generated%20Header">Generated Header</a>: 
<li><a href="#Generated%20Source">Generated Source</a>: 
<li><a href="#Generated%20Test%20Source">Generated Test Source</a>: 
<li><a href="#Machine%20Code">Machine Code</a>: 
</ul>

<p><hr>
Node:<a name="Example%20Input">Example Input</a>,
Next:<a rel=next href="#Generated%20Header">Generated Header</a>,
Previous:<a rel=previous href="#Example">Example</a>,
Up:<a rel=up href="#Example">Example</a>
<br>

<h3>Example Input</h3>

<br><pre>

# Hashgen input file example:
# Lookup class for C++ reserved words.

# The [entries] section: lists keys and associated data.
# The [entries] section header is implied by default.
# Double quotes around the key values are omitted.

asm,        TOKEN_ASM
auto,       TOKEN_AUTO
break,      TOKEN_BREAK
case,       TOKEN_CASE
catch,      TOKEN_CATCH
char,       TOKEN_CHAR
class,      TOKEN_CLASS
const,      TOKEN_CONST
continue,   TOKEN_CONTINUE
default,    TOKEN_DEFAULT
delete,     TOKEN_DELETE
do,         TOKEN_DO
double,     TOKEN_DOUBLE
else,       TOKEN_ELSE
enum,       TOKEN_ENUM
extern,     TOKEN_EXTERN
float,      TOKEN_FLOAT
for,        TOKEN_FOR
friend,     TOKEN_FRIEND
goto,       TOKEN_GOTO
if,         TOKEN_IF
inline,     TOKEN_INLINE
int,        TOKEN_INT
long,       TOKEN_LONG
new,        TOKEN_NEW
operator,   TOKEN_OPERATOR
overload,   TOKEN_OVERLOAD