Merge branch 'arkkra' into shiny

[mup] / mup / mup / symtbl.c

/* Copyright (c) 1995, 1996, 1997, 1998, 2000, 2001, 2002, 2003, 2004, 2005, 2006 by Arkkra Enterprises */
/* All rights reserved */

/* This file contains functions for dealing with symbol tables.
 * There is a symbol table that maps the names of location variables
 * to the addresses of their array of coordinate info,
 * a symbol table to map headshape names to the list of shapes,
 * a table to map time signatures to beamstyle and/or timeunit values,
 * and a symbol table to map grid names to definitions of the grids.
 * Symbol names are hashed for fast lookup.
 */

#include "defines.h"
#include "structs.h"
#include "globals.h"


/* shapes for quarter and shorter, half, whole, double whole */
#define MAX_SHAPE_DURS	(4)
/* UP and DOWN */
#define MAX_STEM_DIRS	(2)

/* First index of headchar and headfont is based on stem direction;
 * also index of ystem_off. */
#define STEMINDEX(stemdir)		( (stemdir) == UP ? 0 : 1 )
/* Second index of headchar and headfont is based on basictime */
#define HCDUR(basictime)	( (basictime) > 2 ? 0 : 3 - (basictime) )
/* First index of Nhead_map */
#define FONTINDEX(font)		(font - FONT_MUSIC)
/* Second index of Nhead_map */
#define CHARINDEX(ch)		(ch - FIRST_CHAR)

struct HDSHAPEINFO {
	/* We give each headshape instance a unique index number,
	 * as a compact way to refer to it. */
	short	index;

	/* This says what notehead characters to use for this shape.
	 * The first dimension is for stem direction, the second for
	 * duration (quarter and shorter, half, whole, double whole).
	 */
	char	headchar[MAX_STEM_DIRS][MAX_SHAPE_DURS];
	/* This array parallels the notehead array, saying which music
	 * font the character is in. */
	char	headfont[MAX_STEM_DIRS][MAX_SHAPE_DURS];
};

/* How many "headshape" entries we allow. This must be small enough to
 * fit in the number of bits allowed for shape indexes in GRPSYL and NOTE.
 * Entry 0 isn't used since we need an "unknown" value.
 */
#define MAX_SHAPE_ENTRIES	(32)

/* These are the predefined headshape entries. Users can define more.
 * We define them here using the same syntax as user would, so we can
 * use the same code to add to our internal table. */
struct SHAPENAMES {
	char *clan_name;	/* name for the set of shapes */
	char *member_names;	/* The names of the 4 shapes in the set */
} Predef_shape_names[] = {
	{ "norm",	"4n 2n 1n dblwhole" },
	{ "x",		"xnote diamond diamond dwhdiamond" },
	{ "allx",	"xnote xnote xnote xnote" },
	{ "diam",	"filldiamond diamond diamond dwhdiamond" },
	{ "blank",	"blankhead blankhead blankhead blankhead" },
	{ "righttri",	"u?fillrighttriangle u?righttriangle u?righttriangle u?dwhrighttriangle" },
	{ "isostri",	"fillisostriangle isostriangle isostriangle dwhisostriangle" },
	{ "rect",	"fillrectangle rectangle rectangle dwhrectangle" },
	{ "pie",	"fillpiewedge piewedge piewedge dwhpiewedge" },
	{ "semicirc",	"fillsemicircle semicircle semicircle dwhsemicircle" },
	{ "allslash",	"fillslashhead fillslashhead fillslashhead fillslashhead" },
	{ "slash",	"fillslashhead slashhead slashhead dwhslashhead" },
	{ 0, 0 }
};

/* Information about characters that are allowed to be noteheads */
struct HEADINFO {
	char ch;	/* code number 32-127 */
	char font;	/* FONT_MUSIC*  */
	float ystem_off[MAX_STEM_DIRS];	/* stepsizes from y to end stem */
};

