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