hashgen.html

产生哈希函数的代码

private,    TOKEN_PRIVATE
protected,  TOKEN_PROTECTED
public,     TOKEN_PUBLIC
register,   TOKEN_REGISTER
return,     TOKEN_RETURN
short,      TOKEN_SHORT
signed,     TOKEN_SIGNED
sizeof,     TOKEN_SIZEOF
static,     TOKEN_STATIC
struct,     TOKEN_STRUCT
switch,     TOKEN_SWITCH
template,   TOKEN_TEMPLATE
this,       TOKEN_THIS
typedef,    TOKEN_TYPEDEF
union,      TOKEN_UNION
unsigned,   TOKEN_UNSIGNED
virtual,    TOKEN_VIRTUAL
void,       TOKEN_VOID
volatile,   TOKEN_VOLATILE
while,      TOKEN_WHILE


[options]

# All the options set explicitly for demonstration purposes
# (for most the default values would be okay.)

language = C++
header = cxx_keywords.h
source = cxx_keywords.cxx
test = cxx_keywords_test.cxx
namespace-name = Scanner
entry-struct-name = Token
key-name = text
lookup-struct-name = TokenHash
lookup-data-name = tokenHash
lookup-func-name = lookup
key-table-name = tokens
weight-table-name = charWeights
length-table-name = keyLengths
hash-table-name = hashTable
collision-table-name = hashCollisions

optimize-hits = yes
length-switch = yes
#inline-lookup-func = yes
static-lookup-data = no
min-expected-char = 0x30
max-expected-char = 0x7a


# The [declarations] sections: defines the structure
# of a key table entry (`Token' in this example).
# Also may contain any additional declarations,
# everything is copied verbatim into the generated header.

[declarations]

struct Token {
  const char* text;
  int token;
};

enum {
  TOKEN_ASM,
  TOKEN_AUTO,
  TOKEN_BREAK,
  TOKEN_CASE,
  TOKEN_CATCH,
  TOKEN_CHAR,
  TOKEN_CLASS,
  TOKEN_CONST,
  TOKEN_CONTINUE,
  TOKEN_DEFAULT,
  TOKEN_DELETE,
  TOKEN_DO,
  TOKEN_DOUBLE,
  TOKEN_ELSE,
  TOKEN_ENUM,
  TOKEN_EXTERN,
  TOKEN_FLOAT,
  TOKEN_FOR,
  TOKEN_FRIEND,
  TOKEN_GOTO,
  TOKEN_IF,
  TOKEN_INLINE,
  TOKEN_INT,
  TOKEN_LONG,
  TOKEN_NEW,
  TOKEN_OPERATOR,
  TOKEN_OVERLOAD,
  TOKEN_PRIVATE,
  TOKEN_PROTECTED,
  TOKEN_PUBLIC,
  TOKEN_REGISTER,
  TOKEN_RETURN,
  TOKEN_SHORT,
  TOKEN_SIGNED,
  TOKEN_SIZEOF,
  TOKEN_STATIC,
  TOKEN_STRUCT,
  TOKEN_SWITCH,
  TOKEN_TEMPLATE,
  TOKEN_THIS,
  TOKEN_TYPEDEF,
  TOKEN_UNION,
  TOKEN_UNSIGNED,
  TOKEN_VIRTUAL,
  TOKEN_VOID,
  TOKEN_VOLATILE,
  TOKEN_WHILE
};

</pre>

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

<h3>Generated Header</h3>

<br><pre>

// Generated by hashgen 1.0b (Dec  8 2002)
// language: C++
// 47 keys, hash table size 68 (145%), 0 collision(s)
// expected char range: 0x30-0x7a
// Mon Dec  9 14:50:21 2002

#ifndef TokenHash_INCLUDED
#define TokenHash_INCLUDED

#include &lt;cstring&gt;

namespace Scanner {

  struct Token {
    const char* text;
    int token;
  };