/* Predefined note head music characters and their attributes. */
struct HEADDATA {
	char *name;
	struct HEADINFO info;
} Predef_headinfo[] = {
  { "dblwhole",		{ C_DBLWHOLE,		FONT_MUSIC, { 0.0, 0.0 } } },
  { "1n",		{ C_1N,			FONT_MUSIC, { 0.0, 0.0 } } },
  { "2n",		{ C_2N,			FONT_MUSIC, { 0.25, -0.25 } } },
  { "4n",		{ C_4N,			FONT_MUSIC, { 0.25, -0.25 } } },
  { "xnote",		{ C_XNOTE,		FONT_MUSIC, { 1.0, -1.0 } } },
  { "dwhdiamond",	{ C_DWHDIAMOND,		FONT_MUSIC, { 0.0, 0.0 } } },
  { "diamond",		{ C_DIAMOND,		FONT_MUSIC, { 0.0, 0.0 } } },
  { "filldiamond",	{ C_FILLDIAMOND,	FONT_MUSIC, { 0.0, 0.0 } } },
  { "dwhrighttriangle",	{ C_DWHRIGHTTRIANGLE,	FONT_MUSIC2, { 0.0, 0.0 } } },
  { "righttriangle",	{ C_RIGHTTRIANGLE,	FONT_MUSIC2, { 0.0, 0.9 } } },
  { "fillrighttriangle",{ C_FILLRIGHTTRIANGLE,	FONT_MUSIC2, { 0.0, 0.9 } } },
  { "udwhrighttriangle",{ C_UDWHRIGHTTRIANGLE,	FONT_MUSIC2, { 0.0, 0.9 } } },
  { "urighttriangle",	{ C_URIGHTTRIANGLE,	FONT_MUSIC2, { -0.9, 0.0 } } },
  { "ufillrighttriangle",{ C_UFILLRIGHTTRIANGLE,FONT_MUSIC2, { -0.9, 0.0 } } },
  { "dwhrectangle",	{ C_DWHRECTANGLE,	FONT_MUSIC2, { -0.9, 0.0 } } },
  { "rectangle",	{ C_RECTANGLE,		FONT_MUSIC2, { 0.0, 0.0 } } },
  { "fillrectangle",	{ C_FILLRECTANGLE,	FONT_MUSIC2, { 0.0, 0.0 } } },
  { "dwhisostriangle",	{ C_DWHISOSTRIANGLE,	FONT_MUSIC2, { -0.8, -0.8 } } },
  { "isostriangle",	{ C_ISOSTRIANGLE,	FONT_MUSIC2, { -0.8, -0.8 } } },
  { "fillisostriangle",	{ C_FILLISOSTRIANGLE,	FONT_MUSIC2, { -0.8, -0.8 } } },
  { "dwhpiewedge",	{ C_DWHPIEWEDGE,	FONT_MUSIC2, { 0.1, 0.2 } } },
  { "piewedge",		{ C_PIEWEDGE,		FONT_MUSIC2, { 0.1, 0.2 } } },
  { "fillpiewedge",	{ C_FILLPIEWEDGE,	FONT_MUSIC2, { 0.1, 0.2 } } },
  { "dwhsemicircle",	{ C_DWHSEMICIRCLE,	FONT_MUSIC2, { 0.8, 0.8 } } },
  { "semicircle",	{ C_SEMICIRCLE,		FONT_MUSIC2, { 0.8, 0.8 } } },
  { "fillsemicircle",	{ C_FILLSEMICIRCLE,	FONT_MUSIC2, { 0.8, 0.8 } } },
  { "blankhead",	{ C_BLANKHEAD,		FONT_MUSIC2, { 0.0, 0.0 } } },
  { "slashhead",	{ C_SLASHHEAD,		FONT_MUSIC2, { 1.8, -1.8 } } },
  { "fillslashhead",	{ C_FILLSLASHHEAD,	FONT_MUSIC2, { 1.8, -1.8 } } },
  { "dwhslashhead",	{ C_DWHSLASHHEAD,	FONT_MUSIC2, { 1.8, -1.8 } } },
  { 0,			{ 0,			0, 	     { 0.0, 0.0 } } }
};

/*
 * This struct provides a mapping from a time signature to all the
 * beamstyle and timeunit values to be associated with that time signature.
 *
 * The [0][0] entry is used for the C_SCORE value.
 * The entries [0][1] through [0][MAXVOICES+1] are unused.
 * The [s][0] entries are used for C_STAFF values where 1 <= s <= MAXSTAFFS
 * The [s][v] entries are used for C_VOICE values where 1 <= s <= MAXSTAFFS
 *			and 1 <= v <= MAXVOICES
 * There will be one of these allocated for each time signature used in the
 * input, if and only if the user also specified at least one beamstyle
 * or timeunit while that time signature was in effect.
 */
struct SSVTABLES {
	struct SSV *beamstyle_table[MAXSTAFFS+1][MAXVOICES+1];
	struct SSV *timeunit_table[MAXSTAFFS+1][MAXVOICES+1];
};


/* information about a symbol: its name and current value.
 * This is used for location tags, chord grids, headshapes, and time signatures.
 * Note that in the case of location tags,
 * if the same name is used in a later measure, just the coordlist_p will
 * change, and when the symbol table is queried for the value of a symbol,
 * it will get the current value for that symbol */
struct Sym {
	char	*symname;
	union {
		float	*coordlist_p;	/* when used for location tags, this is
					 * where its AX, RX, etc values are */
		struct GRID *grid_p;	/* when used for grids */
		struct HDSHAPEINFO *shapeinfo_p;/* when used for headshapes */
		struct HEADINFO *noteinfo_p;	/* when used for note head info */
		/* Info about beamstyles and/or timeunits associated with
		 * the time signature given by the symname. */
		struct SSVTABLES *ssvtables_p;
	} val;
	struct Sym *next;		/* for collision chain off hash table */
};

/* symbol hash table size-- if this changes, hash() has to change accordingly */
#define SYMTBLSIZE	(128)

/* this is the symbol table for location tags */
static struct Sym *Tag_table[SYMTBLSIZE];

/* this is the symbol table for guitar grids. It is malloc-ed at runtime
 * only if needed */
static struct Sym **Grid_table;

/* This is the symbol table for headshapes */
static struct Sym *Shape_table[SYMTBLSIZE];

/* This maps headshape indexes to the corresponding info.
 * Element 0 is unused, since index 0 means "unknown" shape.
 */
static struct Sym *Shape_map[MAX_SHAPE_ENTRIES];
/* How many Shape_map entries are actually used */
static short Shape_entries = 0;

/* This is the symbol table for noteheads, to get stem offsets */
static struct Sym  *Nhead_table[SYMTBLSIZE];

/* This maps notehead character codes to the stem offset info */
static struct HEADINFO *Nhead_map[NUM_MFONTS][CHARS_IN_FONT];

/* This is used to remember what beamstyle and/or timeunit values were
 * associated with time signatures. This is really only needed during parse,
 * and then only if user specifies beamstyle or timeunit somewhere.
 */
static struct Sym *Time_map[SYMTBLSIZE];

/* Internal name for tag used to store the virtual _win coords for blocks */
char Blockwin[] = "~blockwin";
/* This points to where in the symbol table
 * to save the pointer to the coord array for blocks.
 * Having this pointer is a speed optimization,
 * to save us from having to look it up every time. */
float **Blockcoord_p_p;


/* static functions */
static struct GRID *parse_grid P((char *griddef));
static struct Sym *add2tbl P((char *symname, struct Sym **table));
static struct Sym *findSym P((char *symname, struct Sym **table));
static int hash P((char *string));
static int coordhash P((float *key));
static void rep_ref P((float **old_ref_p_p, float **new_ref_p_p));
static void delete_coord P((float *coord_p));
static int is_valid_notehead P((int ch, int font));
static void add_head P((char *name, struct HEADINFO *info_p));


