/************************************************************************
 * 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.						*
 ************************************************************************/
/*+++*
 *  title:	maps.c
 *  abstract:	keymap handling routines.
 *  author:	T.R.Hageman, Groningen, The Netherlands.
 *  created:	june 1990
 *  modified:	04-Jul-92
 *  description:
 *---*/

#include "tune.h"	/* to allow definition of debug flags there. */

#ifdef DEBUG		/* General debug flag, turn on file-specific flag. */
#   ifndef MAPS_DEBUG
#	define MAPS_DEBUG	1
#   endif
#else
#   if MAPS_DEBUG	/* File-specific debug flag, turn on general flag. */
#	define DEBUG
#   endif
#endif

#include "jove.h"

RCS("$Id: maps.c,v 14.31.0.12 1994/06/23 02:46:25 tom Exp tom $")

#include "ctype.h"
#define Extern
#include "maps.h"

#undef DEF_MAP

#ifndef FIXED_MAPS
#   define DEF_MAP(name,binds,n)	{ DEFMAP(name, binds, n), \
					  &Maps[((n)&~SPARSE)-1] }
#else
#   define DEF_MAP(name,binds,n)	{ DEFMAP(NULL, binds, n) }
#endif

#define DEFMAP(name,binds,n)		FROZEN|KEYMAP|((n)&SPARSE), name, binds

/* The builtin keymaps are defined by the array `Maps'.
   For backward compatibility's sake, the prefix maps are also entered into
   the commands table, tagged with FUNCTION|PREFIX|ARG(n), and the `c_proc'
   field pointing to the correspondent entry in `Maps'.  If FIXED_MAPS is
   defined,  the only way for the user to get to the keymaps is through
   the commands table.  The builtin sparsemaps are associated in a similar
   fashion with their commands, that is, the corresponding command is tagged
   with SPARSE|ARG(____MAP_INDEX). */

public Keymap Maps[] = {
    { DEFMAP( "mainmap", mainmap, 0 ) },
DEF_MAP( "prefix-1", pref1map, 1 ),
DEF_MAP( "prefix-2", pref2map, 2 ),
DEF_MAP( "prefix-3", miscmap, 3 )
#ifndef FIXED_MAPS
, DEF_MAP( "window-find-map", (data_obj **) WFindMap, WINDFINDMAP_INDEX | SPARSE )
, DEF_MAP( "help-map", (data_obj **) HelpMap, HELPMAP_INDEX | SPARSE )
#endif
};

#define MAINMAP	(&Maps[0])

#ifndef FIXED_MAPS

/* Sparsemap speed optimization: first entry of sparsemap array can point
   to a bit vector that caches the key bindings in the sparsemap. */

#   define MAPSET_MAGIC		0x1B1D	/* Impossible keystroke. */
#   define MAPSET_OP(smap,OP,c)	(((sparsemap*)(smap))->s_chr != MAPSET_MAGIC ||\
				 BITSET_OP(((sparsemap*)(smap))->s_cmd,OP,(c)))

private data_obj **bind_sparse __(( Keymap *_(map), int _(c), int _(options) ));
private void	Active __(( void ));

/* `keymaps' is the head of the list of all existing keymaps.
   `activemap' is the head of the list of currently active (top-level) keymaps.
   `activebuf' is the buffer for which the active list was last calculated.
   This is remembered so that the active list can be updated lazily, that is,
   only when it is needed. */

public Keymap	*keymaps = &Maps[sizeof Maps / sizeof Maps[0] - 1],
		*activemap = MAINMAP;

private Buffer	*activebuf ZERO;

/*
 * Return the up-to-date active keymap.
 */
public Keymap *
active_map()
{
	if (curbuf != activebuf)
		Active();
	return activemap;
}

/*
 * create a keymap and link it in the list.
 * It is assumed it does not already exist.
 */
