1321936Shselasky/* 2321936Shselasky * Copyright (c) 2004, 2005 Voltaire, Inc. All rights reserved. 3321936Shselasky * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved. 4321936Shselasky * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5321936Shselasky * 6321936Shselasky * This software is available to you under a choice of one of two 7321936Shselasky * licenses. You may choose to be licensed under the terms of the GNU 8321936Shselasky * General Public License (GPL) Version 2, available from the file 9321936Shselasky * COPYING in the main directory of this source tree, or the 10321936Shselasky * OpenIB.org BSD license below: 11321936Shselasky * 12321936Shselasky * Redistribution and use in source and binary forms, with or 13321936Shselasky * without modification, are permitted provided that the following 14321936Shselasky * conditions are met: 15321936Shselasky * 16321936Shselasky * - Redistributions of source code must retain the above 17321936Shselasky * copyright notice, this list of conditions and the following 18321936Shselasky * disclaimer. 19321936Shselasky * 20321936Shselasky * - Redistributions in binary form must reproduce the above 21321936Shselasky * copyright notice, this list of conditions and the following 22321936Shselasky * disclaimer in the documentation and/or other materials 23321936Shselasky * provided with the distribution. 24321936Shselasky * 25321936Shselasky * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26321936Shselasky * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27321936Shselasky * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28321936Shselasky * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29321936Shselasky * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30321936Shselasky * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31321936Shselasky * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32321936Shselasky * SOFTWARE. 33321936Shselasky * 34321936Shselasky */ 35321936Shselasky 36321936Shselasky/* 37321936Shselasky * Abstract: 38321936Shselasky * Declaration of quick map, a binary tree where the caller always provides 39321936Shselasky * all necessary storage. 40321936Shselasky */ 41321936Shselasky 42321936Shselasky#ifndef _CL_QMAP_H_ 43321936Shselasky#define _CL_QMAP_H_ 44321936Shselasky 45321936Shselasky#include <complib/cl_qpool.h> 46321936Shselasky 47321936Shselasky#ifdef __cplusplus 48321936Shselasky# define BEGIN_C_DECLS extern "C" { 49321936Shselasky# define END_C_DECLS } 50321936Shselasky#else /* !__cplusplus */ 51321936Shselasky# define BEGIN_C_DECLS 52321936Shselasky# define END_C_DECLS 53321936Shselasky#endif /* __cplusplus */ 54321936Shselasky 55321936ShselaskyBEGIN_C_DECLS 56321936Shselasky/****h* Component Library/Quick Map 57321936Shselasky* NAME 58321936Shselasky* Quick Map 59321936Shselasky* 60321936Shselasky* DESCRIPTION 61321936Shselasky* Quick map implements a binary tree that stores user provided cl_map_item_t 62321936Shselasky* structures. Each item stored in a quick map has a unique 64-bit key 63321936Shselasky* (duplicates are not allowed). Quick map provides the ability to 64321936Shselasky* efficiently search for an item given a key. 65321936Shselasky* 66321936Shselasky* Quick map does not allocate any memory, and can therefore not fail 67321936Shselasky* any operations due to insufficient memory. Quick map can thus be useful 68321936Shselasky* in minimizing the error paths in code. 69321936Shselasky* 70321936Shselasky* Quick map is not thread safe, and users must provide serialization when 71321936Shselasky* adding and removing items from the map. 72321936Shselasky* 73321936Shselasky* The quick map functions operate on a cl_qmap_t structure which should be 74321936Shselasky* treated as opaque and should be manipulated only through the provided 75321936Shselasky* functions. 76321936Shselasky* 77321936Shselasky* SEE ALSO 78321936Shselasky* Structures: 79321936Shselasky* cl_qmap_t, cl_map_item_t, cl_map_obj_t 80321936Shselasky* 81321936Shselasky* Callbacks: 82321936Shselasky* cl_pfn_qmap_apply_t 83321936Shselasky* 84321936Shselasky* Item Manipulation: 85321936Shselasky* cl_qmap_set_obj, cl_qmap_obj, cl_qmap_key 86321936Shselasky* 87321936Shselasky* Initialization: 88321936Shselasky* cl_qmap_init 89321936Shselasky* 90321936Shselasky* Iteration: 91321936Shselasky* cl_qmap_end, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev 92321936Shselasky* 93321936Shselasky* Manipulation: 94321936Shselasky* cl_qmap_insert, cl_qmap_get, cl_qmap_remove_item, cl_qmap_remove, 95321936Shselasky* cl_qmap_remove_all, cl_qmap_merge, cl_qmap_delta, cl_qmap_get_next 96321936Shselasky* 97321936Shselasky* Search: 98321936Shselasky* cl_qmap_apply_func 99321936Shselasky* 100321936Shselasky* Attributes: 101321936Shselasky* cl_qmap_count, cl_is_qmap_empty, 102321936Shselasky*********/ 103321936Shselasky/****i* Component Library: Quick Map/cl_map_color_t 104321936Shselasky* NAME 105321936Shselasky* cl_map_color_t 106321936Shselasky* 107321936Shselasky* DESCRIPTION 108321936Shselasky* The cl_map_color_t enumerated type is used to note the color of 109321936Shselasky* nodes in a map. 110321936Shselasky* 111321936Shselasky* SYNOPSIS 112321936Shselasky*/ 113321936Shselaskytypedef enum _cl_map_color { 114321936Shselasky CL_MAP_RED, 115321936Shselasky CL_MAP_BLACK 116321936Shselasky} cl_map_color_t; 117321936Shselasky/* 118321936Shselasky* VALUES 119321936Shselasky* CL_MAP_RED 120321936Shselasky* The node in the map is red. 121321936Shselasky* 122321936Shselasky* CL_MAP_BLACK 123321936Shselasky* The node in the map is black. 124321936Shselasky* 125321936Shselasky* SEE ALSO 126321936Shselasky* Quick Map, cl_map_item_t 127321936Shselasky*********/ 128321936Shselasky 129321936Shselasky/****s* Component Library: Quick Map/cl_map_item_t 130321936Shselasky* NAME 131321936Shselasky* cl_map_item_t 132321936Shselasky* 133321936Shselasky* DESCRIPTION 134321936Shselasky* The cl_map_item_t structure is used by maps to store objects. 135321936Shselasky* 136321936Shselasky* The cl_map_item_t structure should be treated as opaque and should 137321936Shselasky* be manipulated only through the provided functions. 138321936Shselasky* 139321936Shselasky* SYNOPSIS 140321936Shselasky*/ 141321936Shselaskytypedef struct _cl_map_item { 142321936Shselasky /* Must be first to allow casting. */ 143321936Shselasky cl_pool_item_t pool_item; 144321936Shselasky struct _cl_map_item *p_left; 145321936Shselasky struct _cl_map_item *p_right; 146321936Shselasky struct _cl_map_item *p_up; 147321936Shselasky cl_map_color_t color; 148321936Shselasky uint64_t key; 149321936Shselasky#ifdef _DEBUG_ 150321936Shselasky struct _cl_qmap *p_map; 151321936Shselasky#endif 152321936Shselasky} cl_map_item_t; 153321936Shselasky/* 154321936Shselasky* FIELDS 155321936Shselasky* pool_item 156321936Shselasky* Used to store the item in a doubly linked list, allowing more 157321936Shselasky* efficient map traversal. 158321936Shselasky* 159321936Shselasky* p_left 160321936Shselasky* Pointer to the map item that is a child to the left of the node. 161321936Shselasky* 162321936Shselasky* p_right 163321936Shselasky* Pointer to the map item that is a child to the right of the node. 164321936Shselasky* 165321936Shselasky* p_up 166321936Shselasky* Pointer to the map item that is the parent of the node. 167321936Shselasky* 168321936Shselasky* p_nil 169321936Shselasky* Pointer to the map's NIL item, used as a terminator for leaves. 170321936Shselasky* The NIL sentinel is in the cl_qmap_t structure. 171321936Shselasky* 172321936Shselasky* color 173321936Shselasky* Indicates whether a node is red or black in the map. 174321936Shselasky* 175321936Shselasky* key 176321936Shselasky* Value that uniquely represents a node in a map. This value is 177321936Shselasky* set by calling cl_qmap_insert and can be retrieved by calling 178321936Shselasky* cl_qmap_key. 179321936Shselasky* 180321936Shselasky* NOTES 181321936Shselasky* None of the fields of this structure should be manipulated by users, as 182321936Shselasky* they are crititcal to the proper operation of the map in which they 183321936Shselasky* are stored. 184321936Shselasky* 185321936Shselasky* To allow storing items in either a quick list, a quick pool, or a quick 186321936Shselasky* map, the map implementation guarantees that the map item can be safely 187321936Shselasky* cast to a pool item used for storing an object in a quick pool, or cast 188321936Shselasky* to a list item used for storing an object in a quick list. This removes 189321936Shselasky* the need to embed a map item, a list item, and a pool item in objects 190321936Shselasky* that need to be stored in a quick list, a quick pool, and a quick map. 191321936Shselasky* 192321936Shselasky* SEE ALSO 193321936Shselasky* Quick Map, cl_qmap_insert, cl_qmap_key, cl_pool_item_t, cl_list_item_t 194321936Shselasky*********/ 195321936Shselasky 196321936Shselasky/****s* Component Library: Quick Map/cl_map_obj_t 197321936Shselasky* NAME 198321936Shselasky* cl_map_obj_t 199321936Shselasky* 200321936Shselasky* DESCRIPTION 201321936Shselasky* The cl_map_obj_t structure is used to store objects in maps. 202321936Shselasky* 203321936Shselasky* The cl_map_obj_t structure should be treated as opaque and should 204321936Shselasky* be manipulated only through the provided functions. 205321936Shselasky* 206321936Shselasky* SYNOPSIS 207321936Shselasky*/ 208321936Shselaskytypedef struct _cl_map_obj { 209321936Shselasky cl_map_item_t item; 210321936Shselasky const void *p_object; 211321936Shselasky} cl_map_obj_t; 212321936Shselasky/* 213321936Shselasky* FIELDS 214321936Shselasky* item 215321936Shselasky* Map item used by internally by the map to store an object. 216321936Shselasky* 217321936Shselasky* p_object 218321936Shselasky* User defined context. Users should not access this field directly. 219321936Shselasky* Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the value 220321936Shselasky* of this field. 221321936Shselasky* 222321936Shselasky* NOTES 223321936Shselasky* None of the fields of this structure should be manipulated by users, as 224321936Shselasky* they are crititcal to the proper operation of the map in which they 225321936Shselasky* are stored. 226321936Shselasky* 227321936Shselasky* Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the object 228321936Shselasky* stored in a map item, respectively. 229321936Shselasky* 230321936Shselasky* SEE ALSO 231321936Shselasky* Quick Map, cl_qmap_set_obj, cl_qmap_obj, cl_map_item_t 232321936Shselasky*********/ 233321936Shselasky 234321936Shselasky/****s* Component Library: Quick Map/cl_qmap_t 235321936Shselasky* NAME 236321936Shselasky* cl_qmap_t 237321936Shselasky* 238321936Shselasky* DESCRIPTION 239321936Shselasky* Quick map structure. 240321936Shselasky* 241321936Shselasky* The cl_qmap_t structure should be treated as opaque and should 242321936Shselasky* be manipulated only through the provided functions. 243321936Shselasky* 244321936Shselasky* SYNOPSIS 245321936Shselasky*/ 246321936Shselaskytypedef struct _cl_qmap { 247321936Shselasky cl_map_item_t root; 248321936Shselasky cl_map_item_t nil; 249321936Shselasky cl_state_t state; 250321936Shselasky size_t count; 251321936Shselasky} cl_qmap_t; 252321936Shselasky/* 253321936Shselasky* PARAMETERS 254321936Shselasky* root 255321936Shselasky* Map item that serves as root of the map. The root is set up to 256321936Shselasky* always have itself as parent. The left pointer is set to point 257321936Shselasky* to the item at the root. 258321936Shselasky* 259321936Shselasky* nil 260321936Shselasky* Map item that serves as terminator for all leaves, as well as 261321936Shselasky* providing the list item used as quick list for storing map items 262321936Shselasky* in a list for faster traversal. 263321936Shselasky* 264321936Shselasky* state 265321936Shselasky* State of the map, used to verify that operations are permitted. 266321936Shselasky* 267321936Shselasky* count 268321936Shselasky* Number of items in the map. 269321936Shselasky* 270321936Shselasky* SEE ALSO 271321936Shselasky* Quick Map 272321936Shselasky*********/ 273321936Shselasky 274321936Shselasky/****d* Component Library: Quick Map/cl_pfn_qmap_apply_t 275321936Shselasky* NAME 276321936Shselasky* cl_pfn_qmap_apply_t 277321936Shselasky* 278321936Shselasky* DESCRIPTION 279321936Shselasky* The cl_pfn_qmap_apply_t function type defines the prototype for 280321936Shselasky* functions used to iterate items in a quick map. 281321936Shselasky* 282321936Shselasky* SYNOPSIS 283321936Shselasky*/ 284321936Shselaskytypedef void 285321936Shselasky (*cl_pfn_qmap_apply_t) (IN cl_map_item_t * const p_map_item, IN void *context); 286321936Shselasky/* 287321936Shselasky* PARAMETERS 288321936Shselasky* p_map_item 289321936Shselasky* [in] Pointer to a cl_map_item_t structure. 290321936Shselasky* 291321936Shselasky* context 292321936Shselasky* [in] Value passed to the callback function. 293321936Shselasky* 294321936Shselasky* RETURN VALUE 295321936Shselasky* This function does not return a value. 296321936Shselasky* 297321936Shselasky* NOTES 298321936Shselasky* This function type is provided as function prototype reference for the 299321936Shselasky* function provided by users as a parameter to the cl_qmap_apply_func 300321936Shselasky* function. 301321936Shselasky* 302321936Shselasky* SEE ALSO 303321936Shselasky* Quick Map, cl_qmap_apply_func 304321936Shselasky*********/ 305321936Shselasky 306321936Shselasky/****f* Component Library: Quick Map/cl_qmap_count 307321936Shselasky* NAME 308321936Shselasky* cl_qmap_count 309321936Shselasky* 310321936Shselasky* DESCRIPTION 311321936Shselasky* The cl_qmap_count function returns the number of items stored 312321936Shselasky* in a quick map. 313321936Shselasky* 314321936Shselasky* SYNOPSIS 315321936Shselasky*/ 316321936Shselaskystatic inline uint32_t cl_qmap_count(IN const cl_qmap_t * const p_map) 317321936Shselasky{ 318321936Shselasky CL_ASSERT(p_map); 319321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 320321936Shselasky return ((uint32_t) p_map->count); 321321936Shselasky} 322321936Shselasky 323321936Shselasky/* 324321936Shselasky* PARAMETERS 325321936Shselasky* p_map 326321936Shselasky* [in] Pointer to a cl_qmap_t structure whose item count to return. 327321936Shselasky* 328321936Shselasky* RETURN VALUE 329321936Shselasky* Returns the number of items stored in the map. 330321936Shselasky* 331321936Shselasky* SEE ALSO 332321936Shselasky* Quick Map, cl_is_qmap_empty 333321936Shselasky*********/ 334321936Shselasky 335321936Shselasky/****f* Component Library: Quick Map/cl_is_qmap_empty 336321936Shselasky* NAME 337321936Shselasky* cl_is_qmap_empty 338321936Shselasky* 339321936Shselasky* DESCRIPTION 340321936Shselasky* The cl_is_qmap_empty function returns whether a quick map is empty. 341321936Shselasky* 342321936Shselasky* SYNOPSIS 343321936Shselasky*/ 344321936Shselaskystatic inline boolean_t cl_is_qmap_empty(IN const cl_qmap_t * const p_map) 345321936Shselasky{ 346321936Shselasky CL_ASSERT(p_map); 347321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 348321936Shselasky 349321936Shselasky return (p_map->count == 0); 350321936Shselasky} 351321936Shselasky 352321936Shselasky/* 353321936Shselasky* PARAMETERS 354321936Shselasky* p_map 355321936Shselasky* [in] Pointer to a cl_qmap_t structure to test for emptiness. 356321936Shselasky* 357321936Shselasky* RETURN VALUES 358321936Shselasky* TRUE if the quick map is empty. 359321936Shselasky* 360321936Shselasky* FALSE otherwise. 361321936Shselasky* 362321936Shselasky* SEE ALSO 363321936Shselasky* Quick Map, cl_qmap_count, cl_qmap_remove_all 364321936Shselasky*********/ 365321936Shselasky 366321936Shselasky/****f* Component Library: Quick Map/cl_qmap_set_obj 367321936Shselasky* NAME 368321936Shselasky* cl_qmap_set_obj 369321936Shselasky* 370321936Shselasky* DESCRIPTION 371321936Shselasky* The cl_qmap_set_obj function sets the object stored in a map object. 372321936Shselasky* 373321936Shselasky* SYNOPSIS 374321936Shselasky*/ 375321936Shselaskystatic inline void 376321936Shselaskycl_qmap_set_obj(IN cl_map_obj_t * const p_map_obj, 377321936Shselasky IN const void *const p_object) 378321936Shselasky{ 379321936Shselasky CL_ASSERT(p_map_obj); 380321936Shselasky p_map_obj->p_object = p_object; 381321936Shselasky} 382321936Shselasky 383321936Shselasky/* 384321936Shselasky* PARAMETERS 385321936Shselasky* p_map_obj 386321936Shselasky* [in] Pointer to a map object stucture whose object pointer 387321936Shselasky* is to be set. 388321936Shselasky* 389321936Shselasky* p_object 390321936Shselasky* [in] User defined context. 391321936Shselasky* 392321936Shselasky* RETURN VALUE 393321936Shselasky* This function does not return a value. 394321936Shselasky* 395321936Shselasky* SEE ALSO 396321936Shselasky* Quick Map, cl_qmap_obj 397321936Shselasky*********/ 398321936Shselasky 399321936Shselasky/****f* Component Library: Quick Map/cl_qmap_obj 400321936Shselasky* NAME 401321936Shselasky* cl_qmap_obj 402321936Shselasky* 403321936Shselasky* DESCRIPTION 404321936Shselasky* The cl_qmap_obj function returns the object stored in a map object. 405321936Shselasky* 406321936Shselasky* SYNOPSIS 407321936Shselasky*/ 408321936Shselaskystatic inline void *cl_qmap_obj(IN const cl_map_obj_t * const p_map_obj) 409321936Shselasky{ 410321936Shselasky CL_ASSERT(p_map_obj); 411321936Shselasky return ((void *)p_map_obj->p_object); 412321936Shselasky} 413321936Shselasky 414321936Shselasky/* 415321936Shselasky* PARAMETERS 416321936Shselasky* p_map_obj 417321936Shselasky* [in] Pointer to a map object stucture whose object pointer to return. 418321936Shselasky* 419321936Shselasky* RETURN VALUE 420321936Shselasky* Returns the value of the object pointer stored in the map object. 421321936Shselasky* 422321936Shselasky* SEE ALSO 423321936Shselasky* Quick Map, cl_qmap_set_obj 424321936Shselasky*********/ 425321936Shselasky 426321936Shselasky/****f* Component Library: Quick Map/cl_qmap_key 427321936Shselasky* NAME 428321936Shselasky* cl_qmap_key 429321936Shselasky* 430321936Shselasky* DESCRIPTION 431321936Shselasky* The cl_qmap_key function retrieves the key value of a map item. 432321936Shselasky* 433321936Shselasky* SYNOPSIS 434321936Shselasky*/ 435321936Shselaskystatic inline uint64_t cl_qmap_key(IN const cl_map_item_t * const p_item) 436321936Shselasky{ 437321936Shselasky CL_ASSERT(p_item); 438321936Shselasky return (p_item->key); 439321936Shselasky} 440321936Shselasky 441321936Shselasky/* 442321936Shselasky* PARAMETERS 443321936Shselasky* p_item 444321936Shselasky* [in] Pointer to a map item whose key value to return. 445321936Shselasky* 446321936Shselasky* RETURN VALUE 447321936Shselasky* Returns the 64-bit key value for the specified map item. 448321936Shselasky* 449321936Shselasky* NOTES 450321936Shselasky* The key value is set in a call to cl_qmap_insert. 451321936Shselasky* 452321936Shselasky* SEE ALSO 453321936Shselasky* Quick Map, cl_qmap_insert 454321936Shselasky*********/ 455321936Shselasky 456321936Shselasky/****f* Component Library: Quick Map/cl_qmap_init 457321936Shselasky* NAME 458321936Shselasky* cl_qmap_init 459321936Shselasky* 460321936Shselasky* DESCRIPTION 461321936Shselasky* The cl_qmap_init function initialized a quick map for use. 462321936Shselasky* 463321936Shselasky* SYNOPSIS 464321936Shselasky*/ 465321936Shselaskyvoid cl_qmap_init(IN cl_qmap_t * const p_map); 466321936Shselasky/* 467321936Shselasky* PARAMETERS 468321936Shselasky* p_map 469321936Shselasky* [in] Pointer to a cl_qmap_t structure to initialize. 470321936Shselasky* 471321936Shselasky* RETURN VALUES 472321936Shselasky* This function does not return a value. 473321936Shselasky* 474321936Shselasky* NOTES 475321936Shselasky* Allows calling quick map manipulation functions. 476321936Shselasky* 477321936Shselasky* SEE ALSO 478321936Shselasky* Quick Map, cl_qmap_insert, cl_qmap_remove 479321936Shselasky*********/ 480321936Shselasky 481321936Shselasky/****f* Component Library: Quick Map/cl_qmap_end 482321936Shselasky* NAME 483321936Shselasky* cl_qmap_end 484321936Shselasky* 485321936Shselasky* DESCRIPTION 486321936Shselasky* The cl_qmap_end function returns the end of a quick map. 487321936Shselasky* 488321936Shselasky* SYNOPSIS 489321936Shselasky*/ 490321936Shselaskystatic inline const cl_map_item_t *cl_qmap_end(IN const cl_qmap_t * const p_map) 491321936Shselasky{ 492321936Shselasky CL_ASSERT(p_map); 493321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 494321936Shselasky /* Nil is the end of the map. */ 495321936Shselasky return (&p_map->nil); 496321936Shselasky} 497321936Shselasky 498321936Shselasky/* 499321936Shselasky* PARAMETERS 500321936Shselasky* p_map 501321936Shselasky* [in] Pointer to a cl_qmap_t structure whose end to return. 502321936Shselasky* 503321936Shselasky* RETURN VALUE 504321936Shselasky* Pointer to the end of the map. 505321936Shselasky* 506321936Shselasky* NOTES 507321936Shselasky* cl_qmap_end is useful for determining the validity of map items returned 508321936Shselasky* by cl_qmap_head, cl_qmap_tail, cl_qmap_next, or cl_qmap_prev. If the 509321936Shselasky* map item pointer returned by any of these functions compares to the end, 510321936Shselasky* the end of the map was encoutered. 511321936Shselasky* When using cl_qmap_head or cl_qmap_tail, this condition indicates that 512321936Shselasky* the map is empty. 513321936Shselasky* 514321936Shselasky* SEE ALSO 515321936Shselasky* Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev 516321936Shselasky*********/ 517321936Shselasky 518321936Shselasky/****f* Component Library: Quick Map/cl_qmap_head 519321936Shselasky* NAME 520321936Shselasky* cl_qmap_head 521321936Shselasky* 522321936Shselasky* DESCRIPTION 523321936Shselasky* The cl_qmap_head function returns the map item with the lowest key 524321936Shselasky* value stored in a quick map. 525321936Shselasky* 526321936Shselasky* SYNOPSIS 527321936Shselasky*/ 528321936Shselaskystatic inline cl_map_item_t *cl_qmap_head(IN const cl_qmap_t * const p_map) 529321936Shselasky{ 530321936Shselasky CL_ASSERT(p_map); 531321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 532321936Shselasky return ((cl_map_item_t *) p_map->nil.pool_item.list_item.p_next); 533321936Shselasky} 534321936Shselasky 535321936Shselasky/* 536321936Shselasky* PARAMETERS 537321936Shselasky* p_map 538321936Shselasky* [in] Pointer to a cl_qmap_t structure whose item with the lowest 539321936Shselasky* key is returned. 540321936Shselasky* 541321936Shselasky* RETURN VALUES 542321936Shselasky* Pointer to the map item with the lowest key in the quick map. 543321936Shselasky* 544321936Shselasky* Pointer to the map end if the quick map was empty. 545321936Shselasky* 546321936Shselasky* NOTES 547321936Shselasky* cl_qmap_head does not remove the item from the map. 548321936Shselasky* 549321936Shselasky* SEE ALSO 550321936Shselasky* Quick Map, cl_qmap_tail, cl_qmap_next, cl_qmap_prev, cl_qmap_end, 551321936Shselasky* cl_qmap_item_t 552321936Shselasky*********/ 553321936Shselasky 554321936Shselasky/****f* Component Library: Quick Map/cl_qmap_tail 555321936Shselasky* NAME 556321936Shselasky* cl_qmap_tail 557321936Shselasky* 558321936Shselasky* DESCRIPTION 559321936Shselasky* The cl_qmap_tail function returns the map item with the highest key 560321936Shselasky* value stored in a quick map. 561321936Shselasky* 562321936Shselasky* SYNOPSIS 563321936Shselasky*/ 564321936Shselaskystatic inline cl_map_item_t *cl_qmap_tail(IN const cl_qmap_t * const p_map) 565321936Shselasky{ 566321936Shselasky CL_ASSERT(p_map); 567321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 568321936Shselasky return ((cl_map_item_t *) p_map->nil.pool_item.list_item.p_prev); 569321936Shselasky} 570321936Shselasky 571321936Shselasky/* 572321936Shselasky* PARAMETERS 573321936Shselasky* p_map 574321936Shselasky* [in] Pointer to a cl_qmap_t structure whose item with the 575321936Shselasky* highest key is returned. 576321936Shselasky* 577321936Shselasky* RETURN VALUES 578321936Shselasky* Pointer to the map item with the highest key in the quick map. 579321936Shselasky* 580321936Shselasky* Pointer to the map end if the quick map was empty. 581321936Shselasky* 582321936Shselasky* NOTES 583321936Shselasky* cl_qmap_end does not remove the item from the map. 584321936Shselasky* 585321936Shselasky* SEE ALSO 586321936Shselasky* Quick Map, cl_qmap_head, cl_qmap_next, cl_qmap_prev, cl_qmap_end, 587321936Shselasky* cl_qmap_item_t 588321936Shselasky*********/ 589321936Shselasky 590321936Shselasky/****f* Component Library: Quick Map/cl_qmap_next 591321936Shselasky* NAME 592321936Shselasky* cl_qmap_next 593321936Shselasky* 594321936Shselasky* DESCRIPTION 595321936Shselasky* The cl_qmap_next function returns the map item with the next higher 596321936Shselasky* key value than a specified map item. 597321936Shselasky* 598321936Shselasky* SYNOPSIS 599321936Shselasky*/ 600321936Shselaskystatic inline cl_map_item_t *cl_qmap_next(IN const cl_map_item_t * const p_item) 601321936Shselasky{ 602321936Shselasky CL_ASSERT(p_item); 603321936Shselasky return ((cl_map_item_t *) p_item->pool_item.list_item.p_next); 604321936Shselasky} 605321936Shselasky 606321936Shselasky/* 607321936Shselasky* PARAMETERS 608321936Shselasky* p_item 609321936Shselasky* [in] Pointer to a map item whose successor to return. 610321936Shselasky* 611321936Shselasky* RETURN VALUES 612321936Shselasky* Pointer to the map item with the next higher key value in a quick map. 613321936Shselasky* 614321936Shselasky* Pointer to the map end if the specified item was the last item in 615321936Shselasky* the quick map. 616321936Shselasky* 617321936Shselasky* SEE ALSO 618321936Shselasky* Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_prev, cl_qmap_end, 619321936Shselasky* cl_map_item_t 620321936Shselasky*********/ 621321936Shselasky 622321936Shselasky/****f* Component Library: Quick Map/cl_qmap_prev 623321936Shselasky* NAME 624321936Shselasky* cl_qmap_prev 625321936Shselasky* 626321936Shselasky* DESCRIPTION 627321936Shselasky* The cl_qmap_prev function returns the map item with the next lower 628321936Shselasky* key value than a precified map item. 629321936Shselasky* 630321936Shselasky* SYNOPSIS 631321936Shselasky*/ 632321936Shselaskystatic inline cl_map_item_t *cl_qmap_prev(IN const cl_map_item_t * const p_item) 633321936Shselasky{ 634321936Shselasky CL_ASSERT(p_item); 635321936Shselasky return ((cl_map_item_t *) p_item->pool_item.list_item.p_prev); 636321936Shselasky} 637321936Shselasky 638321936Shselasky/* 639321936Shselasky* PARAMETERS 640321936Shselasky* p_item 641321936Shselasky* [in] Pointer to a map item whose predecessor to return. 642321936Shselasky* 643321936Shselasky* RETURN VALUES 644321936Shselasky* Pointer to the map item with the next lower key value in a quick map. 645321936Shselasky* 646321936Shselasky* Pointer to the map end if the specifid item was the first item in 647321936Shselasky* the quick map. 648321936Shselasky* 649321936Shselasky* SEE ALSO 650321936Shselasky* Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_end, 651321936Shselasky* cl_map_item_t 652321936Shselasky*********/ 653321936Shselasky 654321936Shselasky/****f* Component Library: Quick Map/cl_qmap_insert 655321936Shselasky* NAME 656321936Shselasky* cl_qmap_insert 657321936Shselasky* 658321936Shselasky* DESCRIPTION 659321936Shselasky* The cl_qmap_insert function inserts a map item into a quick map. 660321936Shselasky* NOTE: Only if such a key does not alerady exist in the map !!!! 661321936Shselasky* 662321936Shselasky* SYNOPSIS 663321936Shselasky*/ 664321936Shselaskycl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map, 665321936Shselasky IN const uint64_t key, 666321936Shselasky IN cl_map_item_t * const p_item); 667321936Shselasky/* 668321936Shselasky* PARAMETERS 669321936Shselasky* p_map 670321936Shselasky* [in] Pointer to a cl_qmap_t structure into which to add the item. 671321936Shselasky* 672321936Shselasky* key 673321936Shselasky* [in] Value to assign to the item. 674321936Shselasky* 675321936Shselasky* p_item 676321936Shselasky* [in] Pointer to a cl_map_item_t stucture to insert into the quick map. 677321936Shselasky* 678321936Shselasky* RETURN VALUE 679321936Shselasky* Pointer to the item in the map with the specified key. If insertion 680321936Shselasky* was successful, this is the pointer to the item. If an item with the 681321936Shselasky* specified key already exists in the map, the pointer to that item is 682321936Shselasky* returned - but the new key is NOT inserted... 683321936Shselasky* 684321936Shselasky* NOTES 685321936Shselasky* Insertion operations may cause the quick map to rebalance. 686321936Shselasky* 687321936Shselasky* SEE ALSO 688321936Shselasky* Quick Map, cl_qmap_remove, cl_map_item_t 689321936Shselasky*********/ 690321936Shselasky 691321936Shselasky/****f* Component Library: Quick Map/cl_qmap_get 692321936Shselasky* NAME 693321936Shselasky* cl_qmap_get 694321936Shselasky* 695321936Shselasky* DESCRIPTION 696321936Shselasky* The cl_qmap_get function returns the map item associated with a key. 697321936Shselasky* 698321936Shselasky* SYNOPSIS 699321936Shselasky*/ 700321936Shselaskycl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map, 701321936Shselasky IN const uint64_t key); 702321936Shselasky/* 703321936Shselasky* PARAMETERS 704321936Shselasky* p_map 705321936Shselasky* [in] Pointer to a cl_qmap_t structure from which to retrieve the 706321936Shselasky* item with the specified key. 707321936Shselasky* 708321936Shselasky* key 709321936Shselasky* [in] Key value used to search for the desired map item. 710321936Shselasky* 711321936Shselasky* RETURN VALUES 712321936Shselasky* Pointer to the map item with the desired key value. 713321936Shselasky* 714321936Shselasky* Pointer to the map end if there was no item with the desired key value 715321936Shselasky* stored in the quick map. 716321936Shselasky* 717321936Shselasky* NOTES 718321936Shselasky* cl_qmap_get does not remove the item from the quick map. 719321936Shselasky* 720321936Shselasky* SEE ALSO 721321936Shselasky* Quick Map, cl_qmap_get_next, cl_qmap_remove 722321936Shselasky*********/ 723321936Shselasky 724321936Shselasky/****f* Component Library: Quick Map/cl_qmap_get_next 725321936Shselasky* NAME 726321936Shselasky* cl_qmap_get_next 727321936Shselasky* 728321936Shselasky* DESCRIPTION 729321936Shselasky* The cl_qmap_get_next function returns the first map item associated with a 730321936Shselasky* key > the key specified. 731321936Shselasky* 732321936Shselasky* SYNOPSIS 733321936Shselasky*/ 734321936Shselaskycl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map, 735321936Shselasky IN const uint64_t key); 736321936Shselasky/* 737321936Shselasky* PARAMETERS 738321936Shselasky* p_map 739321936Shselasky* [in] Pointer to a cl_qmap_t structure from which to retrieve the 740321936Shselasky* first item with a key > the specified key. 741321936Shselasky* 742321936Shselasky* key 743321936Shselasky* [in] Key value used to search for the desired map item. 744321936Shselasky* 745321936Shselasky* RETURN VALUES 746321936Shselasky* Pointer to the first map item with a key > the desired key value. 747321936Shselasky* 748321936Shselasky* Pointer to the map end if there was no item with a key > the desired key 749321936Shselasky* value stored in the quick map. 750321936Shselasky* 751321936Shselasky* NOTES 752321936Shselasky* cl_qmap_get_next does not remove the item from the quick map. 753321936Shselasky* 754321936Shselasky* SEE ALSO 755321936Shselasky* Quick Map, cl_qmap_get, cl_qmap_remove 756321936Shselasky*********/ 757321936Shselasky 758321936Shselasky/****f* Component Library: Quick Map/cl_qmap_remove_item 759321936Shselasky* NAME 760321936Shselasky* cl_qmap_remove_item 761321936Shselasky* 762321936Shselasky* DESCRIPTION 763321936Shselasky* The cl_qmap_remove_item function removes the specified map item 764321936Shselasky* from a quick map. 765321936Shselasky* 766321936Shselasky* SYNOPSIS 767321936Shselasky*/ 768321936Shselaskyvoid 769321936Shselaskycl_qmap_remove_item(IN cl_qmap_t * const p_map, 770321936Shselasky IN cl_map_item_t * const p_item); 771321936Shselasky/* 772321936Shselasky* PARAMETERS 773321936Shselasky* p_item 774321936Shselasky* [in] Pointer to a map item to remove from its quick map. 775321936Shselasky* 776321936Shselasky* RETURN VALUES 777321936Shselasky* This function does not return a value. 778321936Shselasky* 779321936Shselasky* In a debug build, cl_qmap_remove_item asserts that the item being removed 780321936Shselasky* is in the specified map. 781321936Shselasky* 782321936Shselasky* NOTES 783321936Shselasky* Removes the map item pointed to by p_item from its quick map. 784321936Shselasky* 785321936Shselasky* SEE ALSO 786321936Shselasky* Quick Map, cl_qmap_remove, cl_qmap_remove_all, cl_qmap_insert 787321936Shselasky*********/ 788321936Shselasky 789321936Shselasky/****f* Component Library: Quick Map/cl_qmap_remove 790321936Shselasky* NAME 791321936Shselasky* cl_qmap_remove 792321936Shselasky* 793321936Shselasky* DESCRIPTION 794321936Shselasky* The cl_qmap_remove function removes the map item with the specified key 795321936Shselasky* from a quick map. 796321936Shselasky* 797321936Shselasky* SYNOPSIS 798321936Shselasky*/ 799321936Shselaskycl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, 800321936Shselasky IN const uint64_t key); 801321936Shselasky/* 802321936Shselasky* PARAMETERS 803321936Shselasky* p_map 804321936Shselasky* [in] Pointer to a cl_qmap_t structure from which to remove the item 805321936Shselasky* with the specified key. 806321936Shselasky* 807321936Shselasky* key 808321936Shselasky* [in] Key value used to search for the map item to remove. 809321936Shselasky* 810321936Shselasky* RETURN VALUES 811321936Shselasky* Pointer to the removed map item if it was found. 812321936Shselasky* 813321936Shselasky* Pointer to the map end if no item with the specified key exists in the 814321936Shselasky* quick map. 815321936Shselasky* 816321936Shselasky* SEE ALSO 817321936Shselasky* Quick Map, cl_qmap_remove_item, cl_qmap_remove_all, cl_qmap_insert 818321936Shselasky*********/ 819321936Shselasky 820321936Shselasky/****f* Component Library: Quick Map/cl_qmap_remove_all 821321936Shselasky* NAME 822321936Shselasky* cl_qmap_remove_all 823321936Shselasky* 824321936Shselasky* DESCRIPTION 825321936Shselasky* The cl_qmap_remove_all function removes all items in a quick map, 826321936Shselasky* leaving it empty. 827321936Shselasky* 828321936Shselasky* SYNOPSIS 829321936Shselasky*/ 830321936Shselaskystatic inline void cl_qmap_remove_all(IN cl_qmap_t * const p_map) 831321936Shselasky{ 832321936Shselasky CL_ASSERT(p_map); 833321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 834321936Shselasky 835321936Shselasky p_map->root.p_left = &p_map->nil; 836321936Shselasky p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item; 837321936Shselasky p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item; 838321936Shselasky p_map->count = 0; 839321936Shselasky} 840321936Shselasky 841321936Shselasky/* 842321936Shselasky* PARAMETERS 843321936Shselasky* p_map 844321936Shselasky* [in] Pointer to a cl_qmap_t structure to empty. 845321936Shselasky* 846321936Shselasky* RETURN VALUES 847321936Shselasky* This function does not return a value. 848321936Shselasky* 849321936Shselasky* SEE ALSO 850321936Shselasky* Quick Map, cl_qmap_remove, cl_qmap_remove_item 851321936Shselasky*********/ 852321936Shselasky 853321936Shselasky/****f* Component Library: Quick Map/cl_qmap_merge 854321936Shselasky* NAME 855321936Shselasky* cl_qmap_merge 856321936Shselasky* 857321936Shselasky* DESCRIPTION 858321936Shselasky* The cl_qmap_merge function moves all items from one map to another, 859321936Shselasky* excluding duplicates. 860321936Shselasky* 861321936Shselasky* SYNOPSIS 862321936Shselasky*/ 863321936Shselaskyvoid 864321936Shselaskycl_qmap_merge(OUT cl_qmap_t * const p_dest_map, 865321936Shselasky IN OUT cl_qmap_t * const p_src_map); 866321936Shselasky/* 867321936Shselasky* PARAMETERS 868321936Shselasky* p_dest_map 869321936Shselasky* [out] Pointer to a cl_qmap_t structure to which items should be added. 870321936Shselasky* 871321936Shselasky* p_src_map 872321936Shselasky* [in/out] Pointer to a cl_qmap_t structure whose items to add 873321936Shselasky* to p_dest_map. 874321936Shselasky* 875321936Shselasky* RETURN VALUES 876321936Shselasky* This function does not return a value. 877321936Shselasky* 878321936Shselasky* NOTES 879321936Shselasky* Items are evaluated based on their keys only. 880321936Shselasky* 881321936Shselasky* Upon return from cl_qmap_merge, the quick map referenced by p_src_map 882321936Shselasky* contains all duplicate items. 883321936Shselasky* 884321936Shselasky* SEE ALSO 885321936Shselasky* Quick Map, cl_qmap_delta 886321936Shselasky*********/ 887321936Shselasky 888321936Shselasky/****f* Component Library: Quick Map/cl_qmap_delta 889321936Shselasky* NAME 890321936Shselasky* cl_qmap_delta 891321936Shselasky* 892321936Shselasky* DESCRIPTION 893321936Shselasky* The cl_qmap_delta function computes the differences between two maps. 894321936Shselasky* 895321936Shselasky* SYNOPSIS 896321936Shselasky*/ 897321936Shselaskyvoid 898321936Shselaskycl_qmap_delta(IN OUT cl_qmap_t * const p_map1, 899321936Shselasky IN OUT cl_qmap_t * const p_map2, 900321936Shselasky OUT cl_qmap_t * const p_new, OUT cl_qmap_t * const p_old); 901321936Shselasky/* 902321936Shselasky* PARAMETERS 903321936Shselasky* p_map1 904321936Shselasky* [in/out] Pointer to the first of two cl_qmap_t structures whose 905321936Shselasky* differences to compute. 906321936Shselasky* 907321936Shselasky* p_map2 908321936Shselasky* [in/out] Pointer to the second of two cl_qmap_t structures whose 909321936Shselasky* differences to compute. 910321936Shselasky* 911321936Shselasky* p_new 912321936Shselasky* [out] Pointer to an empty cl_qmap_t structure that contains the 913321936Shselasky* items unique to p_map2 upon return from the function. 914321936Shselasky* 915321936Shselasky* p_old 916321936Shselasky* [out] Pointer to an empty cl_qmap_t structure that contains the 917321936Shselasky* items unique to p_map1 upon return from the function. 918321936Shselasky* 919321936Shselasky* RETURN VALUES 920321936Shselasky* This function does not return a value. 921321936Shselasky* 922321936Shselasky* NOTES 923321936Shselasky* Items are evaluated based on their keys. Items that exist in both 924321936Shselasky* p_map1 and p_map2 remain in their respective maps. Items that 925321936Shselasky* exist only p_map1 are moved to p_old. Likewise, items that exist only 926321936Shselasky* in p_map2 are moved to p_new. This function can be useful in evaluating 927321936Shselasky* changes between two maps. 928321936Shselasky* 929321936Shselasky* Both maps pointed to by p_new and p_old must be empty on input. This 930321936Shselasky* requirement removes the possibility of failures. 931321936Shselasky* 932321936Shselasky* SEE ALSO 933321936Shselasky* Quick Map, cl_qmap_merge 934321936Shselasky*********/ 935321936Shselasky 936321936Shselasky/****f* Component Library: Quick Map/cl_qmap_apply_func 937321936Shselasky* NAME 938321936Shselasky* cl_qmap_apply_func 939321936Shselasky* 940321936Shselasky* DESCRIPTION 941321936Shselasky* The cl_qmap_apply_func function executes a specified function 942321936Shselasky* for every item stored in a quick map. 943321936Shselasky* 944321936Shselasky* SYNOPSIS 945321936Shselasky*/ 946321936Shselaskyvoid 947321936Shselaskycl_qmap_apply_func(IN const cl_qmap_t * const p_map, 948321936Shselasky IN cl_pfn_qmap_apply_t pfn_func, 949321936Shselasky IN const void *const context); 950321936Shselasky/* 951321936Shselasky* PARAMETERS 952321936Shselasky* p_map 953321936Shselasky* [in] Pointer to a cl_qmap_t structure. 954321936Shselasky* 955321936Shselasky* pfn_func 956321936Shselasky* [in] Function invoked for every item in the quick map. 957321936Shselasky* See the cl_pfn_qmap_apply_t function type declaration for 958321936Shselasky* details about the callback function. 959321936Shselasky* 960321936Shselasky* context 961321936Shselasky* [in] Value to pass to the callback functions to provide context. 962321936Shselasky* 963321936Shselasky* RETURN VALUE 964321936Shselasky* This function does not return a value. 965321936Shselasky* 966321936Shselasky* NOTES 967321936Shselasky* The function provided must not perform any map operations, as these 968321936Shselasky* would corrupt the quick map. 969321936Shselasky* 970321936Shselasky* SEE ALSO 971321936Shselasky* Quick Map, cl_pfn_qmap_apply_t 972321936Shselasky*********/ 973321936Shselasky 974321936ShselaskyEND_C_DECLS 975321936Shselasky#endif /* _CL_QMAP_H_ */ 976