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 map, a binary tree. 39 */ 40 41#ifndef _CL_MAP_H_ 42#define _CL_MAP_H_ 43 44#include <complib/cl_qmap.h> 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/Map 57* NAME 58* Map 59* 60* DESCRIPTION 61* Map implements a binary tree that stores user objects. Each item stored 62* in a map has a unique 64-bit key (duplicates are not allowed). Map 63* provides the ability to efficiently search for an item given a key. 64* 65* Map may allocate memory when inserting objects, and can therefore fail 66* operations due to insufficient memory. Use quick map in situations 67* where such insertion failures cannot be tolerated. 68* 69* Map is not thread safe, and users must provide serialization when adding 70* and removing items from the map. 71* 72* The map functions operates on a cl_map_t structure which should be treated 73* as opaque and should be manipulated only through the provided functions. 74* 75* SEE ALSO 76* Types: 77* cl_map_iterator_t 78* 79* Structures: 80* cl_map_t, cl_map_item_t, cl_map_obj_t 81* 82* Item Manipulation: 83* cl_map_obj, cl_map_key 84* 85* Initialization: 86* cl_map_construct, cl_map_init, cl_map_destroy 87* 88* Iteration: 89* cl_map_end, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev 90* 91* Manipulation 92* cl_map_insert, cl_map_get, cl_map_remove_item, cl_map_remove, 93* cl_map_remove_all, cl_map_merge, cl_map_delta, cl_map_get_next 94* 95* Attributes: 96* cl_map_count, cl_is_map_empty, cl_is_map_inited 97*********/ 98/****s* Component Library: Map/cl_map_t 99* NAME 100* cl_map_t 101* 102* DESCRIPTION 103* Quick map structure. 104* 105* The cl_map_t structure should be treated as opaque and should 106* be manipulated only through the provided functions. 107* 108* SYNOPSIS 109*/ 110typedef struct _cl_map { 111 cl_qmap_t qmap; 112 cl_qpool_t pool; 113} cl_map_t; 114/* 115* FIELDS 116* qmap 117* Quick map object that maintains the map. 118* 119* pool 120* Pool of cl_map_obj_t structures used to store user objects 121* in the map. 122* 123* SEE ALSO 124* Map, cl_map_obj_t 125*********/ 126 127/****d* Component Library: Map/cl_map_iterator_t 128* NAME 129* cl_map_iterator_t 130* 131* DESCRIPTION 132* Iterator type used to walk a map. 133* 134* SYNOPSIS 135*/ 136typedef const cl_map_item_t *cl_map_iterator_t; 137/* 138* NOTES 139* The iterator should be treated as opaque to prevent corrupting the map. 140* 141* SEE ALSO 142* Map, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev, cl_map_key 143*********/ 144 145/****f* Component Library: Map/cl_map_count 146* NAME 147* cl_map_count 148* 149* DESCRIPTION 150* The cl_map_count function returns the number of items stored 151* in a map. 152* 153* SYNOPSIS 154*/ 155static inline size_t cl_map_count(IN const cl_map_t * const p_map) 156{ 157 CL_ASSERT(p_map); 158 return (cl_qmap_count(&p_map->qmap)); 159} 160 161/* 162* PARAMETERS 163* p_map 164* [in] Pointer to a map whose item count to return. 165* 166* RETURN VALUE 167* Returns the number of items stored in the map. 168* 169* SEE ALSO 170* Map, cl_is_map_empty 171*********/ 172 173/****f* Component Library: Map/cl_is_map_empty 174* NAME 175* cl_is_map_empty 176* 177* DESCRIPTION 178* The cl_is_map_empty function returns whether a map is empty. 179* 180* SYNOPSIS 181*/ 182static inline boolean_t cl_is_map_empty(IN const cl_map_t * const p_map) 183{ 184 CL_ASSERT(p_map); 185 return (cl_is_qmap_empty(&p_map->qmap)); 186} 187 188/* 189* PARAMETERS 190* p_map 191* [in] Pointer to a map to test for emptiness. 192* 193* RETURN VALUES 194* TRUE if the map is empty. 195* 196* FALSE otherwise. 197* 198* SEE ALSO 199* Map, cl_map_count, cl_map_remove_all 200*********/ 201 202/****f* Component Library: Map/cl_map_key 203* NAME 204* cl_map_key 205* 206* DESCRIPTION 207* The cl_map_key function retrieves the key value of a map item. 208* 209* SYNOPSIS 210*/ 211static inline uint64_t cl_map_key(IN const cl_map_iterator_t itor) 212{ 213 return (cl_qmap_key(itor)); 214} 215 216/* 217* PARAMETERS 218* itor 219* [in] Iterator for the item whose key to return. 220* 221* RETURN VALUE 222* Returns the 64-bit key value for the specified iterator. 223* 224* NOTES 225* The iterator specified by the itor parameter must have been retrived by 226* a previous call to cl_map_head, cl_map_tail, cl_map_next, or cl_map_prev. 227* 228* The key value is set in a call to cl_map_insert. 229* 230* SEE ALSO 231* Map, cl_map_insert, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev 232*********/ 233 234/****f* Component Library: Map/cl_map_construct 235* NAME 236* cl_map_construct 237* 238* DESCRIPTION 239* The cl_map_construct function constructs a map. 240* 241* SYNOPSIS 242*/ 243void cl_map_construct(IN cl_map_t * const p_map); 244/* 245* PARAMETERS 246* p_map 247* [in] Pointer to a cl_map_t structure to construct. 248* 249* RETURN VALUE 250* This function does not return a value. 251* 252* NOTES 253* Allows calling cl_map_init, cl_map_destroy, and cl_is_map_inited. 254* 255* Calling cl_map_construct is a prerequisite to calling any other 256* map function except cl_map_init. 257* 258* SEE ALSO 259* Map, cl_map_init, cl_map_destroy, cl_is_map_inited 260*********/ 261 262/****f* Component Library: Event/cl_is_map_inited 263* NAME 264* cl_is_map_inited 265* 266* DESCRIPTION 267* The cl_is_map_inited function returns whether a map was 268* successfully initialized. 269* 270* SYNOPSIS 271*/ 272static inline boolean_t cl_is_map_inited(IN const cl_map_t * const p_map) 273{ 274 /* 275 * The map's pool of map items is the last thing initialized. 276 * We can therefore use it to test for initialization. 277 */ 278 return (cl_is_qpool_inited(&p_map->pool)); 279} 280 281/* 282* PARAMETERS 283* p_map 284* [in] Pointer to a cl_map_t structure whose initialization state 285* to check. 286* 287* RETURN VALUES 288* TRUE if the map was initialized successfully. 289* 290* FALSE otherwise. 291* 292* NOTES 293* Allows checking the state of a map to determine if invoking 294* member functions is appropriate. 295* 296* SEE ALSO 297* Map 298*********/ 299 300/****f* Component Library: Map/cl_map_init 301* NAME 302* cl_map_init 303* 304* DESCRIPTION 305* The cl_map_init function initialized a map for use. 306* 307* SYNOPSIS 308*/ 309cl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items); 310/* 311* PARAMETERS 312* p_map 313* [in] Pointer to a cl_map_t structure to initialize. 314* 315* min_items 316* [in] Minimum number of items that can be stored. All necessary 317* allocations to allow storing the minimum number of items is 318* performed at initialization time. 319* 320* RETURN VALUES 321* CL_SUCCESS if the map was initialized successfully. 322* 323* NOTES 324* Allows calling map manipulation functions. 325* 326* SEE ALSO 327* Map, cl_map_destroy, cl_map_insert, cl_map_remove 328*********/ 329 330/****f* Component Library: Map/cl_map_destroy 331* NAME 332* cl_map_destroy 333* 334* DESCRIPTION 335* The cl_map_destroy function destroys a map. 336* 337* SYNOPSIS 338*/ 339void cl_map_destroy(IN cl_map_t * const p_map); 340/* 341* PARAMETERS 342* p_map 343* [in] Pointer to a map to destroy. 344* 345* RETURN VALUE 346* This function does not return a value. 347* 348* NOTES 349* Performs any necessary cleanup of the specified map. Further 350* operations should not be attempted on the map. cl_map_destroy does 351* not affect any of the objects stored in the map. 352* This function should only be called after a call to cl_map_construct. 353* 354* In debug builds, cl_map_destroy asserts that the map is empty. 355* 356* SEE ALSO 357* Map, cl_map_construct, cl_map_init 358*********/ 359 360/****f* Component Library: Map/cl_map_end 361* NAME 362* cl_map_end 363* 364* DESCRIPTION 365* The cl_map_end function returns the iterator for the end of a map. 366* 367* SYNOPSIS 368*/ 369static inline cl_map_iterator_t cl_map_end(IN const cl_map_t * const p_map) 370{ 371 CL_ASSERT(p_map); 372 return (cl_qmap_end(&p_map->qmap)); 373} 374 375/* 376* PARAMETERS 377* p_map 378* [in] Pointer to a cl_map_t structure whose end to return. 379* 380* RETURN VALUE 381* Iterator for the end of the map. 382* 383* NOTES 384* cl_map_end is useful for determining the validity of map items returned 385* by cl_map_head, cl_map_tail, cl_map_next, cl_map_prev. If the iterator 386* by any of these functions compares to the end, the end of the map was 387* encoutered. 388* When using cl_map_head or cl_map_tail, this condition indicates that 389* the map is empty. 390* 391* SEE ALSO 392* Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev 393*********/ 394 395/****f* Component Library: Map/cl_map_head 396* NAME 397* cl_map_head 398* 399* DESCRIPTION 400* The cl_map_head function returns the map item with the lowest key 401* value stored in a map. 402* 403* SYNOPSIS 404*/ 405static inline cl_map_iterator_t cl_map_head(IN const cl_map_t * const p_map) 406{ 407 CL_ASSERT(p_map); 408 return (cl_qmap_head(&p_map->qmap)); 409} 410 411/* 412* PARAMETERS 413* p_map 414* [in] Pointer to a map whose item with the lowest key is returned. 415* 416* RETURN VALUES 417* Iterator for the object with the lowest key in the map. 418* 419* Iterator for the map end if the map was empty. 420* 421* NOTES 422* cl_map_head does not remove the object from the map. 423* 424* SEE ALSO 425* Map, cl_map_tail, cl_map_next, cl_map_prev, cl_map_end 426*********/ 427 428/****f* Component Library: Map/cl_map_tail 429* NAME 430* cl_map_tail 431* 432* DESCRIPTION 433* The cl_map_tail function returns the map item with the highest key 434* value stored in a map. 435* 436* SYNOPSIS 437*/ 438static inline cl_map_iterator_t cl_map_tail(IN const cl_map_t * const p_map) 439{ 440 CL_ASSERT(p_map); 441 return (cl_qmap_tail(&p_map->qmap)); 442} 443 444/* 445* PARAMETERS 446* p_map 447* [in] Pointer to a map whose item with the highest key 448* is returned. 449* 450* RETURN VALUES 451* Iterator for the object with the highest key in the map. 452* 453* Iterator for the map end if the map was empty. 454* 455* NOTES 456* cl_map_end does no remove the object from the map. 457* 458* SEE ALSO 459* Map, cl_map_head, cl_map_next, cl_map_prev, cl_map_end 460*********/ 461 462/****f* Component Library: Map/cl_map_next 463* NAME 464* cl_map_next 465* 466* DESCRIPTION 467* The cl_map_next function returns the map item with the next higher 468* key value than a specified map item. 469* 470* SYNOPSIS 471*/ 472static inline cl_map_iterator_t cl_map_next(IN const cl_map_iterator_t itor) 473{ 474 CL_ASSERT(itor); 475 return (cl_qmap_next(itor)); 476} 477 478/* 479* PARAMETERS 480* itor 481* [in] Iterator for an object in a map whose successor to return. 482* 483* RETURN VALUES 484* Iterator for the object with the next higher key value in a map. 485* 486* Iterator for the map end if the specified object was the last item in 487* the map. 488* 489* NOTES 490* The iterator must have been retrieved by a previous call to cl_map_head, 491* cl_map_tail, cl_map_next, or cl_map_prev. 492* 493* SEE ALSO 494* Map, cl_map_head, cl_map_tail, cl_map_prev, cl_map_end 495*********/ 496 497/****f* Component Library: Map/cl_map_prev 498* NAME 499* cl_map_prev 500* 501* DESCRIPTION 502* The cl_map_prev function returns the map item with the next lower 503* key value than a precified map item. 504* 505* SYNOPSIS 506*/ 507static inline cl_map_iterator_t cl_map_prev(IN const cl_map_iterator_t itor) 508{ 509 CL_ASSERT(itor); 510 return (cl_qmap_prev(itor)); 511} 512 513/* 514* PARAMETERS 515* itor 516* [in] Iterator for an object in a map whose predecessor to return. 517* 518* RETURN VALUES 519* Iterator for the object with the next lower key value in a map. 520* 521* Iterator for the map end if the specified object was the first item in 522* the map. 523* 524* NOTES 525* The iterator must have been retrieved by a previous call to cl_map_head, 526* cl_map_tail, cl_map_next, or cl_map_prev. 527* 528* SEE ALSO 529* Map, cl_map_head, cl_map_tail, cl_map_next, cl_map_end 530*********/ 531 532/****f* Component Library: Map/cl_map_insert 533* NAME 534* cl_map_insert 535* 536* DESCRIPTION 537* The cl_map_insert function inserts a map item into a map. 538* 539* SYNOPSIS 540*/ 541void *cl_map_insert(IN cl_map_t * const p_map, 542 IN const uint64_t key, IN const void *const p_object); 543/* 544* PARAMETERS 545* p_map 546* [in] Pointer to a map into which to add the item. 547* 548* key 549* [in] Value to associate with the object. 550* 551* p_object 552* [in] Pointer to an object to insert into the map. 553* 554* RETURN VALUES 555* Pointer to the object in the map with the specified key after the call 556* completes. 557* 558* NULL if there was not enough memory to insert the desired item. 559* 560* NOTES 561* Insertion operations may cause the map to rebalance. 562* 563* If the map already contains an object already with the specified key, 564* that object will not be replaced and the pointer to that object is 565* returned. 566* 567* SEE ALSO 568* Map, cl_map_remove, cl_map_item_t 569*********/ 570 571/****f* Component Library: Map/cl_map_get 572* NAME 573* cl_map_get 574* 575* DESCRIPTION 576* The cl_map_get function returns the object associated with a key. 577* 578* SYNOPSIS 579*/ 580void *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key); 581/* 582* PARAMETERS 583* p_map 584* [in] Pointer to a map from which to retrieve the object with 585* the specified key. 586* 587* key 588* [in] Key value used to search for the desired object. 589* 590* RETURN VALUES 591* Pointer to the object with the desired key value. 592* 593* NULL if there was no item with the desired key value stored in 594* the map. 595* 596* NOTES 597* cl_map_get does not remove the item from the map. 598* 599* SEE ALSO 600* Map, cl_map_remove, cl_map_get_next 601*********/ 602 603/****f* Component Library: Map/cl_map_get_next 604* NAME 605* cl_map_get_next 606* 607* DESCRIPTION 608* The cl_qmap_get_next function returns the first object associated with a 609* key > the key specified. 610* 611* SYNOPSIS 612*/ 613void *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key); 614/* 615* PARAMETERS 616* p_map 617* [in] Pointer to a map from which to retrieve the object with 618* the specified key. 619* 620* key 621* [in] Key value used to search for the desired object. 622* 623* RETURN VALUES 624* Pointer to the first object with a key > the desired key value. 625* 626* NULL if there was no item with a key > the desired key 627* value stored in the map. 628* 629* NOTES 630* cl_map_get does not remove the item from the map. 631* 632* SEE ALSO 633* Map, cl_map_remove, cl_map_get 634*********/ 635 636/****f* Component Library: Map/cl_map_remove_item 637* NAME 638* cl_map_remove_item 639* 640* DESCRIPTION 641* The cl_map_remove_item function removes the specified map item 642* from a map. 643* 644* SYNOPSIS 645*/ 646void 647cl_map_remove_item(IN cl_map_t * const p_map, IN const cl_map_iterator_t itor); 648/* 649* PARAMETERS 650* p_map 651* [in] Pointer to a map from which to remove the object associated 652* with the specified iterator. 653* 654* itor 655* [in] Iterator for an object to remove from its map. 656* 657* RETURN VALUE 658* This function does not return a value. 659* 660* NOTES 661* Removes the object associated with the specifid iterator from its map. 662* 663* The specified iterator is no longer valid after the call completes. 664* 665* The iterator must have been retrieved by a previous call to cl_map_head, 666* cl_map_tail, cl_map_next, or cl_map_prev. 667* 668* SEE ALSO 669* Map, cl_map_remove, cl_map_remove_all, cl_map_insert, cl_map_head, 670* cl_map_tail, cl_map_next, cl_map_prev 671*********/ 672 673/****f* Component Library: Map/cl_map_remove 674* NAME 675* cl_map_remove 676* 677* DESCRIPTION 678* The cl_map_remove function removes the map item with the specified key 679* from a map. 680* 681* SYNOPSIS 682*/ 683void *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key); 684/* 685* PARAMETERS 686* p_map 687* [in] Pointer to a cl_map_t structure from which to remove the 688* item with the specified key. 689* 690* key 691* [in] Key value used to search for the object to remove. 692* 693* RETURN VALUES 694* Pointer to the object associated with the specified key if 695* it was found and removed. 696* 697* NULL if no object with the specified key exists in the map. 698* 699* SEE ALSO 700* Map, cl_map_remove_item, cl_map_remove_all, cl_map_insert 701*********/ 702 703/****f* Component Library: Map/cl_map_remove_all 704* NAME 705* cl_map_remove_all 706* 707* DESCRIPTION 708* The cl_map_remove_all function removes all objects from a map, 709* leaving it empty. 710* 711* SYNOPSIS 712*/ 713void cl_map_remove_all(IN cl_map_t * const p_map); 714/* 715* PARAMETERS 716* p_map 717* [in] Pointer to a map to empty. 718* 719* RETURN VALUE 720* This function does not return a value. 721* 722* SEE ALSO 723* Map, cl_map_remove, cl_map_remove_item 724*********/ 725 726/****f* Component Library: Map/cl_map_obj 727* NAME 728* cl_map_obj 729* 730* DESCRIPTION 731* The cl_map_obj function returns the object associated with an iterator. 732* 733* SYNOPSIS 734*/ 735static inline void *cl_map_obj(IN const cl_map_iterator_t itor) 736{ 737 return (cl_qmap_obj(PARENT_STRUCT(itor, cl_map_obj_t, item))); 738} 739 740/* 741* PARAMETERS 742* itor 743* [in] Iterator whose object to return. 744* 745* RETURN VALUES 746* Returns the value of the object pointer associated with the iterator. 747* 748* The iterator must have been retrieved by a previous call to cl_map_head, 749* cl_map_tail, cl_map_next, or cl_map_prev. 750* 751* SEE ALSO 752* Map, cl_map_head, cl_map_tail, cl_map_next, cl_map_prev 753*********/ 754 755/****f* Component Library: Map/cl_map_merge 756* NAME 757* cl_map_merge 758* 759* DESCRIPTION 760* The cl_map_merge function moves all items from one map to another, 761* excluding duplicates. 762* 763* SYNOPSIS 764*/ 765cl_status_t 766cl_map_merge(OUT cl_map_t * const p_dest_map, 767 IN OUT cl_map_t * const p_src_map); 768/* 769* PARAMETERS 770* p_dest_map 771* [out] Pointer to a cl_map_t structure to which items should be added. 772* 773* p_src_map 774* [in/out] Pointer to a cl_map_t structure whose items to add 775* to p_dest_map. 776* 777* RETURN VALUES 778* CL_SUCCESS if the operation succeeded. 779* 780* CL_INSUFFICIENT_MEMORY if there was not enough memory for the operation 781* to succeed. 782* 783* NOTES 784* Items are evaluated based on their keys only. 785* 786* Upon return from cl_map_merge, the map referenced by p_src_map contains 787* all duplicate items. 788* 789* SEE ALSO 790* Map, cl_map_delta 791*********/ 792 793/****f* Component Library: Map/cl_map_delta 794* NAME 795* cl_map_delta 796* 797* DESCRIPTION 798* The cl_map_delta function computes the differences between two maps. 799* 800* SYNOPSIS 801*/ 802cl_status_t 803cl_map_delta(IN OUT cl_map_t * const p_map1, 804 IN OUT cl_map_t * const p_map2, 805 OUT cl_map_t * const p_new, OUT cl_map_t * const p_old); 806/* 807* PARAMETERS 808* p_map1 809* [in/out] Pointer to the first of two cl_map_t structures whose 810* differences to compute. 811* 812* p_map2 813* [in/out] Pointer to the second of two cl_map_t structures whose 814* differences to compute. 815* 816* p_new 817* [out] Pointer to an empty cl_map_t structure that contains the 818* items unique to p_map2 upon return from the function. 819* 820* p_old 821* [out] Pointer to an empty cl_map_t structure that contains the 822* items unique to p_map1 upon return from the function. 823* 824* RETURN VALUES 825* CL_SUCCESS if the operation succeeded. 826* 827* CL_INSUFFICIENT_MEMORY if there was not enough memory for the operation 828* to succeed. 829* 830* NOTES 831* Items are evaluated based on their keys. Items that exist in both 832* p_map1 and p_map2 remain in their respective maps. Items that 833* exist only p_map1 are moved to p_old. Likewise, items that exist only 834* in p_map2 are moved to p_new. This function can be useful in evaluating 835* changes between two maps. 836* 837* Both maps pointed to by p_new and p_old must be empty on input. 838* 839* Upon failure, all input maps are restored to their original state. 840* 841* SEE ALSO 842* Map, cl_map_merge 843*********/ 844 845END_C_DECLS 846#endif /* _CL_MAP_H_ */ 847