core/complib/cl_map.c

   1 /*\r
   2  * Copyright (c) 2005 SilverStorm Technologies.  All rights reserved.\r
   3  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. \r
   4  *\r
   5  * This software is available to you under the OpenIB.org BSD license\r
   6  * below:\r
   7  *\r
   8  *     Redistribution and use in source and binary forms, with or\r
   9  *     without modification, are permitted provided that the following\r
  10  *     conditions are met:\r
  11  *\r
  12  *      - Redistributions of source code must retain the above\r
  13  *        copyright notice, this list of conditions and the following\r
  14  *        disclaimer.\r
  15  *\r
  16  *      - Redistributions in binary form must reproduce the above\r
  17  *        copyright notice, this list of conditions and the following\r
  18  *        disclaimer in the documentation and/or other materials\r
  19  *        provided with the distribution.\r
  20  *\r
  21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
  22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
  23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
  24  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
  25  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
  26  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
  27  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  28  * SOFTWARE.\r
  29  *\r
  30  * $Id$\r
  31  */\r
  32 \r
  33 \r
  34 \r
  35 /*\r
  36  * Abstract:\r
  37  *      Implementation of quick map, a binary tree where the caller always provides\r
  38  *      all necessary storage.\r
  39  *\r
  40  * Environment:\r
  41  *      All\r
  42  */\r
  43 \r
  44 \r
  45 /*****************************************************************************\r
  46 *\r
  47 * Map\r
  48 *\r
  49 * Map is an associative array.  By providing a key, the caller can retrieve\r
  50 * an object from the map.  All objects in the map have an associated key,\r
  51 * as specified by the caller when the object was inserted into the map.\r
  52 * In addition to random access, the caller can traverse the map much like\r
  53 * a linked list, either forwards from the first object or backwards from\r
  54 * the last object.  The objects in the map are always traversed in\r
  55 * order since the nodes are stored sorted.\r
  56 *\r
  57 * This implementation of Map uses a red black tree verified against\r
  58 * Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth\r
  59 * printing, 1994.\r
  60 *\r
  61 *****************************************************************************/\r
  62 \r
  63 \r
  64 #include <complib/cl_rbmap.h>\r
  65 #include <complib/cl_qmap.h>\r
  66 #include <complib/cl_map.h>\r
  67 #include <complib/cl_fleximap.h>\r
  68 #include <complib/cl_memory.h>\r
  69 \r
  70 \r
  71 /******************************************************************************\r
  72 *******************************************************************************\r
  73 **************                                                                                                     ************\r
  74 **************                   IMPLEMENTATION OF RB MAP                                  ************\r
  75 **************                                                                                                     ************\r
  76 *******************************************************************************\r
  77 ******************************************************************************/\r
  78 \r
  79 \r
  80 /*\r
  81  * Returns whether a given item is on the left of its parent.\r
  82  */\r
  83 static boolean_t\r
  84 __cl_rbmap_is_left_child(\r
  85         IN      const cl_rbmap_item_t* const    p_item )\r
  86 {\r
  87         CL_ASSERT( p_item );\r
  88         CL_ASSERT( p_item->p_up );\r
  89         CL_ASSERT( p_item->p_up != p_item );\r
  90 \r
  91         return( p_item->p_up->p_left == p_item );\r
  92 }\r
  93 \r
  94 \r
  95 /*\r
  96  * Retrieve the pointer to the parent's pointer to an item.\r
  97  */\r
  98 static cl_rbmap_item_t**\r
  99 __cl_rbmap_get_parent_ptr_to_item(\r
 100         IN      cl_rbmap_item_t* const  p_item )\r
 101 {\r
 102         CL_ASSERT( p_item );\r
 103         CL_ASSERT( p_item->p_up );\r
 104         CL_ASSERT( p_item->p_up != p_item );\r
 105 \r
 106         if( __cl_rbmap_is_left_child( p_item ) )\r
 107                 return( &p_item->p_up->p_left );\r
 108 \r
 109         CL_ASSERT( p_item->p_up->p_right == p_item );\r
 110         return( &p_item->p_up->p_right );\r
 111 }\r
 112 \r
 113 \r
 114 /*\r
 115  * Rotate a node to the left.  This rotation affects the least number of links\r
 116  * between nodes and brings the level of C up by one while increasing the depth\r
 117  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.\r
 118  *\r
 119  *          R                                 R\r
 120  *          |                                 |\r
 121  *          A                                 C\r
 122  *        /   \                         /   \\r
 123  *      W       C                         A       Z\r
 124  *             / \                       / \\r
 125  *            B   Z                     W   B\r
 126  *           / \                           / \\r
 127  *          X   Y                         X   Y\r
 128  */\r
 129 static void\r
 130 __cl_rbmap_rot_left(\r
 131         IN      cl_rbmap_t* const               p_map,\r
 132         IN      cl_rbmap_item_t* const  p_item )\r
 133 {\r
 134         cl_rbmap_item_t **pp_root;\r
 135 \r
 136         CL_ASSERT( p_map );\r
 137         CL_ASSERT( p_item );\r
 138         CL_ASSERT( p_item->p_right != &p_map->nil );\r
 139 \r
 140         pp_root = __cl_rbmap_get_parent_ptr_to_item( p_item );\r
 141 \r
 142         /* Point R to C instead of A. */\r
 143         *pp_root = p_item->p_right;\r
 144         /* Set C's parent to R. */\r
 145         (*pp_root)->p_up = p_item->p_up;\r
 146 \r
 147         /* Set A's right to B */\r
 148         p_item->p_right = (*pp_root)->p_left;\r
 149         /*\r
 150          * Set B's parent to A.  We trap for B being NIL since the\r
 151          * caller may depend on NIL not changing.\r
 152          */\r
 153         if( (*pp_root)->p_left != &p_map->nil )\r
 154                 (*pp_root)->p_left->p_up = p_item;\r
 155 \r
 156         /* Set C's left to A. */\r
 157         (*pp_root)->p_left = p_item;\r
 158         /* Set A's parent to C. */\r
 159         p_item->p_up = *pp_root;\r
 160 }\r
 161 \r
 162 \r
 163 /*\r
 164  * Rotate a node to the right.  This rotation affects the least number of links\r
 165  * between nodes and brings the level of A up by one while increasing the depth\r
 166  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.\r
 167  *\r
 168  *              R                                    R\r
 169  *              |                                    |\r
 170  *              C                                    A\r
 171  *            /   \                                /   \\r
 172  *          A       Z                    W       C\r
 173  *         / \                                          / \\r
 174  *        W   B                                        B   Z\r
 175  *           / \                                      / \\r
 176  *          X   Y                                    X   Y\r
 177  */\r
 178 static void\r
 179 __cl_rbmap_rot_right(\r
 180         IN      cl_rbmap_t* const               p_map,\r
 181         IN      cl_rbmap_item_t* const  p_item )\r
 182 {\r
 183         cl_rbmap_item_t **pp_root;\r
 184 \r
 185         CL_ASSERT( p_map );\r
 186         CL_ASSERT( p_item );\r
 187         CL_ASSERT( p_item->p_left != &p_map->nil );\r
 188 \r
 189         /* Point R to A instead of C. */\r
 190         pp_root = __cl_rbmap_get_parent_ptr_to_item( p_item );\r
 191         (*pp_root) = p_item->p_left;\r
 192         /* Set A's parent to R. */\r
 193         (*pp_root)->p_up = p_item->p_up;\r
 194 \r
 195         /* Set C's left to B */\r
 196         p_item->p_left = (*pp_root)->p_right;\r
 197         /*\r
 198          * Set B's parent to C.  We trap for B being NIL since the\r
 199          * caller may depend on NIL not changing.\r
 200          */\r
 201         if( (*pp_root)->p_right != &p_map->nil )\r
 202                 (*pp_root)->p_right->p_up = p_item;\r
 203 \r
 204         /* Set A's right to C. */\r
 205         (*pp_root)->p_right = p_item;\r
 206         /* Set C's parent to A. */\r
 207         p_item->p_up = *pp_root;\r
 208 }\r
 209 \r
 210 \r
 211 /*\r
 212  * Balance a tree starting at a given item back to the root.\r
 213  */\r
 214 static void\r
 215 __cl_rbmap_ins_bal(\r
 216         IN      cl_rbmap_t* const       p_map,\r
 217         IN      cl_rbmap_item_t*        p_item )\r
 218 {\r
 219         cl_rbmap_item_t*                p_grand_uncle;\r
 220 \r
 221         CL_ASSERT( p_map );\r
 222         CL_ASSERT( p_item );\r
 223         CL_ASSERT( p_item != &p_map->root );\r
 224 \r
 225         while( p_item->p_up->color == CL_MAP_RED )\r
 226         {\r
 227                 if( __cl_rbmap_is_left_child( p_item->p_up ) )\r
 228                 {\r
 229                         p_grand_uncle = p_item->p_up->p_up->p_right;\r
 230                         CL_ASSERT( p_grand_uncle );\r
 231                         if( p_grand_uncle->color == CL_MAP_RED )\r
 232                         {\r
 233                                 p_grand_uncle->color = CL_MAP_BLACK;\r
 234                                 p_item->p_up->color = CL_MAP_BLACK;\r
 235                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
 236                                 p_item = p_item->p_up->p_up;\r
 237                                 continue;\r
 238                         }\r
 239 \r
 240                         if( !__cl_rbmap_is_left_child( p_item ) )\r
 241                         {\r
 242                                 p_item = p_item->p_up;\r
 243                                 __cl_rbmap_rot_left( p_map, p_item );\r
 244                         }\r
 245                         p_item->p_up->color = CL_MAP_BLACK;\r
 246                         p_item->p_up->p_up->color = CL_MAP_RED;\r
 247                         __cl_rbmap_rot_right( p_map, p_item->p_up->p_up );\r
 248                 }\r
 249                 else\r
 250                 {\r
 251                         p_grand_uncle = p_item->p_up->p_up->p_left;\r
 252                         CL_ASSERT( p_grand_uncle );\r
 253                         if( p_grand_uncle->color == CL_MAP_RED )\r
 254                         {\r
 255                                 p_grand_uncle->color = CL_MAP_BLACK;\r
 256                                 p_item->p_up->color = CL_MAP_BLACK;\r
 257                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
 258                                 p_item = p_item->p_up->p_up;\r
 259                                 continue;\r
 260                         }\r
 261 \r
 262                         if( __cl_rbmap_is_left_child( p_item ) )\r
 263                         {\r
 264                                 p_item = p_item->p_up;\r
 265                                 __cl_rbmap_rot_right( p_map, p_item );\r
 266                         }\r
 267                         p_item->p_up->color = CL_MAP_BLACK;\r
 268                         p_item->p_up->p_up->color = CL_MAP_RED;\r
 269                         __cl_rbmap_rot_left( p_map, p_item->p_up->p_up );\r
 270                 }\r
 271         }\r
 272 }\r
 273 \r
 274 \r
 275 void\r
 276 cl_rbmap_insert(\r
 277         IN      cl_rbmap_t* const               p_map,\r
 278         IN      cl_rbmap_item_t* const  p_insert_at,\r
 279         IN      cl_rbmap_item_t* const  p_item,\r
 280         IN      boolean_t                               left )\r
 281 {\r
 282         CL_ASSERT( p_map );\r
 283         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
 284         CL_ASSERT( p_insert_at );\r
 285         CL_ASSERT( p_item );\r
 286         CL_ASSERT( p_map->root.p_up == &p_map->root );\r
 287         CL_ASSERT( p_map->root.color != CL_MAP_RED );\r
 288         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
 289 \r
 290         p_item->p_left = &p_map->nil;\r
 291         p_item->p_right = &p_map->nil;\r
 292         p_item->color = CL_MAP_RED;\r
 293 \r
 294         if( p_insert_at == cl_rbmap_end( p_map ) )\r
 295         {\r
 296                 p_map->root.p_left = p_item;\r
 297                 p_item->p_up = &p_map->root;\r
 298         }\r
 299         else\r
 300         {\r
 301                 if( left )\r
 302                         p_insert_at->p_left = p_item;\r
 303                 else\r
 304                         p_insert_at->p_right = p_item;\r
 305 \r
 306                 p_item->p_up = p_insert_at;\r
 307         }\r
 308 \r
 309         /* Increase the count. */\r
 310         p_map->count++;\r
 311 \r
 312         /*\r
 313          * We have added depth to this section of the tree.\r
 314          * Rebalance as necessary as we retrace our path through the tree\r
 315          * and update colors.\r
 316          */\r
 317         __cl_rbmap_ins_bal( p_map, p_item );\r
 318 \r
 319         cl_rbmap_root( p_map )->color = CL_MAP_BLACK;\r
 320 \r
 321         /*\r
 322          * Note that it is not necessary to re-color the nil node black because all\r
 323          * red color assignments are made via the p_up pointer, and nil is never\r
 324          * set as the value of a p_up pointer.\r
 325          */\r
 326 \r
 327 #ifdef _DEBUG_\r
 328         /* Set the pointer to the map in the map item for consistency checking. */\r
 329         p_item->p_map = p_map;\r
 330 #endif\r
 331 }\r
 332 \r
 333 \r
 334 static void\r
 335 __cl_rbmap_del_bal(\r
 336         IN      cl_rbmap_t* const       p_map,\r
 337         IN      cl_rbmap_item_t*        p_item )\r
 338 {\r
 339         cl_rbmap_item_t         *p_uncle;\r
 340 \r
 341         while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )\r
 342         {\r
 343                 if( __cl_rbmap_is_left_child( p_item ) )\r
 344                 {\r
 345                         p_uncle = p_item->p_up->p_right;\r
 346 \r
 347                         if( p_uncle->color == CL_MAP_RED )\r
 348                         {\r
 349                                 p_uncle->color = CL_MAP_BLACK;\r
 350                                 p_item->p_up->color = CL_MAP_RED;\r
 351                                 __cl_rbmap_rot_left( p_map, p_item->p_up );\r
 352                                 p_uncle = p_item->p_up->p_right;\r
 353                         }\r
 354 \r
 355                         if( p_uncle->p_right->color != CL_MAP_RED )\r
 356                         {\r
 357                                 if( p_uncle->p_left->color != CL_MAP_RED )\r
 358                                 {\r
 359                                         p_uncle->color = CL_MAP_RED;\r
 360                                         p_item = p_item->p_up;\r
 361                                         continue;\r
 362                                 }\r
 363 \r
 364                                 p_uncle->p_left->color = CL_MAP_BLACK;\r
 365                                 p_uncle->color = CL_MAP_RED;\r
 366                                 __cl_rbmap_rot_right( p_map, p_uncle );\r
 367                                 p_uncle = p_item->p_up->p_right;\r
 368                         }\r
 369                         p_uncle->color = p_item->p_up->color;\r
 370                         p_item->p_up->color = CL_MAP_BLACK;\r
 371                         p_uncle->p_right->color = CL_MAP_BLACK;\r
 372                         __cl_rbmap_rot_left( p_map, p_item->p_up );\r
 373                         break;\r
 374                 }\r
 375                 else\r
 376                 {\r
 377                         p_uncle = p_item->p_up->p_left;\r
 378 \r
 379                         if( p_uncle->color == CL_MAP_RED )\r
 380                         {\r
 381                                 p_uncle->color = CL_MAP_BLACK;\r
 382                                 p_item->p_up->color = CL_MAP_RED;\r
 383                                 __cl_rbmap_rot_right( p_map, p_item->p_up );\r
 384                                 p_uncle = p_item->p_up->p_left;\r
 385                         }\r
 386 \r
 387                         if( p_uncle->p_left->color != CL_MAP_RED )\r
 388                         {\r
 389                                 if( p_uncle->p_right->color != CL_MAP_RED )\r
 390                                 {\r
 391                                         p_uncle->color = CL_MAP_RED;\r
 392                                         p_item = p_item->p_up;\r
 393                                         continue;\r
 394                                 }\r
 395 \r
 396                                 p_uncle->p_right->color = CL_MAP_BLACK;\r
 397                                 p_uncle->color = CL_MAP_RED;\r
 398                                 __cl_rbmap_rot_left( p_map, p_uncle );\r
 399                                 p_uncle = p_item->p_up->p_left;\r
 400                         }\r
 401                         p_uncle->color = p_item->p_up->color;\r
 402                         p_item->p_up->color = CL_MAP_BLACK;\r
 403                         p_uncle->p_left->color = CL_MAP_BLACK;\r
 404                         __cl_rbmap_rot_right( p_map, p_item->p_up );\r
 405                         break;\r
 406                 }\r
 407         }\r
 408         p_item->color = CL_MAP_BLACK;\r
 409 }\r
 410 \r
 411 \r
 412 void\r
 413 cl_rbmap_remove_item(\r
 414         IN      cl_rbmap_t* const               p_map,\r
 415         IN      cl_rbmap_item_t* const  p_item )\r
 416 {\r
 417         cl_rbmap_item_t *p_child, *p_del_item;\r
 418 \r
 419         CL_ASSERT( p_map );\r
 420         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
 421         CL_ASSERT( p_item );\r
 422         CL_ASSERT( p_item->p_map == p_map );\r
 423 \r
 424         if( p_item == cl_rbmap_end( p_map ) )\r
 425                 return;\r
 426 \r
 427         if( p_item->p_right == &p_map->nil )\r
 428         {\r
 429                 /* The item being removed has children on at most its left. */\r
 430                 p_del_item = p_item;\r
 431                 p_child = p_del_item->p_left;\r
 432         }\r
 433         else if( p_item->p_left == &p_map->nil )\r
 434         {\r
 435                 /* The item being removed has children on at most its right. */\r
 436                 p_del_item = p_item;\r
 437                 p_child = p_del_item->p_right;\r
 438         }\r
 439         else\r
 440         {\r
 441                 /*\r
 442                  * The item being removed has children on both side.\r
 443                  * We select the item that will replace it.  After removing\r
 444                  * the substitute item and rebalancing, the tree will have the\r
 445                  * correct topology.  Exchanging the substitute for the item\r
 446                  * will finalize the removal.\r
 447                  */\r
 448                 p_del_item = p_item->p_right;\r
 449                 CL_ASSERT( p_del_item != &p_map->nil );\r
 450                 while( p_del_item->p_left != &p_map->nil )\r
 451                         p_del_item = p_del_item->p_left;\r
 452                 p_child = p_del_item->p_right;\r
 453         }\r
 454 \r
 455         /* Decrement the item count. */\r
 456         p_map->count--;\r
 457 \r
 458         /*\r
 459          * This assignment may modify the parent pointer of the nil node.\r
 460          * This is inconsequential.\r
 461          */\r
 462         p_child->p_up = p_del_item->p_up;\r
 463         (*__cl_rbmap_get_parent_ptr_to_item( p_del_item )) = p_child; // 2 right = 5\r
 464 \r
 465         if( p_del_item->color != CL_MAP_RED )\r
 466                 __cl_rbmap_del_bal( p_map, p_child );\r
 467 \r
 468         /*\r
 469          * Note that the splicing done below does not need to occur before\r
 470          * the tree is balanced, since the actual topology changes are made by the\r
 471          * preceding code.  The topology is preserved by the color assignment made\r
 472          * below (reader should be reminded that p_del_item == p_item in some cases).\r
 473          */\r
 474         if( p_del_item != p_item )\r
 475         {\r
 476                 /*\r
 477                  * Finalize the removal of the specified item by exchanging it with\r
 478                  * the substitute which we removed above.\r
 479                  */\r
 480                 p_del_item->p_up = p_item->p_up;\r
 481                 p_del_item->p_left = p_item->p_left;\r
 482                 p_del_item->p_right = p_item->p_right;\r
 483                 (*__cl_rbmap_get_parent_ptr_to_item( p_item )) = p_del_item;\r
 484                 p_item->p_right->p_up = p_del_item;\r
 485                 p_item->p_left->p_up = p_del_item;\r
 486                 p_del_item->color = p_item->color;\r
 487         }\r
 488 \r
 489         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
 490 \r
 491 #ifdef _DEBUG_\r
 492         /* Clear the pointer to the map since the item has been removed. */\r
 493         p_item->p_map = NULL;\r
 494 #endif\r
 495 }\r
 496 \r
 497 \r
 498 /******************************************************************************\r
 499 *******************************************************************************\r
 500 **************                                                                                                     ************\r
 501 **************                   IMPLEMENTATION OF QUICK MAP                       ************\r
 502 **************                                                                                                     ************\r
 503 *******************************************************************************\r
 504 ******************************************************************************/\r
 505 \r
 506 /*\r
 507  * Get the root.\r
 508  */\r
 509 static inline cl_map_item_t*\r
 510 __cl_map_root(\r
 511         IN      const cl_qmap_t* const  p_map )\r
 512 {\r
 513         CL_ASSERT( p_map );\r
 514         return( p_map->root.p_left );\r
 515 }\r
 516 \r
 517 \r
 518 /*\r
 519  * Returns whether a given item is on the left of its parent.\r
 520  */\r
 521 static boolean_t\r
 522 __cl_map_is_left_child(\r
 523         IN      const cl_map_item_t* const      p_item )\r
 524 {\r
 525         CL_ASSERT( p_item );\r
 526         CL_ASSERT( p_item->p_up );\r
 527         CL_ASSERT( p_item->p_up != p_item );\r
 528 \r
 529         return( p_item->p_up->p_left == p_item );\r
 530 }\r
 531 \r
 532 \r
 533 /*\r
 534  * Retrieve the pointer to the parent's pointer to an item.\r
 535  */\r
 536 static cl_map_item_t**\r
 537 __cl_map_get_parent_ptr_to_item(\r
 538         IN      cl_map_item_t* const    p_item )\r
 539 {\r
 540         CL_ASSERT( p_item );\r
 541         CL_ASSERT( p_item->p_up );\r
 542         CL_ASSERT( p_item->p_up != p_item );\r
 543 \r
 544         if( __cl_map_is_left_child( p_item ) )\r
 545                 return( &p_item->p_up->p_left );\r
 546 \r
 547         CL_ASSERT( p_item->p_up->p_right == p_item );\r
 548         return( &p_item->p_up->p_right );\r
 549 }\r
 550 \r
 551 \r
 552 /*\r
 553  * Rotate a node to the left.  This rotation affects the least number of links\r
 554  * between nodes and brings the level of C up by one while increasing the depth\r
 555  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.\r
 556  *\r
 557  *          R                                 R\r
 558  *          |                                 |\r
 559  *          A                                 C\r
 560  *        /   \                         /   \\r
 561  *      W       C                         A       Z\r
 562  *             / \                       / \\r
 563  *            B   Z                     W   B\r
 564  *           / \                           / \\r
 565  *          X   Y                         X   Y\r
 566  */\r
 567 static void\r
 568 __cl_map_rot_left(\r
 569         IN      cl_qmap_t* const                p_map,\r
 570         IN      cl_map_item_t* const    p_item )\r
 571 {\r
 572         cl_map_item_t   **pp_root;\r
 573 \r
 574         CL_ASSERT( p_map );\r
 575         CL_ASSERT( p_item );\r
 576         CL_ASSERT( p_item->p_right != &p_map->nil );\r
 577 \r
 578         pp_root = __cl_map_get_parent_ptr_to_item( p_item );\r
 579 \r
 580         /* Point R to C instead of A. */\r
 581         *pp_root = p_item->p_right;\r
 582         /* Set C's parent to R. */\r
 583         (*pp_root)->p_up = p_item->p_up;\r
 584 \r
 585         /* Set A's right to B */\r
 586         p_item->p_right = (*pp_root)->p_left;\r
 587         /*\r
 588          * Set B's parent to A.  We trap for B being NIL since the\r
 589          * caller may depend on NIL not changing.\r
 590          */\r
 591         if( (*pp_root)->p_left != &p_map->nil )\r
 592                 (*pp_root)->p_left->p_up = p_item;\r
 593 \r
 594         /* Set C's left to A. */\r
 595         (*pp_root)->p_left = p_item;\r
 596         /* Set A's parent to C. */\r
 597         p_item->p_up = *pp_root;\r
 598 }\r
 599 \r
 600 \r
 601 /*\r
 602  * Rotate a node to the right.  This rotation affects the least number of links\r
 603  * between nodes and brings the level of A up by one while increasing the depth\r
 604  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.\r
 605  *\r
 606  *              R                                    R\r
 607  *              |                                    |\r
 608  *              C                                    A\r
 609  *            /   \                                /   \\r
 610  *          A       Z                    W       C\r
 611  *         / \                                          / \\r
 612  *        W   B                                        B   Z\r
 613  *           / \                                      / \\r
 614  *          X   Y                                    X   Y\r
 615  */\r
 616 static void\r
 617 __cl_map_rot_right(\r
 618         IN      cl_qmap_t* const                p_map,\r
 619         IN      cl_map_item_t* const    p_item )\r
 620 {\r
 621         cl_map_item_t   **pp_root;\r
 622 \r
 623         CL_ASSERT( p_map );\r
 624         CL_ASSERT( p_item );\r
 625         CL_ASSERT( p_item->p_left != &p_map->nil );\r
 626 \r
 627         /* Point R to A instead of C. */\r
 628         pp_root = __cl_map_get_parent_ptr_to_item( p_item );\r
 629         (*pp_root) = p_item->p_left;\r
 630         /* Set A's parent to R. */\r
 631         (*pp_root)->p_up = p_item->p_up;\r
 632 \r
 633         /* Set C's left to B */\r
 634         p_item->p_left = (*pp_root)->p_right;\r
 635         /*\r
 636          * Set B's parent to C.  We trap for B being NIL since the\r
 637          * caller may depend on NIL not changing.\r
 638          */\r
 639         if( (*pp_root)->p_right != &p_map->nil )\r
 640                 (*pp_root)->p_right->p_up = p_item;\r
 641 \r
 642         /* Set A's right to C. */\r
 643         (*pp_root)->p_right = p_item;\r
 644         /* Set C's parent to A. */\r
 645         p_item->p_up = *pp_root;\r
 646 }\r
 647 \r
 648 \r
 649 void\r
 650 cl_qmap_init(\r
 651         IN      cl_qmap_t* const        p_map )\r
 652 {\r
 653         CL_ASSERT( p_map );\r
 654 \r
 655         cl_memclr( p_map, sizeof(cl_qmap_t) );\r
 656 \r
 657         /* special setup for the root node */\r
 658         p_map->root.p_up = &p_map->root;\r
 659         p_map->root.p_left = &p_map->nil;\r
 660         p_map->root.p_right = &p_map->nil;\r
 661         p_map->root.color = CL_MAP_BLACK;\r
 662 \r
 663         /* Setup the node used as terminator for all leaves. */\r
 664         p_map->nil.p_up = &p_map->nil;\r
 665         p_map->nil.p_left = &p_map->nil;\r
 666         p_map->nil.p_right = &p_map->nil;\r
 667         p_map->nil.color = CL_MAP_BLACK;\r
 668 \r
 669 #ifdef _DEBUG_\r
 670         p_map->root.p_map = p_map;\r
 671         p_map->nil.p_map = p_map;\r
 672 #endif\r
 673 \r
 674         p_map->state = CL_INITIALIZED;\r
 675 \r
 676         cl_qmap_remove_all( p_map );\r
 677 }\r
 678 \r
 679 \r
 680 cl_map_item_t*\r
 681 cl_qmap_get(\r
 682         IN      const cl_qmap_t* const  p_map,\r
 683         IN      const uint64_t                  key )\r
 684 {\r
 685         cl_map_item_t   *p_item;\r
 686 \r
 687         CL_ASSERT( p_map );\r
 688         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
 689 \r
 690         p_item = __cl_map_root( p_map );\r
 691 \r
 692         while( p_item != &p_map->nil )\r
 693         {\r
 694                 if( key == p_item->key )\r
 695                         break;                                          /* just right */\r
 696 \r
 697                 if( key < p_item->key )\r
 698                         p_item = p_item->p_left;        /* too small */\r
 699                 else\r
 700                         p_item = p_item->p_right;       /* too big */\r
 701         }\r
 702 \r
 703         return( p_item );\r
 704 }\r
 705 \r
 706 \r
 707 void\r
 708 cl_qmap_apply_func(\r
 709         IN      const cl_qmap_t* const  p_map,\r
 710         IN      cl_pfn_qmap_apply_t             pfn_func,\r
 711         IN      const void* const               context )\r
 712 {\r
 713         cl_map_item_t*  p_map_item;\r
 714 \r
 715         /* Note that context can have any arbitrary value. */\r
 716         CL_ASSERT( p_map );\r
 717         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
 718         CL_ASSERT( pfn_func );\r
 719 \r
 720         p_map_item = cl_qmap_head( p_map );\r
 721         while( p_map_item != cl_qmap_end( p_map ) )\r
 722         {\r
 723                 pfn_func( p_map_item, (void*)context );\r
 724                 p_map_item = cl_qmap_next( p_map_item );\r
 725         }\r
 726 }\r
 727 \r
 728 \r
 729 /*\r
 730  * Balance a tree starting at a given item back to the root.\r
 731  */\r
 732 static void\r
 733 __cl_map_ins_bal(\r
 734         IN      cl_qmap_t* const        p_map,\r
 735         IN      cl_map_item_t*          p_item )\r
 736 {\r
 737         cl_map_item_t*          p_grand_uncle;\r
 738 \r
 739         CL_ASSERT( p_map );\r
 740         CL_ASSERT( p_item );\r
 741         CL_ASSERT( p_item != &p_map->root );\r
 742 \r
 743         while( p_item->p_up->color == CL_MAP_RED )\r
 744         {\r
 745                 if( __cl_map_is_left_child( p_item->p_up ) )\r
 746                 {\r
 747                         p_grand_uncle = p_item->p_up->p_up->p_right;\r
 748                         CL_ASSERT( p_grand_uncle );\r
 749                         if( p_grand_uncle->color == CL_MAP_RED )\r
 750                         {\r
 751                                 p_grand_uncle->color = CL_MAP_BLACK;\r
 752                                 p_item->p_up->color = CL_MAP_BLACK;\r
 753                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
 754                                 p_item = p_item->p_up->p_up;\r
 755                                 continue;\r
 756                         }\r
 757 \r
 758                         if( !__cl_map_is_left_child( p_item ) )\r
 759                         {\r
 760                                 p_item = p_item->p_up;\r
 761                                 __cl_map_rot_left( p_map, p_item );\r
 762                         }\r
 763                         p_item->p_up->color = CL_MAP_BLACK;\r
 764                         p_item->p_up->p_up->color = CL_MAP_RED;\r
 765                         __cl_map_rot_right( p_map, p_item->p_up->p_up );\r
 766                 }\r
 767                 else\r
 768                 {\r
 769                         p_grand_uncle = p_item->p_up->p_up->p_left;\r
 770                         CL_ASSERT( p_grand_uncle );\r
 771                         if( p_grand_uncle->color == CL_MAP_RED )\r
 772                         {\r
 773                                 p_grand_uncle->color = CL_MAP_BLACK;\r
 774                                 p_item->p_up->color = CL_MAP_BLACK;\r
 775                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
 776                                 p_item = p_item->p_up->p_up;\r
 777                                 continue;\r
 778                         }\r
 779 \r
 780                         if( __cl_map_is_left_child( p_item ) )\r
 781                         {\r
 782                                 p_item = p_item->p_up;\r
 783                                 __cl_map_rot_right( p_map, p_item );\r
 784                         }\r
 785                         p_item->p_up->color = CL_MAP_BLACK;\r
 786                         p_item->p_up->p_up->color = CL_MAP_RED;\r
 787                         __cl_map_rot_left( p_map, p_item->p_up->p_up );\r
 788                 }\r
 789         }\r
 790 }\r
 791 \r
 792 \r
 793 cl_map_item_t*\r
 794 cl_qmap_insert(\r
 795         IN      cl_qmap_t* const                p_map,\r
 796         IN      const uint64_t                  key,\r
 797         IN      cl_map_item_t* const    p_item )\r
 798 {\r
 799         cl_map_item_t   *p_insert_at, *p_comp_item;\r
 800 \r
 801         CL_ASSERT( p_map );\r
 802         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
 803         CL_ASSERT( p_item );\r
 804         CL_ASSERT( p_map->root.p_up == &p_map->root );\r
 805         CL_ASSERT( p_map->root.color != CL_MAP_RED );\r
 806         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
 807 \r
 808         p_item->p_left = &p_map->nil;\r
 809         p_item->p_right = &p_map->nil;\r
 810         p_item->key = key;\r
 811         p_item->color = CL_MAP_RED;\r
 812 \r
 813         /* Find the insertion location. */\r
 814         p_insert_at = &p_map->root;\r
 815         p_comp_item = __cl_map_root( p_map );\r
 816 \r
 817         while( p_comp_item != &p_map->nil )\r
 818         {\r
 819                 p_insert_at = p_comp_item;\r
 820 \r
 821                 if( key == p_insert_at->key )\r
 822                         return( p_insert_at );\r
 823 \r
 824                 /* Traverse the tree until the correct insertion point is found. */\r
 825                 if( key < p_insert_at->key )\r
 826                         p_comp_item = p_insert_at->p_left;\r
 827                 else\r
 828                         p_comp_item = p_insert_at->p_right;\r
 829         }\r
 830 \r
 831         CL_ASSERT( p_insert_at != &p_map->nil );\r
 832         CL_ASSERT( p_comp_item == &p_map->nil );\r
 833         /* Insert the item. */\r
 834         if( p_insert_at == &p_map->root )\r
 835         {\r
 836                 p_insert_at->p_left = p_item;\r
 837                 /*\r
 838                  * Primitive insert places the new item in front of\r
 839                  * the existing item.\r
 840                  */\r
 841                 __cl_primitive_insert( &p_map->nil.pool_item.list_item,\r
 842                         &p_item->pool_item.list_item );\r
 843         }\r
 844         else if( key < p_insert_at->key )\r
 845         {\r
 846                 p_insert_at->p_left = p_item;\r
 847                 /*\r
 848                  * Primitive insert places the new item in front of\r
 849                  * the existing item.\r
 850                  */\r
 851                 __cl_primitive_insert( &p_insert_at->pool_item.list_item,\r
 852                         &p_item->pool_item.list_item );\r
 853         }\r
 854         else\r
 855         {\r
 856                 p_insert_at->p_right = p_item;\r
 857                 /*\r
 858                  * Primitive insert places the new item in front of\r
 859                  * the existing item.\r
 860                  */\r
 861                 __cl_primitive_insert( p_insert_at->pool_item.list_item.p_next,\r
 862                         &p_item->pool_item.list_item );\r
 863         }\r
 864         /* Increase the count. */\r
 865         p_map->count++;\r
 866 \r
 867         p_item->p_up = p_insert_at;\r
 868 \r
 869         /*\r
 870          * We have added depth to this section of the tree.\r
 871          * Rebalance as necessary as we retrace our path through the tree\r
 872          * and update colors.\r
 873          */\r
 874         __cl_map_ins_bal( p_map, p_item );\r
 875 \r
 876         __cl_map_root( p_map )->color = CL_MAP_BLACK;\r
 877 \r
 878         /*\r
 879          * Note that it is not necessary to re-color the nil node black because all\r
 880          * red color assignments are made via the p_up pointer, and nil is never\r
 881          * set as the value of a p_up pointer.\r
 882          */\r
 883 \r
 884 #ifdef _DEBUG_\r
 885         /* Set the pointer to the map in the map item for consistency checking. */\r
 886         p_item->p_map = p_map;\r
 887 #endif\r
 888 \r
 889         return( p_item );\r
 890 }\r
 891 \r
 892 \r
 893 static void\r
 894 __cl_map_del_bal(\r
 895         IN      cl_qmap_t* const        p_map,\r
 896         IN      cl_map_item_t*          p_item )\r
 897 {\r
 898         cl_map_item_t           *p_uncle;\r
 899 \r
 900         while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )\r
 901         {\r
 902                 if( __cl_map_is_left_child( p_item ) )\r
 903                 {\r
 904                         p_uncle = p_item->p_up->p_right;\r
 905 \r
 906                         if( p_uncle->color == CL_MAP_RED )\r
 907                         {\r
 908                                 p_uncle->color = CL_MAP_BLACK;\r
 909                                 p_item->p_up->color = CL_MAP_RED;\r
 910                                 __cl_map_rot_left( p_map, p_item->p_up );\r
 911                                 p_uncle = p_item->p_up->p_right;\r
 912                         }\r
 913 \r
 914                         if( p_uncle->p_right->color != CL_MAP_RED )\r
 915                         {\r
 916                                 if( p_uncle->p_left->color != CL_MAP_RED )\r
 917                                 {\r
 918                                         p_uncle->color = CL_MAP_RED;\r
 919                                         p_item = p_item->p_up;\r
 920                                         continue;\r
 921                                 }\r
 922 \r
 923                                 p_uncle->p_left->color = CL_MAP_BLACK;\r
 924                                 p_uncle->color = CL_MAP_RED;\r
 925                                 __cl_map_rot_right( p_map, p_uncle );\r
 926                                 p_uncle = p_item->p_up->p_right;\r
 927                         }\r
 928                         p_uncle->color = p_item->p_up->color;\r
 929                         p_item->p_up->color = CL_MAP_BLACK;\r
 930                         p_uncle->p_right->color = CL_MAP_BLACK;\r
 931                         __cl_map_rot_left( p_map, p_item->p_up );\r
 932                         break;\r
 933                 }\r
 934                 else\r
 935                 {\r
 936                         p_uncle = p_item->p_up->p_left;\r
 937 \r
 938                         if( p_uncle->color == CL_MAP_RED )\r
 939                         {\r
 940                                 p_uncle->color = CL_MAP_BLACK;\r
 941                                 p_item->p_up->color = CL_MAP_RED;\r
 942                                 __cl_map_rot_right( p_map, p_item->p_up );\r
 943                                 p_uncle = p_item->p_up->p_left;\r
 944                         }\r
 945 \r
 946                         if( p_uncle->p_left->color != CL_MAP_RED )\r
 947                         {\r
 948                                 if( p_uncle->p_right->color != CL_MAP_RED )\r
 949                                 {\r
 950                                         p_uncle->color = CL_MAP_RED;\r
 951                                         p_item = p_item->p_up;\r
 952                                         continue;\r
 953                                 }\r
 954 \r
 955                                 p_uncle->p_right->color = CL_MAP_BLACK;\r
 956                                 p_uncle->color = CL_MAP_RED;\r
 957                                 __cl_map_rot_left( p_map, p_uncle );\r
 958                                 p_uncle = p_item->p_up->p_left;\r
 959                         }\r
 960                         p_uncle->color = p_item->p_up->color;\r
 961                         p_item->p_up->color = CL_MAP_BLACK;\r
 962                         p_uncle->p_left->color = CL_MAP_BLACK;\r
 963                         __cl_map_rot_right( p_map, p_item->p_up );\r
 964                         break;\r
 965                 }\r
 966         }\r
 967         p_item->color = CL_MAP_BLACK;\r
 968 }\r
 969 \r
 970 \r
 971 void\r
 972 cl_qmap_remove_item(\r
 973         IN      cl_qmap_t* const                p_map,\r
 974         IN      cl_map_item_t* const    p_item )\r
 975 {\r
 976         cl_map_item_t   *p_child, *p_del_item;\r
 977 \r
 978         CL_ASSERT( p_map );\r
 979         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
 980         CL_ASSERT( p_item );\r
 981         CL_ASSERT( p_item->p_map == p_map );\r
 982 \r
 983         if( p_item == cl_qmap_end( p_map ) )\r
 984                 return;\r
 985 \r
 986         if( (p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil ) )\r
 987         {\r
 988                 /* The item being removed has children on at most on side. */\r
 989                 p_del_item = p_item;\r
 990         }\r
 991         else\r
 992         {\r
 993                 /*\r
 994                  * The item being removed has children on both side.\r
 995                  * We select the item that will replace it.  After removing\r
 996                  * the substitute item and rebalancing, the tree will have the\r
 997                  * correct topology.  Exchanging the substitute for the item\r
 998                  * will finalize the removal.\r
 999                  */\r
1000                 p_del_item = cl_qmap_next( p_item );\r
1001                 CL_ASSERT( p_del_item != &p_map->nil );\r
1002         }\r
1003 \r
1004         /* Remove the item from the list. */\r
1005         __cl_primitive_remove( &p_item->pool_item.list_item );\r
1006         /* Decrement the item count. */\r
1007         p_map->count--;\r
1008 \r
1009         /* Get the pointer to the new root's child, if any. */\r
1010         if( p_del_item->p_left != &p_map->nil )\r
1011                 p_child = p_del_item->p_left;\r
1012         else\r
1013                 p_child = p_del_item->p_right;\r
1014 \r
1015         /*\r
1016          * This assignment may modify the parent pointer of the nil node.\r
1017          * This is inconsequential.\r
1018          */\r
1019         p_child->p_up = p_del_item->p_up;\r
1020         (*__cl_map_get_parent_ptr_to_item( p_del_item )) = p_child;\r
1021 \r
1022         if( p_del_item->color != CL_MAP_RED )\r
1023                 __cl_map_del_bal( p_map, p_child );\r
1024 \r
1025         /*\r
1026          * Note that the splicing done below does not need to occur before\r
1027          * the tree is balanced, since the actual topology changes are made by the\r
1028          * preceding code.  The topology is preserved by the color assignment made\r
1029          * below (reader should be reminded that p_del_item == p_item in some cases).\r
1030          */\r
1031         if( p_del_item != p_item )\r
1032         {\r
1033                 /*\r
1034                  * Finalize the removal of the specified item by exchanging it with\r
1035                  * the substitute which we removed above.\r
1036                  */\r
1037                 p_del_item->p_up = p_item->p_up;\r
1038                 p_del_item->p_left = p_item->p_left;\r
1039                 p_del_item->p_right = p_item->p_right;\r
1040                 (*__cl_map_get_parent_ptr_to_item( p_item )) = p_del_item;\r
1041                 p_item->p_right->p_up = p_del_item;\r
1042                 p_item->p_left->p_up = p_del_item;\r
1043                 p_del_item->color = p_item->color;\r
1044         }\r
1045 \r
1046         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
1047 \r
1048 #ifdef _DEBUG_\r
1049         /* Clear the pointer to the map since the item has been removed. */\r
1050         p_item->p_map = NULL;\r
1051 #endif\r
1052 }\r
1053 \r
1054 \r
1055 cl_map_item_t*\r
1056 cl_qmap_remove(\r
1057         IN      cl_qmap_t* const        p_map,\r
1058         IN      const uint64_t          key )\r
1059 {\r
1060         cl_map_item_t   *p_item;\r
1061 \r
1062         CL_ASSERT( p_map );\r
1063         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1064 \r
1065         /* Seek the node with the specified key */\r
1066         p_item = cl_qmap_get( p_map, key );\r
1067 \r
1068         cl_qmap_remove_item( p_map, p_item );\r
1069 \r
1070         return( p_item );\r
1071 }\r
1072 \r
1073 \r
1074 void\r
1075 cl_qmap_merge(\r
1076         OUT             cl_qmap_t* const        p_dest_map,\r
1077         IN OUT  cl_qmap_t* const        p_src_map )\r
1078 {\r
1079         cl_map_item_t           *p_item, *p_item2, *p_next;\r
1080 \r
1081         CL_ASSERT( p_dest_map );\r
1082         CL_ASSERT( p_src_map );\r
1083 \r
1084         p_item = cl_qmap_head( p_src_map );\r
1085 \r
1086         while( p_item != cl_qmap_end( p_src_map ) )\r
1087         {\r
1088                 p_next = cl_qmap_next( p_item );\r
1089 \r
1090                 /* Remove the item from its current map. */\r
1091                 cl_qmap_remove_item( p_src_map, p_item );\r
1092                 /* Insert the item into the destination map. */\r
1093                 p_item2 = cl_qmap_insert( p_dest_map, cl_qmap_key( p_item ), p_item );\r
1094                 /* Check that the item was successfully inserted. */\r
1095                 if( p_item2 != p_item )\r
1096                 {\r
1097                         /* Put the item in back in the source map. */\r
1098                         p_item2 =\r
1099                                 cl_qmap_insert( p_src_map, cl_qmap_key( p_item ), p_item );\r
1100                         CL_ASSERT( p_item2 == p_item );\r
1101                 }\r
1102                 p_item = p_next;\r
1103         }\r
1104 }\r
1105 \r
1106 \r
1107 static void\r
1108 __cl_qmap_delta_move(\r
1109         IN OUT  cl_qmap_t* const                p_dest,\r
1110         IN OUT  cl_qmap_t* const                p_src,\r
1111         IN OUT  cl_map_item_t** const   pp_item )\r
1112 {\r
1113         cl_map_item_t           *p_temp, *p_next;\r
1114 \r
1115         /*\r
1116          * Get the next item so that we can ensure that pp_item points to\r
1117          * a valid item upon return from the function.\r
1118          */\r
1119         p_next = cl_qmap_next( *pp_item );\r
1120         /* Move the old item from its current map the the old map. */\r
1121         cl_qmap_remove_item( p_src, *pp_item );\r
1122         p_temp = cl_qmap_insert( p_dest, cl_qmap_key( *pp_item ), *pp_item );\r
1123         /* We should never have duplicates. */\r
1124         CL_ASSERT( p_temp == *pp_item );\r
1125         /* Point pp_item to a valid item in the source map. */\r
1126         (*pp_item) = p_next;\r
1127 }\r
1128 \r
1129 \r
1130 void\r
1131 cl_qmap_delta(\r
1132         IN OUT  cl_qmap_t* const        p_map1,\r
1133         IN OUT  cl_qmap_t* const        p_map2,\r
1134         OUT             cl_qmap_t* const        p_new,\r
1135         OUT             cl_qmap_t* const        p_old )\r
1136 {\r
1137         cl_map_item_t           *p_item1, *p_item2;\r
1138         uint64_t                        key1, key2;\r
1139 \r
1140         CL_ASSERT( p_map1 );\r
1141         CL_ASSERT( p_map2 );\r
1142         CL_ASSERT( p_new );\r
1143         CL_ASSERT( p_old );\r
1144         CL_ASSERT( cl_is_qmap_empty( p_new ) );\r
1145         CL_ASSERT( cl_is_qmap_empty( p_old ) );\r
1146 \r
1147         p_item1 = cl_qmap_head( p_map1 );\r
1148         p_item2 = cl_qmap_head( p_map2 );\r
1149 \r
1150         while( p_item1 != cl_qmap_end( p_map1 ) &&\r
1151                 p_item2 != cl_qmap_end( p_map2 ) )\r
1152         {\r
1153                 key1 = cl_qmap_key( p_item1 );\r
1154                 key2 = cl_qmap_key( p_item2 );\r
1155                 if( key1 < key2 )\r
1156                 {\r
1157                         /* We found an old item. */\r
1158                         __cl_qmap_delta_move( p_old, p_map1, &p_item1 );\r
1159                 }\r
1160                 else if( key1 > key2 )\r
1161                 {\r
1162                         /* We found a new item. */\r
1163                         __cl_qmap_delta_move( p_new, p_map2, &p_item2 );\r
1164                 }\r
1165                 else\r
1166                 {\r
1167                         /* Move both forward since they have the same key. */\r
1168                         p_item1 = cl_qmap_next( p_item1 );\r
1169                         p_item2 = cl_qmap_next( p_item2 );\r
1170                 }\r
1171         }\r
1172 \r
1173         /* Process the remainder if the end of either source map was reached. */\r
1174         while( p_item2 != cl_qmap_end( p_map2 ) )\r
1175                 __cl_qmap_delta_move( p_new, p_map2, &p_item2 );\r
1176 \r
1177         while( p_item1 != cl_qmap_end( p_map1 ) )\r
1178                 __cl_qmap_delta_move( p_old, p_map1, &p_item1 );\r
1179 }\r
1180 \r
1181 \r
1182 /******************************************************************************\r
1183 *******************************************************************************\r
1184 **************                                                                                                     ************\r
1185 **************                          IMPLEMENTATION OF MAP                              ************\r
1186 **************                                                                                                     ************\r
1187 *******************************************************************************\r
1188 ******************************************************************************/\r
1189 \r
1190 \r
1191 #define MAP_GROW_SIZE 32\r
1192 \r
1193 \r
1194 void\r
1195 cl_map_construct(\r
1196         IN      cl_map_t* const p_map )\r
1197 {\r
1198         CL_ASSERT( p_map );\r
1199 \r
1200         cl_qpool_construct( &p_map->pool );\r
1201 }\r
1202 \r
1203 \r
1204 cl_status_t\r
1205 cl_map_init(\r
1206         IN      cl_map_t* const p_map,\r
1207         IN      const size_t    min_items )\r
1208 {\r
1209         size_t  grow_size;\r
1210 \r
1211         CL_ASSERT( p_map );\r
1212 \r
1213         cl_qmap_init( &p_map->qmap );\r
1214 \r
1215         /*\r
1216          * We will grow by min_items/8 items at a time, with a minimum of\r
1217          * MAP_GROW_SIZE.\r
1218          */\r
1219         grow_size = min_items >> 3;\r
1220         if( grow_size < MAP_GROW_SIZE )\r
1221                 grow_size = MAP_GROW_SIZE;\r
1222 \r
1223         return( cl_qpool_init( &p_map->pool, min_items, 0, grow_size,\r
1224                 sizeof(cl_map_obj_t), NULL, NULL, NULL ) );\r
1225 }\r
1226 \r
1227 \r
1228 void\r
1229 cl_map_destroy(\r
1230         IN      cl_map_t* const p_map )\r
1231 {\r
1232         CL_ASSERT( p_map );\r
1233 \r
1234         cl_qpool_destroy( &p_map->pool );\r
1235 }\r
1236 \r
1237 \r
1238 void*\r
1239 cl_map_insert(\r
1240         IN      cl_map_t* const         p_map,\r
1241         IN      const uint64_t          key,\r
1242         IN      const void* const       p_object )\r
1243 {\r
1244         cl_map_obj_t    *p_map_obj, *p_obj_at_key;\r
1245 \r
1246         CL_ASSERT( p_map );\r
1247 \r
1248         p_map_obj = (cl_map_obj_t*)cl_qpool_get( &p_map->pool );\r
1249 \r
1250         if( !p_map_obj )\r
1251                 return( NULL );\r
1252 \r
1253         cl_qmap_set_obj( p_map_obj, p_object );\r
1254 \r
1255         p_obj_at_key =\r
1256                 (cl_map_obj_t*)cl_qmap_insert( &p_map->qmap, key, &p_map_obj->item );\r
1257 \r
1258         /* Return the item to the pool if insertion failed. */\r
1259         if( p_obj_at_key != p_map_obj )\r
1260                 cl_qpool_put( &p_map->pool, &p_map_obj->item.pool_item );\r
1261 \r
1262         return( cl_qmap_obj( p_obj_at_key ) );\r
1263 }\r
1264 \r
1265 \r
1266 void*\r
1267 cl_map_get(\r
1268         IN      const cl_map_t* const   p_map,\r
1269         IN      const uint64_t                  key )\r
1270 {\r
1271         cl_map_item_t   *p_item;\r
1272 \r
1273         CL_ASSERT( p_map );\r
1274 \r
1275         p_item = cl_qmap_get( &p_map->qmap, key );\r
1276 \r
1277         if( p_item == cl_qmap_end( &p_map->qmap ) )\r
1278                 return( NULL );\r
1279 \r
1280         return( cl_qmap_obj( PARENT_STRUCT( p_item, cl_map_obj_t, item ) ) );\r
1281 }\r
1282 \r
1283 \r
1284 void\r
1285 cl_map_remove_item(\r
1286         IN      cl_map_t* const                 p_map,\r
1287         IN      const cl_map_iterator_t itor )\r
1288 {\r
1289         CL_ASSERT( itor->p_map == &p_map->qmap );\r
1290 \r
1291         if( itor == cl_map_end( p_map ) )\r
1292                 return;\r
1293 \r
1294         cl_qmap_remove_item( &p_map->qmap, (cl_map_item_t*)itor );\r
1295         cl_qpool_put( &p_map->pool, &((cl_map_item_t*)itor)->pool_item );\r
1296 }\r
1297 \r
1298 \r
1299 void*\r
1300 cl_map_remove(\r
1301         IN      cl_map_t* const p_map,\r
1302         IN      const uint64_t  key )\r
1303 {\r
1304         cl_map_item_t   *p_item;\r
1305 \r
1306         CL_ASSERT( p_map );\r
1307 \r
1308         p_item = cl_qmap_remove( &p_map->qmap, key );\r
1309 \r
1310         if( p_item == cl_qmap_end( &p_map->qmap ) )\r
1311                 return( NULL );\r
1312 \r
1313         cl_qpool_put( &p_map->pool, &p_item->pool_item );\r
1314 \r
1315         return( cl_qmap_obj( (cl_map_obj_t*)p_item ) );\r
1316 }\r
1317 \r
1318 \r
1319 void\r
1320 cl_map_remove_all(\r
1321         IN      cl_map_t* const p_map )\r
1322 {\r
1323         cl_map_item_t   *p_item;\r
1324 \r
1325         CL_ASSERT( p_map );\r
1326 \r
1327         /* Return all map items to the pool. */\r
1328         while( !cl_is_qmap_empty( &p_map->qmap ) )\r
1329         {\r
1330                 p_item = cl_qmap_head( &p_map->qmap );\r
1331                 cl_qmap_remove_item( &p_map->qmap, p_item );\r
1332                 cl_qpool_put( &p_map->pool, &p_item->pool_item );\r
1333 \r
1334                 if( !cl_is_qmap_empty( &p_map->qmap ) )\r
1335                 {\r
1336                         p_item = cl_qmap_tail( &p_map->qmap );\r
1337                         cl_qmap_remove_item( &p_map->qmap, p_item );\r
1338                         cl_qpool_put( &p_map->pool, &p_item->pool_item );\r
1339                 }\r
1340         }\r
1341 }\r
1342 \r
1343 \r
1344 cl_status_t\r
1345 cl_map_merge(\r
1346         OUT             cl_map_t* const p_dest_map,\r
1347         IN OUT  cl_map_t* const p_src_map )\r
1348 {\r
1349         cl_status_t                     status = CL_SUCCESS;\r
1350         cl_map_iterator_t       itor, next;\r
1351         uint64_t                        key;\r
1352         void                            *p_obj, *p_obj2;\r
1353 \r
1354         CL_ASSERT( p_dest_map );\r
1355         CL_ASSERT( p_src_map );\r
1356 \r
1357         itor = cl_map_head( p_src_map );\r
1358         while( itor != cl_map_end( p_src_map ) )\r
1359         {\r
1360                 next = cl_map_next( itor );\r
1361 \r
1362                 p_obj = cl_map_obj( itor );\r
1363                 key = cl_map_key( itor );\r
1364 \r
1365                 cl_map_remove_item( p_src_map, itor );\r
1366 \r
1367                 /* Insert the object into the destination map. */\r
1368                 p_obj2 = cl_map_insert( p_dest_map, key, p_obj );\r
1369                 /* Trap for failure. */\r
1370                 if( p_obj != p_obj2 )\r
1371                 {\r
1372                         if( !p_obj2 )\r
1373                                 status = CL_INSUFFICIENT_MEMORY;\r
1374                         /* Put the object back in the source map.  This must succeed. */\r
1375                         p_obj2 = cl_map_insert( p_src_map, key, p_obj );\r
1376                         CL_ASSERT( p_obj == p_obj2 );\r
1377                         /* If the failure was due to insufficient memory, return. */\r
1378                         if( status != CL_SUCCESS )\r
1379                                 return( status );\r
1380                 }\r
1381                 itor = next;\r
1382         }\r
1383 \r
1384         return( CL_SUCCESS );\r
1385 }\r
1386 \r
1387 \r
1388 static void\r
1389 __cl_map_revert(\r
1390         IN OUT  cl_map_t* const p_map1,\r
1391         IN OUT  cl_map_t* const p_map2,\r
1392         IN OUT  cl_map_t* const p_new,\r
1393         IN OUT  cl_map_t* const p_old )\r
1394 {\r
1395         cl_status_t             status;\r
1396 \r
1397         /* Restore the initial state. */\r
1398         status = cl_map_merge( p_map1, p_old );\r
1399         CL_ASSERT( status == CL_SUCCESS );\r
1400         status = cl_map_merge( p_map2, p_new );\r
1401         CL_ASSERT( status == CL_SUCCESS );\r
1402 }\r
1403 \r
1404 \r
1405 static cl_status_t\r
1406 __cl_map_delta_move(\r
1407         OUT             cl_map_t* const                         p_dest,\r
1408         IN OUT  cl_map_t* const                         p_src,\r
1409         IN OUT  cl_map_iterator_t* const        p_itor )\r
1410 {\r
1411         cl_map_iterator_t       next;\r
1412         void                            *p_obj, *p_obj2;\r
1413         uint64_t                        key;\r
1414 \r
1415         /* Get a valid iterator so we can continue the loop. */\r
1416         next = cl_map_next( *p_itor );\r
1417         /* Get the pointer to the object for insertion. */\r
1418         p_obj = cl_map_obj( *p_itor );\r
1419         /* Get the key for the object. */\r
1420         key = cl_map_key( *p_itor );\r
1421         /* Move the object. */\r
1422         cl_map_remove_item( p_src, *p_itor );\r
1423         p_obj2 = cl_map_insert( p_dest, key, p_obj );\r
1424         /* Check for failure. We should never get a duplicate. */\r
1425         if( !p_obj2 )\r
1426         {\r
1427                 p_obj2 = cl_map_insert( p_src, key, p_obj );\r
1428                 CL_ASSERT( p_obj2 == p_obj );\r
1429                 return( CL_INSUFFICIENT_MEMORY );\r
1430         }\r
1431 \r
1432         /* We should never get a duplicate */\r
1433         CL_ASSERT( p_obj == p_obj2 );\r
1434         /* Update the iterator so that it is valid. */\r
1435         (*p_itor) = next;\r
1436 \r
1437         return( CL_SUCCESS );\r
1438 }\r
1439 \r
1440 \r
1441 cl_status_t\r
1442 cl_map_delta(\r
1443         IN OUT  cl_map_t* const p_map1,\r
1444         IN OUT  cl_map_t* const p_map2,\r
1445         OUT             cl_map_t* const p_new,\r
1446         OUT             cl_map_t* const p_old )\r
1447 {\r
1448         cl_map_iterator_t       itor1, itor2;\r
1449         uint64_t                        key1, key2;\r
1450         cl_status_t                     status;\r
1451 \r
1452         CL_ASSERT( p_map1 );\r
1453         CL_ASSERT( p_map2 );\r
1454         CL_ASSERT( p_new );\r
1455         CL_ASSERT( p_old );\r
1456         CL_ASSERT( cl_is_map_empty( p_new ) );\r
1457         CL_ASSERT( cl_is_map_empty( p_old ) );\r
1458 \r
1459         itor1 = cl_map_head( p_map1 );\r
1460         itor2 = cl_map_head( p_map2 );\r
1461 \r
1462         /*\r
1463          * Note that the check is for the end, since duplicate items will remain\r
1464          * in their respective maps.\r
1465          */\r
1466         while( itor1 != cl_map_end( p_map1 ) &&\r
1467                 itor2 != cl_map_end( p_map2 ) )\r
1468         {\r
1469                 key1 = cl_map_key( itor1 );\r
1470                 key2 = cl_map_key( itor2 );\r
1471                 if( key1 < key2 )\r
1472                 {\r
1473                         status = __cl_map_delta_move( p_old, p_map1, &itor1 );\r
1474                         /* Check for failure. */\r
1475                         if( status != CL_SUCCESS )\r
1476                         {\r
1477                                 /* Restore the initial state. */\r
1478                                 __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1479                                 /* Return the failure status. */\r
1480                                 return( status );\r
1481                         }\r
1482                 }\r
1483                 else if( key1 > key2 )\r
1484                 {\r
1485                         status = __cl_map_delta_move( p_new, p_map2, &itor2 );\r
1486                         if( status != CL_SUCCESS )\r
1487                         {\r
1488                                 /* Restore the initial state. */\r
1489                                 __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1490                                 /* Return the failure status. */\r
1491                                 return( status );\r
1492                         }\r
1493                 }\r
1494                 else\r
1495                 {\r
1496                         /* Move both forward since they have the same key. */\r
1497                         itor1 = cl_map_next( itor1 );\r
1498                         itor2 = cl_map_next( itor2 );\r
1499                 }\r
1500         }\r
1501 \r
1502         /* Process the remainder if either source map is empty. */\r
1503         while( itor2 != cl_map_end( p_map2 ) )\r
1504         {\r
1505                 status = __cl_map_delta_move( p_new, p_map2, &itor2 );\r
1506                 if( status != CL_SUCCESS )\r
1507                 {\r
1508                         /* Restore the initial state. */\r
1509                         __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1510                         /* Return the failure status. */\r
1511                         return( status );\r
1512                 }\r
1513         }\r
1514 \r
1515         while( itor1 != cl_map_end( p_map1 ) )\r
1516         {\r
1517                 status = __cl_map_delta_move( p_old, p_map1, &itor1 );\r
1518                 if( status != CL_SUCCESS )\r
1519                 {\r
1520                         /* Restore the initial state. */\r
1521                         __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1522                         /* Return the failure status. */\r
1523                         return( status );\r
1524                 }\r
1525         }\r
1526 \r
1527         return( CL_SUCCESS );\r
1528 }\r
1529 \r
1530 \r
1531 /******************************************************************************\r
1532 *******************************************************************************\r
1533 **************                                                                                                     ************\r
1534 **************                   IMPLEMENTATION OF FLEXI MAP                       ************\r
1535 **************                                                                                                     ************\r
1536 *******************************************************************************\r
1537 ******************************************************************************/\r
1538 \r
1539 /*\r
1540  * Get the root.\r
1541  */\r
1542 static inline cl_fmap_item_t*\r
1543 __cl_fmap_root(\r
1544         IN      const cl_fmap_t* const  p_map )\r
1545 {\r
1546         CL_ASSERT( p_map );\r
1547         return( p_map->root.p_left );\r
1548 }\r
1549 \r
1550 \r
1551 /*\r
1552  * Returns whether a given item is on the left of its parent.\r
1553  */\r
1554 static boolean_t\r
1555 __cl_fmap_is_left_child(\r
1556         IN      const cl_fmap_item_t* const     p_item )\r
1557 {\r
1558         CL_ASSERT( p_item );\r
1559         CL_ASSERT( p_item->p_up );\r
1560         CL_ASSERT( p_item->p_up != p_item );\r
1561 \r
1562         return( p_item->p_up->p_left == p_item );\r
1563 }\r
1564 \r
1565 \r
1566 /*\r
1567  * Retrieve the pointer to the parent's pointer to an item.\r
1568  */\r
1569 static cl_fmap_item_t**\r
1570 __cl_fmap_get_parent_ptr_to_item(\r
1571         IN      cl_fmap_item_t* const   p_item )\r
1572 {\r
1573         CL_ASSERT( p_item );\r
1574         CL_ASSERT( p_item->p_up );\r
1575         CL_ASSERT( p_item->p_up != p_item );\r
1576 \r
1577         if( __cl_fmap_is_left_child( p_item ) )\r
1578                 return( &p_item->p_up->p_left );\r
1579 \r
1580         CL_ASSERT( p_item->p_up->p_right == p_item );\r
1581         return( &p_item->p_up->p_right );\r
1582 }\r
1583 \r
1584 \r
1585 /*\r
1586  * Rotate a node to the left.  This rotation affects the least number of links\r
1587  * between nodes and brings the level of C up by one while increasing the depth\r
1588  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.\r
1589  *\r
1590  *          R                                 R\r
1591  *          |                                 |\r
1592  *          A                                 C\r
1593  *        /   \                         /   \\r
1594  *      W       C                         A       Z\r
1595  *             / \                       / \\r
1596  *            B   Z                     W   B\r
1597  *           / \                           / \\r
1598  *          X   Y                         X   Y\r
1599  */\r
1600 static void\r
1601 __cl_fmap_rot_left(\r
1602         IN      cl_fmap_t* const                p_map,\r
1603         IN      cl_fmap_item_t* const   p_item )\r
1604 {\r
1605         cl_fmap_item_t  **pp_root;\r
1606 \r
1607         CL_ASSERT( p_map );\r
1608         CL_ASSERT( p_item );\r
1609         CL_ASSERT( p_item->p_right != &p_map->nil );\r
1610 \r
1611         pp_root = __cl_fmap_get_parent_ptr_to_item( p_item );\r
1612 \r
1613         /* Point R to C instead of A. */\r
1614         *pp_root = p_item->p_right;\r
1615         /* Set C's parent to R. */\r
1616         (*pp_root)->p_up = p_item->p_up;\r
1617 \r
1618         /* Set A's right to B */\r
1619         p_item->p_right = (*pp_root)->p_left;\r
1620         /*\r
1621          * Set B's parent to A.  We trap for B being NIL since the\r
1622          * caller may depend on NIL not changing.\r
1623          */\r
1624         if( (*pp_root)->p_left != &p_map->nil )\r
1625                 (*pp_root)->p_left->p_up = p_item;\r
1626 \r
1627         /* Set C's left to A. */\r
1628         (*pp_root)->p_left = p_item;\r
1629         /* Set A's parent to C. */\r
1630         p_item->p_up = *pp_root;\r
1631 }\r
1632 \r
1633 \r
1634 /*\r
1635  * Rotate a node to the right.  This rotation affects the least number of links\r
1636  * between nodes and brings the level of A up by one while increasing the depth\r
1637  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.\r
1638  *\r
1639  *              R                                    R\r
1640  *              |                                    |\r
1641  *              C                                    A\r
1642  *            /   \                                /   \\r
1643  *          A       Z                    W       C\r
1644  *         / \                                          / \\r
1645  *        W   B                                        B   Z\r
1646  *           / \                                      / \\r
1647  *          X   Y                                    X   Y\r
1648  */\r
1649 static void\r
1650 __cl_fmap_rot_right(\r
1651         IN      cl_fmap_t* const                p_map,\r
1652         IN      cl_fmap_item_t* const   p_item )\r
1653 {\r
1654         cl_fmap_item_t  **pp_root;\r
1655 \r
1656         CL_ASSERT( p_map );\r
1657         CL_ASSERT( p_item );\r
1658         CL_ASSERT( p_item->p_left != &p_map->nil );\r
1659 \r
1660         /* Point R to A instead of C. */\r
1661         pp_root = __cl_fmap_get_parent_ptr_to_item( p_item );\r
1662         (*pp_root) = p_item->p_left;\r
1663         /* Set A's parent to R. */\r
1664         (*pp_root)->p_up = p_item->p_up;\r
1665 \r
1666         /* Set C's left to B */\r
1667         p_item->p_left = (*pp_root)->p_right;\r
1668         /*\r
1669          * Set B's parent to C.  We trap for B being NIL since the\r
1670          * caller may depend on NIL not changing.\r
1671          */\r
1672         if( (*pp_root)->p_right != &p_map->nil )\r
1673                 (*pp_root)->p_right->p_up = p_item;\r
1674 \r
1675         /* Set A's right to C. */\r
1676         (*pp_root)->p_right = p_item;\r
1677         /* Set C's parent to A. */\r
1678         p_item->p_up = *pp_root;\r
1679 }\r
1680 \r
1681 \r
1682 void\r
1683 cl_fmap_init(\r
1684         IN      cl_fmap_t* const        p_map,\r
1685         IN      cl_pfn_fmap_cmp_t       pfn_compare )\r
1686 {\r
1687         CL_ASSERT( p_map );\r
1688         CL_ASSERT( pfn_compare );\r
1689 \r
1690         cl_memclr( p_map, sizeof(cl_fmap_t) );\r
1691 \r
1692         /* special setup for the root node */\r
1693         p_map->root.p_up = &p_map->root;\r
1694         p_map->root.p_left = &p_map->nil;\r
1695         p_map->root.p_right = &p_map->nil;\r
1696         p_map->root.color = CL_MAP_BLACK;\r
1697 \r
1698         /* Setup the node used as terminator for all leaves. */\r
1699         p_map->nil.p_up = &p_map->nil;\r
1700         p_map->nil.p_left = &p_map->nil;\r
1701         p_map->nil.p_right = &p_map->nil;\r
1702         p_map->nil.color = CL_MAP_BLACK;\r
1703 \r
1704         /* Store the compare function pointer. */\r
1705         p_map->pfn_compare = pfn_compare;\r
1706 \r
1707         p_map->state = CL_INITIALIZED;\r
1708 \r
1709         cl_fmap_remove_all( p_map );\r
1710 }\r
1711 \r
1712 \r
1713 cl_fmap_item_t*\r
1714 cl_fmap_get(\r
1715         IN      const cl_fmap_t* const  p_map,\r
1716         IN      const void* const               p_key )\r
1717 {\r
1718         cl_fmap_item_t  *p_item;\r
1719         intn_t                  cmp;\r
1720 \r
1721         CL_ASSERT( p_map );\r
1722         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1723 \r
1724         p_item = __cl_fmap_root( p_map );\r
1725 \r
1726         while( p_item != &p_map->nil )\r
1727         {\r
1728                 cmp = p_map->pfn_compare( p_key, p_item->p_key );\r
1729 \r
1730                 if( !cmp )\r
1731                         break;                                          /* just right */\r
1732 \r
1733                 if( cmp < 0 )\r
1734                         p_item = p_item->p_left;        /* too small */\r
1735                 else\r
1736                         p_item = p_item->p_right;       /* too big */\r
1737         }\r
1738 \r
1739         return( p_item );\r
1740 }\r
1741 \r
1742 \r
1743 void\r
1744 cl_fmap_apply_func(\r
1745         IN      const cl_fmap_t* const  p_map,\r
1746         IN      cl_pfn_fmap_apply_t             pfn_func,\r
1747         IN      const void* const               context )\r
1748 {\r
1749         cl_fmap_item_t* p_fmap_item;\r
1750 \r
1751         /* Note that context can have any arbitrary value. */\r
1752         CL_ASSERT( p_map );\r
1753         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1754         CL_ASSERT( pfn_func );\r
1755 \r
1756         p_fmap_item = cl_fmap_head( p_map );\r
1757         while( p_fmap_item != cl_fmap_end( p_map ) )\r
1758         {\r
1759                 pfn_func( p_fmap_item, (void*)context );\r
1760                 p_fmap_item = cl_fmap_next( p_fmap_item );\r
1761         }\r
1762 }\r
1763 \r
1764 \r
1765 /*\r
1766  * Balance a tree starting at a given item back to the root.\r
1767  */\r
1768 static void\r
1769 __cl_fmap_ins_bal(\r
1770         IN      cl_fmap_t* const        p_map,\r
1771         IN      cl_fmap_item_t*         p_item )\r
1772 {\r
1773         cl_fmap_item_t*         p_grand_uncle;\r
1774 \r
1775         CL_ASSERT( p_map );\r
1776         CL_ASSERT( p_item );\r
1777         CL_ASSERT( p_item != &p_map->root );\r
1778 \r
1779         while( p_item->p_up->color == CL_MAP_RED )\r
1780         {\r
1781                 if( __cl_fmap_is_left_child( p_item->p_up ) )\r
1782                 {\r
1783                         p_grand_uncle = p_item->p_up->p_up->p_right;\r
1784                         CL_ASSERT( p_grand_uncle );\r
1785                         if( p_grand_uncle->color == CL_MAP_RED )\r
1786                         {\r
1787                                 p_grand_uncle->color = CL_MAP_BLACK;\r
1788                                 p_item->p_up->color = CL_MAP_BLACK;\r
1789                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
1790                                 p_item = p_item->p_up->p_up;\r
1791                                 continue;\r
1792                         }\r
1793 \r
1794                         if( !__cl_fmap_is_left_child( p_item ) )\r
1795                         {\r
1796                                 p_item = p_item->p_up;\r
1797                                 __cl_fmap_rot_left( p_map, p_item );\r
1798                         }\r
1799                         p_item->p_up->color = CL_MAP_BLACK;\r
1800                         p_item->p_up->p_up->color = CL_MAP_RED;\r
1801                         __cl_fmap_rot_right( p_map, p_item->p_up->p_up );\r
1802                 }\r
1803                 else\r
1804                 {\r
1805                         p_grand_uncle = p_item->p_up->p_up->p_left;\r
1806                         CL_ASSERT( p_grand_uncle );\r
1807                         if( p_grand_uncle->color == CL_MAP_RED )\r
1808                         {\r
1809                                 p_grand_uncle->color = CL_MAP_BLACK;\r
1810                                 p_item->p_up->color = CL_MAP_BLACK;\r
1811                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
1812                                 p_item = p_item->p_up->p_up;\r
1813                                 continue;\r
1814                         }\r
1815 \r
1816                         if( __cl_fmap_is_left_child( p_item ) )\r
1817                         {\r
1818                                 p_item = p_item->p_up;\r
1819                                 __cl_fmap_rot_right( p_map, p_item );\r
1820                         }\r
1821                         p_item->p_up->color = CL_MAP_BLACK;\r
1822                         p_item->p_up->p_up->color = CL_MAP_RED;\r
1823                         __cl_fmap_rot_left( p_map, p_item->p_up->p_up );\r
1824                 }\r
1825         }\r
1826 }\r
1827 \r
1828 \r
1829 cl_fmap_item_t*\r
1830 cl_fmap_insert(\r
1831         IN      cl_fmap_t* const                p_map,\r
1832         IN      const void* const               p_key,\r
1833         IN      cl_fmap_item_t* const   p_item )\r
1834 {\r
1835         cl_fmap_item_t  *p_insert_at, *p_comp_item;\r
1836         intn_t                  cmp = 0;\r
1837 \r
1838         CL_ASSERT( p_map );\r
1839         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1840         CL_ASSERT( p_item );\r
1841         CL_ASSERT( p_map->root.p_up == &p_map->root );\r
1842         CL_ASSERT( p_map->root.color != CL_MAP_RED );\r
1843         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
1844 \r
1845         p_item->p_left = &p_map->nil;\r
1846         p_item->p_right = &p_map->nil;\r
1847         p_item->p_key = p_key;\r
1848         p_item->color = CL_MAP_RED;\r
1849 \r
1850         /* Find the insertion location. */\r
1851         p_insert_at = &p_map->root;\r
1852         p_comp_item = __cl_fmap_root( p_map );\r
1853 \r
1854         while( p_comp_item != &p_map->nil )\r
1855         {\r
1856                 p_insert_at = p_comp_item;\r
1857 \r
1858                 cmp = p_map->pfn_compare( p_key, p_insert_at->p_key );\r
1859 \r
1860                 if( !cmp )\r
1861                         return( p_insert_at );\r
1862 \r
1863                 /* Traverse the tree until the correct insertion point is found. */\r
1864                 if( cmp < 0 )\r
1865                         p_comp_item = p_insert_at->p_left;\r
1866                 else\r
1867                         p_comp_item = p_insert_at->p_right;\r
1868         }\r
1869 \r
1870         CL_ASSERT( p_insert_at != &p_map->nil );\r
1871         CL_ASSERT( p_comp_item == &p_map->nil );\r
1872         /* Insert the item. */\r
1873         if( p_insert_at == &p_map->root )\r
1874         {\r
1875                 p_insert_at->p_left = p_item;\r
1876                 /*\r
1877                  * Primitive insert places the new item in front of\r
1878                  * the existing item.\r
1879                  */\r
1880                 __cl_primitive_insert( &p_map->nil.pool_item.list_item,\r
1881                         &p_item->pool_item.list_item );\r
1882         }\r
1883         else if( cmp < 0 )\r
1884         {\r
1885                 p_insert_at->p_left = p_item;\r
1886                 /*\r
1887                  * Primitive insert places the new item in front of\r
1888                  * the existing item.\r
1889                  */\r
1890                 __cl_primitive_insert( &p_insert_at->pool_item.list_item,\r
1891                         &p_item->pool_item.list_item );\r
1892         }\r
1893         else\r
1894         {\r
1895                 p_insert_at->p_right = p_item;\r
1896                 /*\r
1897                  * Primitive insert places the new item in front of\r
1898                  * the existing item.\r
1899                  */\r
1900                 __cl_primitive_insert( p_insert_at->pool_item.list_item.p_next,\r
1901                         &p_item->pool_item.list_item );\r
1902         }\r
1903         /* Increase the count. */\r
1904         p_map->count++;\r
1905 \r
1906         p_item->p_up = p_insert_at;\r
1907 \r
1908         /*\r
1909          * We have added depth to this section of the tree.\r
1910          * Rebalance as necessary as we retrace our path through the tree\r
1911          * and update colors.\r
1912          */\r
1913         __cl_fmap_ins_bal( p_map, p_item );\r
1914 \r
1915         __cl_fmap_root( p_map )->color = CL_MAP_BLACK;\r
1916 \r
1917         /*\r
1918          * Note that it is not necessary to re-color the nil node black because all\r
1919          * red color assignments are made via the p_up pointer, and nil is never\r
1920          * set as the value of a p_up pointer.\r
1921          */\r
1922 \r
1923 #ifdef _DEBUG_\r
1924         /* Set the pointer to the map in the map item for consistency checking. */\r
1925         p_item->p_map = p_map;\r
1926 #endif\r
1927 \r
1928         return( p_item );\r
1929 }\r
1930 \r
1931 \r
1932 static void\r
1933 __cl_fmap_del_bal(\r
1934         IN      cl_fmap_t* const        p_map,\r
1935         IN      cl_fmap_item_t*         p_item )\r
1936 {\r
1937         cl_fmap_item_t          *p_uncle;\r
1938 \r
1939         while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )\r
1940         {\r
1941                 if( __cl_fmap_is_left_child( p_item ) )\r
1942                 {\r
1943                         p_uncle = p_item->p_up->p_right;\r
1944 \r
1945                         if( p_uncle->color == CL_MAP_RED )\r
1946                         {\r
1947                                 p_uncle->color = CL_MAP_BLACK;\r
1948                                 p_item->p_up->color = CL_MAP_RED;\r
1949                                 __cl_fmap_rot_left( p_map, p_item->p_up );\r
1950                                 p_uncle = p_item->p_up->p_right;\r
1951                         }\r
1952 \r
1953                         if( p_uncle->p_right->color != CL_MAP_RED )\r
1954                         {\r
1955                                 if( p_uncle->p_left->color != CL_MAP_RED )\r
1956                                 {\r
1957                                         p_uncle->color = CL_MAP_RED;\r
1958                                         p_item = p_item->p_up;\r
1959                                         continue;\r
1960                                 }\r
1961 \r
1962                                 p_uncle->p_left->color = CL_MAP_BLACK;\r
1963                                 p_uncle->color = CL_MAP_RED;\r
1964                                 __cl_fmap_rot_right( p_map, p_uncle );\r
1965                                 p_uncle = p_item->p_up->p_right;\r
1966                         }\r
1967                         p_uncle->color = p_item->p_up->color;\r
1968                         p_item->p_up->color = CL_MAP_BLACK;\r
1969                         p_uncle->p_right->color = CL_MAP_BLACK;\r
1970                         __cl_fmap_rot_left( p_map, p_item->p_up );\r
1971                         break;\r
1972                 }\r
1973                 else\r
1974                 {\r
1975                         p_uncle = p_item->p_up->p_left;\r
1976 \r
1977                         if( p_uncle->color == CL_MAP_RED )\r
1978                         {\r
1979                                 p_uncle->color = CL_MAP_BLACK;\r
1980                                 p_item->p_up->color = CL_MAP_RED;\r
1981                                 __cl_fmap_rot_right( p_map, p_item->p_up );\r
1982                                 p_uncle = p_item->p_up->p_left;\r
1983                         }\r
1984 \r
1985                         if( p_uncle->p_left->color != CL_MAP_RED )\r
1986                         {\r
1987                                 if( p_uncle->p_right->color != CL_MAP_RED )\r
1988                                 {\r
1989                                         p_uncle->color = CL_MAP_RED;\r
1990                                         p_item = p_item->p_up;\r
1991                                         continue;\r
1992                                 }\r
1993 \r
1994                                 p_uncle->p_right->color = CL_MAP_BLACK;\r
1995                                 p_uncle->color = CL_MAP_RED;\r
1996                                 __cl_fmap_rot_left( p_map, p_uncle );\r
1997                                 p_uncle = p_item->p_up->p_left;\r
1998                         }\r
1999                         p_uncle->color = p_item->p_up->color;\r
2000                         p_item->p_up->color = CL_MAP_BLACK;\r
2001                         p_uncle->p_left->color = CL_MAP_BLACK;\r
2002                         __cl_fmap_rot_right( p_map, p_item->p_up );\r
2003                         break;\r
2004                 }\r
2005         }\r
2006         p_item->color = CL_MAP_BLACK;\r
2007 }\r
2008 \r
2009 \r
2010 void\r
2011 cl_fmap_remove_item(\r
2012         IN      cl_fmap_t* const                p_map,\r
2013         IN      cl_fmap_item_t* const   p_item )\r
2014 {\r
2015         cl_fmap_item_t  *p_child, *p_del_item;\r
2016 \r
2017         CL_ASSERT( p_map );\r
2018         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
2019         CL_ASSERT( p_item );\r
2020         CL_ASSERT( p_item->p_map == p_map );\r
2021 \r
2022         if( p_item == cl_fmap_end( p_map ) )\r
2023                 return;\r
2024 \r
2025         if( (p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil ) )\r
2026         {\r
2027                 /* The item being removed has children on at most on side. */\r
2028                 p_del_item = p_item;\r
2029         }\r
2030         else\r
2031         {\r
2032                 /*\r
2033                  * The item being removed has children on both side.\r
2034                  * We select the item that will replace it.  After removing\r
2035                  * the substitute item and rebalancing, the tree will have the\r
2036                  * correct topology.  Exchanging the substitute for the item\r
2037                  * will finalize the removal.\r
2038                  */\r
2039                 p_del_item = cl_fmap_next( p_item );\r
2040                 CL_ASSERT( p_del_item != &p_map->nil );\r
2041         }\r
2042 \r
2043         /* Remove the item from the list. */\r
2044         __cl_primitive_remove( &p_item->pool_item.list_item );\r
2045         /* Decrement the item count. */\r
2046         p_map->count--;\r
2047 \r
2048         /* Get the pointer to the new root's child, if any. */\r
2049         if( p_del_item->p_left != &p_map->nil )\r
2050                 p_child = p_del_item->p_left;\r
2051         else\r
2052                 p_child = p_del_item->p_right;\r
2053 \r
2054         /*\r
2055          * This assignment may modify the parent pointer of the nil node.\r
2056          * This is inconsequential.\r
2057          */\r
2058         p_child->p_up = p_del_item->p_up;\r
2059         (*__cl_fmap_get_parent_ptr_to_item( p_del_item )) = p_child;\r
2060 \r
2061         if( p_del_item->color != CL_MAP_RED )\r
2062                 __cl_fmap_del_bal( p_map, p_child );\r
2063 \r
2064         /*\r
2065          * Note that the splicing done below does not need to occur before\r
2066          * the tree is balanced, since the actual topology changes are made by the\r
2067          * preceding code.  The topology is preserved by the color assignment made\r
2068          * below (reader should be reminded that p_del_item == p_item in some cases).\r
2069          */\r
2070         if( p_del_item != p_item )\r
2071         {\r
2072                 /*\r
2073                  * Finalize the removal of the specified item by exchanging it with\r
2074                  * the substitute which we removed above.\r
2075                  */\r
2076                 p_del_item->p_up = p_item->p_up;\r
2077                 p_del_item->p_left = p_item->p_left;\r
2078                 p_del_item->p_right = p_item->p_right;\r
2079                 (*__cl_fmap_get_parent_ptr_to_item( p_item )) = p_del_item;\r
2080                 p_item->p_right->p_up = p_del_item;\r
2081                 p_item->p_left->p_up = p_del_item;\r
2082                 p_del_item->color = p_item->color;\r
2083         }\r
2084 \r
2085         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
2086 \r
2087 #ifdef _DEBUG_\r
2088         /* Clear the pointer to the map since the item has been removed. */\r
2089         p_item->p_map = NULL;\r
2090 #endif\r
2091 }\r
2092 \r
2093 \r
2094 cl_fmap_item_t*\r
2095 cl_fmap_remove(\r
2096         IN      cl_fmap_t* const        p_map,\r
2097         IN      const void* const       p_key )\r
2098 {\r
2099         cl_fmap_item_t  *p_item;\r
2100 \r
2101         CL_ASSERT( p_map );\r
2102         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
2103 \r
2104         /* Seek the node with the specified key */\r
2105         p_item = cl_fmap_get( p_map, p_key );\r
2106 \r
2107         cl_fmap_remove_item( p_map, p_item );\r
2108 \r
2109         return( p_item );\r
2110 }\r
2111 \r
2112 \r
2113 void\r
2114 cl_fmap_merge(\r
2115         OUT             cl_fmap_t* const        p_dest_map,\r
2116         IN OUT  cl_fmap_t* const        p_src_map )\r
2117 {\r
2118         cl_fmap_item_t          *p_item, *p_item2, *p_next;\r
2119 \r
2120         CL_ASSERT( p_dest_map );\r
2121         CL_ASSERT( p_src_map );\r
2122 \r
2123         p_item = cl_fmap_head( p_src_map );\r
2124 \r
2125         while( p_item != cl_fmap_end( p_src_map ) )\r
2126         {\r
2127                 p_next = cl_fmap_next( p_item );\r
2128 \r
2129                 /* Remove the item from its current map. */\r
2130                 cl_fmap_remove_item( p_src_map, p_item );\r
2131                 /* Insert the item into the destination map. */\r
2132                 p_item2 = cl_fmap_insert( p_dest_map, cl_fmap_key( p_item ), p_item );\r
2133                 /* Check that the item was successfully inserted. */\r
2134                 if( p_item2 != p_item )\r
2135                 {\r
2136                         /* Put the item in back in the source map. */\r
2137                         p_item2 =\r
2138                                 cl_fmap_insert( p_src_map, cl_fmap_key( p_item ), p_item );\r
2139                         CL_ASSERT( p_item2 == p_item );\r
2140                 }\r
2141                 p_item = p_next;\r
2142         }\r
2143 }\r
2144 \r
2145 \r
2146 static void\r
2147 __cl_fmap_delta_move(\r
2148         IN OUT  cl_fmap_t* const                p_dest,\r
2149         IN OUT  cl_fmap_t* const                p_src,\r
2150         IN OUT  cl_fmap_item_t** const  pp_item )\r
2151 {\r
2152         cl_fmap_item_t          *p_temp, *p_next;\r
2153 \r
2154         /*\r
2155          * Get the next item so that we can ensure that pp_item points to\r
2156          * a valid item upon return from the function.\r
2157          */\r
2158         p_next = cl_fmap_next( *pp_item );\r
2159         /* Move the old item from its current map the the old map. */\r
2160         cl_fmap_remove_item( p_src, *pp_item );\r
2161         p_temp = cl_fmap_insert( p_dest, cl_fmap_key( *pp_item ), *pp_item );\r
2162         /* We should never have duplicates. */\r
2163         CL_ASSERT( p_temp == *pp_item );\r
2164         /* Point pp_item to a valid item in the source map. */\r
2165         (*pp_item) = p_next;\r
2166 }\r
2167 \r
2168 \r
2169 void\r
2170 cl_fmap_delta(\r
2171         IN OUT  cl_fmap_t* const        p_map1,\r
2172         IN OUT  cl_fmap_t* const        p_map2,\r
2173         OUT             cl_fmap_t* const        p_new,\r
2174         OUT             cl_fmap_t* const        p_old )\r
2175 {\r
2176         cl_fmap_item_t          *p_item1, *p_item2;\r
2177         intn_t                          cmp;\r
2178 \r
2179         CL_ASSERT( p_map1 );\r
2180         CL_ASSERT( p_map2 );\r
2181         CL_ASSERT( p_new );\r
2182         CL_ASSERT( p_old );\r
2183         CL_ASSERT( cl_is_fmap_empty( p_new ) );\r
2184         CL_ASSERT( cl_is_fmap_empty( p_old ) );\r
2185 \r
2186         p_item1 = cl_fmap_head( p_map1 );\r
2187         p_item2 = cl_fmap_head( p_map2 );\r
2188 \r
2189         while( p_item1 != cl_fmap_end( p_map1 ) &&\r
2190                 p_item2 != cl_fmap_end( p_map2 ) )\r
2191         {\r
2192                 cmp = p_map1->pfn_compare( cl_fmap_key( p_item1 ),\r
2193                         cl_fmap_key( p_item2 ) );\r
2194                 if( cmp < 0 )\r
2195                 {\r
2196                         /* We found an old item. */\r
2197                         __cl_fmap_delta_move( p_old, p_map1, &p_item1 );\r
2198                 }\r
2199                 else if( cmp > 0 )\r
2200                 {\r
2201                         /* We found a new item. */\r
2202                         __cl_fmap_delta_move( p_new, p_map2, &p_item2 );\r
2203                 }\r
2204                 else\r
2205                 {\r
2206                         /* Move both forward since they have the same key. */\r
2207                         p_item1 = cl_fmap_next( p_item1 );\r
2208                         p_item2 = cl_fmap_next( p_item2 );\r
2209                 }\r
2210         }\r
2211 \r
2212         /* Process the remainder if the end of either source map was reached. */\r
2213         while( p_item2 != cl_fmap_end( p_map2 ) )\r
2214                 __cl_fmap_delta_move( p_new, p_map2, &p_item2 );\r
2215 \r
2216         while( p_item1 != cl_fmap_end( p_map1 ) )\r
2217                 __cl_fmap_delta_move( p_old, p_map1, &p_item1 );\r
2218 }\r