/*
 *                      ***************
 *                      * X R F 2 . C *
 *                      ***************
 *
 * This file contains the identifier tree and reference list management
 * things. It uses a simple binary tree to store the identifiers for
 * lookup and later sorted printing. Each node in the id tree has a
 * pointer to the id string, left and right links and pointers to the
 * beginning and end of the linked list of reference nodes for that
 * id. Only the root of the tree is global, it is used by the sorted
 * index printing function 'prtree'.
 *
 * Version V1.3          9-May-80
 * Version V1.4		10-Jul-80 MM	Bummed code
 * Version V1.5		23-Jul-80 MM	Redid storage code
 * Version V1.6		23-Dec-80 RBD	Fixed bug in myalloc()
 */

#include <stdio.h>
#include "xrf.h"


















/*
 * Tree search and insertion. This function returns a pointer to
 * the new node if created. This may require some head scratching
 * (I had to!). Look particularly at the significance of the pointer
 * that is returned and how it is used by the recursive caller. If
 * you want more, read "Algorithms + Data Structures = Programs"
 * by Niklaus Wirth (Prentice Hall ISBN 0-13-022418-9) Chapter 4.
 *
 * It searches through the tree for a match to the supplied id (*kp).
 * If it is found, a new reference node is linked into the list for
 * that id. If no match is found, a new is node is inserted into the
 * tree and appropriately initialized, including a first reference
 * node.
 *
 */

struct idt *search(kp, link)            /* Function "search" */
struct idt *link;                       /* Pointer to id node in tree */
char *kp;                               /* Pointer to key string */
   {
   register struct idt *l;              /* Fast tree pointer */
   register struct ref *r;              /* Fast list pointer */
   register int cond;                   /* Condition from strcmp */
   struct ref *newref();		/* Make reference function */
   char *myalloc(); 

   if (debug) {printf("xrf: begin search\n");}
   l = link;                            /* Copy link into register */
   if(l == NULL)                        /* Not found, insert new id node */
      {
      l = (struct idt *)myalloc(sizeof(struct idt)); /* Make new ident node */
      l->keyp = myalloc(strlen(kp)+1);	/* Get string space */
                                        /* Fill in pointer to ... */
      strcpy(l->keyp, kp);              /* ... stashed key string */
      l->left = l->right = NULL;        /* No children */
      l->first = l->last = newref();    /* Attach it to the id node */
	if (debug) {printf("xrf: node insertion complete\n");}
      }
   else if((cond = strcmp(kp, l->keyp)) == 0) /* Match if true */
      {
	if (debug) {printf("xrf: found another reference at %d\n",lineno);}
      r = newref();			/* Get a new ref. node */
      l->last->next = r;		/* Hook new node into the list */
      l->last = r;
      }
   else if(cond < 0) {                    /* Look left */
	if (debug) {printf("xrf: looking left\n");}
      l->left = search(kp, l->left);
   } else {                                 /* Look right */
	if (debug) {printf("xrf: looking right\n");}
      l->right = search(kp, l->right);
   }
   return(l);
}


/*
 * Initialize a line number referece
 */

static struct ref *
newref()
{
   char *myalloc();
   register struct ref *r;

   if (debug) {printf("xrf: initializing line %d reference\n",lineno);}
   r = (struct ref *)myalloc(sizeof(struct ref)); /* Make a reference node */
   r->lno = lineno;                     /* Fill in line no. of ref. */
   r->next = NULL;                      /* This is the end for now */
   return(r);				/* Return pointer to the node */
}

/*
 * Storage allocation:
 *
 * my_free		Free byte pointer in local buffer
 * my_left		Number of bytes left in local buffer
 * my_link		Link of free space buffers (from malloc())
 *
 * If space can be gotten locally, get it.  If not, request a "large"
 * chunk of memory and update my_free, my_left.
 *
 * My_link links chunks from monitor, myfree() returns them (called
 * at a new input file).
 */

struct my_alloc {
	struct my_alloc	*my_next;
};

static struct my_alloc	*my_link	= NULL;
static char		*my_free	= NULL;
static int		my_left		= 0;

char *myalloc(amount)
int		amount;
/*
 * Allocate amount bytes.
 */
{
	register char	*new;
	register int	needed;
	char		*malloc();

	needed = (amount + 1) & ~1;  /* Round up to a word bound */
	if (needed > my_left) {
		/*
		 * Gotta get storage
		 */
		if ((my_free = malloc(512)) == NULL) {
			quit();
		}
		my_left = 512 - (sizeof (struct my_alloc));
		((struct my_alloc *)my_free)->my_next = my_link;
		my_link = (struct my_alloc *)my_free;
		my_free += sizeof (struct my_alloc);
	}
	my_left -= needed;
	if (my_left < 0) {
		fprintf(stderr,"Trying to get too much: %d\n", needed);
		exit(-1);
	}
	new = my_free;
	my_free += needed;
	return(new);
}

myfree()
/*
 * Return all storage to the pool
 */
{
	register struct my_alloc	*link;
	register struct my_alloc	*next;

	next = my_link;
	while ((link = next) != NULL) {
		next = link->my_next;
		free(link);
	}
	my_link = NULL;
	my_free = NULL;
	my_left = 0;
}











/*
 * 'quit' handles dynamic memory deficit. (Sounds like U.S. Government!).
 * It issues a polite message to the user, marks the list file for delete
 * and exits to RSX.
 *
 */

quit()
   {
   puts("Not enough memory space, sorry.\n");
   fclose(lst);
   unlink(lst_name);
   exit(1);
   }