/*+++*
 *  title:	_tcpfind.c
 *  abstract:	find a termcap capability
 *  author:	T.R.Hageman, Groningen, The Netherlands.
 *  created:	march 1990
 *  modified:	16-Jun-90, fixed typo in SLOWCAP/HASHED code
 *		24-Jun-92, make FASTCAP table grow downward when compiling.
 *  description:
 *
#if FASTCAP
 *	Do a binary search for the capability in the capabilities-table.
 *	If there is a match, return a NULL pointer if we are compiling
 *	and a pointer to the VALUE of the matching entry if we are not.
 *	If there is no match, insert the new entry in the table and return
 *	a pointer to the ENTRY (cast to char *) if we are compiling, or a NULL
 *	pointer if we are not. 
 *	 The routine does not make any assumptions on the maximum allowed size
 *	of the table when a new entry is inserted; it faithfully assumes
 *	that this is checked before.
 *	Also note that the table grows DOWNward when compiling.
#else
 *	Scan the termcap entry string for a capability name.
#endif
 *---*/

#include "_termcap.h"

#ifdef RCS_ID
static const char rcsid[] =
	"$Id: _tcpfind.c,v 1.4 1993/08/19 23:15:40 tom Exp tom $";
#endif

#if !FASTCAP
#   ifdef HASHED
	/* a very simplistic hash function indeed */

#	define HASHSIZE	32	/* power of 2! */
#	define HASH(id)	((unsigned)(((id)[0]) + ((id)[1])) & (HASHSIZE-1))

	static char *	hashtable[HASHSIZE];
#   endif
#endif

char *
_tcpfind(cap)
const char	*cap;
{
#if FASTCAP

#	define MAKEKEY(key,cap) {register const char*t=cap; key=(t[0]<<8)|t[1];}

	register t_entry *p;
	int		key;

	DPRINTF(("%.2s ", cap));

	MAKEKEY(key, cap);
    {
	register int	top = 0,
			end = _tcptable.t_size,
			med;
	/*
	 * Store capabilities in reverse lexical order, so that copying
	 * is minimized for termcap entries in normal lexical order.
	 * (since we grow downward)
	 */
	while (top < end) {
		p = &_tcptable.t_body[med = (top + end) >> 1];
		if (key > p->t_cap)
			end = med;
		else if (key < p->t_cap)
			top = med + 1;
		else {
			DPRINTF(("found @%d\n", med));
			return (_tcptable.t_compiling) ? NULL : _TCP_VAL(p);
		}
	}
    }
	DPRINTF(("not found"));

	if (!_tcptable.t_compiling) {
		DPRINTF(("\n"));
		return NULL;
	}

	/* if we get here, we are compiling and should insert the entry. */
    {
#    ifndef COPY_T
#	define COPY_T	short
	/*
	 * This assumes the table is aligned on a short boundary, and
	 * sizeof(t_entry) is an integer multiple of sizeof(short).
	 * (which is the case when not a pointer implementation,
	 *  or (sizeof(char *) % sizeof(short)) == 0)
	 * Other reasonable choices are: char, int, or t_entry.
	 */
#    endif
	/*
	 * Make room for a single new entry; shift everything before the 
	 * insertion point one position downward and adjust the base pointer.
	 */

	register COPY_T	*s = (COPY_T *) _tcptable.t_body,
			*d = (COPY_T *) ((t_entry *) s - 1);

	_tcptable.t_body = (t_entry *) d;

	if (_tcptable.t_size == 0) {
		p = (t_entry *) d;
	}
	else {
		if (key > p->t_cap)
			--p;

		while (d < (COPY_T *) p)
			*d++ = *s++;
	}
    }
	_tcptable.t_size++;
	p->t_cap = key;

	DPRINTF(("-- insert @%d\n", (int)(p - _tcptable.t_body)));
	return (char *) p;

#else /* ! FASTCAP */

	register char		*s;
	register const char	*cp = cap;

#   ifdef HASHED
	if (s = hashtable[HASH(s)]) {
		while (!(*s++ == cp[0] && *s++ == cp[1])) {
			--s;
			do {
				if (*s == '\0')
					return NULL;
			} while (*s++ != ':');
		}
	}
	return s;

#   else /* ! HASHED */

	if (s = _tcpbuf) {
		while (*s) {
			if (*s++ == ':') {
				if (*s++ == cp[0] && *s++ == cp[1]) {
					return (s);
				}
				--s;
			}
		}
	}
	return NULL;

#   endif /* HASHED */

#endif /* FASTCAP */
}


#if !FASTCAP
#   ifdef HASHED

void
_tcphash()
{
    {
	register char	*s = _tcpbuf;
	register char	c;
	register char	**hp;

	for (hp = hashtable;  hp < &hashtable[HASHSIZE]; )
		*hp++ = NULL;

	while (c = *s++) {
		if (c == '\\')
			if (*s++)
				continue;
			else
				break;
		if (c != ':')
			continue;
		if ((c = *s) <= ' ' || c == ':' || c >= 0177)
			continue;

		hp = &hashtable[HASH(s)];
		if (*hp == NULL)
			*hp = s;
	}
    }
#	ifdef DEBUG
    {
	register int	n = 0,
			i;

	register char	*p;

	for (i = 0; i < HASHSIZE; i++)
		if (s = hashtable[i]) {
			n++;
			printf("hash %3d\t%.2s[%d]",
				i, s, (int)(s - _tcpbuf));
			while (*s) {
				if (*s++ != ':')
					continue;
				if (*s <= ' ' || *s == ':' || *s >= 0177)
					continue;
				if (HASH(s) != i)
					continue;
				printf("\t%.2s[%d]", s, (int)(s - _tcpbuf));
			}
			printf("\n");
		}
	printf("---- occupied: %d of %d\n\n", n, HASHSIZE);
    }
#	endif /* DEBUG */
}
#   endif /* HASHED */
#endif /* !FASTCAP */

/*======================================================================*
 * $Log: _tcpfind.c,v $
 * Revision 1.4  1993/08/19  23:15:40  tom
 * comment fix; fix typo in RCS Log.
 *
 *======================================================================*/