/* size of Coordinfo hash table. Should be prime */
#define COORDTBLSIZE  (271)

static struct COORD_INFO *Coord_table[COORDTBLSIZE];
\f

/* Add predefined values to the symbol tables */

void
init_symtbl()

{
	struct Sym *sym_p;
	int i;

	addsym("_page", _Page, CT_BUILTIN);
	addsym("_cur", _Cur, CT_BUILTIN);

	/* Blocks each have their own virtual _win,
	 * so we put a placeholder in the symbol table
	 * and save a pointer to its tag's coord pointer.
	 * Then we can update the coords via set_win_coords().
	 */
	addsym(Blockwin, 0, CT_BUILTIN);
	sym_p = findSym(Blockwin, Tag_table);
	if (sym_p == 0) {
		pfatal("couldn't find %s coord right after inserting it!",
							Blockwin);
	}
	Blockcoord_p_p = &(sym_p->val.coordlist_p);

	/* Put the predefined notehead shapes into table. */
	for (i = 0; Predef_headinfo[i].name != 0; i++) {
		add_head(Predef_headinfo[i].name, &(Predef_headinfo[i].info));
	}

	/* Put the predefined head shapes in the shapes table */
	for (i = 0; Predef_shape_names[i].clan_name != 0; i++) {
		add_shape(Predef_shape_names[i].clan_name,
					Predef_shape_names[i].member_names);
	}
}
\f

/* add a symbol to the table if not already there and fill in its coordlist_p
 * in symbol table. */

void
addsym(symname, coordlist_p, coordtype)

char *symname;		/* what to add to table */
float *coordlist_p;	/* set of 13 coordinates associated with symbol */
int coordtype;		/* CT_BAR, CT_GRPSYL, etc */

{
	struct Sym *sym_p;	/* pointer to info about symbol in hash tbl */


	debug(4, "addsym(symname=%s coordlist_p=0x%lx, coordtype=%d)",
					symname, coordlist_p, coordtype);

	/* find in symbol table or add if not yet there */
	sym_p = add2tbl(symname, Tag_table);

	/* fill in coordlist pointer */
	sym_p->val.coordlist_p = coordlist_p;

	/* put entry in coord table */
	add_coord(coordlist_p, coordtype);
}
\f

/* add a symbol to the specified hash table */

static struct Sym *
add2tbl(symname, table)

char *symname;		/* what to add */
struct Sym **table;	/* which table to add to */

{
	struct Sym *sym_p;
	int h;			/* hash number of symbol */

	if ((sym_p = findSym(symname, table)) == (struct Sym *) 0) {

		/* not in list before. Add it */
		MALLOC(Sym, sym_p, 1);
		MALLOCA(char, sym_p->symname, strlen(symname) + 1);
		(void) strcpy(sym_p->symname, symname);
		h = hash(symname);

		/* link onto front of list off hash table */
		sym_p->next = table[h];
		table[h] = sym_p;
	}
	return(sym_p);
}
\f

/* given a symbol name, return pointer to its symbol table entry, or NULL
 * if none */

static struct Sym *
findSym(symname, table)

char *symname;		/* which symbol to look for */
struct Sym **table;	/* which table to look in */

{
	struct Sym *sym_p;	/* symbol info currently being checked
				 * for match with symname */
	int h;			/* hash number */


	h = hash(symname);
	/* go down the linked list (of hash collisions) off the table
	 * searching for match */
	for (sym_p = table[h]; sym_p != (struct Sym *) 0;
						sym_p = sym_p->next) {
		if (strcmp(sym_p->symname, symname) == 0) {
			return(sym_p);
		}
	}
	return((struct Sym *) 0);
}
\f

/* For top/bot/top2/bot2/block we temporarily set the ~blockwin tag to point
 * to the appropriate blockhead's coord array. Before doing a set_win for
 * any of those, this function should be called to set things up, and
 * it should be called again afterwards with 0 to mark we are no longer
 * inside a block.
 */

void
set_win_coord(coord_p)

float *coord_p;

{
	*Blockcoord_p_p = coord_p;
}
\f

/* Given a tag name, return its value (a pointer to the coordinate array
 * containing the AX, AY, etc of the variable).
 * If the tag is not found, an error is printed and 0 is returned.
 * If the ref_p_p is non-null,
 * save that value as something that references the tag. That way if the
 * tag gives moved somewhere else, we can update all the references.
 * If referencing the value of a coord that can never move (a builtin coord
 * like _win), ref_p_p may be null.
 */

float *
symval(symname, ref_p_p)

char *symname;		/* which symbol to look up */
float **ref_p_p;	/* address of reference to the tag */

{
	struct Sym *sym_p;	/* symbol info currently being checked */


	/* _win is a special case: its actual symbol depends on context */
	if (strcmp(symname, "_win") == 0) {
		/* If we're inside a block, use its coord,
		 * else use the global _Win */
		if (*Blockcoord_p_p != 0) {
			return(*Blockcoord_p_p);
		}
		else {
			return(_Win);
		}
	}
	
	/* find the symbol table entry */
	if ((sym_p = findSym(symname, Tag_table)) != (struct Sym *) 0) {
		if (sym_p->val.coordlist_p != (float *) 0) {
			/* save reference information */
			if (ref_p_p != 0) {
				struct COORD_INFO *coordinfo_p;
				struct COORD_REF *ref_p;
				CALLOC(COORD_REF, ref_p, 1);
				ref_p->ref_p_p = ref_p_p;
				/* link onto reference list */
				coordinfo_p = find_coord(sym_p->val.coordlist_p);
				ref_p->next = coordinfo_p->ref_list_p;
				coordinfo_p->ref_list_p = ref_p;
			}
			return(sym_p->val.coordlist_p);
		}
	}

	/* whoops! not in table */
	l_yyerror(Curr_filename, yylineno,
			"reference to uninitialized location tag '%s'",
			symname);
	return((float *) 0);
}	
\f

