usr/src/lib/libbc/libc/gen/common/tsearch.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*      Copyright (c) 1984 AT&T */
  23 /*        All Rights Reserved   */
  24
  25 #pragma ident   "%Z%%M% %I%     %E% SMI"
  26
  27 /*LINTLIBRARY*/
  28 /*
  29  * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T.
  30  *
  31  *
  32  * The NODE * arguments are declared in the lint files as char *,
  33  * because the definition of NODE isn't available to the user.
  34  */
  35
  36 #include <search.h>
  37 #include <stdio.h>
  38 #include <malloc.h>
  39
  40 typedef char *POINTER;
  41 typedef struct node { POINTER key; struct node *llink, *rlink; } NODE;
  42
  43 /*
  44  * Find or insert key into search tree
  45  *
  46  * Arguments
  47  *      key:    Key to be located
  48  *      rootp:  Address of the root of the tree
  49  *      compar: Comparison function
  50  */
  51 NODE *
  52 tsearch(POINTER key, NODE **rootp, int (*compar)(POINTER, POINTER))
  53 {
  54         NODE *q;        /* New node if key not found */
  55
  56         if (rootp == NULL)
  57                 return (NULL);
  58         while (*rootp != NULL) {                        /* T1: */
  59                 int r = (*compar)(key, (*rootp)->key);  /* T2: */
  60                 if (r == 0)
  61                         return (*rootp);        /* Key found */
  62                 rootp = (r < 0) ?
  63                     &(*rootp)->llink :          /* T3: Take left branch */
  64                     &(*rootp)->rlink;           /* T4: Take right branch */
  65         }
  66         q = (NODE *) malloc(sizeof(NODE));      /* T5: Not found */
  67         if (q != NULL) {                        /* Allocate new node */
  68                 *rootp = q;                     /* Link new node to old */
  69                 q->key = key;                   /* Initialize new node */
  70                 q->llink = q->rlink = NULL;
  71         }
  72         return (q);
  73 }
  74
  75 /*
  76  * Delete node with key key
  77  *
  78  * Arguments
  79  *      key:    Key to be deleted
  80  *      rootp:  Address of the root of tree
  81  *      compar: Comparison function
  82  */
  83 NODE *
  84 tdelete(POINTER key, NODE **rootp, int (*compar)(POINTER, POINTER))
  85 {
  86         NODE *p;                /* Parent of node to be deleted */
  87         NODE *q;        /* Successor node */
  88         NODE *r;        /* Right son node */
  89         int ans;                /* Result of comparison */
  90
  91         if (rootp == NULL || (p = *rootp) == NULL)
  92                 return (NULL);
  93         while ((ans = (*compar)(key, (*rootp)->key)) != 0) {
  94                 p = *rootp;
  95                 rootp = (ans < 0) ?
  96                     &(*rootp)->llink :          /* Take left branch */
  97                     &(*rootp)->rlink;           /* Take right branch */
  98                 if (*rootp == NULL)
  99                         return (NULL);          /* Key not found */
 100         }
 101         r = (*rootp)->rlink;                    /* D1: */
 102         if ((q = (*rootp)->llink) == NULL)      /* Llink NULL? */
 103                 q = r;
 104         else if (r != NULL) {                   /* Rlink NULL? */
 105                 if (r->llink == NULL) {         /* D2: Find successor */
 106                         r->llink = q;
 107                         q = r;
 108                 } else {                        /* D3: Find NULL link */
 109                         for (q = r->llink; q->llink != NULL; q = r->llink)
 110                                 r = q;
 111                         r->llink = q->rlink;
 112                         q->llink = (*rootp)->llink;
 113                         q->rlink = (*rootp)->rlink;
 114                 }
 115         }
 116         free((POINTER) *rootp);         /* D4: Free node */
 117         *rootp = q;                     /* Link parent to replacement */
 118         return (p);
 119 }
 120
 121 static void     _twalk(NODE *, void (*)(NODE *, VISIT, int), int);
 122
 123 /*
 124  * Walk the nodes of a tree
 125  *
 126  * Arguments
 127  *      root:   Root of the tree to be walked
 128  *      action: Function to be called at each node
 129  */
 130 void
 131 twalk(NODE *root, void (*action)(NODE *, VISIT, int))
 132 {
 133
 134         if (root != NULL && action != NULL)
 135                 _twalk(root, action, 0);
 136 }
 137
 138 /*
 139  * Walk the nodes of a tree
 140  *
 141  * Arguments
 142  *      root:   Root of the tree to be walked
 143  *      action: Function to be called at each node
 144  */
 145 static void
 146 _twalk(NODE *root, void (*action)(NODE *, VISIT, int), int level)
 147 {
 148         if (root->llink == NULL && root->rlink == NULL)
 149                 (*action)(root, leaf, level);
 150         else {
 151                 (*action)(root, preorder, level);
 152                 if (root->llink != NULL)
 153                         _twalk(root->llink, action, level + 1);
 154                 (*action)(root, postorder, level);
 155                 if (root->rlink != NULL)
 156                         _twalk(root->rlink, action, level + 1);
 157                 (*action)(root, endorder, level);
 158         }
 159 }