Return to hashtab.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / trafshow

trafshow

    1: /*
    2: --------------------------------------------------------------------
    3: By Bob Jenkins, 1996.  hash.h.  Public Domain.
    4: 
    5: This implements a hash table.
    6: * Keys are unique.  Adding an item fails if the key is already there.
    7: * Keys and items are pointed at, not copied.  If you change the value
    8:   of the key after it is inserted then hfind will not be able to find it.
    9: * The hash table maintains a position that can be set and queried.
   10: * The table length doubles dynamically and never shrinks.  The insert
   11:   that causes table doubling may take a long time.
   12: * The table length splits when the table length equals the number of items
   13:   Comparisons usually take 7 instructions.
   14:   Computing a hash value takes 35+6n instructions for an n-byte key.
   15: 
   16:   hcreate  - create a hash table
   17:   hdestroy - destroy a hash table
   18:    hcount  - The number of items in the hash table
   19:    hkey    - key at the current position
   20:    hkeyl   - key length at the current position
   21:    hstuff  - stuff at the current position
   22:   hfind    - find an item in the table
   23:    hadd    - insert an item into the table
   24:    hdel    - delete an item from the table
   25:   hstat    - print statistics about the table
   26:    hfirst  - position at the first item in the table
   27:    hnext   - move the position to the next item in the table
   28: --------------------------------------------------------------------
   29: */
   30: 
   31: #ifndef STANDARD
   32: #include "standard.h"
   33: #endif
   34: 
   35: #ifndef HASHTAB
   36: #define HASHTAB
   37: 
   38: /* PRIVATE TYPES AND DEFINITIONS */
   39: 
   40: struct hitem
   41: {
   42:   ub1          *key;      /* key that is hashed */
   43:   ub4           keyl;     /* length of key */
   44:   void         *stuff;    /* stuff stored in this hitem */
   45:   ub4           hval;     /* hash value */
   46:   struct hitem *next;     /* next hitem in list */
   47: };
   48: typedef  struct hitem  hitem;
   49: 
   50: 
   51: struct htab
   52: {
   53:   struct hitem **table;   /* hash table, array of size 2^logsize */
   54:   word           logsize; /* log of size of table */
   55:   size_t         mask;    /* (hashval & mask) is position in table */
   56:   ub4            count;   /* how many items in this hash table so far? */
   57:   ub4            apos;    /* position in the array */
   58:   struct hitem  *ipos;    /* current item in the array */
   59:   struct reroot *space;   /* space for the hitems */
   60:   ub4            bcount;  /* # hitems useable in current block */
   61: };
   62: typedef  struct htab  htab;
   63: 
   64: 
   65: 
   66: 
   67: 
   68: /* PUBLIC FUNCTIONS */
   69: 
   70: /* hcreate - create a hash table
   71:    ARGUMENTS:
   72:      logsize - 1<<logsize will be the initial table length
   73:    RETURNS:
   74:      the new table
   75:  */
   76: htab *hcreate(word logsize);
   77: 
   78: 
   79: /* hdestroy - destroy a hash table
   80:    ARGUMENTS:
   81:      t - the hash table to be destroyed.  Note that the items and keys
   82:          will not be freed, the user created them and must destroy
   83:          them himself.
   84:    RETURNS:
   85:      nothing
   86:  */
   87: void  hdestroy(htab *t);
   88: 
   89: 
   90: /* hcount, hkey, hkeyl, hstuff
   91:      ARGUMENTS:
   92:      t - the hash table
   93:    RETURNS:
   94:      hcount - (ub4)    The number of items in the hash table
   95:      hkey   - (ub1 *)  key for the current item
   96:      hkeyl  - (ub4)    key length for the current item
   97:      hstuff - (void *) stuff for the current item
   98:    NOTE:
   99:      The current position always has an item as long as there
  100:        are items in the table, so hexist can be used to test if the
  101:        table is empty.
  102:      hkey, hkeyl, and hstuff will crash if hcount returns 0
  103:  */
  104: #define hcount(t) ((t)->count)
  105: #define hkey(t)   ((t)->ipos->key)
  106: #define hkeyl(t)  ((t)->ipos->keyl)
  107: #define hstuff(t) ((t)->ipos->stuff)
  108: 
  109: 
  110: 
  111: /* hfind - move the current position to a given key
  112:    ARGUMENTS:
  113:      t    - the hash table
  114:      key  - the key to look for
  115:      keyl - length of the key
  116:    RETURNS:
  117:      TRUE if the item exists, FALSE if it does not.
  118:      If the item exists, moves the current position to that item.
  119:  */
  120: word  hfind(htab *t, ub1 *key, ub4 keyl);
  121: 
  122: 
  123: /* hadd - add a new item to the hash table
  124:           change the position to point at the item with the key
  125:    ARGUMENTS:
  126:      t     - the hash table
  127:      key   - the key to look for
  128:      keyl  - length of the key
  129:      stuff - other stuff to be stored in this item
  130:    RETURNS:
  131:      FALSE if the operation fails (because that key is already there).
  132:  */
  133: word  hadd(htab *t, ub1 *key, ub4 keyl, void *stuff);
  134: 
  135: 
  136: /* hdel - delete the item at the current position
  137:           change the position to the following item
  138:   ARGUMENTS:
  139:     t    - the hash table
  140:   RETURNS:
  141:     FALSE if there is no current item (meaning the table is empty)
  142:   NOTE:
  143:     This frees the item, but not the key or stuff stored in the item.
  144:     If you want these then deal with them first.  For example:
  145:       if (hfind(tab, key, keyl))
  146:       {
  147:         free(hkey(tab));
  148:         free(hstuff(tab));
  149:         hdel(tab);
  150:       }
  151:  */
  152: word  hdel(htab *t);
  153: 
  154: 
  155: /* hfirst - move position to the first item in the table
  156:   ARGUMENTS:
  157:     t    - the hash table
  158:   RETURNS:
  159:     FALSE if there is no current item (meaning the table is empty)
  160:   NOTE:
  161:  */
  162: word hfirst(htab *t);
  163: 
  164: 
  165: /* hnext - move position to the next item in the table
  166:   ARGUMENTS:
  167:     t    - the hash table
  168:   RETURNS:
  169:     FALSE if the position wraps around to the beginning of the table
  170:   NOTE:
  171:     To see every item in the table, do
  172:       if (hfirst(t)) do
  173:       {
  174:         key   = hkey(t);
  175:         stuff = hstuff(t);
  176:       }
  177:       while (hnext(t));
  178:  */
  179: /* word hnext(htab *t); */
  180: #define hnext(t) \
  181:   ((!(t)->ipos) ? FALSE :  \
  182:    ((t)->ipos=(t)->ipos->next) ? TRUE : hnbucket(t))
  183: 
  184: /* hnbucket - PRIVATE - move to first item in the next nonempty bucket
  185:   ARGUMENTS:
  186:     t    - the hash table
  187:   RETURNS:
  188:     FALSE if the position wraps around to the beginning of the table
  189:   NOTE:
  190:     This is private to hashtab; do not use it externally.
  191:  */
  192: word hnbucket(htab *t);
  193: 
  194: 
  195: /* hstat - print statistics about the hash table
  196:   ARGUMENTS:
  197:     t    - the hash table
  198:   NOTE:
  199:     items <0>:  <#buckets with zero items> buckets
  200:     items <1>:  <#buckets with 1 item> buckets
  201:     ...
  202:     buckets: #buckets  items: #items  existing: x
  203:     ( x is the average length of the list when you look for an
  204:       item that exists.  When the item does not exists, the average
  205:       length is #items/#buckets. )
  206: 
  207:     If you put n items into n buckets, expect 1/(n!)e buckets to
  208:     have n items.  That is, .3678 0, .3678 1, .1839 2, ...
  209:     Also expect "existing" to be about 2.
  210:  */
  211: void hstat(FILE *fp, htab *t);
  212: 
  213: #endif   /* HASHTAB */