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 flexi map, a binary tree where the caller always provides
39 * all necessary storage.
42 #ifndef _CL_FLEXIMAP_H_
43 #define _CL_FLEXIMAP_H_
45 #include <complib/cl_qmap.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/Flexi Map
61 * Flexi map implements a binary tree that stores user provided cl_fmap_item_t
62 * structures. Each item stored in a flexi map has a unique user defined
63 * key (duplicates are not allowed). Flexi map provides the ability to
64 * efficiently search for an item given a key. Flexi map allows user
65 * defined keys of any size. Storage for keys and a comparison function
66 * are provided by users to allow flexi map to store items with arbitrary
69 * Flexi map does not allocate any memory, and can therefore not fail
70 * any operations due to insufficient memory. Flexi map can thus be useful
71 * in minimizing the error paths in code.
73 * Flexi map is not thread safe, and users must provide serialization when
74 * adding and removing items from the map.
76 * The flexi map functions operate on a cl_fmap_t structure which should
77 * be treated as opaque and should be manipulated only through the provided
82 * cl_fmap_t, cl_fmap_item_t
94 * cl_fmap_end, cl_fmap_head, cl_fmap_tail, cl_fmap_next, cl_fmap_prev
97 * cl_fmap_insert, cl_fmap_get, cl_fmap_remove_item, cl_fmap_remove,
98 * cl_fmap_remove_all, cl_fmap_merge, cl_fmap_delta, cl_fmap_get_next
104 * cl_fmap_count, cl_is_fmap_empty,
106 /****s* Component Library: Flexi Map/cl_fmap_item_t
111 * The cl_fmap_item_t structure is used by maps to store objects.
113 * The cl_fmap_item_t structure should be treated as opaque and should
114 * be manipulated only through the provided functions.
118 typedef struct _cl_fmap_item {
119 /* Must be first to allow casting. */
120 cl_pool_item_t pool_item;
121 struct _cl_fmap_item *p_left;
122 struct _cl_fmap_item *p_right;
123 struct _cl_fmap_item *p_up;
124 cl_map_color_t color;
127 struct _cl_fmap *p_map;
133 * Used to store the item in a doubly linked list, allowing more
134 * efficient map traversal.
137 * Pointer to the map item that is a child to the left of the node.
140 * Pointer to the map item that is a child to the right of the node.
143 * Pointer to the map item that is the parent of the node.
146 * Pointer to the map's NIL item, used as a terminator for leaves.
147 * The NIL sentinel is in the cl_fmap_t structure.
150 * Indicates whether a node is red or black in the map.
153 * Pointer to the value that uniquely represents a node in a map. This
154 * pointer is set by calling cl_fmap_insert and can be retrieved by
155 * calling cl_fmap_key.
158 * None of the fields of this structure should be manipulated by users, as
159 * they are crititcal to the proper operation of the map in which they
162 * To allow storing items in either a quick list, a quick pool, or a flexi
163 * map, the map implementation guarantees that the map item can be safely
164 * cast to a pool item used for storing an object in a quick pool, or cast
165 * to a list item used for storing an object in a quick list. This removes
166 * the need to embed a flexi map item, a list item, and a pool item in
167 * objects that need to be stored in a quick list, a quick pool, and a
171 * Flexi Map, cl_fmap_insert, cl_fmap_key, cl_pool_item_t, cl_list_item_t
174 /****d* Component Library: Flexi Map/cl_pfn_fmap_cmp_t
179 * The cl_pfn_fmap_cmp_t function type defines the prototype for functions
180 * used to compare item keys in a flexi map.
185 (*cl_pfn_fmap_cmp_t) (IN const void *const p_key1,
186 IN const void *const p_key2);
190 * [in] Pointer to the first of two keys to compare.
193 * [in] Pointer to the second of two keys to compare.
196 * Returns 0 if the keys match.
197 * Returns less than 0 if *p_key1 is less than *p_key2.
198 * Returns greater than 0 if *p_key1 is greater than *p_key2.
201 * This function type is provided as function prototype reference for the
202 * function provided by users as a parameter to the cl_fmap_init function.
205 * Flexi Map, cl_fmap_init
208 /****s* Component Library: Flexi Map/cl_fmap_t
213 * Flexi map structure.
215 * The cl_fmap_t structure should be treated as opaque and should
216 * be manipulated only through the provided functions.
220 typedef struct _cl_fmap {
225 cl_pfn_fmap_cmp_t pfn_compare;
230 * Map item that serves as root of the map. The root is set up to
231 * always have itself as parent. The left pointer is set to point
232 * to the item at the root.
235 * Map item that serves as terminator for all leaves, as well as
236 * providing the list item used as quick list for storing map items
237 * in a list for faster traversal.
240 * State of the map, used to verify that operations are permitted.
243 * Number of items in the map.
246 * Pointer to a compare function to invoke to compare the keys of
250 * Flexi Map, cl_pfn_fmap_cmp_t
253 /****d* Component Library: Flexi Map/cl_pfn_fmap_apply_t
255 * cl_pfn_fmap_apply_t
258 * The cl_pfn_fmap_apply_t function type defines the prototype for
259 * functions used to iterate items in a flexi map.
264 (*cl_pfn_fmap_apply_t) (IN cl_fmap_item_t * const p_map_item,
269 * [in] Pointer to a cl_fmap_item_t structure.
272 * [in] Value passed to the callback function.
275 * This function does not return a value.
278 * This function type is provided as function prototype reference for the
279 * function provided by users as a parameter to the cl_fmap_apply_func
283 * Flexi Map, cl_fmap_apply_func
286 /****f* Component Library: Flexi Map/cl_fmap_count
291 * The cl_fmap_count function returns the number of items stored
296 static inline size_t cl_fmap_count(IN const cl_fmap_t * const p_map)
299 CL_ASSERT(p_map->state == CL_INITIALIZED);
300 return (p_map->count);
306 * [in] Pointer to a cl_fmap_t structure whose item count to return.
309 * Returns the number of items stored in the map.
312 * Flexi Map, cl_is_fmap_empty
315 /****f* Component Library: Flexi Map/cl_is_fmap_empty
320 * The cl_is_fmap_empty function returns whether a flexi map is empty.
324 static inline boolean_t cl_is_fmap_empty(IN const cl_fmap_t * const p_map)
327 CL_ASSERT(p_map->state == CL_INITIALIZED);
329 return (p_map->count == 0);
335 * [in] Pointer to a cl_fmap_t structure to test for emptiness.
338 * TRUE if the flexi map is empty.
343 * Flexi Map, cl_fmap_count, cl_fmap_remove_all
346 /****f* Component Library: Flexi Map/cl_fmap_key
351 * The cl_fmap_key function retrieves the key value of a map item.
355 static inline const void *cl_fmap_key(IN const cl_fmap_item_t * const p_item)
358 return (p_item->p_key);
364 * [in] Pointer to a map item whose key value to return.
367 * Returns the a pointer to the key value for the specified map item.
368 * The key value should not be modified to insure proper flexi map operation.
371 * The key value is set in a call to cl_fmap_insert.
374 * Flexi Map, cl_fmap_insert
377 /****f* Component Library: Flexi Map/cl_fmap_init
382 * The cl_fmap_init function initialized a flexi map for use.
386 void cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare);
390 * [in] Pointer to a cl_fmap_t structure to initialize.
393 * [in] Pointer to the compare function used to compare keys.
394 * See the cl_pfn_fmap_cmp_t function type declaration for details
395 * about the callback function.
398 * This function does not return a value.
401 * Allows calling flexi map manipulation functions.
404 * Flexi Map, cl_fmap_insert, cl_fmap_remove
407 /****f* Component Library: Flexi Map/cl_fmap_end
412 * The cl_fmap_end function returns the end of a flexi map.
416 static inline const cl_fmap_item_t *cl_fmap_end(IN const cl_fmap_t *
420 CL_ASSERT(p_map->state == CL_INITIALIZED);
421 /* Nil is the end of the map. */
422 return (&p_map->nil);
428 * [in] Pointer to a cl_fmap_t structure whose end to return.
431 * Pointer to the end of the map.
434 * cl_fmap_end is useful for determining the validity of map items returned
435 * by cl_fmap_head, cl_fmap_tail, cl_fmap_next, or cl_fmap_prev. If the
436 * map item pointer returned by any of these functions compares to the end,
437 * the end of the map was encoutered.
438 * When using cl_fmap_head or cl_fmap_tail, this condition indicates that
442 * Flexi Map, cl_fmap_head, cl_fmap_tail, cl_fmap_next, cl_fmap_prev
445 /****f* Component Library: Flexi Map/cl_fmap_head
450 * The cl_fmap_head function returns the map item with the lowest key
451 * value stored in a flexi map.
455 static inline cl_fmap_item_t *cl_fmap_head(IN const cl_fmap_t * const p_map)
458 CL_ASSERT(p_map->state == CL_INITIALIZED);
459 return ((cl_fmap_item_t *) p_map->nil.pool_item.list_item.p_next);
465 * [in] Pointer to a cl_fmap_t structure whose item with the lowest key
469 * Pointer to the map item with the lowest key in the flexi map.
471 * Pointer to the map end if the flexi map was empty.
474 * cl_fmap_head does not remove the item from the map.
477 * Flexi Map, cl_fmap_tail, cl_fmap_next, cl_fmap_prev, cl_fmap_end,
481 /****f* Component Library: Flexi Map/cl_fmap_tail
486 * The cl_fmap_tail function returns the map item with the highest key
487 * value stored in a flexi map.
491 static inline cl_fmap_item_t *cl_fmap_tail(IN const cl_fmap_t * const p_map)
494 CL_ASSERT(p_map->state == CL_INITIALIZED);
495 return ((cl_fmap_item_t *) p_map->nil.pool_item.list_item.p_prev);
501 * [in] Pointer to a cl_fmap_t structure whose item with the highest key
505 * Pointer to the map item with the highest key in the flexi map.
507 * Pointer to the map end if the flexi map was empty.
510 * cl_fmap_end does not remove the item from the map.
513 * Flexi Map, cl_fmap_head, cl_fmap_next, cl_fmap_prev, cl_fmap_end,
517 /****f* Component Library: Flexi Map/cl_fmap_next
522 * The cl_fmap_next function returns the map item with the next higher
523 * key value than a specified map item.
527 static inline cl_fmap_item_t *cl_fmap_next(IN const cl_fmap_item_t *
531 return ((cl_fmap_item_t *) p_item->pool_item.list_item.p_next);
537 * [in] Pointer to a map item whose successor to return.
540 * Pointer to the map item with the next higher key value in a flexi map.
542 * Pointer to the map end if the specified item was the last item in
546 * Flexi Map, cl_fmap_head, cl_fmap_tail, cl_fmap_prev, cl_fmap_end,
550 /****f* Component Library: Flexi Map/cl_fmap_prev
555 * The cl_fmap_prev function returns the map item with the next lower
556 * key value than a precified map item.
560 static inline cl_fmap_item_t *cl_fmap_prev(IN const cl_fmap_item_t *
564 return ((cl_fmap_item_t *) p_item->pool_item.list_item.p_prev);
570 * [in] Pointer to a map item whose predecessor to return.
573 * Pointer to the map item with the next lower key value in a flexi map.
575 * Pointer to the map end if the specifid item was the first item in
579 * Flexi Map, cl_fmap_head, cl_fmap_tail, cl_fmap_next, cl_fmap_end,
583 /****f* Component Library: Flexi Map/cl_fmap_insert
588 * The cl_fmap_insert function inserts a map item into a flexi map.
592 cl_fmap_item_t *cl_fmap_insert(IN cl_fmap_t * const p_map,
593 IN const void *const p_key,
594 IN cl_fmap_item_t * const p_item);
598 * [in] Pointer to a cl_fmap_t structure into which to add the item.
601 * [in] Pointer to the key value to assign to the item. Storage
602 * for the key must be persistant, as only the pointer is stored.
603 * Users are responsible for maintaining the validity of key
604 * pointers while they are in use.
607 * [in] Pointer to a cl_fmap_item_t stucture to insert into the flexi map.
610 * Pointer to the item in the map with the specified key. If insertion
611 * was successful, this is the pointer to the item. If an item with the
612 * specified key already exists in the map, the pointer to that item is
616 * Insertion operations may cause the flexi map to rebalance.
619 * Flexi Map, cl_fmap_remove, cl_fmap_item_t
622 /****f* Component Library: Flexi Map/cl_fmap_get
627 * The cl_fmap_get function returns the map item associated with a key.
631 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map,
632 IN const void *const p_key);
636 * [in] Pointer to a cl_fmap_t structure from which to retrieve the
637 * item with the specified key.
640 * [in] Pointer to a key value used to search for the desired map item.
643 * Pointer to the map item with the desired key value.
645 * Pointer to the map end if there was no item with the desired key value
646 * stored in the flexi map.
649 * cl_fmap_get does not remove the item from the flexi map.
652 * Flexi Map, cl_fmap_remove, cl_fmap_get_next
655 /****f* Component Library: Flexi Map/cl_fmap_get_next
660 * The cl_fmap_get_next function returns the first map item associated with a
661 * key > the key specified.
665 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map,
666 IN const void *const p_key);
670 * [in] Pointer to a cl_fmap_t structure from which to retrieve the
671 * item with the specified key.
674 * [in] Pointer to a key value used to search for the desired map item.
677 * Pointer to the first map item with a key > the desired key value.
679 * Pointer to the map end if there was no item with a key > the desired key
680 * value stored in the flexi map.
683 * cl_fmap_get_next does not remove the item from the flexi map.
686 * Flexi Map, cl_fmap_remove, cl_fmap_get
689 /****f* Component Library: Flexi Map/cl_fmap_remove_item
691 * cl_fmap_remove_item
694 * The cl_fmap_remove_item function removes the specified map item
700 cl_fmap_remove_item(IN cl_fmap_t * const p_map,
701 IN cl_fmap_item_t * const p_item);
705 * [in] Pointer to a map item to remove from its flexi map.
708 * This function does not return a value.
710 * In a debug build, cl_fmap_remove_item asserts that the item being
711 * removed es in the specified map.
714 * Removes the map item pointed to by p_item from its flexi map.
717 * Flexi Map, cl_fmap_remove, cl_fmap_remove_all, cl_fmap_insert
720 /****f* Component Library: Flexi Map/cl_fmap_remove
725 * The cl_fmap_remove function removes the map item with the specified key
730 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map,
731 IN const void *const p_key);
735 * [in] Pointer to a cl_fmap_t structure from which to remove the
736 * item with the specified key.
739 * [in] Pointer to the key value used to search for the map item
743 * Pointer to the removed map item if it was found.
745 * Pointer to the map end if no item with the specified key exists in the
749 * Flexi Map, cl_fmap_remove_item, cl_fmap_remove_all, cl_fmap_insert
752 /****f* Component Library: Flexi Map/cl_fmap_remove_all
757 * The cl_fmap_remove_all function removes all items in a flexi map,
762 static inline void cl_fmap_remove_all(IN cl_fmap_t * const p_map)
765 CL_ASSERT(p_map->state == CL_INITIALIZED);
767 p_map->root.p_left = &p_map->nil;
768 p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item;
769 p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item;
776 * [in] Pointer to a cl_fmap_t structure to empty.
779 * This function does not return a value.
782 * Flexi Map, cl_fmap_remove, cl_fmap_remove_item
785 /****f* Component Library: Flexi Map/cl_fmap_merge
790 * The cl_fmap_merge function moves all items from one map to another,
791 * excluding duplicates.
796 cl_fmap_merge(OUT cl_fmap_t * const p_dest_map,
797 IN OUT cl_fmap_t * const p_src_map);
801 * [out] Pointer to a cl_fmap_t structure to which items should be added.
804 * [in/out] Pointer to a cl_fmap_t structure whose items to add
808 * This function does not return a value.
811 * Items are evaluated based on their keys only.
813 * Upon return from cl_fmap_merge, the flexi map referenced by p_src_map
814 * contains all duplicate items.
817 * Flexi Map, cl_fmap_delta
820 /****f* Component Library: Flexi Map/cl_fmap_delta
825 * The cl_fmap_delta function computes the differences between two maps.
830 cl_fmap_delta(IN OUT cl_fmap_t * const p_map1,
831 IN OUT cl_fmap_t * const p_map2,
832 OUT cl_fmap_t * const p_new, OUT cl_fmap_t * const p_old);
836 * [in/out] Pointer to the first of two cl_fmap_t structures whose
837 * differences to compute.
840 * [in/out] Pointer to the second of two cl_fmap_t structures whose
841 * differences to compute.
844 * [out] Pointer to an empty cl_fmap_t structure that contains the
845 * items unique to p_map2 upon return from the function.
848 * [out] Pointer to an empty cl_fmap_t structure that contains the
849 * items unique to p_map1 upon return from the function.
852 * This function does not return a value.
855 * Items are evaluated based on their keys. Items that exist in both
856 * p_map1 and p_map2 remain in their respective maps. Items that
857 * exist only p_map1 are moved to p_old. Likewise, items that exist only
858 * in p_map2 are moved to p_new. This function can be useful in evaluating
859 * changes between two maps.
861 * Both maps pointed to by p_new and p_old must be empty on input. This
862 * requirement removes the possibility of failures.
865 * Flexi Map, cl_fmap_merge
868 /****f* Component Library: Flexi Map/cl_fmap_apply_func
873 * The cl_fmap_apply_func function executes a specified function
874 * for every item stored in a flexi map.
879 cl_fmap_apply_func(IN const cl_fmap_t * const p_map,
880 IN cl_pfn_fmap_apply_t pfn_func,
881 IN const void *const context);
885 * [in] Pointer to a cl_fmap_t structure.
888 * [in] Function invoked for every item in the flexi map.
889 * See the cl_pfn_fmap_apply_t function type declaration for
890 * details about the callback function.
893 * [in] Value to pass to the callback functions to provide context.
896 * This function does not return a value.
899 * The function provided must not perform any map operations, as these
900 * would corrupt the flexi map.
903 * Flexi Map, cl_pfn_fmap_apply_t
907 #endif /* _CL_FLEXIMAP_H_ */