/*
 * Copyright (c) 1997, by Sun Microsystems, Inc.
 * All rights reserved.
 */

/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
/*	  All Rights Reserved  	*/

/*	THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T	*/
/*	The copyright notice above does not evidence any   	*/
/*	actual or intended publication of such source code.	*/

#ident	"@(#)tree.c	1.6	97/07/28 SMI"	/* SVr4.0 k18.2   */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "symtab.h"
#include "kbd.h"

extern int linnum;	/* line number */

struct node *root;
int numnode = 0;

struct node *nalloc(void);

/*
 * Build nodes in the tree for new strings.
 */

int dup_error = 0;
			/*
			 * the line number that is duped by this entry IF
			 * it is a duplicate of something already in
			 * the tree.
			 */

int
tree(struct node *p, unsigned char *input, unsigned char *result)
{
	struct node *q;

	dup_error = 0;	/* set initially to zero */
	if (! *input) {
		fprintf(stderr, gettxt("kbdcomp:52",
			"Internal error in 'tree' (no input).\n"));
		return (E_ERROR);
	}
	q = p;	/* p is the first node at this level */
	while (p && (p->n_val != *input)) {
		/* seek the *i at this level */
		p = p->n_next;
	}
	if (!p) {	/* no node this level */
		/* make p a new node this level, link it AFTER q. */
		p = nalloc();
		if (q) {
			p->n_next = q->n_next;
			q->n_next = p;
		}
		/* make a child node */
		p->n_what.n_child = nalloc();
		if (! (*(input+1))) { /* we're at last character */
			p->n_val = *input;
			p->n_what.n_child->n_flag = N_RESULT;
			p->n_what.n_child->n_what.n_result =
				strsave((char *)result);
/*
 * Try to keep track of line numbers whenever a result is
 * generated.  It may help when the table has duplicate nodes.
 */
			p->n_what.n_child->n_lnum = linnum;
			return (0);
		} else {	/* have to descend */
			p->n_flag = N_CHILD;
			p->n_val = *input++;
			tree(p->n_what.n_child, input, result);
/*
 * Remove null entries generated by the "descent" mechanism.. SIGH...
 */
			if ((! p->n_what.n_child->n_val) &&
				p->n_what.n_child->n_next) {
				q = p->n_what.n_child;
				p->n_what.n_child = q->n_next;
				free(q);
			}
			return (0);
		}
	}
	if (p->n_val != *input) {
		fprintf(stderr, gettxt("kbdcomp:53",
			"Internal error in 'tree' (n_val != *input)\n"));
		return (E_ERROR);
	}
	/* we have found the node at at this level */
	if (! (*(input+1))) {
		/*
		 * if at "end of string", it's a DUP:  trying to define
		 * a shorter string dup'ing one already in the tree.
		 */
		return (E_DUP);
	}
	if (p->n_flag == N_RESULT) {
		fprintf(stderr, gettxt("kbdcomp:54",
			"Internal error: bad node type in 'tree'.\n"));
		return (E_ERROR);
	}
	if (p->n_what.n_child) {	/* has a child??? */
		if (p->n_what.n_child->n_flag == N_RESULT) {
			/*
			 * Catch places where we're trying to do a dup
			 * that's LONGER than something already defined.
			 */
			dup_error = p->n_what.n_child->n_lnum;
			return (E_DUP);
		}
		++input;
	} else {	/* why no children ? */
		p->n_what.n_child = nalloc();
		p->n_what.n_child->n_flag = N_CHILD;
		p->n_val = *input++;
		if (! *input) {
			fprintf(stderr, gettxt("kbdcomp:55",
"Internal error in tree walk (unexpected end of input).\n"));
			return (E_ERROR);
		}
	}
	return (tree(p->n_what.n_child, input, result));
}



struct node *
nalloc(void)
{
	struct node *n;

	if (n = (struct node *) calloc(1, sizeof (struct node))) {
		if (!root)
			root = n;
		return (n);
	} else {
		fprintf(stderr, gettxt("kbdcomp:56",
			"Error - calloc failed in 'nalloc'.\n"));
		exit(1);
	}
}

int level = 0;

#if 0	/* Debugging Routines */
void
showtree(struct node *p)
{
	while (p) {
		switch (p->n_flag) {
		case N_CHILD:	fprintf(stderr, "C"); break;
		case N_RESULT:	fprintf(stderr, "R"); break;
		case N_EMPTY:	fprintf(stderr, "E"); break;
		default:	fprintf(stderr, "?"); break;
		}
		fprintf(stderr, "-%04d(%04d)", p->n_num, p->n_node);
		dolevel(level);
		switch (p->n_flag) {
		case N_CHILD:
			if (!p->n_val)
				fprintf(stderr, gettxt("kbdcomp:57",
					"(null)\n"));
			else
				fprintf(stderr, "%c\n", p->n_val);
			++level;
			showtree(p->n_what.n_child);
			--level;
			break;
		case N_RESULT:
			fprintf(stderr, "%s\n", p->n_what.n_result);
			break;
		case N_EMPTY:
			fprintf(stderr, "EMPTY:%03o\n", p->n_val);
			break;
		default:
			fprintf(stderr, gettxt("kbdcomp:58",
				"Unknown Node Type %d\n"), p->n_flag);
			break;
		}
		p = p->n_next;
	}

}

void
dolevel(int i)
{
	fprintf(stderr, "%4d ", i);
	while (i--)
		fprintf(stderr, "  ");

}
#endif	/* end of Debugging Routines */

/*
 * Number the nodes of the tree prior to building the output tree.
 * We number a whole level, then descend to each child, in order,
 * and number the level recursively.  This insures that a whole
 * level is contiguous in the output.
 */

extern void
numtree(struct node *p)
{
	struct node *q;
	struct node *ick;

	q = p;
	while (q) {
		if (q->n_next) {
			/*
			 * I'm not sure why, but this comes up sometimes.
			 * We just free the "icky node" and continue.
			 * I wish I knew the cause of this...  It does not
			 * seem to be fatal or result in any strangeness
			 * in the output table.
			 */
			if (! q->n_val) { /* && (q->n_flag == N_CHILD)) { */
				ick = q->n_next;
				q->n_next = q->n_next->n_next;
				free(ick);
			}
		}
/*
 * Don't number result nodes - they'll get hoisted!  Empty nodes still
 * get numbered.
 */
		if (q->n_flag != N_RESULT)
			q->n_num = numnode++;
		else
			q->n_num = (-1);
		q = q->n_next;
	}
	q = p;
	while (q) {
		switch (q->n_flag) {
		case N_CHILD:
			numtree(q->n_what.n_child);
			break;
/*
 * EMPTY nodes have no children.  With RESULT nodes, we're "there".
 */
		case N_EMPTY:
		case N_RESULT:
			break;
		default:
			fprintf(stderr, gettxt("kbdcomp:59",
"Internal error - unknown node type %d\n"), q->n_flag);
			exit(1);
			break;
		}
		q = q->n_next;
	}
	q = p;
	while (q) {
		switch (q->n_flag) {
		case N_CHILD:
			q->n_node = q->n_what.n_child->n_num;
			break;
		case N_EMPTY:
		case N_RESULT:
			q->n_node = 0;
			break;
		default:
			fprintf(stderr, gettxt("kbdcomp:60",
"Internal error - unknown node type(2) %d\n"), q->n_flag);
			exit(1);
		}
		q = q->n_next;
	}
}
