util.c

操作系统源代码

/* util.c: Utility routines for bc. */

/*  This file is part of bc written for MINIX.
    Copyright (C) 1991, 1992 Free Software Foundation, Inc.

    This program 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 2 of the License , or
    (at your option) any later version.

    This program 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 this program; see the file COPYING.  If not, write to
    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.

    You may contact the author by:
       e-mail:  [e-mail]
      us-mail:  Philip A. Nelson
                Computer Science Department, 9062
                Western Washington University
                Bellingham, WA 98226-9062
       
*************************************************************************/


#include "bcdefs.h"
#ifndef VARARGS
#include <stdarg.h>
#else
#include <varargs.h>
#endif
#include "global.h"
#include "proto.h"


/* strcopyof mallocs new memory and copies a string to to the new
   memory. */

char *
strcopyof (str)
     char *str;
{
  char *temp;

  temp = (char *) bc_malloc (strlen (str)+1);
  return (strcpy (temp,str));
}


/* nextarg adds another value to the list of arguments. */

arg_list *
nextarg (args, val)
     arg_list *args;
     char val;
{ arg_list *temp;

  temp = (arg_list *) bc_malloc (sizeof (arg_list));
  temp->av_name = val;
  temp->next = args;
 
  return (temp);
}


/* For generate, we must produce a string in the form
    "val,val,...,val".  We also need a couple of static variables
   for retaining old generated strings.  It also uses a recursive
   function that builds the string. */

static char *arglist1 = NULL, *arglist2 = NULL;


/* make_arg_str does the actual construction of the argument string.
   ARGS is the pointer to the list and LEN is the maximum number of
   characters needed.  1 char is the minimum needed. COMMAS tells
   if each number should be seperated by commas.*/

_PROTOTYPE (static char *make_arg_str, (arg_list *args, int len, int commas));

static char *
make_arg_str (args, len, commas)
      arg_list *args;
      int len;
      int commas;
{
  char *temp;
  char sval[20];

  /* Recursive call. */
  if (args != NULL)
    temp = make_arg_str (args->next, len+11, commas);
  else
    {
      temp = (char *) bc_malloc (len);
      *temp = 0;
      return temp;
    }

  /* Add the current number to the end of the string. */
  if (len != 1 && commas) 
    sprintf (sval, "%d,", args->av_name);
  else
    sprintf (sval, "%d", args->av_name);
  temp = strcat (temp, sval);
  return (temp);
}

char *
arg_str (args, commas)
     arg_list *args;
     int commas;
{
  if (arglist2 != NULL) 
    free (arglist2);
  arglist2 = arglist1;
  arglist1 = make_arg_str (args, 1, commas);
  return (arglist1);
}


/* free_args frees an argument list ARGS. */

void
free_args (args)
      arg_list *args;
{ 
  arg_list *temp;
 
  temp = args;
  while (temp != NULL)
    {
      args = args->next;
      free (temp);
      temp = args;
    }
}


/* Check for valid parameter (PARAMS) and auto (AUTOS) lists.
   There must be no duplicates any where.  Also, this is where
   warnings are generated for array parameters. */

void
check_params ( params, autos )
     arg_list *params, *autos;
{
  arg_list *tmp1, *tmp2;

  /* Check for duplicate parameters. */
  if (params != NULL)
    {
      tmp1 = params;
      while (tmp1 != NULL)
	{
	  tmp2 = tmp1->next;
	  while (tmp2 != NULL)
	    {
	      if (tmp2->av_name == tmp1->av_name) 
		yyerror ("duplicate parameter names");
	      tmp2 = tmp2->next;
	    }
	  if (tmp1->av_name < 0)
	    warn ("Array parameter");
	  tmp1 = tmp1->next;
	}
    }

  /* Check for duplicate autos. */
  if (autos != NULL)
    {
      tmp1 = autos;
      while (tmp1 != NULL)
	{
	  tmp2 = tmp1->next;
	  while (tmp2 != NULL)
	    {
	      if (tmp2->av_name == tmp1->av_name) 
		yyerror ("duplicate auto variable names");
	      tmp2 = tmp2->next;
	    }
	  tmp1 = tmp1->next;
	}
    }

  /* Check for duplicate between parameters and autos. */
  if ((params != NULL) && (autos != NULL))
    {
      tmp1 = params;
      while (tmp1 != NULL)
	{
	  tmp2 = autos;
	  while (tmp2 != NULL)
	    {
	      if (tmp2->av_name == tmp1->av_name) 
		yyerror ("variable in both parameter and auto lists");
	      tmp2 = tmp2->next;
	    }
	  tmp1 = tmp1->next;
	}
    }
}


