gonzui

    1: /*      $OpenBSD: tsearch.c,v 1.7 2012/02/06 20:29:54 guenther Exp $ */
    2: 
    3: /*
    4:  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
    5:  * the AT&T man page says.
    6:  *
    7:  * The node_t structure is for internal use only, lint doesn't grok it.
    8:  *
    9:  * Written by reading the System V Interface Definition, not the code.
   10:  *
   11:  * Totally public domain.
   12:  */
   13: /*LINTLIBRARY*/
   14: 
   15: #include <search.h>
   16: #include <stdlib.h>
   17: 
   18: typedef struct node_t {
   19:     char          *key;
   20:     struct node_t *left, *right;
   21: } node;
   22: 
   23: /* find or insert datum into search tree */
   24: void *
   25: tsearch(const void *vkey, void **vrootp,
   26:     int (*compar)(const void *, const void *))
   27: {
   28:     node *q;
   29:     char *key = (char *)vkey;
   30:     node **rootp = (node **)vrootp;
   31: 
   32:     if (rootp == (struct node_t **)0)
   33:         return ((void *)0);
   34:     while (*rootp != (struct node_t *)0) {      /* Knuth's T1: */
   35:         int r;
   36: 
   37:         if ((r = (*compar)(key, (*rootp)->key)) == 0)  /* T2: */
   38:             return ((void *)*rootp);           /* we found it! */
   39:         rootp = (r < 0) ?
   40:             &(*rootp)->left :          /* T3: follow left branch */
   41:             &(*rootp)->right;          /* T4: follow right branch */
   42:     }
   43:     q = (node *) malloc(sizeof(node));  /* T5: key not found */
   44:     if (q != (struct node_t *)0) {      /* make new node */
   45:         *rootp = q;                    /* link new node to old */
   46:         q->key = key;                  /* initialize new node */
   47:         q->left = q->right = (struct node_t *)0;
   48:     }
   49:     return ((void *)q);
   50: }
   51: 
   52: /* delete node with given key */
   53: void *
   54: tdelete(const void *vkey, void **vrootp,
   55:     int (*compar)(const void *, const void *))
   56: {
   57:     node **rootp = (node **)vrootp;
   58:     char *key = (char *)vkey;
   59:     node *p = (node *)1;
   60:     node *q;
   61:     node *r;
   62:     int cmp;
   63: 
   64:     if (rootp == (struct node_t **)0 || *rootp == (struct node_t *)0)
   65:         return ((struct node_t *)0);
   66:     while ((cmp = (*compar)(key, (*rootp)->key)) != 0) {
   67:         p = *rootp;
   68:         rootp = (cmp < 0) ?
   69:             &(*rootp)->left :          /* follow left branch */
   70:             &(*rootp)->right;          /* follow right branch */
   71:         if (*rootp == (struct node_t *)0)
   72:             return ((void *)0);                /* key not found */
   73:     }
   74:     r = (*rootp)->right;                        /* D1: */
   75:     if ((q = (*rootp)->left) == (struct node_t *)0)     /* Left (struct node_t *)0? */
   76:         q = r;
   77:     else if (r != (struct node_t *)0) {         /* Right link is null? */
   78:         if (r->left == (struct node_t *)0) {   /* D2: Find successor */
   79:             r->left = q;
   80:             q = r;
   81:         } else {                       /* D3: Find (struct node_t *)0 link */
   82:             for (q = r->left; q->left != (struct node_t *)0; q = r->left)
   83:                 r = q;
   84:             r->left = q->right;
   85:             q->left = (*rootp)->left;
   86:             q->right = (*rootp)->right;
   87:         }
   88:     }
   89:     free((struct node_t *) *rootp);     /* D4: Free node */
   90:     *rootp = q;                         /* link parent to new node */
   91:     return(p);
   92: }
   93: 
   94: /* Walk the nodes of a tree */
   95: static void
   96: trecurse(node *root, void (*action)(const void *, VISIT, int), int level)
   97: {
   98:     if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
   99:         (*action)(root, leaf, level);
  100:     else {
  101:         (*action)(root, preorder, level);
  102:         if (root->left != (struct node_t *)0)
  103:             trecurse(root->left, action, level + 1);
  104:         (*action)(root, postorder, level);
  105:         if (root->right != (struct node_t *)0)
  106:             trecurse(root->right, action, level + 1);
  107:         (*action)(root, endorder, level);
  108:     }
  109: }
  110: 
  111: /* Walk the nodes of a tree */
  112: void
  113: twalk(const void *vroot, void (*action)(const void *, VISIT, int))
  114: {
  115:     node *root = (node *)vroot;
  116: 
  117:     if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0)
  118:         trecurse(root, action, 0);
  119: }