1219820Sjeff/* 2219820Sjeff * Copyright (c) 2004, 2005 Voltaire, Inc. All rights reserved. 3219820Sjeff * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved. 4219820Sjeff * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5219820Sjeff * 6219820Sjeff * This software is available to you under a choice of one of two 7219820Sjeff * licenses. You may choose to be licensed under the terms of the GNU 8219820Sjeff * General Public License (GPL) Version 2, available from the file 9219820Sjeff * COPYING in the main directory of this source tree, or the 10219820Sjeff * OpenIB.org BSD license below: 11219820Sjeff * 12219820Sjeff * Redistribution and use in source and binary forms, with or 13219820Sjeff * without modification, are permitted provided that the following 14219820Sjeff * conditions are met: 15219820Sjeff * 16219820Sjeff * - Redistributions of source code must retain the above 17219820Sjeff * copyright notice, this list of conditions and the following 18219820Sjeff * disclaimer. 19219820Sjeff * 20219820Sjeff * - Redistributions in binary form must reproduce the above 21219820Sjeff * copyright notice, this list of conditions and the following 22219820Sjeff * disclaimer in the documentation and/or other materials 23219820Sjeff * provided with the distribution. 24219820Sjeff * 25219820Sjeff * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26219820Sjeff * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27219820Sjeff * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28219820Sjeff * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29219820Sjeff * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30219820Sjeff * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31219820Sjeff * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32219820Sjeff * SOFTWARE. 33219820Sjeff * 34219820Sjeff */ 35219820Sjeff 36219820Sjeff/* 37219820Sjeff * Abstract: 38219820Sjeff * Declaration of map, a binary tree. 39219820Sjeff */ 40219820Sjeff 41219820Sjeff#ifndef _CL_MAP_H_ 42219820Sjeff#define _CL_MAP_H_ 43219820Sjeff 44219820Sjeff#include <complib/cl_qmap.h> 45219820Sjeff#include <complib/cl_qpool.h> 46219820Sjeff 47219820Sjeff#ifdef __cplusplus 48219820Sjeff# define BEGIN_C_DECLS extern "C" { 49219820Sjeff# define END_C_DECLS } 50219820Sjeff#else /* !__cplusplus */ 51219820Sjeff# define BEGIN_C_DECLS 52219820Sjeff# define END_C_DECLS 53219820Sjeff#endif /* __cplusplus */ 54219820Sjeff 55219820SjeffBEGIN_C_DECLS 56219820Sjeff/****h* Component Library/Map 57219820Sjeff* NAME 58219820Sjeff* Map 59219820Sjeff* 60219820Sjeff* DESCRIPTION 61219820Sjeff* Map implements a binary tree that stores user objects. Each item stored 62219820Sjeff* in a map has a unique 64-bit key (duplicates are not allowed). Map 63219820Sjeff* provides the ability to efficiently search for an item given a key. 64219820Sjeff* 65219820Sjeff* Map may allocate memory when inserting objects, and can therefore fail 66219820Sjeff* operations due to insufficient memory. Use quick map in situations 67219820Sjeff* where such insertion failures cannot be tolerated. 68219820Sjeff* 69219820Sjeff* Map is not thread safe, and users must provide serialization when adding 70219820Sjeff* and removing items from the map. 71219820Sjeff* 72219820Sjeff* The map functions operates on a cl_map_t structure which should be treated 73219820Sjeff* as opaque and should be manipulated only through the provided functions. 74219820Sjeff* 75219820Sjeff* SEE ALSO 76219820Sjeff* Types: 77219820Sjeff* cl_map_iterator_t 78219820Sjeff* 79219820Sjeff* Structures: 80219820Sjeff* cl_map_t, cl_map_item_t, cl_map_obj_t 81219820Sjeff* 82219820Sjeff* Item Manipulation: 83219820Sjeff* cl_map_obj, cl_map_key 84219820Sjeff* 85219820Sjeff* Initialization: 86219820Sjeff* cl_map_construct, cl_map_init, cl_map_destroy 87219820Sjeff* 88219820Sjeff* Iteration: 89219820Sjeff* cl_map_end, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev 90219820Sjeff* 91219820Sjeff* Manipulation 92219820Sjeff* cl_map_insert, cl_map_get, cl_map_remove_item, cl_map_remove, 93219820Sjeff* cl_map_remove_all, cl_map_merge, cl_map_delta, cl_map_get_next 94219820Sjeff* 95219820Sjeff* Attributes: 96219820Sjeff* cl_map_count, cl_is_map_empty, cl_is_map_inited 97219820Sjeff*********/ 98219820Sjeff/****s* Component Library: Map/cl_map_t 99219820Sjeff* NAME 100219820Sjeff* cl_map_t 101219820Sjeff* 102219820Sjeff* DESCRIPTION 103219820Sjeff* Quick map structure. 104219820Sjeff* 105219820Sjeff* The cl_map_t structure should be treated as opaque and should 106219820Sjeff* be manipulated only through the provided functions. 107219820Sjeff* 108219820Sjeff* SYNOPSIS 109219820Sjeff*/ 110219820Sjefftypedef struct _cl_map { 111219820Sjeff cl_qmap_t qmap; 112219820Sjeff cl_qpool_t pool; 113219820Sjeff} cl_map_t; 114219820Sjeff/* 115219820Sjeff* FIELDS 116219820Sjeff* qmap 117219820Sjeff* Quick map object that maintains the map. 118219820Sjeff* 119219820Sjeff* pool 120219820Sjeff* Pool of cl_map_obj_t structures used to store user objects 121219820Sjeff* in the map. 122219820Sjeff* 123219820Sjeff* SEE ALSO 124219820Sjeff* Map, cl_map_obj_t 125219820Sjeff*********/ 126219820Sjeff 127219820Sjeff/****d* Component Library: Map/cl_map_iterator_t 128219820Sjeff* NAME 129219820Sjeff* cl_map_iterator_t 130219820Sjeff* 131219820Sjeff* DESCRIPTION 132219820Sjeff* Iterator type used to walk a map. 133219820Sjeff* 134219820Sjeff* SYNOPSIS 135219820Sjeff*/ 136219820Sjefftypedef const cl_map_item_t *cl_map_iterator_t; 137219820Sjeff/* 138219820Sjeff* NOTES 139219820Sjeff* The iterator should be treated as opaque to prevent corrupting the map. 140219820Sjeff* 141219820Sjeff* SEE ALSO 142219820Sjeff* Map, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev, cl_map_key 143219820Sjeff*********/ 144219820Sjeff 145219820Sjeff/****f* Component Library: Map/cl_map_count 146219820Sjeff* NAME 147219820Sjeff* cl_map_count 148219820Sjeff* 149219820Sjeff* DESCRIPTION 150219820Sjeff* The cl_map_count function returns the number of items stored 151219820Sjeff* in a map. 152219820Sjeff* 153219820Sjeff* SYNOPSIS 154219820Sjeff*/ 155219820Sjeffstatic inline size_t cl_map_count(IN const cl_map_t * const p_map) 156219820Sjeff{ 157219820Sjeff CL_ASSERT(p_map); 158219820Sjeff return (cl_qmap_count(&p_map->qmap)); 159219820Sjeff} 160219820Sjeff 161219820Sjeff/* 162219820Sjeff* PARAMETERS 163219820Sjeff* p_map 164219820Sjeff* [in] Pointer to a map whose item count to return. 165219820Sjeff* 166219820Sjeff* RETURN VALUE 167219820Sjeff* Returns the number of items stored in the map. 168219820Sjeff* 169219820Sjeff* SEE ALSO 170219820Sjeff* Map, cl_is_map_empty 171219820Sjeff*********/ 172219820Sjeff 173219820Sjeff/****f* Component Library: Map/cl_is_map_empty 174219820Sjeff* NAME 175219820Sjeff* cl_is_map_empty 176219820Sjeff* 177219820Sjeff* DESCRIPTION 178219820Sjeff* The cl_is_map_empty function returns whether a map is empty. 179219820Sjeff* 180219820Sjeff* SYNOPSIS 181219820Sjeff*/ 182219820Sjeffstatic inline boolean_t cl_is_map_empty(IN const cl_map_t * const p_map) 183219820Sjeff{ 184219820Sjeff CL_ASSERT(p_map); 185219820Sjeff return (cl_is_qmap_empty(&p_map->qmap)); 186219820Sjeff} 187219820Sjeff 188219820Sjeff/* 189219820Sjeff* PARAMETERS 190219820Sjeff* p_map 191219820Sjeff* [in] Pointer to a map to test for emptiness. 192219820Sjeff* 193219820Sjeff* RETURN VALUES 194219820Sjeff* TRUE if the map is empty. 195219820Sjeff* 196219820Sjeff* FALSE otherwise. 197219820Sjeff* 198219820Sjeff* SEE ALSO 199219820Sjeff* Map, cl_map_count, cl_map_remove_all 200219820Sjeff*********/ 201219820Sjeff 202219820Sjeff/****f* Component Library: Map/cl_map_key 203219820Sjeff* NAME 204219820Sjeff* cl_map_key 205219820Sjeff* 206219820Sjeff* DESCRIPTION 207219820Sjeff* The cl_map_key function retrieves the key value of a map item. 208219820Sjeff* 209219820Sjeff* SYNOPSIS 210219820Sjeff*/ 211219820Sjeffstatic inline uint64_t cl_map_key(IN const cl_map_iterator_t itor) 212219820Sjeff{ 213219820Sjeff return (cl_qmap_key(itor)); 214219820Sjeff} 215219820Sjeff 216219820Sjeff/* 217219820Sjeff* PARAMETERS 218219820Sjeff* itor 219219820Sjeff* [in] Iterator for the item whose key to return. 220219820Sjeff* 221219820Sjeff* RETURN VALUE 222219820Sjeff* Returns the 64-bit key value for the specified iterator. 223219820Sjeff* 224219820Sjeff* NOTES 225219820Sjeff* The iterator specified by the itor parameter must have been retrived by 226219820Sjeff* a previous call to cl_map_head, cl_map_tail, cl_map_next, or cl_map_prev. 227219820Sjeff* 228219820Sjeff* The key value is set in a call to cl_map_insert. 229219820Sjeff* 230219820Sjeff* SEE ALSO 231219820Sjeff* Map, cl_map_insert, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev 232219820Sjeff*********/ 233219820Sjeff 234219820Sjeff/****f* Component Library: Map/cl_map_construct 235219820Sjeff* NAME 236219820Sjeff* cl_map_construct 237219820Sjeff* 238219820Sjeff* DESCRIPTION 239219820Sjeff* The cl_map_construct function constructs a map. 240219820Sjeff* 241219820Sjeff* SYNOPSIS 242219820Sjeff*/ 243219820Sjeffvoid cl_map_construct(IN cl_map_t * const p_map); 244219820Sjeff/* 245219820Sjeff* PARAMETERS 246219820Sjeff* p_map 247219820Sjeff* [in] Pointer to a cl_map_t structure to construct. 248219820Sjeff* 249219820Sjeff* RETURN VALUE 250219820Sjeff* This function does not return a value. 251219820Sjeff* 252219820Sjeff* NOTES 253219820Sjeff* Allows calling cl_map_init, cl_map_destroy, and cl_is_map_inited. 254219820Sjeff* 255219820Sjeff* Calling cl_map_construct is a prerequisite to calling any other 256219820Sjeff* map function except cl_map_init. 257219820Sjeff* 258219820Sjeff* SEE ALSO 259219820Sjeff* Map, cl_map_init, cl_map_destroy, cl_is_map_inited 260219820Sjeff*********/ 261219820Sjeff 262219820Sjeff/****f* Component Library: Event/cl_is_map_inited 263219820Sjeff* NAME 264219820Sjeff* cl_is_map_inited 265219820Sjeff* 266219820Sjeff* DESCRIPTION 267219820Sjeff* The cl_is_map_inited function returns whether a map was 268219820Sjeff* successfully initialized. 269219820Sjeff* 270219820Sjeff* SYNOPSIS 271219820Sjeff*/ 272219820Sjeffstatic inline boolean_t cl_is_map_inited(IN const cl_map_t * const p_map) 273219820Sjeff{ 274219820Sjeff /* 275219820Sjeff * The map's pool of map items is the last thing initialized. 276219820Sjeff * We can therefore use it to test for initialization. 277219820Sjeff */ 278219820Sjeff return (cl_is_qpool_inited(&p_map->pool)); 279219820Sjeff} 280219820Sjeff 281219820Sjeff/* 282219820Sjeff* PARAMETERS 283219820Sjeff* p_map 284219820Sjeff* [in] Pointer to a cl_map_t structure whose initialization state 285219820Sjeff* to check. 286219820Sjeff* 287219820Sjeff* RETURN VALUES 288219820Sjeff* TRUE if the map was initialized successfully. 289219820Sjeff* 290219820Sjeff* FALSE otherwise. 291219820Sjeff* 292219820Sjeff* NOTES 293219820Sjeff* Allows checking the state of a map to determine if invoking 294219820Sjeff* member functions is appropriate. 295219820Sjeff* 296219820Sjeff* SEE ALSO 297219820Sjeff* Map 298219820Sjeff*********/ 299219820Sjeff 300219820Sjeff/****f* Component Library: Map/cl_map_init 301219820Sjeff* NAME 302219820Sjeff* cl_map_init 303219820Sjeff* 304219820Sjeff* DESCRIPTION 305219820Sjeff* The cl_map_init function initialized a map for use. 306219820Sjeff* 307219820Sjeff* SYNOPSIS 308219820Sjeff*/ 309219820Sjeffcl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items); 310219820Sjeff/* 311219820Sjeff* PARAMETERS 312219820Sjeff* p_map 313219820Sjeff* [in] Pointer to a cl_map_t structure to initialize. 314219820Sjeff* 315219820Sjeff* min_items 316219820Sjeff* [in] Minimum number of items that can be stored. All necessary 317219820Sjeff* allocations to allow storing the minimum number of items is 318219820Sjeff* performed at initialization time. 319219820Sjeff* 320219820Sjeff* RETURN VALUES 321219820Sjeff* CL_SUCCESS if the map was initialized successfully. 322219820Sjeff* 323219820Sjeff* NOTES 324219820Sjeff* Allows calling map manipulation functions. 325219820Sjeff* 326219820Sjeff* SEE ALSO 327219820Sjeff* Map, cl_map_destroy, cl_map_insert, cl_map_remove 328219820Sjeff*********/ 329219820Sjeff 330219820Sjeff/****f* Component Library: Map/cl_map_destroy 331219820Sjeff* NAME 332219820Sjeff* cl_map_destroy 333219820Sjeff* 334219820Sjeff* DESCRIPTION 335219820Sjeff* The cl_map_destroy function destroys a map. 336219820Sjeff* 337219820Sjeff* SYNOPSIS 338219820Sjeff*/ 339219820Sjeffvoid cl_map_destroy(IN cl_map_t * const p_map); 340219820Sjeff/* 341219820Sjeff* PARAMETERS 342219820Sjeff* p_map 343219820Sjeff* [in] Pointer to a map to destroy. 344219820Sjeff* 345219820Sjeff* RETURN VALUE 346219820Sjeff* This function does not return a value. 347219820Sjeff* 348219820Sjeff* NOTES 349219820Sjeff* Performs any necessary cleanup of the specified map. Further 350219820Sjeff* operations should not be attempted on the map. cl_map_destroy does 351219820Sjeff* not affect any of the objects stored in the map. 352219820Sjeff* This function should only be called after a call to cl_map_construct. 353219820Sjeff* 354219820Sjeff* In debug builds, cl_map_destroy asserts that the map is empty. 355219820Sjeff* 356219820Sjeff* SEE ALSO 357219820Sjeff* Map, cl_map_construct, cl_map_init 358219820Sjeff*********/ 359219820Sjeff 360219820Sjeff/****f* Component Library: Map/cl_map_end 361219820Sjeff* NAME 362219820Sjeff* cl_map_end 363219820Sjeff* 364219820Sjeff* DESCRIPTION 365219820Sjeff* The cl_map_end function returns the iterator for the end of a map. 366219820Sjeff* 367219820Sjeff* SYNOPSIS 368219820Sjeff*/ 369219820Sjeffstatic inline cl_map_iterator_t cl_map_end(IN const cl_map_t * const p_map) 370219820Sjeff{ 371219820Sjeff CL_ASSERT(p_map); 372219820Sjeff return (cl_qmap_end(&p_map->qmap)); 373219820Sjeff} 374219820Sjeff 375219820Sjeff/* 376219820Sjeff* PARAMETERS 377219820Sjeff* p_map 378219820Sjeff* [in] Pointer to a cl_map_t structure whose end to return. 379219820Sjeff* 380219820Sjeff* RETURN VALUE 381219820Sjeff* Iterator for the end of the map. 382219820Sjeff* 383219820Sjeff* NOTES 384219820Sjeff* cl_map_end is useful for determining the validity of map items returned 385219820Sjeff* by cl_map_head, cl_map_tail, cl_map_next, cl_map_prev. If the iterator 386219820Sjeff* by any of these functions compares to the end, the end of the map was 387219820Sjeff* encoutered. 388219820Sjeff* When using cl_map_head or cl_map_tail, this condition indicates that 389219820Sjeff* the map is empty. 390219820Sjeff* 391219820Sjeff* SEE ALSO 392219820Sjeff* Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev 393219820Sjeff*********/ 394219820Sjeff 395219820Sjeff/****f* Component Library: Map/cl_map_head 396219820Sjeff* NAME 397219820Sjeff* cl_map_head 398219820Sjeff* 399219820Sjeff* DESCRIPTION 400219820Sjeff* The cl_map_head function returns the map item with the lowest key 401219820Sjeff* value stored in a map. 402219820Sjeff* 403219820Sjeff* SYNOPSIS 404219820Sjeff*/ 405219820Sjeffstatic inline cl_map_iterator_t cl_map_head(IN const cl_map_t * const p_map) 406219820Sjeff{ 407219820Sjeff CL_ASSERT(p_map); 408219820Sjeff return (cl_qmap_head(&p_map->qmap)); 409219820Sjeff} 410219820Sjeff 411219820Sjeff/* 412219820Sjeff* PARAMETERS 413219820Sjeff* p_map 414219820Sjeff* [in] Pointer to a map whose item with the lowest key is returned. 415219820Sjeff* 416219820Sjeff* RETURN VALUES 417219820Sjeff* Iterator for the object with the lowest key in the map. 418219820Sjeff* 419219820Sjeff* Iterator for the map end if the map was empty. 420219820Sjeff* 421219820Sjeff* NOTES 422219820Sjeff* cl_map_head does not remove the object from the map. 423219820Sjeff* 424219820Sjeff* SEE ALSO 425219820Sjeff* Map, cl_map_tail, cl_map_next, cl_map_prev, cl_map_end 426219820Sjeff*********/ 427219820Sjeff 428219820Sjeff/****f* Component Library: Map/cl_map_tail 429219820Sjeff* NAME 430219820Sjeff* cl_map_tail 431219820Sjeff* 432219820Sjeff* DESCRIPTION 433219820Sjeff* The cl_map_tail function returns the map item with the highest key 434219820Sjeff* value stored in a map. 435219820Sjeff* 436219820Sjeff* SYNOPSIS 437219820Sjeff*/ 438219820Sjeffstatic inline cl_map_iterator_t cl_map_tail(IN const cl_map_t * const p_map) 439219820Sjeff{ 440219820Sjeff CL_ASSERT(p_map); 441219820Sjeff return (cl_qmap_tail(&p_map->qmap)); 442219820Sjeff} 443219820Sjeff 444219820Sjeff/* 445219820Sjeff* PARAMETERS 446219820Sjeff* p_map 447219820Sjeff* [in] Pointer to a map whose item with the highest key 448219820Sjeff* is returned. 449219820Sjeff* 450219820Sjeff* RETURN VALUES 451219820Sjeff* Iterator for the object with the highest key in the map. 452219820Sjeff* 453219820Sjeff* Iterator for the map end if the map was empty. 454219820Sjeff* 455219820Sjeff* NOTES 456219820Sjeff* cl_map_end does no remove the object from the map. 457219820Sjeff* 458219820Sjeff* SEE ALSO 459219820Sjeff* Map, cl_map_head, cl_map_next, cl_map_prev, cl_map_end 460219820Sjeff*********/ 461219820Sjeff 462219820Sjeff/****f* Component Library: Map/cl_map_next 463219820Sjeff* NAME 464219820Sjeff* cl_map_next 465219820Sjeff* 466219820Sjeff* DESCRIPTION 467219820Sjeff* The cl_map_next function returns the map item with the next higher 468219820Sjeff* key value than a specified map item. 469219820Sjeff* 470219820Sjeff* SYNOPSIS 471219820Sjeff*/ 472219820Sjeffstatic inline cl_map_iterator_t cl_map_next(IN const cl_map_iterator_t itor) 473219820Sjeff{ 474219820Sjeff CL_ASSERT(itor); 475219820Sjeff return (cl_qmap_next(itor)); 476219820Sjeff} 477219820Sjeff 478219820Sjeff/* 479219820Sjeff* PARAMETERS 480219820Sjeff* itor 481219820Sjeff* [in] Iterator for an object in a map whose successor to return. 482219820Sjeff* 483219820Sjeff* RETURN VALUES 484219820Sjeff* Iterator for the object with the next higher key value in a map. 485219820Sjeff* 486219820Sjeff* Iterator for the map end if the specified object was the last item in 487219820Sjeff* the map. 488219820Sjeff* 489219820Sjeff* NOTES 490219820Sjeff* The iterator must have been retrieved by a previous call to cl_map_head, 491219820Sjeff* cl_map_tail, cl_map_next, or cl_map_prev. 492219820Sjeff* 493219820Sjeff* SEE ALSO 494219820Sjeff* Map, cl_map_head, cl_map_tail, cl_map_prev, cl_map_end 495219820Sjeff*********/ 496219820Sjeff 497219820Sjeff/****f* Component Library: Map/cl_map_prev 498219820Sjeff* NAME 499219820Sjeff* cl_map_prev 500219820Sjeff* 501219820Sjeff* DESCRIPTION 502219820Sjeff* The cl_map_prev function returns the map item with the next lower 503219820Sjeff* key value than a precified map item. 504219820Sjeff* 505219820Sjeff* SYNOPSIS 506219820Sjeff*/ 507219820Sjeffstatic inline cl_map_iterator_t cl_map_prev(IN const cl_map_iterator_t itor) 508219820Sjeff{ 509219820Sjeff CL_ASSERT(itor); 510219820Sjeff return (cl_qmap_prev(itor)); 511219820Sjeff} 512219820Sjeff 513219820Sjeff/* 514219820Sjeff* PARAMETERS 515219820Sjeff* itor 516219820Sjeff* [in] Iterator for an object in a map whose predecessor to return. 517219820Sjeff* 518219820Sjeff* RETURN VALUES 519219820Sjeff* Iterator for the object with the next lower key value in a map. 520219820Sjeff* 521219820Sjeff* Iterator for the map end if the specified object was the first item in 522219820Sjeff* the map. 523219820Sjeff* 524219820Sjeff* NOTES 525219820Sjeff* The iterator must have been retrieved by a previous call to cl_map_head, 526219820Sjeff* cl_map_tail, cl_map_next, or cl_map_prev. 527219820Sjeff* 528219820Sjeff* SEE ALSO 529219820Sjeff* Map, cl_map_head, cl_map_tail, cl_map_next, cl_map_end 530219820Sjeff*********/ 531219820Sjeff 532219820Sjeff/****f* Component Library: Map/cl_map_insert 533219820Sjeff* NAME 534219820Sjeff* cl_map_insert 535219820Sjeff* 536219820Sjeff* DESCRIPTION 537219820Sjeff* The cl_map_insert function inserts a map item into a map. 538219820Sjeff* 539219820Sjeff* SYNOPSIS 540219820Sjeff*/ 541219820Sjeffvoid *cl_map_insert(IN cl_map_t * const p_map, 542219820Sjeff IN const uint64_t key, IN const void *const p_object); 543219820Sjeff/* 544219820Sjeff* PARAMETERS 545219820Sjeff* p_map 546219820Sjeff* [in] Pointer to a map into which to add the item. 547219820Sjeff* 548219820Sjeff* key 549219820Sjeff* [in] Value to associate with the object. 550219820Sjeff* 551219820Sjeff* p_object 552219820Sjeff* [in] Pointer to an object to insert into the map. 553219820Sjeff* 554219820Sjeff* RETURN VALUES 555219820Sjeff* Pointer to the object in the map with the specified key after the call 556219820Sjeff* completes. 557219820Sjeff* 558219820Sjeff* NULL if there was not enough memory to insert the desired item. 559219820Sjeff* 560219820Sjeff* NOTES 561219820Sjeff* Insertion operations may cause the map to rebalance. 562219820Sjeff* 563219820Sjeff* If the map already contains an object already with the specified key, 564219820Sjeff* that object will not be replaced and the pointer to that object is 565219820Sjeff* returned. 566219820Sjeff* 567219820Sjeff* SEE ALSO 568219820Sjeff* Map, cl_map_remove, cl_map_item_t 569219820Sjeff*********/ 570219820Sjeff 571219820Sjeff/****f* Component Library: Map/cl_map_get 572219820Sjeff* NAME 573219820Sjeff* cl_map_get 574219820Sjeff* 575219820Sjeff* DESCRIPTION 576219820Sjeff* The cl_map_get function returns the object associated with a key. 577219820Sjeff* 578219820Sjeff* SYNOPSIS 579219820Sjeff*/ 580219820Sjeffvoid *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key); 581219820Sjeff/* 582219820Sjeff* PARAMETERS 583219820Sjeff* p_map 584219820Sjeff* [in] Pointer to a map from which to retrieve the object with 585219820Sjeff* the specified key. 586219820Sjeff* 587219820Sjeff* key 588219820Sjeff* [in] Key value used to search for the desired object. 589219820Sjeff* 590219820Sjeff* RETURN VALUES 591219820Sjeff* Pointer to the object with the desired key value. 592219820Sjeff* 593219820Sjeff* NULL if there was no item with the desired key value stored in 594219820Sjeff* the map. 595219820Sjeff* 596219820Sjeff* NOTES 597219820Sjeff* cl_map_get does not remove the item from the map. 598219820Sjeff* 599219820Sjeff* SEE ALSO 600219820Sjeff* Map, cl_map_remove, cl_map_get_next 601219820Sjeff*********/ 602219820Sjeff 603219820Sjeff/****f* Component Library: Map/cl_map_get_next 604219820Sjeff* NAME 605219820Sjeff* cl_map_get_next 606219820Sjeff* 607219820Sjeff* DESCRIPTION 608219820Sjeff* The cl_qmap_get_next function returns the first object associated with a 609219820Sjeff* key > the key specified. 610219820Sjeff* 611219820Sjeff* SYNOPSIS 612219820Sjeff*/ 613219820Sjeffvoid *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key); 614219820Sjeff/* 615219820Sjeff* PARAMETERS 616219820Sjeff* p_map 617219820Sjeff* [in] Pointer to a map from which to retrieve the object with 618219820Sjeff* the specified key. 619219820Sjeff* 620219820Sjeff* key 621219820Sjeff* [in] Key value used to search for the desired object. 622219820Sjeff* 623219820Sjeff* RETURN VALUES 624219820Sjeff* Pointer to the first object with a key > the desired key value. 625219820Sjeff* 626219820Sjeff* NULL if there was no item with a key > the desired key 627219820Sjeff* value stored in the map. 628219820Sjeff* 629219820Sjeff* NOTES 630219820Sjeff* cl_map_get does not remove the item from the map. 631219820Sjeff* 632219820Sjeff* SEE ALSO 633219820Sjeff* Map, cl_map_remove, cl_map_get 634219820Sjeff*********/ 635219820Sjeff 636219820Sjeff/****f* Component Library: Map/cl_map_remove_item 637219820Sjeff* NAME 638219820Sjeff* cl_map_remove_item 639219820Sjeff* 640219820Sjeff* DESCRIPTION 641219820Sjeff* The cl_map_remove_item function removes the specified map item 642219820Sjeff* from a map. 643219820Sjeff* 644219820Sjeff* SYNOPSIS 645219820Sjeff*/ 646219820Sjeffvoid 647219820Sjeffcl_map_remove_item(IN cl_map_t * const p_map, IN const cl_map_iterator_t itor); 648219820Sjeff/* 649219820Sjeff* PARAMETERS 650219820Sjeff* p_map 651219820Sjeff* [in] Pointer to a map from which to remove the object associated 652219820Sjeff* with the specified iterator. 653219820Sjeff* 654219820Sjeff* itor 655219820Sjeff* [in] Iterator for an object to remove from its map. 656219820Sjeff* 657219820Sjeff* RETURN VALUE 658219820Sjeff* This function does not return a value. 659219820Sjeff* 660219820Sjeff* NOTES 661219820Sjeff* Removes the object associated with the specifid iterator from its map. 662219820Sjeff* 663219820Sjeff* The specified iterator is no longer valid after the call completes. 664219820Sjeff* 665219820Sjeff* The iterator must have been retrieved by a previous call to cl_map_head, 666219820Sjeff* cl_map_tail, cl_map_next, or cl_map_prev. 667219820Sjeff* 668219820Sjeff* SEE ALSO 669219820Sjeff* Map, cl_map_remove, cl_map_remove_all, cl_map_insert, cl_map_head, 670219820Sjeff* cl_map_tail, cl_map_next, cl_map_prev 671219820Sjeff*********/ 672219820Sjeff 673219820Sjeff/****f* Component Library: Map/cl_map_remove 674219820Sjeff* NAME 675219820Sjeff* cl_map_remove 676219820Sjeff* 677219820Sjeff* DESCRIPTION 678219820Sjeff* The cl_map_remove function removes the map item with the specified key 679219820Sjeff* from a map. 680219820Sjeff* 681219820Sjeff* SYNOPSIS 682219820Sjeff*/ 683219820Sjeffvoid *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key); 684219820Sjeff/* 685219820Sjeff* PARAMETERS 686219820Sjeff* p_map 687219820Sjeff* [in] Pointer to a cl_map_t structure from which to remove the 688219820Sjeff* item with the specified key. 689219820Sjeff* 690219820Sjeff* key 691219820Sjeff* [in] Key value used to search for the object to remove. 692219820Sjeff* 693219820Sjeff* RETURN VALUES 694219820Sjeff* Pointer to the object associated with the specified key if 695219820Sjeff* it was found and removed. 696219820Sjeff* 697219820Sjeff* NULL if no object with the specified key exists in the map. 698219820Sjeff* 699219820Sjeff* SEE ALSO 700219820Sjeff* Map, cl_map_remove_item, cl_map_remove_all, cl_map_insert 701219820Sjeff*********/ 702219820Sjeff 703219820Sjeff/****f* Component Library: Map/cl_map_remove_all 704219820Sjeff* NAME 705219820Sjeff* cl_map_remove_all 706219820Sjeff* 707219820Sjeff* DESCRIPTION 708219820Sjeff* The cl_map_remove_all function removes all objects from a map, 709219820Sjeff* leaving it empty. 710219820Sjeff* 711219820Sjeff* SYNOPSIS 712219820Sjeff*/ 713219820Sjeffvoid cl_map_remove_all(IN cl_map_t * const p_map); 714219820Sjeff/* 715219820Sjeff* PARAMETERS 716219820Sjeff* p_map 717219820Sjeff* [in] Pointer to a map to empty. 718219820Sjeff* 719219820Sjeff* RETURN VALUE 720219820Sjeff* This function does not return a value. 721219820Sjeff* 722219820Sjeff* SEE ALSO 723219820Sjeff* Map, cl_map_remove, cl_map_remove_item 724219820Sjeff*********/ 725219820Sjeff 726219820Sjeff/****f* Component Library: Map/cl_map_obj 727219820Sjeff* NAME 728219820Sjeff* cl_map_obj 729219820Sjeff* 730219820Sjeff* DESCRIPTION 731219820Sjeff* The cl_map_obj function returns the object associated with an iterator. 732219820Sjeff* 733219820Sjeff* SYNOPSIS 734219820Sjeff*/ 735219820Sjeffstatic inline void *cl_map_obj(IN const cl_map_iterator_t itor) 736219820Sjeff{ 737219820Sjeff return (cl_qmap_obj(PARENT_STRUCT(itor, cl_map_obj_t, item))); 738219820Sjeff} 739219820Sjeff 740219820Sjeff/* 741219820Sjeff* PARAMETERS 742219820Sjeff* itor 743219820Sjeff* [in] Iterator whose object to return. 744219820Sjeff* 745219820Sjeff* RETURN VALUES 746219820Sjeff* Returns the value of the object pointer associated with the iterator. 747219820Sjeff* 748219820Sjeff* The iterator must have been retrieved by a previous call to cl_map_head, 749219820Sjeff* cl_map_tail, cl_map_next, or cl_map_prev. 750219820Sjeff* 751219820Sjeff* SEE ALSO 752219820Sjeff* Map, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev 753219820Sjeff*********/ 754219820Sjeff 755219820Sjeff/****f* Component Library: Map/cl_map_merge 756219820Sjeff* NAME 757219820Sjeff* cl_map_merge 758219820Sjeff* 759219820Sjeff* DESCRIPTION 760219820Sjeff* The cl_map_merge function moves all items from one map to another, 761219820Sjeff* excluding duplicates. 762219820Sjeff* 763219820Sjeff* SYNOPSIS 764219820Sjeff*/ 765219820Sjeffcl_status_t 766219820Sjeffcl_map_merge(OUT cl_map_t * const p_dest_map, 767219820Sjeff IN OUT cl_map_t * const p_src_map); 768219820Sjeff/* 769219820Sjeff* PARAMETERS 770219820Sjeff* p_dest_map 771219820Sjeff* [out] Pointer to a cl_map_t structure to which items should be added. 772219820Sjeff* 773219820Sjeff* p_src_map 774219820Sjeff* [in/out] Pointer to a cl_map_t structure whose items to add 775219820Sjeff* to p_dest_map. 776219820Sjeff* 777219820Sjeff* RETURN VALUES 778219820Sjeff* CL_SUCCESS if the operation succeeded. 779219820Sjeff* 780219820Sjeff* CL_INSUFFICIENT_MEMORY if there was not enough memory for the operation 781219820Sjeff* to succeed. 782219820Sjeff* 783219820Sjeff* NOTES 784219820Sjeff* Items are evaluated based on their keys only. 785219820Sjeff* 786219820Sjeff* Upon return from cl_map_merge, the map referenced by p_src_map contains 787219820Sjeff* all duplicate items. 788219820Sjeff* 789219820Sjeff* SEE ALSO 790219820Sjeff* Map, cl_map_delta 791219820Sjeff*********/ 792219820Sjeff 793219820Sjeff/****f* Component Library: Map/cl_map_delta 794219820Sjeff* NAME 795219820Sjeff* cl_map_delta 796219820Sjeff* 797219820Sjeff* DESCRIPTION 798219820Sjeff* The cl_map_delta function computes the differences between two maps. 799219820Sjeff* 800219820Sjeff* SYNOPSIS 801219820Sjeff*/ 802219820Sjeffcl_status_t 803219820Sjeffcl_map_delta(IN OUT cl_map_t * const p_map1, 804219820Sjeff IN OUT cl_map_t * const p_map2, 805219820Sjeff OUT cl_map_t * const p_new, OUT cl_map_t * const p_old); 806219820Sjeff/* 807219820Sjeff* PARAMETERS 808219820Sjeff* p_map1 809219820Sjeff* [in/out] Pointer to the first of two cl_map_t structures whose 810219820Sjeff* differences to compute. 811219820Sjeff* 812219820Sjeff* p_map2 813219820Sjeff* [in/out] Pointer to the second of two cl_map_t structures whose 814219820Sjeff* differences to compute. 815219820Sjeff* 816219820Sjeff* p_new 817219820Sjeff* [out] Pointer to an empty cl_map_t structure that contains the 818219820Sjeff* items unique to p_map2 upon return from the function. 819219820Sjeff* 820219820Sjeff* p_old 821219820Sjeff* [out] Pointer to an empty cl_map_t structure that contains the 822219820Sjeff* items unique to p_map1 upon return from the function. 823219820Sjeff* 824219820Sjeff* RETURN VALUES 825219820Sjeff* CL_SUCCESS if the operation succeeded. 826219820Sjeff* 827219820Sjeff* CL_INSUFFICIENT_MEMORY if there was not enough memory for the operation 828219820Sjeff* to succeed. 829219820Sjeff* 830219820Sjeff* NOTES 831219820Sjeff* Items are evaluated based on their keys. Items that exist in both 832219820Sjeff* p_map1 and p_map2 remain in their respective maps. Items that 833219820Sjeff* exist only p_map1 are moved to p_old. Likewise, items that exist only 834219820Sjeff* in p_map2 are moved to p_new. This function can be useful in evaluating 835219820Sjeff* changes between two maps. 836219820Sjeff* 837219820Sjeff* Both maps pointed to by p_new and p_old must be empty on input. 838219820Sjeff* 839219820Sjeff* Upon failure, all input maps are restored to their original state. 840219820Sjeff* 841219820Sjeff* SEE ALSO 842219820Sjeff* Map, cl_map_merge 843219820Sjeff*********/ 844219820Sjeff 845219820SjeffEND_C_DECLS 846219820Sjeff#endif /* _CL_MAP_H_ */ 847