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