contrib/ofed/management/opensm/include/complib/cl_qmap.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 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_ */