private Keymap *map_create __(( const char *_(name), int _(size) ));
private Keymap *
map_create(name, size)
const char	*name;
int		size;
{
#define FULL_MAPSIZE	(sizeof(data_obj *) * MAPSIZE)

	register Keymap	*map;
	register size_t	total_size = sizeof(Keymap) + FULL_MAPSIZE;
	register int	Type = KEYMAP;

	/* Only use sparse map if requested and it gains memory. */
	if (size > 1 &&
	    size < (FULL_MAPSIZE - BITSET_SIZE(MAPSIZE))/sizeof(sparsemap) -1) {
		total_size = (sizeof(Keymap) + BITSET_SIZE(MAPSIZE) +
			      sizeof(sparsemap) /*sentinel*/ +
			      sizeof(sparsemap) * size);
		Type |= SPARSE;
	}
	map = emalloc(total_size);
	bzero(map, total_size);

	if (Type & SPARSE) {
		register sparsemap	*sp = (sparsemap *) &map[1];

		sp[size].s_chr = -1;		/* set sentinel. */
		sp[0].s_chr = MAPSET_MAGIC;	/* set index cache. */
		sp[0].s_cmd = (data_obj *) &sp[size + 1];
	}
	map->Type = Type;
	map->Name = name;
	map->k_bind = (data_obj **) &map[1];
	map->k_next = keymaps;
	keymaps = map;

	return map;
}

#ifdef IPROCS
private Keymap *proc_map __(( void ));
private Keymap *
proc_map()
{
	static Keymap	*procmap ZERO;

	if (procmap == NULL)
		(procmap = map_create("process-map", 20))->Type |= FROZEN;
		/* so you can't delete it... */

	return procmap;
}
#endif /* IPROCS */


private data_obj *findmap __(( const char *_(prompt) ));
private data_obj *
findmap(prompt)
const char	*prompt;
{
	const char	*names[400];	/* should be enough... */
	register Keymap	*map;

	/* build name vector */
    {
	register const char	**strs = names;

	map = keymaps;
	do  *strs++ = map->Name;  while (map = map->k_next);
	*strs = NULL;
    }
    {
	register int		i = NOTHING;
	register const char	*p;

	if ((p = prompt) == NULL) {		/* [TRH] this is a kludge */
		p = ProcFmt;
		i = RET_STATE;
	}
	if ((i = complete(names, i, p)) < 0) {
		if (i == ORIGINAL || i == AMBIGUOUS)
			return NULL;
		complain(NullStr);
	}
	for (map = keymaps; --i >= 0; map = map->k_next) ;

    }
	return (data_obj *) map;
}

/* determine the active keymaps; MAINMAP is always at the end of the list */

private void	Active_1 __(( Keymap *_(map) ));

private void
Active()
{
	register Buffer *cb = curbuf;
	register Keymap	*map,
			*prev = MAINMAP;

	activebuf = cb;

	/* Start with a clean slate. */
	map = keymaps;
	do {
		map->k_active = NULL;
	} while (K_NEXT(map));

#ifdef IPROCS
	if (cb->b_process) {
		map = proc_map(),
		map->k_active = prev,
		prev = map;
	}
#endif
	if ((map = cb->b_keymap) && map != prev) {
		map->k_active = prev,
		prev = map;
	}
	activemap = prev;

	if (prev->k_active) {	/* Scan Active maps for hidden Prefix maps. */
		map_init_visit();
		Active_1(prev);
	}
}

/*
 * Recursively find prefixes that cover others in the active list,
 * and chain these into their own active-list.
 */
private void	Active_2 __(( Keymap *_(map), int _(c), Keymap *_(prefix) ));

private void
Active_1(map)
register Keymap	*map;
{
	char	found[MAPSIZE];

	if (map->k_active == NULL)
		return;

	bzero(found, sizeof found);

	do {
		/* Fast scan through the keymaps. */
		if (map->Type & SPARSE) {
			register sparsemap	*sp = (sparsemap *) map->k_bind;
			register int		c = sp->s_chr;

			do {
				register data_obj	*dp;
				register Keymap		*prefix;

				if (c == MAPSET_MAGIC)
					continue;
				if ((dp = sp->s_cmd) == NULL)
					continue;
				if (found[c])
					continue;
				if (!isfunckey(c) && found[tolower(c)]++)
					continue;
				found[c]++;
				if ((prefix = IsPrefix(dp)) == NULL)
					continue;

				Active_2(map, c, prefix);

			} while ((c = (++sp)->s_chr) >= 0);
		}
		else {
			register int	c = 0;

			do {
				register data_obj	*dp;
				register Keymap		*prefix;

				if ((dp = map->k_bind[c]) == NULL)
					continue;
				if (found[c]++)
					continue;
				if ((prefix = IsPrefix(dp)) == NULL)
					continue;

				Active_2(map, c, prefix);

			} while (++c < MAPSIZE);
		}

	} while (K_ACTIVE_NEXT(map)->k_active);
}

