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