contrib/ofed/management/opensm/complib/cl_map.c

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