lib/typerb.c

   1 /* RB-tree */
   2
   3 /*
   4  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 /*
  29  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
  30  *
  31  * Permission to use, copy, modify, and distribute this software for any
  32  * purpose with or without fee is hereby granted, provided that the above
  33  * copyright notice and this permission notice appear in all copies.
  34  *
  35  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  36  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  37  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  38  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  39  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  40  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  41  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  42  */
  43
  44 #ifdef HAVE_CONFIG_H
  45 #include "config.h"
  46 #endif
  47
  48 #include <string.h>
  49 #include "typerb.h"
  50
  51 #define RB_BLACK        0
  52 #define RB_RED          1
  53
  54 #define rb_entry                typed_rb_entry
  55 #define rbt_tree                typed_rb_root
  56
  57 #define RBE_LEFT(_rbe)          (_rbe)->rbt_left
  58 #define RBE_RIGHT(_rbe)         (_rbe)->rbt_right
  59 #define RBE_PARENT(_rbe)        (_rbe)->rbt_parent
  60 #define RBE_COLOR(_rbe)         (_rbe)->rbt_color
  61
  62 #define RBH_ROOT(_rbt)          (_rbt)->rbt_root
  63
  64 static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
  65 {
  66         RBE_PARENT(rbe) = parent;
  67         RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
  68         RBE_COLOR(rbe) = RB_RED;
  69 }
  70
  71 static inline void rbe_set_blackred(struct rb_entry *black,
  72                                     struct rb_entry *red)
  73 {
  74         RBE_COLOR(black) = RB_BLACK;
  75         RBE_COLOR(red) = RB_RED;
  76 }
  77
  78 static inline void rbe_rotate_left(struct rbt_tree *rbt, struct rb_entry *rbe)
  79 {
  80         struct rb_entry *parent;
  81         struct rb_entry *tmp;
  82
  83         tmp = RBE_RIGHT(rbe);
  84         RBE_RIGHT(rbe) = RBE_LEFT(tmp);
  85         if (RBE_RIGHT(rbe) != NULL)
  86                 RBE_PARENT(RBE_LEFT(tmp)) = rbe;
  87
  88         parent = RBE_PARENT(rbe);
  89         RBE_PARENT(tmp) = parent;
  90         if (parent != NULL) {
  91                 if (rbe == RBE_LEFT(parent))
  92                         RBE_LEFT(parent) = tmp;
  93                 else
  94                         RBE_RIGHT(parent) = tmp;
  95         } else
  96                 RBH_ROOT(rbt) = tmp;
  97
  98         RBE_LEFT(tmp) = rbe;
  99         RBE_PARENT(rbe) = tmp;
 100 }
 101
 102 static inline void rbe_rotate_right(struct rbt_tree *rbt, struct rb_entry *rbe)
 103 {
 104         struct rb_entry *parent;
 105         struct rb_entry *tmp;
 106
 107         tmp = RBE_LEFT(rbe);
 108         RBE_LEFT(rbe) = RBE_RIGHT(tmp);
 109         if (RBE_LEFT(rbe) != NULL)
 110                 RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
 111
 112         parent = RBE_PARENT(rbe);
 113         RBE_PARENT(tmp) = parent;
 114         if (parent != NULL) {
 115                 if (rbe == RBE_LEFT(parent))
 116                         RBE_LEFT(parent) = tmp;
 117                 else
 118                         RBE_RIGHT(parent) = tmp;
 119         } else
 120                 RBH_ROOT(rbt) = tmp;
 121
 122         RBE_RIGHT(tmp) = rbe;
 123         RBE_PARENT(rbe) = tmp;
 124 }
 125
 126 static inline void rbe_insert_color(struct rbt_tree *rbt, struct rb_entry *rbe)
 127 {
 128         struct rb_entry *parent, *gparent, *tmp;
 129
 130         rbt->count++;
 131
 132         while ((parent = RBE_PARENT(rbe)) != NULL
 133                && RBE_COLOR(parent) == RB_RED) {
 134                 gparent = RBE_PARENT(parent);
 135
 136                 if (parent == RBE_LEFT(gparent)) {
 137                         tmp = RBE_RIGHT(gparent);
 138                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 139                                 RBE_COLOR(tmp) = RB_BLACK;
 140                                 rbe_set_blackred(parent, gparent);
 141                                 rbe = gparent;
 142                                 continue;
 143                         }
 144
 145                         if (RBE_RIGHT(parent) == rbe) {
 146                                 rbe_rotate_left(rbt, parent);
 147                                 tmp = parent;
 148                                 parent = rbe;
 149                                 rbe = tmp;
 150                         }
 151
 152                         rbe_set_blackred(parent, gparent);
 153                         rbe_rotate_right(rbt, gparent);
 154                 } else {
 155                         tmp = RBE_LEFT(gparent);
 156                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 157                                 RBE_COLOR(tmp) = RB_BLACK;
 158                                 rbe_set_blackred(parent, gparent);
 159                                 rbe = gparent;
 160                                 continue;
 161                         }
 162
 163                         if (RBE_LEFT(parent) == rbe) {
 164                                 rbe_rotate_right(rbt, parent);
 165                                 tmp = parent;
 166                                 parent = rbe;
 167                                 rbe = tmp;
 168                         }
 169
 170                         rbe_set_blackred(parent, gparent);
 171                         rbe_rotate_left(rbt, gparent);
 172                 }
 173         }
 174
 175         RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
 176 }
 177
 178 static inline void rbe_remove_color(struct rbt_tree *rbt,
 179                                     struct rb_entry *parent,
 180                                     struct rb_entry *rbe)
 181 {
 182         struct rb_entry *tmp;
 183
 184         while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
 185                && rbe != RBH_ROOT(rbt) && parent) {
 186                 if (RBE_LEFT(parent) == rbe) {
 187                         tmp = RBE_RIGHT(parent);
 188                         if (RBE_COLOR(tmp) == RB_RED) {
 189                                 rbe_set_blackred(tmp, parent);
 190                                 rbe_rotate_left(rbt, parent);
 191                                 tmp = RBE_RIGHT(parent);
 192                         }
 193                         if ((RBE_LEFT(tmp) == NULL
 194                              || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
 195                             && (RBE_RIGHT(tmp) == NULL
 196                                 || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 197                                 RBE_COLOR(tmp) = RB_RED;
 198                                 rbe = parent;
 199                                 parent = RBE_PARENT(rbe);
 200                         } else {
 201                                 if (RBE_RIGHT(tmp) == NULL
 202                                     || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
 203                                         struct rb_entry *oleft;
 204
 205                                         oleft = RBE_LEFT(tmp);
 206                                         if (oleft != NULL)
 207                                                 RBE_COLOR(oleft) = RB_BLACK;
 208
 209                                         RBE_COLOR(tmp) = RB_RED;
 210                                         rbe_rotate_right(rbt, tmp);
 211                                         tmp = RBE_RIGHT(parent);
 212                                 }
 213
 214                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 215                                 RBE_COLOR(parent) = RB_BLACK;
 216                                 if (RBE_RIGHT(tmp))
 217                                         RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
 218
 219                                 rbe_rotate_left(rbt, parent);
 220                                 rbe = RBH_ROOT(rbt);
 221                                 break;
 222                         }
 223                 } else {
 224                         tmp = RBE_LEFT(parent);
 225                         if (RBE_COLOR(tmp) == RB_RED) {
 226                                 rbe_set_blackred(tmp, parent);
 227                                 rbe_rotate_right(rbt, parent);
 228                                 tmp = RBE_LEFT(parent);
 229                         }
 230
 231                         if ((RBE_LEFT(tmp) == NULL
 232                              || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
 233                             && (RBE_RIGHT(tmp) == NULL
 234                                 || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 235                                 RBE_COLOR(tmp) = RB_RED;
 236                                 rbe = parent;
 237                                 parent = RBE_PARENT(rbe);
 238                         } else {
 239                                 if (RBE_LEFT(tmp) == NULL
 240                                     || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
 241                                         struct rb_entry *oright;
 242
 243                                         oright = RBE_RIGHT(tmp);
 244                                         if (oright != NULL)
 245                                                 RBE_COLOR(oright) = RB_BLACK;
 246
 247                                         RBE_COLOR(tmp) = RB_RED;
 248                                         rbe_rotate_left(rbt, tmp);
 249                                         tmp = RBE_LEFT(parent);
 250                                 }
 251
 252                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 253                                 RBE_COLOR(parent) = RB_BLACK;
 254                                 if (RBE_LEFT(tmp) != NULL)
 255                                         RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
 256
 257                                 rbe_rotate_right(rbt, parent);
 258                                 rbe = RBH_ROOT(rbt);
 259                                 break;
 260                         }
 261                 }
 262         }
 263
 264         if (rbe != NULL)
 265                 RBE_COLOR(rbe) = RB_BLACK;
 266 }
 267
 268 static inline struct rb_entry *
 269 rbe_remove(struct rbt_tree *rbt, struct rb_entry *rbe)
 270 {
 271         struct rb_entry *child, *parent, *old = rbe;
 272         unsigned int color;
 273
 274         if (RBE_LEFT(rbe) == NULL)
 275                 child = RBE_RIGHT(rbe);
 276         else if (RBE_RIGHT(rbe) == NULL)
 277                 child = RBE_LEFT(rbe);
 278         else {
 279                 struct rb_entry *tmp;
 280
 281                 rbe = RBE_RIGHT(rbe);
 282                 while ((tmp = RBE_LEFT(rbe)) != NULL)
 283                         rbe = tmp;
 284
 285                 child = RBE_RIGHT(rbe);
 286                 parent = RBE_PARENT(rbe);
 287                 color = RBE_COLOR(rbe);
 288                 if (child != NULL)
 289                         RBE_PARENT(child) = parent;
 290                 if (parent != NULL) {
 291                         if (RBE_LEFT(parent) == rbe)
 292                                 RBE_LEFT(parent) = child;
 293                         else
 294                                 RBE_RIGHT(parent) = child;
 295                 } else
 296                         RBH_ROOT(rbt) = child;
 297                 if (RBE_PARENT(rbe) == old)
 298                         parent = rbe;
 299                 *rbe = *old;
 300
 301                 tmp = RBE_PARENT(old);
 302                 if (tmp != NULL) {
 303                         if (RBE_LEFT(tmp) == old)
 304                                 RBE_LEFT(tmp) = rbe;
 305                         else
 306                                 RBE_RIGHT(tmp) = rbe;
 307                 } else
 308                         RBH_ROOT(rbt) = rbe;
 309
 310                 RBE_PARENT(RBE_LEFT(old)) = rbe;
 311                 if (RBE_RIGHT(old))
 312                         RBE_PARENT(RBE_RIGHT(old)) = rbe;
 313
 314                 goto color;
 315         }
 316
 317         parent = RBE_PARENT(rbe);
 318         color = RBE_COLOR(rbe);
 319
 320         if (child != NULL)
 321                 RBE_PARENT(child) = parent;
 322         if (parent != NULL) {
 323                 if (RBE_LEFT(parent) == rbe)
 324                         RBE_LEFT(parent) = child;
 325                 else
 326                         RBE_RIGHT(parent) = child;
 327         } else
 328                 RBH_ROOT(rbt) = child;
 329 color:
 330         if (color == RB_BLACK)
 331                 rbe_remove_color(rbt, parent, child);
 332
 333         rbt->count--;
 334         memset(old, 0, sizeof(*old));
 335         return (old);
 336 }
 337
 338 struct typed_rb_entry *typed_rb_remove(struct rbt_tree *rbt,
 339                                        struct rb_entry *rbe)
 340 {
 341         return rbe_remove(rbt, rbe);
 342 }
 343
 344 struct typed_rb_entry *typed_rb_insert(struct rbt_tree *rbt,
 345                 struct rb_entry *rbe, int (*cmpfn)(
 346                         const struct typed_rb_entry *a,
 347                         const struct typed_rb_entry *b))
 348 {
 349         struct rb_entry *tmp;
 350         struct rb_entry *parent = NULL;
 351         int comp = 0;
 352
 353         tmp = RBH_ROOT(rbt);
 354         while (tmp != NULL) {
 355                 parent = tmp;
 356
 357                 comp = cmpfn(rbe, tmp);
 358                 if (comp < 0)
 359                         tmp = RBE_LEFT(tmp);
 360                 else if (comp > 0)
 361                         tmp = RBE_RIGHT(tmp);
 362                 else
 363                         return tmp;
 364         }
 365
 366         rbe_set(rbe, parent);
 367
 368         if (parent != NULL) {
 369                 if (comp < 0)
 370                         RBE_LEFT(parent) = rbe;
 371                 else
 372                         RBE_RIGHT(parent) = rbe;
 373         } else
 374                 RBH_ROOT(rbt) = rbe;
 375
 376         rbe_insert_color(rbt, rbe);
 377
 378         return NULL;
 379 }
 380
 381 /* Finds the node with the same key as elm */
 382 const struct rb_entry *typed_rb_find(const struct rbt_tree *rbt,
 383                 const struct rb_entry *key,
 384                 int (*cmpfn)(
 385                         const struct typed_rb_entry *a,
 386                         const struct typed_rb_entry *b))
 387 {
 388         const struct rb_entry *tmp = RBH_ROOT(rbt);
 389         int comp;
 390
 391         while (tmp != NULL) {
 392                 comp = cmpfn(key, tmp);
 393                 if (comp < 0)
 394                         tmp = RBE_LEFT(tmp);
 395                 else if (comp > 0)
 396                         tmp = RBE_RIGHT(tmp);
 397                 else
 398                         return tmp;
 399         }
 400
 401         return NULL;
 402 }
 403
 404 const struct rb_entry *typed_rb_find_gteq(const struct rbt_tree *rbt,
 405                 const struct rb_entry *key,
 406                 int (*cmpfn)(
 407                         const struct typed_rb_entry *a,
 408                         const struct typed_rb_entry *b))
 409 {
 410         const struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
 411         int comp;
 412
 413         while (tmp != NULL) {
 414                 comp = cmpfn(key, tmp);
 415                 if (comp < 0) {
 416                         best = tmp;
 417                         tmp = RBE_LEFT(tmp);
 418                 } else if (comp > 0)
 419                         tmp = RBE_RIGHT(tmp);
 420                 else
 421                         return tmp;
 422         }
 423
 424         return best;
 425 }
 426
 427 const struct rb_entry *typed_rb_find_lt(const struct rbt_tree *rbt,
 428                 const struct rb_entry *key,
 429                 int (*cmpfn)(
 430                         const struct typed_rb_entry *a,
 431                         const struct typed_rb_entry *b))
 432 {
 433         const struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
 434         int comp;
 435
 436         while (tmp != NULL) {
 437                 comp = cmpfn(key, tmp);
 438                 if (comp <= 0)
 439                         tmp = RBE_LEFT(tmp);
 440                 else {
 441                         best = tmp;
 442                         tmp = RBE_RIGHT(tmp);
 443                 }
 444         }
 445
 446         return best;
 447 }
 448
 449 struct rb_entry *typed_rb_next(const struct rb_entry *rbe_const)
 450 {
 451         struct rb_entry *rbe = (struct rb_entry *)rbe_const;
 452
 453         if (RBE_RIGHT(rbe) != NULL) {
 454                 rbe = RBE_RIGHT(rbe);
 455                 while (RBE_LEFT(rbe) != NULL)
 456                         rbe = RBE_LEFT(rbe);
 457         } else {
 458                 if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 459                         rbe = RBE_PARENT(rbe);
 460                 else {
 461                         while (RBE_PARENT(rbe)
 462                                && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 463                                 rbe = RBE_PARENT(rbe);
 464                         rbe = RBE_PARENT(rbe);
 465                 }
 466         }
 467
 468         return rbe;
 469 }
 470
 471 struct rb_entry *typed_rb_prev(const struct rb_entry *rbe_const)
 472 {
 473         struct rb_entry *rbe = (struct rb_entry *)rbe_const;
 474
 475         if (RBE_LEFT(rbe)) {
 476                 rbe = RBE_LEFT(rbe);
 477                 while (RBE_RIGHT(rbe))
 478                         rbe = RBE_RIGHT(rbe);
 479         } else {
 480                 if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 481                         rbe = RBE_PARENT(rbe);
 482                 else {
 483                         while (RBE_PARENT(rbe)
 484                                && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 485                                 rbe = RBE_PARENT(rbe);
 486                         rbe = RBE_PARENT(rbe);
 487                 }
 488         }
 489
 490         return rbe;
 491 }
 492
 493 struct rb_entry *typed_rb_min(const struct rbt_tree *rbt)
 494 {
 495         struct rb_entry *rbe = RBH_ROOT(rbt);
 496         struct rb_entry *parent = NULL;
 497
 498         while (rbe != NULL) {
 499                 parent = rbe;
 500                 rbe = RBE_LEFT(rbe);
 501         }
 502
 503         return parent;
 504 }
 505
 506 struct rb_entry *typed_rb_max(const struct rbt_tree *rbt)
 507 {
 508         struct rb_entry *rbe = RBH_ROOT(rbt);
 509         struct rb_entry *parent = NULL;
 510
 511         while (rbe != NULL) {
 512                 parent = rbe;
 513                 rbe = RBE_RIGHT(rbe);
 514         }
 515
 516         return parent;
 517 }
 518
 519 bool typed_rb_member(const struct typed_rb_root *rbt,
 520                      const struct typed_rb_entry *rbe)
 521 {
 522         while (rbe->rbt_parent)
 523                 rbe = rbe->rbt_parent;
 524         return rbe == rbt->rbt_root;
 525 }