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 void *
  36 tsearch(const void *key, void **rootp,
  37     int (*compar)(const void *, const void *))
  38 {
  39         struct path path;
  40         node_t *root, **base, **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                 root = *rootp;
  47
  48         /*
  49          * Find the leaf where the new key needs to be inserted. Return
  50          * if we've found an existing entry. Keep track of the path that
  51          * is taken to get to the node, as we will need it to adjust the
  52          * balances.
  53         */
  54         path_init(&path);
  55         base = &root;
  56         leaf = &root;
  57         while (*leaf != NULL) {
  58                 if ((*leaf)->balance != 0) {
  59                         /*
  60                          * If we reach a node that has a non-zero
  61                          * balance on the way, we know that we won't
  62                          * need to perform any rotations above this
  63                          * point. In this case rotations are always
  64                          * capable of keeping the subtree in balance.
  65                          * Make this the base node and reset the path.
  66                          */
  67                         base = leaf;
  68                         path_init(&path);
  69                 }
  70                 cmp = compar(key, (*leaf)->key);
  71                 if (cmp < 0) {
  72                         path_taking_left(&path);
  73                         leaf = &(*leaf)->llink;
  74                 } else if (cmp > 0) {
  75                         path_taking_right(&path);
  76                         leaf = &(*leaf)->rlink;
  77                 } else {
  78                         return (&(*leaf)->key);
  79                 }
  80         }
  81
  82         /* Did not find a matching key in the tree. Insert a new node. */
  83         result = *leaf = malloc(sizeof(**leaf));
  84         if (result == NULL)
  85                 return (NULL);
  86         result->key = (void *)key;
  87         result->llink = NULL;
  88         result->rlink = NULL;
  89         result->balance = 0;
  90
  91         /*
  92          * Walk along the same path a second time and adjust the
  93          * balances. Except for the first node, all of these nodes must
  94          * have a balance of zero, meaning that these nodes will not get
  95          * out of balance.
  96         */
  97         for (n = *base; n != *leaf;) {
  98                 if (path_took_left(&path)) {
  99                         n->balance += 1;
 100                         n = n->llink;
 101                 } else {
 102                         n->balance -= 1;
 103                         n = n->rlink;
 104                 }
 105         }
 106
 107         /*
 108          * Adjusting the balances may have pushed the balance of the
 109          * base node out of range. Perform a rotation to bring the
 110          * balance back in range.
 111          */
 112         x = *base;
 113         if (x->balance > 1) {
 114                 y = x->llink;
 115                 if (y->balance < 0) {
 116                         /*
 117                          * Left-right case.
 118                          *
 119                          *         x
 120                          *        / \            z
 121                          *       y   D          / \
 122                          *      / \     -->    y   x
 123                          *     A   z          /|   |\
 124                          *        / \        A B   C D
 125                          *       B   C
 126                          */
 127                         z = y->rlink;
 128                         y->rlink = z->llink;
 129                         z->llink = y;
 130                         x->llink = z->rlink;
 131                         z->rlink = x;
 132                         *base = z;
 133
 134                         x->balance = z->balance > 0 ? -1 : 0;
 135                         y->balance = z->balance < 0 ? 1 : 0;
 136                         z->balance = 0;
 137                 } else {
 138                         /*
 139                          * Left-left case.
 140                          *
 141                          *        x           y
 142                          *       / \         / \
 143                          *      y   C  -->  A   x
 144                          *     / \             / \
 145                          *    A   B           B   C
 146                          */
 147                         x->llink = y->rlink;
 148                         y->rlink = x;
 149                         *base = y;
 150
 151                         x->balance = 0;
 152                         y->balance = 0;
 153                 }
 154         } else if (x->balance < -1) {
 155                 y = x->rlink;
 156                 if (y->balance > 0) {
 157                         /*
 158                          * Right-left case.
 159                          *
 160                          *       x
 161                          *      / \              z
 162                          *     A   y            / \
 163                          *        / \   -->    x   y
 164                          *       z   D        /|   |\
 165                          *      / \          A B   C D
 166                          *     B   C
 167                          */
 168                         node_t *z = y->llink;
 169                         x->rlink = z->llink;
 170                         z->llink = x;
 171                         y->llink = z->rlink;
 172                         z->rlink = y;
 173                         *base = z;
 174
 175                         x->balance = z->balance < 0 ? 1 : 0;
 176                         y->balance = z->balance > 0 ? -1 : 0;
 177                         z->balance = 0;
 178                 } else {
 179                         /*
 180                          * Right-right case.
 181                          *
 182                          *       x               y
 183                          *      / \             / \
 184                          *     A   y    -->    x   C
 185                          *        / \         / \
 186                          *       B   C       A   B
 187                          */
 188                         x->rlink = y->llink;
 189                         y->llink = x;
 190                         *base = y;
 191
 192                         x->balance = 0;
 193                         y->balance = 0;
 194                 }
 195         }
 196
 197         /* Return the new entry. */
 198         *rootp = root;
 199         return (&result->key);
 200 }