Lines Matching +full:no +full:- +full:map
2 * Copyright (c) 2004-2009 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.
16 * - Redistributions of source code must retain the above
20 * - Redistributions in binary form must reproduce the above
28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
38 * Declaration of flexi map, a binary tree where the caller always provides
56 /****h* Component Library/Flexi Map
58 * 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
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
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
106 /****s* Component Library: Flexi Map/cl_fmap_item_t
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.
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
159 * they are crititcal to the proper operation of the map in which they
163 * map, the map implementation guarantees that the map item can be safely
166 * the need to embed a flexi map item, a list item, and a pool item in
168 * flexi map.
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
180 * used to compare item keys in a flexi map.
205 * Flexi Map, cl_fmap_init
208 /****s* Component Library: Flexi Map/cl_fmap_t
213 * Flexi map structure.
230 * Map item that serves as root of the map. The root is set up to
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
240 * State of the map, used to verify that operations are permitted.
243 * Number of items in the map.
247 * items in the map.
250 * Flexi Map, cl_pfn_fmap_cmp_t
253 /****d* Component Library: Flexi Map/cl_pfn_fmap_apply_t
259 * functions used to iterate items in a flexi map.
283 * Flexi Map, cl_fmap_apply_func
286 /****f* Component Library: Flexi Map/cl_fmap_count
292 * in a flexi map.
299 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_count()
300 return (p_map->count); in cl_fmap_count()
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.
327 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_is_fmap_empty()
329 return (p_map->count == 0); in cl_is_fmap_empty()
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.
358 return (p_item->p_key); in cl_fmap_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.
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.
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.
420 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_end()
421 /* Nil is the end of the map. */ in cl_fmap_end()
422 return (&p_map->nil); in cl_fmap_end()
431 * Pointer to the end of the map.
434 * cl_fmap_end is useful for determining the validity of map items returned
436 * map item pointer returned by any of these functions compares to the end,
437 * the end of the map was encoutered.
439 * the map is empty.
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.
458 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_head()
459 return ((cl_fmap_item_t *) p_map->nil.pool_item.list_item.p_next); in cl_fmap_head()
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.
494 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_tail()
495 return ((cl_fmap_item_t *) p_map->nil.pool_item.list_item.p_prev); in cl_fmap_tail()
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.
531 return ((cl_fmap_item_t *) p_item->pool_item.list_item.p_next); in cl_fmap_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
543 * the flexi map.
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.
564 return ((cl_fmap_item_t *) p_item->pool_item.list_item.p_prev); in cl_fmap_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
576 * the flexi map.
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.
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
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_match
627 * The cl_fmap_match function returns the map item matching a key.
641 * [in] Pointer to a key value used to search for the desired map item.
645 * keys of items in the map. Passing NULL here makes such call
649 * Pointer to the map item matching the desired key value.
651 * Pointer to the map end if there was no item matching the desired key
652 * value stored in the flexi map.
655 * Flexi Map, cl_fmap_remove, cl_fmap_get
658 /****f* Component Library: Flexi Map/cl_fmap_get
663 * The cl_fmap_get function returns the map item associated with a key.
676 * [in] Pointer to a key value used to search for the desired map item.
679 * Pointer to the map item with the desired key value.
681 * Pointer to the map end if there was no item with the desired key value
682 * stored in the flexi map.
685 * cl_fmap_get does not remove the item from the flexi map.
688 * Flexi Map, cl_fmap_remove, cl_fmap_get_next
691 /****f* Component Library: Flexi Map/cl_fmap_get_next
696 * The cl_fmap_get_next function returns the first map item associated with
710 * [in] Pointer to a key value used to search for the desired map item.
713 * Pointer to the first map item with a key > the desired key value.
715 * Pointer to the map end if there was no item with a key > the desired key
716 * value stored in the flexi map.
719 * cl_fmap_get_next does not remove the item from the flexi map.
722 * Flexi Map, cl_fmap_remove, cl_fmap_get
725 /****f* Component Library: Flexi Map/cl_fmap_remove_item
730 * The cl_fmap_remove_item function removes the specified map item
731 * from a flexi map.
741 * [in] Pointer to a map item to remove from its flexi map.
747 * removed is in the specified map.
750 * Removes the map item pointed to by p_item from its flexi map.
753 * Flexi Map, cl_fmap_remove, cl_fmap_remove_all, cl_fmap_insert
756 /****f* Component Library: Flexi Map/cl_fmap_remove
761 * The cl_fmap_remove function removes the map item with the specified key
762 * from a flexi map.
775 * [in] Pointer to the key value used to search for the map item
779 * Pointer to the removed map item if it was found.
781 * Pointer to the map end if no item with the specified key exists in the
782 * flexi map.
785 * Flexi Map, cl_fmap_remove_item, cl_fmap_remove_all, cl_fmap_insert
788 /****f* Component Library: Flexi Map/cl_fmap_remove_all
793 * The cl_fmap_remove_all function removes all items in a flexi map,
801 CL_ASSERT(p_map->state == CL_INITIALIZED); in cl_fmap_remove_all()
803 p_map->root.p_left = &p_map->nil; in cl_fmap_remove_all()
804 p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item; in cl_fmap_remove_all()
805 p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item; in cl_fmap_remove_all()
806 p_map->count = 0; in cl_fmap_remove_all()
818 * Flexi Map, cl_fmap_remove, cl_fmap_remove_item
821 /****f* Component Library: Flexi Map/cl_fmap_merge
826 * The cl_fmap_merge function moves all items from one map to another,
849 * Upon return from cl_fmap_merge, the flexi map referenced by p_src_map
853 * Flexi Map, cl_fmap_delta
856 /****f* Component Library: Flexi Map/cl_fmap_delta
901 * Flexi Map, cl_fmap_merge
904 /****f* Component Library: Flexi Map/cl_fmap_apply_func
910 * for every item stored in a flexi map.
924 * [in] Function invoked for every item in the flexi map.
935 * The function provided must not perform any map operations, as these
936 * would corrupt the flexi map.
939 * Flexi Map, cl_pfn_fmap_apply_t