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 "typerb.h"
  49
  50 #define RB_BLACK        0
  51 #define RB_RED          1
  52
  53 #define rb_entry                typed_rb_entry
  54 #define rbt_tree                typed_rb_root
  55
  56 #define RBE_LEFT(_rbe)          (_rbe)->rbt_left
  57 #define RBE_RIGHT(_rbe)         (_rbe)->rbt_right
  58 #define RBE_PARENT(_rbe)        (_rbe)->rbt_parent
  59 #define RBE_COLOR(_rbe)         (_rbe)->rbt_color
  60
  61 #define RBH_ROOT(_rbt)          (_rbt)->rbt_root
  62
  63 static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
  64 {
  65         RBE_PARENT(rbe) = parent;
  66         RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
  67         RBE_COLOR(rbe) = RB_RED;
  68 }
  69
  70 static inline void rbe_set_blackred(struct rb_entry *black,
  71                                     struct rb_entry *red)
  72 {
  73         RBE_COLOR(black) = RB_BLACK;
  74         RBE_COLOR(red) = RB_RED;
  75 }
  76
  77 static inline void rbe_rotate_left(struct rbt_tree *rbt, struct rb_entry *rbe)
  78 {
  79         struct rb_entry *parent;
  80         struct rb_entry *tmp;
  81
  82         tmp = RBE_RIGHT(rbe);
  83         RBE_RIGHT(rbe) = RBE_LEFT(tmp);
  84         if (RBE_RIGHT(rbe) != NULL)
  85                 RBE_PARENT(RBE_LEFT(tmp)) = rbe;
  86
  87         parent = RBE_PARENT(rbe);
  88         RBE_PARENT(tmp) = parent;
  89         if (parent != NULL) {
  90                 if (rbe == RBE_LEFT(parent))
  91                         RBE_LEFT(parent) = tmp;
  92                 else
  93                         RBE_RIGHT(parent) = tmp;
  94         } else
  95                 RBH_ROOT(rbt) = tmp;
  96
  97         RBE_LEFT(tmp) = rbe;
  98         RBE_PARENT(rbe) = tmp;
  99 }
 100
 101 static inline void rbe_rotate_right(struct rbt_tree *rbt, struct rb_entry *rbe)
 102 {
 103         struct rb_entry *parent;
 104         struct rb_entry *tmp;
 105
 106         tmp = RBE_LEFT(rbe);
 107         RBE_LEFT(rbe) = RBE_RIGHT(tmp);
 108         if (RBE_LEFT(rbe) != NULL)
 109                 RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
 110
 111         parent = RBE_PARENT(rbe);
 112         RBE_PARENT(tmp) = parent;
 113         if (parent != NULL) {
 114                 if (rbe == RBE_LEFT(parent))
 115                         RBE_LEFT(parent) = tmp;
 116                 else
 117                         RBE_RIGHT(parent) = tmp;
 118         } else
 119                 RBH_ROOT(rbt) = tmp;
 120
 121         RBE_RIGHT(tmp) = rbe;
 122         RBE_PARENT(rbe) = tmp;
 123 }
 124
 125 static inline void rbe_insert_color(struct rbt_tree *rbt, struct rb_entry *rbe)
 126 {
 127         struct rb_entry *parent, *gparent, *tmp;
 128
 129         rbt->count++;
 130
 131         while ((parent = RBE_PARENT(rbe)) != NULL
 132                && RBE_COLOR(parent) == RB_RED) {
 133                 gparent = RBE_PARENT(parent);
 134
 135                 if (parent == RBE_LEFT(gparent)) {
 136                         tmp = RBE_RIGHT(gparent);
 137                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 138                                 RBE_COLOR(tmp) = RB_BLACK;
 139                                 rbe_set_blackred(parent, gparent);
 140                                 rbe = gparent;
 141                                 continue;
 142                         }
 143
 144                         if (RBE_RIGHT(parent) == rbe) {
 145                                 rbe_rotate_left(rbt, parent);
 146                                 tmp = parent;
 147                                 parent = rbe;
 148                                 rbe = tmp;
 149                         }
 150
 151                         rbe_set_blackred(parent, gparent);
 152                         rbe_rotate_right(rbt, gparent);
 153                 } else {
 154                         tmp = RBE_LEFT(gparent);
 155                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 156                                 RBE_COLOR(tmp) = RB_BLACK;
 157                                 rbe_set_blackred(parent, gparent);
 158                                 rbe = gparent;
 159                                 continue;
 160                         }
 161
 162                         if (RBE_LEFT(parent) == rbe) {
 163                                 rbe_rotate_right(rbt, parent);
 164                                 tmp = parent;
 165                                 parent = rbe;
 166                                 rbe = tmp;
 167                         }
 168
 169                         rbe_set_blackred(parent, gparent);
 170                         rbe_rotate_left(rbt, gparent);
 171                 }
 172         }
 173
 174         RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
 175 }
 176
 177 static inline void rbe_remove_color(struct rbt_tree *rbt,
 178                                     struct rb_entry *parent,
 179                                     struct rb_entry *rbe)
 180 {
 181         struct rb_entry *tmp;
 182
 183         while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
 184                && rbe != RBH_ROOT(rbt) && parent) {
 185                 if (RBE_LEFT(parent) == rbe) {
 186                         tmp = RBE_RIGHT(parent);
 187                         if (RBE_COLOR(tmp) == RB_RED) {
 188                                 rbe_set_blackred(tmp, parent);
 189                                 rbe_rotate_left(rbt, parent);
 190                                 tmp = RBE_RIGHT(parent);
 191                         }
 192                         if ((RBE_LEFT(tmp) == NULL
 193                              || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
 194                             && (RBE_RIGHT(tmp) == NULL
 195                                 || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 196                                 RBE_COLOR(tmp) = RB_RED;
 197                                 rbe = parent;
 198                                 parent = RBE_PARENT(rbe);
 199                         } else {
 200                                 if (RBE_RIGHT(tmp) == NULL
 201                                     || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
 202                                         struct rb_entry *oleft;
 203
 204                                         oleft = RBE_LEFT(tmp);
 205                                         if (oleft != NULL)
 206                                                 RBE_COLOR(oleft) = RB_BLACK;
 207
 208                                         RBE_COLOR(tmp) = RB_RED;
 209                                         rbe_rotate_right(rbt, tmp);
 210                                         tmp = RBE_RIGHT(parent);
 211                                 }
 212
 213                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 214                                 RBE_COLOR(parent) = RB_BLACK;
 215                                 if (RBE_RIGHT(tmp))
 216                                         RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
 217
 218                                 rbe_rotate_left(rbt, parent);
 219                                 rbe = RBH_ROOT(rbt);
 220                                 break;
 221                         }
 222                 } else {
 223                         tmp = RBE_LEFT(parent);
 224                         if (RBE_COLOR(tmp) == RB_RED) {
 225                                 rbe_set_blackred(tmp, parent);
 226                                 rbe_rotate_right(rbt, parent);
 227                                 tmp = RBE_LEFT(parent);
 228                         }
 229
 230                         if ((RBE_LEFT(tmp) == NULL
 231                              || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
 232                             && (RBE_RIGHT(tmp) == NULL
 233                                 || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 234                                 RBE_COLOR(tmp) = RB_RED;
 235                                 rbe = parent;
 236                                 parent = RBE_PARENT(rbe);
 237                         } else {
 238                                 if (RBE_LEFT(tmp) == NULL
 239                                     || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
 240                                         struct rb_entry *oright;
 241
 242                                         oright = RBE_RIGHT(tmp);
 243                                         if (oright != NULL)
 244                                                 RBE_COLOR(oright) = RB_BLACK;
 245
 246                                         RBE_COLOR(tmp) = RB_RED;
 247                                         rbe_rotate_left(rbt, tmp);
 248                                         tmp = RBE_LEFT(parent);
 249                                 }
 250
 251                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 252                                 RBE_COLOR(parent) = RB_BLACK;
 253                                 if (RBE_LEFT(tmp) != NULL)
 254                                         RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
 255
 256                                 rbe_rotate_right(rbt, parent);
 257                                 rbe = RBH_ROOT(rbt);
 258                                 break;
 259                         }
 260                 }
 261         }
 262
 263         if (rbe != NULL)
 264                 RBE_COLOR(rbe) = RB_BLACK;
 265 }
 266
 267 static inline struct rb_entry *
 268 rbe_remove(struct rbt_tree *rbt, struct rb_entry *rbe)
 269 {
 270         struct rb_entry *child, *parent, *old = rbe;
 271         unsigned int color;
 272
 273         if (RBE_LEFT(rbe) == NULL)
 274                 child = RBE_RIGHT(rbe);
 275         else if (RBE_RIGHT(rbe) == NULL)
 276                 child = RBE_LEFT(rbe);
 277         else {
 278                 struct rb_entry *tmp;
 279
 280                 rbe = RBE_RIGHT(rbe);
 281                 while ((tmp = RBE_LEFT(rbe)) != NULL)
 282                         rbe = tmp;
 283
 284                 child = RBE_RIGHT(rbe);
 285                 parent = RBE_PARENT(rbe);
 286                 color = RBE_COLOR(rbe);
 287                 if (child != NULL)
 288                         RBE_PARENT(child) = parent;
 289                 if (parent != NULL) {
 290                         if (RBE_LEFT(parent) == rbe)
 291                                 RBE_LEFT(parent) = child;
 292                         else
 293                                 RBE_RIGHT(parent) = child;
 294                 } else
 295                         RBH_ROOT(rbt) = child;
 296                 if (RBE_PARENT(rbe) == old)
 297                         parent = rbe;
 298                 *rbe = *old;
 299
 300                 tmp = RBE_PARENT(old);
 301                 if (tmp != NULL) {
 302                         if (RBE_LEFT(tmp) == old)
 303                                 RBE_LEFT(tmp) = rbe;
 304                         else
 305                                 RBE_RIGHT(tmp) = rbe;
 306                 } else
 307                         RBH_ROOT(rbt) = rbe;
 308
 309                 RBE_PARENT(RBE_LEFT(old)) = rbe;
 310                 if (RBE_RIGHT(old))
 311                         RBE_PARENT(RBE_RIGHT(old)) = rbe;
 312
 313                 goto color;
 314         }
 315
 316         parent = RBE_PARENT(rbe);
 317         color = RBE_COLOR(rbe);
 318
 319         if (child != NULL)
 320                 RBE_PARENT(child) = parent;
 321         if (parent != NULL) {
 322                 if (RBE_LEFT(parent) == rbe)
 323                         RBE_LEFT(parent) = child;
 324                 else
 325                         RBE_RIGHT(parent) = child;
 326         } else
 327                 RBH_ROOT(rbt) = child;
 328 color:
 329         if (color == RB_BLACK)
 330                 rbe_remove_color(rbt, parent, child);
 331
 332         rbt->count--;
 333         return (old);
 334 }
 335
 336 struct typed_rb_entry *typed_rb_remove(struct rbt_tree *rbt,
 337                                        struct rb_entry *rbe)
 338 {
 339         return rbe_remove(rbt, rbe);
 340 }
 341
 342 struct typed_rb_entry *typed_rb_insert(struct rbt_tree *rbt,
 343                 struct rb_entry *rbe, int (*cmpfn)(
 344                         const struct typed_rb_entry *a,
 345                         const struct typed_rb_entry *b))
 346 {
 347         struct rb_entry *tmp;
 348         struct rb_entry *parent = NULL;
 349         int comp = 0;
 350
 351         tmp = RBH_ROOT(rbt);
 352         while (tmp != NULL) {
 353                 parent = tmp;
 354
 355                 comp = cmpfn(rbe, tmp);
 356                 if (comp < 0)
 357                         tmp = RBE_LEFT(tmp);
 358                 else if (comp > 0)
 359                         tmp = RBE_RIGHT(tmp);
 360                 else
 361                         return tmp;
 362         }
 363
 364         rbe_set(rbe, parent);
 365
 366         if (parent != NULL) {
 367                 if (comp < 0)
 368                         RBE_LEFT(parent) = rbe;
 369                 else
 370                         RBE_RIGHT(parent) = rbe;
 371         } else
 372                 RBH_ROOT(rbt) = rbe;
 373
 374         rbe_insert_color(rbt, rbe);
 375
 376         return NULL;
 377 }
 378
 379 /* Finds the node with the same key as elm */
 380 struct rb_entry *typed_rb_find(struct rbt_tree *rbt, const struct rb_entry *key,
 381                 int (*cmpfn)(
 382                         const struct typed_rb_entry *a,
 383                         const struct typed_rb_entry *b))
 384 {
 385         struct rb_entry *tmp = RBH_ROOT(rbt);
 386         int comp;
 387
 388         while (tmp != NULL) {
 389                 comp = cmpfn(key, tmp);
 390                 if (comp < 0)
 391                         tmp = RBE_LEFT(tmp);
 392                 else if (comp > 0)
 393                         tmp = RBE_RIGHT(tmp);
 394                 else
 395                         return tmp;
 396         }
 397
 398         return NULL;
 399 }
 400
 401 struct rb_entry *typed_rb_find_gteq(struct rbt_tree *rbt,
 402                 const struct rb_entry *key,
 403                 int (*cmpfn)(
 404                         const struct typed_rb_entry *a,
 405                         const struct typed_rb_entry *b))
 406 {
 407         struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
 408         int comp;
 409
 410         while (tmp != NULL) {
 411                 comp = cmpfn(key, tmp);
 412                 if (comp < 0) {
 413                         best = tmp;
 414                         tmp = RBE_LEFT(tmp);
 415                 } else if (comp > 0)
 416                         tmp = RBE_RIGHT(tmp);
 417                 else
 418                         return tmp;
 419         }
 420
 421         return best;
 422 }
 423
 424 struct rb_entry *typed_rb_find_lt(struct rbt_tree *rbt,
 425                 const struct rb_entry *key,
 426                 int (*cmpfn)(
 427                         const struct typed_rb_entry *a,
 428                         const struct typed_rb_entry *b))
 429 {
 430         struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
 431         int comp;
 432
 433         while (tmp != NULL) {
 434                 comp = cmpfn(key, tmp);
 435                 if (comp <= 0)
 436                         tmp = RBE_LEFT(tmp);
 437                 else {
 438                         best = tmp;
 439                         tmp = RBE_RIGHT(tmp);
 440                 }
 441         }
 442
 443         return best;
 444 }
 445
 446 struct rb_entry *typed_rb_next(struct rb_entry *rbe)
 447 {
 448         if (RBE_RIGHT(rbe) != NULL) {
 449                 rbe = RBE_RIGHT(rbe);
 450                 while (RBE_LEFT(rbe) != NULL)
 451                         rbe = RBE_LEFT(rbe);
 452         } else {
 453                 if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 454                         rbe = RBE_PARENT(rbe);
 455                 else {
 456                         while (RBE_PARENT(rbe)
 457                                && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 458                                 rbe = RBE_PARENT(rbe);
 459                         rbe = RBE_PARENT(rbe);
 460                 }
 461         }
 462
 463         return rbe;
 464 }
 465
 466 struct rb_entry *typed_rb_min(struct rbt_tree *rbt)
 467 {
 468         struct rb_entry *rbe = RBH_ROOT(rbt);
 469         struct rb_entry *parent = NULL;
 470
 471         while (rbe != NULL) {
 472                 parent = rbe;
 473                 rbe = RBE_LEFT(rbe);
 474         }
 475
 476         return parent;
 477 }