/* add item to grid table if not already there. */

void
add_grid(name, griddef)

char *name;		/* chord name */
char *griddef;		/* user's definition of the grid */

{
	char *internal_name;	/* internal format name */
	char *grid_name;	/* permanent copy of internal_name */
	char *symname;		/* ASCII-ized name */
	char *key;		/* permanent copy of symname, key into hash tbl */
	struct Sym *sym_p;
	struct GRID *grid_p;


	/* if table doesn't exist yet, create it */
	if (Grid_table == 0) {
		int g;

		MALLOCA(struct Sym *, Grid_table, SYMTBLSIZE);
		for (g = 0; g < SYMTBLSIZE; g++) {
			Grid_table[g] = 0;
		}
	}

	/* Do all the transforms to get into internal form with
	 * accidentals as music characters. For historical reasons,
	 * this has to be done in several steps, in just the right order. */
	internal_name = modify_chstr(name, TM_CHORD);
	internal_name = fix_string(internal_name, Score.font, Score.size,
						Curr_filename, yylineno);
	/* convert accidentals, then convert to all ASCII */
 	grid_name = tranchstr(internal_name, -1);
	symname = ascii_str(grid_name, YES, NO, TM_CHORD);

	if (strlen(symname) == 0) {
		yyerror("empty grid name not allowed");
		return;
	}

	if ((sym_p = findSym(symname, Grid_table)) != 0) {
		l_warning(Curr_filename, yylineno,
			"duplicate definition of grid for '%s', discarding previous",
			symname);
		/* discard old definition, use new one */
		if (sym_p->val.grid_p != 0) {
			if (sym_p->val.grid_p->name != 0) {
				FREE(sym_p->val.grid_p->name);
			}
			FREE(sym_p->val.grid_p);
			sym_p->val.grid_p = 0;
		}
		key = sym_p->symname;
	}
	else {
		/* make permanent copy of key */
		MALLOCA(char, key, strlen(symname) + 1);
		(void) strcpy(key, symname);
	}

	if ((grid_p = parse_grid(griddef)) != 0) {
		/* it's good, so put in hash table */
		sym_p = add2tbl(key, Grid_table);

		/* fill in the name and grid pointer */
		grid_p->name = grid_name;
		sym_p->val.grid_p = grid_p;;
		{
			/* buffer--2 digits and a space for each string, plus null */
			char fretlist[3 * MAXTABLINES + 1];
			int f;
			for (f = 0; f < grid_p->numstr; f++) {
				(void) sprintf(fretlist + 3 * f, "%3d",
							 grid_p->positions[f]);
			}
			fretlist[sizeof(fretlist) - 1] = '\0';
			debug(4, "added grid '%s' key '%s' with %d strings: %s curve %d to %d",
					name, key,
					grid_p->numstr, fretlist,
					grid_p->curvel, grid_p->curver);
		}
	}
}
\f

/* take the user's grid definition, like "2 (3 1) o x -"
 * and populate a GRID struct with the info. If not parse-able,
 * return 0 */

static struct GRID *
parse_grid(griddef)

char *griddef;	/* user's definition of the grid */

{
	struct GRID *grid_p;	/* the malloc-ed grid to populate & return */
	int error = NO;
	int value;

	MALLOC(GRID, grid_p, 1);
	grid_p->numstr = 0;
	grid_p->curvel = grid_p->curver = 0;
	grid_p->used = NO;
	/* the +2 is to skip the font/size bytes */
	for (griddef += 2; *griddef != '\0' && error == NO; griddef++) {
		/* init to something illegal */
		value = -1000;

		while (*griddef == ' ' || *griddef == '\t') {
			griddef++;
		}
		if (*griddef == '\0') {
			break;
		}

		if ( isdigit(*griddef) ) {
			value = *griddef - '0';
			if (isdigit(*(griddef+1))) {
				value *= 10;
				griddef++;
				value += *griddef - '0';
			}
			if (value == 0) {
				yyerror("fret of zero not allowed; use 'o' for open or '-' for nothing");
				error = YES;
			}
		}
		else if (*griddef == '(') {
			if (grid_p->curvel != 0) {
				yyerror("only one '(' allowed in grid definition");
				error = YES;
			}
			else {
				grid_p->curvel = grid_p->numstr + 1;
			}
		}
		else if (*griddef == ')') {
			if (grid_p->curver != 0) {
				yyerror("only one ')' allowed in grid definition");
				error = YES;
			}
			else if (grid_p->curvel == 0) {
				yyerror("missing '(' in grid definition");
				error = YES;
			}
			else if (grid_p->curvel == grid_p->numstr) {
				yyerror("curve in grid definition must encompass more than one string");
				error = YES;
			}
			else {
				grid_p->curver = grid_p->numstr;
			}
		}
		else if (*griddef == 'o') {
			value = 0;
		}
		else if (*griddef == 'x') {
			value = -1;
		}
		else if (*griddef == '-') {
			value = -2;
		}
		else {
			yyerror("invalid grid specification");
			FREE(grid_p);
			return (0);
		}

		if (value >= -2) {
			/* We found a fret value (not parentheses).
			 * Next better be white space sort of thing */
			char c;
			c = *(griddef + 1);
			if (c != ' ' && c != '\t' && c != '(' && c != ')'
							&& c != '\0') {
				yyerror("missing white space in grid specification");
				error = YES;
			}
			else if (grid_p->numstr < MAXTABLINES) {
				/* all is well; save info for current string */
				grid_p->positions[grid_p->numstr] = value;
				(grid_p->numstr)++;
			}
			else {
				yyerror("too many strings in grid specification");
				error = YES;
			}
		}
	}

	if (error == NO && grid_p->curvel != 0 && grid_p->curver == 0) {
		yyerror("missing ')' in grid specification");
		error = YES;
	}
	
	if (grid_p->numstr < 1) {
		yyerror("grid must include at least one string");
		error = YES;
	}

	/* every curve must have at least one real fret in it */
	if (grid_p->curvel != 0) {
		int s;
		/* the -1 is because curves start at 1, but positions at 0 */
		for (s = grid_p->curvel - 1; s <= grid_p->curver - 1; s++) {
			if (grid_p->positions[s] > 0) {
				break;
			}
		}
		if (s == grid_p->curver) {
			yyerror("grid curve must include at least one fret number, not just x, o, and -");
			error = YES;
		}
	}

	if (error == YES) {
		/* clean up */
		FREE(grid_p);
		grid_p = 0;
	}
	return(grid_p);
}
\f