private void
Active_2(map, c, prefix)
register Keymap		*map;
int			c;
Keymap			*prefix;
{
	register Keymap	*head = prefix;

	if (head->Type & VISITED)
		return;

	head->Type |= VISITED;

	while (K_ACTIVE_NEXT(map)) {
		register data_obj	*dp;
		register Keymap		*next;

		if ((dp = get_shallow_bind(map, c)) == NULL)
			continue;

		if ((next = IsPrefix(dp)) == NULL)
			break;

		if (next == head)
			continue;

		head->k_active = next;

		/* Check for loops; break the loop if necessary. */
		do {
			if (next->k_active == head)
				next->k_active = NULL;
		} while (next = next->k_active);

		head = head->k_active;

		/* No point in continuing if we've already followed the
		   chain in the past. */

		if (head->Type & VISITED)
			break;

		head->Type |= VISITED;
	}

	/* and finally recurse into `prefix' to see if it contains keymaps. */
	Active_1(prefix);
}

/*===== Create your own keymap. ==============================================*/

DEF_CMD( "make-keymap", NonExisting, NO ); _IF(def FIXED_MAPS)
DEF_CMD( "make-keymap", MakeMap, NO ) _IF(ndef FIXED_MAPS)
{
	register Keymap	*map;

	if (map = (Keymap *) findmap((char *) 0))
		s_mess("%N: %f %s [already exists]", map->Name);
	else
		map_create(copystr(Minibuf), exp);
}

/*===== Delete a keymap. =====================================================*/

DEF_CMD( "delete-keymap", DelMap, NO ) _IF(ndef FIXED_MAPS)
{
	register Keymap	*map = (Keymap *) findmap(ProcFmt),
			**hp;
	register Buffer *b;

	/* Don't allow builtin maps to be deleted. */
	if (map->Type & FROZEN)
		complain("%N: %f %s [not that one!]", map->Name);

	/* unlink this one from the keymap list */
	for (hp = &keymaps; (*hp) != map; hp = &(*hp)->k_next)
		if (*hp == NULL)
			complain("?keymap?");
	(*hp) = map->k_next;

	/* now, delete any references to this keymap */
	DelBind((data_obj *) map);

	if (b = world) do {
		if (b->b_keymap == map)
			b->b_keymap = NULL;
	} while (b = b->b_next);

	/* Now, delete the map itself. */
	free((void_*) map->Name);
	free((void_*) map);

	Active();	/* ... may have been changed */
}

/*===== Bind (or unbind) a keymap to curbuf. =================================*/

DEF_CMD( "bind-keymap-to-buffer", BindBuf, NO ) _IF(ndef FIXED_MAPS)
{
	register Keymap	*map = (Keymap *) findmap(ProcFmt);

	if (map == MAINMAP)
		map = NULL;
	else if (map->Type & FROZEN)
		complain("%N: %f %s [not that one!]", map->Name);
	curbuf->b_keymap = map;
	Active();
}
#endif /* !FIXED_MAPS */

public data_obj * (*const Find[])__((const char *_(prompt))) = {
	findcom,		/* FUNCTION */
	findvar,		/* VARIABLE */
	findmac,		/* MACRO */
#ifndef FIXED_MAPS
	findmap,		/* KEYMAP */
#endif
};

#define MAP(pp)	((Keymap *)(void_*)(pp))
		/* {{Silly ^^^^^^^^ cast needed for crufty MSC compiler.}} */
#define FUN(cp)	(((Command *)(cp))->c_proc)

