Annotation of embedaddon/trafshow/hashtab.h, revision 1.1
1.1 ! misho 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 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hashtab.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / trafshow