/* Locate a named GRID in the grid hash table. Returns 0 if not found,
 * else pointer to desired GRID. */

struct GRID *
findgrid(name)

char *name;	/* find GRID with this chord name */

{
	struct Sym *sym_p;
	char *ascii_name;
	int length;
	int first_char;

	if (Grid_table == 0) {
		/* no grids defined */
		return((struct GRID *) 0);
	}

	ascii_name = ascii_str(name, YES, NO, TM_CHORD);
	/* Chord names in STUFF have a space padding at the end of them
	 * unless they are in a box or circle, so strip that off for matching
	 * the name. We store the grid name without the space, because for
	 * grid printing, we want the name centered without end padding. */
	length = strlen(ascii_name);
	first_char = ((int)*(name+2)) & 0xff;
	if (first_char != STR_BOX && first_char != STR_CIR
					&& ascii_name[length-1] == ' ') {
		ascii_name[length-1] = '\0';
	}

	/* look it up */
	sym_p = findSym(ascii_name, Grid_table);

	return (sym_p ? sym_p->val.grid_p : 0);
}
\f

/* Function to iterate through all the GRIDs. First time, call it with
 * argument of zero, and it returns the first GRID it finds. To walk
 * through the list, call it repeatedly, each time passing the GRID
 * you got the last time.  When you get back a zero, the list is done.
 * Restrictions: you must either call with zero or the last one you got.
 * You can't remember some previous value and use that to try to jump
 * to elsewhere on the list, or have multiple walks going on at once.
 * Caller should assume values are returned in arbitrary order.
 */

struct GRID *
nextgrid(grid_p)

struct GRID *grid_p;

{
	static int tbl_index = -1;
	static struct Sym *last_sym_p = 0;	/* remember where we were the
						 * last time we were called */

	if (grid_p == 0) {
		/* starting at beginning */
		tbl_index = -1;
		last_sym_p = 0;
	}
	else if (last_sym_p == 0 || grid_p != last_sym_p->val.grid_p) {
		pfatal("nextgrid called incorrectly");
	}

	/* if there is another on the current collision chain, use that */
	if (last_sym_p != 0) {
		last_sym_p = last_sym_p->next;
	}

	/* if none, either if just starting, or if ran off the end
	 * of a collision chain, find next chain. */
	if (last_sym_p == 0) {
		for (tbl_index++; tbl_index <  SYMTBLSIZE; tbl_index++) {
			if (Grid_table[tbl_index] != 0) {
				/* found a populated chain */
				last_sym_p = Grid_table[tbl_index];
				break;
			}
		}
	}

	return(last_sym_p == 0 ? 0 : last_sym_p->val.grid_p);
}
\f

/* return a hash number from a string. XOR the bytes together */

static int
hash(string)

char *string;	/* hash this string */

{
	int h;	/* hash number */

	for (h = 0; *string != '\0'; string++) {
		h ^= *string;
	}
	/* return hash number between 0 and 127 */
	return(h & 0x7f);
}
\f

/* add entry to COORD_INFO table */

void
add_coord(coordlist_p, coordtype)

float *coordlist_p;	/* address of set of 13 coordinates to add to tbl */
int coordtype;		/* CT_GRPSYL, etc */

{
	struct COORD_INFO *new_p;	/* space for saving coord info */
	int h;				/* hash number */


	/* if not already in table, add it */
	if (find_coord(coordlist_p) == (struct COORD_INFO *) 0) {

		/* get space, fill in coord type, and link into hash table */
		CALLOC(COORD_INFO, new_p, 1);

		new_p->coordlist_p = coordlist_p;
		new_p->flags = (short) coordtype;

		h = coordhash(coordlist_p);
		new_p->next = Coord_table[h];
		Coord_table[h] = new_p;
	}
}
\f

/* Given an address of an array of floats (a coordinate array), return a hash
 * number, which is modulo of the Coord_table table size */

static int
coordhash(key)

float *key;	/* hash this number */

{
	return ((int) ( (unsigned long) key % COORDTBLSIZE));
}
\f

/* Given a coordinate (pointer to array of floats), return the location of
 * the info about it in the Coord_table, or 0 if not in table */

struct COORD_INFO *
find_coord(key)

float *key;		/* look up this key in hash table */

{
	int h;			/* hash number */
	struct COORD_INFO *c_p;


	/* search hash table for matching entry */
	h = coordhash(key);
	for (c_p = Coord_table[h]; c_p != (struct COORD_INFO *) 0;
							c_p = c_p->next) {
		if (key == c_p->coordlist_p) {
			return(c_p);
		}
	}
	return( (struct COORD_INFO *) 0);
}
\f

/* Given an existing INPCOORD, and a new INPCOORD that is to replace it,
 * adjust any tag references (hor_p or vert_p) to point to the new one. */

void
rep_inpcoord(old_inpcoord_p, new_inpcoord_p)

struct INPCOORD *old_inpcoord_p;
struct INPCOORD *new_inpcoord_p;

