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