  enum {
    TOKEN_ASM,
    TOKEN_AUTO,
    TOKEN_BREAK,
    TOKEN_CASE,
    TOKEN_CATCH,
    TOKEN_CHAR,
    TOKEN_CLASS,
    TOKEN_CONST,
    TOKEN_CONTINUE,
    TOKEN_DEFAULT,
    TOKEN_DELETE,
    TOKEN_DO,
    TOKEN_DOUBLE,
    TOKEN_ELSE,
    TOKEN_ENUM,
    TOKEN_EXTERN,
    TOKEN_FLOAT,
    TOKEN_FOR,
    TOKEN_FRIEND,
    TOKEN_GOTO,
    TOKEN_IF,
    TOKEN_INLINE,
    TOKEN_INT,
    TOKEN_LONG,
    TOKEN_NEW,
    TOKEN_OPERATOR,
    TOKEN_OVERLOAD,
    TOKEN_PRIVATE,
    TOKEN_PROTECTED,
    TOKEN_PUBLIC,
    TOKEN_REGISTER,
    TOKEN_RETURN,
    TOKEN_SHORT,
    TOKEN_SIGNED,
    TOKEN_SIZEOF,
    TOKEN_STATIC,
    TOKEN_STRUCT,
    TOKEN_SWITCH,
    TOKEN_TEMPLATE,
    TOKEN_THIS,
    TOKEN_TYPEDEF,
    TOKEN_UNION,
    TOKEN_UNSIGNED,
    TOKEN_VIRTUAL,
    TOKEN_VOID,
    TOKEN_VOLATILE,
    TOKEN_WHILE
  };

  class TokenHash {
  public:
    static size_t size() {
      return 47;
    }
    static const Token* at(size_t index) {
      return tokens + index;
    }
    static const Token* lookup(const char* key) {
      return lookup(key, std::strlen(key));
    }
    static Token* lookup(const char* key, size_t len);
  protected:
    static unsigned char hashTable[68];
    static unsigned char charWeights[75];
    static Token tokens[47];
  };

  extern TokenHash tokenHash;

}

#endif
</pre>

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

<h3>Generated Source</h3>

<br><pre>

#include "cxx_keywords.h"

namespace Scanner {

  TokenHash tokenHash;

  unsigned char TokenHash::hashTable[68] = {
    // Hash table. Each element either points to a key table entry,
    // or is null (47) if there is no key with this hash value.
    /*  0 */  47, 47, 47,  0, 47, 47, 35, 40,  1, 47,
    /* 10 */  36,  3,  7, 13, 34,  8, 31, 38, 19,  4,
    /* 20 */  15,  6, 30, 25, 28, 11, 17, 23, 29, 10,
    /* 30 */   9, 39, 37, 20, 24, 18, 14, 16, 32,  2,
    /* 40 */  41, 45, 22, 47,  5, 33, 47, 26, 43, 47,
    /* 50 */  47, 42, 47, 21, 47, 27, 47, 12, 47, 47,
    /* 60 */  44, 47, 47, 47, 47, 47, 47, 46
  };

  unsigned char TokenHash::charWeights[75] = {
    // Weight table (one character hash function).
    /*  40 */                                          255, 255,
    /*  50 */  255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    /*  60 */  255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    /*  70 */  255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    /*  80 */  255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    /*  90 */  255, 255, 255, 255, 255, 255, 255,   0,  28,   7,
    /* 100 */   23,   0,  23,  14,  27,   8, 255, 255,   9,   1,
    /* 110 */   31,   0,   9, 255,   6,   0,   0,   4,  33,  26,
    /* 120 */   14,   0, 255
  };

