/************************************************************************
 * This program is Copyright (C) 1986 by Jonathan Payne.  JOVE is       *
 * provided to you without charge, and with no warranty.  You may give  *
 * away copies of JOVE, including sources, provided that this notice is *
 * included in all the files.                                           *
 ************************************************************************/

#include "jove.h"

#ifdef LISP

RCS("$Id: table.c,v 14.26.0.1 1993/07/07 13:11:12 tom Exp tom $")

#define Extern public
#include "table.h"

private void table_expand __(( Table *_(table) ));

#if 0	/* not needed */
Table *
make_table(cmp)
int	(*cmp)();
{
	register Table	*tab = (Table *) emalloc(sizeof *tab);

	tab->t_wordlist = NULL;
	tab->t_size = tab->t_max = 0;
	tab->t_cmp = cmp;

	return tab;
}
#endif

char *
table_lookup(table, word, ins)
register Table	*table;
const char	*word;
int		ins;
{
	register const char **tp;
	register int	top = 0,
			med = 0,
			end = table->t_size,
			key = 0;

	while (top < end) {	/* binary search */
		tp = &table->t_wordlist[med = (top + end) >> 1];
		if ((key = (*table->t_cmp)(word, *tp, strlen(*tp))) < 0)
			end = med;
		else if (key > 0)
			top = med + 1;
		else
			return (char *) *tp;
	}
	/* not found; insert it, if so requested. */
	if (ins) {
		register const char	**base;

		if (table->t_size >= table->t_max)
			table_expand(table);
		if (key > 0)
			med++;
		table->t_size++;
		/* shift tail */
		for (tp = &table->t_wordlist[table->t_size],
		     base = &table->t_wordlist[med]; tp > base; tp--) {
			tp[0] = tp[-1];
		}
		*tp = copystr(word);
	}
	return NULL;
}

private void
table_expand(table)
register Table	*table;
{
	register const char	**src = table->t_wordlist,
				**dest;
	register int	n = table->t_size,
			newsize = n + 16;

	dest = (const char **) emalloc(newsize * sizeof(char **));
	if (src) {
		while (--n >= 0) {
			*dest++ = *src++;
		}
	}
	if (table->t_max)
		free(src);
	table->t_max = newsize;
}

#endif /* LISP */

/*======================================================================
 * $Log: table.c,v $
 * Revision 14.26.0.1  1993/07/07  13:11:12  tom
 * fix const botches to avoid warnings.
 *
 * Revision 14.26  1992/08/26  23:56:58  tom
 * add RCS directives.
 *
 */