public Keymap *
IsPrefix(dp)
const data_obj	*dp;
{
	register Keymap	*kp;

	if (kp = (Keymap *) dp) {
		switch (kp->Type & (TYPEMASK|SPARSE)) {
#ifndef FIXED_MAPS
		case FUNCTION|SPARSE:
			/* This is to make commands that use a sparsemap
			   like "window-find" `transparent' with respect to
			   key (un)binding and -listing.  (The command is
			   still executed as a command since ExecCmd()
			   resolves keymaps slightly differently than this
			   routine.)  These commands should also have the
			   index (in Maps[]) of the corresponding sparsemap
			   ARG()ed in. */

			kp = &Maps[ObjArg(kp)];
			break;

		case KEYMAP|SPARSE:
			break;

		case KEYMAP:
			break;
#endif
		case FUNCTION|PREFIX:
			kp = MAP(FUN(kp));
			break;

		default:
			kp = NULL;
		}
	}
	return kp;
}

/*
 * Setup keymaps for recursive visitation.
 */
void
map_init_visit()
{
	register Keymap	*map;

	/* first un-visit all keymaps... */
	map = keymaps;
	do
		map->Type &= ~VISITED;
	while (K_NEXT(map));

	/* then visit active keymaps */
	map = active_map();
	do
		map->Type |= VISITED;
	while (K_ACTIVE_NEXT(map));
}

/* Walk through the keymaps to find the location of the binding
   corresponding to the key sequence. The walk starts at `initial_map' and
   continues until the key sequence has been recognized, unless `dp' is
   NULL and the sequence stops early. (this allows you to unbind keymaps).
 */

DEF_REF( "quoted-insert", QuoteCmd );

public data_obj **
#ifndef FIXED_MAPS
bind_key(initial_map, options)
Keymap	*initial_map;
#else
bind_key(options)
#   define initial_map	MAINMAP
#endif
int	options;
{
	register Keymap		*map = initial_map;
	register data_obj	**this_bind;
	register int		c,
				prev_c = EOF;
#ifndef TINY
	/* to keep key display correct if keymap completion is not enforced. */
	register char		*end_prompt = mesgbuf;
#endif

	for (;;) {
#ifndef TINY
		if (!InJoverc && (options & MAP_ALLOW_PREFIX)) {
			end_prompt += strlen(end_prompt);
		}
#endif
		c = addgetc();

		if (options & MAP_ALLOW_PREFIX) {
			if (prev_c != QuoteChar) {
#ifndef TINY
				register char	savec = *end_prompt;
				*end_prompt = '\0';
#endif
				if (c == CR || c == LF || c < 0) {
					if (prev_c >= 0)
						break;
				}
				/* allows unbinding of "prefix {C-J,C-M,C-Q}" */
				if (mainmap[c] == QuoteCmd) {
					prev_c = QuoteChar;
					continue;
				}
				if (c == AbortChar)
					complain("[aborted]");
#ifndef TINY
				*end_prompt = savec;
#endif
			}
		}
		if ((unsigned) c >= MAPSIZE)	/* includes (c < 0) */
			complain((c >= 0) ? (char *) 0 :
				 (prev_c < 0) ? "[Empty key sequence]" :
				 "[Premature end of key sequence]");
		prev_c = c;
		/*
		 * if unbinding, walk the active list while the entry is unused
		 */
		do {
#ifndef FIXED_MAPS
			if (map->Type & SPARSE)
				this_bind = bind_sparse(map, c, options);
			else
#endif
				this_bind = &map->k_bind[c];
		} while (K_ACTIVE_NEXT(map) && *this_bind == NULL &&
			 (options & MAP_FOLLOW_ACTIVE_LIST));

		if ((map = IsPrefix(
#ifndef FIXED_MAPS	/* if we didn't follow active list before, do so now. */
				    (*this_bind == NULL && map) ?
				    get_bind(map, c) :
#endif
				    *this_bind)) == NULL)
			break;
	}
#ifdef MENUS
	if (options & (MAP_BIND|MAP_UNBIND))
		Bindchange++;
#endif
	return this_bind;
}

/*===== Unbind a key sequence. ===============================================*/

DEF_CMD( "unbind-key", UnbindC, NO )
{
#define UNBIND_OPTIONS	MAP_ALLOW_PREFIX|MAP_FOLLOW_ACTIVE_LIST|MAP_UNBIND
#ifdef FIXED_MAPS
#	define map	MAINMAP
#	define options	UNBIND_OPTIONS
#else /* !FIXED_MAPS */
	register Keymap	*map = active_map();
	register int	options = UNBIND_OPTIONS;

	if (exp_p) {
		if (exp <= 0)
			map = MAINMAP;
		else
			map = (Keymap *) findmap(": %f, in keymap: ");
		options &= ~MAP_FOLLOW_ACTIVE_LIST;
	}
#endif /* FIXED_MAPS */
	s_mess(ProcFmt);
	*MapKey(map, options) = NULL;

#undef map
#undef options
#undef UNBIND_OPTIONS
}