{
	rep_ref( &(old_inpcoord_p->hor_p), &(new_inpcoord_p->hor_p) );
	rep_ref( &(old_inpcoord_p->vert_p), &(new_inpcoord_p->vert_p) );
	
}

/* Given an existing reference to a tag in an INPCOORD, replace that
 * reference with the new reference. This is for when transferring a
 * temporary INPCOORD to a permanent one.
 */

static void
rep_ref(old_ref_p_p, new_ref_p_p)

float **old_ref_p_p;
float **new_ref_p_p;

{
	struct COORD_INFO *coordinfo_p;
	struct COORD_REF *ref_p;

	if (*old_ref_p_p == 0) {
		/* This can happen if user references uninitialized tag.
		 * We already give error message elsewhere for that. */
		return;
	}
	if (*new_ref_p_p == 0) {
		pfatal("attempt to replace tag reference with null.");
		return;
	}

	/* Find this information about the coordinate */
	if ((coordinfo_p = find_coord(*old_ref_p_p)) == 0) {
		/* Must have been earlier user error. */
		return;
	}

	/* Find any references matching the old and update them.
	 * Really should be only one, but seems safer to check all.
	 */
	for (ref_p = coordinfo_p->ref_list_p; ref_p != 0; ref_p = ref_p->next) {
		if (ref_p->ref_p_p == old_ref_p_p) {
			ref_p->ref_p_p = new_ref_p_p;
		}
	}
}
\f

/* Given an existing coord array address and an address it is being moved to,
 * update all references to the old to point to the new, and update our
 * hash table to insert the old and delete the old.
 */

void
upd_ref(oldcoord_p, newcoord_p)

float * oldcoord_p;
float * newcoord_p;

{
	struct COORD_INFO *coordinfo_p;	/* existing info about oldcoord_p */
	struct COORD_INFO *newcoordinfo_p;	/* for info about newcoord_p */
	struct COORD_REF *ref_p;	/* for walking through ref list */

	if ((coordinfo_p = find_coord(oldcoord_p)) == 0) {
		/* apparently no tags associated with this coord array */
		return;
        }
	/* update all the references to the tag with the new value */
        for (ref_p = coordinfo_p->ref_list_p; ref_p != 0; ref_p = ref_p->next) {
                *(ref_p->ref_p_p) = newcoord_p;
        }

	/* Now need to create new entry for the new coord, and delete old */
	add_coord(newcoord_p, coordinfo_p->flags);
	/* Append reference list to new coord info */
	if ((newcoordinfo_p = find_coord(newcoord_p)) != 0) {
		/* Should always get here; the 'if' is to just paranoia
		 * to be sure to avoid null pointer deference. */
		/* If coord already existed before, because one coord is
		 * being combined with another, we want to concatenate the
		 * reference list, so find end to append to. */
		struct COORD_REF **append_p_p;
		for (append_p_p = &(newcoordinfo_p->ref_list_p);
					*append_p_p != 0;
					append_p_p = &((*append_p_p)->next)) {
			;
		}

		*append_p_p = coordinfo_p->ref_list_p;
		coordinfo_p->ref_list_p = 0;
	}
	delete_coord(oldcoord_p);
}
\f

/* Delete the given coordinate information */

static void
delete_coord(coord_p)

float * coord_p;

{
	int h;			/* hash number */
	struct COORD_INFO **c_p_p;

	/* search hash table for matching entry and delete it */
	h = coordhash(coord_p);
	for (c_p_p = &(Coord_table[h]); *c_p_p != 0; *(c_p_p) = (*c_p_p)->next) {
		if ((*c_p_p)->coordlist_p == coord_p) {
			struct COORD_INFO * to_delete_p;
			to_delete_p = *c_p_p;
			*c_p_p = (*c_p_p)->next;
			FREE(to_delete_p);
			return;
		}
	}
}
\f

/* Given a shape name and string containing the 4 note heads to use for it,
 * as would exist in a line of "headshapes" context, parse the
 * string with the noteheads and save all the information
 * in the shapes hash table.
 */

void
add_shape(name, shapes)

char *name;	/* name of the list of shapes */
char *shapes;	/* list of 4 shape names */

