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