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