lib/libc/stdlib/tdelete.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 <stdbool.h>
  32 #include <stdlib.h>
  33
  34 #include "tsearch_path.h"
  35
  36 /*
  37  * Makes a step to the left along the binary search tree. This step is
  38  * also saved, so it can be replayed while rebalancing.
  39 */
  40 #define GO_LEFT() do {                                                  \
  41         if ((*leaf)->balance == 0 ||                                    \
  42             ((*leaf)->balance < 0 && (*leaf)->rlink->balance == 0)) {   \
  43                 /*                                                      \
  44                  * If we reach a node that is balanced, or has a child  \
  45                  * in the opposite direction that is balanced, we know  \
  46                  * that we won't need to perform any rotations above    \
  47                  * this point. In this case rotations are always        \
  48                  * capable of keeping the subtree in balance. Make      \
  49                  * this the base node and reset the path.               \
  50                  */                                                     \
  51                 base = leaf;                                            \
  52                 path_init(&path);                                       \
  53         }                                                               \
  54         path_taking_left(&path);                                        \
  55         leaf = &(*leaf)->llink;                                         \
  56 } while (0)
  57
  58 /* Makes a step to the right along the binary search tree. */
  59 #define GO_RIGHT() do {                                                 \
  60         if ((*leaf)->balance == 0 ||                                    \
  61             ((*leaf)->balance > 0 && (*leaf)->llink->balance == 0)) {   \
  62                 base = leaf;                                            \
  63                 path_init(&path);                                       \
  64         }                                                               \
  65         result = &(*leaf)->key;                                         \
  66         path_taking_right(&path);                                       \
  67         leaf = &(*leaf)->rlink;                                         \
  68 } while (0)
  69
  70 void *
  71 tdelete(const void *restrict key, void **restrict rootp,
  72     int (*compar)(const void *, const void *))
  73 {
  74         struct path path;
  75         node_t *root, **base, **leaf, *old, **n, *x, *y, *z;
  76         void *result;
  77         int cmp;
  78
  79         /* POSIX requires that tdelete() returns NULL if rootp is NULL. */
  80         if (rootp == NULL)
  81                 return (NULL);
  82         root = *rootp;
  83
  84         /*
  85          * Find the leaf that needs to be removed. Return if we cannot
  86          * find an existing entry. Keep track of the path that is taken
  87          * to get to the node, as we will need it to adjust the
  88          * balances.
  89          */
  90         result = (void *)1;
  91         path_init(&path);
  92         base = &root;
  93         leaf = &root;
  94         for (;;) {
  95                 if (*leaf == NULL)
  96                         return (NULL);
  97                 cmp = compar(key, (*leaf)->key);
  98                 if (cmp < 0) {
  99                         result = &(*leaf)->key;
 100                         GO_LEFT();
 101                 } else if (cmp > 0) {
 102                         result = &(*leaf)->key;
 103                         GO_RIGHT();
 104                 } else {
 105                         break;
 106                 }
 107         }
 108
 109         /* Found a matching key in the tree. Remove the node. */
 110         if ((*leaf)->llink == NULL) {
 111                 /* Node has no left children. Replace by its right subtree. */
 112                 old = *leaf;
 113                 *leaf = old->rlink;
 114                 free(old);
 115         } else {
 116                 /*
 117                  * Node has left children. Replace this node's key by
 118                  * its predecessor's and remove that node instead.
 119                  */
 120                 void **keyp = &(*leaf)->key;
 121                 GO_LEFT();
 122                 while ((*leaf)->rlink != NULL)
 123                         GO_RIGHT();
 124                 old = *leaf;
 125                 *keyp = old->key;
 126                 *leaf = old->llink;
 127                 free(old);
 128         }
 129
 130         /*
 131          * Walk along the same path a second time and adjust the
 132          * balances. Though this code looks similar to the rebalancing
 133          * performed in tsearch(), it is not identical. We now also need
 134          * to consider the case of outward imbalance in the right-right
 135          * and left-left case that only exists when deleting. Hence the
 136          * duplication of code.
 137          */
 138         for (n = base; n != leaf;) {
 139                 if (path_took_left(&path)) {
 140                         x = *n;
 141                         if (x->balance < 0) {
 142                                 y = x->rlink;
 143                                 if (y->balance > 0) {
 144                                         /* Right-left case. */
 145                                         z = y->llink;
 146                                         x->rlink = z->llink;
 147                                         z->llink = x;
 148                                         y->llink = z->rlink;
 149                                         z->rlink = y;
 150                                         *n = z;
 151
 152                                         x->balance = z->balance < 0 ? 1 : 0;
 153                                         y->balance = z->balance > 0 ? -1 : 0;
 154                                         z->balance = 0;
 155                                 } else {
 156                                         /* Right-right case. */
 157                                         x->rlink = y->llink;
 158                                         y->llink = x;
 159                                         *n = y;
 160
 161                                         if (y->balance < 0) {
 162                                                 x->balance = 0;
 163                                                 y->balance = 0;
 164                                         } else {
 165                                                 x->balance = -1;
 166                                                 y->balance = 1;
 167                                         }
 168                                 }
 169                         } else {
 170                                 --x->balance;
 171                         }
 172                         n = &x->llink;
 173                 } else {
 174                         x = *n;
 175                         if (x->balance > 0) {
 176                                 y = x->llink;
 177                                 if (y->balance < 0) {
 178                                         /* Left-right case. */
 179                                         z = y->rlink;
 180                                         y->rlink = z->llink;
 181                                         z->llink = y;
 182                                         x->llink = z->rlink;
 183                                         z->rlink = x;
 184                                         *n = z;
 185
 186                                         x->balance = z->balance > 0 ? -1 : 0;
 187                                         y->balance = z->balance < 0 ? 1 : 0;
 188                                         z->balance = 0;
 189                                 } else {
 190                                         /* Left-left case. */
 191                                         x->llink = y->rlink;
 192                                         y->rlink = x;
 193                                         *n = y;
 194
 195                                         if (y->balance > 0) {
 196                                                 x->balance = 0;
 197                                                 y->balance = 0;
 198                                         } else {
 199                                                 x->balance = 1;
 200                                                 y->balance = -1;
 201                                         }
 202                                 }
 203                         } else {
 204                                 ++x->balance;
 205                         }
 206                         n = &x->rlink;
 207                 }
 208         }
 209
 210         /* Return the parent of the old entry. */
 211         *rootp = root;
 212         return (result);
 213 }