diff options
author | Karl Berry <karl@freefriends.org> | 2006-01-17 21:41:51 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2006-01-17 21:41:51 +0000 |
commit | 487ca4806cc046076293cf6cc5fbba0db282bac7 (patch) | |
tree | 847b412ab5158dd7bdd7ed7e5a4cc3fbca94be32 /Build/source/texk/seetexk/search.c | |
parent | a3d3111bfe26b8e5f5bc6049dfb2a4ca2edc7881 (diff) |
texk 1
git-svn-id: svn://tug.org/texlive/trunk@1485 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/seetexk/search.c')
-rw-r--r-- | Build/source/texk/seetexk/search.c | 182 |
1 files changed, 182 insertions, 0 deletions
diff --git a/Build/source/texk/seetexk/search.c b/Build/source/texk/seetexk/search.c new file mode 100644 index 00000000000..0768450787d --- /dev/null +++ b/Build/source/texk/seetexk/search.c @@ -0,0 +1,182 @@ +/* + * Copyright (c) 1987, 1989 University of Maryland + * Department of Computer Science. All rights reserved. + * Permission to copy for any purpose is hereby granted + * so long as this copyright notice remains intact. + */ + +#ifndef lint +static char rcsid[] = "$Header: /usr/src/local/tex/local/mctex/lib/RCS/search.c,v 3.1 89/08/22 21:58:14 chris Exp $"; +#endif + +/* + * 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 "types.h" +#include "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 */ + +#ifndef KPATHSEA +char *malloc(), *realloc(); +#endif + +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); +} + +/* + * 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 BLOCK_COPY + 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 + BLOCK_COPY(keyaddr, keyaddr + s->s_dsize, + 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); +} + +/* + * Call function `f' for each element in the search table `s'. + */ +void +SEnumerate(s, f) + register struct search *s; + register void (*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; + } +} |