1 /* 2 * Copyright (c) 2004, 2005 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 * Declaration of quick map, a binary tree where the caller always provides 39 * all necessary storage. 40 */ 41 42 #ifndef _CL_QMAP_H_ 43 #define _CL_QMAP_H_ 44 45 #include <complib/cl_qpool.h> 46 47 #ifdef __cplusplus 48 # define BEGIN_C_DECLS extern "C" { 49 # define END_C_DECLS } 50 #else /* !__cplusplus */ 51 # define BEGIN_C_DECLS 52 # define END_C_DECLS 53 #endif /* __cplusplus */ 54 55 BEGIN_C_DECLS 56 /****h* Component Library/Quick Map 57 * NAME 58 * Quick Map 59 * 60 * DESCRIPTION 61 * Quick map implements a binary tree that stores user provided cl_map_item_t 62 * structures. Each item stored in a quick map has a unique 64-bit key 63 * (duplicates are not allowed). Quick map provides the ability to 64 * efficiently search for an item given a key. 65 * 66 * Quick map does not allocate any memory, and can therefore not fail 67 * any operations due to insufficient memory. Quick map can thus be useful 68 * in minimizing the error paths in code. 69 * 70 * Quick map is not thread safe, and users must provide serialization when 71 * adding and removing items from the map. 72 * 73 * The quick map functions operate on a cl_qmap_t structure which should be 74 * treated as opaque and should be manipulated only through the provided 75 * functions. 76 * 77 * SEE ALSO 78 * Structures: 79 * cl_qmap_t, cl_map_item_t, cl_map_obj_t 80 * 81 * Callbacks: 82 * cl_pfn_qmap_apply_t 83 * 84 * Item Manipulation: 85 * cl_qmap_set_obj, cl_qmap_obj, cl_qmap_key 86 * 87 * Initialization: 88 * cl_qmap_init 89 * 90 * Iteration: 91 * cl_qmap_end, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev 92 * 93 * Manipulation: 94 * cl_qmap_insert, cl_qmap_get, cl_qmap_remove_item, cl_qmap_remove, 95 * cl_qmap_remove_all, cl_qmap_merge, cl_qmap_delta, cl_qmap_get_next 96 * 97 * Search: 98 * cl_qmap_apply_func 99 * 100 * Attributes: 101 * cl_qmap_count, cl_is_qmap_empty, 102 *********/ 103 /****i* Component Library: Quick Map/cl_map_color_t 104 * NAME 105 * cl_map_color_t 106 * 107 * DESCRIPTION 108 * The cl_map_color_t enumerated type is used to note the color of 109 * nodes in a map. 110 * 111 * SYNOPSIS 112 */ 113 typedef enum _cl_map_color { 114 CL_MAP_RED, 115 CL_MAP_BLACK 116 } cl_map_color_t; 117 /* 118 * VALUES 119 * CL_MAP_RED 120 * The node in the map is red. 121 * 122 * CL_MAP_BLACK 123 * The node in the map is black. 124 * 125 * SEE ALSO 126 * Quick Map, cl_map_item_t 127 *********/ 128 129 /****s* Component Library: Quick Map/cl_map_item_t 130 * NAME 131 * cl_map_item_t 132 * 133 * DESCRIPTION 134 * The cl_map_item_t structure is used by maps to store objects. 135 * 136 * The cl_map_item_t structure should be treated as opaque and should 137 * be manipulated only through the provided functions. 138 * 139 * SYNOPSIS 140 */ 141 typedef struct _cl_map_item { 142 /* Must be first to allow casting. */ 143 cl_pool_item_t pool_item; 144 struct _cl_map_item *p_left; 145 struct _cl_map_item *p_right; 146 struct _cl_map_item *p_up; 147 cl_map_color_t color; 148 uint64_t key; 149 #ifdef _DEBUG_ 150 struct _cl_qmap *p_map; 151 #endif 152 } cl_map_item_t; 153 /* 154 * FIELDS 155 * pool_item 156 * Used to store the item in a doubly linked list, allowing more 157 * efficient map traversal. 158 * 159 * p_left 160 * Pointer to the map item that is a child to the left of the node. 161 * 162 * p_right 163 * Pointer to the map item that is a child to the right of the node. 164 * 165 * p_up 166 * Pointer to the map item that is the parent of the node. 167 * 168 * p_nil 169 * Pointer to the map's NIL item, used as a terminator for leaves. 170 * The NIL sentinel is in the cl_qmap_t structure. 171 * 172 * color 173 * Indicates whether a node is red or black in the map. 174 * 175 * key 176 * Value that uniquely represents a node in a map. This value is 177 * set by calling cl_qmap_insert and can be retrieved by calling 178 * cl_qmap_key. 179 * 180 * NOTES 181 * None of the fields of this structure should be manipulated by users, as 182 * they are crititcal to the proper operation of the map in which they 183 * are stored. 184 * 185 * To allow storing items in either a quick list, a quick pool, or a quick 186 * map, the map implementation guarantees that the map item can be safely 187 * cast to a pool item used for storing an object in a quick pool, or cast 188 * to a list item used for storing an object in a quick list. This removes 189 * the need to embed a map item, a list item, and a pool item in objects 190 * that need to be stored in a quick list, a quick pool, and a quick map. 191 * 192 * SEE ALSO 193 * Quick Map, cl_qmap_insert, cl_qmap_key, cl_pool_item_t, cl_list_item_t 194 *********/ 195 196 /****s* Component Library: Quick Map/cl_map_obj_t 197 * NAME 198 * cl_map_obj_t 199 * 200 * DESCRIPTION 201 * The cl_map_obj_t structure is used to store objects in maps. 202 * 203 * The cl_map_obj_t structure should be treated as opaque and should 204 * be manipulated only through the provided functions. 205 * 206 * SYNOPSIS 207 */ 208 typedef struct _cl_map_obj { 209 cl_map_item_t item; 210 const void *p_object; 211 } cl_map_obj_t; 212 /* 213 * FIELDS 214 * item 215 * Map item used by internally by the map to store an object. 216 * 217 * p_object 218 * User defined context. Users should not access this field directly. 219 * Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the value 220 * of this field. 221 * 222 * NOTES 223 * None of the fields of this structure should be manipulated by users, as 224 * they are crititcal to the proper operation of the map in which they 225 * are stored. 226 * 227 * Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the object 228 * stored in a map item, respectively. 229 * 230 * SEE ALSO 231 * Quick Map, cl_qmap_set_obj, cl_qmap_obj, cl_map_item_t 232 *********/ 233 234 /****s* Component Library: Quick Map/cl_qmap_t 235 * NAME 236 * cl_qmap_t 237 * 238 * DESCRIPTION 239 * Quick map structure. 240 * 241 * The cl_qmap_t structure should be treated as opaque and should 242 * be manipulated only through the provided functions. 243 * 244 * SYNOPSIS 245 */ 246 typedef struct _cl_qmap { 247 cl_map_item_t root; 248 cl_map_item_t nil; 249 cl_state_t state; 250 size_t count; 251 } cl_qmap_t; 252 /* 253 * PARAMETERS 254 * root 255 * Map item that serves as root of the map. The root is set up to 256 * always have itself as parent. The left pointer is set to point 257 * to the item at the root. 258 * 259 * nil 260 * Map item that serves as terminator for all leaves, as well as 261 * providing the list item used as quick list for storing map items 262 * in a list for faster traversal. 263 * 264 * state 265 * State of the map, used to verify that operations are permitted. 266 * 267 * count 268 * Number of items in the map. 269 * 270 * SEE ALSO 271 * Quick Map 272 *********/ 273 274 /****d* Component Library: Quick Map/cl_pfn_qmap_apply_t 275 * NAME 276 * cl_pfn_qmap_apply_t 277 * 278 * DESCRIPTION 279 * The cl_pfn_qmap_apply_t function type defines the prototype for 280 * functions used to iterate items in a quick map. 281 * 282 * SYNOPSIS 283 */ 284 typedef void 285 (*cl_pfn_qmap_apply_t) (IN cl_map_item_t * const p_map_item, IN void *context); 286 /* 287 * PARAMETERS 288 * p_map_item 289 * [in] Pointer to a cl_map_item_t structure. 290 * 291 * context 292 * [in] Value passed to the callback function. 293 * 294 * RETURN VALUE 295 * This function does not return a value. 296 * 297 * NOTES 298 * This function type is provided as function prototype reference for the 299 * function provided by users as a parameter to the cl_qmap_apply_func 300 * function. 301 * 302 * SEE ALSO 303 * Quick Map, cl_qmap_apply_func 304 *********/ 305 306 /****f* Component Library: Quick Map/cl_qmap_count 307 * NAME 308 * cl_qmap_count 309 * 310 * DESCRIPTION 311 * The cl_qmap_count function returns the number of items stored 312 * in a quick map. 313 * 314 * SYNOPSIS 315 */ 316 static inline uint32_t cl_qmap_count(IN const cl_qmap_t * const p_map) 317 { 318 CL_ASSERT(p_map); 319 CL_ASSERT(p_map->state == CL_INITIALIZED); 320 return ((uint32_t) p_map->count); 321 } 322 323 /* 324 * PARAMETERS 325 * p_map 326 * [in] Pointer to a cl_qmap_t structure whose item count to return. 327 * 328 * RETURN VALUE 329 * Returns the number of items stored in the map. 330 * 331 * SEE ALSO 332 * Quick Map, cl_is_qmap_empty 333 *********/ 334 335 /****f* Component Library: Quick Map/cl_is_qmap_empty 336 * NAME 337 * cl_is_qmap_empty 338 * 339 * DESCRIPTION 340 * The cl_is_qmap_empty function returns whether a quick map is empty. 341 * 342 * SYNOPSIS 343 */ 344 static inline boolean_t cl_is_qmap_empty(IN const cl_qmap_t * const p_map) 345 { 346 CL_ASSERT(p_map); 347 CL_ASSERT(p_map->state == CL_INITIALIZED); 348 349 return (p_map->count == 0); 350 } 351 352 /* 353 * PARAMETERS 354 * p_map 355 * [in] Pointer to a cl_qmap_t structure to test for emptiness. 356 * 357 * RETURN VALUES 358 * TRUE if the quick map is empty. 359 * 360 * FALSE otherwise. 361 * 362 * SEE ALSO 363 * Quick Map, cl_qmap_count, cl_qmap_remove_all 364 *********/ 365 366 /****f* Component Library: Quick Map/cl_qmap_set_obj 367 * NAME 368 * cl_qmap_set_obj 369 * 370 * DESCRIPTION 371 * The cl_qmap_set_obj function sets the object stored in a map object. 372 * 373 * SYNOPSIS 374 */ 375 static inline void 376 cl_qmap_set_obj(IN cl_map_obj_t * const p_map_obj, 377 IN const void *const p_object) 378 { 379 CL_ASSERT(p_map_obj); 380 p_map_obj->p_object = p_object; 381 } 382 383 /* 384 * PARAMETERS 385 * p_map_obj 386 * [in] Pointer to a map object stucture whose object pointer 387 * is to be set. 388 * 389 * p_object 390 * [in] User defined context. 391 * 392 * RETURN VALUE 393 * This function does not return a value. 394 * 395 * SEE ALSO 396 * Quick Map, cl_qmap_obj 397 *********/ 398 399 /****f* Component Library: Quick Map/cl_qmap_obj 400 * NAME 401 * cl_qmap_obj 402 * 403 * DESCRIPTION 404 * The cl_qmap_obj function returns the object stored in a map object. 405 * 406 * SYNOPSIS 407 */ 408 static inline void *cl_qmap_obj(IN const cl_map_obj_t * const p_map_obj) 409 { 410 CL_ASSERT(p_map_obj); 411 return ((void *)p_map_obj->p_object); 412 } 413 414 /* 415 * PARAMETERS 416 * p_map_obj 417 * [in] Pointer to a map object stucture whose object pointer to return. 418 * 419 * RETURN VALUE 420 * Returns the value of the object pointer stored in the map object. 421 * 422 * SEE ALSO 423 * Quick Map, cl_qmap_set_obj 424 *********/ 425 426 /****f* Component Library: Quick Map/cl_qmap_key 427 * NAME 428 * cl_qmap_key 429 * 430 * DESCRIPTION 431 * The cl_qmap_key function retrieves the key value of a map item. 432 * 433 * SYNOPSIS 434 */ 435 static inline uint64_t cl_qmap_key(IN const cl_map_item_t * const p_item) 436 { 437 CL_ASSERT(p_item); 438 return (p_item->key); 439 } 440 441 /* 442 * PARAMETERS 443 * p_item 444 * [in] Pointer to a map item whose key value to return. 445 * 446 * RETURN VALUE 447 * Returns the 64-bit key value for the specified map item. 448 * 449 * NOTES 450 * The key value is set in a call to cl_qmap_insert. 451 * 452 * SEE ALSO 453 * Quick Map, cl_qmap_insert 454 *********/ 455 456 /****f* Component Library: Quick Map/cl_qmap_init 457 * NAME 458 * cl_qmap_init 459 * 460 * DESCRIPTION 461 * The cl_qmap_init function initialized a quick map for use. 462 * 463 * SYNOPSIS 464 */ 465 void cl_qmap_init(IN cl_qmap_t * const p_map); 466 /* 467 * PARAMETERS 468 * p_map 469 * [in] Pointer to a cl_qmap_t structure to initialize. 470 * 471 * RETURN VALUES 472 * This function does not return a value. 473 * 474 * NOTES 475 * Allows calling quick map manipulation functions. 476 * 477 * SEE ALSO 478 * Quick Map, cl_qmap_insert, cl_qmap_remove 479 *********/ 480 481 /****f* Component Library: Quick Map/cl_qmap_end 482 * NAME 483 * cl_qmap_end 484 * 485 * DESCRIPTION 486 * The cl_qmap_end function returns the end of a quick map. 487 * 488 * SYNOPSIS 489 */ 490 static inline const cl_map_item_t *cl_qmap_end(IN const cl_qmap_t * const p_map) 491 { 492 CL_ASSERT(p_map); 493 CL_ASSERT(p_map->state == CL_INITIALIZED); 494 /* Nil is the end of the map. */ 495 return (&p_map->nil); 496 } 497 498 /* 499 * PARAMETERS 500 * p_map 501 * [in] Pointer to a cl_qmap_t structure whose end to return. 502 * 503 * RETURN VALUE 504 * Pointer to the end of the map. 505 * 506 * NOTES 507 * cl_qmap_end is useful for determining the validity of map items returned 508 * by cl_qmap_head, cl_qmap_tail, cl_qmap_next, or cl_qmap_prev. If the 509 * map item pointer returned by any of these functions compares to the end, 510 * the end of the map was encoutered. 511 * When using cl_qmap_head or cl_qmap_tail, this condition indicates that 512 * the map is empty. 513 * 514 * SEE ALSO 515 * Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev 516 *********/ 517 518 /****f* Component Library: Quick Map/cl_qmap_head 519 * NAME 520 * cl_qmap_head 521 * 522 * DESCRIPTION 523 * The cl_qmap_head function returns the map item with the lowest key 524 * value stored in a quick map. 525 * 526 * SYNOPSIS 527 */ 528 static inline cl_map_item_t *cl_qmap_head(IN const cl_qmap_t * const p_map) 529 { 530 CL_ASSERT(p_map); 531 CL_ASSERT(p_map->state == CL_INITIALIZED); 532 return ((cl_map_item_t *) p_map->nil.pool_item.list_item.p_next); 533 } 534 535 /* 536 * PARAMETERS 537 * p_map 538 * [in] Pointer to a cl_qmap_t structure whose item with the lowest 539 * key is returned. 540 * 541 * RETURN VALUES 542 * Pointer to the map item with the lowest key in the quick map. 543 * 544 * Pointer to the map end if the quick map was empty. 545 * 546 * NOTES 547 * cl_qmap_head does not remove the item from the map. 548 * 549 * SEE ALSO 550 * Quick Map, cl_qmap_tail, cl_qmap_next, cl_qmap_prev, cl_qmap_end, 551 * cl_qmap_item_t 552 *********/ 553 554 /****f* Component Library: Quick Map/cl_qmap_tail 555 * NAME 556 * cl_qmap_tail 557 * 558 * DESCRIPTION 559 * The cl_qmap_tail function returns the map item with the highest key 560 * value stored in a quick map. 561 * 562 * SYNOPSIS 563 */ 564 static inline cl_map_item_t *cl_qmap_tail(IN const cl_qmap_t * const p_map) 565 { 566 CL_ASSERT(p_map); 567 CL_ASSERT(p_map->state == CL_INITIALIZED); 568 return ((cl_map_item_t *) p_map->nil.pool_item.list_item.p_prev); 569 } 570 571 /* 572 * PARAMETERS 573 * p_map 574 * [in] Pointer to a cl_qmap_t structure whose item with the 575 * highest key is returned. 576 * 577 * RETURN VALUES 578 * Pointer to the map item with the highest key in the quick map. 579 * 580 * Pointer to the map end if the quick map was empty. 581 * 582 * NOTES 583 * cl_qmap_end does not remove the item from the map. 584 * 585 * SEE ALSO 586 * Quick Map, cl_qmap_head, cl_qmap_next, cl_qmap_prev, cl_qmap_end, 587 * cl_qmap_item_t 588 *********/ 589 590 /****f* Component Library: Quick Map/cl_qmap_next 591 * NAME 592 * cl_qmap_next 593 * 594 * DESCRIPTION 595 * The cl_qmap_next function returns the map item with the next higher 596 * key value than a specified map item. 597 * 598 * SYNOPSIS 599 */ 600 static inline cl_map_item_t *cl_qmap_next(IN const cl_map_item_t * const p_item) 601 { 602 CL_ASSERT(p_item); 603 return ((cl_map_item_t *) p_item->pool_item.list_item.p_next); 604 } 605 606 /* 607 * PARAMETERS 608 * p_item 609 * [in] Pointer to a map item whose successor to return. 610 * 611 * RETURN VALUES 612 * Pointer to the map item with the next higher key value in a quick map. 613 * 614 * Pointer to the map end if the specified item was the last item in 615 * the quick map. 616 * 617 * SEE ALSO 618 * Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_prev, cl_qmap_end, 619 * cl_map_item_t 620 *********/ 621 622 /****f* Component Library: Quick Map/cl_qmap_prev 623 * NAME 624 * cl_qmap_prev 625 * 626 * DESCRIPTION 627 * The cl_qmap_prev function returns the map item with the next lower 628 * key value than a precified map item. 629 * 630 * SYNOPSIS 631 */ 632 static inline cl_map_item_t *cl_qmap_prev(IN const cl_map_item_t * const p_item) 633 { 634 CL_ASSERT(p_item); 635 return ((cl_map_item_t *) p_item->pool_item.list_item.p_prev); 636 } 637 638 /* 639 * PARAMETERS 640 * p_item 641 * [in] Pointer to a map item whose predecessor to return. 642 * 643 * RETURN VALUES 644 * Pointer to the map item with the next lower key value in a quick map. 645 * 646 * Pointer to the map end if the specifid item was the first item in 647 * the quick map. 648 * 649 * SEE ALSO 650 * Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_end, 651 * cl_map_item_t 652 *********/ 653 654 /****f* Component Library: Quick Map/cl_qmap_insert 655 * NAME 656 * cl_qmap_insert 657 * 658 * DESCRIPTION 659 * The cl_qmap_insert function inserts a map item into a quick map. 660 * NOTE: Only if such a key does not alerady exist in the map !!!! 661 * 662 * SYNOPSIS 663 */ 664 cl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map, 665 IN const uint64_t key, 666 IN cl_map_item_t * const p_item); 667 /* 668 * PARAMETERS 669 * p_map 670 * [in] Pointer to a cl_qmap_t structure into which to add the item. 671 * 672 * key 673 * [in] Value to assign to the item. 674 * 675 * p_item 676 * [in] Pointer to a cl_map_item_t stucture to insert into the quick map. 677 * 678 * RETURN VALUE 679 * Pointer to the item in the map with the specified key. If insertion 680 * was successful, this is the pointer to the item. If an item with the 681 * specified key already exists in the map, the pointer to that item is 682 * returned - but the new key is NOT inserted... 683 * 684 * NOTES 685 * Insertion operations may cause the quick map to rebalance. 686 * 687 * SEE ALSO 688 * Quick Map, cl_qmap_remove, cl_map_item_t 689 *********/ 690 691 /****f* Component Library: Quick Map/cl_qmap_get 692 * NAME 693 * cl_qmap_get 694 * 695 * DESCRIPTION 696 * The cl_qmap_get function returns the map item associated with a key. 697 * 698 * SYNOPSIS 699 */ 700 cl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map, 701 IN const uint64_t key); 702 /* 703 * PARAMETERS 704 * p_map 705 * [in] Pointer to a cl_qmap_t structure from which to retrieve the 706 * item with the specified key. 707 * 708 * key 709 * [in] Key value used to search for the desired map item. 710 * 711 * RETURN VALUES 712 * Pointer to the map item with the desired key value. 713 * 714 * Pointer to the map end if there was no item with the desired key value 715 * stored in the quick map. 716 * 717 * NOTES 718 * cl_qmap_get does not remove the item from the quick map. 719 * 720 * SEE ALSO 721 * Quick Map, cl_qmap_get_next, cl_qmap_remove 722 *********/ 723 724 /****f* Component Library: Quick Map/cl_qmap_get_next 725 * NAME 726 * cl_qmap_get_next 727 * 728 * DESCRIPTION 729 * The cl_qmap_get_next function returns the first map item associated with a 730 * key > the key specified. 731 * 732 * SYNOPSIS 733 */ 734 cl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map, 735 IN const uint64_t key); 736 /* 737 * PARAMETERS 738 * p_map 739 * [in] Pointer to a cl_qmap_t structure from which to retrieve the 740 * first item with a key > the specified key. 741 * 742 * key 743 * [in] Key value used to search for the desired map item. 744 * 745 * RETURN VALUES 746 * Pointer to the first map item with a key > the desired key value. 747 * 748 * Pointer to the map end if there was no item with a key > the desired key 749 * value stored in the quick map. 750 * 751 * NOTES 752 * cl_qmap_get_next does not remove the item from the quick map. 753 * 754 * SEE ALSO 755 * Quick Map, cl_qmap_get, cl_qmap_remove 756 *********/ 757 758 /****f* Component Library: Quick Map/cl_qmap_remove_item 759 * NAME 760 * cl_qmap_remove_item 761 * 762 * DESCRIPTION 763 * The cl_qmap_remove_item function removes the specified map item 764 * from a quick map. 765 * 766 * SYNOPSIS 767 */ 768 void 769 cl_qmap_remove_item(IN cl_qmap_t * const p_map, 770 IN cl_map_item_t * const p_item); 771 /* 772 * PARAMETERS 773 * p_item 774 * [in] Pointer to a map item to remove from its quick map. 775 * 776 * RETURN VALUES 777 * This function does not return a value. 778 * 779 * In a debug build, cl_qmap_remove_item asserts that the item being removed 780 * is in the specified map. 781 * 782 * NOTES 783 * Removes the map item pointed to by p_item from its quick map. 784 * 785 * SEE ALSO 786 * Quick Map, cl_qmap_remove, cl_qmap_remove_all, cl_qmap_insert 787 *********/ 788 789 /****f* Component Library: Quick Map/cl_qmap_remove 790 * NAME 791 * cl_qmap_remove 792 * 793 * DESCRIPTION 794 * The cl_qmap_remove function removes the map item with the specified key 795 * from a quick map. 796 * 797 * SYNOPSIS 798 */ 799 cl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, 800 IN const uint64_t key); 801 /* 802 * PARAMETERS 803 * p_map 804 * [in] Pointer to a cl_qmap_t structure from which to remove the item 805 * with the specified key. 806 * 807 * key 808 * [in] Key value used to search for the map item to remove. 809 * 810 * RETURN VALUES 811 * Pointer to the removed map item if it was found. 812 * 813 * Pointer to the map end if no item with the specified key exists in the 814 * quick map. 815 * 816 * SEE ALSO 817 * Quick Map, cl_qmap_remove_item, cl_qmap_remove_all, cl_qmap_insert 818 *********/ 819 820 /****f* Component Library: Quick Map/cl_qmap_remove_all 821 * NAME 822 * cl_qmap_remove_all 823 * 824 * DESCRIPTION 825 * The cl_qmap_remove_all function removes all items in a quick map, 826 * leaving it empty. 827 * 828 * SYNOPSIS 829 */ 830 static inline void cl_qmap_remove_all(IN cl_qmap_t * const p_map) 831 { 832 CL_ASSERT(p_map); 833 CL_ASSERT(p_map->state == CL_INITIALIZED); 834 835 p_map->root.p_left = &p_map->nil; 836 p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item; 837 p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item; 838 p_map->count = 0; 839 } 840 841 /* 842 * PARAMETERS 843 * p_map 844 * [in] Pointer to a cl_qmap_t structure to empty. 845 * 846 * RETURN VALUES 847 * This function does not return a value. 848 * 849 * SEE ALSO 850 * Quick Map, cl_qmap_remove, cl_qmap_remove_item 851 *********/ 852 853 /****f* Component Library: Quick Map/cl_qmap_merge 854 * NAME 855 * cl_qmap_merge 856 * 857 * DESCRIPTION 858 * The cl_qmap_merge function moves all items from one map to another, 859 * excluding duplicates. 860 * 861 * SYNOPSIS 862 */ 863 void 864 cl_qmap_merge(OUT cl_qmap_t * const p_dest_map, 865 IN OUT cl_qmap_t * const p_src_map); 866 /* 867 * PARAMETERS 868 * p_dest_map 869 * [out] Pointer to a cl_qmap_t structure to which items should be added. 870 * 871 * p_src_map 872 * [in/out] Pointer to a cl_qmap_t structure whose items to add 873 * to p_dest_map. 874 * 875 * RETURN VALUES 876 * This function does not return a value. 877 * 878 * NOTES 879 * Items are evaluated based on their keys only. 880 * 881 * Upon return from cl_qmap_merge, the quick map referenced by p_src_map 882 * contains all duplicate items. 883 * 884 * SEE ALSO 885 * Quick Map, cl_qmap_delta 886 *********/ 887 888 /****f* Component Library: Quick Map/cl_qmap_delta 889 * NAME 890 * cl_qmap_delta 891 * 892 * DESCRIPTION 893 * The cl_qmap_delta function computes the differences between two maps. 894 * 895 * SYNOPSIS 896 */ 897 void 898 cl_qmap_delta(IN OUT cl_qmap_t * const p_map1, 899 IN OUT cl_qmap_t * const p_map2, 900 OUT cl_qmap_t * const p_new, OUT cl_qmap_t * const p_old); 901 /* 902 * PARAMETERS 903 * p_map1 904 * [in/out] Pointer to the first of two cl_qmap_t structures whose 905 * differences to compute. 906 * 907 * p_map2 908 * [in/out] Pointer to the second of two cl_qmap_t structures whose 909 * differences to compute. 910 * 911 * p_new 912 * [out] Pointer to an empty cl_qmap_t structure that contains the 913 * items unique to p_map2 upon return from the function. 914 * 915 * p_old 916 * [out] Pointer to an empty cl_qmap_t structure that contains the 917 * items unique to p_map1 upon return from the function. 918 * 919 * RETURN VALUES 920 * This function does not return a value. 921 * 922 * NOTES 923 * Items are evaluated based on their keys. Items that exist in both 924 * p_map1 and p_map2 remain in their respective maps. Items that 925 * exist only p_map1 are moved to p_old. Likewise, items that exist only 926 * in p_map2 are moved to p_new. This function can be useful in evaluating 927 * changes between two maps. 928 * 929 * Both maps pointed to by p_new and p_old must be empty on input. This 930 * requirement removes the possibility of failures. 931 * 932 * SEE ALSO 933 * Quick Map, cl_qmap_merge 934 *********/ 935 936 /****f* Component Library: Quick Map/cl_qmap_apply_func 937 * NAME 938 * cl_qmap_apply_func 939 * 940 * DESCRIPTION 941 * The cl_qmap_apply_func function executes a specified function 942 * for every item stored in a quick map. 943 * 944 * SYNOPSIS 945 */ 946 void 947 cl_qmap_apply_func(IN const cl_qmap_t * const p_map, 948 IN cl_pfn_qmap_apply_t pfn_func, 949 IN const void *const context); 950 /* 951 * PARAMETERS 952 * p_map 953 * [in] Pointer to a cl_qmap_t structure. 954 * 955 * pfn_func 956 * [in] Function invoked for every item in the quick map. 957 * See the cl_pfn_qmap_apply_t function type declaration for 958 * details about the callback function. 959 * 960 * context 961 * [in] Value to pass to the callback functions to provide context. 962 * 963 * RETURN VALUE 964 * This function does not return a value. 965 * 966 * NOTES 967 * The function provided must not perform any map operations, as these 968 * would corrupt the quick map. 969 * 970 * SEE ALSO 971 * Quick Map, cl_pfn_qmap_apply_t 972 *********/ 973 974 END_C_DECLS 975 #endif /* _CL_QMAP_H_ */ 976