/* Initialize the code generator the parser. */

void
init_gen ()
{
  /* Get things ready. */
  break_label = 0;
  continue_label = 0;
  next_label  = 1;
  out_count = 2;
  if (compile_only) 
    printf ("@i");
  else
    init_load ();
  had_error = FALSE;
  did_gen = FALSE;
}


/* generate code STR for the machine. */

void
generate (str)
      char *str;
{
  did_gen = TRUE;
  if (compile_only)
    {
      printf ("%s",str);
      out_count += strlen(str);
      if (out_count > 60)
	{
	  printf ("\n");
	  out_count = 0;
	}
    }
  else
    load_code (str);
}


/* Execute the current code as loaded. */

void
run_code()
{
  /* If no compile errors run the current code. */
  if (!had_error && did_gen)
    {
      if (compile_only)
	{
	  printf ("@r\n"); 
	  out_count = 0;
	}
      else
	execute ();
    }

  /* Reinitialize the code generation and machine. */
  if (did_gen)
    init_gen();
  else
    had_error = FALSE;
}


/* Output routines: Write a character CH to the standard output.
   It keeps track of the number of characters output and may
   break the output with a "\<cr>". */

void
out_char (ch)
     char ch;
{
  if (ch == '\n')
    {
      out_col = 0;
      putchar ('\n');
    }
  else
    {
      out_col++;
      if (out_col == 70)
	{
	  putchar ('\\');
	  putchar ('\n');
	  out_col = 1;
	}
      putchar (ch);
    }
}


/* The following are "Symbol Table" routines for the parser. */

/*  find_id returns a pointer to node in TREE that has the correct
    ID.  If there is no node in TREE with ID, NULL is returned. */

id_rec *
find_id (tree, id)
     id_rec *tree;
     char   *id;
{
  int cmp_result;
  
  /* Check for an empty tree. */
  if (tree == NULL)
    return NULL;

  /* Recursively search the tree. */
  cmp_result = strcmp (id, tree->id);
  if (cmp_result == 0)
    return tree;  /* This is the item. */
  else if (cmp_result < 0)
    return find_id (tree->left, id);
  else
    return find_id (tree->right, id);  
}


/* insert_id_rec inserts a NEW_ID rec into the tree whose ROOT is
   provided.  insert_id_rec returns TRUE if the tree height from
   ROOT down is increased otherwise it returns FALSE.  This is a
   recursive balanced binary tree insertion algorithm. */

int insert_id_rec (root, new_id)
     id_rec **root;
     id_rec *new_id;
{
  id_rec *A, *B;

  /* If root is NULL, this where it is to be inserted. */
  if (*root == NULL)
    {
      *root = new_id;
      new_id->left = NULL;
      new_id->right = NULL;
      new_id->balance = 0;
      return (TRUE);
    }

  /* We need to search for a leaf. */
  if (strcmp (new_id->id, (*root)->id) < 0)
    {
      /* Insert it on the left. */
      if (insert_id_rec (&((*root)->left), new_id))
	{
	  /* The height increased. */
	  (*root)->balance --;
	  
      switch ((*root)->balance)
	{
	case  0:  /* no height increase. */
	  return (FALSE);
	case -1:  /* height increase. */
	  return (FALSE);
	case -2:  /* we need to do a rebalancing act. */
	  A = *root;
	  B = (*root)->left;
	  if (B->balance <= 0)
	    {
	      /* Single Rotate. */
	      A->left = B->right;
	      B->right = A;
	      *root = B;
	      A->balance = 0;
	      B->balance = 0;
	    }
	  else
	    {
	      /* Double Rotate. */
	      *root = B->right;
	      B->right = (*root)->left;
	      A->left = (*root)->right;
	      (*root)->left = B;
	      (*root)->right = A;
	      switch ((*root)->balance)
		{
		case -1:
		  A->balance = 1;
		  B->balance = 0;
		  break;
		case  0:
		  A->balance = 0;
		  B->balance = 0;
		  break;
		case  1:
		  A->balance = 0;
		  B->balance = -1;
		  break;
		}