/* ctt.c -- Character Transition Tree Operations

This file is part of STAR, the Saturn Macro Assembler.

   STAR is not distributed by the Free Software Foundation. Do not ask
them for a copy or how to obtain new releases. Instead, send e-mail to
the address below. STAR is merely covered by the GNU General Public
License.

Please send your comments, ideas, and bug reports to
Jan Brittenson <bson@ai.mit.edu>

*/


/* Copyright (C) 1991 Jan Brittenson.

   STAR is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 1, or (at your option) any
later version.

   STAR is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.

   You should have received a copy of the GNU General Public License
along with STAR; see the file COPYING. If not, to obtain a copy, write
to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139,
USA, or send e-mail to bson@ai.mit.edu. */


#include <stdio.h>
#include "star.h"
#include "symbols.h"
#include "ctt.h"


/* Allocate ctt root */
static CTT_ROOT *ctt_alloc()
{
  CTT_ROOT *ctt_tmp;
  extern char *malloc();

  
  if(!(ctt_tmp = (CTT_ROOT *) malloc(sizeof(CTT_ROOT))))
    fatal("Cannot allocate CTT root, %d bytes", sizeof(CTT_ROOT));

  bclear((char *) ctt_tmp, sizeof(CTT_ROOT));

  return(ctt_tmp);
}


/* Allocate ctt node */
static CTT_NODE *ctt_node_alloc()
{
  CTT_NODE *ctt_tmp;
  extern char *malloc();

  
  if(!(ctt_tmp = (CTT_NODE *) malloc(sizeof(CTT_NODE))))
    fatal("Cannot allocate CTT node, %d bytes", sizeof(CTT_NODE));

  bclear((char *) ctt_tmp, sizeof(CTT_NODE));

  return(ctt_tmp);
}


/* Create new ctt root */
CTT_ROOT *ctt_new()
{
  return(ctt_alloc());
}


/* Walk characters */
struct sstruct *ctt_find(ctt_root, cpp)
  CTT_ROOT *ctt_root;
  char **cpp;
{
  CTT_NODE *node, *last_match;
  char *str = *cpp, *save = *cpp, *last_match_str;


  if(!ctt_root || !cpp)
    return((struct sstruct *) 0);

  /* Walk */
  for(last_match = NULL, last_match_str = str,
      node = ctt_root->ctt_node[toupper(*str)];
      node; )
    {
      /* Does the current character match the current node? */
      if(node->ctt_c == toupper(*str))
	{
	  /* Yes, do we have a binding here? */
	  if(node->ctt_binding)

	    /* Yes, then remember this node */
	    last_match = node;

	  /* Follow match link and move to next char */
	  last_match_str = str++;
	  node = node->ctt_match;
	}
      else
	/* No, follow fail link */
	node = node->ctt_next;
    }
  

  /* Return last match point */
  if(last_match)
    {
      /* Make sure we're not stuck with the initial
       * part of a symbol name, such as "sin" in "sing".
       * The latter should be interpreted as sing, rather
       * sin(g). The exception is when the operator name isn't
       * a valid symbol name, e.g. "0x40".
       */
      if(issym(*last_match_str) && issym(last_match_str[1]) &&
	 isisym(*save))
      
	return((struct sstruct *) 0);

      *cpp = last_match_str+1;
      return(last_match->ctt_binding);
    }
  else
    {
      *cpp = save;
      return((SYM_NODE *) 0);
    }
}


/* Convert string to virgin match list */
static CTT_NODE *ctt_make_match(str, binding)
  char *str;
  SYM_NODE *binding;
{
  CTT_NODE *start_node, *node, *new_node;

  start_node = ctt_node_alloc();

  for(node = start_node, start_node->ctt_c = *str++; *str; node = new_node)
    {
      new_node = ctt_node_alloc();

      new_node->ctt_c = *str++;
      node->ctt_match = new_node;
    }

  node->ctt_binding = binding;

  return(start_node);
}


/* Add string to tree */
void ctt_add(ctt_root, str, binding)
  CTT_ROOT *ctt_root;
  char *str;
  SYM_NODE *binding;
{
  CTT_NODE *node;

  if(!ctt_root)
    return;

  
  /* Walk until we're at the link point */
  if(!(node = ctt_root->ctt_node[*str]))
    {
      /* Virgin tree, initialize */
      ctt_root->ctt_node[*str] = ctt_make_match(str, binding);
      return;
    }

  /* If we drop out of the loop, the string cannot be added */
  while(*str)
    {
      /* Does the current character match the current node? */
      if(node->ctt_c == *str)
	{
	  /* Yes, do we have a match link? */
	  if(!node->ctt_match)
	    {
	      /* No - link up here */
	      if(*++str)
		node->ctt_match = ctt_make_match(str, binding);
	      else
		node->ctt_binding = binding;

	      return;
	    }

	  /* Yes, follow it and move to next char.
	   * See if end of string */
	  if(!*++str)
	    {
	      /* This means we're entering a substring, so we
	       * just rebind the node.
	       */
	      node->ctt_binding = binding;
	      return;
	    }
	  node = node->ctt_match;
	}
      else
	/* No, follow fail link */
	if(node->ctt_next)
	  node = node->ctt_next;
	else
	  {
	    /* No fail link - link up here */
	    node->ctt_next = ctt_make_match(str, binding);
	    return;
	  }
    }
}
