Category : C Source Code
Archive   : CSRC2.ZIP
Filename : TABLES.C

 
Output of file : TABLES.C contained in archive : CSRC2.ZIP
/*
* 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);
}


  3 Responses to “Category : C Source Code
Archive   : CSRC2.ZIP
Filename : TABLES.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/