  Token TokenHash::tokens[47] = {
    // Key table. Holds keys and associated data (order preserved.)
    /*  0 */  { "asm",         TOKEN_ASM },
    /*  1 */  { "auto",        TOKEN_AUTO },
    /*  2 */  { "break",       TOKEN_BREAK },
    /*  3 */  { "case",        TOKEN_CASE },
    /*  4 */  { "catch",       TOKEN_CATCH },
    /*  5 */  { "char",        TOKEN_CHAR },
    /*  6 */  { "class",       TOKEN_CLASS },
    /*  7 */  { "const",       TOKEN_CONST },
    /*  8 */  { "continue",    TOKEN_CONTINUE },
    /*  9 */  { "default",     TOKEN_DEFAULT },
    /* 10 */  { "delete",      TOKEN_DELETE },
    /* 11 */  { "do",          TOKEN_DO },
    /* 12 */  { "double",      TOKEN_DOUBLE },
    /* 13 */  { "else",        TOKEN_ELSE },
    /* 14 */  { "enum",        TOKEN_ENUM },
    /* 15 */  { "extern",      TOKEN_EXTERN },
    /* 16 */  { "float",       TOKEN_FLOAT },
    /* 17 */  { "for",         TOKEN_FOR },
    /* 18 */  { "friend",      TOKEN_FRIEND },
    /* 19 */  { "goto",        TOKEN_GOTO },
    /* 20 */  { "if",          TOKEN_IF },
    /* 21 */  { "inline",      TOKEN_INLINE },
    /* 22 */  { "int",         TOKEN_INT },
    /* 23 */  { "long",        TOKEN_LONG },
    /* 24 */  { "new",         TOKEN_NEW },
    /* 25 */  { "operator",    TOKEN_OPERATOR },
    /* 26 */  { "overload",    TOKEN_OVERLOAD },
    /* 27 */  { "private",     TOKEN_PRIVATE },
    /* 28 */  { "protected",   TOKEN_PROTECTED },
    /* 29 */  { "public",      TOKEN_PUBLIC },
    /* 30 */  { "register",    TOKEN_REGISTER },
    /* 31 */  { "return",      TOKEN_RETURN },
    /* 32 */  { "short",       TOKEN_SHORT },
    /* 33 */  { "signed",      TOKEN_SIGNED },
    /* 34 */  { "sizeof",      TOKEN_SIZEOF },
    /* 35 */  { "static",      TOKEN_STATIC },
    /* 36 */  { "struct",      TOKEN_STRUCT },
    /* 37 */  { "switch",      TOKEN_SWITCH },
    /* 38 */  { "template",    TOKEN_TEMPLATE },
    /* 39 */  { "this",        TOKEN_THIS },
    /* 40 */  { "typedef",     TOKEN_TYPEDEF },
    /* 41 */  { "union",       TOKEN_UNION },
    /* 42 */  { "unsigned",    TOKEN_UNSIGNED },
    /* 43 */  { "virtual",     TOKEN_VIRTUAL },
    /* 44 */  { "void",        TOKEN_VOID },
    /* 45 */  { "volatile",    TOKEN_VOLATILE },
    /* 46 */  { "while",       TOKEN_WHILE }
  };

  // Key characters must be in 0x30-0x7a range.

  Token* TokenHash::lookup(const char* key, size_t len) {
    using namespace std;
    register struct Token* p;
    register unsigned h = len;
    switch (h) {
      default: return 0;
      case 9:
      case 8:
      case 7:
      case 6:
      case 5:
      case 4:
        h += tokenHash.charWeights[(unsigned char)key[3]-48];
      case 3:
      case 2:
        h += tokenHash.charWeights[(unsigned char)key[1]-48];
      case 1:
        h += tokenHash.charWeights[(unsigned char)key[0]-48];
      case 0: ;
    }
    if (h &gt; 67)
      return 0;
    h = tokenHash.hashTable[h];
    if (h == 47)
      return 0;
    p = &amp;tokenHash.tokens[h];
    if (*key == *p-&gt;text &amp;&amp; !strcmp(key, p-&gt;text))
      return p;
    return 0;
  }

  // Please notice that in expression `a[x-c]', where `a' is a static
  // array and `c' is a constant, `a-c' is a constant sub-expression,
  // so the offset should not incur additional runtime overhead.

}

</pre>

<p><hr>
Node:<a name="Generated%20Test%20Source">Generated Test Source</a>,
Next:<a rel=next href="#Machine%20Code">Machine Code</a>,
Previous:<a rel=previous href="#Generated%20Source">Generated Source</a>,