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