trees.c

Go to the documentation of this file.

/* Copyright 1991 Digital Equipment Corporation.
** All Rights Reserved.
*****************************************************************/

#include "defs.h"

long intcmp(long a,long b)
{
#ifdef CMPDBG
    printf("intcmp a = %ld b = %ld a - b = %ld\n", a ,b  , a - b);
#endif
       return a - b;
}


long is_int(char **s, long *len, long *sgn)
{
  char *sint; /* Ptr to first non-zero digit */
  char *stmp; /* Scratchpad for string ptr */
#ifdef CMPDBG
  printf("is_int *s = %s\n",*s);
#endif
  /*
    { register char *p= *s;
    register char c= *p;
    if(c>'0' && c<='9' && *(p+1)==0) return TRUE;
    }
  */
  
  stmp=(*s);
  if ((*sgn=(*stmp=='-'))) { 
    stmp++;
    if (!*stmp)
      {
#ifdef CMPDBG
    printf("is_int = FALSE\n");
#endif
    return   FALSE;
      }
  }
  if (!*stmp)
    { 
#ifdef CMPDBG
      printf("is_int = FALSE\n");
#endif
      return FALSE; /* 6.10 */
    }
  while (*stmp=='0') stmp++;
  sint=stmp;
  while (*stmp) {
    if (*stmp<'0' || *stmp>'9') 
      {
#ifdef CMPDBG
    printf("is_int = FALSE\n"); 
#endif
    return FALSE;
      }
    stmp++;
  }
  *len=stmp-sint;
  *s=sint;
#ifdef CMPDBG
  printf("is_int = TRUE *len = %ld *sgn = %ld *s = %s\n",*len,*sgn,*s);
#endif
  return TRUE;
}

long featcmp(char *str1,char *str2)
{
  long len1,len2,sgn1,sgn2;
  char *s1,*s2;

  if(str1==str2)
    return 0;
  
  /* if (*str1==0 && *str2==0) return 0; "" bug is unaffected -- PVR 23.2.94 */

  if(*(str1+1)==0 && *(str2+1)==0)
    return *str1 - *str2;
  
  
  s1=str1; /* Local copies of the pointers */
  s2=str2;

  if (is_int(&s1,&len1,&sgn1)) {
    if (is_int(&s2,&len2,&sgn2)) {
      if (sgn1!=sgn2) return (sgn2-sgn1); /* Check signs first */
      if (len1!=len2) return (len1-len2); /* Then check lengths */
      return strcmp(s1,s2); /* Use strcmp only if same sign and length */
    }
    else
      return -1;
  }
  else {
    if (is_int(&s2,&len2,&sgn2))
      return 1;
    else
      return strcmp(s1,s2);
  }
}

char *heap_ncopy_string(char *s,int n)
{
  char *p;
  
  if (s==one || s==two) return s;

  p=(char *)heap_alloc(n+1);
  strncpy(p,s,n);
  p[n]='\0';
  
  return p;
}

char *heap_copy_string(char *s)
{ return heap_ncopy_string(s,strlen(s)); }

char *stack_copy_string(char *s)
{
  char *p;
  
  if (s==one || s==two) return s;

  p=(char *)stack_alloc(strlen(s)+1);
  strcpy(p,s);
  
  return p;
}

