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 55BEGIN_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*/ 118typedef 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*/ 184typedef 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*/ 220typedef 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*/ 263typedef 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*/ 296static 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*/ 324static 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*/ 355static 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*/ 386void 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*/ 416static 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*/ 455static 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*/ 491static 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*/ 527static 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*/ 560static 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*/ 592cl_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*/ 631cl_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*/ 667cl_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*/ 701cl_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*/ 735void 736cl_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*/ 766cl_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*/ 798static 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*/ 831void 832cl_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*/ 865void 866cl_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*/ 914void 915cl_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 942END_C_DECLS 943#endif /* _CL_FLEXIMAP_H_ */ 944