/* * t a b l e s . c */ /*)LIBRARY */ #ifdef DOCUMENTATION title tables Hash Table Handler Functions index Hash table handler functions index Create a new table index Delete a table element index Insert a new element into a table index Look a key up in a table index Scan through a table index Update a table element synopsis typedef char TABLE; TABLE * table(size) int size; tdelete(t,key) TABLE *t; char *key; tinsert(t,key,value) TABLE *t; char *key; int value; tlookup(t,key) TABLE *t; char *key; tnext(t,n,key,value) TABLE *t; int n; char **key; int *value; tupdate(t,key,value) TABLE *t; char *key; int value; internal The actual datatypes used are: typedef struct { char *key; int value; } PAIR; typedef struct { int tsize; PAIR tdata[]; } TABLE; PAIR * $$locate(t,key) TABLE *t; char *key; description Tables are associative memory. They consist of keys and associated values. You can add, delete, and change pairs of keys and values and look up the value associated with a key. Keys are arbitrary strings; values are arbitrary integers, except that NULL should not be used as a value since tlookup() returns NULL to indicate that a key was not found in the table. In many cases, value is actually a pointer to a string. Note the difference in the handling of key and value. The functions automatically copy the string that key points to (with savestr()) when they create a new table entry; hence, you can pass a pointer to a string in a buffer or anywhere. value, however, is treated as a simple int; if it points to a string somewhere, it is your responsibility to make sure that that string remains unchanged as long as you need it. Tables can be freed with free(); however, note that this will not free the space used for the keys in the table. You must free this space, and space used for value strings, if any; use tnext() to find all the elements. table(size) creates a new table and returns a pointer to it. The table has room for size elements, and cannot grow; however, the space used for deleted elements is reclaimed automatically. table() returns NULL if it cannot obtain (from malloc()) the space it needs - 2*sizeof(char *)*size bytes, plus a small fixed overhead. Tables are implemented using a hashing technique. Accesses will be fast as long as the table does not become too full; however, performance will degrade rapidly if the table fills. A good rule of thumb is to allow space for 10% more elements than you will actually need to store. tdelete(t,key) deletes key and its associated value from t. If all goes well, 0 is returned; if key was not in t, 1 is returned and t is unaltered. Note that only the space that tinsert() allocated - for the key - is freed automatically; you must free any space used by the value associated with key. tinsert(t,key,value) inserts value as the value associated with key in table t. If all went well, tinsert() returns 0. If the table is full, or no space could be allocated to copy the key, tinsert() returns -1. If key is already in t, tinsert() returns 1; the value currently associated with key is not changed. tlookup(t,key) returns the value associated with key in t or NULL if key isn't found. .tp 9 tnext() is used to scan through all elements in a table in sequence. It is used thus: char *key; int value; for (n = -1; (n = tnext(t, n, &key, &value)) >= 0;) { /* process pair (key, value) */ } Unpredictable results will occur if you insert new elements into a table (with tinsert()) while scanning it. The other table functions may be called with no problems. CAUTION: The string pointed to by key as returned is the only copy available in the table. Treat it as read-only! tupdate(t,key,value) changes the value associated with key to value. tupdate() returns 0 if all went well, 1 if key was not found in t. In the latter case, t is unaltered. internal $$locate(t,key) locates key in table t. It returns the address of an entry in the table. That entry may be EMPTY or DELETED, in which case the caller may store key into it. If NULL is returned, the entry wasn't found and no free entry could be found either. bugs author Jerry Leichter #endif /* *)EDITLEVEL=30 * Edit history * 0.0 21-May-81 JSL Invention * 0.1 22-May-81 JSL Use signed arithmetic for speed; bug fixed; add tnext. * 1.0 28-May-81 JSL Bugs arising from oddball unsigned conversions finally * fixed; clean up user interface; add documentation. * 1.1 23-Jun-81 JSL Improve (and fix) documentation; declare malloc(). * 1.2 13-Jul-82 JSL Removed extra argument from tdelete(). */ #define NULL 0 #define TOOBIG 8192 /* Table size limit */ /* Define TOOBIG so that TOOBIG * sizeof(PAIR) just overflows an int */ #define EMPTY 0 /* Empty table entry key value */ #define DELETED 1 /* Deleted table entry value */ /* * EMPTY and DELETED must be two different values each distinct from any * possible string address. * */ #define LIMIT 5 /* "Random probe" limit */ extern char *malloc(); extern char *savestr(); typedef struct /* One table entry */ { char *key; int value; } PAIR; typedef struct { int tsize; PAIR tdata[]; } TABLE; TABLE * /* Create a new table */ table(size) register int size; { register TABLE *t; register int i; if ( size < 0 || size >= TOOBIG || (t = malloc(size*sizeof(PAIR)+sizeof(int))) == NULL ) return(NULL); t->tsize = size; for (i = 0; i < size; i++) t->tdata[i].key = EMPTY; return(t); } PAIR * $$locate(t,key) TABLE *t; char *key; { register int bigh, i; register char *p; int h, size; char *free; long temp; bigh = 0; for (p = key; *p; ) bigh = 253*bigh + *p++; free = NULL; size = t->tsize; for (i = 0; i < LIMIT; i++) /* Random probes */ { bigh = 251 * bigh + 1233; temp = (unsigned)bigh; /* Avoid compiler bug... */ h = (temp * size) >> 16; #ifdef DEBUG printf("Probe %d: bigh = %d[%u], h = %d[%u], size = %d, \ temp = %ld\n",i,bigh,bigh,h,h,size,temp); #endif p = t->tdata[h].key; if (free == NULL && (p == EMPTY || p == DELETED)) free = &t->tdata[h]; if (p == EMPTY) return(free); if (p != DELETED && streq(p,key)) return(&t->tdata[h]); } #ifdef DEBUG printf("Random probes failed...\n"); #endif for (h = 0; h < size; h++) /* Exhaustive search */ { p = t->tdata[h].key; if (free == NULL && (p == EMPTY || p == DELETED)) free = &t->tdata[h]; if (p == EMPTY) return(free); if (p != DELETED && streq(p,key)) return(&t->tdata[h]); } return(free); } tdelete(t,key) TABLE *t; char *key; { register PAIR *p; p = $$locate(t,key); if (p == NULL || p->key == EMPTY || p->key == DELETED) return(1); free(p->key); p->key = DELETED; return(0); } tinsert(t,key,value) TABLE *t; char *key; int value; { register PAIR *p; p = $$locate(t,key); if (p == NULL) /* Table overflow */ return(-1); if (p->key != EMPTY && p->key != DELETED) /* It's there */ return(1); if ((p->key = savestr(key)) == NULL) /* No core */ return(-1); p->value = value; return(0); } tlookup(t,key) TABLE *t; char *key; { register PAIR *p; p = $$locate(t,key); if (p == NULL || p->key == EMPTY || p->key == DELETED) return(0); return(p->value); } tnext(t,n,key,value) TABLE *t; int n; char **key; int *value; { register int i, size; register PAIR *p; if ( n < 0 ) n = -1; size = t->tsize; for (i = n + 1; i < size; i++) if ((p = t->tdata[i].key) != EMPTY && p != DELETED) { *key = p; *value = t->tdata[i].value; return(i); } return(-1); } tupdate(t,key,value) TABLE *t; char *key; int value; { register PAIR *p; p = $$locate(t,key); if (p == NULL || p->key == EMPTY || p->key == DELETED) return(1); p->value = value; return(0); }