ptr_node general_insert(long comp,char *keystr,ptr_node *tree,GENERIC info,long heapflag,long copystr,long bkflag)
{
  long cmp;
  ptr_node result;
  long to_do=TRUE;

  
  do {
    if (*tree==NULL) {
      if (bkflag==1) push_ptr_value(int_ptr,(GENERIC *)tree);
      else if (bkflag==2) push_ptr_value_global(int_ptr,(GENERIC *)tree);
      *tree = (heapflag==HEAP) ? HEAP_ALLOC(node): STACK_ALLOC(node);
      result= *tree;
      (*tree)->key = copystr ? heap_copy_string(keystr) : keystr;
      (*tree)->left=NULL;
      (*tree)->right=NULL;
      (*tree)->data=info;
      to_do=FALSE;
    }
    else {
      if (comp == INTCMP)
    cmp = intcmp((long)keystr,(long) (*tree)->key);
      else if (comp == FEATCMP)
    cmp = featcmp(keystr,(*tree)->key);
      else if (comp == STRCMP)
    cmp = strcmp(keystr,(*tree)->key);
      else
    Errorline("Bad comp in general_insert.\n");

      if (cmp<0)
    tree=(&((*tree)->left));
      else
    if (cmp==0) {
          if (bkflag)
            Errorline("attempt to overwrite an existing feature; ignored.\n");
          else
        (*tree)->data=info;
      result= *tree;
      to_do=FALSE;
    }
    else
      tree=(&((*tree)->right));
    }
  } while (to_do);
  
  return result;
}

void heap_insert_copystr(char *keystr,ptr_node *tree,GENERIC info)
{
  (void)general_insert(FEATCMP,keystr,tree,info,HEAP,TRUE,0L);
}

void stack_insert_copystr(char *keystr,ptr_node *tree,GENERIC info)
{

  (void)general_insert(FEATCMP,keystr,tree,info,STACK,TRUE,0L);
}

ptr_node heap_insert(long comp,char *keystr,ptr_node *tree,GENERIC info)
{

  return general_insert(comp,keystr,tree,info,HEAP,FALSE,0L);
}

ptr_node stack_insert(long comp,char *keystr,ptr_node *tree,GENERIC info)
{

  return general_insert(comp,keystr,tree,info,STACK,FALSE,0L);
}

ptr_node bk_stack_insert(long comp,char *keystr,ptr_node *tree,GENERIC info)
{

  return general_insert(comp,keystr,tree,info,STACK,FALSE,1L);
}

ptr_node bk2_stack_insert(long comp,char *keystr,ptr_node *tree,GENERIC info)
{

  return general_insert(comp,keystr,tree,info,STACK,FALSE,2L);
}

ptr_node find(long comp,char *keystr,ptr_node tree)
{
  ptr_node result;
  long cmp;
  long to_do=TRUE;

  /*
    if(comp==strcmp)
    printf("%s ",keystr);
    */
    
  do {
    if (tree==NULL) {
      result=NULL;
      to_do=FALSE;
    }
    else {
      if (comp == INTCMP)
    cmp = intcmp((long)keystr,(long) (tree)->key);
      else if (comp == FEATCMP)
    cmp = featcmp(keystr,(tree)->key);
      else if (comp == STRCMP)
    cmp = strcmp(keystr,(tree)->key);
      else
    Errorline("Bad comp in general_insert.\n");

      if (cmp<0)
    tree=tree->left;
      else
    if (cmp==0) {
      result=tree;
      to_do=FALSE;
    }
      else
    tree=tree->right;
    }
  } while (to_do);


  /* RM: Jan 27 1993 
    if(comp==strcmp)
    printf("Find: '%s' -> %x\n",keystr,result);
    */
  
  return result;
}

ptr_node find_data(GENERIC p,ptr_node t)
{
  ptr_node r=NULL;

  if(t) 
    if(t->data==p)
      r=t;
    else {
      r=find_data(p,t->left);
      if(r==NULL)
    r=find_data(p,t->right);
    }
  
  return r;
}

void delete_attr(char *s,ptr_node *n)
{
  long cmp;
  ptr_node new,r;

  if (*n) {
    cmp=featcmp(s,(*n)->key);
    if (cmp<0)
      delete_attr(s,&((*n)->left));
    else if (cmp>0)
    delete_attr(s,&((*n)->right));
    else if ((*n)->left) {
      if ((*n)->right) {
        r=(*n)->right;
        new=heap_insert(FEATCMP,r->key,&((*n)->left),r->data);
        new->left=r->left;
        new->right=r->right;
        *n = (*n) -> left;
      }
      else
        *n = (*n)->left;
    }
    else
      *n = (*n)->right;
  }
}