{
	struct Sym *sym_p;		/* where added into Shape_table */
	struct HDSHAPEINFO *shapeinfo_p;/* internal format for shape data */
	int i;			/* index through shapes */
	int d;			/* index through durations */
	int nameleng;		/* length of one name in shapes list */
	char namebuff[40];	/* one of the names in shapes list.
				 * Needs to be big enough to hold longer
				 * name of any valid note head character. */
	char ch;		/* music character corresponding to head name */
	int font;		/* which font FONT_MUSIC*  */
	int size;		/* not really needed here, but function we
				 * call expect it */
	short flips;		/* YES if stem down uses upside down version */

	debug(4, "add_shape name='%s' shapes='%s'", name, shapes);

	/* Add to symbol table */
	sym_p = add2tbl(name, Shape_table);
	MALLOC(HDSHAPEINFO, shapeinfo_p, 1);
	sym_p->val.shapeinfo_p = shapeinfo_p;

	/* Allocate an index and fill in the index-to-info mapping array */
	shapeinfo_p->index = ++Shape_entries;
	if (Shape_entries >= MAX_SHAPE_ENTRIES) {
		yyerror("Too many headshapes");
		return;
	}
	else {
		Shape_map[Shape_entries] = sym_p;
	}

	/* Parse the list of 4 shapes and save their info */
	size = DFLT_SIZE;
	for (d = i = 0; shapes[i] != '\0';  ) {
		/* Skip white space */
		if (isspace(shapes[i])) {
			i++;
			continue;
		}

		/* Make sure user didn't give too many shapes */
		if (d >= MAX_SHAPE_DURS) {
			l_yyerror(Curr_filename, yylineno,
				"Too many shapes for headshape '%s' (%d expected, %d found)\n",
				name, MAX_SHAPE_DURS, d);
			return;
		}

		/* Check if stem down gets a flipped character */
		if (shapes[i] == 'u' && shapes[i+1] == '?') {
			flips = YES;
			i += 2;
		}
		else {
			flips = NO;
		}

		/* get copy of current head name, and look up its character */
		nameleng = strcspn(shapes + i, " \t\r\n");
		/* leave room for null and 'u' for upsidedown */
		if (nameleng > sizeof(namebuff) - 2) {
			ufatal("head shape name too long");
		}
		if (nameleng == 0 && flips == YES) {
			l_yyerror(Curr_filename, yylineno,
				"'u?' must be followed immediately by a note head character name");
			return;
		}
		strncpy(namebuff, shapes + i, nameleng);
		namebuff[nameleng] = '\0';
		ch = mc_name2num(namebuff, Curr_filename, yylineno, &size, &font);
		if (is_valid_notehead(ch, font) == NO) {
			l_yyerror(Curr_filename, yylineno,
				"'%s' is not a valid note head name", namebuff);
			return;
		}
			
		shapeinfo_p->headchar[STEMINDEX(UP)][d] = ch;
		shapeinfo_p->headfont[STEMINDEX(UP)][d] = font;

		/* If flips, get upside down version. Else use same again */
		if (flips == YES) {
			namebuff[0] = 'u';
			strncpy(namebuff + 1, shapes + i, nameleng);
			namebuff[nameleng+1] = '\0';
			ch = mc_name2num(namebuff, Curr_filename, yylineno, &size, &font);
			if (is_valid_notehead(ch, font) == NO) {
				l_yyerror(Curr_filename, yylineno,
					"'%s' is not a valid note head name", namebuff);
				return;
			}
		}
		shapeinfo_p->headchar[STEMINDEX(DOWN)][d] = ch;
		shapeinfo_p->headfont[STEMINDEX(DOWN)][d] = font;

		/* Prepare for next in the list, if any */
		d++;
		i += nameleng;
	}
	if (d < MAX_SHAPE_DURS) {
		l_yyerror(Curr_filename, yylineno,
			"Too few shapes for headshape '%s' (%d expected, %d found)\n",
			name, MAX_SHAPE_DURS, d);
	}
}
\f

/* Given a head shape index, stemdir, and basictime, return the notehead
 * character to use and (via font_p pointer)
 * which music font that notehead character is in.
 */

int
nheadchar(headshape, basictime, stemdir, font_p)

int headshape;		/* head shape index */
int basictime;		/* 8 for eighth, 2 for half, etc */
int stemdir;		/* UP or DOWN */
int *font_p;		/* FONT_MUSIC* is returned here */

{
	struct Sym *info_p;	/* shape to character map */
	int dir;		/* first index into headchar */
	int dur;		/* second index into headchar */

	if (headshape == HS_UNKNOWN || headshape > Shape_entries) {
		pfatal("illegal headshape index to nheadchar (%d)", headshape);
	}

	info_p = Shape_map[headshape];

	dir = STEMINDEX(stemdir);
	dur = HCDUR(basictime);
	*font_p = info_p->val.shapeinfo_p->headfont[dir][dur];
	return(info_p->val.shapeinfo_p->headchar[dir][dur]);
}
\f

/* Given a head shape name, return the internal index number we use
 * to refer to that shape.
 */

int
get_shape_num(shapename)

char *shapename;

{
	struct Sym *sym_p;

	if ((sym_p = findSym(shapename, Shape_table)) != 0) {
		return(sym_p->val.shapeinfo_p->index);
	}
	return(HS_UNKNOWN);
}
\f

/* Return YES if given character is a valid note head character, else NO */

static int
is_valid_notehead(ch, font)

int ch;		/* character code */
int font;	/* FONT_MUSIC*  */

{
	if ( IS_MUSIC_FONT(font) == NO || ch < 0 || ch >= CHARS_IN_FONT) {
		/* If caller passes us the return from mc_name2num(),
		 * that could return BAD_CHAR, so we don't pfatal here,
		 * but do return right away, so we don't do an illegal
		 * array index below.
		 */
		return(NO);
	}
	return (Nhead_map[FONTINDEX(font)][CHARINDEX(ch)] == 0 ? NO : YES);
}
\f

/* Save note head information in table */
/** If we allow users to supply their own some day,
 * would need a function that allocates and fills in a HEADINFO,
 * and then calls this one. */

static void
add_head(name, info_p)

char *name;	/* music character name */
struct HEADINFO *info_p;	/* char/font/stem offset */

{
	struct Sym *sym_p;

	
	sym_p = add2tbl(name, Nhead_table);
	sym_p->val.noteinfo_p = info_p;

	/* Fill in reverse lookup map */
	Nhead_map[FONTINDEX(info_p->font)][CHARINDEX(info_p->ch)] = info_p;
}
\f

/* Given a note head character and stem direction,
 * return the y offset for the stem to end, in stepsizes.
 */

double
stem_yoff(headch, font, stemdir)

int headch;	/* music character code */
int font;	/* FONT_MUSIC*   */
int stemdir;	/* UP or DOWN */

{
	struct HEADINFO *info_p;

	if ( IS_MUSIC_FONT(font) == NO || headch < 0 || headch >= CHARS_IN_FONT) {
		pfatal("invalid argument: stem_yoffset(%d, %d, stemdir)",
							headch, font, stemdir);
	}
	info_p = Nhead_map[FONTINDEX(font)][CHARINDEX(headch)];
	if (info_p == 0) {
		pfatal("No notehead map for ch=%d, font=%d", headch, font);
	}
	if (stemdir == UNKNOWN) {
		pfatal("stem_yoff called with unknown stemdir");
	}
	return(info_p->ystem_off[STEMINDEX(stemdir)]);
}
\f

