chris@umcp-cs.UUCP (Chris Torek) (09/12/85)
# The following is some almost-generic table storage and lookup code.
# It operates off 32-bit keys, which is where it departs from being
# generic, but could be easily modified for other uses.
#
# The documentation consists of the following extract from ../lib/README:
# ---------------------------------------------------------------
# struct search *SCreate(dsize)
# unsigned dsize;
#
# Creates a search table; keys are i32 integers, data objects are of
# size dsize and of unspecified type. A null pointer is returned if
# the table cannot be created.
#
# SEnumerate(table, func)
# struct search *table;
# int (*func)();
#
# Invokes the given function on each object in the table. The function
# is handed a "char *" pointer to the objects as its first argument
# and the i32 key as its second. (The return value from (*func)(),
# if any, is ignored; technically it should be void (*func)(), but
# that is not implemented quite right in many Unix compilers...)
#
# char *SSearch(table, key, disp)
# struct search *table;
# i32 key;
# int *disp;
#
# Searches for a given key within the given search table. A number
# of dispositions can be specified; see ../h/search.h for the flags
# that can be specified in *disp. *disp is modified before return
# to set the reason for the search success or failure. The return
# value is a pointer to the user data area for the given key if found,
# otherwise NULL.
#
# WARNING: data areas may move on future searches that create new
# data objects.
# ---------------------------------------------------------------
# You will probably have to fiddle with the file names somewhat, as
# I am using this code in a large project where lots of directories
# are helpful. Also note that ``types.h'' is machine dependent.
#
# For those of you who are stuck with System V, bcopy and memcpy have
# identical semantics (only the order of arguments is different);
# bzero can be accomplished with memset (set all bytes to '\0').
# bcopy takes (from, to, count), and bzero takes (from, count);
# see your manual for the arguments for memcpy and memset.
#
# Chris
#
: Run this shell script with "sh" not "csh"
PATH=:/bin:/usr/bin:/usr/ucb
export PATH
all=FALSE
if [ x$1 = x-a ]; then
all=TRUE
fi
/bin/echo 'Extracting search.c'
sed 's/^X//' <<'//go.sysin dd *' >search.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/ctex/lib/RCS/search.c,v 1.2 85/09/11 18:31:19 chris Exp $";
#endif
X/*
* Key search routines (for a 32 bit key)
*
* SCreate initializes the search control area.
*
* SSearch returns the address of the data area (if found or created)
* or a null pointer (if not). The last argument controls the disposition
* in various cases, and is a ``value-result'' parameter.
*
* SEnumerate calls the given function on each data object within the
* search table. Note that no ordering is specified (though currently
* it runs in increasing-key-value sequence).
*/
#include "../h/types.h"
#include "../h/search.h"
#if vax || mc68000 || ns32000 || pyr
#define HARD_ALIGNMENT 4
#else
#define HARD_ALIGNMENT 16 /* should suffice for most everyone */
#endif
static int DOffset; /* part of alignment code */
char *malloc(), *realloc();
struct search *
SCreate (dsize)
register unsigned int dsize;
{
register struct search *s;
if ((s = (struct search *) malloc (sizeof *s)) == 0)
return 0;
if (DOffset == 0) {
#ifndef HARD_ALIGNMENT
DOffset = sizeof (i32);
#else
DOffset = (sizeof (i32) + HARD_ALIGNMENT - 1) & ~(HARD_ALIGNMENT - 1);
#endif
}
dsize += DOffset; /* tack on space for keys */
#ifdef HARD_ALIGNMENT
/* For machines with strict alignment constraints, it may be necessary to
align the data at a multiple of some positive power of two. In general,
it would suffice to make dsize a power of two, but this could be very
space-wasteful, so instead we align it to HARD_ALIGNMENT. 64 bit
machines might ``#define HARD_ALIGNMENT 8'', for example. N.B.: we
assume that HARD_ALIGNMENT is a power of two. */
dsize = (dsize + HARD_ALIGNMENT - 1) & ~(HARD_ALIGNMENT - 1);
#endif
s -> s_dsize = dsize; /* save data object size */
s -> s_space = 10; /* initially, room for 10 objects */
s -> s_n = 0; /* and none in the table */
if ((s -> s_data = malloc (s -> s_space * dsize)) == 0) {
free ((char *) s);
return 0;
}
return s;
}
X/* we actually use a binary search right now - this may change */
char *
SSearch (s, key, disp)
register struct search *s;
register i32 key;
int *disp;
{
register char *keyaddr;
int itemstomove;
*disp &= S_CREATE | S_EXCL; /* clear return codes */
if (s -> s_n) { /* look for the key */
register int h, l, m;
h = s -> s_n - 1;
l = 0;
while (l <= h) {
m = (l + h) >> 1;
keyaddr = s -> s_data + m * s -> s_dsize;
if (*(i32 *) keyaddr > key)
h = m - 1;
else if (*(i32 *) keyaddr < key)
l = m + 1;
else { /* found it, now what? */
if (*disp & S_EXCL) {
*disp |= S_COLL;
return 0; /* collision */
}
*disp |= S_FOUND;
return keyaddr + DOffset;
}
}
keyaddr = s -> s_data + l * s -> s_dsize;
}
else
keyaddr = s -> s_data;
/* keyaddr is now where the key should have been found, if anywhere */
if ((*disp & S_CREATE) == 0)
return 0; /* not found */
/* avoid using realloc so as to retain old data if out of memory */
if (s -> s_space <= 0) { /* must expand; double it */
register char *new;
if ((new = malloc ((s -> s_n << 1) * s -> s_dsize)) == 0) {
*disp |= S_ERROR; /* no space */
return 0;
}
keyaddr = (keyaddr - s -> s_data) + new; /* relocate */
bcopy (s -> s_data, new, s -> s_n * s -> s_dsize);
free (s -> s_data);
s -> s_data = new;
s -> s_space = s -> s_n;
}
/* now move any keyed data that is beyond keyaddr down */
itemstomove = s -> s_n - (keyaddr - s -> s_data) / s -> s_dsize;
if (itemstomove) {
#ifndef USE_BCOPY /* often bcopy doesn't handle overlap */
register char *from, *to;
from = s -> s_data + s -> s_n * s -> s_dsize;
to = from + s -> s_dsize;
while (from > keyaddr)
*--to = *--from;
#else
bcopy (keyaddr + s -> s_dsize, keyaddr + (s -> s_dsize << 1),
itemstomove * s -> s_dsize);
#endif
}
*disp |= S_NEW;
s -> s_n++;
s -> s_space--;
*(i32 *) keyaddr = key;
keyaddr += DOffset; /* now actually dataaddr */
/* the bzero is just a frill... */
bzero (keyaddr, s -> s_dsize - DOffset);
return keyaddr;
}
SEnumerate (s, f)
register struct search *s;
register int (*f) (); {
register int n;
register char *p;
n = s -> s_n;
p = s -> s_data;
while (--n >= 0) {
(*f) (p + DOffset, *(i32 *) p);
p += s -> s_dsize;
}
}
//go.sysin dd *
if [ `wc -c < search.c` != 4404 ]; then
made=FALSE
/bin/echo 'error transmitting "search.c" --'
/bin/echo 'length should be 4404, not' `wc -c < search.c`
else
made=TRUE
fi
if [ $made = TRUE ]; then
/bin/chmod 644 search.c
/bin/echo -n ' '; /bin/ls -ld search.c
fi
/bin/echo 'Extracting search.h'
sed 's/^X//' <<'//go.sysin dd *' >search.h
X/* search structures and routines for 32-bit key, arbitrary data */
struct search {
unsigned s_dsize; /* data object size (includes key size) */
unsigned s_space; /* space left (in terms of objects) */
unsigned s_n; /* number of objects in the table */
char *s_data; /* data area */
};
X/* returns a pointer to the search table (for future search/installs) */
struct search *SCreate (); /* create a search table */
X/* returns a pointer to the data object found or created */
char *SSearch (); /* search for a data object */
X/* the third argument to SSearch controls operation as follows: */
#define S_LOOKUP 0x00 /* pseudo flag */
#define S_CREATE 0x01 /* create object if not found */
#define S_EXCL 0x02 /* complain if already exists */
X/* in addition, it is modified before return to hold status: */
#define S_COLL 0x04 /* collision (occurs iff S_EXCL set) */
#define S_FOUND 0x08 /* found (occurs iff existed already) */
#define S_NEW 0x10 /* created (occurs iff S_CREATE && !S_EXCL) */
#define S_ERROR 0x20 /* problem creating (out of memory) */
//go.sysin dd *
if [ `wc -c < search.h` != 1066 ]; then
made=FALSE
/bin/echo 'error transmitting "search.h" --'
/bin/echo 'length should be 1066, not' `wc -c < search.h`
else
made=TRUE
fi
if [ $made = TRUE ]; then
/bin/chmod 644 search.h
/bin/echo -n ' '; /bin/ls -ld search.h
fi
/bin/echo 'Extracting types.h'
sed 's/^X//' <<'//go.sysin dd *' >types.h
X/* a 32 (or more) bit integer (signed) */
typedef int i32;
X/* macros to sign extend quantities that are less than 32 bits long */
X/* Sun mishandles (int)(char)(constant) */
#ifndef sun
#define Sign8(n) ((int)(char)(n))
#else
#define Sign8(n) (((n) << 24) >> 24)
#endif
#define Sign16(n) ((int)(short)(n))
X/* #define Sign24(n) ((n) & (1<<23) ? ((n)|0xff000000) : (n)) */
#define Sign24(n) (((n) << 8) >> 8)
X/* macros to truncate quantites that are signed but shouldn't be */
#define UnSign8(n) ((n) & 0xff)
#define UnSign16(n) ((n) & 0xffff)
#define UnSign24(n) ((n) & 0xffffff)
X/* note that we never have unsigned 32 bit integers */
//go.sysin dd *
if [ `wc -c < types.h` != 636 ]; then
made=FALSE
/bin/echo 'error transmitting "types.h" --'
/bin/echo 'length should be 636, not' `wc -c < types.h`
else
made=TRUE
fi
if [ $made = TRUE ]; then
/bin/chmod 644 types.h
/bin/echo -n ' '; /bin/ls -ld types.h
fi
exit 0
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 4251)
UUCP: seismo!umcp-cs!chris
CSNet: chris@umcp-cs ARPA: chris@maryland