lib/libc/stdlib/tsearch.c

   1 /*-
   2  * Copyright (c) 2015 Nuxi, https://nuxi.nl/
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  23  * SUCH DAMAGE.
  24  */
  25
  26 #include <sys/cdefs.h>
  27 __FBSDID("$FreeBSD$");
  28
  29 #define _SEARCH_PRIVATE
  30 #include <search.h>
  31 #include <stdlib.h>
  32
  33 #include "tsearch_path.h"
  34
  35 posix_tnode *
  36 tsearch(const void *key, posix_tnode **rootp,
  37     int (*compar)(const void *, const void *))
  38 {
  39         struct path path;
  40         posix_tnode **leaf, *result, *n, *x, *y, *z;
  41         int cmp;
  42
  43         /* POSIX requires that tsearch() returns NULL if rootp is NULL. */
  44         if (rootp == NULL)
  45                 return (NULL);
  46
  47         /*
  48          * Find the leaf where the new key needs to be inserted. Return
  49          * if we've found an existing entry. Keep track of the path that
  50          * is taken to get to the node, as we will need it to adjust the
  51          * balances.
  52         */
  53         path_init(&path);
  54         leaf = rootp;
  55         while (*leaf != NULL) {
  56                 if ((*leaf)->balance != 0) {
  57                         /*
  58                          * If we reach a node that has a non-zero
  59                          * balance on the way, we know that we won't
  60                          * need to perform any rotations above this
  61                          * point. In this case rotations are always
  62                          * capable of keeping the subtree in balance.
  63                          * Make this the root node and reset the path.
  64                          */
  65                         rootp = leaf;
  66                         path_init(&path);
  67                 }
  68                 cmp = compar(key, (*leaf)->key);
  69                 if (cmp < 0) {
  70                         path_taking_left(&path);
  71                         leaf = &(*leaf)->llink;
  72                 } else if (cmp > 0) {
  73                         path_taking_right(&path);
  74                         leaf = &(*leaf)->rlink;
  75                 } else {
  76                         return (*leaf);
  77                 }
  78         }
  79
  80         /* Did not find a matching key in the tree. Insert a new node. */
  81         result = *leaf = malloc(sizeof(**leaf));
  82         if (result == NULL)
  83                 return (NULL);
  84         result->key = (void *)key;
  85         result->llink = NULL;
  86         result->rlink = NULL;
  87         result->balance = 0;
  88
  89         /*
  90          * Walk along the same path a second time and adjust the
  91          * balances. Except for the first node, all of these nodes must
  92          * have a balance of zero, meaning that these nodes will not get
  93          * out of balance.
  94         */
  95         for (n = *rootp; n != *leaf;) {
  96                 if (path_took_left(&path)) {
  97                         n->balance += 1;
  98                         n = n->llink;
  99                 } else {
 100                         n->balance -= 1;
 101                         n = n->rlink;
 102                 }
 103         }
 104
 105         /*
 106          * Adjusting the balances may have pushed the balance of the
 107          * root node out of range. Perform a rotation to bring the
 108          * balance back in range.
 109          */
 110         x = *rootp;
 111         if (x->balance > 1) {
 112                 y = x->llink;
 113                 if (y->balance < 0) {
 114                         /*
 115                          * Left-right case.
 116                          *
 117                          *         x
 118                          *        / \            z
 119                          *       y   D          / \
 120                          *      / \     -->    y   x
 121                          *     A   z          /|   |\
 122                          *        / \        A B   C D
 123                          *       B   C
 124                          */
 125                         z = y->rlink;
 126                         y->rlink = z->llink;
 127                         z->llink = y;
 128                         x->llink = z->rlink;
 129                         z->rlink = x;
 130                         *rootp = z;
 131
 132                         x->balance = z->balance > 0 ? -1 : 0;
 133                         y->balance = z->balance < 0 ? 1 : 0;
 134                         z->balance = 0;
 135                 } else {
 136                         /*
 137                          * Left-left case.
 138                          *
 139                          *        x           y
 140                          *       / \         / \
 141                          *      y   C  -->  A   x
 142                          *     / \             / \
 143                          *    A   B           B   C
 144                          */
 145                         x->llink = y->rlink;
 146                         y->rlink = x;
 147                         *rootp = y;
 148
 149                         x->balance = 0;
 150                         y->balance = 0;
 151                 }
 152         } else if (x->balance < -1) {
 153                 y = x->rlink;
 154                 if (y->balance > 0) {
 155                         /*
 156                          * Right-left case.
 157                          *
 158                          *       x
 159                          *      / \              z
 160                          *     A   y            / \
 161                          *        / \   -->    x   y
 162                          *       z   D        /|   |\
 163                          *      / \          A B   C D
 164                          *     B   C
 165                          */
 166                         posix_tnode *z = y->llink;
 167                         x->rlink = z->llink;
 168                         z->llink = x;
 169                         y->llink = z->rlink;
 170                         z->rlink = y;
 171                         *rootp = z;
 172
 173                         x->balance = z->balance < 0 ? 1 : 0;
 174                         y->balance = z->balance > 0 ? -1 : 0;
 175                         z->balance = 0;
 176                 } else {
 177                         /*
 178                          * Right-right case.
 179                          *
 180                          *       x               y
 181                          *      / \             / \
 182                          *     A   y    -->    x   C
 183                          *        / \         / \
 184                          *       B   C       A   B
 185                          */
 186                         x->rlink = y->llink;
 187                         y->llink = x;
 188                         *rootp = y;
 189
 190                         x->balance = 0;
 191                         y->balance = 0;
 192                 }
 193         }
 194
 195         /* Return the new entry. */
 196         return (result);
 197 }