/*===== Bind (or unbind) something. ==========================================*/

DEF_CMD( "bind-to-key", Bind, ARG(FUNCTION) );
DEF_CMD( "bind-keymap-to-key", Bind, ARG(KEYMAP) ); _IF(ndef FIXED_MAPS)
DEF_CMD( "bind-macro-to-key", Bind, ARG(MACRO) );
DEF_CMD( "bind-variable-to-key", Bind, ARG(VARIABLE) );
DEF_CMD( "process-bind-to-key", Bind, ARG(PMAP|FUNCTION) ); _IF(ndef FIXED_MAPS)_IF(def IPROCS)
DEF_CMD( "process-bind-macro-to-key", Bind, ARG(PMAP|MACRO) ) _IF(ndef FIXED_MAPS)_IF(def IPROCS)
{
	register data_obj	*dp = NULL;
#ifdef FIXED_MAPS
#	define kind	ObjArg(LastCmd)
#	define map	MAINMAP
#else /* !FIXED_MAPS */
	register int	kind = ObjArg(LastCmd);
	register Keymap	*map = active_map();

#   ifdef IPROCS
	if (kind & PMAP) {
		map = proc_map();
		kind &= ~PMAP;
	}
	else
#   endif /* IPROCS */
	if (exp_p) {
		if (exp <= 0)
			map = MAINMAP;
		else
			map = (Keymap *) findmap(": %f, in keymap: ");
	}
#endif /* FIXED_MAPS */

	dp = FindObj(kind, ProcFmt);
	s_mess(ProcArgFmt, dp->Name);
	*MapKey(map, MAP_BIND) = dp;
#undef map
#undef kind
#ifndef FIXED_MAPS
	if (IsPrefix(dp))	/* This may have an effect on active keymaps. */
		Active();
#endif
}

/* Delete all bindings of `dp' from the keymaps */

public void
DelBind(dp)
const data_obj	*dp;
{
	register Keymap		*map = keymaps;

	do {	/* keymaps list is guaranteed to be non-empty */
#ifndef FIXED_MAPS
		if (map->Type & SPARSE) {
			register sparsemap	*sp = (sparsemap *) map->k_bind;

			do {
				if (sp->s_cmd == dp) {
					MAPSET_OP(map->k_bind, &= ~, sp->s_chr);
					sp->s_cmd = NULL;
				}
			} while ((++sp)->s_chr >= 0);
		}
		else
#endif
		{
			register data_obj	**mp = map->k_bind,
						**ep = mp + MAPSIZE;
			do {
				if (*mp == dp)
					*mp = NULL;
			} while (++mp != ep);
		}
	} while (K_NEXT(map));
}

/*===== Execute a command (macro, variable, whatever...) =====================*/

int		Interactive ZERO;
const char	ProcFmt[] = "%N: %f ",
		ProcDefFmt[] = "%N: %f (default %s) ",
		ProcArgFmt[] = "%N: %f %s ";

public void
ExecCmd(cp)
register const data_obj	*cp;
{
	while (LastCmd = cp) {			/* ordinarily just once */

		register void	(*proc)__(( void )) = FUN(cp);
		register int	Type = cp->Type;

		switch (Type & TYPEMASK) {

		case FUNCTION|EDIT|NEGATE:
			exp = -exp;
			/* fall through. */

		case FUNCTION|EDIT:
			if (MinorMode(View))	/* inline for efficiency. */
				view_mode_check();

			(*proc)();
			break;

		case FUNCTION|NEGATE:
			exp = -exp;
			/* fall through. */

		case FUNCTION:
			(*proc)();
			break;
#ifndef FIXED_MAPS
		case KEYMAP:
			proc = (void (*)__((void))) cp;
			/* fall through. */
#endif
		case FUNCTION|PREFIX:
#			define	c	Type		/* alias! */

			c = waitchar();

			if (c == AbortChar) {
				message("[Aborted]");
				rbell();
				break;
			}
			cp = get_bind(MAP(proc), c);

#			undef	c			/* unalias! */

			continue;

		case MACRO:
			do_macro((Macro *) cp);
			break;

		case FUNCTION|MAJOR_MODE:
			Type >>= 8;
			SetMajor(Type);
			break;

		case FUNCTION|MINOR_MODE:
			Type >>= 8;
			TogMinor(Type);
			break;

		default:
			if ((Type & REALTYPEMASK) != VARIABLE)
				complain("can't execute \"%f\", type 0x%x", Type);
			DoSetVar((Variable *) cp);
			break;
		}
		return;
	}

	/* only get here if cp == NULL, i.e., unbound. */
	s_mess("[%sunbound]", key_strokes());
	rbell();
}

