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         path_taking_right(&path);                                       \
  66         leaf = &(*leaf)->rlink;                                         \
  67 } while (0)
  68
  69 void *
  70 tdelete(const void *restrict key, void **restrict rootp,
  71     int (*compar)(const void *, const void *))
  72 {
  73         struct path path;
  74         node_t *root, **base, **leaf, *old, **n, *x, *y, *z;
  75         void *result;
  76         int cmp;
  77
  78         /* POSIX requires that tdelete() returns NULL if rootp is NULL. */
  79         if (rootp == NULL)
  80                 return (NULL);
  81         root = *rootp;
  82
  83         /*
  84          * Find the leaf that needs to be removed. Return if we cannot
  85          * find an existing entry. Keep track of the path that is taken
  86          * to get to the node, as we will need it to adjust the
  87          * balances.
  88          */
  89         result = (void *)1;
  90         path_init(&path);
  91         base = &root;
  92         leaf = &root;
  93         for (;;) {
  94                 if (*leaf == NULL)
  95                         return (NULL);
  96                 cmp = compar(key, (*leaf)->key);
  97                 if (cmp < 0) {
  98                         result = &(*leaf)->key;
  99                         GO_LEFT();
 100                 } else if (cmp > 0) {
 101                         result = &(*leaf)->key;
 102                         GO_RIGHT();
 103                 } else {
 104                         break;
 105                 }
 106         }
 107
 108         /* Found a matching key in the tree. Remove the node. */
 109         if ((*leaf)->llink == NULL) {
 110                 /* Node has no left children. Replace by its right subtree. */
 111                 old = *leaf;
 112                 *leaf = old->rlink;
 113                 free(old);
 114         } else {
 115                 /*
 116                  * Node has left children. Replace this node's key by
 117                  * its predecessor's and remove that node instead.
 118                  */
 119                 void **keyp = &(*leaf)->key;
 120                 GO_LEFT();
 121                 while ((*leaf)->rlink != NULL)
 122                         GO_RIGHT();
 123                 old = *leaf;
 124                 *keyp = old->key;
 125                 *leaf = old->llink;
 126                 free(old);
 127         }
 128
 129         /*
 130          * Walk along the same path a second time and adjust the
 131          * balances. Though this code looks similar to the rebalancing
 132          * performed in tsearch(), it is not identical. We now also need
 133          * to consider the case of outward imbalance in the right-right
 134          * and left-left case that only exists when deleting. Hence the
 135          * duplication of code.
 136          */
 137         for (n = base; n != leaf;) {
 138                 if (path_took_left(&path)) {
 139                         x = *n;
 140                         if (x->balance < 0) {
 141                                 y = x->rlink;
 142                                 if (y->balance > 0) {
 143                                         /* Right-left case. */
 144                                         z = y->llink;
 145                                         x->rlink = z->llink;
 146                                         z->llink = x;
 147                                         y->llink = z->rlink;
 148                                         z->rlink = y;
 149                                         *n = z;
 150
 151                                         x->balance = z->balance < 0 ? 1 : 0;
 152                                         y->balance = z->balance > 0 ? -1 : 0;
 153                                         z->balance = 0;
 154                                 } else {
 155                                         /* Right-right case. */
 156                                         x->rlink = y->llink;
 157                                         y->llink = x;
 158                                         *n = y;
 159
 160                                         if (y->balance < 0) {
 161                                                 x->balance = 0;
 162                                                 y->balance = 0;
 163                                         } else {
 164                                                 x->balance = -1;
 165                                                 y->balance = 1;
 166                                         }
 167                                 }
 168                         } else {
 169                                 --x->balance;
 170                         }
 171                         n = &x->llink;
 172                 } else {
 173                         x = *n;
 174                         if (x->balance > 0) {
 175                                 y = x->llink;
 176                                 if (y->balance < 0) {
 177                                         /* Left-right case. */
 178                                         z = y->rlink;
 179                                         y->rlink = z->llink;
 180                                         z->llink = y;
 181                                         x->llink = z->rlink;
 182                                         z->rlink = x;
 183                                         *n = z;
 184
 185                                         x->balance = z->balance > 0 ? -1 : 0;
 186                                         y->balance = z->balance < 0 ? 1 : 0;
 187                                         z->balance = 0;
 188                                 } else {
 189                                         /* Left-left case. */
 190                                         x->llink = y->rlink;
 191                                         y->rlink = x;
 192                                         *n = y;
 193
 194                                         if (y->balance > 0) {
 195                                                 x->balance = 0;
 196                                                 y->balance = 0;
 197                                         } else {
 198                                                 x->balance = 1;
 199                                                 y->balance = -1;
 200                                         }
 201                                 }
 202                         } else {
 203                                 ++x->balance;
 204                         }
 205                         n = &x->rlink;
 206                 }
 207         }
 208
 209         /* Return the parent of the old entry. */
 210         *rootp = root;
 211         return (result);
 212 }