contrib/ofed/opensm/complib/cl_map.c

   1 /*
   2  * Copyright (c) 2004-2009 Voltaire, Inc. All rights reserved.
   3  * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved.
   4  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.
   5  *
   6  * This software is available to you under a choice of one of two
   7  * licenses.  You may choose to be licensed under the terms of the GNU
   8  * General Public License (GPL) Version 2, available from the file
   9  * COPYING in the main directory of this source tree, or the
  10  * OpenIB.org BSD license below:
  11  *
  12  *     Redistribution and use in source and binary forms, with or
  13  *     without modification, are permitted provided that the following
  14  *     conditions are met:
  15  *
  16  *      - Redistributions of source code must retain the above
  17  *        copyright notice, this list of conditions and the following
  18  *        disclaimer.
  19  *
  20  *      - Redistributions in binary form must reproduce the above
  21  *        copyright notice, this list of conditions and the following
  22  *        disclaimer in the documentation and/or other materials
  23  *        provided with the distribution.
  24  *
  25  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  29  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  30  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  31  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  32  * SOFTWARE.
  33  *
  34  */
  35
  36 /*
  37  * Abstract:
  38  *      Implementation of quick map, a binary tree where the caller always
  39  *      provides all necessary storage.
  40  *
  41  */
  42
  43 /*****************************************************************************
  44 *
  45 * Map
  46 *
  47 * Map is an associative array.  By providing a key, the caller can retrieve
  48 * an object from the map.  All objects in the map have an associated key,
  49 * as specified by the caller when the object was inserted into the map.
  50 * In addition to random access, the caller can traverse the map much like
  51 * a linked list, either forwards from the first object or backwards from
  52 * the last object.  The objects in the map are always traversed in
  53 * order since the nodes are stored sorted.
  54 *
  55 * This implementation of Map uses a red black tree verified against
  56 * Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth
  57 * printing, 1994.
  58 *
  59 *****************************************************************************/
  60
  61 #if HAVE_CONFIG_H
  62 #  include <config.h>
  63 #endif                          /* HAVE_CONFIG_H */
  64
  65 #include <string.h>
  66 #include <complib/cl_qmap.h>
  67 #include <complib/cl_map.h>
  68 #include <complib/cl_fleximap.h>
  69
  70 /******************************************************************************
  71  IMPLEMENTATION OF QUICK MAP
  72 ******************************************************************************/
  73
  74 /*
  75  * Get the root.
  76  */
  77 static inline cl_map_item_t *__cl_map_root(IN const cl_qmap_t * const p_map)
  78 {
  79         CL_ASSERT(p_map);
  80         return (p_map->root.p_left);
  81 }
  82
  83 /*
  84  * Returns whether a given item is on the left of its parent.
  85  */
  86 static boolean_t __cl_map_is_left_child(IN const cl_map_item_t * const p_item)
  87 {
  88         CL_ASSERT(p_item);
  89         CL_ASSERT(p_item->p_up);
  90         CL_ASSERT(p_item->p_up != p_item);
  91
  92         return (p_item->p_up->p_left == p_item);
  93 }
  94
  95 /*
  96  * Retrieve the pointer to the parent's pointer to an item.
  97  */
  98 static cl_map_item_t **__cl_map_get_parent_ptr_to_item(IN cl_map_item_t *
  99                                                        const p_item)
 100 {
 101         CL_ASSERT(p_item);
 102         CL_ASSERT(p_item->p_up);
 103         CL_ASSERT(p_item->p_up != p_item);
 104
 105         if (__cl_map_is_left_child(p_item))
 106                 return (&p_item->p_up->p_left);
 107
 108         CL_ASSERT(p_item->p_up->p_right == p_item);
 109         return (&p_item->p_up->p_right);
 110 }
 111
 112 /*
 113  * Rotate a node to the left.  This rotation affects the least number of links
 114  * between nodes and brings the level of C up by one while increasing the depth
 115  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.
 116  *
 117  *          R                                 R
 118  *          |                                 |
 119  *          A                                 C
 120  *        /   \                         /   \
 121  *      W       C                         A       Z
 122  *             / \                       / \
 123  *            B   Z                     W   B
 124  *           / \                           / \
 125  *          X   Y                         X   Y
 126  */
 127 static void __cl_map_rot_left(IN cl_qmap_t * const p_map,
 128                               IN cl_map_item_t * const p_item)
 129 {
 130         cl_map_item_t **pp_root;
 131
 132         CL_ASSERT(p_map);
 133         CL_ASSERT(p_item);
 134         CL_ASSERT(p_item->p_right != &p_map->nil);
 135
 136         pp_root = __cl_map_get_parent_ptr_to_item(p_item);
 137
 138         /* Point R to C instead of A. */
 139         *pp_root = p_item->p_right;
 140         /* Set C's parent to R. */
 141         (*pp_root)->p_up = p_item->p_up;
 142
 143         /* Set A's right to B */
 144         p_item->p_right = (*pp_root)->p_left;
 145         /*
 146          * Set B's parent to A.  We trap for B being NIL since the
 147          * caller may depend on NIL not changing.
 148          */
 149         if ((*pp_root)->p_left != &p_map->nil)
 150                 (*pp_root)->p_left->p_up = p_item;
 151
 152         /* Set C's left to A. */
 153         (*pp_root)->p_left = p_item;
 154         /* Set A's parent to C. */
 155         p_item->p_up = *pp_root;
 156 }
 157
 158 /*
 159  * Rotate a node to the right.  This rotation affects the least number of links
 160  * between nodes and brings the level of A up by one while increasing the depth
 161  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.
 162  *
 163  *              R                                    R
 164  *              |                                    |
 165  *              C                                    A
 166  *            /   \                                /   \
 167  *          A       Z                    W       C
 168  *         / \                                          / \
 169  *        W   B                                        B   Z
 170  *           / \                                      / \
 171  *          X   Y                                    X   Y
 172  */
 173 static void __cl_map_rot_right(IN cl_qmap_t * const p_map,
 174                                IN cl_map_item_t * const p_item)
 175 {
 176         cl_map_item_t **pp_root;
 177
 178         CL_ASSERT(p_map);
 179         CL_ASSERT(p_item);
 180         CL_ASSERT(p_item->p_left != &p_map->nil);
 181
 182         /* Point R to A instead of C. */
 183         pp_root = __cl_map_get_parent_ptr_to_item(p_item);
 184         (*pp_root) = p_item->p_left;
 185         /* Set A's parent to R. */
 186         (*pp_root)->p_up = p_item->p_up;
 187
 188         /* Set C's left to B */
 189         p_item->p_left = (*pp_root)->p_right;
 190         /*
 191          * Set B's parent to C.  We trap for B being NIL since the
 192          * caller may depend on NIL not changing.
 193          */
 194         if ((*pp_root)->p_right != &p_map->nil)
 195                 (*pp_root)->p_right->p_up = p_item;
 196
 197         /* Set A's right to C. */
 198         (*pp_root)->p_right = p_item;
 199         /* Set C's parent to A. */
 200         p_item->p_up = *pp_root;
 201 }
 202
 203 void cl_qmap_init(IN cl_qmap_t * const p_map)
 204 {
 205         CL_ASSERT(p_map);
 206
 207         memset(p_map, 0, sizeof(cl_qmap_t));
 208
 209         /* special setup for the root node */
 210         p_map->root.p_up = &p_map->root;
 211         p_map->root.p_left = &p_map->nil;
 212         p_map->root.p_right = &p_map->nil;
 213         p_map->root.color = CL_MAP_BLACK;
 214
 215         /* Setup the node used as terminator for all leaves. */
 216         p_map->nil.p_up = &p_map->nil;
 217         p_map->nil.p_left = &p_map->nil;
 218         p_map->nil.p_right = &p_map->nil;
 219         p_map->nil.color = CL_MAP_BLACK;
 220
 221         p_map->state = CL_INITIALIZED;
 222
 223         cl_qmap_remove_all(p_map);
 224 }
 225
 226 cl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map,
 227                            IN const uint64_t key)
 228 {
 229         cl_map_item_t *p_item;
 230
 231         CL_ASSERT(p_map);
 232         CL_ASSERT(p_map->state == CL_INITIALIZED);
 233
 234         p_item = __cl_map_root(p_map);
 235
 236         while (p_item != &p_map->nil) {
 237                 if (key == p_item->key)
 238                         break;  /* just right */
 239
 240                 if (key < p_item->key)
 241                         p_item = p_item->p_left;        /* too small */
 242                 else
 243                         p_item = p_item->p_right;       /* too big */
 244         }
 245
 246         return (p_item);
 247 }
 248
 249 cl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map,
 250                                 IN const uint64_t key)
 251 {
 252         cl_map_item_t *p_item;
 253         cl_map_item_t *p_item_found;
 254
 255         CL_ASSERT(p_map);
 256         CL_ASSERT(p_map->state == CL_INITIALIZED);
 257
 258         p_item = __cl_map_root(p_map);
 259         p_item_found = (cl_map_item_t *) & p_map->nil;
 260
 261         while (p_item != &p_map->nil) {
 262                 if (key < p_item->key) {
 263                         p_item_found = p_item;
 264                         p_item = p_item->p_left;
 265                 } else {
 266                         p_item = p_item->p_right;
 267                 }
 268         }
 269
 270         return (p_item_found);
 271 }
 272
 273 void cl_qmap_apply_func(IN const cl_qmap_t * const p_map,
 274                         IN cl_pfn_qmap_apply_t pfn_func,
 275                         IN const void *const context)
 276 {
 277         cl_map_item_t *p_map_item;
 278
 279         /* Note that context can have any arbitrary value. */
 280         CL_ASSERT(p_map);
 281         CL_ASSERT(p_map->state == CL_INITIALIZED);
 282         CL_ASSERT(pfn_func);
 283
 284         p_map_item = cl_qmap_head(p_map);
 285         while (p_map_item != cl_qmap_end(p_map)) {
 286                 pfn_func(p_map_item, (void *)context);
 287                 p_map_item = cl_qmap_next(p_map_item);
 288         }
 289 }
 290
 291 /*
 292  * Balance a tree starting at a given item back to the root.
 293  */
 294 static void __cl_map_ins_bal(IN cl_qmap_t * const p_map,
 295                              IN cl_map_item_t * p_item)
 296 {
 297         cl_map_item_t *p_grand_uncle;
 298
 299         CL_ASSERT(p_map);
 300         CL_ASSERT(p_item);
 301         CL_ASSERT(p_item != &p_map->root);
 302
 303         while (p_item->p_up->color == CL_MAP_RED) {
 304                 if (__cl_map_is_left_child(p_item->p_up)) {
 305                         p_grand_uncle = p_item->p_up->p_up->p_right;
 306                         CL_ASSERT(p_grand_uncle);
 307                         if (p_grand_uncle->color == CL_MAP_RED) {
 308                                 p_grand_uncle->color = CL_MAP_BLACK;
 309                                 p_item->p_up->color = CL_MAP_BLACK;
 310                                 p_item->p_up->p_up->color = CL_MAP_RED;
 311                                 p_item = p_item->p_up->p_up;
 312                                 continue;
 313                         }
 314
 315                         if (!__cl_map_is_left_child(p_item)) {
 316                                 p_item = p_item->p_up;
 317                                 __cl_map_rot_left(p_map, p_item);
 318                         }
 319                         p_item->p_up->color = CL_MAP_BLACK;
 320                         p_item->p_up->p_up->color = CL_MAP_RED;
 321                         __cl_map_rot_right(p_map, p_item->p_up->p_up);
 322                 } else {
 323                         p_grand_uncle = p_item->p_up->p_up->p_left;
 324                         CL_ASSERT(p_grand_uncle);
 325                         if (p_grand_uncle->color == CL_MAP_RED) {
 326                                 p_grand_uncle->color = CL_MAP_BLACK;
 327                                 p_item->p_up->color = CL_MAP_BLACK;
 328                                 p_item->p_up->p_up->color = CL_MAP_RED;
 329                                 p_item = p_item->p_up->p_up;
 330                                 continue;
 331                         }
 332
 333                         if (__cl_map_is_left_child(p_item)) {
 334                                 p_item = p_item->p_up;
 335                                 __cl_map_rot_right(p_map, p_item);
 336                         }
 337                         p_item->p_up->color = CL_MAP_BLACK;
 338                         p_item->p_up->p_up->color = CL_MAP_RED;
 339                         __cl_map_rot_left(p_map, p_item->p_up->p_up);
 340                 }
 341         }
 342 }
 343
 344 cl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map,
 345                               IN const uint64_t key,
 346                               IN cl_map_item_t * const p_item)
 347 {
 348         cl_map_item_t *p_insert_at, *p_comp_item;
 349
 350         CL_ASSERT(p_map);
 351         CL_ASSERT(p_map->state == CL_INITIALIZED);
 352         CL_ASSERT(p_item);
 353         CL_ASSERT(p_map->root.p_up == &p_map->root);
 354         CL_ASSERT(p_map->root.color != CL_MAP_RED);
 355         CL_ASSERT(p_map->nil.color != CL_MAP_RED);
 356
 357         p_item->p_left = &p_map->nil;
 358         p_item->p_right = &p_map->nil;
 359         p_item->key = key;
 360         p_item->color = CL_MAP_RED;
 361
 362         /* Find the insertion location. */
 363         p_insert_at = &p_map->root;
 364         p_comp_item = __cl_map_root(p_map);
 365
 366         while (p_comp_item != &p_map->nil) {
 367                 p_insert_at = p_comp_item;
 368
 369                 if (key == p_insert_at->key)
 370                         return (p_insert_at);
 371
 372                 /* Traverse the tree until the correct insertion point is found. */
 373                 if (key < p_insert_at->key)
 374                         p_comp_item = p_insert_at->p_left;
 375                 else
 376                         p_comp_item = p_insert_at->p_right;
 377         }
 378
 379         CL_ASSERT(p_insert_at != &p_map->nil);
 380         CL_ASSERT(p_comp_item == &p_map->nil);
 381         /* Insert the item. */
 382         if (p_insert_at == &p_map->root) {
 383                 p_insert_at->p_left = p_item;
 384                 /*
 385                  * Primitive insert places the new item in front of
 386                  * the existing item.
 387                  */
 388                 __cl_primitive_insert(&p_map->nil.pool_item.list_item,
 389                                       &p_item->pool_item.list_item);
 390         } else if (key < p_insert_at->key) {
 391                 p_insert_at->p_left = p_item;
 392                 /*
 393                  * Primitive insert places the new item in front of
 394                  * the existing item.
 395                  */
 396                 __cl_primitive_insert(&p_insert_at->pool_item.list_item,
 397                                       &p_item->pool_item.list_item);
 398         } else {
 399                 p_insert_at->p_right = p_item;
 400                 /*
 401                  * Primitive insert places the new item in front of
 402                  * the existing item.
 403                  */
 404                 __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next,
 405                                       &p_item->pool_item.list_item);
 406         }
 407         /* Increase the count. */
 408         p_map->count++;
 409
 410         p_item->p_up = p_insert_at;
 411
 412         /*
 413          * We have added depth to this section of the tree.
 414          * Rebalance as necessary as we retrace our path through the tree
 415          * and update colors.
 416          */
 417         __cl_map_ins_bal(p_map, p_item);
 418
 419         __cl_map_root(p_map)->color = CL_MAP_BLACK;
 420
 421         /*
 422          * Note that it is not necessary to re-color the nil node black because all
 423          * red color assignments are made via the p_up pointer, and nil is never
 424          * set as the value of a p_up pointer.
 425          */
 426
 427 #ifdef _DEBUG_
 428         /* Set the pointer to the map in the map item for consistency checking. */
 429         p_item->p_map = p_map;
 430 #endif
 431
 432         return (p_item);
 433 }
 434
 435 static void __cl_map_del_bal(IN cl_qmap_t * const p_map,
 436                              IN cl_map_item_t * p_item)
 437 {
 438         cl_map_item_t *p_uncle;
 439
 440         while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) {
 441                 if (__cl_map_is_left_child(p_item)) {
 442                         p_uncle = p_item->p_up->p_right;
 443
 444                         if (p_uncle->color == CL_MAP_RED) {
 445                                 p_uncle->color = CL_MAP_BLACK;
 446                                 p_item->p_up->color = CL_MAP_RED;
 447                                 __cl_map_rot_left(p_map, p_item->p_up);
 448                                 p_uncle = p_item->p_up->p_right;
 449                         }
 450
 451                         if (p_uncle->p_right->color != CL_MAP_RED) {
 452                                 if (p_uncle->p_left->color != CL_MAP_RED) {
 453                                         p_uncle->color = CL_MAP_RED;
 454                                         p_item = p_item->p_up;
 455                                         continue;
 456                                 }
 457
 458                                 p_uncle->p_left->color = CL_MAP_BLACK;
 459                                 p_uncle->color = CL_MAP_RED;
 460                                 __cl_map_rot_right(p_map, p_uncle);
 461                                 p_uncle = p_item->p_up->p_right;
 462                         }
 463                         p_uncle->color = p_item->p_up->color;
 464                         p_item->p_up->color = CL_MAP_BLACK;
 465                         p_uncle->p_right->color = CL_MAP_BLACK;
 466                         __cl_map_rot_left(p_map, p_item->p_up);
 467                         break;
 468                 } else {
 469                         p_uncle = p_item->p_up->p_left;
 470
 471                         if (p_uncle->color == CL_MAP_RED) {
 472                                 p_uncle->color = CL_MAP_BLACK;
 473                                 p_item->p_up->color = CL_MAP_RED;
 474                                 __cl_map_rot_right(p_map, p_item->p_up);
 475                                 p_uncle = p_item->p_up->p_left;
 476                         }
 477
 478                         if (p_uncle->p_left->color != CL_MAP_RED) {
 479                                 if (p_uncle->p_right->color != CL_MAP_RED) {
 480                                         p_uncle->color = CL_MAP_RED;
 481                                         p_item = p_item->p_up;
 482                                         continue;
 483                                 }
 484
 485                                 p_uncle->p_right->color = CL_MAP_BLACK;
 486                                 p_uncle->color = CL_MAP_RED;
 487                                 __cl_map_rot_left(p_map, p_uncle);
 488                                 p_uncle = p_item->p_up->p_left;
 489                         }
 490                         p_uncle->color = p_item->p_up->color;
 491                         p_item->p_up->color = CL_MAP_BLACK;
 492                         p_uncle->p_left->color = CL_MAP_BLACK;
 493                         __cl_map_rot_right(p_map, p_item->p_up);
 494                         break;
 495                 }
 496         }
 497         p_item->color = CL_MAP_BLACK;
 498 }
 499
 500 void cl_qmap_remove_item(IN cl_qmap_t * const p_map,
 501                          IN cl_map_item_t * const p_item)
 502 {
 503         cl_map_item_t *p_child, *p_del_item;
 504
 505         CL_ASSERT(p_map);
 506         CL_ASSERT(p_map->state == CL_INITIALIZED);
 507         CL_ASSERT(p_item);
 508
 509         if (p_item == cl_qmap_end(p_map))
 510                 return;
 511
 512         /* must be checked after comparing to cl_qmap_end, since
 513            the end is not a valid item. */
 514         CL_ASSERT(p_item->p_map == p_map);
 515
 516         if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) {
 517                 /* The item being removed has children on at most on side. */
 518                 p_del_item = p_item;
 519         } else {
 520                 /*
 521                  * The item being removed has children on both side.
 522                  * We select the item that will replace it.  After removing
 523                  * the substitute item and rebalancing, the tree will have the
 524                  * correct topology.  Exchanging the substitute for the item
 525                  * will finalize the removal.
 526                  */
 527                 p_del_item = cl_qmap_next(p_item);
 528                 CL_ASSERT(p_del_item != &p_map->nil);
 529         }
 530
 531         /* Remove the item from the list. */
 532         __cl_primitive_remove(&p_item->pool_item.list_item);
 533         /* Decrement the item count. */
 534         p_map->count--;
 535
 536         /* Get the pointer to the new root's child, if any. */
 537         if (p_del_item->p_left != &p_map->nil)
 538                 p_child = p_del_item->p_left;
 539         else
 540                 p_child = p_del_item->p_right;
 541
 542         /*
 543          * This assignment may modify the parent pointer of the nil node.
 544          * This is inconsequential.
 545          */
 546         p_child->p_up = p_del_item->p_up;
 547         (*__cl_map_get_parent_ptr_to_item(p_del_item)) = p_child;
 548
 549         if (p_del_item->color != CL_MAP_RED)
 550                 __cl_map_del_bal(p_map, p_child);
 551
 552         /*
 553          * Note that the splicing done below does not need to occur before
 554          * the tree is balanced, since the actual topology changes are made by the
 555          * preceding code.  The topology is preserved by the color assignment made
 556          * below (reader should be reminded that p_del_item == p_item in some cases).
 557          */
 558         if (p_del_item != p_item) {
 559                 /*
 560                  * Finalize the removal of the specified item by exchanging it with
 561                  * the substitute which we removed above.
 562                  */
 563                 p_del_item->p_up = p_item->p_up;
 564                 p_del_item->p_left = p_item->p_left;
 565                 p_del_item->p_right = p_item->p_right;
 566                 (*__cl_map_get_parent_ptr_to_item(p_item)) = p_del_item;
 567                 p_item->p_right->p_up = p_del_item;
 568                 p_item->p_left->p_up = p_del_item;
 569                 p_del_item->color = p_item->color;
 570         }
 571
 572         CL_ASSERT(p_map->nil.color != CL_MAP_RED);
 573
 574 #ifdef _DEBUG_
 575         /* Clear the pointer to the map since the item has been removed. */
 576         p_item->p_map = NULL;
 577 #endif
 578 }
 579
 580 cl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, IN const uint64_t key)
 581 {
 582         cl_map_item_t *p_item;
 583
 584         CL_ASSERT(p_map);
 585         CL_ASSERT(p_map->state == CL_INITIALIZED);
 586
 587         /* Seek the node with the specified key */
 588         p_item = cl_qmap_get(p_map, key);
 589
 590         cl_qmap_remove_item(p_map, p_item);
 591
 592         return (p_item);
 593 }
 594
 595 void cl_qmap_merge(OUT cl_qmap_t * const p_dest_map,
 596                    IN OUT cl_qmap_t * const p_src_map)
 597 {
 598         cl_map_item_t *p_item, *p_item2, *p_next;
 599
 600         CL_ASSERT(p_dest_map);
 601         CL_ASSERT(p_src_map);
 602
 603         p_item = cl_qmap_head(p_src_map);
 604
 605         while (p_item != cl_qmap_end(p_src_map)) {
 606                 p_next = cl_qmap_next(p_item);
 607
 608                 /* Remove the item from its current map. */
 609                 cl_qmap_remove_item(p_src_map, p_item);
 610                 /* Insert the item into the destination map. */
 611                 p_item2 =
 612                     cl_qmap_insert(p_dest_map, cl_qmap_key(p_item), p_item);
 613                 /* Check that the item was successfully inserted. */
 614                 if (p_item2 != p_item) {
 615                         /* Put the item in back in the source map. */
 616                         p_item2 =
 617                             cl_qmap_insert(p_src_map, cl_qmap_key(p_item),
 618                                            p_item);
 619                         CL_ASSERT(p_item2 == p_item);
 620                 }
 621                 p_item = p_next;
 622         }
 623 }
 624
 625 static void __cl_qmap_delta_move(IN OUT cl_qmap_t * const p_dest,
 626                                  IN OUT cl_qmap_t * const p_src,
 627                                  IN OUT cl_map_item_t ** const pp_item)
 628 {
 629         cl_map_item_t __attribute__((__unused__)) *p_temp;
 630         cl_map_item_t *p_next;
 631
 632         /*
 633          * Get the next item so that we can ensure that pp_item points to
 634          * a valid item upon return from the function.
 635          */
 636         p_next = cl_qmap_next(*pp_item);
 637         /* Move the old item from its current map the the old map. */
 638         cl_qmap_remove_item(p_src, *pp_item);
 639         p_temp = cl_qmap_insert(p_dest, cl_qmap_key(*pp_item), *pp_item);
 640         /* We should never have duplicates. */
 641         CL_ASSERT(p_temp == *pp_item);
 642         /* Point pp_item to a valid item in the source map. */
 643         (*pp_item) = p_next;
 644 }
 645
 646 void cl_qmap_delta(IN OUT cl_qmap_t * const p_map1,
 647                    IN OUT cl_qmap_t * const p_map2,
 648                    OUT cl_qmap_t * const p_new, OUT cl_qmap_t * const p_old)
 649 {
 650         cl_map_item_t *p_item1, *p_item2;
 651         uint64_t key1, key2;
 652
 653         CL_ASSERT(p_map1);
 654         CL_ASSERT(p_map2);
 655         CL_ASSERT(p_new);
 656         CL_ASSERT(p_old);
 657         CL_ASSERT(cl_is_qmap_empty(p_new));
 658         CL_ASSERT(cl_is_qmap_empty(p_old));
 659
 660         p_item1 = cl_qmap_head(p_map1);
 661         p_item2 = cl_qmap_head(p_map2);
 662
 663         while (p_item1 != cl_qmap_end(p_map1) && p_item2 != cl_qmap_end(p_map2)) {
 664                 key1 = cl_qmap_key(p_item1);
 665                 key2 = cl_qmap_key(p_item2);
 666                 if (key1 < key2) {
 667                         /* We found an old item. */
 668                         __cl_qmap_delta_move(p_old, p_map1, &p_item1);
 669                 } else if (key1 > key2) {
 670                         /* We found a new item. */
 671                         __cl_qmap_delta_move(p_new, p_map2, &p_item2);
 672                 } else {
 673                         /* Move both forward since they have the same key. */
 674                         p_item1 = cl_qmap_next(p_item1);
 675                         p_item2 = cl_qmap_next(p_item2);
 676                 }
 677         }
 678
 679         /* Process the remainder if the end of either source map was reached. */
 680         while (p_item2 != cl_qmap_end(p_map2))
 681                 __cl_qmap_delta_move(p_new, p_map2, &p_item2);
 682
 683         while (p_item1 != cl_qmap_end(p_map1))
 684                 __cl_qmap_delta_move(p_old, p_map1, &p_item1);
 685 }
 686
 687 /******************************************************************************
 688  IMPLEMENTATION OF MAP
 689 ******************************************************************************/
 690
 691 #define MAP_GROW_SIZE 32
 692
 693 void cl_map_construct(IN cl_map_t * const p_map)
 694 {
 695         CL_ASSERT(p_map);
 696
 697         cl_qpool_construct(&p_map->pool);
 698 }
 699
 700 cl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items)
 701 {
 702         uint32_t grow_size;
 703
 704         CL_ASSERT(p_map);
 705
 706         cl_qmap_init(&p_map->qmap);
 707
 708         /*
 709          * We will grow by min_items/8 items at a time, with a minimum of
 710          * MAP_GROW_SIZE.
 711          */
 712         grow_size = min_items >> 3;
 713         if (grow_size < MAP_GROW_SIZE)
 714                 grow_size = MAP_GROW_SIZE;
 715
 716         return (cl_qpool_init(&p_map->pool, min_items, 0, grow_size,
 717                               sizeof(cl_map_obj_t), NULL, NULL, NULL));
 718 }
 719
 720 void cl_map_destroy(IN cl_map_t * const p_map)
 721 {
 722         CL_ASSERT(p_map);
 723
 724         cl_qpool_destroy(&p_map->pool);
 725 }
 726
 727 void *cl_map_insert(IN cl_map_t * const p_map,
 728                     IN const uint64_t key, IN const void *const p_object)
 729 {
 730         cl_map_obj_t *p_map_obj, *p_obj_at_key;
 731
 732         CL_ASSERT(p_map);
 733
 734         p_map_obj = (cl_map_obj_t *) cl_qpool_get(&p_map->pool);
 735
 736         if (!p_map_obj)
 737                 return (NULL);
 738
 739         cl_qmap_set_obj(p_map_obj, p_object);
 740
 741         p_obj_at_key =
 742             (cl_map_obj_t *) cl_qmap_insert(&p_map->qmap, key,
 743                                             &p_map_obj->item);
 744
 745         /* Return the item to the pool if insertion failed. */
 746         if (p_obj_at_key != p_map_obj)
 747                 cl_qpool_put(&p_map->pool, &p_map_obj->item.pool_item);
 748
 749         return (cl_qmap_obj(p_obj_at_key));
 750 }
 751
 752 void *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key)
 753 {
 754         cl_map_item_t *p_item;
 755
 756         CL_ASSERT(p_map);
 757
 758         p_item = cl_qmap_get(&p_map->qmap, key);
 759
 760         if (p_item == cl_qmap_end(&p_map->qmap))
 761                 return (NULL);
 762
 763         return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item)));
 764 }
 765
 766 void *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key)
 767 {
 768         cl_map_item_t *p_item;
 769
 770         CL_ASSERT(p_map);
 771
 772         p_item = cl_qmap_get_next(&p_map->qmap, key);
 773
 774         if (p_item == cl_qmap_end(&p_map->qmap))
 775                 return (NULL);
 776
 777         return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item)));
 778 }
 779
 780 void cl_map_remove_item(IN cl_map_t * const p_map,
 781                         IN const cl_map_iterator_t itor)
 782 {
 783         CL_ASSERT(itor->p_map == &p_map->qmap);
 784
 785         if (itor == cl_map_end(p_map))
 786                 return;
 787
 788         cl_qmap_remove_item(&p_map->qmap, (cl_map_item_t *) itor);
 789         cl_qpool_put(&p_map->pool, &((cl_map_item_t *) itor)->pool_item);
 790 }
 791
 792 void *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key)
 793 {
 794         cl_map_item_t *p_item;
 795         void *p_obj;
 796
 797         CL_ASSERT(p_map);
 798
 799         p_item = cl_qmap_remove(&p_map->qmap, key);
 800
 801         if (p_item == cl_qmap_end(&p_map->qmap))
 802                 return (NULL);
 803
 804         p_obj = cl_qmap_obj((cl_map_obj_t *) p_item);
 805         cl_qpool_put(&p_map->pool, &p_item->pool_item);
 806
 807         return (p_obj);
 808 }
 809
 810 void cl_map_remove_all(IN cl_map_t * const p_map)
 811 {
 812         cl_map_item_t *p_item;
 813
 814         CL_ASSERT(p_map);
 815
 816         /* Return all map items to the pool. */
 817         while (!cl_is_qmap_empty(&p_map->qmap)) {
 818                 p_item = cl_qmap_head(&p_map->qmap);
 819                 cl_qmap_remove_item(&p_map->qmap, p_item);
 820                 cl_qpool_put(&p_map->pool, &p_item->pool_item);
 821
 822                 if (!cl_is_qmap_empty(&p_map->qmap)) {
 823                         p_item = cl_qmap_tail(&p_map->qmap);
 824                         cl_qmap_remove_item(&p_map->qmap, p_item);
 825                         cl_qpool_put(&p_map->pool, &p_item->pool_item);
 826                 }
 827         }
 828 }
 829
 830 cl_status_t cl_map_merge(OUT cl_map_t * const p_dest_map,
 831                          IN OUT cl_map_t * const p_src_map)
 832 {
 833         cl_status_t status = CL_SUCCESS;
 834         cl_map_iterator_t itor, next;
 835         uint64_t key;
 836         void *p_obj, *p_obj2;
 837
 838         CL_ASSERT(p_dest_map);
 839         CL_ASSERT(p_src_map);
 840
 841         itor = cl_map_head(p_src_map);
 842         while (itor != cl_map_end(p_src_map)) {
 843                 next = cl_map_next(itor);
 844
 845                 p_obj = cl_map_obj(itor);
 846                 key = cl_map_key(itor);
 847
 848                 cl_map_remove_item(p_src_map, itor);
 849
 850                 /* Insert the object into the destination map. */
 851                 p_obj2 = cl_map_insert(p_dest_map, key, p_obj);
 852                 /* Trap for failure. */
 853                 if (p_obj != p_obj2) {
 854                         if (!p_obj2)
 855                                 status = CL_INSUFFICIENT_MEMORY;
 856                         /* Put the object back in the source map.  This must succeed. */
 857                         p_obj2 = cl_map_insert(p_src_map, key, p_obj);
 858                         CL_ASSERT(p_obj == p_obj2);
 859                         /* If the failure was due to insufficient memory, return. */
 860                         if (status != CL_SUCCESS)
 861                                 return (status);
 862                 }
 863                 itor = next;
 864         }
 865
 866         return (CL_SUCCESS);
 867 }
 868
 869 static void __cl_map_revert(IN OUT cl_map_t * const p_map1,
 870                             IN OUT cl_map_t * const p_map2,
 871                             IN OUT cl_map_t * const p_new,
 872                             IN OUT cl_map_t * const p_old)
 873 {
 874         cl_status_t __attribute__((__unused__)) status;
 875
 876         /* Restore the initial state. */
 877         status = cl_map_merge(p_map1, p_old);
 878         CL_ASSERT(status == CL_SUCCESS);
 879         status = cl_map_merge(p_map2, p_new);
 880         CL_ASSERT(status == CL_SUCCESS);
 881 }
 882
 883 static cl_status_t __cl_map_delta_move(OUT cl_map_t * const p_dest,
 884                                        IN OUT cl_map_t * const p_src,
 885                                        IN OUT cl_map_iterator_t * const p_itor)
 886 {
 887         cl_map_iterator_t next;
 888         void *p_obj, *p_obj2;
 889         uint64_t key;
 890
 891         /* Get a valid iterator so we can continue the loop. */
 892         next = cl_map_next(*p_itor);
 893         /* Get the pointer to the object for insertion. */
 894         p_obj = cl_map_obj(*p_itor);
 895         /* Get the key for the object. */
 896         key = cl_map_key(*p_itor);
 897         /* Move the object. */
 898         cl_map_remove_item(p_src, *p_itor);
 899         p_obj2 = cl_map_insert(p_dest, key, p_obj);
 900         /* Check for failure. We should never get a duplicate. */
 901         if (!p_obj2) {
 902                 p_obj2 = cl_map_insert(p_src, key, p_obj);
 903                 CL_ASSERT(p_obj2 == p_obj);
 904                 return (CL_INSUFFICIENT_MEMORY);
 905         }
 906
 907         /* We should never get a duplicate */
 908         CL_ASSERT(p_obj == p_obj2);
 909         /* Update the iterator so that it is valid. */
 910         (*p_itor) = next;
 911
 912         return (CL_SUCCESS);
 913 }
 914
 915 cl_status_t cl_map_delta(IN OUT cl_map_t * const p_map1,
 916                          IN OUT cl_map_t * const p_map2,
 917                          OUT cl_map_t * const p_new, OUT cl_map_t * const p_old)
 918 {
 919         cl_map_iterator_t itor1, itor2;
 920         uint64_t key1, key2;
 921         cl_status_t status;
 922
 923         CL_ASSERT(p_map1);
 924         CL_ASSERT(p_map2);
 925         CL_ASSERT(p_new);
 926         CL_ASSERT(p_old);
 927         CL_ASSERT(cl_is_map_empty(p_new));
 928         CL_ASSERT(cl_is_map_empty(p_old));
 929
 930         itor1 = cl_map_head(p_map1);
 931         itor2 = cl_map_head(p_map2);
 932
 933         /*
 934          * Note that the check is for the end, since duplicate items will remain
 935          * in their respective maps.
 936          */
 937         while (itor1 != cl_map_end(p_map1) && itor2 != cl_map_end(p_map2)) {
 938                 key1 = cl_map_key(itor1);
 939                 key2 = cl_map_key(itor2);
 940                 if (key1 < key2) {
 941                         status = __cl_map_delta_move(p_old, p_map1, &itor1);
 942                         /* Check for failure. */
 943                         if (status != CL_SUCCESS) {
 944                                 /* Restore the initial state. */
 945                                 __cl_map_revert(p_map1, p_map2, p_new, p_old);
 946                                 /* Return the failure status. */
 947                                 return (status);
 948                         }
 949                 } else if (key1 > key2) {
 950                         status = __cl_map_delta_move(p_new, p_map2, &itor2);
 951                         if (status != CL_SUCCESS) {
 952                                 /* Restore the initial state. */
 953                                 __cl_map_revert(p_map1, p_map2, p_new, p_old);
 954                                 /* Return the failure status. */
 955                                 return (status);
 956                         }
 957                 } else {
 958                         /* Move both forward since they have the same key. */
 959                         itor1 = cl_map_next(itor1);
 960                         itor2 = cl_map_next(itor2);
 961                 }
 962         }
 963
 964         /* Process the remainder if either source map is empty. */
 965         while (itor2 != cl_map_end(p_map2)) {
 966                 status = __cl_map_delta_move(p_new, p_map2, &itor2);
 967                 if (status != CL_SUCCESS) {
 968                         /* Restore the initial state. */
 969                         __cl_map_revert(p_map1, p_map2, p_new, p_old);
 970                         /* Return the failure status. */
 971                         return (status);
 972                 }
 973         }
 974
 975         while (itor1 != cl_map_end(p_map1)) {
 976                 status = __cl_map_delta_move(p_old, p_map1, &itor1);
 977                 if (status != CL_SUCCESS) {
 978                         /* Restore the initial state. */
 979                         __cl_map_revert(p_map1, p_map2, p_new, p_old);
 980                         /* Return the failure status. */
 981                         return (status);
 982                 }
 983         }
 984
 985         return (CL_SUCCESS);
 986 }
 987
 988 /******************************************************************************
 989  IMPLEMENTATION OF FLEXI MAP
 990 ******************************************************************************/
 991
 992 /*
 993  * Get the root.
 994  */
 995 static inline cl_fmap_item_t *__cl_fmap_root(IN const cl_fmap_t * const p_map)
 996 {
 997         CL_ASSERT(p_map);
 998         return (p_map->root.p_left);
 999 }