/* Dispatch the command for key `c' */

public void
dispatch(c)
int	c;
{
	register const data_obj	*cp;
	register const Keymap	*map = active_map();

	this_cmd = 0;

	do {
		if (cp = get_shallow_bind(map, c)) {
			ExecCmd(cp);
			return;
		}
	} while (K_ACTIVE_NEXT(map));

	rbell();
	errormsg = NO;
}

#ifndef get_bind
public data_obj *
get_bind(map, c)
register const Keymap	*map;
int	c;
{
	register data_obj *dp;

	do {
		if ((dp = get_shallow_bind(map, c)))
			break;

	} while (K_ACTIVE_NEXT(map));

	return dp;
}
#endif /* !get_bind */

/* Support command: complain if current buffer in View mode. */

void
view_mode_check()
{
	register Buffer *cb = curbuf;

	if (BufMinorMode(cb, View))
		complain("[Can't modify buffer \"%b\" in View mode]", cb);
}

/*=====	Sparsemap handling. ==================================================*/

/*
 * Find a binding for character `c' in sparsemap `smap' (case-insensitive).
#ifndef TINY
 * If `c' equals -1 (== sentinel for `smap->s_chr') just build a prompt message.
#endif
 * {{This should be used only for builtin sparsemaps--and these should not
 *   have an index cache.}}
 */
data_obj *
findsparse(sparse_map, c)
const sparsemap	*sparse_map;
register int	c;
{
	/* search in smap and build message on the fly... */
	register const sparsemap *smap = sparse_map;
	register const char	*fmt;
	static const char	Format[] = ", %p: %s";
#ifndef TINY
	register const char	*theFormat = Format;
#	define Format	theFormat

	if (c < 0) {
		s_mess("%N: %f (");
		Format = ", %p";	/* terse... */
	}
	else
#endif
	{
		mesgbuf[0] = '\0';
		if (!isfunckey(c))
			c = toupper(c);	/* Sparsemaps are case-insensitive. */
	}
	for (fmt = Format + 2; /* empty */; ++smap) {

		if (smap->s_cmd == NULL) {
#ifndef FIXED_MAPS
			if (smap->s_chr >= 0)	/* empty slot */
				continue;
			/* else end of map (sentinel: smap->s_chr == -1) */
#endif
#ifndef TINY
			if (c < 0) {		/* make  prompt */
				add_mess(") ");
				break;
			}
#endif
			add_mess(".");
#ifndef TINY
			/* extended help, in case it won't fit on the message
			   line. Do it AFTER we scanned through the table,
			   so `?' can still be bound to something else if
			   the user so desires. */
			if (c == '?') {
				TOstart("*Help*", TRUE);
				Typeout("Key bindings for \"%f\".");
				Typeout((char *) 0);
				smap = sparse_map;
				do {
#   ifndef FIXED_MAPS
					if (smap->s_cmd == NULL)
						continue;
#   endif
					Typeout("  %-5p %s",
						smap->s_chr, smap->s_cmd->Name);
				} while ((++smap)->s_chr >= 0);
				TOstop();
				mesgbuf[0] = '\0';
			}
#endif
			complain((char *)0);
		}
		if (smap->s_chr == c) {
			mesgbuf[0] = '\0'; /* discard the error message... */
			break;
		}
		add_mess(fmt, smap->s_chr, smap->s_cmd->Name);
		fmt = Format;
	}
	return smap->s_cmd;
}

#ifndef FIXED_MAPS

/* This is similar to findsparse(), but without all the frills. */

