opal/class/opal_interval

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
opal_interval_tree_construct
opal_interval_tree_destruct
opal_interval_tree_reader_get_token
opal_interval_tree_reader_return_token
opal_interval_tree_init
opal_interval_tree_write_trylock
opal_interval_tree_write_lock
opal_interval_tree_write_unlock
opal_interval_tree_insert_fixup_helper
opal_interval_tree_insert_fixup
opal_interval_tree_delete_fixup_helper
opal_interval_tree_delete_fixup
opal_interval_tree_gc_clean
opal_interval_tree_insert
opal_interval_tree_find_interval
opal_interval_tree_find_node
opal_interval_tree_find_overlapping
opal_interval_tree_depth_node
opal_interval_tree_depth
rp_publish
rp_wait_for_readers
rp_free_wait
rp_free
opal_interval_tree_node_copy
opal_interval_tree_delete_leaf
opal_interval_tree_delete_interior
opal_interval_tree_delete
opal_interval_tree_destroy
opal_interval_tree_next
opal_interval_tree_insert_node
inorder_traversal
inorder_destroy
opal_interval_tree_traverse
left_rotate
right_rotate
opal_interval_tree_size
opal_interval_tree_verify_node
opal_interval_tree_black_depth
opal_interval_tree_verify
opal_interval_tree_dump_node
opal_interval_tree_dump
   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
   2 /*
   3  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   4  *                         University Research and Technology
   5  *                         Corporation.  All rights reserved.
   6  * Copyright (c) 2004-2013 The University of Tennessee and The University
   7  *                         of Tennessee Research Foundation.  All rights
   8  *                         reserved.
   9  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
  10  *                         University of Stuttgart.  All rights reserved.
  11  * Copyright (c) 2004-2005 The Regents of the University of California.
  12  *                         All rights reserved.
  13  * Copyright (c) 2015-2018 Los Alamos National Security, LLC. All rights
  14  *                         reserved.
  15  * $COPYRIGHT$
  16  *
  17  * Additional copyrights may follow
  18  *
  19  * $HEADER$
  20  */
  21 /*
  22  * @file
  23  */
  24 
  25 #include "opal_config.h"
  26 
  27 #include "opal/class/opal_interval_tree.h"
  28 #include <limits.h>
  29 
  30 /* Private functions */
  31 static void opal_interval_tree_insert_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node);
  32 
  33 /* tree rebalancing functions */
  34 static void opal_interval_tree_delete_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *node,
  35                                              opal_interval_tree_node_t *parent);
  36 static void opal_interval_tree_insert_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *x);
  37 
  38 static opal_interval_tree_node_t *opal_interval_tree_next (opal_interval_tree_t *tree,
  39                                                            opal_interval_tree_node_t *node);
  40 static opal_interval_tree_node_t * opal_interval_tree_find_node(opal_interval_tree_t *tree,
  41                                                                 uint64_t low, uint64_t high,
  42                                                                 bool exact, void *data);
  43 
  44 static opal_interval_tree_node_t *left_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x);
  45 static opal_interval_tree_node_t *right_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x);
  46 
  47 static void inorder_destroy(opal_interval_tree_t *tree, opal_interval_tree_node_t * node);
  48 
  49 #define max(x,y) (((x) > (y)) ? (x) : (y))
  50 
  51 /**
  52  * the constructor function. creates the free list to get the nodes from
  53  *
  54  * @param object the tree that is to be used
  55  *
  56  * @retval NONE
  57  */
  58 static void opal_interval_tree_construct (opal_interval_tree_t *tree)
  59 {
  60     OBJ_CONSTRUCT(&tree->root, opal_interval_tree_node_t);
  61     OBJ_CONSTRUCT(&tree->nill, opal_interval_tree_node_t);
  62     OBJ_CONSTRUCT(&tree->free_list, opal_free_list_t);
  63     OBJ_CONSTRUCT(&tree->gc_list, opal_list_t);
  64 
  65     /* initialize sentinel */
  66     tree->nill.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
  67     tree->nill.left = tree->nill.right = tree->nill.parent = &tree->nill;
  68     tree->nill.max = 0;
  69     tree->nill.data = NULL;
  70 
  71     /* initialize root sentinel */
  72     tree->root.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
  73     tree->root.left = tree->root.right = tree->root.parent = &tree->nill;
  74     /* this simplifies inserting at the root as we only have to check the
  75      * low value. */
  76     tree->root.low = (uint64_t) -1;
  77     tree->root.data = NULL;
  78 
  79     /* set the tree size to zero */
  80     tree->tree_size = 0;
  81     tree->lock = 0;
  82     tree->reader_count = 0;
  83     tree->epoch = 0;
  84 
  85     /* set all reader epochs to UINT_MAX. this value is used to simplfy
  86      * checks against the current epoch. */
  87     for (int i = 0 ; i < OPAL_INTERVAL_TREE_MAX_READERS ; ++i) {
  88         tree->reader_epochs[i] = UINT_MAX;
  89     }
  90 }
  91 
  92 /**
  93  * the destructor function. Free the tree and destroys the free list.
  94  *
  95  * @param object the tree object
  96  */
  97 static void opal_interval_tree_destruct (opal_interval_tree_t *tree)
  98 {
  99     opal_interval_tree_destroy (tree);
 100 
 101     OBJ_DESTRUCT(&tree->free_list);
 102     OBJ_DESTRUCT(&tree->root);
 103     OBJ_DESTRUCT(&tree->nill);
 104 }
 105 
 106 /* declare the instance of the classes  */
 107 OBJ_CLASS_INSTANCE(opal_interval_tree_node_t, opal_free_list_item_t, NULL, NULL);
 108 OBJ_CLASS_INSTANCE(opal_interval_tree_t, opal_object_t, opal_interval_tree_construct,
 109                    opal_interval_tree_destruct);
 110 
 111 typedef int32_t opal_interval_tree_token_t;
 112 
 113 /**
 114  * @brief pick and return a reader slot
 115  */
 116 static opal_interval_tree_token_t opal_interval_tree_reader_get_token (opal_interval_tree_t *tree)
 117 {
 118     opal_interval_tree_token_t token = -1;
 119 
 120     if (token < 0) {
 121         int32_t reader_count = tree->reader_count;
 122         /* NTH: could have used an atomic here but all we are after is some distribution of threads
 123          * across the reader slots. with high thread counts i see no real performance difference
 124          * using atomics. */
 125         token = tree->reader_id++ % OPAL_INTERVAL_TREE_MAX_READERS;
 126         while (OPAL_UNLIKELY(reader_count <= token)) {
 127             if (opal_atomic_compare_exchange_strong_32 (&tree->reader_count, &reader_count, token + 1)) {
 128                 break;
 129             }
 130         }
 131     }
 132 
 133     while (!OPAL_ATOMIC_COMPARE_EXCHANGE_STRONG_32((opal_atomic_int32_t *) &tree->reader_epochs[token],
 134                                                    &(int32_t) {UINT_MAX}, tree->epoch));
 135 
 136     return token;
 137 }
 138 
 139 static void opal_interval_tree_reader_return_token (opal_interval_tree_t *tree, opal_interval_tree_token_t token)
 140 {
 141     tree->reader_epochs[token] = UINT_MAX;
 142 }
 143 
 144 /* Create the tree */
 145 int opal_interval_tree_init (opal_interval_tree_t *tree)
 146 {
 147     return opal_free_list_init (&tree->free_list, sizeof(opal_interval_tree_node_t),
 148                                 opal_cache_line_size, OBJ_CLASS(opal_interval_tree_node_t),
 149                                 0, opal_cache_line_size, 0, -1 , 128, NULL, 0, NULL, NULL, NULL);
 150 }
 151 
 152 static bool opal_interval_tree_write_trylock (opal_interval_tree_t *tree)
 153 {
 154     opal_atomic_rmb ();
 155     return !(tree->lock || opal_atomic_swap_32 (&tree->lock, 1));
 156 }
 157 
 158 static void opal_interval_tree_write_lock (opal_interval_tree_t *tree)
 159 {
 160     while (!opal_interval_tree_write_trylock (tree));
 161 }
 162 
 163 static void opal_interval_tree_write_unlock (opal_interval_tree_t *tree)
 164 {
 165     opal_atomic_wmb ();
 166     tree->lock = 0;
 167 }
 168 
 169 static void opal_interval_tree_insert_fixup_helper (opal_interval_tree_t *tree, opal_interval_tree_node_t *node) {
 170     opal_interval_tree_node_t *y, *parent = node->parent;
 171     bool rotate_right = false;
 172 
 173     if (parent->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
 174         return;
 175     }
 176 
 177     if (parent == parent->parent->left) {
 178         y = parent->parent->right;
 179         rotate_right = true;
 180     } else {
 181         y = parent->parent->left;
 182     }
 183 
 184     if (y->color == OPAL_INTERVAL_TREE_COLOR_RED) {
 185         parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 186         y->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 187         parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
 188         opal_interval_tree_insert_fixup_helper (tree, parent->parent);
 189         return;
 190     }
 191 
 192     if (rotate_right) {
 193         if (node == parent->right) {
 194             node = left_rotate (tree, parent);
 195             parent = node->parent;
 196         }
 197 
 198         parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 199         parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
 200         (void) right_rotate(tree, parent->parent);
 201     } else {
 202         if (node == parent->left) {
 203             node = right_rotate(tree, parent);
 204             parent = node->parent;
 205         }
 206         parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 207         parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
 208         (void) left_rotate(tree, parent->parent);
 209     }
 210 
 211     opal_interval_tree_insert_fixup_helper (tree, node);
 212 }
 213 
 214 static void opal_interval_tree_insert_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *node) {
 215     /* do the rotations */
 216     /* usually one would have to check for NULL, but because of the sentinal,
 217      * we don't have to   */
 218     opal_interval_tree_insert_fixup_helper (tree, node);
 219 
 220     /* after the rotations the root is black */
 221     tree->root.left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 222 }
 223 
 224 /**
 225  * @brief Guts of the delete fixup
 226  *
 227  * @param[in] tree    opal interval tree
 228  * @param[in] node    node to fixup
 229  * @param[in] left    true if the node is a left child of its parent
 230  *
 231  * @returns the next node to fixup or root if done
 232  */
 233 static inline opal_interval_tree_node_t *
 234 opal_interval_tree_delete_fixup_helper (opal_interval_tree_t *tree, opal_interval_tree_node_t *node,
 235                                         opal_interval_tree_node_t *parent, const bool left)
 236 {
 237     opal_interval_tree_node_t *w;
 238 
 239     /* get sibling */
 240     w = left ? parent->right : parent->left;
 241     if (w->color == OPAL_INTERVAL_TREE_COLOR_RED) {
 242         w->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 243         parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
 244         if (left) {
 245             (void) left_rotate(tree, parent);
 246             w = parent->right;
 247         } else {
 248             (void) right_rotate(tree, parent);
 249             w = parent->left;
 250         }
 251     }
 252 
 253     if ((w->left->color == OPAL_INTERVAL_TREE_COLOR_BLACK) && (w->right->color == OPAL_INTERVAL_TREE_COLOR_BLACK)) {
 254         w->color = OPAL_INTERVAL_TREE_COLOR_RED;
 255         return parent;
 256     }
 257 
 258     if (left) {
 259         if (w->right->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
 260             w->left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 261             w->color = OPAL_INTERVAL_TREE_COLOR_RED;
 262             (void) right_rotate(tree, w);
 263             w = parent->right;
 264         }
 265         w->color = parent->color;
 266         parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 267         w->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 268         (void) left_rotate(tree, parent);
 269     } else {
 270         if (w->left->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
 271             w->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 272             w->color = OPAL_INTERVAL_TREE_COLOR_RED;
 273             (void) left_rotate(tree, w);
 274             w = parent->left;
 275         }
 276         w->color = parent->color;
 277         parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 278         w->left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 279         (void) right_rotate(tree, parent);
 280     }
 281 
 282     /* return the root */
 283     return tree->root.left;
 284  }
 285 
 286 /* Fixup the balance of the btree after deletion    */
 287 static void opal_interval_tree_delete_fixup (opal_interval_tree_t *tree, opal_interval_tree_node_t *node,
 288                                              opal_interval_tree_node_t *parent)
 289 {
 290     while ((node != tree->root.left) && (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK)) {
 291         node = opal_interval_tree_delete_fixup_helper (tree, node, parent, node == parent->left);
 292         parent = node->parent;
 293     }
 294 
 295     node->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 296     tree->nill.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 297 }
 298 
 299 /* traverse the garbage-collection list and return any nodes that can not have any
 300  * references. this function MUST be called with the writer lock held. */
 301 static void opal_interval_tree_gc_clean (opal_interval_tree_t *tree)
 302 {
 303     opal_interval_tree_node_t *node, *next;
 304     uint32_t oldest_epoch = UINT_MAX;
 305 
 306     if (0 == opal_list_get_size (&tree->gc_list)) {
 307         return;
 308     }
 309 
 310     for (int i = 0 ; i < tree->reader_count ; ++i) {
 311         oldest_epoch = (oldest_epoch < tree->reader_epochs[i]) ? oldest_epoch : tree->reader_epochs[i];
 312     }
 313 
 314     OPAL_LIST_FOREACH_SAFE(node, next, &tree->gc_list, opal_interval_tree_node_t) {
 315         if (node->epoch < oldest_epoch) {
 316             opal_list_remove_item (&tree->gc_list, &node->super.super);
 317             opal_free_list_return_st (&tree->free_list, &node->super);
 318         }
 319     }
 320 }
 321 
 322 /* This inserts a node into the tree based on the passed values. */
 323 int opal_interval_tree_insert (opal_interval_tree_t *tree, void *value, uint64_t low, uint64_t high)
 324 {
 325     opal_interval_tree_node_t * node;
 326 
 327     if (low > high) {
 328         return OPAL_ERR_BAD_PARAM;
 329     }
 330 
 331     opal_interval_tree_write_lock (tree);
 332 
 333     opal_interval_tree_gc_clean (tree);
 334 
 335     /* get the memory for a node */
 336     node = (opal_interval_tree_node_t *) opal_free_list_get (&tree->free_list);
 337     if (OPAL_UNLIKELY(NULL == node)) {
 338         opal_interval_tree_write_unlock (tree);
 339         return OPAL_ERR_OUT_OF_RESOURCE;
 340     }
 341 
 342     /* insert the data into the node */
 343     node->data = value;
 344     node->low = low;
 345     node->high = high;
 346     node->max = high;
 347     node->epoch = tree->epoch;
 348 
 349     /* insert the node into the tree */
 350     opal_interval_tree_insert_node (tree, node);
 351 
 352     opal_interval_tree_insert_fixup (tree, node);
 353     opal_interval_tree_write_unlock (tree);
 354 
 355     return OPAL_SUCCESS;
 356 }
 357 
 358 static opal_interval_tree_node_t *opal_interval_tree_find_interval(opal_interval_tree_t *tree, opal_interval_tree_node_t *node, uint64_t low,
 359                                                                    uint64_t high, bool exact, void *data)
 360 {
 361     if (node == &tree->nill) {
 362         return NULL;
 363     }
 364 
 365     if (((exact && node->low == low && node->high == high) || (!exact && node->low <= low && node->high >= high)) &&
 366         (!data || node->data == data)) {
 367         return node;
 368     }
 369 
 370     if (low <= node->low) {
 371         return opal_interval_tree_find_interval (tree, node->left, low, high, exact, data);
 372     }
 373 
 374     return opal_interval_tree_find_interval (tree, node->right, low, high, exact, data);
 375 }
 376 
 377 /* Finds the node in the tree based on the key and returns a pointer
 378  * to the node. This is a bit a code duplication, but this has to be fast
 379  * so we go ahead with the duplication */
 380 static opal_interval_tree_node_t *opal_interval_tree_find_node(opal_interval_tree_t *tree, uint64_t low, uint64_t high, bool exact, void *data)
 381 {
 382     return opal_interval_tree_find_interval (tree, tree->root.left, low, high, exact, data);
 383 }
 384 
 385 void *opal_interval_tree_find_overlapping (opal_interval_tree_t *tree, uint64_t low, uint64_t high)
 386 {
 387     opal_interval_tree_token_t token;
 388     opal_interval_tree_node_t *node;
 389 
 390     token = opal_interval_tree_reader_get_token (tree);
 391     node = opal_interval_tree_find_node (tree, low, high, true, NULL);
 392     opal_interval_tree_reader_return_token (tree, token);
 393 
 394     return node ? node->data : NULL;
 395 }
 396 
 397 static size_t opal_interval_tree_depth_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 398 {
 399     if (&tree->nill == node) {
 400         return 0;
 401     }
 402 
 403     return 1 + max (opal_interval_tree_depth_node (tree, node->right), opal_interval_tree_depth_node (tree, node->left));
 404 }
 405 
 406 size_t opal_interval_tree_depth (opal_interval_tree_t *tree)
 407 {
 408     opal_interval_tree_token_t token;
 409     size_t depth;
 410 
 411     token = opal_interval_tree_reader_get_token (tree);
 412     depth = opal_interval_tree_depth_node (tree, &tree->root);
 413     opal_interval_tree_reader_return_token (tree, token);
 414 
 415     return depth;
 416 }
 417 
 418 /* update the value of a tree pointer */
 419 static inline void rp_publish (opal_interval_tree_node_t **ptr, opal_interval_tree_node_t *node)
 420 {
 421     /* ensure all writes complete before continuing */
 422     opal_atomic_wmb ();
 423     /* just set the value */
 424     *ptr = node;
 425 }
 426 
 427 
 428 static inline void rp_wait_for_readers (opal_interval_tree_t *tree)
 429 {
 430     uint32_t epoch_id = ++tree->epoch;
 431 
 432     /* wait for all readers to see the new tree version */
 433     for (int i = 0 ; i < tree->reader_count ; ++i) {
 434         while (tree->reader_epochs[i] < epoch_id);
 435     }
 436 }
 437 
 438 /* waits for all writers to finish with the node then releases the last reference */
 439 static inline void rp_free_wait (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 440 {
 441     rp_wait_for_readers (tree);
 442     /* no other threads are working on this node so go ahead and return it */
 443     opal_free_list_return_st (&tree->free_list, &node->super);
 444 }
 445 
 446 /* schedules the node for releasing */
 447 static inline void rp_free (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 448 {
 449     opal_list_append (&tree->gc_list, &node->super.super);
 450 }
 451 
 452 static opal_interval_tree_node_t *opal_interval_tree_node_copy (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 453 {
 454     opal_interval_tree_node_t *copy = (opal_interval_tree_node_t *) opal_free_list_wait_st (&tree->free_list);
 455     size_t color_offset = offsetof(opal_interval_tree_node_t, color);
 456     assert (NULL != copy);
 457     memcpy ((unsigned char *) copy + color_offset, (unsigned char *) node + color_offset,
 458             sizeof (*node) - color_offset);
 459     return copy;
 460 }
 461 
 462 /* this function deletes a node that is either a left or right leaf (or both) */
 463 static void opal_interval_tree_delete_leaf (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 464 {
 465     const opal_interval_tree_node_t *nill = &tree->nill;
 466     opal_interval_tree_node_t **parent_ptr, *next, *parent = node->parent;
 467     opal_interval_tree_nodecolor_t color = node->color;
 468 
 469     assert (node->left == nill || node->right == nill);
 470 
 471     parent_ptr = (parent->right == node) ? &parent->right : &parent->left;
 472 
 473     next = (node->right == nill) ? node->left : node->right;
 474 
 475     next->parent = node->parent;
 476     rp_publish (parent_ptr, next);
 477 
 478     rp_free (tree, node);
 479 
 480     if (OPAL_INTERVAL_TREE_COLOR_BLACK == color) {
 481         if (OPAL_INTERVAL_TREE_COLOR_RED == next->color) {
 482             next->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 483         } else {
 484             opal_interval_tree_delete_fixup (tree, next, parent);
 485         }
 486     }
 487 }
 488 
 489 static void opal_interval_tree_delete_interior (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 490 {
 491     opal_interval_tree_node_t **parent_ptr, *next, *next_copy, *parent = node->parent;
 492     opal_interval_tree_nodecolor_t color = node->color, next_color;
 493 
 494     parent_ptr = (parent->right == node) ? &parent->right : &parent->left;
 495     next = opal_interval_tree_next (tree, node);
 496     next_color = next->color;
 497 
 498     if (next != node->right) {
 499         /* case 3 */
 500         next_copy = opal_interval_tree_node_copy (tree, next);
 501         next_copy->color = node->color;
 502         next_copy->left = node->left;
 503         next_copy->left->parent = next_copy;
 504         next_copy->right = node->right;
 505         next_copy->right->parent = next_copy;
 506         next_copy->parent = node->parent;
 507 
 508         rp_publish (parent_ptr, next_copy);
 509         rp_free_wait (tree, node);
 510 
 511         opal_interval_tree_delete_leaf (tree, next);
 512     } else {
 513         /* case 2. no copies are needed */
 514         next->color = color;
 515         next->left = node->left;
 516         next->left->parent = next;
 517         next->parent = node->parent;
 518         rp_publish (parent_ptr, next);
 519         rp_free (tree, node);
 520 
 521         /* since we are actually "deleting" the next node the fixup needs to happen on the
 522          * right child of next (by definition next was a left child) */
 523         if (OPAL_INTERVAL_TREE_COLOR_BLACK == next_color) {
 524             if (OPAL_INTERVAL_TREE_COLOR_RED == next->right->color) {
 525                 next->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
 526             } else {
 527                 opal_interval_tree_delete_fixup (tree, next->right, next);
 528             }
 529         }
 530     }
 531 }
 532 
 533 /* Delete a node from the tree based on the key */
 534 int opal_interval_tree_delete (opal_interval_tree_t *tree, uint64_t low, uint64_t high, void *data)
 535 {
 536     opal_interval_tree_node_t *node;
 537 
 538     opal_interval_tree_write_lock (tree);
 539     node = opal_interval_tree_find_node (tree, low, high, true, data);
 540     if (NULL == node) {
 541         opal_interval_tree_write_unlock (tree);
 542         return OPAL_ERR_NOT_FOUND;
 543     }
 544 
 545     /* there are three cases that have to be handled:
 546      * 1) the node p is a left leaf or a right left (one of p's children is nill)
 547      *    in this case we can delete p and we can replace it with one of it's children
 548      *    or nill (if both children are nill).
 549      * 2) the right child of p is a left leaf (node->right->left == nill)
 550      *    in this case we can set node->right->left = node->left and replace node with node->right
 551      * 3) p is a interior node
 552      *    we replace node with next(node)
 553      */
 554     
 555     if ((node->left == &tree->nill) || (node->right == &tree->nill)) {
 556         /* handle case 1 */
 557         opal_interval_tree_delete_leaf (tree, node);
 558     } else {
 559         /* handle case 2 and 3 */
 560         opal_interval_tree_delete_interior (tree, node);
 561     }
 562 
 563     --tree->tree_size;
 564 
 565     opal_interval_tree_write_unlock (tree);
 566 
 567     return OPAL_SUCCESS;
 568 }
 569 
 570 int opal_interval_tree_destroy (opal_interval_tree_t *tree)
 571 {
 572     /* Recursive inorder traversal for delete */
 573     inorder_destroy(tree, &tree->root);
 574     tree->tree_size = 0;
 575     return OPAL_SUCCESS;
 576 }
 577 
 578 
 579 /* Find the next inorder successor of a node    */
 580 static opal_interval_tree_node_t *opal_interval_tree_next (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 581 {
 582     opal_interval_tree_node_t *p = node->right;
 583 
 584     if (p == &tree->nill) {
 585         p = node->parent;
 586         while (node == p->right) {
 587             node = p;
 588             p = p->parent;
 589         }
 590 
 591         if (p == &tree->root) {
 592             return &tree->nill;
 593         }
 594 
 595         return p;
 596     }
 597 
 598     while (p->left != &tree->nill) {
 599         p = p->left;
 600     }
 601 
 602     return p;
 603 }
 604 
 605 /* Insert an element in the normal binary search tree fashion    */
 606 /* this function goes through the tree and finds the leaf where
 607  * the node will be inserted   */
 608 static void opal_interval_tree_insert_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 609 {
 610     opal_interval_tree_node_t *parent = &tree->root;
 611     opal_interval_tree_node_t *n = parent->left; /* the real root of the tree */
 612     opal_interval_tree_node_t *nill = &tree->nill;
 613 
 614     /* set up initial values for the node */
 615     node->color = OPAL_INTERVAL_TREE_COLOR_RED;
 616     node->parent = NULL;
 617     node->left = nill;
 618     node->right = nill;
 619 
 620     /* find the leaf where we will insert the node */
 621     while (n != nill) {
 622         if (n->max < node->high) {
 623             n->max = node->high;
 624         }
 625 
 626         parent = n;
 627         n = ((node->low < n->low) ? n->left : n->right);
 628         assert (nill == n || n->parent == parent);
 629     }
 630 
 631     /* place it on either the left or the right */
 632     if ((node->low < parent->low)) {
 633         parent->left = node;
 634     } else {
 635         parent->right = node;
 636     }
 637 
 638     /* set its parent and children */
 639     node->parent = parent;
 640 
 641     ++tree->tree_size;
 642 }
 643 
 644 static int inorder_traversal (opal_interval_tree_t *tree, uint64_t low, uint64_t high,
 645                               bool partial_ok, opal_interval_tree_action_fn_t action,
 646                               opal_interval_tree_node_t * node, void *ctx)
 647 {
 648     int rc;
 649 
 650     if (node == &tree->nill) {
 651         return OPAL_SUCCESS;
 652     }
 653 
 654     rc = inorder_traversal(tree, low, high, partial_ok, action, node->left, ctx);
 655     if (OPAL_SUCCESS != rc) {
 656         return rc;
 657     }
 658 
 659     if ((!partial_ok && (node->low <= low && node->high >= high)) ||
 660         (partial_ok && ((low >= node->low && low <= node->high) ||
 661                         (high >= node->low && high <= node->high) ||
 662                         (node->low >= low && node->low <= high) ||
 663                         (node->high >= high && node->high <= high)))) {
 664         rc = action (node->low, node->high, node->data, ctx);
 665         if (OPAL_SUCCESS != rc) {
 666             return rc;
 667         }
 668     }
 669 
 670     return inorder_traversal(tree, low, high, partial_ok, action, node->right, ctx);
 671 }
 672 
 673 /* Free the nodes in inorder fashion    */
 674 
 675 static void inorder_destroy (opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
 676 {
 677     if (node == &tree->nill) {
 678         return;
 679     }
 680 
 681     inorder_destroy(tree, node->left);
 682     inorder_destroy(tree, node->right);
 683 
 684     if (node->left != &tree->nill) {
 685         opal_free_list_return_st (&tree->free_list, &node->left->super);
 686     }
 687 
 688     if (node->right != &tree->nill) {
 689         opal_free_list_return_st (&tree->free_list, &node->right->super);
 690     }
 691 }
 692 
 693 /* Try to access all the elements of the hashmap conditionally */
 694 
 695 int opal_interval_tree_traverse (opal_interval_tree_t *tree, uint64_t low, uint64_t high,
 696                                  bool partial_ok, opal_interval_tree_action_fn_t action, void *ctx)
 697 {
 698     opal_interval_tree_token_t token;
 699     int rc;
 700 
 701     if (action == NULL) {
 702         return OPAL_ERR_BAD_PARAM;
 703     }
 704 
 705     token = opal_interval_tree_reader_get_token (tree);
 706     rc = inorder_traversal (tree, low, high, partial_ok, action, tree->root.left, ctx);
 707     opal_interval_tree_reader_return_token (tree, token);
 708     return rc;
 709 }
 710 
 711 /* Left rotate the tree    */
 712 /* basically what we want to do is to make x be the left child
 713  * of its right child    */
 714 static opal_interval_tree_node_t *left_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x)
 715 {
 716     opal_interval_tree_node_t *x_copy = x;
 717     opal_interval_tree_node_t *y = x->right;
 718     opal_interval_tree_node_t *parent = x->parent;
 719 
 720     /* make the left child of y's parent be x if it is not the sentinal node*/
 721     if (y->left != &tree->nill) {
 722         y->left->parent = x_copy;
 723     }
 724 
 725     /* x's parent is now y */
 726     x_copy->parent = y;
 727     x_copy->right = y->left;
 728     x_copy->max = max (x_copy->high, max (x_copy->left->max, x_copy->left->max));
 729 
 730     rp_publish (&y->left, x_copy);
 731 
 732     /* normlly we would have to check to see if we are at the root.
 733      * however, the root sentinal takes care of it for us */
 734     if (x == parent->left) {
 735         rp_publish (&parent->left, y);
 736     } else {
 737         rp_publish (&parent->right, y);
 738     }
 739 
 740     /* the old parent of x is now y's parent */
 741     y->parent = parent;
 742 
 743     return x_copy;
 744 }
 745 
 746 
 747 /* Right rotate the tree    */
 748 /* basically what we want to do is to make x be the right child
 749  * of its left child */
 750 static opal_interval_tree_node_t *right_rotate (opal_interval_tree_t *tree, opal_interval_tree_node_t *x)
 751 {
 752     opal_interval_tree_node_t *x_copy = x;
 753     opal_interval_tree_node_t *y = x->left;
 754     opal_interval_tree_node_t *parent = x->parent;
 755 
 756     /* make the left child of y's parent be x if it is not the sentinal node*/
 757     if (y->right != &tree->nill) {
 758         y->right->parent = x_copy;
 759     }
 760 
 761     x_copy->left = y->right;
 762     x_copy->parent = y;
 763 
 764     rp_publish (&y->right, x_copy);
 765 
 766     /* the maximum value in the subtree rooted at y is now the value it
 767      * was at x */
 768     y->max = x->max;
 769     y->parent = parent;
 770 
 771     if (parent->left == x) {
 772         rp_publish (&parent->left, y);
 773     } else {
 774         rp_publish (&parent->right, y);
 775     }
 776 
 777     return x_copy;
 778 }
 779 
 780 /* returns the size of the tree */
 781 size_t opal_interval_tree_size(opal_interval_tree_t *tree)
 782 {
 783     return tree->tree_size;
 784 }
 785 
 786 static bool opal_interval_tree_verify_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node, int black_depth,
 787                                             int current_black_depth)
 788 {
 789     if (node == &tree->nill) {
 790         return true;
 791     }
 792 
 793     if (OPAL_INTERVAL_TREE_COLOR_RED == node->color &&
 794         (OPAL_INTERVAL_TREE_COLOR_BLACK != node->left->color ||
 795          OPAL_INTERVAL_TREE_COLOR_BLACK != node->right->color)) {
 796         fprintf (stderr, "Red node has a red child!\n");
 797         return false;
 798     }
 799 
 800     if (OPAL_INTERVAL_TREE_COLOR_BLACK == node->color) {
 801         current_black_depth++;
 802     }
 803 
 804     if (node->left == &tree->nill && node->right == &tree->nill) {
 805         if (black_depth != current_black_depth) {
 806             fprintf (stderr, "Found leaf with unexpected black depth: %d, expected: %d\n", current_black_depth, black_depth);
 807             return false;
 808         }
 809 
 810         return true;
 811     }
 812 
 813     return opal_interval_tree_verify_node (tree, node->left, black_depth, current_black_depth) ||
 814         opal_interval_tree_verify_node (tree, node->right, black_depth, current_black_depth);
 815 }
 816 
 817 static int opal_interval_tree_black_depth (opal_interval_tree_t *tree, opal_interval_tree_node_t *node, int depth)
 818 {
 819     if (node == &tree->nill) {
 820         return depth;
 821     }
 822 
 823     /* suffices to always go left */
 824     if (OPAL_INTERVAL_TREE_COLOR_BLACK == node->color) {
 825         depth++;
 826     }
 827 
 828     return opal_interval_tree_black_depth (tree, node->left, depth);
 829 }
 830 
 831 bool opal_interval_tree_verify (opal_interval_tree_t *tree)
 832 {
 833     int black_depth;
 834 
 835     if (OPAL_INTERVAL_TREE_COLOR_BLACK != tree->root.left->color) {
 836         fprintf (stderr, "Root node of tree is NOT black!\n");
 837         return false;
 838     }
 839 
 840     if (OPAL_INTERVAL_TREE_COLOR_BLACK != tree->nill.color) {
 841         fprintf (stderr, "Leaf node color is NOT black!\n");
 842         return false;
 843     }
 844 
 845     black_depth = opal_interval_tree_black_depth (tree, tree->root.left, 0);
 846 
 847     return opal_interval_tree_verify_node (tree, tree->root.left, black_depth, 0);
 848 }
 849 
 850 static void opal_interval_tree_dump_node (opal_interval_tree_t *tree, opal_interval_tree_node_t *node, int black_rank, FILE *fh)
 851 {
 852     const char *color = (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK) ? "black" : "red";
 853     uintptr_t left = (uintptr_t) node->left, right = (uintptr_t) node->right;
 854     opal_interval_tree_node_t *nill = &tree->nill;
 855 
 856     if (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
 857         ++black_rank;
 858     }
 859 
 860     if (nill == node) {
 861         return;
 862     }
 863 
 864     /* print out nill nodes if any */
 865     if ((uintptr_t) nill == left) {
 866         left = (uintptr_t) node | 0x1;
 867         fprintf (fh, "  Node%lx [color=black,label=nill];\n\n", left);
 868     } else {
 869         left = (uintptr_t) node->left;
 870     }
 871 
 872     if ((uintptr_t) nill == right) {
 873         right = (uintptr_t) node | 0x2;
 874         fprintf (fh, "  Node%lx [color=black,label=nill];\n\n", right);
 875     } else {
 876         right = (uintptr_t) node->right;
 877     }
 878 
 879     /* print out this node and its edges */
 880     fprintf (fh, "  Node%lx [color=%s,shape=box,label=\"[0x%" PRIx64 ",0x%" PRIx64 "]\\nmax=0x%" PRIx64
 881              "\\ndata=0x%lx\\nblack rank=%d\"];\n", (uintptr_t) node, color, node->low, node->high, node->max,
 882              (uintptr_t) node->data, black_rank);
 883     fprintf (fh, "  Node%lx -> Node%lx;\n", (uintptr_t) node, left);
 884     fprintf (fh, "  Node%lx -> Node%lx;\n\n", (uintptr_t) node, right);
 885     if (node != tree->root.left) {
 886         fprintf (fh, "  Node%lx -> Node%lx;\n\n", (uintptr_t) node, (uintptr_t) node->parent);
 887     }
 888     opal_interval_tree_dump_node (tree, node->left, black_rank, fh);
 889     opal_interval_tree_dump_node (tree, node->right, black_rank, fh);
 890 }
 891 
 892 int opal_interval_tree_dump (opal_interval_tree_t *tree, const char *path)
 893 {
 894     FILE *fh;
 895 
 896     fh = fopen (path, "w");
 897     if (NULL == fh) {
 898         return OPAL_ERR_BAD_PARAM;
 899     }
 900 
 901     fprintf (fh, "digraph {\n");
 902     fprintf (fh, "  graph [ordering=\"out\"];");
 903     opal_interval_tree_dump_node (tree, tree->root.left, 0, fh);
 904     fprintf (fh, "}\n");
 905 
 906     fclose (fh);
 907 
 908     return OPAL_SUCCESS;
 909 }
/* [<][>][^][v][top][bottom][index][help] */
root/opal/class/opal_interval_tree.c

DEFINITIONS