1000
1001 /*
1002  * Returns whether a given item is on the left of its parent.
1003  */
1004 static boolean_t __cl_fmap_is_left_child(IN const cl_fmap_item_t * const p_item)
1005 {
1006         CL_ASSERT(p_item);
1007         CL_ASSERT(p_item->p_up);
1008         CL_ASSERT(p_item->p_up != p_item);
1009
1010         return (p_item->p_up->p_left == p_item);
1011 }
1012
1013 /*
1014  * Retrieve the pointer to the parent's pointer to an item.
1015  */
1016 static cl_fmap_item_t **__cl_fmap_get_parent_ptr_to_item(IN cl_fmap_item_t *
1017                                                          const p_item)
1018 {
1019         CL_ASSERT(p_item);
1020         CL_ASSERT(p_item->p_up);
1021         CL_ASSERT(p_item->p_up != p_item);
1022
1023         if (__cl_fmap_is_left_child(p_item))
1024                 return (&p_item->p_up->p_left);
1025
1026         CL_ASSERT(p_item->p_up->p_right == p_item);
1027         return (&p_item->p_up->p_right);
1028 }
1029
1030 /*
1031  * Rotate a node to the left.  This rotation affects the least number of links
1032  * between nodes and brings the level of C up by one while increasing the depth
1033  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.
1034  *
1035  *          R                                 R
1036  *          |                                 |
1037  *          A                                 C
1038  *        /   \                         /   \
1039  *      W       C                         A       Z
1040  *             / \                       / \
1041  *            B   Z                     W   B
1042  *           / \                           / \
1043  *          X   Y                         X   Y
1044  */
1045 static void __cl_fmap_rot_left(IN cl_fmap_t * const p_map,
1046                                IN cl_fmap_item_t * const p_item)
1047 {
1048         cl_fmap_item_t **pp_root;
1049
1050         CL_ASSERT(p_map);
1051         CL_ASSERT(p_item);
1052         CL_ASSERT(p_item->p_right != &p_map->nil);
1053
1054         pp_root = __cl_fmap_get_parent_ptr_to_item(p_item);
1055
1056         /* Point R to C instead of A. */
1057         *pp_root = p_item->p_right;
1058         /* Set C's parent to R. */
1059         (*pp_root)->p_up = p_item->p_up;
1060
1061         /* Set A's right to B */
1062         p_item->p_right = (*pp_root)->p_left;
1063         /*
1064          * Set B's parent to A.  We trap for B being NIL since the
1065          * caller may depend on NIL not changing.
1066          */
1067         if ((*pp_root)->p_left != &p_map->nil)
1068                 (*pp_root)->p_left->p_up = p_item;
1069
1070         /* Set C's left to A. */
1071         (*pp_root)->p_left = p_item;
1072         /* Set A's parent to C. */
1073         p_item->p_up = *pp_root;
1074 }
1075
1076 /*
1077  * Rotate a node to the right.  This rotation affects the least number of links
1078  * between nodes and brings the level of A up by one while increasing the depth
1079  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.
1080  *
1081  *              R                                    R
1082  *              |                                    |
1083  *              C                                    A
1084  *            /   \                                /   \
1085  *          A       Z                    W       C
1086  *         / \                                          / \
1087  *        W   B                                        B   Z
1088  *           / \                                      / \
1089  *          X   Y                                    X   Y
1090  */
1091 static void __cl_fmap_rot_right(IN cl_fmap_t * const p_map,
1092                                 IN cl_fmap_item_t * const p_item)
1093 {
1094         cl_fmap_item_t **pp_root;
1095
1096         CL_ASSERT(p_map);
1097         CL_ASSERT(p_item);
1098         CL_ASSERT(p_item->p_left != &p_map->nil);
1099
1100         /* Point R to A instead of C. */
1101         pp_root = __cl_fmap_get_parent_ptr_to_item(p_item);
1102         (*pp_root) = p_item->p_left;
1103         /* Set A's parent to R. */
1104         (*pp_root)->p_up = p_item->p_up;
1105
1106         /* Set C's left to B */
1107         p_item->p_left = (*pp_root)->p_right;
1108         /*
1109          * Set B's parent to C.  We trap for B being NIL since the
1110          * caller may depend on NIL not changing.
1111          */
1112         if ((*pp_root)->p_right != &p_map->nil)
1113                 (*pp_root)->p_right->p_up = p_item;
1114
1115         /* Set A's right to C. */
1116         (*pp_root)->p_right = p_item;
1117         /* Set C's parent to A. */
1118         p_item->p_up = *pp_root;
1119 }
1120
1121 void cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare)
1122 {
1123         CL_ASSERT(p_map);
1124         CL_ASSERT(pfn_compare);
1125
1126         memset(p_map, 0, sizeof(cl_fmap_t));
1127
1128         /* special setup for the root node */
1129         p_map->root.p_up = &p_map->root;
1130         p_map->root.p_left = &p_map->nil;
1131         p_map->root.p_right = &p_map->nil;
1132         p_map->root.color = CL_MAP_BLACK;
1133
1134         /* Setup the node used as terminator for all leaves. */
1135         p_map->nil.p_up = &p_map->nil;
1136         p_map->nil.p_left = &p_map->nil;
1137         p_map->nil.p_right = &p_map->nil;
1138         p_map->nil.color = CL_MAP_BLACK;
1139
1140         /* Store the compare function pointer. */
1141         p_map->pfn_compare = pfn_compare;
1142
1143         p_map->state = CL_INITIALIZED;
1144
1145         cl_fmap_remove_all(p_map);
1146 }
1147
1148 cl_fmap_item_t *cl_fmap_match(IN const cl_fmap_t * const p_map,
1149                               IN const void *const p_key,
1150                               IN cl_pfn_fmap_cmp_t pfn_compare)
1151 {
1152         cl_fmap_item_t *p_item;
1153         int cmp;
1154
1155         CL_ASSERT(p_map);
1156         CL_ASSERT(p_map->state == CL_INITIALIZED);
1157
1158         p_item = __cl_fmap_root(p_map);
1159
1160         while (p_item != &p_map->nil) {
1161                 cmp = pfn_compare ? pfn_compare(p_key, p_item->p_key) :
1162                         p_map->pfn_compare(p_key, p_item->p_key);
1163
1164                 if (!cmp)
1165                         break;  /* just right */
1166
1167                 if (cmp < 0)
1168                         p_item = p_item->p_left;        /* too small */
1169                 else
1170                         p_item = p_item->p_right;       /* too big */
1171         }
1172
1173         return (p_item);
1174 }
1175
1176 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map,
1177                             IN const void *const p_key)
1178 {
1179         return cl_fmap_match(p_map, p_key, p_map->pfn_compare);
1180 }
1181
1182 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map,
1183                                  IN const void *const p_key)
1184 {
1185         cl_fmap_item_t *p_item;
1186         cl_fmap_item_t *p_item_found;
1187         int cmp;
1188
1189         CL_ASSERT(p_map);
1190         CL_ASSERT(p_map->state == CL_INITIALIZED);
1191
1192         p_item = __cl_fmap_root(p_map);
1193         p_item_found = (cl_fmap_item_t *) & p_map->nil;
1194
1195         while (p_item != &p_map->nil) {
1196                 cmp = p_map->pfn_compare(p_key, p_item->p_key);
1197
1198                 if (cmp < 0) {
1199                         p_item_found = p_item;
1200                         p_item = p_item->p_left;        /* too small */
1201                 } else {
1202                         p_item = p_item->p_right;       /* too big or match */
1203                 }
1204         }
1205
1206         return (p_item_found);
1207 }
1208
1209 void cl_fmap_apply_func(IN const cl_fmap_t * const p_map,
1210                         IN cl_pfn_fmap_apply_t pfn_func,
1211                         IN const void *const context)
1212 {
1213         cl_fmap_item_t *p_fmap_item;
1214
1215         /* Note that context can have any arbitrary value. */
1216         CL_ASSERT(p_map);
1217         CL_ASSERT(p_map->state == CL_INITIALIZED);
1218         CL_ASSERT(pfn_func);
1219
1220         p_fmap_item = cl_fmap_head(p_map);
1221         while (p_fmap_item != cl_fmap_end(p_map)) {
1222                 pfn_func(p_fmap_item, (void *)context);
1223                 p_fmap_item = cl_fmap_next(p_fmap_item);
1224         }
1225 }
1226
1227 /*
1228  * Balance a tree starting at a given item back to the root.
1229  */
1230 static void __cl_fmap_ins_bal(IN cl_fmap_t * const p_map,
1231                               IN cl_fmap_item_t * p_item)
1232 {
1233         cl_fmap_item_t *p_grand_uncle;
1234
1235         CL_ASSERT(p_map);
1236         CL_ASSERT(p_item);
1237         CL_ASSERT(p_item != &p_map->root);
1238
1239         while (p_item->p_up->color == CL_MAP_RED) {
1240                 if (__cl_fmap_is_left_child(p_item->p_up)) {
1241                         p_grand_uncle = p_item->p_up->p_up->p_right;
1242                         CL_ASSERT(p_grand_uncle);
1243                         if (p_grand_uncle->color == CL_MAP_RED) {
1244                                 p_grand_uncle->color = CL_MAP_BLACK;
1245                                 p_item->p_up->color = CL_MAP_BLACK;
1246                                 p_item->p_up->p_up->color = CL_MAP_RED;
1247                                 p_item = p_item->p_up->p_up;
1248                                 continue;
1249                         }
1250
1251                         if (!__cl_fmap_is_left_child(p_item)) {
1252                                 p_item = p_item->p_up;
1253                                 __cl_fmap_rot_left(p_map, p_item);
1254                         }
1255                         p_item->p_up->color = CL_MAP_BLACK;
1256                         p_item->p_up->p_up->color = CL_MAP_RED;
1257                         __cl_fmap_rot_right(p_map, p_item->p_up->p_up);
1258                 } else {
1259                         p_grand_uncle = p_item->p_up->p_up->p_left;
1260                         CL_ASSERT(p_grand_uncle);
1261                         if (p_grand_uncle->color == CL_MAP_RED) {
1262                                 p_grand_uncle->color = CL_MAP_BLACK;
1263                                 p_item->p_up->color = CL_MAP_BLACK;
1264                                 p_item->p_up->p_up->color = CL_MAP_RED;
1265                                 p_item = p_item->p_up->p_up;
1266                                 continue;
1267                         }
1268
1269                         if (__cl_fmap_is_left_child(p_item)) {
1270                                 p_item = p_item->p_up;
1271                                 __cl_fmap_rot_right(p_map, p_item);
1272                         }
1273                         p_item->p_up->color = CL_MAP_BLACK;
1274                         p_item->p_up->p_up->color = CL_MAP_RED;
1275                         __cl_fmap_rot_left(p_map, p_item->p_up->p_up);
1276                 }
1277         }
1278 }
1279
1280 cl_fmap_item_t *cl_fmap_insert(IN cl_fmap_t * const p_map,
1281                                IN const void *const p_key,
1282                                IN cl_fmap_item_t * const p_item)
1283 {
1284         cl_fmap_item_t *p_insert_at, *p_comp_item;
1285         int cmp = 0;
1286
1287         CL_ASSERT(p_map);
1288         CL_ASSERT(p_map->state == CL_INITIALIZED);
1289         CL_ASSERT(p_item);
1290         CL_ASSERT(p_map->root.p_up == &p_map->root);
1291         CL_ASSERT(p_map->root.color != CL_MAP_RED);
1292         CL_ASSERT(p_map->nil.color != CL_MAP_RED);
1293
1294         p_item->p_left = &p_map->nil;
1295         p_item->p_right = &p_map->nil;
1296         p_item->p_key = p_key;
1297         p_item->color = CL_MAP_RED;
1298
1299         /* Find the insertion location. */
1300         p_insert_at = &p_map->root;
1301         p_comp_item = __cl_fmap_root(p_map);
1302
1303         while (p_comp_item != &p_map->nil) {
1304                 p_insert_at = p_comp_item;
1305
1306                 cmp = p_map->pfn_compare(p_key, p_insert_at->p_key);
1307
1308                 if (!cmp)
1309                         return (p_insert_at);
1310
1311                 /* Traverse the tree until the correct insertion point is found. */
1312                 if (cmp < 0)
1313                         p_comp_item = p_insert_at->p_left;
1314                 else
1315                         p_comp_item = p_insert_at->p_right;
1316         }
1317
1318         CL_ASSERT(p_insert_at != &p_map->nil);
1319         CL_ASSERT(p_comp_item == &p_map->nil);
1320         /* Insert the item. */
1321         if (p_insert_at == &p_map->root) {
1322                 p_insert_at->p_left = p_item;
1323                 /*
1324                  * Primitive insert places the new item in front of
1325                  * the existing item.
1326                  */
1327                 __cl_primitive_insert(&p_map->nil.pool_item.list_item,
1328                                       &p_item->pool_item.list_item);
1329         } else if (cmp < 0) {
1330                 p_insert_at->p_left = p_item;
1331                 /*
1332                  * Primitive insert places the new item in front of
1333                  * the existing item.
1334                  */
1335                 __cl_primitive_insert(&p_insert_at->pool_item.list_item,
1336                                       &p_item->pool_item.list_item);
1337         } else {
1338                 p_insert_at->p_right = p_item;
1339                 /*
1340                  * Primitive insert places the new item in front of
1341                  * the existing item.
1342                  */
1343                 __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next,
1344                                       &p_item->pool_item.list_item);
1345         }
1346         /* Increase the count. */
1347         p_map->count++;
1348
1349         p_item->p_up = p_insert_at;
1350
1351         /*
1352          * We have added depth to this section of the tree.
1353          * Rebalance as necessary as we retrace our path through the tree
1354          * and update colors.
1355          */
1356         __cl_fmap_ins_bal(p_map, p_item);
1357
1358         __cl_fmap_root(p_map)->color = CL_MAP_BLACK;
1359
1360         /*
1361          * Note that it is not necessary to re-color the nil node black because all
1362          * red color assignments are made via the p_up pointer, and nil is never
1363          * set as the value of a p_up pointer.
1364          */
1365
1366 #ifdef _DEBUG_
1367         /* Set the pointer to the map in the map item for consistency checking. */
1368         p_item->p_map = p_map;
1369 #endif
1370
1371         return (p_item);
1372 }
1373
1374 static void __cl_fmap_del_bal(IN cl_fmap_t * const p_map,
1375                               IN cl_fmap_item_t * p_item)
1376 {
1377         cl_fmap_item_t *p_uncle;
1378
1379         while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) {
1380                 if (__cl_fmap_is_left_child(p_item)) {
1381                         p_uncle = p_item->p_up->p_right;
1382
1383                         if (p_uncle->color == CL_MAP_RED) {
1384                                 p_uncle->color = CL_MAP_BLACK;
1385                                 p_item->p_up->color = CL_MAP_RED;
1386                                 __cl_fmap_rot_left(p_map, p_item->p_up);
1387                                 p_uncle = p_item->p_up->p_right;
1388                         }
1389
1390                         if (p_uncle->p_right->color != CL_MAP_RED) {
1391                                 if (p_uncle->p_left->color != CL_MAP_RED) {
1392                                         p_uncle->color = CL_MAP_RED;
1393                                         p_item = p_item->p_up;
1394                                         continue;
1395                                 }
1396
1397                                 p_uncle->p_left->color = CL_MAP_BLACK;
1398                                 p_uncle->color = CL_MAP_RED;
1399                                 __cl_fmap_rot_right(p_map, p_uncle);
1400                                 p_uncle = p_item->p_up->p_right;
1401                         }
1402                         p_uncle->color = p_item->p_up->color;
1403                         p_item->p_up->color = CL_MAP_BLACK;
1404                         p_uncle->p_right->color = CL_MAP_BLACK;
1405                         __cl_fmap_rot_left(p_map, p_item->p_up);
1406                         break;
1407                 } else {
1408                         p_uncle = p_item->p_up->p_left;
1409
1410                         if (p_uncle->color == CL_MAP_RED) {
1411                                 p_uncle->color = CL_MAP_BLACK;
1412                                 p_item->p_up->color = CL_MAP_RED;
1413                                 __cl_fmap_rot_right(p_map, p_item->p_up);
1414                                 p_uncle = p_item->p_up->p_left;
1415                         }
1416
1417                         if (p_uncle->p_left->color != CL_MAP_RED) {
1418                                 if (p_uncle->p_right->color != CL_MAP_RED) {
1419                                         p_uncle->color = CL_MAP_RED;
1420                                         p_item = p_item->p_up;
1421                                         continue;
1422                                 }
1423
1424                                 p_uncle->p_right->color = CL_MAP_BLACK;
1425                                 p_uncle->color = CL_MAP_RED;
1426                                 __cl_fmap_rot_left(p_map, p_uncle);
1427                                 p_uncle = p_item->p_up->p_left;
1428                         }
1429                         p_uncle->color = p_item->p_up->color;
1430                         p_item->p_up->color = CL_MAP_BLACK;
1431                         p_uncle->p_left->color = CL_MAP_BLACK;
1432                         __cl_fmap_rot_right(p_map, p_item->p_up);
1433                         break;
1434                 }
1435         }
1436         p_item->color = CL_MAP_BLACK;
1437 }
1438
1439 void cl_fmap_remove_item(IN cl_fmap_t * const p_map,
1440                          IN cl_fmap_item_t * const p_item)
1441 {
1442         cl_fmap_item_t *p_child, *p_del_item;
1443
1444         CL_ASSERT(p_map);
1445         CL_ASSERT(p_map->state == CL_INITIALIZED);
1446         CL_ASSERT(p_item);
1447         CL_ASSERT(p_item->p_map == p_map);
1448
1449         if (p_item == cl_fmap_end(p_map))
1450                 return;
1451
1452         if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) {
1453                 /* The item being removed has children on at most on side. */
1454                 p_del_item = p_item;
1455         } else {
1456                 /*
1457                  * The item being removed has children on both side.
1458                  * We select the item that will replace it.  After removing
1459                  * the substitute item and rebalancing, the tree will have the
1460                  * correct topology.  Exchanging the substitute for the item
1461                  * will finalize the removal.
1462                  */
1463                 p_del_item = cl_fmap_next(p_item);
1464                 CL_ASSERT(p_del_item != &p_map->nil);
1465         }
1466
1467         /* Remove the item from the list. */
1468         __cl_primitive_remove(&p_item->pool_item.list_item);
1469         /* Decrement the item count. */
1470         p_map->count--;
1471
1472         /* Get the pointer to the new root's child, if any. */
1473         if (p_del_item->p_left != &p_map->nil)
1474                 p_child = p_del_item->p_left;
1475         else
1476                 p_child = p_del_item->p_right;
1477
1478         /*
1479          * This assignment may modify the parent pointer of the nil node.
1480          * This is inconsequential.
1481          */
1482         p_child->p_up = p_del_item->p_up;
1483         (*__cl_fmap_get_parent_ptr_to_item(p_del_item)) = p_child;
1484
1485         if (p_del_item->color != CL_MAP_RED)
1486                 __cl_fmap_del_bal(p_map, p_child);
1487
1488         /*
1489          * Note that the splicing done below does not need to occur before
1490          * the tree is balanced, since the actual topology changes are made by the
1491          * preceding code.  The topology is preserved by the color assignment made
1492          * below (reader should be reminded that p_del_item == p_item in some cases).
1493          */
1494         if (p_del_item != p_item) {
1495                 /*
1496                  * Finalize the removal of the specified item by exchanging it with
1497                  * the substitute which we removed above.
1498                  */
1499                 p_del_item->p_up = p_item->p_up;
1500                 p_del_item->p_left = p_item->p_left;
1501                 p_del_item->p_right = p_item->p_right;
1502                 (*__cl_fmap_get_parent_ptr_to_item(p_item)) = p_del_item;
1503                 p_item->p_right->p_up = p_del_item;
1504                 p_item->p_left->p_up = p_del_item;
1505                 p_del_item->color = p_item->color;
1506         }
1507
1508         CL_ASSERT(p_map->nil.color != CL_MAP_RED);
1509
1510 #ifdef _DEBUG_
1511         /* Clear the pointer to the map since the item has been removed. */
1512         p_item->p_map = NULL;
1513 #endif
1514 }
1515
1516 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map,
1517                                IN const void *const p_key)
1518 {
1519         cl_fmap_item_t *p_item;
1520
1521         CL_ASSERT(p_map);
1522         CL_ASSERT(p_map->state == CL_INITIALIZED);
1523
1524         /* Seek the node with the specified key */
1525         p_item = cl_fmap_get(p_map, p_key);
1526
1527         cl_fmap_remove_item(p_map, p_item);
1528
1529         return (p_item);
1530 }
1531
1532 void cl_fmap_merge(OUT cl_fmap_t * const p_dest_map,
1533                    IN OUT cl_fmap_t * const p_src_map)
1534 {
1535         cl_fmap_item_t *p_item, *p_item2, *p_next;
1536
1537         CL_ASSERT(p_dest_map);
1538         CL_ASSERT(p_src_map);
1539
1540         p_item = cl_fmap_head(p_src_map);
1541
1542         while (p_item != cl_fmap_end(p_src_map)) {
1543                 p_next = cl_fmap_next(p_item);
1544
1545                 /* Remove the item from its current map. */
1546                 cl_fmap_remove_item(p_src_map, p_item);
1547                 /* Insert the item into the destination map. */
1548                 p_item2 =
1549                     cl_fmap_insert(p_dest_map, cl_fmap_key(p_item), p_item);
1550                 /* Check that the item was successfully inserted. */
1551                 if (p_item2 != p_item) {
1552                         /* Put the item in back in the source map. */
1553                         p_item2 =
1554                             cl_fmap_insert(p_src_map, cl_fmap_key(p_item),
1555                                            p_item);
1556                         CL_ASSERT(p_item2 == p_item);
1557                 }
1558                 p_item = p_next;
1559         }
1560 }
1561
1562 static void __cl_fmap_delta_move(IN OUT cl_fmap_t * const p_dest,
1563                                  IN OUT cl_fmap_t * const p_src,
1564                                  IN OUT cl_fmap_item_t ** const pp_item)
1565 {
1566         cl_fmap_item_t __attribute__((__unused__)) *p_temp;
1567         cl_fmap_item_t *p_next;
1568
1569         /*
1570          * Get the next item so that we can ensure that pp_item points to
1571          * a valid item upon return from the function.
1572          */
1573         p_next = cl_fmap_next(*pp_item);
1574         /* Move the old item from its current map the the old map. */
1575         cl_fmap_remove_item(p_src, *pp_item);
1576         p_temp = cl_fmap_insert(p_dest, cl_fmap_key(*pp_item), *pp_item);
1577         /* We should never have duplicates. */
1578         CL_ASSERT(p_temp == *pp_item);
1579         /* Point pp_item to a valid item in the source map. */
1580         (*pp_item) = p_next;
1581 }
1582
1583 void cl_fmap_delta(IN OUT cl_fmap_t * const p_map1,
1584                    IN OUT cl_fmap_t * const p_map2,
1585                    OUT cl_fmap_t * const p_new, OUT cl_fmap_t * const p_old)
1586 {
1587         cl_fmap_item_t *p_item1, *p_item2;
1588         int cmp;
1589
1590         CL_ASSERT(p_map1);
1591         CL_ASSERT(p_map2);
1592         CL_ASSERT(p_new);
1593         CL_ASSERT(p_old);
1594         CL_ASSERT(cl_is_fmap_empty(p_new));
1595         CL_ASSERT(cl_is_fmap_empty(p_old));
1596
1597         p_item1 = cl_fmap_head(p_map1);
1598         p_item2 = cl_fmap_head(p_map2);
1599
1600         while (p_item1 != cl_fmap_end(p_map1) && p_item2 != cl_fmap_end(p_map2)) {
1601                 cmp = p_map1->pfn_compare(cl_fmap_key(p_item1),
1602                                           cl_fmap_key(p_item2));
1603                 if (cmp < 0) {
1604                         /* We found an old item. */
1605                         __cl_fmap_delta_move(p_old, p_map1, &p_item1);
1606                 } else if (cmp > 0) {
1607                         /* We found a new item. */
1608                         __cl_fmap_delta_move(p_new, p_map2, &p_item2);
1609                 } else {
1610                         /* Move both forward since they have the same key. */
1611                         p_item1 = cl_fmap_next(p_item1);
1612                         p_item2 = cl_fmap_next(p_item2);
1613                 }
1614         }
1615
1616         /* Process the remainder if the end of either source map was reached. */
1617         while (p_item2 != cl_fmap_end(p_map2))
1618                 __cl_fmap_delta_move(p_new, p_map2, &p_item2);
1619
1620         while (p_item1 != cl_fmap_end(p_map1))
1621                 __cl_fmap_delta_move(p_old, p_map1, &p_item1);
1622 }