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