cde/programs/dtcm/server/tree.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: tree.c /main/4 1995/11/09 12:53:11 rswiston $ */
  24 /*
  25  *  (c) Copyright 1993, 1994 Hewlett-Packard Company
  26  *  (c) Copyright 1993, 1994 International Business Machines Corp.
  27  *  (c) Copyright 1993, 1994 Novell, Inc.
  28  *  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
  29  */
  30
  31 /*      2-3-4 tree, a.k.a. red-black tree, implementation  */
  32
  33 #include <EUSCompat.h>
  34 #include <sys/param.h>
  35 #include <unistd.h>
  36 #include <stdlib.h>
  37 #include "tree.h"
  38
  39 extern int debug;
  40
  41 typedef struct {
  42         int size;               /* used in insert and size */
  43         int count;              /* used in checktree only */
  44         Rb_Status status;       /* used in checktree and insert */
  45         caddr_t data;           /* used in lookups only */
  46         Tree_node *i;           /* used in insert only */
  47         caddr_t key;            /* used in insert only */
  48         Tree_node *d;           /* used in delete only */
  49         Tree_node *y;           /* dummy that is at both links of z */
  50         Tree_node *z;           /* dummy used as child of leaf nodes */
  51         Rb_tree *tree;          /* back link to parent tree */
  52         _DtCmsGetKeyProc get;
  53         _DtCmsEnumerateProc enumerate;
  54         _DtCmsCompareProc compare;
  55         } Private;
  56
  57 typedef void (*Action_proc)
  58         (/* Private *private; Tree_node *y, *z, *root */);
  59
  60
  61 static Tree_node *
  62 balance(Tree_node *gg, Tree_node *g, Tree_node *f, Tree_node *x)
  63 {
  64         Tree_node *t;
  65         Color tc;
  66         if (gg == NULL || g == NULL) exit (-1);
  67         if (f == g->llink) {
  68                 if (x == f->rlink) {
  69                         f->rlink = x->llink;
  70                         x->llink = f;
  71                         t = f;
  72                         f = x;
  73                         x = t;
  74                 }
  75         }
  76         else {
  77                 if (x == f->llink) {
  78                         f->llink = x->rlink;
  79                         x->rlink = f;
  80                         t = f;
  81                         f = x;
  82                         x = t;
  83                 }
  84         }
  85         if (x == f->llink) {
  86                 g->llink = f->rlink;
  87                 f->rlink = g;
  88         }
  89         else {
  90                 g->rlink = f->llink;
  91                 f->llink = g;
  92         }
  93         if (g == gg->rlink) gg->rlink = f;
  94         else gg->llink = f;
  95         tc = g->color;
  96         g->color = f->color;
  97         f->color = tc;
  98         return(f);
  99 }
 100
 101 static void
 102 doit(Rb_tree *tree, Action_proc proc)
 103 {
 104         Private *private;
 105         Tree_node *root;
 106
 107         if (tree==NULL) return;
 108         private = (Private *) tree->private;
 109         root = tree->root;
 110         if (root == NULL || root->llink != NULL) {
 111                 private->status = rb_badtable;
 112                 return;
 113         }
 114         proc(private, private->y, private->z, root);
 115 }
 116
 117 extern Rb_tree *
 118 rb_create (_DtCmsGetKeyProc get, _DtCmsCompareProc compare)
 119 {
 120         Private *p;
 121         Tree_node *root, *y, *z;
 122         Rb_tree *tree;
 123
 124         p = (Private *) calloc (1, sizeof(Private));
 125         p->size = 0;
 126         p->count = 0;
 127         p->status = rb_ok;
 128         p->data = NULL;
 129         p->i = NULL;
 130         p->key = 0;
 131         p->d = NULL;
 132         p->y = (Tree_node *) calloc (1, sizeof(Tree_node));
 133         p->z = (Tree_node *) calloc (1, sizeof(Tree_node));
 134         p->get = get;
 135         p->enumerate = NULL;
 136         p->compare = compare;
 137
 138         root = (Tree_node *) calloc (1, sizeof(Tree_node));
 139         y = p->y;
 140         z = p->z;
 141         tree = (Rb_tree *) calloc (1, sizeof(Rb_tree));
 142         tree->root = root;
 143         tree->private = (caddr_t) p;
 144         p->tree = tree;   /* link back so callbacks can access */
 145         root->color = black;
 146         root->llink = NULL;
 147         root->rlink = z;
 148         y->color = red;
 149         y->llink = y->rlink = NULL;
 150         z->color = black;
 151         z->llink = z->rlink = y;
 152
 153         return(tree);
 154 }
 155
 156
 157 extern void
 158 rb_destroy(Rb_tree *tree, _DtCmsEnumerateProc destroy)
 159 {
 160         Private *p = NULL;
 161         caddr_t data = NULL;
 162         Tree_node *node = NULL;
 163         caddr_t key;
 164
 165         /* NOTE:there is a client data field
 166                 associated with the tree struct.
 167                 It is up to the client to destroy
 168                 these.                          */
 169         if (tree==NULL) return;
 170         p = (Private *) tree->private;
 171         data = rb_lookup_smallest(tree);
 172
 173         /* enumerate tree, destroying data */
 174         while(data != NULL) {
 175                 key = p->get(data);
 176                 node = rb_delete(tree, key);
 177                 if (destroy)
 178                         destroy(data);
 179                 free(node);
 180                 data = rb_lookup_next_larger(tree, key);
 181         }
 182
 183         /* destroy the private internal struct */
 184         free(p->y);
 185         free(p->z);
 186         free(p);
 187
 188         /* destroy the root node */
 189         free(tree->root);
 190
 191         /* destroy the tree */
 192         free(tree);
 193 }
 194
 195 /* ARGSUSED */
 196 static void
 197 size_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 198 {
 199         /* dummy proc for monitor */
 200 }
 201
 202 extern int
 203 rb_size(Rb_tree *tree)
 204 {
 205         Private *p;
 206         if (tree==NULL) return(0);
 207         p = (Private *) tree->private;
 208         if (tree != NULL) {
 209                 doit(tree, size_callback);
 210                 return(p->size);
 211         }
 212         else return(0);
 213 }
 214
 215 /* ARGSUSED */
 216 static void
 217 insert_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 218 {
 219         Tree_node *x=NULL, *gg=NULL, *g=NULL, *f=NULL;
 220         _DtCmsComparisonResult c = _DtCmsIsGreater;
 221
 222         f = root;
 223         x = f->rlink;
 224         for (;;) {
 225                 if (x->llink->color == red && x->rlink->color == red) {
 226                         if (x == z) {
 227                                 if (c == _DtCmsIsEqual) {
 228                                         private->status = rb_duplicate;
 229                                         root->rlink->color = black;
 230                                         return;
 231                                 }
 232                                 x = private->i;
 233                                 x->llink = z;
 234                                 x->rlink = z;
 235                                 if (c == _DtCmsIsLess) f->llink = x; else f->rlink = x;
 236                                 c = _DtCmsIsEqual;
 237                                 private->size++;
 238                         }
 239                         x->llink->color = black;
 240                         x->rlink->color = black;
 241                         x->color = red;
 242                         if (f->color == red) {
 243                                 g = balance (gg, g, f, x);
 244                                 x = g;
 245                         }
 246                 }
 247                 if (c == _DtCmsIsEqual) break;
 248                 gg = g; g = f; f = x;
 249                 c = private->compare (private->key, x->data);
 250                 if (c==_DtCmsIsEqual) {
 251                         private->status=rb_duplicate;
 252                         root->rlink->color=black;
 253                         return;
 254                 }
 255                 x = (c == _DtCmsIsLess) ? x->llink : x-> rlink;
 256         }
 257         root->rlink->color = black;
 258 }
 259
 260 extern Rb_Status
 261 rb_insert_node(Rb_tree *tree, Tree_node *node, caddr_t key)
 262 {
 263         Private *private;
 264
 265         if (tree==NULL) return(rb_notable);
 266         private = (Private *) tree->private;
 267         private->status = rb_ok;
 268         private->i = node;
 269         private->key = key;
 270         doit (tree, insert_callback);
 271         return (private->status);
 272 }
 273
 274 extern Rb_Status
 275 rb_insert(Rb_tree *tree, caddr_t data, caddr_t key)
 276 {
 277         Tree_node *node;
 278
 279         if (tree==NULL) return(rb_notable);
 280         node = (Tree_node *)calloc(1, sizeof(Tree_node));
 281         node->data = data;
 282         return(rb_insert_node(tree, node, key));
 283 }
 284
 285 static void
 286 delete_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 287 {
 288         Tree_node *f, *result, *parent;
 289         Tree_node *x, *g, *b;
 290         _DtCmsComparisonResult c;
 291
 292         f = root;
 293         x = f->rlink;
 294         result = NULL;
 295
 296         if (x == z) return;
 297         y->color = black;
 298         if (x->llink->color == black && x->rlink->color == black)
 299                 x->color = red;
 300         c = private->compare(private->key, x->data);
 301         if (c == _DtCmsIsEqual) {
 302                 result = x;
 303                 parent = f;
 304         }
 305         for (;;) {
 306                 g = f;
 307                 f = x;
 308                 if (c == _DtCmsIsLess) {
 309                         b = x->rlink;
 310                         x = x->llink;
 311                 }
 312                 else {
 313                         b = x->llink;
 314                         x = x->rlink;
 315                 }
 316                 if (x != z) {
 317                         c = private->compare(private->key, x->data);
 318                         if (c == _DtCmsIsEqual) {
 319                                 result = x;
 320                                 parent = f;
 321                         }
 322                 }
 323                 if (x->color == red || x->llink->color == red ||
 324                         x->rlink->color == red) continue;
 325                 if (b->color == red) {
 326                         if (b == f->llink) {
 327                                 f->llink = b->rlink;
 328                                 b->rlink = f;
 329                         }
 330                         else {
 331                                 f->rlink = b->llink;
 332                                 b->llink = f;
 333                         }
 334                         f->color = red;
 335                         b->color = black;
 336                         if (f == g->llink) g->llink = b;
 337                         else g->rlink = b;
 338                         x = b;
 339                         c = private->compare(private->key, x->data);
 340                         continue;
 341                 }
 342                 if (x == z) break;
 343                 x->color = red;
 344                 if (b->llink->color == red) {
 345                         b->llink->color = black;
 346                         x = balance (g, f, b, b->llink);
 347                         c = private->compare(private->key, x->data);
 348                         continue;
 349                 }
 350                 if (b->rlink->color == red) {
 351                         b->rlink->color = black;
 352                         x = balance(g, f, b, b->rlink);
 353                         c = private->compare(private->key, x->data);
 354                         continue;
 355                 }
 356                 f->color = black;
 357                 b->color = red;
 358         } /* end for-loop */
 359         root->rlink->color = black;
 360         z->color = black;
 361         y->color = red;
 362         if (result != NULL) {
 363                 if (g->llink == f) g->llink = z;
 364                 else g->rlink = z;
 365                 if (f != result) {
 366                         if (parent->llink == result) parent->llink = f;
 367                         else parent->rlink = f;
 368                         f->llink = result->llink;
 369                         f->rlink = result->rlink;
 370                         f->color = result->color;
 371                 }
 372                 private->size--;
 373         }
 374         private->d = result;
 375 }
 376
 377 extern Tree_node *
 378 rb_delete(Rb_tree *tree, caddr_t key)
 379 {
 380         Private *p;
 381         if (tree==NULL) return((Tree_node *)NULL);
 382         p = (Private *) tree->private;
 383         p->key = key;
 384         p->d = NULL;    /* in case the key is not found */
 385         doit (tree, delete_callback);
 386         return(p->d);
 387 }
 388
 389 /* ARGSUSED */
 390 static void
 391 lookup_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 392 {
 393         _DtCmsComparisonResult c;
 394         Tree_node *eq = root->rlink;
 395         for (;;) {
 396                 if (eq == z) return;
 397                 c = private->compare(private->key, eq->data);
 398                 switch(c) {
 399                 case _DtCmsIsEqual:
 400                         goto bye;
 401                 case _DtCmsIsLess:
 402                         eq = eq->llink;
 403                         break;
 404                 case _DtCmsIsGreater:
 405                         eq = eq->rlink;
 406                         break;
 407                 default:
 408                         break;
 409                 }
 410         }
 411         bye: private->data = eq->data;
 412 }
 413
 414 extern caddr_t
 415 rb_lookup(Rb_tree *tree, caddr_t key)
 416 {
 417         Private *private;
 418         if (tree==NULL) return((caddr_t)NULL);
 419         private = (Private *)tree->private;
 420         private->key = key;
 421         private->data = NULL; /* might have been previously used */
 422         doit (tree, lookup_callback);
 423         return (private->data);
 424 }
 425
 426 /* ARGSUSED */
 427 static void
 428 lookup_smallest_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 429 {
 430         Tree_node *smallest = root->rlink;
 431         if (smallest == z) return;
 432         while (smallest->llink != z) {
 433                   smallest = smallest->llink;
 434         }
 435         private->data = smallest->data;
 436 }
 437
 438 extern caddr_t
 439 rb_lookup_smallest(Rb_tree *tree)
 440 {
 441         Private *private;
 442         if (tree==NULL) return((caddr_t)NULL);
 443         private = (Private *)tree->private;
 444         private->data = NULL; /* might have been previously used */
 445         doit (tree, lookup_smallest_callback);
 446         return (private->data);
 447 }
 448
 449 /* ARGSUSED */
 450 static void
 451 next_larger_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 452 {
 453         Tree_node *larger = NULL;
 454         Tree_node *x = root->rlink;
 455         while (x != z) {
 456                 if (private->compare (private->key, x->data) == _DtCmsIsLess) {
 457                         larger = x;
 458                         x = x->llink;
 459                 }
 460                 else x= x->rlink;
 461         }
 462         if (larger != NULL) private->data = larger->data;
 463 }
 464
 465 extern caddr_t
 466 rb_lookup_next_larger(Rb_tree *tree, caddr_t key)
 467 {
 468         Private *private;
 469         if (tree==NULL) return((caddr_t)NULL);
 470         private = (Private *) tree->private;
 471         private->key = key;
 472         private->data = NULL; /* might have been previously used */
 473         doit (tree, next_larger_callback);
 474         return(private->data);
 475 }
 476
 477 /* ARGSUSED */
 478 static void
 479 lookup_largest_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 480 {
 481         Tree_node *largest = root->rlink;
 482         if (largest == z) return;
 483         while (largest->rlink != z) {
 484                 largest = largest->rlink;
 485         }
 486         private->data = largest->data;
 487 }
 488
 489 extern caddr_t
 490 rb_lookup_largest(Rb_tree *tree)
 491 {
 492         Private *private;
 493
 494         if (tree==NULL) return((caddr_t)NULL);
 495         private = (Private *) tree->private;
 496         private->data = NULL; /* might have been previously used */
 497         doit (tree, lookup_largest_callback);
 498         return (private->data);
 499 }
 500
 501 /* ARGSUSED */
 502 static void
 503 next_smaller_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 504 {
 505
 506         Tree_node *smaller = NULL;
 507         Tree_node *x = root->rlink;
 508         while (x != z) {
 509                 if (private->compare(private->key, x->data) == _DtCmsIsGreater) {
 510                         smaller = x;
 511                         x = x->rlink;
 512                 }
 513                 else x = x->llink;
 514         }
 515         if (smaller != NULL) private->data = smaller->data;
 516 }
 517
 518 extern caddr_t
 519 rb_lookup_next_smaller(Rb_tree *tree, caddr_t key)
 520 {
 521         Private *private;
 522         if (tree==NULL) return((caddr_t)NULL);
 523         private = (Private *) tree->private;
 524         private->key = key;
 525         private->data = NULL; /* might have been previously used */
 526         doit (tree, next_smaller_callback);
 527         return(private->data);
 528 }
 529
 530 typedef enum {up, down} Direction;
 531
 532 static boolean_t
 533 visit_subtree(Tree_node *node, Private *p, Tree_node *z, Direction dir)
 534 {
 535         Tree_node *link;
 536         link = (dir == up) ? node->llink : node->rlink;
 537         if (link != z && visit_subtree(link, p, z, dir)) return(B_TRUE);
 538         if (p->enumerate((caddr_t)node, node->data)) return(B_TRUE);
 539         link = (dir == up) ? node->rlink : node->llink;
 540         if (link != z) return(visit_subtree(link, p, z, dir));
 541         else return(B_FALSE);
 542 }
 543
 544 /* ARGSUSED */
 545 static boolean_t
 546 enumerate_up_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 547 {
 548         if (root == NULL || root->rlink == z) return (B_FALSE);
 549         return (visit_subtree(root->rlink, private, z, up));
 550 }
 551
 552 extern Rb_Status
 553 rb_enumerate_up(Rb_tree *tree, _DtCmsEnumerateProc proc)
 554 {
 555         Private *private;
 556         if (tree==NULL) return (rb_badtable);
 557         private = (Private *) tree->private;
 558         private->enumerate = proc;
 559         if (tree->root == NULL || tree->root->llink != NULL)
 560                 return rb_badtable;
 561
 562         if (enumerate_up_callback(private, private->y, private->z, tree->root))
 563                 return (rb_failed);
 564         else
 565                 return (rb_ok);
 566 }
 567
 568 /* ARGSUSED */
 569 static void
 570 enumerate_down_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 571 {
 572         if (root == NULL || root->rlink == z) return;
 573         (void) visit_subtree(root->rlink, private, z, down);
 574 }
 575
 576 extern void
 577 rb_enumerate_down(Rb_tree *tree, _DtCmsEnumerateProc proc)
 578 {
 579         Private *private;
 580         if (tree==NULL) return;
 581         private = (Private *) tree->private;
 582         private->enumerate = proc;
 583         doit (tree, enumerate_down_callback);
 584 }
 585
 586 /* --------------------DEBUGGING-------------------------*/
 587
 588 static int
 589 assert(int p)
 590 {
 591         return(p);
 592 }
 593
 594 typedef struct {caddr_t max; int i; boolean_t bool;} Rec;
 595
 596 static void
 597 check1(Tree_node *x, caddr_t max, Tree_node *z, Rec *rec, Private *private)
 598 {
 599         int dl, dr;
 600         boolean_t redchild;
 601         Rec localrec; Rec *localp = &localrec;
 602         if (x == z) {
 603                 rec->max = max;
 604                 rec->i = 0;
 605                 rec->bool = B_FALSE;
 606                 return;
 607         }
 608         check1(x->llink, max, z, localp, private);
 609         if (private->status == rb_badtable) return;
 610         max = localp->max;
 611         dl = localp->i;
 612         redchild = localp->bool;
 613         if (!assert (!(redchild && (x->color == red)))) {
 614                 private->status = rb_badtable;
 615                 return;
 616         }
 617         if (!assert (private->compare(max, x->data) ==
 618                      (private->count == 0 ? _DtCmsIsEqual : _DtCmsIsLess))) {
 619                 private->status = rb_badtable;
 620                 return;
 621         }
 622         private->count++;
 623         check1(x->rlink, private->get(x->data), z, localp, private);
 624         if (private->status == rb_badtable) return;
 625         max = localp->max;
 626         dr = localp->i;
 627         redchild = localp->bool;
 628         if (!assert (!(redchild && (x->color == red)))) {
 629                 private->status = rb_badtable;
 630                 return;
 631         }
 632         if (!assert (dl == dr)) {
 633                 private->status = rb_badtable;
 634                 return;
 635         }
 636         rec->max = max;
 637         rec->i = dl + ((x->color == black) ? 1 : 0);
 638         rec->bool = ((x->color == red) ? B_TRUE : B_FALSE);
 639 }
 640
 641 static void
 642 check_tree_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
 643 {
 644         if (!assert (z->llink == y)) {
 645                 private->status = rb_badtable;
 646                 return;
 647         }
 648         if (!assert (z->rlink == y)) {
 649                 private->status = rb_badtable;
 650                 return;
 651         }
 652         if (root->rlink != z) {
 653                 Rec localrec;
 654                 Rec *localp = &localrec;
 655                 Tree_node *smallest = root->rlink;
 656                 while (smallest->llink != z) {
 657                         smallest = smallest->llink;
 658                 }
 659                 check1(root->rlink, private->get(smallest->data), z, localp, private);
 660                 if (private->status == rb_badtable) return;
 661         }
 662 }
 663
 664 extern Rb_Status
 665 rb_check_tree(Rb_tree *tree)
 666 {
 667         Private *p;
 668         if (tree==NULL) return(rb_notable);
 669         p = (Private *) tree->private;
 670         p->status = rb_ok;
 671         p->count = 0;
 672         doit (tree, check_tree_callback);
 673         return(p->status);
 674 }