public data_obj *
get_sparse_bind(sparse_map, c)
const Keymap	*sparse_map;
register int	c;
{
	register const sparsemap *smap = (sparsemap *) sparse_map->k_bind;

	ASSERT(sparse_map->Type & SPARSE);

	if (!isfunckey(c))
		c = toupper(c);		/* Sparsemaps are case-insensitive. */

	if (!MAPSET_OP(smap, &, c))
		return NULL;

	for (; /* empty */; ++smap) {

		if (smap->s_cmd == NULL) {
			if (smap->s_chr >= 0)	/* empty slot */
				continue;
			/* else end of map (sentinel: smap->s_chr == -1) */
			break;
		}
		if (smap->s_chr == c) {
			break;
		}
	}
	return smap->s_cmd;
}

private data_obj **
bind_sparse(map, c, options)
Keymap		*map;
register int	c;
int		options;
{
	register sparsemap	*smap;
	register sparsemap	*this_bind = NULL;

	ASSERT(map->Type & SPARSE);

	if (!isfunckey(c))
		c = toupper(c);		/* Sparsemaps are case-insensitive. */

	for (smap = (sparsemap *) map->k_bind; /* empty */; smap++) {

		if (smap->s_cmd != NULL) {

			if (smap->s_chr != c)
				continue;

			/* Match! */
			this_bind = smap;

			if (options & MAP_UNBIND) {
				smap = (sparsemap *) map->k_bind;
				MAPSET_OP(smap, &= ~, c);
			}
			break;
		}
		/* else unbound (smap->s_cmd == NULL) */

		if (this_bind == NULL)	/* remember first empty slot. */
			this_bind = smap;

		if (smap->s_chr >= 0)	/* empty slot */
			continue;
		/* else end of map (sentinel: smap->s_chr == -1) */

		/* If we're trying to bind something and the sparsemap is full,
		   expand it by allocating a larger table and copying the old
		   contents. */
		if (!(options & MAP_BIND))
			break;
		if (this_bind == smap) {
#			define SPARSE_EXPAND	8
			register int	size = (char *) smap -
					       (char *) map->k_bind;

			smap = emalloc(size + sizeof(*smap) * (SPARSE_EXPAND+1));
			/* make this_bind point in new table. */
			this_bind = (sparsemap *)((char *) smap + size);
			byte_copy(map->k_bind, smap, size);
			bzero(this_bind, (sizeof(*smap) * (SPARSE_EXPAND+1)));
			this_bind[SPARSE_EXPAND].s_chr = -1;

			/* dispose contents only if we can... */
			if (!ISSTATIC(map->k_bind) &&
			    map->k_bind != (data_obj **)&map[1])
				free((void_*) map->k_bind);

			map->k_bind = (data_obj **) smap;
		}
		this_bind->s_chr = c;
		smap = (sparsemap *) map->k_bind;
		MAPSET_OP(smap, |=, c);
		break;
	}
	return &this_bind->s_cmd;
}
#endif /* FIXED_MAPS */

/*======================================================================
 * $Log: maps.c,v $
 * Revision 14.31.0.12  1994/06/23  02:46:25  tom
 *  (findsparse): fix name of scratch buffer.
 *
 * Revision 14.31.0.11  1994/06/10  13:51:12  tom
 * (view_mode_check): new support function; (ExecCmd): use it.
 *
 * Revision 14.31  1993/02/15  02:01:48  tom
 * allow debug options to be specified in "tune.h" cf. "Local.h".
 *
 * Revision 14.30  1993/02/05  00:07:30  tom
 * cleanup whitespace; some random optimizations; standardize DEBUG options;
 * improve activemap detection: now finds overlapping prefix maps too; add
 * optional bit vector indexed by keystroke to sparsemaps for efficient access;
 * improve integration of sparsemaps with regular keymaps.
 *
 * Revision 14.28  1992/10/24  01:24:21  tom
 * integrate sparsemaps in regular keymap mechanism;
 * convert to "port{ansi,defs}.h" conventions.
 *
 * Revision 14.27  1992/09/22  15:23:11  tom
 * replace CTL('Q') with `QuoteChar'.
 *
 * Revision 14.26  1992/08/26  23:56:56  tom
 * add RCS directives.
 *
 */