trees.c File Reference

Go to the source code of this file.

Functions
long	intcmp (long a, long b)
long	is_int (char **s, long *len, long *sgn)
long	featcmp (char *str1, char *str2)
char *	heap_ncopy_string (char *s, int n)
char *	heap_copy_string (char *s)
char *	stack_copy_string (char *s)
ptr_node	general_insert (long comp, char *keystr, ptr_node *tree, GENERIC info, long heapflag, long copystr, long bkflag)
void	heap_insert_copystr (char *keystr, ptr_node *tree, GENERIC info)
void	stack_insert_copystr (char *keystr, ptr_node *tree, GENERIC info)
ptr_node	heap_insert (long comp, char *keystr, ptr_node *tree, GENERIC info)
ptr_node	stack_insert (long comp, char *keystr, ptr_node *tree, GENERIC info)
ptr_node	bk_stack_insert (long comp, char *keystr, ptr_node *tree, GENERIC info)
ptr_node	bk2_stack_insert (long comp, char *keystr, ptr_node *tree, GENERIC info)
ptr_node	find (long comp, char *keystr, ptr_node tree)
ptr_node	find_data (GENERIC p, ptr_node t)
void	delete_attr (char *s, ptr_node *n)

Function Documentation

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

Definition at line 327 of file trees.c.

References FALSE, general_insert(), and STACK.

{

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

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

Definition at line 309 of file trees.c.

References FALSE, general_insert(), and STACK.

{

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

void delete_attr	(	char *	s,
		ptr_node *	n
	)

Definition at line 466 of file trees.c.

References wl_node::data, featcmp(), FEATCMP, heap_insert(), wl_node::key, wl_node::left, and wl_node::right.

{
  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;
  }
}

long featcmp	(	char *	str1,
		char *	str2
	)

Definition at line 89 of file trees.c.

References is_int().

{
  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);
  }
}

ptr_node find	(	long	comp,
		char *	keystr,
		ptr_node	tree
	)

Definition at line 341 of file trees.c.

References Errorline(), FALSE, featcmp(), FEATCMP, intcmp(), INTCMP, wl_node::left, NULL, wl_node::right, STRCMP, and TRUE.

{
  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
	)

Definition at line 399 of file trees.c.

References wl_node::data, wl_node::left, NULL, and wl_node::right.

{
  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;
}

ptr_node general_insert	(	long	comp,
		char *	keystr,
		ptr_node *	tree,
		GENERIC	info,
		long	heapflag,
		long	copystr,
		long	bkflag
	)

Definition at line 184 of file trees.c.

References Errorline(), FALSE, featcmp(), FEATCMP, HEAP, HEAP_ALLOC, heap_copy_string(), int_ptr, intcmp(), INTCMP, wl_node::key, NULL, push_ptr_value(), push_ptr_value_global(), STACK_ALLOC, STRCMP, and TRUE.

{
  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;
}

char* heap_copy_string

(

char *

s

)

Definition at line 147 of file trees.c.

References heap_ncopy_string().

{ return heap_ncopy_string(s,strlen(s)); }

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

Definition at line 276 of file trees.c.

References FALSE, general_insert(), and HEAP.

{

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

void heap_insert_copystr	(	char *	keystr,
		ptr_node *	tree,
		GENERIC	info
	)

Definition at line 245 of file trees.c.

References FEATCMP, general_insert(), HEAP, and TRUE.

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

char* heap_ncopy_string	(	char *	s,
		int	n
	)

Definition at line 128 of file trees.c.

References heap_alloc(), one, and two.

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

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

long intcmp	(	long	a,
		long	b
	)

Definition at line 12 of file trees.c.

{
#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
	)

Definition at line 27 of file trees.c.

References FALSE, and TRUE.

{
  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;
}

char* stack_copy_string

(

char *

s

)

Definition at line 155 of file trees.c.

References one, stack_alloc(), and two.

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

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

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

Definition at line 291 of file trees.c.

References FALSE, general_insert(), and STACK.

{

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

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

Definition at line 260 of file trees.c.

References FEATCMP, general_insert(), STACK, and TRUE.

{

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