/*
This file is provided under a dual BSD/GPLv2 license. When using or
redistributing this file, you may do so under either license.
GPL LICENSE SUMMARY
Copyright(c) 2015 Intel Corporation.
This program is free software; you can redistribute it and/or modify
it under the terms of version 2 of the GNU General Public License as
published by the Free Software Foundation.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
Contact Information:
Intel Corporation, www.intel.com
BSD LICENSE
Copyright(c) 2015 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.
*/
/* Copyright (c) 2003-2015 Intel Corporation. All rights reserved. */
/*
* 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 <string.h> /* for memset declaration */
// RBTREE_CMP should be a comparator, i.e. RBTREE_CMP(a, b) should evaluate to
// -1, 0, or 1 depending on if a < b, a == b, or a > b, respectively.
#ifdef RBTREE_CMP
#if defined(RBTREE_GET_LEFTMOST) || defined(RBTREE_GET_RIGHTMOST)
#error Cannot define both RBTREE_CMP and RBTREE_GET_(LEFT|RIGHT)MOST
#endif
#elif !defined ( RBTREE_GET_LEFTMOST ) || \
! defined ( RBTREE_GET_RIGHTMOST ) || \
! defined ( RBTREE_MAP_COUNT ) || \
! defined ( RBTREE_ASSERT )
#error "You must define RBTREE_GET_LEFTMOST and RBTREE_GET_RIGHTMOST and \
RBTREE_MAP_COUNT and RBTREE_ASSERT before including rbtree.c"
#endif /* RBTREE_CMP */
#define IN /* nothing */
/******************************************************************************
*******************************************************************************
************** ************
************** IMPLEMENTATION OF QUICK MAP ************
************** ************
*******************************************************************************
******************************************************************************/
/* Forward declarations: */
static void ips_cl_qmap_init(
IN cl_qmap_t *p_map,
IN cl_map_item_t* const root,
IN cl_map_item_t* const nil);
static void ips_cl_qmap_insert_item(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* const p_item);
static void ips_cl_qmap_remove_item(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* const p_item);
static cl_map_item_t* ips_cl_qmap_successor(
IN cl_qmap_t* const p_map,
IN const cl_map_item_t* p_item);
#ifndef RBTREE_NO_EMIT_IPS_CL_QMAP_PREDECESSOR
static cl_map_item_t* ips_cl_qmap_predecessor(
IN cl_qmap_t* const p_map,
IN const cl_map_item_t* p_item);
#endif
#if defined(RBTREE_GET_LEFTMOST)
static cl_map_item_t* ips_cl_qmap_search(
IN cl_qmap_t* const p_map,
IN unsigned long start,
IN unsigned long end);
#else
static cl_map_item_t* ips_cl_qmap_searchv(
cl_qmap_t* const p_map,
const RBTREE_MI_PL *key);
#endif
/*
* Get the root.
*/
static inline cl_map_item_t*
__cl_map_root(
IN const cl_qmap_t* const p_map )
{
RBTREE_ASSERT( p_map );
return( p_map->root->p_left );
}
/*
* Returns whether a given item is on the left of its parent.
*/
static int
__cl_map_is_left_child(
IN const cl_map_item_t* const p_item )
{
RBTREE_ASSERT( p_item );
RBTREE_ASSERT( p_item->p_up );
RBTREE_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 )
{
RBTREE_ASSERT( p_item );
RBTREE_ASSERT( p_item->p_up );
RBTREE_ASSERT( p_item->p_up != p_item );
if( __cl_map_is_left_child( p_item ) )
return( &p_item->p_up->p_left );
RBTREE_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;
RBTREE_ASSERT( p_map );
RBTREE_ASSERT( p_item );
RBTREE_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;
RBTREE_ASSERT( p_map );
RBTREE_ASSERT( p_item );
RBTREE_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;
}
/*
* 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;
RBTREE_ASSERT( p_map );
RBTREE_ASSERT( p_item );
RBTREE_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;
RBTREE_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;
RBTREE_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 );
}
}
}
static void ips_cl_qmap_init(
IN cl_qmap_t *p_map,
IN cl_map_item_t* const root,
IN cl_map_item_t* const nil_item)
{
RBTREE_ASSERT( p_map );
RBTREE_ASSERT( root );
RBTREE_ASSERT( nil_item );
memset(p_map,0,sizeof(cl_qmap_t));
p_map->root = root;
/* setup the RB tree map */
p_map->nil_item = nil_item;
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;
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;
}
static void
ips_cl_qmap_insert_item(
IN cl_qmap_t* const p_map,
IN cl_map_item_t* const p_item )
{
cl_map_item_t *p_insert_at, *p_comp_item;
int compare_res = 0;
RBTREE_ASSERT( p_map );
RBTREE_ASSERT( p_item );
RBTREE_ASSERT( p_map->root->p_up == p_map->root );
RBTREE_ASSERT( p_map->root->color != CL_MAP_RED );
RBTREE_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 );
while( p_comp_item != p_map->nil_item )
{
p_insert_at = p_comp_item;
/* Traverse the tree until the correct insertion point is found. */
#ifdef RBTREE_GET_LEFTMOST
if( RBTREE_GET_LEFTMOST(&p_item->payload) < RBTREE_GET_LEFTMOST(&p_insert_at->payload) )
#else
if(RBTREE_CMP(&p_item->payload, &p_insert_at->payload) < 0)
#endif
{
p_comp_item = p_insert_at->p_left;
compare_res = 1;
} else {
p_comp_item = p_insert_at->p_right;
compare_res = -1;
}
}
RBTREE_ASSERT( p_insert_at != p_map->nil_item );
RBTREE_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->color = CL_MAP_RED;
if( p_insert_at == p_map->root )
{
p_insert_at->p_left = p_item;
}
else if( compare_res > 0 ) /* key < p_insert_at->key */
{
p_insert_at->p_left = p_item;
}
else
{
p_insert_at->p_right = p_item;
}
/* Increase the count. */
RBTREE_MAP_COUNT(&p_map->payload)++;
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.
*/
}
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;
}
static void
ips_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;
RBTREE_ASSERT( p_map );
RBTREE_ASSERT( p_item );
if( p_item == p_map->nil_item )
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 = ips_cl_qmap_successor(p_map, p_item);
RBTREE_ASSERT( p_del_item != p_map->nil_item );
}
RBTREE_MAP_COUNT(&p_map->payload)--;
/* 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;
}
RBTREE_ASSERT( p_map->nil_item->color != CL_MAP_RED );
}
static cl_map_item_t *
ips_cl_qmap_successor(
IN cl_qmap_t* const p_map,
IN const cl_map_item_t* p_item )
{
cl_map_item_t *p_tmp;
p_tmp = p_item->p_right;
if (p_tmp != p_map->nil_item) {
while (p_tmp->p_left != p_map->nil_item)
p_tmp = p_tmp->p_left;
return p_tmp;
} else {
p_tmp = p_item->p_up;
while (p_tmp->p_right == p_item) {
p_item = p_tmp;
p_tmp = p_tmp->p_up;
}
if (p_tmp == p_map->root)
return p_map->nil_item;
return p_tmp;
}
}
// When includer defines RBTREE_CMP, ips_cl_qmap_search() is not emitted.
// When this happens, ips_cl_qmap_predecessor() may not be called.
// Combined with -Werror -Wunused-function, libpsm2 fails to build.
// So provide macro to control emitting this function
#ifndef RBTREE_NO_EMIT_IPS_CL_QMAP_PREDECESSOR
static cl_map_item_t *
ips_cl_qmap_predecessor(
IN cl_qmap_t* const p_map,
IN const cl_map_item_t* p_item )
{
cl_map_item_t *p_tmp;
p_tmp = p_item->p_left;
if (p_tmp != p_map->nil_item) {
while (p_tmp->p_right != p_map->nil_item)
p_tmp = p_tmp->p_right;
return p_tmp;
} else {
p_tmp = p_item->p_up;
while (p_tmp->p_left == p_item) {
p_item = p_tmp;
p_tmp = p_tmp->p_up;
}
if (p_tmp == p_map->root)
return p_map->nil_item;
return p_tmp;
}
}
#endif /* RBTREE_NO_EMIT_IPS_CL_QMAP_PREDECESSOR */
#if defined(RBTREE_GET_LEFTMOST)
/*
* return the first node with buffer overlapping or zero.
*/
static cl_map_item_t *
ips_cl_qmap_search(cl_qmap_t * const p_map,
unsigned long start, unsigned long end)
{
cl_map_item_t *p_item, *p_tmp;
RBTREE_ASSERT( p_map );
p_item = __cl_map_root(p_map);
while (p_item != p_map->nil_item) {
if (start > RBTREE_GET_LEFTMOST(&p_item->payload)) {
p_tmp = p_item->p_right;
if (p_tmp != p_map->nil_item) {
p_item = p_tmp;
continue;
}
/*
* p_item is on immediate left side of 'start'.
*/
if (start >= RBTREE_GET_RIGHTMOST(&p_item->payload)) {
/*
* p_item is on immediate right
* side of 'start'.
*/
p_item = ips_cl_qmap_successor(p_map, p_item);
if (p_item != p_map->nil_item &&
end <= RBTREE_GET_LEFTMOST(&p_item->payload))
p_item = p_map->nil_item;
}
} else if (start < RBTREE_GET_LEFTMOST(&p_item->payload)) {
p_tmp = p_item->p_left;
if (p_tmp != p_map->nil_item) {
p_item = p_tmp;
continue;
}
/*
* p_tmp is on immediate left side of 'start'.
*/
p_tmp = ips_cl_qmap_predecessor(p_map, p_item);
if (p_tmp == p_map->nil_item ||
(start >= RBTREE_GET_RIGHTMOST(&p_tmp->payload))) {
/*
* p_item is on immediate right
* side of 'start'.
*/
if (end <= RBTREE_GET_LEFTMOST(&p_item->payload))
p_item = p_map->nil_item;
} else
p_item = p_tmp;
}
break;
}
return p_item;
}
#else /* defined(...LEFTMOST) || defined(...RIGHTMOST) */
static cl_map_item_t *
ips_cl_qmap_searchv(cl_qmap_t * const p_map, const RBTREE_MI_PL *key)
{
RBTREE_ASSERT( p_map );
cl_map_item_t *p_item = __cl_map_root(p_map);
while (p_item != p_map->nil_item) {
if (RBTREE_CMP(key, &p_item->payload) > 0) {
p_item = p_item->p_right;
} else if (RBTREE_CMP(key, &p_item->payload) < 0) {
p_item = p_item->p_left;
} else {
break;
}
}
return p_item;
}
#endif /* defined(...LEFTMOST) || defined(...RIGHTMOST) */