/* This should be called when an SSV has been collected by the user.
 * If the user set beamstyle and/or timeunit in the SSV,
 * create a mapping between the current time signature and that beamstyle
 * and/or timeunit, so that if the user later sets the same time signature,
 * they don't have to set the other things too.
 * If they set time signature, see if we have a mapping
 * for that time signature. If so, set the beamstyles and timeunits
 * from that mapping.
 */

void
remember_tsig_params(mll_p)

struct MAINLL *mll_p;	/* contains SSV */

{
	struct SSV *ssv_p;	/* the SSV to process */
	char *timesig;		/* current time signature representation */
	struct Sym *entry;	/* entry in time sig info mapping table */


	if (mll_p->str != S_SSV) {
		pfatal("remember_tsig_params got bad str value %d", mll_p->str);
	}
	ssv_p = mll_p->u.ssv_p;

	if (ssv_p->used[TIME] == NO && ssv_p->used[BEAMSTLIST] == NO &&
					ssv_p->used[TIMEUNIT] == NO) {
		/* nothing of interest in this SSV */
		return;
	}

	/* If user set time signature in this SSV, that's the time sig
	 * of interest, otherwise use the current time signature */
	timesig = (ssv_p->used[TIME] == YES ? ssv_p->timerep : Score.timerep);
	if ((entry = findSym(timesig, Time_map)) == 0) {
		entry = add2tbl(timesig, Time_map);
		/* We'll only allocate the actual table if user gives a
		 * beamstyle or timeunit somewhere. If they never do,
		 * this will avoid wasting memory.
		 */
		entry->val.ssvtables_p = 0;
	}

	/* If beamstyle or timeunit are set in this SSV, associate them
	 * with the current time signature. */
	if (ssv_p->used[BEAMSTLIST] == YES) {
		if (entry->val.ssvtables_p == 0) {
			CALLOC(SSVTABLES, entry->val.ssvtables_p, 1);
		}
		/* Note that when staffno and voiceno are zero,
		 * that's actually a score entry, and when voiceno is zero,
		 * but staffno is non-zero, that is actually a staff entry. */
		entry->val.ssvtables_p->beamstyle_table[ssv_p->staffno][ssv_p->voiceno] = ssv_p;
	}
	if (ssv_p->used[TIMEUNIT] == YES) {
		if (entry->val.ssvtables_p == 0) {
			CALLOC(SSVTABLES, entry->val.ssvtables_p, 1);
		}
		entry->val.ssvtables_p->timeunit_table[ssv_p->staffno][ssv_p->voiceno] = ssv_p;
	}

	/* If time signature is set in this SSV, see if we have any
	 * beamstyles or timeunits associated with that time signature.
	 * If so, restore their values. */
	if (ssv_p->used[TIME] == YES && entry->val.ssvtables_p != 0) {
		/* Make new SSVs and copy the relevant fields for any
		 * remembered beamstyles and/or timesunits associated 
		 * with this time signature. */
		struct SSV *beamstyle_ssv_p;	/* SSV having beamstyle info */
		struct SSV *timeunit_ssv_p;	/* SSV having timeunit info */
		struct MAINLL *mll_ssv_p;	/* new SSV to add to list */
		struct SSV *nssv_p;		/* new SSV to add to list */
		int s;				/* staff */
		int v;				/* voice */

		/* Check all SSV contexts. The [0][0] entry is for Scoreo			 * The rest of row [0] is unused.
		 * The [0] column is for staffs, for s > 0.
		 */
		for (s = 0; s <= MAXSTAFFS; s++) {
			for (v = 0; v <= MAXVOICES; v++) {

				/* Check if we need to create an SSV for
				 * this staff/voice */
				beamstyle_ssv_p = entry->val.ssvtables_p->beamstyle_table[s][v];
				timeunit_ssv_p = entry->val.ssvtables_p->timeunit_table[s][v];
				if (beamstyle_ssv_p == 0 &&
						timeunit_ssv_p == 0) {
					/* nothing to do for this one */
					continue;
				}

				/* If both saved SSVs are either zero or
				 * the same SSV as where the time was just
				 * set, no need to make another SSV */
				if ( (beamstyle_ssv_p == 0 ||
						beamstyle_ssv_p == ssv_p) &&
						(timeunit_ssv_p == 0 ||
						timeunit_ssv_p == ssv_p) ) {
					continue;
				}

				/* need to create an SSV */
				mll_ssv_p = newMAINLLstruct(S_SSV, -1);
				insertMAINLL(mll_ssv_p, mll_p);
				mll_p = mll_ssv_p;

				/* populate the new SSV */
				nssv_p = mll_ssv_p->u.ssv_p;
				if (beamstyle_ssv_p != 0) {
					nssv_p->nbeam = beamstyle_ssv_p->nbeam;
					nssv_p->beamstlist = beamstyle_ssv_p->beamstlist;
					nssv_p->beamrests = beamstyle_ssv_p->beamrests;
					nssv_p->beamspaces = beamstyle_ssv_p->beamspaces;
					nssv_p->nsubbeam = beamstyle_ssv_p->nsubbeam;
					nssv_p->subbeamstlist = beamstyle_ssv_p->subbeamstlist;
					nssv_p->used[BEAMSTLIST] = YES;
				}
				if (timeunit_ssv_p != 0) {
					nssv_p->timeunit = timeunit_ssv_p->timeunit;
					nssv_p->used[TIMEUNIT] = YES;
				}

				/* fill in the SSV header */
				if (v != 0) {
					nssv_p->context = C_VOICE;
				}
				else if (s != 0) {
					/* The [s][0] entry is for staff s
					 * when s > 0 */
					nssv_p->context = C_STAFF;
				}
				else {
					/* The [0][0] entry is actually score */
					nssv_p->context = C_SCORE;
				}
				nssv_p->staffno = s;
				nssv_p->voiceno = v;
				asgnssv(nssv_p);
			}
		}
	}
}