/* BEGIN_ICS_COPYRIGHT6 ****************************************
Copyright (c) 2015-2020, Intel Corporation
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
* Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
* Neither the name of Intel Corporation nor the names of its contributors
may be used to endorse or promote products derived from this software
without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
** END_ICS_COPYRIGHT6 ****************************************/
/* This file incorporates work covered by the following copyright and permission notice */
/*
* Copyright (c) 2004-2006 Voltaire, Inc. All rights reserved.
* Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved.
* Copyright (c) 1996-2003 Intel Corporation. All rights reserved.
*
* This software is available to you under a choice of one of two
* licenses. You may choose to be licensed under the terms of the GNU
* General Public License (GPL) Version 2, available from the file
* COPYING in the main directory of this source tree, or the
* OpenIB.org BSD license below:
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
*
* - Redistributions of source code must retain the above
* copyright notice, this list of conditions and the following
* disclaimer.
*
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
* BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
* ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*
*/
/*
* Abstract:
* Implementation of quick map, a binary tree where the caller always provides
* all necessary storage.
*
* Environment:
* All
*
* $Revision$
*/
/*****************************************************************************
*
* Map
*
* Map is an associative array. By providing a key, the caller can retrieve
* an object from the map. All objects in the map have an associated key,
* as specified by the caller when the object was inserted into the map.
* In addition to random access, the caller can traverse the map much like
* a linked list, either forwards from the first object or backwards from
* the last object. The objects in the map are always traversed in
* order since the nodes are stored sorted.
*
* This implementation of Map uses a red black tree verified against
* Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth
* printing, 1994.
*
*****************************************************************************/
#include <iquickmap.h>
#include <imemory.h>
/******************************************************************************
*******************************************************************************
************** ************
************** IMPLEMENTATION OF QUICK MAP ************
************** ************
*******************************************************************************
******************************************************************************/
/*
* Get the root.
*/
static inline cl_map_item_t*
__cl_map_root(
IN const cl_qmap_t* const p_map )
{
ASSERT( p_map );
return( p_map->root.p_left );
}
/*
* Returns whether a given item is on the left of its parent.
*/
static boolean
__cl_map_is_left_child(
IN const cl_map_item_t* const p_item )
{
ASSERT( p_item );
ASSERT( p_item->p_up );
ASSERT( p_item->p_up != p_item );
return( p_item->p_up->p_left == p_item );
}
/*
* Retrieve the pointer to the parent's pointer to an item.
*/
static cl_map_item_t**
__cl_map_get_parent_ptr_to_item(
IN cl_map_item_t* const p_item )
{
ASSERT( p_item );
ASSERT( p_item->p_up );
ASSERT( p_item->p_up != p_item );
if( __cl_map_is_left_child( p_item ) )
return( &p_item->p_up->p_left );
ASSERT( p_item->p_up->p_right == p_item );
return( &p_item->p_up->p_right );
}
/*
* Rotate a node to the left. This rotation affects the least number of links
* between nodes and brings the level of C up by one while increasing the depth
* of A one. Note that the links to/from W, X, Y, and Z are not affected.
*
* R R
* | |
* A C
* / \ / \
* W C A Z
* / \ / \
* B Z W B
* / \ / \
* X Y X Y
*/
static void
__cl_map_rot_left(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* const p_item )
{
cl_map_item_t **pp_root;
ASSERT( p_map );
ASSERT( p_item );
ASSERT( p_item->p_right != &p_map->nil_item );
pp_root = __cl_map_get_parent_ptr_to_item( p_item );
/* Point R to C instead of A. */
*pp_root = p_item->p_right;
/* Set C's parent to R. */
(*pp_root)->p_up = p_item->p_up;
/* Set A's right to B */
p_item->p_right = (*pp_root)->p_left;
/*
* Set B's parent to A. We trap for B being NIL since the
* caller may depend on NIL not changing.
*/
if( (*pp_root)->p_left != &p_map->nil_item )
(*pp_root)->p_left->p_up = p_item;
/* Set C's left to A. */
(*pp_root)->p_left = p_item;
/* Set A's parent to C. */
p_item->p_up = *pp_root;
}
/*
* Rotate a node to the right. This rotation affects the least number of links
* between nodes and brings the level of A up by one while increasing the depth
* of C one. Note that the links to/from W, X, Y, and Z are not affected.
*
* R R
* | |
* C A
* / \ / \
* A Z W C
* / \ / \
* W B B Z
* / \ / \
* X Y X Y
*/
static void
__cl_map_rot_right(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* const p_item )
{
cl_map_item_t **pp_root;
ASSERT( p_map );
ASSERT( p_item );
ASSERT( p_item->p_left != &p_map->nil_item );
/* Point R to A instead of C. */
pp_root = __cl_map_get_parent_ptr_to_item( p_item );
(*pp_root) = p_item->p_left;
/* Set A's parent to R. */
(*pp_root)->p_up = p_item->p_up;
/* Set C's left to B */
p_item->p_left = (*pp_root)->p_right;
/*
* Set B's parent to C. We trap for B being NIL since the
* caller may depend on NIL not changing.
*/
if( (*pp_root)->p_right != &p_map->nil_item )
(*pp_root)->p_right->p_up = p_item;
/* Set A's right to C. */
(*pp_root)->p_right = p_item;
/* Set C's parent to A. */
p_item->p_up = *pp_root;
}
void
cl_qmap_init(
IN cl_qmap_t* const p_map,
IN cl_pfn_qmap_compare_key_t key_compare)
{
ASSERT( p_map );
MemoryClear( p_map, sizeof(cl_qmap_t) );
/* special setup for the root node */
p_map->root.p_up = &p_map->root;
p_map->root.p_left = &p_map->nil_item;
p_map->root.p_right = &p_map->nil_item;
p_map->root.color = CL_MAP_BLACK;
#if QMAP_DEBUG
p_map->root.p_map = p_map;
#endif
/* Setup the node used as terminator for all leaves. */
p_map->nil_item.p_up = &p_map->nil_item;
p_map->nil_item.p_left = &p_map->nil_item;
p_map->nil_item.p_right = &p_map->nil_item;
p_map->nil_item.color = CL_MAP_BLACK;
#if QMAP_DEBUG
p_map->nil_item.p_map = p_map;
#endif
p_map->state = CL_INITIALIZED;
p_map->key_compare = key_compare;
cl_qmap_remove_all( p_map );
}
cl_map_item_t*
cl_qmap_get(
IN const cl_qmap_t* const p_map,
IN const uint64 key )
{
cl_map_item_t *p_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
p_item = __cl_map_root( p_map );
if (p_map->key_compare == NULL)
{
while( p_item != &p_map->nil_item )
{
if( key == p_item->key )
break; /* just right */
if( key < p_item->key )
p_item = p_item->p_left; /* too small */
else
p_item = p_item->p_right; /* too big */
}
} else {
while( p_item != &p_map->nil_item )
{
int compare_res = (*p_map->key_compare)(p_item->key, key);
if( compare_res == 0 ) /* key == p_item->key */
break; /* just right */
if( compare_res > 0 ) /* p_item->key > key */
p_item = p_item->p_left; /* too small */
else
p_item = p_item->p_right; /* too big */
}
}
return( p_item );
}
cl_map_item_t*
cl_qmap_get_next(
IN const cl_qmap_t* const p_map,
IN const uint64 key )
{
cl_map_item_t *p_item;
cl_map_item_t *p_item_found;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
p_item = __cl_map_root( p_map );
p_item_found = (cl_map_item_t*)&p_map->nil_item;
if (p_map->key_compare == NULL)
{
while( p_item != &p_map->nil_item )
{
if( key < p_item->key ){
p_item_found = p_item;
p_item = p_item->p_left;
}else{
p_item = p_item->p_right;
}
}
} else {
while( p_item != &p_map->nil_item )
{
int compare_res = (*p_map->key_compare)(p_item->key, key);
if( compare_res < 0 ){
p_item_found = p_item;
p_item = p_item->p_left;
}else{
p_item = p_item->p_right;
}
}
}
return( p_item_found );
}
cl_map_item_t*
cl_qmap_get_compare(
IN const cl_qmap_t* const p_map,
IN const uint64 key,
IN cl_pfn_qmap_compare_key_t key_compare)
{
cl_map_item_t *p_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( key_compare != NULL);
p_item = __cl_map_root( p_map );
while( p_item != &p_map->nil_item )
{
int compare_res = (*key_compare)(p_item->key, key);
if( compare_res == 0 ) /* key == p_item->key */
break; /* just right */
if( compare_res > 0 ) /* p_item->key > key */
p_item = p_item->p_left; /* too small */
else
p_item = p_item->p_right; /* too big */
}
return( p_item );
}
cl_map_item_t*
cl_qmap_get_item_compare(
IN const cl_qmap_t* const p_map,
IN const uint64 key,
IN cl_pfn_qmap_item_compare_t compare)
{
cl_map_item_t *p_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( compare != NULL);
p_item = __cl_map_root( p_map );
while( p_item != &p_map->nil_item )
{
int compare_res = (*compare)(p_item, key);
if( compare_res == 0 ) /* key == p_item->key */
break; /* just right */
if( compare_res > 0 ) /* p_item->key > key */
p_item = p_item->p_left; /* too small */
else
p_item = p_item->p_right; /* too big */
}
return( p_item );
}
void
cl_qmap_apply_func(
IN const cl_qmap_t* const p_map,
IN cl_pfn_qmap_apply_t pfn_func,
IN const void* const context )
{
cl_map_item_t* p_map_item;
/* Note that context can have any arbitrary value. */
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( pfn_func );
p_map_item = cl_qmap_head( p_map );
while( p_map_item != cl_qmap_end( p_map ) )
{
pfn_func( p_map_item, (void*)context );
p_map_item = cl_qmap_next( p_map_item );
}
}
/*
* Balance a tree starting at a given item back to the root.
*/
static void
__cl_map_ins_bal(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* p_item )
{
cl_map_item_t* p_grand_uncle;
ASSERT( p_map );
ASSERT( p_item );
ASSERT( p_item != &p_map->root );
while( p_item->p_up->color == CL_MAP_RED )
{
if( __cl_map_is_left_child( p_item->p_up ) )
{
p_grand_uncle = p_item->p_up->p_up->p_right;
ASSERT( p_grand_uncle );
if( p_grand_uncle->color == CL_MAP_RED )
{
p_grand_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
p_item = p_item->p_up->p_up;
continue;
}
if( !__cl_map_is_left_child( p_item ) )
{
p_item = p_item->p_up;
__cl_map_rot_left( p_map, p_item );
}
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
__cl_map_rot_right( p_map, p_item->p_up->p_up );
}
else
{
p_grand_uncle = p_item->p_up->p_up->p_left;
ASSERT( p_grand_uncle );
if( p_grand_uncle->color == CL_MAP_RED )
{
p_grand_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
p_item = p_item->p_up->p_up;
continue;
}
if( __cl_map_is_left_child( p_item ) )
{
p_item = p_item->p_up;
__cl_map_rot_right( p_map, p_item );
}
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
__cl_map_rot_left( p_map, p_item->p_up->p_up );
}
}
}
cl_map_item_t*
cl_qmap_insert(
IN cl_qmap_t* const p_map,
IN const uint64 key,
IN cl_map_item_t* const p_item )
{
cl_map_item_t *p_insert_at, *p_comp_item;
int compare_res = 0;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( p_item );
ASSERT( p_map->root.p_up == &p_map->root );
ASSERT( p_map->root.color != CL_MAP_RED );
ASSERT( p_map->nil_item.color != CL_MAP_RED );
/* Find the insertion location. */
p_insert_at = &p_map->root;
p_comp_item = __cl_map_root( p_map );
if (p_map->key_compare == NULL)
{
while( p_comp_item != &p_map->nil_item )
{
p_insert_at = p_comp_item;
if( key == p_insert_at->key )
return( p_insert_at );
/* Traverse the tree until the correct insertion point is found. */
if( key < p_insert_at->key )
{
p_comp_item = p_insert_at->p_left;
compare_res = 1;
} else {
p_comp_item = p_insert_at->p_right;
compare_res = -1;
}
}
} else {
while( p_comp_item != &p_map->nil_item )
{
p_insert_at = p_comp_item;
compare_res = (*p_map->key_compare)(p_insert_at->key, key);
if( compare_res == 0 ) /* key == p_insert_at->key */
return( p_insert_at );
/* Traverse the tree until the correct insertion point is found. */
if( compare_res > 0 ) /* p_insert_at->key > key */
p_comp_item = p_insert_at->p_left;
else
p_comp_item = p_insert_at->p_right;
}
}
ASSERT( p_insert_at != &p_map->nil_item );
ASSERT( p_comp_item == &p_map->nil_item );
/* Insert the item. */
p_item->p_left = &p_map->nil_item;
p_item->p_right = &p_map->nil_item;
p_item->key = key;
p_item->color = CL_MAP_RED;
if( p_insert_at == &p_map->root )
{
p_insert_at->p_left = p_item;
/*
* Primitive insert places the new item in front of
* the existing item.
*/
__cl_primitive_insert( &p_map->nil_item.pool_item.list_item,
&p_item->pool_item.list_item );
}
else if( compare_res > 0 ) /* key < p_insert_at->key */
{
p_insert_at->p_left = p_item;
/*
* Primitive insert places the new item in front of
* the existing item.
*/
__cl_primitive_insert( &p_insert_at->pool_item.list_item,
&p_item->pool_item.list_item );
}
else
{
p_insert_at->p_right = p_item;
/*
* Primitive insert places the new item in front of
* the existing item.
*/
__cl_primitive_insert( p_insert_at->pool_item.list_item.p_next,
&p_item->pool_item.list_item );
}
/* Increase the count. */
p_map->count++;
p_item->p_up = p_insert_at;
/*
* We have added depth to this section of the tree.
* Rebalance as necessary as we retrace our path through the tree
* and update colors.
*/
__cl_map_ins_bal( p_map, p_item );
__cl_map_root( p_map )->color = CL_MAP_BLACK;
/*
* Note that it is not necessary to re-color the nil node black because all
* red color assignments are made via the p_up pointer, and nil is never
* set as the value of a p_up pointer.
*/
#if QMAP_DEBUG
/* Set the pointer to the map in the map item for consistency checking. */
p_item->p_map = p_map;
#endif
return( p_item );
}
static void
__cl_map_del_bal(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* p_item )
{
cl_map_item_t *p_uncle;
while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )
{
if( __cl_map_is_left_child( p_item ) )
{
p_uncle = p_item->p_up->p_right;
if( p_uncle->color == CL_MAP_RED )
{
p_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_RED;
__cl_map_rot_left( p_map, p_item->p_up );
p_uncle = p_item->p_up->p_right;
}
if( p_uncle->p_right->color != CL_MAP_RED )
{
if( p_uncle->p_left->color != CL_MAP_RED )
{
p_uncle->color = CL_MAP_RED;
p_item = p_item->p_up;
continue;
}
p_uncle->p_left->color = CL_MAP_BLACK;
p_uncle->color = CL_MAP_RED;
__cl_map_rot_right( p_map, p_uncle );
p_uncle = p_item->p_up->p_right;
}
p_uncle->color = p_item->p_up->color;
p_item->p_up->color = CL_MAP_BLACK;
p_uncle->p_right->color = CL_MAP_BLACK;
__cl_map_rot_left( p_map, p_item->p_up );
break;
}
else
{
p_uncle = p_item->p_up->p_left;
if( p_uncle->color == CL_MAP_RED )
{
p_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_RED;
__cl_map_rot_right( p_map, p_item->p_up );
p_uncle = p_item->p_up->p_left;
}
if( p_uncle->p_left->color != CL_MAP_RED )
{
if( p_uncle->p_right->color != CL_MAP_RED )
{
p_uncle->color = CL_MAP_RED;
p_item = p_item->p_up;
continue;
}
p_uncle->p_right->color = CL_MAP_BLACK;
p_uncle->color = CL_MAP_RED;
__cl_map_rot_left( p_map, p_uncle );
p_uncle = p_item->p_up->p_left;
}
p_uncle->color = p_item->p_up->color;
p_item->p_up->color = CL_MAP_BLACK;
p_uncle->p_left->color = CL_MAP_BLACK;
__cl_map_rot_right( p_map, p_item->p_up );
break;
}
}
p_item->color = CL_MAP_BLACK;
}
void
cl_qmap_remove_item(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* const p_item )
{
cl_map_item_t *p_child, *p_del_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( p_item );
#if QMAP_DEBUG
ASSERT( p_item->p_map == p_map );
#endif
if( p_item == cl_qmap_end( p_map ) )
return;
if( (p_item->p_right == &p_map->nil_item) || (p_item->p_left == &p_map->nil_item ) )
{
/* The item being removed has children on at most on side. */
p_del_item = p_item;
}
else
{
/*
* The item being removed has children on both side.
* We select the item that will replace it. After removing
* the substitute item and rebalancing, the tree will have the
* correct topology. Exchanging the substitute for the item
* will finalize the removal.
*/
p_del_item = cl_qmap_next( p_item );
ASSERT( p_del_item != &p_map->nil_item );
}
/* Remove the item from the list. */
__cl_primitive_remove( &p_item->pool_item.list_item );
/* Decrement the item count. */
p_map->count--;
/* Get the pointer to the new root's child, if any. */
if( p_del_item->p_left != &p_map->nil_item )
p_child = p_del_item->p_left;
else
p_child = p_del_item->p_right;
/*
* This assignment may modify the parent pointer of the nil node.
* This is inconsequential.
*/
p_child->p_up = p_del_item->p_up;
(*__cl_map_get_parent_ptr_to_item( p_del_item )) = p_child;
if( p_del_item->color != CL_MAP_RED )
__cl_map_del_bal( p_map, p_child );
/*
* Note that the splicing done below does not need to occur before
* the tree is balanced, since the actual topology changes are made by the
* preceding code. The topology is preserved by the color assignment made
* below (reader should be reminded that p_del_item == p_item in some cases).
*/
if( p_del_item != p_item )
{
/*
* Finalize the removal of the specified item by exchanging it with
* the substitute which we removed above.
*/
p_del_item->p_up = p_item->p_up;
p_del_item->p_left = p_item->p_left;
p_del_item->p_right = p_item->p_right;
(*__cl_map_get_parent_ptr_to_item( p_item )) = p_del_item;
p_item->p_right->p_up = p_del_item;
p_item->p_left->p_up = p_del_item;
p_del_item->color = p_item->color;
}
ASSERT( p_map->nil_item.color != CL_MAP_RED );
#if QMAP_DEBUG
/* Clear the pointer to the map since the item has been removed. */
p_item->p_map = NULL;
#endif
}
cl_map_item_t*
cl_qmap_remove(
IN cl_qmap_t* const p_map,
IN const uint64 key )
{
cl_map_item_t *p_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
/* Seek the node with the specified key */
p_item = cl_qmap_get( p_map, key );
cl_qmap_remove_item( p_map, p_item );
return( p_item );
}
cl_map_item_t*
cl_qmap_remove_compare(
IN cl_qmap_t* const p_map,
IN const uint64 key,
IN cl_pfn_qmap_compare_key_t key_compare)
{
cl_map_item_t *p_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
/* Seek the node with the specified key */
p_item = cl_qmap_get_compare( p_map, key, key_compare );
cl_qmap_remove_item( p_map, p_item );
return( p_item );
}
void
cl_qmap_merge(
OUT cl_qmap_t* const p_dest_map,
IN OUT cl_qmap_t* const p_src_map )
{
cl_map_item_t *p_item, *p_item2, *p_next;
ASSERT( p_dest_map );
ASSERT( p_src_map );
ASSERT( p_src_map->key_compare == p_dest_map->key_compare );
p_item = cl_qmap_head( p_src_map );
while( p_item != cl_qmap_end( p_src_map ) )
{
p_next = cl_qmap_next( p_item );
/* Remove the item from its current map. */
cl_qmap_remove_item( p_src_map, p_item );
/* Insert the item into the destination map. */
p_item2 = cl_qmap_insert( p_dest_map, cl_qmap_key( p_item ), p_item );
/* Check that the item was successfully inserted. */
if( p_item2 != p_item )
{
/* Put the item in back in the source map. */
p_item2 =
cl_qmap_insert( p_src_map, cl_qmap_key( p_item ), p_item );
ASSERT( p_item2 == p_item );
}
p_item = p_next;
}
}
static void
__cl_qmap_delta_move(
IN OUT cl_qmap_t* const p_dest,
IN OUT cl_qmap_t* const p_src,
IN OUT cl_map_item_t** const pp_item )
{
cl_map_item_t *p_temp, *p_next;
/*
* Get the next item so that we can ensure that pp_item points to
* a valid item upon return from the function.
*/
p_next = cl_qmap_next( *pp_item );
/* Move the old item from its current map the the old map. */
cl_qmap_remove_item( p_src, *pp_item );
p_temp = cl_qmap_insert( p_dest, cl_qmap_key( *pp_item ), *pp_item );
/* We should never have duplicates. */
ASSERT( p_temp == *pp_item );
/* Point pp_item to a valid item in the source map. */
(*pp_item) = p_next;
}
void
cl_qmap_delta(
IN OUT cl_qmap_t* const p_map1,
IN OUT cl_qmap_t* const p_map2,
OUT cl_qmap_t* const p_new,
OUT cl_qmap_t* const p_old )
{
cl_map_item_t *p_item1, *p_item2;
uint64 key1, key2;
ASSERT( p_map1 );
ASSERT( p_map2 );
ASSERT( p_new );
ASSERT( p_old );
ASSERT( cl_is_qmap_empty( p_new ) );
ASSERT( cl_is_qmap_empty( p_old ) );
ASSERT( p_map1->key_compare == p_map1->key_compare );
p_item1 = cl_qmap_head( p_map1 );
p_item2 = cl_qmap_head( p_map2 );
while( p_item1 != cl_qmap_end( p_map1 ) &&
p_item2 != cl_qmap_end( p_map2 ) )
{
key1 = cl_qmap_key( p_item1 );
key2 = cl_qmap_key( p_item2 );
if( key1 < key2 )
{
/* We found an old item. */
__cl_qmap_delta_move( p_old, p_map1, &p_item1 );
}
else if( key1 > key2 )
{
/* We found a new item. */
__cl_qmap_delta_move( p_new, p_map2, &p_item2 );
}
else
{
/* Move both forward since they have the same key. */
p_item1 = cl_qmap_next( p_item1 );
p_item2 = cl_qmap_next( p_item2 );
}
}
/* Process the remainder if the end of either source map was reached. */
while( p_item2 != cl_qmap_end( p_map2 ) )
__cl_qmap_delta_move( p_new, p_map2, &p_item2 );
while( p_item1 != cl_qmap_end( p_map1 ) )
__cl_qmap_delta_move( p_old, p_map1, &p_item1 );
}
/******************************************************************************
*******************************************************************************
************** ************
************** IMPLEMENTATION OF MAP ************
************** ************
*******************************************************************************
******************************************************************************/
#if 0
#define MAP_GROW_SIZE 32
void
cl_map_construct(
IN cl_map_t* const p_map )
{
ASSERT( p_map );
cl_qpool_construct( &p_map->pool );
}
cl_status_t
cl_map_init(
IN cl_map_t* const p_map,
IN const size_t min_items )
{
size_t grow_size;
ASSERT( p_map );
cl_qmap_init( &p_map->qmap );
/*
* We will grow by min_items/8 items at a time, with a minimum of
* MAP_GROW_SIZE.
*/
grow_size = min_items >> 3;
if( grow_size < MAP_GROW_SIZE )
grow_size = MAP_GROW_SIZE;
return( cl_qpool_init( &p_map->pool, min_items, 0, grow_size,
sizeof(cl_map_obj_t), NULL, NULL, NULL ) );
}
void
cl_map_destroy(
IN cl_map_t* const p_map )
{
ASSERT( p_map );
cl_qpool_destroy( &p_map->pool );
}
void*
cl_map_insert(
IN cl_map_t* const p_map,
IN const uint64 key,
IN const void* const p_object )
{
cl_map_obj_t *p_map_obj, *p_obj_at_key;
ASSERT( p_map );
p_map_obj = (cl_map_obj_t*)cl_qpool_get( &p_map->pool );
if( !p_map_obj )
return( NULL );
cl_qmap_set_obj( p_map_obj, p_object );
p_obj_at_key =
(cl_map_obj_t*)cl_qmap_insert( &p_map->qmap, key, &p_map_obj->item );
/* Return the item to the pool if insertion failed. */
if( p_obj_at_key != p_map_obj )
cl_qpool_put( &p_map->pool, &p_map_obj->item.pool_item );
return( cl_qmap_obj( p_obj_at_key ) );
}
void*
cl_map_get(
IN const cl_map_t* const p_map,
IN const uint64 key )
{
cl_map_item_t *p_item;
ASSERT( p_map );
p_item = cl_qmap_get( &p_map->qmap, key );
if( p_item == cl_qmap_end( &p_map->qmap ) )
return( NULL );
return( cl_qmap_obj( PARENT_STRUCT( p_item, cl_map_obj_t, item ) ) );
}
void
cl_map_remove_item(
IN cl_map_t* const p_map,
IN const cl_map_iterator_t itor )
{
ASSERT( itor->p_map == &p_map->qmap );
if( itor == cl_map_end( p_map ) )
return;
cl_qmap_remove_item( &p_map->qmap, (cl_map_item_t*)itor );
cl_qpool_put( &p_map->pool, &((cl_map_item_t*)itor)->pool_item );
}
void*
cl_map_remove(
IN cl_map_t* const p_map,
IN const uint64 key )
{
cl_map_item_t *p_item;
ASSERT( p_map );
p_item = cl_qmap_remove( &p_map->qmap, key );
if( p_item == cl_qmap_end( &p_map->qmap ) )
return( NULL );
cl_qpool_put( &p_map->pool, &p_item->pool_item );
return( cl_qmap_obj( (cl_map_obj_t*)p_item ) );
}
void
cl_map_remove_all(
IN cl_map_t* const p_map )
{
cl_map_item_t *p_item;
ASSERT( p_map );
/* Return all map items to the pool. */
while( !cl_is_qmap_empty( &p_map->qmap ) )
{
p_item = cl_qmap_head( &p_map->qmap );
cl_qmap_remove_item( &p_map->qmap, p_item );
cl_qpool_put( &p_map->pool, &p_item->pool_item );
if( !cl_is_qmap_empty( &p_map->qmap ) )
{
p_item = cl_qmap_tail( &p_map->qmap );
cl_qmap_remove_item( &p_map->qmap, p_item );
cl_qpool_put( &p_map->pool, &p_item->pool_item );
}
}
}
cl_status_t
cl_map_merge(
OUT cl_map_t* const p_dest_map,
IN OUT cl_map_t* const p_src_map )
{
cl_status_t status = CL_SUCCESS;
cl_map_iterator_t itor, next;
uint64 key;
void *p_obj, *p_obj2;
ASSERT( p_dest_map );
ASSERT( p_src_map );
itor = cl_map_head( p_src_map );
while( itor != cl_map_end( p_src_map ) )
{
next = cl_map_next( itor );
p_obj = cl_map_obj( itor );
key = cl_map_key( itor );
cl_map_remove_item( p_src_map, itor );
/* Insert the object into the destination map. */
p_obj2 = cl_map_insert( p_dest_map, key, p_obj );
/* Trap for failure. */
if( p_obj != p_obj2 )
{
if( !p_obj2 )
status = CL_INSUFFICIENT_MEMORY;
/* Put the object back in the source map. This must succeed. */
p_obj2 = cl_map_insert( p_src_map, key, p_obj );
ASSERT( p_obj == p_obj2 );
/* If the failure was due to insufficient memory, return. */
if( status != CL_SUCCESS )
return( status );
}
itor = next;
}
return( CL_SUCCESS );
}
static void
__cl_map_revert(
IN OUT cl_map_t* const p_map1,
IN OUT cl_map_t* const p_map2,
IN OUT cl_map_t* const p_new,
IN OUT cl_map_t* const p_old )
{
cl_status_t status;
/* Restore the initial state. */
status = cl_map_merge( p_map1, p_old );
ASSERT( status == CL_SUCCESS );
status = cl_map_merge( p_map2, p_new );
ASSERT( status == CL_SUCCESS );
}
static cl_status_t
__cl_map_delta_move(
OUT cl_map_t* const p_dest,
IN OUT cl_map_t* const p_src,
IN OUT cl_map_iterator_t* const p_itor )
{
cl_map_iterator_t next;
void *p_obj, *p_obj2;
uint64 key;
/* Get a valid iterator so we can continue the loop. */
next = cl_map_next( *p_itor );
/* Get the pointer to the object for insertion. */
p_obj = cl_map_obj( *p_itor );
/* Get the key for the object. */
key = cl_map_key( *p_itor );
/* Move the object. */
cl_map_remove_item( p_src, *p_itor );
p_obj2 = cl_map_insert( p_dest, key, p_obj );
/* Check for failure. We should never get a duplicate. */
if( !p_obj2 )
{
p_obj2 = cl_map_insert( p_src, key, p_obj );
ASSERT( p_obj2 == p_obj );
return( CL_INSUFFICIENT_MEMORY );
}
/* We should never get a duplicate */
ASSERT( p_obj == p_obj2 );
/* Update the iterator so that it is valid. */
(*p_itor) = next;
return( CL_SUCCESS );
}
cl_status_t
cl_map_delta(
IN OUT cl_map_t* const p_map1,
IN OUT cl_map_t* const p_map2,
OUT cl_map_t* const p_new,
OUT cl_map_t* const p_old )
{
cl_map_iterator_t itor1, itor2;
uint64 key1, key2;
cl_status_t status;
ASSERT( p_map1 );
ASSERT( p_map2 );
ASSERT( p_new );
ASSERT( p_old );
ASSERT( cl_is_map_empty( p_new ) );
ASSERT( cl_is_map_empty( p_old ) );
itor1 = cl_map_head( p_map1 );
itor2 = cl_map_head( p_map2 );
/*
* Note that the check is for the end, since duplicate items will remain
* in their respective maps.
*/
while( itor1 != cl_map_end( p_map1 ) &&
itor2 != cl_map_end( p_map2 ) )
{
key1 = cl_map_key( itor1 );
key2 = cl_map_key( itor2 );
if( key1 < key2 )
{
status = __cl_map_delta_move( p_old, p_map1, &itor1 );
/* Check for failure. */
if( status != CL_SUCCESS )
{
/* Restore the initial state. */
__cl_map_revert( p_map1, p_map2, p_new, p_old );
/* Return the failure status. */
return( status );
}
}
else if( key1 > key2 )
{
status = __cl_map_delta_move( p_new, p_map2, &itor2 );
if( status != CL_SUCCESS )
{
/* Restore the initial state. */
__cl_map_revert( p_map1, p_map2, p_new, p_old );
/* Return the failure status. */
return( status );
}
}
else
{
/* Move both forward since they have the same key. */
itor1 = cl_map_next( itor1 );
itor2 = cl_map_next( itor2 );
}
}
/* Process the remainder if either source map is empty. */
while( itor2 != cl_map_end( p_map2 ) )
{
status = __cl_map_delta_move( p_new, p_map2, &itor2 );
if( status != CL_SUCCESS )
{
/* Restore the initial state. */
__cl_map_revert( p_map1, p_map2, p_new, p_old );
/* Return the failure status. */
return( status );
}
}
while( itor1 != cl_map_end( p_map1 ) )
{
status = __cl_map_delta_move( p_old, p_map1, &itor1 );
if( status != CL_SUCCESS )
{
/* Restore the initial state. */
__cl_map_revert( p_map1, p_map2, p_new, p_old );
/* Return the failure status. */
return( status );
}
}
return( CL_SUCCESS );
}
/******************************************************************************
*******************************************************************************
************** ************
************** IMPLEMENTATION OF FLEXI MAP ************
************** ************
*******************************************************************************
******************************************************************************/
/*
* Get the root.
*/
static inline cl_fmap_item_t*
__cl_fmap_root(
IN const cl_fmap_t* const p_map )
{
ASSERT( p_map );
return( p_map->root.p_left );
}
/*
* Returns whether a given item is on the left of its parent.
*/
static boolean
__cl_fmap_is_left_child(
IN const cl_fmap_item_t* const p_item )
{
ASSERT( p_item );
ASSERT( p_item->p_up );
ASSERT( p_item->p_up != p_item );
return( p_item->p_up->p_left == p_item );
}
/*
* Retrieve the pointer to the parent's pointer to an item.
*/
static cl_fmap_item_t**
__cl_fmap_get_parent_ptr_to_item(
IN cl_fmap_item_t* const p_item )
{
ASSERT( p_item );
ASSERT( p_item->p_up );
ASSERT( p_item->p_up != p_item );
if( __cl_fmap_is_left_child( p_item ) )
return( &p_item->p_up->p_left );
ASSERT( p_item->p_up->p_right == p_item );
return( &p_item->p_up->p_right );
}
/*
* Rotate a node to the left. This rotation affects the least number of links
* between nodes and brings the level of C up by one while increasing the depth
* of A one. Note that the links to/from W, X, Y, and Z are not affected.
*
* R R
* | |
* A C
* / \ / \
* W C A Z
* / \ / \
* B Z W B
* / \ / \
* X Y X Y
*/
static void
__cl_fmap_rot_left(
IN cl_fmap_t* const p_map,
IN cl_fmap_item_t* const p_item )
{
cl_fmap_item_t **pp_root;
ASSERT( p_map );
ASSERT( p_item );
ASSERT( p_item->p_right != &p_map->nil_item );
pp_root = __cl_fmap_get_parent_ptr_to_item( p_item );
/* Point R to C instead of A. */
*pp_root = p_item->p_right;
/* Set C's parent to R. */
(*pp_root)->p_up = p_item->p_up;
/* Set A's right to B */
p_item->p_right = (*pp_root)->p_left;
/*
* Set B's parent to A. We trap for B being NIL since the
* caller may depend on NIL not changing.
*/
if( (*pp_root)->p_left != &p_map->nil_item )
(*pp_root)->p_left->p_up = p_item;
/* Set C's left to A. */
(*pp_root)->p_left = p_item;
/* Set A's parent to C. */
p_item->p_up = *pp_root;
}
/*
* Rotate a node to the right. This rotation affects the least number of links
* between nodes and brings the level of A up by one while increasing the depth
* of C one. Note that the links to/from W, X, Y, and Z are not affected.
*
* R R
* | |
* C A
* / \ / \
* A Z W C
* / \ / \
* W B B Z
* / \ / \
* X Y X Y
*/
static void
__cl_fmap_rot_right(
IN cl_fmap_t* const p_map,
IN cl_fmap_item_t* const p_item )
{
cl_fmap_item_t **pp_root;
ASSERT( p_map );
ASSERT( p_item );
ASSERT( p_item->p_left != &p_map->nil_item );
/* Point R to A instead of C. */
pp_root = __cl_fmap_get_parent_ptr_to_item( p_item );
(*pp_root) = p_item->p_left;
/* Set A's parent to R. */
(*pp_root)->p_up = p_item->p_up;
/* Set C's left to B */
p_item->p_left = (*pp_root)->p_right;
/*
* Set B's parent to C. We trap for B being NIL since the
* caller may depend on NIL not changing.
*/
if( (*pp_root)->p_right != &p_map->nil_item )
(*pp_root)->p_right->p_up = p_item;
/* Set A's right to C. */
(*pp_root)->p_right = p_item;
/* Set C's parent to A. */
p_item->p_up = *pp_root;
}
void
cl_fmap_init(
IN cl_fmap_t* const p_map,
IN cl_pfn_fmap_cmp_t pfn_compare )
{
ASSERT( p_map );
ASSERT( pfn_compare );
MemoryClear( p_map, sizeof(cl_fmap_t) );
/* special setup for the root node */
p_map->root.p_up = &p_map->root;
p_map->root.p_left = &p_map->nil_item;
p_map->root.p_right = &p_map->nil_item;
p_map->root.color = CL_MAP_BLACK;
#if QMAP_DEBUG
p_map->root.p_map = p_map;
#endif
/* Setup the node used as terminator for all leaves. */
p_map->nil_item.p_up = &p_map->nil_item;
p_map->nil_item.p_left = &p_map->nil_item;
p_map->nil_item.p_right = &p_map->nil_item;
p_map->nil_item.color = CL_MAP_BLACK;
#if QMAP_DEBUG
p_map->nil_item.p_map = p_map;
#endif
/* Store the compare function pointer. */
p_map->pfn_compare = pfn_compare;
p_map->state = CL_INITIALIZED;
cl_fmap_remove_all( p_map );
}
cl_fmap_item_t*
cl_fmap_get(
IN const cl_fmap_t* const p_map,
IN const void* const p_key )
{
cl_fmap_item_t *p_item;
intn_t cmp;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
p_item = __cl_fmap_root( p_map );
while( p_item != &p_map->nil_item )
{
cmp = p_map->pfn_compare( p_key, p_item->p_key );
if( !cmp )
break; /* just right */
if( cmp < 0 )
p_item = p_item->p_left; /* too small */
else
p_item = p_item->p_right; /* too big */
}
return( p_item );
}
void
cl_fmap_apply_func(
IN const cl_fmap_t* const p_map,
IN cl_pfn_fmap_apply_t pfn_func,
IN const void* const context )
{
cl_fmap_item_t* p_fmap_item;
/* Note that context can have any arbitrary value. */
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( pfn_func );
p_fmap_item = cl_fmap_head( p_map );
while( p_fmap_item != cl_fmap_end( p_map ) )
{
pfn_func( p_fmap_item, (void*)context );
p_fmap_item = cl_fmap_next( p_fmap_item );
}
}
/*
* Balance a tree starting at a given item back to the root.
*/
static void
__cl_fmap_ins_bal(
IN cl_fmap_t* const p_map,
IN cl_fmap_item_t* p_item )
{
cl_fmap_item_t* p_grand_uncle;
ASSERT( p_map );
ASSERT( p_item );
ASSERT( p_item != &p_map->root );
while( p_item->p_up->color == CL_MAP_RED )
{
if( __cl_fmap_is_left_child( p_item->p_up ) )
{
p_grand_uncle = p_item->p_up->p_up->p_right;
ASSERT( p_grand_uncle );
if( p_grand_uncle->color == CL_MAP_RED )
{
p_grand_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
p_item = p_item->p_up->p_up;
continue;
}
if( !__cl_fmap_is_left_child( p_item ) )
{
p_item = p_item->p_up;
__cl_fmap_rot_left( p_map, p_item );
}
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
__cl_fmap_rot_right( p_map, p_item->p_up->p_up );
}
else
{
p_grand_uncle = p_item->p_up->p_up->p_left;
ASSERT( p_grand_uncle );
if( p_grand_uncle->color == CL_MAP_RED )
{
p_grand_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
p_item = p_item->p_up->p_up;
continue;
}
if( __cl_fmap_is_left_child( p_item ) )
{
p_item = p_item->p_up;
__cl_fmap_rot_right( p_map, p_item );
}
p_item->p_up->color = CL_MAP_BLACK;
p_item->p_up->p_up->color = CL_MAP_RED;
__cl_fmap_rot_left( p_map, p_item->p_up->p_up );
}
}
}
cl_fmap_item_t*
cl_fmap_insert(
IN cl_fmap_t* const p_map,
IN const void* const p_key,
IN cl_fmap_item_t* const p_item )
{
cl_fmap_item_t *p_insert_at, *p_comp_item;
intn_t cmp = 0;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( p_item );
ASSERT( p_map->root.p_up == &p_map->root );
ASSERT( p_map->root.color != CL_MAP_RED );
ASSERT( p_map->nil_item.color != CL_MAP_RED );
p_item->p_left = &p_map->nil_item;
p_item->p_right = &p_map->nil_item;
p_item->p_key = p_key;
p_item->color = CL_MAP_RED;
/* Find the insertion location. */
p_insert_at = &p_map->root;
p_comp_item = __cl_fmap_root( p_map );
while( p_comp_item != &p_map->nil_item )
{
p_insert_at = p_comp_item;
cmp = p_map->pfn_compare( p_key, p_insert_at->p_key );
if( !cmp )
return( p_insert_at );
/* Traverse the tree until the correct insertion point is found. */
if( cmp < 0 )
p_comp_item = p_insert_at->p_left;
else
p_comp_item = p_insert_at->p_right;
}
ASSERT( p_insert_at != &p_map->nil_item );
ASSERT( p_comp_item == &p_map->nil_item );
/* Insert the item. */
if( p_insert_at == &p_map->root )
{
p_insert_at->p_left = p_item;
/*
* Primitive insert places the new item in front of
* the existing item.
*/
__cl_primitive_insert( &p_map->nil_item.pool_item.list_item,
&p_item->pool_item.list_item );
}
else if( cmp < 0 )
{
p_insert_at->p_left = p_item;
/*
* Primitive insert places the new item in front of
* the existing item.
*/
__cl_primitive_insert( &p_insert_at->pool_item.list_item,
&p_item->pool_item.list_item );
}
else
{
p_insert_at->p_right = p_item;
/*
* Primitive insert places the new item in front of
* the existing item.
*/
__cl_primitive_insert( p_insert_at->pool_item.list_item.p_next,
&p_item->pool_item.list_item );
}
/* Increase the count. */
p_map->count++;
p_item->p_up = p_insert_at;
/*
* We have added depth to this section of the tree.
* Rebalance as necessary as we retrace our path through the tree
* and update colors.
*/
__cl_fmap_ins_bal( p_map, p_item );
__cl_fmap_root( p_map )->color = CL_MAP_BLACK;
/*
* Note that it is not necessary to re-color the nil node black because all
* red color assignments are made via the p_up pointer, and nil is never
* set as the value of a p_up pointer.
*/
#if QMAP_DEBUG
/* Set the pointer to the map in the map item for consistency checking. */
p_item->p_map = p_map;
#endif
return( p_item );
}
static void
__cl_fmap_del_bal(
IN cl_fmap_t* const p_map,
IN cl_fmap_item_t* p_item )
{
cl_fmap_item_t *p_uncle;
while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )
{
if( __cl_fmap_is_left_child( p_item ) )
{
p_uncle = p_item->p_up->p_right;
if( p_uncle->color == CL_MAP_RED )
{
p_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_RED;
__cl_fmap_rot_left( p_map, p_item->p_up );
p_uncle = p_item->p_up->p_right;
}
if( p_uncle->p_right->color != CL_MAP_RED )
{
if( p_uncle->p_left->color != CL_MAP_RED )
{
p_uncle->color = CL_MAP_RED;
p_item = p_item->p_up;
continue;
}
p_uncle->p_left->color = CL_MAP_BLACK;
p_uncle->color = CL_MAP_RED;
__cl_fmap_rot_right( p_map, p_uncle );
p_uncle = p_item->p_up->p_right;
}
p_uncle->color = p_item->p_up->color;
p_item->p_up->color = CL_MAP_BLACK;
p_uncle->p_right->color = CL_MAP_BLACK;
__cl_fmap_rot_left( p_map, p_item->p_up );
break;
}
else
{
p_uncle = p_item->p_up->p_left;
if( p_uncle->color == CL_MAP_RED )
{
p_uncle->color = CL_MAP_BLACK;
p_item->p_up->color = CL_MAP_RED;
__cl_fmap_rot_right( p_map, p_item->p_up );
p_uncle = p_item->p_up->p_left;
}
if( p_uncle->p_left->color != CL_MAP_RED )
{
if( p_uncle->p_right->color != CL_MAP_RED )
{
p_uncle->color = CL_MAP_RED;
p_item = p_item->p_up;
continue;
}
p_uncle->p_right->color = CL_MAP_BLACK;
p_uncle->color = CL_MAP_RED;
__cl_fmap_rot_left( p_map, p_uncle );
p_uncle = p_item->p_up->p_left;
}
p_uncle->color = p_item->p_up->color;
p_item->p_up->color = CL_MAP_BLACK;
p_uncle->p_left->color = CL_MAP_BLACK;
__cl_fmap_rot_right( p_map, p_item->p_up );
break;
}
}
p_item->color = CL_MAP_BLACK;
}
void
cl_fmap_remove_item(
IN cl_fmap_t* const p_map,
IN cl_fmap_item_t* const p_item )
{
cl_fmap_item_t *p_child, *p_del_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
ASSERT( p_item );
#if QMAP_DEBUG
ASSERT( p_item->p_map == p_map );
#endif
if( p_item == cl_fmap_end( p_map ) )
return;
if( (p_item->p_right == &p_map->nil_item) || (p_item->p_left == &p_map->nil_item ) )
{
/* The item being removed has children on at most on side. */
p_del_item = p_item;
}
else
{
/*
* The item being removed has children on both side.
* We select the item that will replace it. After removing
* the substitute item and rebalancing, the tree will have the
* correct topology. Exchanging the substitute for the item
* will finalize the removal.
*/
p_del_item = cl_fmap_next( p_item );
ASSERT( p_del_item != &p_map->nil_item );
}
/* Remove the item from the list. */
__cl_primitive_remove( &p_item->pool_item.list_item );
/* Decrement the item count. */
p_map->count--;
/* Get the pointer to the new root's child, if any. */
if( p_del_item->p_left != &p_map->nil_item )
p_child = p_del_item->p_left;
else
p_child = p_del_item->p_right;
/*
* This assignment may modify the parent pointer of the nil node.
* This is inconsequential.
*/
p_child->p_up = p_del_item->p_up;
(*__cl_fmap_get_parent_ptr_to_item( p_del_item )) = p_child;
if( p_del_item->color != CL_MAP_RED )
__cl_fmap_del_bal( p_map, p_child );
/*
* Note that the splicing done below does not need to occur before
* the tree is balanced, since the actual topology changes are made by the
* preceding code. The topology is preserved by the color assignment made
* below (reader should be reminded that p_del_item == p_item in some cases).
*/
if( p_del_item != p_item )
{
/*
* Finalize the removal of the specified item by exchanging it with
* the substitute which we removed above.
*/
p_del_item->p_up = p_item->p_up;
p_del_item->p_left = p_item->p_left;
p_del_item->p_right = p_item->p_right;
(*__cl_fmap_get_parent_ptr_to_item( p_item )) = p_del_item;
p_item->p_right->p_up = p_del_item;
p_item->p_left->p_up = p_del_item;
p_del_item->color = p_item->color;
}
ASSERT( p_map->nil_item.color != CL_MAP_RED );
#if QMAP_DEBUG
/* Clear the pointer to the map since the item has been removed. */
p_item->p_map = NULL;
#endif
}
cl_fmap_item_t*
cl_fmap_remove(
IN cl_fmap_t* const p_map,
IN const void* const p_key )
{
cl_fmap_item_t *p_item;
ASSERT( p_map );
ASSERT( p_map->state == CL_INITIALIZED );
/* Seek the node with the specified key */
p_item = cl_fmap_get( p_map, p_key );
cl_fmap_remove_item( p_map, p_item );
return( p_item );
}
void
cl_fmap_merge(
OUT cl_fmap_t* const p_dest_map,
IN OUT cl_fmap_t* const p_src_map )
{
cl_fmap_item_t *p_item, *p_item2, *p_next;
ASSERT( p_dest_map );
ASSERT( p_src_map );
p_item = cl_fmap_head( p_src_map );
while( p_item != cl_fmap_end( p_src_map ) )
{
p_next = cl_fmap_next( p_item );
/* Remove the item from its current map. */
cl_fmap_remove_item( p_src_map, p_item );
/* Insert the item into the destination map. */
p_item2 = cl_fmap_insert( p_dest_map, cl_fmap_key( p_item ), p_item );
/* Check that the item was successfully inserted. */
if( p_item2 != p_item )
{
/* Put the item in back in the source map. */
p_item2 =
cl_fmap_insert( p_src_map, cl_fmap_key( p_item ), p_item );
ASSERT( p_item2 == p_item );
}
p_item = p_next;
}
}
static void
__cl_fmap_delta_move(
IN OUT cl_fmap_t* const p_dest,
IN OUT cl_fmap_t* const p_src,
IN OUT cl_fmap_item_t** const pp_item )
{
cl_fmap_item_t *p_temp, *p_next;
/*
* Get the next item so that we can ensure that pp_item points to
* a valid item upon return from the function.
*/
p_next = cl_fmap_next( *pp_item );
/* Move the old item from its current map the the old map. */
cl_fmap_remove_item( p_src, *pp_item );
p_temp = cl_fmap_insert( p_dest, cl_fmap_key( *pp_item ), *pp_item );
/* We should never have duplicates. */
ASSERT( p_temp == *pp_item );
/* Point pp_item to a valid item in the source map. */
(*pp_item) = p_next;
}
void
cl_fmap_delta(
IN OUT cl_fmap_t* const p_map1,
IN OUT cl_fmap_t* const p_map2,
OUT cl_fmap_t* const p_new,
OUT cl_fmap_t* const p_old )
{
cl_fmap_item_t *p_item1, *p_item2;
intn_t cmp;
ASSERT( p_map1 );
ASSERT( p_map2 );
ASSERT( p_new );
ASSERT( p_old );
ASSERT( cl_is_fmap_empty( p_new ) );
ASSERT( cl_is_fmap_empty( p_old ) );
p_item1 = cl_fmap_head( p_map1 );
p_item2 = cl_fmap_head( p_map2 );
while( p_item1 != cl_fmap_end( p_map1 ) &&
p_item2 != cl_fmap_end( p_map2 ) )
{
cmp = p_map1->pfn_compare( cl_fmap_key( p_item1 ),
cl_fmap_key( p_item2 ) );
if( cmp < 0 )
{
/* We found an old item. */
__cl_fmap_delta_move( p_old, p_map1, &p_item1 );
}
else if( cmp > 0 )
{
/* We found a new item. */
__cl_fmap_delta_move( p_new, p_map2, &p_item2 );
}
else
{
/* Move both forward since they have the same key. */
p_item1 = cl_fmap_next( p_item1 );
p_item2 = cl_fmap_next( p_item2 );
}
}
/* Process the remainder if the end of either source map was reached. */
while( p_item2 != cl_fmap_end( p_map2 ) )
__cl_fmap_delta_move( p_new, p_map2, &p_item2 );
while( p_item1 != cl_fmap_end( p_map1 ) )
__cl_fmap_delta_move( p_old, p_map1, &p_item1 );
}
#endif