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 55BEGIN_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*/ 113typedef 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*/ 141typedef 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*/ 208typedef 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*/ 246typedef 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*/ 284typedef 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*/ 316static 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*/ 344static 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*/ 375static inline void 376cl_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*/ 408static 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*/ 435static 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*/ 465void 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*/ 490static 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*/ 528static 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*/ 564static 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*/ 600static 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*/ 632static 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*/ 664cl_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*/ 700cl_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*/ 734cl_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*/ 768void 769cl_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*/ 799cl_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*/ 830static 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*/ 863void 864cl_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*/ 897void 898cl_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*/ 946void 947cl_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 974END_C_DECLS 975#endif /* _CL_QMAP_H_ */ 976