/*
 * Copyright (c) 1987 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: search.c,v 2.3 87/06/16 18:28:58 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 */

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);
}

/*
 * 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);
}

/*
 * Call function `f' for each element in the search table `s'.
 */
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;
	}
}