| /* |
| ------------------------------------------------------------------------------ |
| perfect.h: code to generate code for a hash for perfect hashing. |
| (c) Bob Jenkins, September 1996 |
| You may use this code in any way you wish, and it is free. No warranty. |
| I hereby place this in the public domain. |
| Source is http://burtleburtle.net/bob/c/perfect.h |
| ------------------------------------------------------------------------------ |
| */ |
| |
| #ifndef STANDARD |
| #include "standard.h" |
| #endif |
| |
| #ifndef PERFECT |
| #define PERFECT |
| |
| #define MAXKEYLEN 30 /* maximum length of a key */ |
| #define USE_SCRAMBLE 4096 /* use scramble if blen >= USE_SCRAMBLE */ |
| #define SCRAMBLE_LEN ((ub4)1<<16) /* length of *scramble* */ |
| #define RETRY_INITKEY 2048 /* number of times to try to find distinct (a,b) */ |
| #define RETRY_PERFECT 1 /* number of times to try to make a perfect hash */ |
| #define RETRY_HEX 200 /* RETRY_PERFECT when hex keys given */ |
| |
| /* the generated code for the final hash, assumes initial hash is done */ |
| struct gencode |
| { |
| char **line; /* array of text lines, 80 bytes apiece */ |
| /* |
| * The code placed here must declare "ub4 rsl" |
| * and assign it the value of the perfect hash using the function inputs. |
| * Later code will be tacked on which returns rsl or manipulates it according |
| * to the user directives. |
| * |
| * This code is at the top of the routine; it may and must declare any |
| * local variables it needs. |
| * |
| * Each way of filling in **line should be given a comment that is a unique |
| * tag. A testcase named with that tag should also be found which tests |
| * the generated code. |
| */ |
| ub4 len; /* number of lines available for final hash */ |
| ub4 used; /* number of lines used by final hash */ |
| |
| ub4 lowbit; /* for HEX, lowest interesting bit */ |
| ub4 highbit; /* for HEX, highest interesting bit */ |
| ub4 diffbits; /* bits which differ for some key */ |
| ub4 i,j,k,l,m,n,o; /* state machine used in hexn() */ |
| }; |
| typedef struct gencode gencode; |
| |
| /* user directives: perfect hash? minimal perfect hash? input is an int? */ |
| struct hashform |
| { |
| enum { |
| NORMAL_HM, /* key is a string */ |
| INLINE_HM, /* user will do initial hash, we must choose salt for them */ |
| HEX_HM, /* key to be hashed is a hexidecimal 4-byte integer */ |
| DECIMAL_HM, /* key to be hashed is a decimal 4-byte integer */ |
| AB_HM, /* key to be hashed is "A B", where A and B are (A,B) in hex */ |
| ABDEC_HM /* like AB_HM, but in decimal */ |
| } mode; |
| enum { |
| STRING_HT, /* key is a string */ |
| INT_HT, /* key is an integer */ |
| AB_HT /* dunno what key is, but input is distinct (A,B) pair */ |
| } hashtype; |
| enum { |
| NORMAL_HP, /* just find a perfect hash */ |
| MINIMAL_HP /* find a minimal perfect hash */ |
| } perfect; |
| enum { |
| FAST_HS, /* fast mode */ |
| SLOW_HS /* slow mode */ |
| } speed; |
| }; |
| typedef struct hashform hashform; |
| |
| /* representation of a key */ |
| struct key |
| { |
| char *name_k; /* the actual key */ |
| ub4 len_k; /* the length of the actual key */ |
| ub4 hash_k; /* the initial hash value for this key */ |
| struct key *next_k; /* next key */ |
| /* beyond this point is mapping-dependent */ |
| ub4 a_k; /* a, of the key maps to (a,b) */ |
| ub4 b_k; /* b, of the key maps to (a,b) */ |
| struct key *nextb_k; /* next key with this b */ |
| }; |
| typedef struct key key; |
| |
| /* things indexed by b of original (a,b) pair */ |
| struct bstuff |
| { |
| ub2 val_b; /* hash=a^tabb[b].val_b */ |
| key *list_b; /* tabb[i].list_b is list of keys with b==i */ |
| ub4 listlen_b; /* length of list_b */ |
| ub4 water_b; /* high watermark of who has visited this map node */ |
| }; |
| typedef struct bstuff bstuff; |
| |
| /* things indexed by final hash value */ |
| struct hstuff |
| { |
| key *key_h; /* tabh[i].key_h is the key with a hash of i */ |
| }; |
| typedef struct hstuff hstuff; |
| |
| /* things indexed by queue position */ |
| struct qstuff |
| { |
| bstuff *b_q; /* b that currently occupies this hash */ |
| ub4 parent_q; /* queue position of parent that could use this hash */ |
| ub2 newval_q; /* what to change parent tab[b] to to use this hash */ |
| ub2 oldval_q; /* original value of tab[b] */ |
| }; |
| typedef struct qstuff qstuff; |
| |
| /* return ceiling(log based 2 of x) */ |
| ub4 phash_log2(ub4 x); |
| |
| /* Given the keys, scramble[], and hash mode, find the perfect hash */ |
| void findhash(bstuff **tabb, hstuff **tabh, ub4 *alen, ub4 *blen, ub4 *salt, |
| gencode *final, ub4 *scramble, ub4 *smax, key *keys, ub4 nkeys, |
| hashform *form); |
| |
| /* private, but in a different file because it's excessively verbose */ |
| int inithex(key *keys, ub4 nkeys, ub4 alen, ub4 blen, ub4 smax, ub4 salt, |
| gencode *final, hashform *form); |
| |
| #endif /* PERFECT */ |