contrib/ofed/management/opensm/include/complib/cl_fleximap.h

   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 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 intn_t
 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 key
 466 *               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_get
 623 * NAME
 624 *       cl_fmap_get
 625 *
 626 * DESCRIPTION
 627 *       The cl_fmap_get function returns the map item associated with a key.
 628 *
 629 * SYNOPSIS
 630 */
 631 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map,
 632                             IN const void *const p_key);
 633 /*
 634 * PARAMETERS
 635 *       p_map
 636 *               [in] Pointer to a cl_fmap_t structure from which to retrieve the
 637 *               item with the specified key.
 638 *
 639 *       p_key
 640 *               [in] Pointer to a key value used to search for the desired map item.
 641 *
 642 * RETURN VALUES
 643 *       Pointer to the map item with the desired key value.
 644 *
 645 *       Pointer to the map end if there was no item with the desired key value
 646 *       stored in the flexi map.
 647 *
 648 * NOTES
 649 *       cl_fmap_get does not remove the item from the flexi map.
 650 *
 651 * SEE ALSO
 652 *       Flexi Map, cl_fmap_remove, cl_fmap_get_next
 653 *********/
 654
 655 /****f* Component Library: Flexi Map/cl_fmap_get_next
 656 * NAME
 657 *       cl_fmap_get_next
 658 *
 659 * DESCRIPTION
 660 *       The cl_fmap_get_next function returns the first map item associated with a
 661 *       key > the key specified.
 662 *
 663 * SYNOPSIS
 664 */
 665 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map,
 666                                  IN const void *const p_key);
 667 /*
 668 * PARAMETERS
 669 *       p_map
 670 *               [in] Pointer to a cl_fmap_t structure from which to retrieve the
 671 *               item with the specified key.
 672 *
 673 *       p_key
 674 *               [in] Pointer to a key value used to search for the desired map item.
 675 *
 676 * RETURN VALUES
 677 *       Pointer to the first map item with a key > the  desired key value.
 678 *
 679 *       Pointer to the map end if there was no item with a key > the desired key
 680 *       value stored in the flexi map.
 681 *
 682 * NOTES
 683 *       cl_fmap_get_next does not remove the item from the flexi map.
 684 *
 685 * SEE ALSO
 686 *       Flexi Map, cl_fmap_remove, cl_fmap_get
 687 *********/
 688
 689 /****f* Component Library: Flexi Map/cl_fmap_remove_item
 690 * NAME
 691 *       cl_fmap_remove_item
 692 *
 693 * DESCRIPTION
 694 *       The cl_fmap_remove_item function removes the specified map item
 695 *       from a flexi map.
 696 *
 697 * SYNOPSIS
 698 */
 699 void
 700 cl_fmap_remove_item(IN cl_fmap_t * const p_map,
 701                     IN cl_fmap_item_t * const p_item);
 702 /*
 703 * PARAMETERS
 704 *       p_item
 705 *               [in] Pointer to a map item to remove from its flexi map.
 706 *
 707 * RETURN VALUES
 708 *       This function does not return a value.
 709 *
 710 *       In a debug build, cl_fmap_remove_item asserts that the item being
 711 *       removed es in the specified map.
 712 *
 713 * NOTES
 714 *       Removes the map item pointed to by p_item from its flexi map.
 715 *
 716 * SEE ALSO
 717 *       Flexi Map, cl_fmap_remove, cl_fmap_remove_all, cl_fmap_insert
 718 *********/
 719
 720 /****f* Component Library: Flexi Map/cl_fmap_remove
 721 * NAME
 722 *       cl_fmap_remove
 723 *
 724 * DESCRIPTION
 725 *       The cl_fmap_remove function removes the map item with the specified key
 726 *       from a flexi map.
 727 *
 728 * SYNOPSIS
 729 */
 730 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map,
 731                                IN const void *const p_key);
 732 /*
 733 * PARAMETERS
 734 *       p_map
 735 *               [in] Pointer to a cl_fmap_t structure from which to remove the
 736 *               item with the specified key.
 737 *
 738 *       p_key
 739 *               [in] Pointer to the key value used to search for the map item
 740 *               to remove.
 741 *
 742 * RETURN VALUES
 743 *       Pointer to the removed map item if it was found.
 744 *
 745 *       Pointer to the map end if no item with the specified key exists in the
 746 *       flexi map.
 747 *
 748 * SEE ALSO
 749 *       Flexi Map, cl_fmap_remove_item, cl_fmap_remove_all, cl_fmap_insert
 750 *********/
 751
 752 /****f* Component Library: Flexi Map/cl_fmap_remove_all
 753 * NAME
 754 *       cl_fmap_remove_all
 755 *
 756 * DESCRIPTION
 757 *       The cl_fmap_remove_all function removes all items in a flexi map,
 758 *       leaving it empty.
 759 *
 760 * SYNOPSIS
 761 */
 762 static inline void cl_fmap_remove_all(IN cl_fmap_t * const p_map)
 763 {
 764         CL_ASSERT(p_map);
 765         CL_ASSERT(p_map->state == CL_INITIALIZED);
 766
 767         p_map->root.p_left = &p_map->nil;
 768         p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item;
 769         p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item;
 770         p_map->count = 0;
 771 }
 772
 773 /*
 774 * PARAMETERS
 775 *       p_map
 776 *               [in] Pointer to a cl_fmap_t structure to empty.
 777 *
 778 * RETURN VALUES
 779 *       This function does not return a value.
 780 *
 781 * SEE ALSO
 782 *       Flexi Map, cl_fmap_remove, cl_fmap_remove_item
 783 *********/
 784
 785 /****f* Component Library: Flexi Map/cl_fmap_merge
 786 * NAME
 787 *       cl_fmap_merge
 788 *
 789 * DESCRIPTION
 790 *       The cl_fmap_merge function moves all items from one map to another,
 791 *       excluding duplicates.
 792 *
 793 * SYNOPSIS
 794 */
 795 void
 796 cl_fmap_merge(OUT cl_fmap_t * const p_dest_map,
 797               IN OUT cl_fmap_t * const p_src_map);
 798 /*
 799 * PARAMETERS
 800 *       p_dest_map
 801 *               [out] Pointer to a cl_fmap_t structure to which items should be added.
 802 *
 803 *       p_src_map
 804 *               [in/out] Pointer to a cl_fmap_t structure whose items to add
 805 *               to p_dest_map.
 806 *
 807 * RETURN VALUES
 808 *       This function does not return a value.
 809 *
 810 * NOTES
 811 *       Items are evaluated based on their keys only.
 812 *
 813 *       Upon return from cl_fmap_merge, the flexi map referenced by p_src_map
 814 *       contains all duplicate items.
 815 *
 816 * SEE ALSO
 817 *       Flexi Map, cl_fmap_delta
 818 *********/
 819
 820 /****f* Component Library: Flexi Map/cl_fmap_delta
 821 * NAME
 822 *       cl_fmap_delta
 823 *
 824 * DESCRIPTION
 825 *       The cl_fmap_delta function computes the differences between two maps.
 826 *
 827 * SYNOPSIS
 828 */
 829 void
 830 cl_fmap_delta(IN OUT cl_fmap_t * const p_map1,
 831               IN OUT cl_fmap_t * const p_map2,
 832               OUT cl_fmap_t * const p_new, OUT cl_fmap_t * const p_old);
 833 /*
 834 * PARAMETERS
 835 *       p_map1
 836 *               [in/out] Pointer to the first of two cl_fmap_t structures whose
 837 *               differences to compute.
 838 *
 839 *       p_map2
 840 *               [in/out] Pointer to the second of two cl_fmap_t structures whose
 841 *               differences to compute.
 842 *
 843 *       p_new
 844 *               [out] Pointer to an empty cl_fmap_t structure that contains the
 845 *               items unique to p_map2 upon return from the function.
 846 *
 847 *       p_old
 848 *               [out] Pointer to an empty cl_fmap_t structure that contains the
 849 *               items unique to p_map1 upon return from the function.
 850 *
 851 * RETURN VALUES
 852 *       This function does not return a value.
 853 *
 854 * NOTES
 855 *       Items are evaluated based on their keys.  Items that exist in both
 856 *       p_map1 and p_map2 remain in their respective maps.  Items that
 857 *       exist only p_map1 are moved to p_old.  Likewise, items that exist only
 858 *       in p_map2 are moved to p_new.  This function can be useful in evaluating
 859 *       changes between two maps.
 860 *
 861 *       Both maps pointed to by p_new and p_old must be empty on input.  This
 862 *       requirement removes the possibility of failures.
 863 *
 864 * SEE ALSO
 865 *       Flexi Map, cl_fmap_merge
 866 *********/
 867
 868 /****f* Component Library: Flexi Map/cl_fmap_apply_func
 869 * NAME
 870 *       cl_fmap_apply_func
 871 *
 872 * DESCRIPTION
 873 *       The cl_fmap_apply_func function executes a specified function
 874 *       for every item stored in a flexi map.
 875 *
 876 * SYNOPSIS
 877 */
 878 void
 879 cl_fmap_apply_func(IN const cl_fmap_t * const p_map,
 880                    IN cl_pfn_fmap_apply_t pfn_func,
 881                    IN const void *const context);
 882 /*
 883 * PARAMETERS
 884 *       p_map
 885 *               [in] Pointer to a cl_fmap_t structure.
 886 *
 887 *       pfn_func
 888 *               [in] Function invoked for every item in the flexi map.
 889 *               See the cl_pfn_fmap_apply_t function type declaration for
 890 *               details about the callback function.
 891 *
 892 *       context
 893 *               [in] Value to pass to the callback functions to provide context.
 894 *
 895 * RETURN VALUE
 896 *       This function does not return a value.
 897 *
 898 * NOTES
 899 *       The function provided must not perform any map operations, as these
 900 *       would corrupt the flexi map.
 901 *
 902 * SEE ALSO
 903 *       Flexi Map, cl_pfn_fmap_apply_t
 904 *********/
 905
 906 END_C_DECLS
 907 #endif                          /* _CL_FLEXIMAP_H_ */