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.
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:
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
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.
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
38 * Declaration of quick map, a binary tree where the caller always provides
39 * all necessary storage.
45 #include <complib/cl_qpool.h>
48 # define BEGIN_C_DECLS extern "C" {
49 # define END_C_DECLS }
50 #else /* !__cplusplus */
51 # define BEGIN_C_DECLS
53 #endif /* __cplusplus */
56 /****h* Component Library/Quick Map
61 * Quick map implements a binary tree that stores user provided cl_map_item_t
62 * structures. Each item stored in a quick map has a unique 64-bit key
63 * (duplicates are not allowed). Quick map provides the ability to
64 * efficiently search for an item given a key.
66 * Quick map does not allocate any memory, and can therefore not fail
67 * any operations due to insufficient memory. Quick map can thus be useful
68 * in minimizing the error paths in code.
70 * Quick map is not thread safe, and users must provide serialization when
71 * adding and removing items from the map.
73 * The quick map functions operate on a cl_qmap_t structure which should be
74 * treated as opaque and should be manipulated only through the provided
79 * cl_qmap_t, cl_map_item_t, cl_map_obj_t
85 * cl_qmap_set_obj, cl_qmap_obj, cl_qmap_key
91 * cl_qmap_end, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev
94 * cl_qmap_insert, cl_qmap_get, cl_qmap_remove_item, cl_qmap_remove,
95 * cl_qmap_remove_all, cl_qmap_merge, cl_qmap_delta, cl_qmap_get_next
101 * cl_qmap_count, cl_is_qmap_empty,
103 /****i* Component Library: Quick Map/cl_map_color_t
108 * The cl_map_color_t enumerated type is used to note the color of
113 typedef enum _cl_map_color {
120 * The node in the map is red.
123 * The node in the map is black.
126 * Quick Map, cl_map_item_t
129 /****s* Component Library: Quick Map/cl_map_item_t
134 * The cl_map_item_t structure is used by maps to store objects.
136 * The cl_map_item_t structure should be treated as opaque and should
137 * be manipulated only through the provided functions.
141 typedef struct _cl_map_item {
142 /* Must be first to allow casting. */
143 cl_pool_item_t pool_item;
144 struct _cl_map_item *p_left;
145 struct _cl_map_item *p_right;
146 struct _cl_map_item *p_up;
147 cl_map_color_t color;
150 struct _cl_qmap *p_map;
156 * Used to store the item in a doubly linked list, allowing more
157 * efficient map traversal.
160 * Pointer to the map item that is a child to the left of the node.
163 * Pointer to the map item that is a child to the right of the node.
166 * Pointer to the map item that is the parent of the node.
169 * Pointer to the map's NIL item, used as a terminator for leaves.
170 * The NIL sentinel is in the cl_qmap_t structure.
173 * Indicates whether a node is red or black in the map.
176 * Value that uniquely represents a node in a map. This value is
177 * set by calling cl_qmap_insert and can be retrieved by calling
181 * None of the fields of this structure should be manipulated by users, as
182 * they are crititcal to the proper operation of the map in which they
185 * To allow storing items in either a quick list, a quick pool, or a quick
186 * map, the map implementation guarantees that the map item can be safely
187 * cast to a pool item used for storing an object in a quick pool, or cast
188 * to a list item used for storing an object in a quick list. This removes
189 * the need to embed a map item, a list item, and a pool item in objects
190 * that need to be stored in a quick list, a quick pool, and a quick map.
193 * Quick Map, cl_qmap_insert, cl_qmap_key, cl_pool_item_t, cl_list_item_t
196 /****s* Component Library: Quick Map/cl_map_obj_t
201 * The cl_map_obj_t structure is used to store objects in maps.
203 * The cl_map_obj_t structure should be treated as opaque and should
204 * be manipulated only through the provided functions.
208 typedef struct _cl_map_obj {
210 const void *p_object;
215 * Map item used by internally by the map to store an object.
218 * User defined context. Users should not access this field directly.
219 * Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the value
223 * None of the fields of this structure should be manipulated by users, as
224 * they are crititcal to the proper operation of the map in which they
227 * Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the object
228 * stored in a map item, respectively.
231 * Quick Map, cl_qmap_set_obj, cl_qmap_obj, cl_map_item_t
234 /****s* Component Library: Quick Map/cl_qmap_t
239 * Quick map structure.
241 * The cl_qmap_t structure should be treated as opaque and should
242 * be manipulated only through the provided functions.
246 typedef struct _cl_qmap {
255 * Map item that serves as root of the map. The root is set up to
256 * always have itself as parent. The left pointer is set to point
257 * to the item at the root.
260 * Map item that serves as terminator for all leaves, as well as
261 * providing the list item used as quick list for storing map items
262 * in a list for faster traversal.
265 * State of the map, used to verify that operations are permitted.
268 * Number of items in the map.
274 /****d* Component Library: Quick Map/cl_pfn_qmap_apply_t
276 * cl_pfn_qmap_apply_t
279 * The cl_pfn_qmap_apply_t function type defines the prototype for
280 * functions used to iterate items in a quick map.
285 (*cl_pfn_qmap_apply_t) (IN cl_map_item_t * const p_map_item, IN void *context);
289 * [in] Pointer to a cl_map_item_t structure.
292 * [in] Value passed to the callback function.
295 * This function does not return a value.
298 * This function type is provided as function prototype reference for the
299 * function provided by users as a parameter to the cl_qmap_apply_func
303 * Quick Map, cl_qmap_apply_func
306 /****f* Component Library: Quick Map/cl_qmap_count
311 * The cl_qmap_count function returns the number of items stored
316 static inline uint32_t cl_qmap_count(IN const cl_qmap_t * const p_map)
319 CL_ASSERT(p_map->state == CL_INITIALIZED);
320 return ((uint32_t) p_map->count);
326 * [in] Pointer to a cl_qmap_t structure whose item count to return.
329 * Returns the number of items stored in the map.
332 * Quick Map, cl_is_qmap_empty
335 /****f* Component Library: Quick Map/cl_is_qmap_empty
340 * The cl_is_qmap_empty function returns whether a quick map is empty.
344 static inline boolean_t cl_is_qmap_empty(IN const cl_qmap_t * const p_map)
347 CL_ASSERT(p_map->state == CL_INITIALIZED);
349 return (p_map->count == 0);
355 * [in] Pointer to a cl_qmap_t structure to test for emptiness.
358 * TRUE if the quick map is empty.
363 * Quick Map, cl_qmap_count, cl_qmap_remove_all
366 /****f* Component Library: Quick Map/cl_qmap_set_obj
371 * The cl_qmap_set_obj function sets the object stored in a map object.
376 cl_qmap_set_obj(IN cl_map_obj_t * const p_map_obj,
377 IN const void *const p_object)
379 CL_ASSERT(p_map_obj);
380 p_map_obj->p_object = p_object;
386 * [in] Pointer to a map object stucture whose object pointer
390 * [in] User defined context.
393 * This function does not return a value.
396 * Quick Map, cl_qmap_obj
399 /****f* Component Library: Quick Map/cl_qmap_obj
404 * The cl_qmap_obj function returns the object stored in a map object.
408 static inline void *cl_qmap_obj(IN const cl_map_obj_t * const p_map_obj)
410 CL_ASSERT(p_map_obj);
411 return ((void *)p_map_obj->p_object);
417 * [in] Pointer to a map object stucture whose object pointer to return.
420 * Returns the value of the object pointer stored in the map object.
423 * Quick Map, cl_qmap_set_obj
426 /****f* Component Library: Quick Map/cl_qmap_key
431 * The cl_qmap_key function retrieves the key value of a map item.
435 static inline uint64_t cl_qmap_key(IN const cl_map_item_t * const p_item)
438 return (p_item->key);
444 * [in] Pointer to a map item whose key value to return.
447 * Returns the 64-bit key value for the specified map item.
450 * The key value is set in a call to cl_qmap_insert.
453 * Quick Map, cl_qmap_insert
456 /****f* Component Library: Quick Map/cl_qmap_init
461 * The cl_qmap_init function initialized a quick map for use.
465 void cl_qmap_init(IN cl_qmap_t * const p_map);
469 * [in] Pointer to a cl_qmap_t structure to initialize.
472 * This function does not return a value.
475 * Allows calling quick map manipulation functions.
478 * Quick Map, cl_qmap_insert, cl_qmap_remove
481 /****f* Component Library: Quick Map/cl_qmap_end
486 * The cl_qmap_end function returns the end of a quick map.
490 static inline const cl_map_item_t *cl_qmap_end(IN const cl_qmap_t * const p_map)
493 CL_ASSERT(p_map->state == CL_INITIALIZED);
494 /* Nil is the end of the map. */
495 return (&p_map->nil);
501 * [in] Pointer to a cl_qmap_t structure whose end to return.
504 * Pointer to the end of the map.
507 * cl_qmap_end is useful for determining the validity of map items returned
508 * by cl_qmap_head, cl_qmap_tail, cl_qmap_next, or cl_qmap_prev. If the
509 * map item pointer returned by any of these functions compares to the end,
510 * the end of the map was encoutered.
511 * When using cl_qmap_head or cl_qmap_tail, this condition indicates that
515 * Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev
518 /****f* Component Library: Quick Map/cl_qmap_head
523 * The cl_qmap_head function returns the map item with the lowest key
524 * value stored in a quick map.
528 static inline cl_map_item_t *cl_qmap_head(IN const cl_qmap_t * const p_map)
531 CL_ASSERT(p_map->state == CL_INITIALIZED);
532 return ((cl_map_item_t *) p_map->nil.pool_item.list_item.p_next);
538 * [in] Pointer to a cl_qmap_t structure whose item with the lowest
542 * Pointer to the map item with the lowest key in the quick map.
544 * Pointer to the map end if the quick map was empty.
547 * cl_qmap_head does not remove the item from the map.
550 * Quick Map, cl_qmap_tail, cl_qmap_next, cl_qmap_prev, cl_qmap_end,
554 /****f* Component Library: Quick Map/cl_qmap_tail
559 * The cl_qmap_tail function returns the map item with the highest key
560 * value stored in a quick map.
564 static inline cl_map_item_t *cl_qmap_tail(IN const cl_qmap_t * const p_map)
567 CL_ASSERT(p_map->state == CL_INITIALIZED);
568 return ((cl_map_item_t *) p_map->nil.pool_item.list_item.p_prev);
574 * [in] Pointer to a cl_qmap_t structure whose item with the
575 * highest key is returned.
578 * Pointer to the map item with the highest key in the quick map.
580 * Pointer to the map end if the quick map was empty.
583 * cl_qmap_end does not remove the item from the map.
586 * Quick Map, cl_qmap_head, cl_qmap_next, cl_qmap_prev, cl_qmap_end,
590 /****f* Component Library: Quick Map/cl_qmap_next
595 * The cl_qmap_next function returns the map item with the next higher
596 * key value than a specified map item.
600 static inline cl_map_item_t *cl_qmap_next(IN const cl_map_item_t * const p_item)
603 return ((cl_map_item_t *) p_item->pool_item.list_item.p_next);
609 * [in] Pointer to a map item whose successor to return.
612 * Pointer to the map item with the next higher key value in a quick map.
614 * Pointer to the map end if the specified item was the last item in
618 * Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_prev, cl_qmap_end,
622 /****f* Component Library: Quick Map/cl_qmap_prev
627 * The cl_qmap_prev function returns the map item with the next lower
628 * key value than a precified map item.
632 static inline cl_map_item_t *cl_qmap_prev(IN const cl_map_item_t * const p_item)
635 return ((cl_map_item_t *) p_item->pool_item.list_item.p_prev);
641 * [in] Pointer to a map item whose predecessor to return.
644 * Pointer to the map item with the next lower key value in a quick map.
646 * Pointer to the map end if the specifid item was the first item in
650 * Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_end,
654 /****f* Component Library: Quick Map/cl_qmap_insert
659 * The cl_qmap_insert function inserts a map item into a quick map.
660 * NOTE: Only if such a key does not alerady exist in the map !!!!
664 cl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map,
665 IN const uint64_t key,
666 IN cl_map_item_t * const p_item);
670 * [in] Pointer to a cl_qmap_t structure into which to add the item.
673 * [in] Value to assign to the item.
676 * [in] Pointer to a cl_map_item_t stucture to insert into the quick map.
679 * Pointer to the item in the map with the specified key. If insertion
680 * was successful, this is the pointer to the item. If an item with the
681 * specified key already exists in the map, the pointer to that item is
682 * returned - but the new key is NOT inserted...
685 * Insertion operations may cause the quick map to rebalance.
688 * Quick Map, cl_qmap_remove, cl_map_item_t
691 /****f* Component Library: Quick Map/cl_qmap_get
696 * The cl_qmap_get function returns the map item associated with a key.
700 cl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map,
701 IN const uint64_t key);
705 * [in] Pointer to a cl_qmap_t structure from which to retrieve the
706 * item with the specified key.
709 * [in] Key value used to search for the desired map item.
712 * Pointer to the map item with the desired key value.
714 * Pointer to the map end if there was no item with the desired key value
715 * stored in the quick map.
718 * cl_qmap_get does not remove the item from the quick map.
721 * Quick Map, cl_qmap_get_next, cl_qmap_remove
724 /****f* Component Library: Quick Map/cl_qmap_get_next
729 * The cl_qmap_get_next function returns the first map item associated with a
730 * key > the key specified.
734 cl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map,
735 IN const uint64_t key);
739 * [in] Pointer to a cl_qmap_t structure from which to retrieve the
740 * first item with a key > the specified key.
743 * [in] Key value used to search for the desired map item.
746 * Pointer to the first map item with a key > the desired key value.
748 * Pointer to the map end if there was no item with a key > the desired key
749 * value stored in the quick map.
752 * cl_qmap_get_next does not remove the item from the quick map.
755 * Quick Map, cl_qmap_get, cl_qmap_remove
758 /****f* Component Library: Quick Map/cl_qmap_remove_item
760 * cl_qmap_remove_item
763 * The cl_qmap_remove_item function removes the specified map item
769 cl_qmap_remove_item(IN cl_qmap_t * const p_map,
770 IN cl_map_item_t * const p_item);
774 * [in] Pointer to a map item to remove from its quick map.
777 * This function does not return a value.
779 * In a debug build, cl_qmap_remove_item asserts that the item being removed
780 * is in the specified map.
783 * Removes the map item pointed to by p_item from its quick map.
786 * Quick Map, cl_qmap_remove, cl_qmap_remove_all, cl_qmap_insert
789 /****f* Component Library: Quick Map/cl_qmap_remove
794 * The cl_qmap_remove function removes the map item with the specified key
799 cl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map,
800 IN const uint64_t key);
804 * [in] Pointer to a cl_qmap_t structure from which to remove the item
805 * with the specified key.
808 * [in] Key value used to search for the map item to remove.
811 * Pointer to the removed map item if it was found.
813 * Pointer to the map end if no item with the specified key exists in the
817 * Quick Map, cl_qmap_remove_item, cl_qmap_remove_all, cl_qmap_insert
820 /****f* Component Library: Quick Map/cl_qmap_remove_all
825 * The cl_qmap_remove_all function removes all items in a quick map,
830 static inline void cl_qmap_remove_all(IN cl_qmap_t * const p_map)
833 CL_ASSERT(p_map->state == CL_INITIALIZED);
835 p_map->root.p_left = &p_map->nil;
836 p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item;
837 p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item;
844 * [in] Pointer to a cl_qmap_t structure to empty.
847 * This function does not return a value.
850 * Quick Map, cl_qmap_remove, cl_qmap_remove_item
853 /****f* Component Library: Quick Map/cl_qmap_merge
858 * The cl_qmap_merge function moves all items from one map to another,
859 * excluding duplicates.
864 cl_qmap_merge(OUT cl_qmap_t * const p_dest_map,
865 IN OUT cl_qmap_t * const p_src_map);
869 * [out] Pointer to a cl_qmap_t structure to which items should be added.
872 * [in/out] Pointer to a cl_qmap_t structure whose items to add
876 * This function does not return a value.
879 * Items are evaluated based on their keys only.
881 * Upon return from cl_qmap_merge, the quick map referenced by p_src_map
882 * contains all duplicate items.
885 * Quick Map, cl_qmap_delta
888 /****f* Component Library: Quick Map/cl_qmap_delta
893 * The cl_qmap_delta function computes the differences between two maps.
898 cl_qmap_delta(IN OUT cl_qmap_t * const p_map1,
899 IN OUT cl_qmap_t * const p_map2,
900 OUT cl_qmap_t * const p_new, OUT cl_qmap_t * const p_old);
904 * [in/out] Pointer to the first of two cl_qmap_t structures whose
905 * differences to compute.
908 * [in/out] Pointer to the second of two cl_qmap_t structures whose
909 * differences to compute.
912 * [out] Pointer to an empty cl_qmap_t structure that contains the
913 * items unique to p_map2 upon return from the function.
916 * [out] Pointer to an empty cl_qmap_t structure that contains the
917 * items unique to p_map1 upon return from the function.
920 * This function does not return a value.
923 * Items are evaluated based on their keys. Items that exist in both
924 * p_map1 and p_map2 remain in their respective maps. Items that
925 * exist only p_map1 are moved to p_old. Likewise, items that exist only
926 * in p_map2 are moved to p_new. This function can be useful in evaluating
927 * changes between two maps.
929 * Both maps pointed to by p_new and p_old must be empty on input. This
930 * requirement removes the possibility of failures.
933 * Quick Map, cl_qmap_merge
936 /****f* Component Library: Quick Map/cl_qmap_apply_func
941 * The cl_qmap_apply_func function executes a specified function
942 * for every item stored in a quick map.
947 cl_qmap_apply_func(IN const cl_qmap_t * const p_map,
948 IN cl_pfn_qmap_apply_t pfn_func,
949 IN const void *const context);
953 * [in] Pointer to a cl_qmap_t structure.
956 * [in] Function invoked for every item in the quick map.
957 * See the cl_pfn_qmap_apply_t function type declaration for
958 * details about the callback function.
961 * [in] Value to pass to the callback functions to provide context.
964 * This function does not return a value.
967 * The function provided must not perform any map operations, as these
968 * would corrupt the quick map.
971 * Quick Map, cl_pfn_qmap_apply_t
975 #endif /* _CL_QMAP_H_ */