4.3BSD - /usr/src/new/spms/src/lib/libtree/src/tree.c

   1: /* $Header$ */
   2: 
   3: /*
   4:  * Author: Peter J. Nicklin
   5:  */
   6: 
   7: /*
   8:  * tree() searchs for a key in a binary tree. If the search is
   9:  * unsuccessful a new node is added to the tree.
  10:  */
  11: #include "tree.h"
  12: #include "null.h"
  13: 
  14: TREE *
  15: tree(p, key)
  16:     TREE *p;            /* current node pointer */
  17:     char *key;          /* pointer to key */
  18: {
  19:     TREE *talloc();         /* allocate a binary tree node */
  20:     char *strsav();         /* save a string */
  21:     int comp;           /* compare key values */
  22:     int strcmp();           /* string comparison */
  23: 
  24:     if (p == NULL)
  25:         {           /* a new key has arrived */
  26:         if ((p = talloc()) == NULL ||
  27:             (p->key = strsav(key)) == NULL)
  28:             fatal("out of memory");
  29:         p->count = 1;
  30:         p->left = p->right = NULL;
  31:         }
  32:     else if ((comp = strcmp(key, p->key)) < 0)
  33:         p->left = tree(p->left, key);
  34:     else if (comp > 0)
  35:         p->right = tree(p->right, key);
  36:     else if (comp == 0)
  37:         p->count++;
  38:     return(p);
  39: }
  40: 
  41: 
  42: 
  43: /*
  44:  * talloc() allocates memory for a binary tree node.
  45:  */
  46: static TREE *
  47: talloc()
  48: {
  49:     char *malloc();         /* memory allocator */
  50: 
  51:     return((TREE *) malloc(sizeof(TREE)));
  52: }

Defined functions