*****************************************************************************/\r
\r
\r
+#include <complib/cl_rbmap.h>\r
#include <complib/cl_qmap.h>\r
#include <complib/cl_map.h>\r
#include <complib/cl_fleximap.h>\r
#include <complib/cl_memory.h>\r
\r
\r
+/******************************************************************************\r
+*******************************************************************************\r
+************** ************\r
+************** IMPLEMENTATION OF RB MAP ************\r
+************** ************\r
+*******************************************************************************\r
+******************************************************************************/\r
+\r
+\r
+/*\r
+ * Returns whether a given item is on the left of its parent.\r
+ */\r
+static boolean_t\r
+__cl_rbmap_is_left_child(\r
+ IN const cl_rbmap_item_t* const p_item )\r
+{\r
+ CL_ASSERT( p_item );\r
+ CL_ASSERT( p_item->p_up );\r
+ CL_ASSERT( p_item->p_up != p_item );\r
+\r
+ return( p_item->p_up->p_left == p_item );\r
+}\r
+\r
+\r
+/*\r
+ * Retrieve the pointer to the parent's pointer to an item.\r
+ */\r
+static cl_rbmap_item_t**\r
+__cl_rbmap_get_parent_ptr_to_item(\r
+ IN cl_rbmap_item_t* const p_item )\r
+{\r
+ CL_ASSERT( p_item );\r
+ CL_ASSERT( p_item->p_up );\r
+ CL_ASSERT( p_item->p_up != p_item );\r
+\r
+ if( __cl_rbmap_is_left_child( p_item ) )\r
+ return( &p_item->p_up->p_left );\r
+\r
+ CL_ASSERT( p_item->p_up->p_right == p_item );\r
+ return( &p_item->p_up->p_right );\r
+}\r
+\r
+\r
+/*\r
+ * Rotate a node to the left. This rotation affects the least number of links\r
+ * between nodes and brings the level of C up by one while increasing the depth\r
+ * of A one. Note that the links to/from W, X, Y, and Z are not affected.\r
+ *\r
+ * R R\r
+ * | |\r
+ * A C\r
+ * / \ / \\r
+ * W C A Z\r
+ * / \ / \\r
+ * B Z W B\r
+ * / \ / \\r
+ * X Y X Y\r
+ */\r
+static void\r
+__cl_rbmap_rot_left(\r
+ IN cl_rbmap_t* const p_map,\r
+ IN cl_rbmap_item_t* const p_item )\r
+{\r
+ cl_rbmap_item_t **pp_root;\r
+\r
+ CL_ASSERT( p_map );\r
+ CL_ASSERT( p_item );\r
+ CL_ASSERT( p_item->p_right != &p_map->nil );\r
+\r
+ pp_root = __cl_rbmap_get_parent_ptr_to_item( p_item );\r
+\r
+ /* Point R to C instead of A. */\r
+ *pp_root = p_item->p_right;\r
+ /* Set C's parent to R. */\r
+ (*pp_root)->p_up = p_item->p_up;\r
+\r
+ /* Set A's right to B */\r
+ p_item->p_right = (*pp_root)->p_left;\r
+ /*\r
+ * Set B's parent to A. We trap for B being NIL since the\r
+ * caller may depend on NIL not changing.\r
+ */\r
+ if( (*pp_root)->p_left != &p_map->nil )\r
+ (*pp_root)->p_left->p_up = p_item;\r
+\r
+ /* Set C's left to A. */\r
+ (*pp_root)->p_left = p_item;\r
+ /* Set A's parent to C. */\r
+ p_item->p_up = *pp_root;\r
+}\r
+\r
+\r
+/*\r
+ * Rotate a node to the right. This rotation affects the least number of links\r
+ * between nodes and brings the level of A up by one while increasing the depth\r
+ * of C one. Note that the links to/from W, X, Y, and Z are not affected.\r
+ *\r
+ * R R\r
+ * | |\r
+ * C A\r
+ * / \ / \\r
+ * A Z W C\r
+ * / \ / \\r
+ * W B B Z\r
+ * / \ / \\r
+ * X Y X Y\r
+ */\r
+static void\r
+__cl_rbmap_rot_right(\r
+ IN cl_rbmap_t* const p_map,\r
+ IN cl_rbmap_item_t* const p_item )\r
+{\r
+ cl_rbmap_item_t **pp_root;\r
+\r
+ CL_ASSERT( p_map );\r
+ CL_ASSERT( p_item );\r
+ CL_ASSERT( p_item->p_left != &p_map->nil );\r
+\r
+ /* Point R to A instead of C. */\r
+ pp_root = __cl_rbmap_get_parent_ptr_to_item( p_item );\r
+ (*pp_root) = p_item->p_left;\r
+ /* Set A's parent to R. */\r
+ (*pp_root)->p_up = p_item->p_up;\r
+\r
+ /* Set C's left to B */\r
+ p_item->p_left = (*pp_root)->p_right;\r
+ /*\r
+ * Set B's parent to C. We trap for B being NIL since the\r
+ * caller may depend on NIL not changing.\r
+ */\r
+ if( (*pp_root)->p_right != &p_map->nil )\r
+ (*pp_root)->p_right->p_up = p_item;\r
+\r
+ /* Set A's right to C. */\r
+ (*pp_root)->p_right = p_item;\r
+ /* Set C's parent to A. */\r
+ p_item->p_up = *pp_root;\r
+}\r
+\r
+\r
+/*\r
+ * Balance a tree starting at a given item back to the root.\r
+ */\r
+static void\r
+__cl_rbmap_ins_bal(\r
+ IN cl_rbmap_t* const p_map,\r
+ IN cl_rbmap_item_t* p_item )\r
+{\r
+ cl_rbmap_item_t* p_grand_uncle;\r
+\r
+ CL_ASSERT( p_map );\r
+ CL_ASSERT( p_item );\r
+ CL_ASSERT( p_item != &p_map->root );\r
+\r
+ while( p_item->p_up->color == CL_MAP_RED )\r
+ {\r
+ if( __cl_rbmap_is_left_child( p_item->p_up ) )\r
+ {\r
+ p_grand_uncle = p_item->p_up->p_up->p_right;\r
+ CL_ASSERT( p_grand_uncle );\r
+ if( p_grand_uncle->color == CL_MAP_RED )\r
+ {\r
+ p_grand_uncle->color = CL_MAP_BLACK;\r
+ p_item->p_up->color = CL_MAP_BLACK;\r
+ p_item->p_up->p_up->color = CL_MAP_RED;\r
+ p_item = p_item->p_up->p_up;\r
+ continue;\r
+ }\r
+\r
+ if( !__cl_rbmap_is_left_child( p_item ) )\r
+ {\r
+ p_item = p_item->p_up;\r
+ __cl_rbmap_rot_left( p_map, p_item );\r
+ }\r
+ p_item->p_up->color = CL_MAP_BLACK;\r
+ p_item->p_up->p_up->color = CL_MAP_RED;\r
+ __cl_rbmap_rot_right( p_map, p_item->p_up->p_up );\r
+ }\r
+ else\r
+ {\r
+ p_grand_uncle = p_item->p_up->p_up->p_left;\r
+ CL_ASSERT( p_grand_uncle );\r
+ if( p_grand_uncle->color == CL_MAP_RED )\r
+ {\r
+ p_grand_uncle->color = CL_MAP_BLACK;\r
+ p_item->p_up->color = CL_MAP_BLACK;\r
+ p_item->p_up->p_up->color = CL_MAP_RED;\r
+ p_item = p_item->p_up->p_up;\r
+ continue;\r
+ }\r
+\r
+ if( __cl_rbmap_is_left_child( p_item ) )\r
+ {\r
+ p_item = p_item->p_up;\r
+ __cl_rbmap_rot_right( p_map, p_item );\r
+ }\r
+ p_item->p_up->color = CL_MAP_BLACK;\r
+ p_item->p_up->p_up->color = CL_MAP_RED;\r
+ __cl_rbmap_rot_left( p_map, p_item->p_up->p_up );\r
+ }\r
+ }\r
+}\r
+\r
+\r
+void\r
+cl_rbmap_insert(\r
+ IN cl_rbmap_t* const p_map,\r
+ IN cl_rbmap_item_t* const p_insert_at,\r
+ IN cl_rbmap_item_t* const p_item,\r
+ IN boolean_t left )\r
+{\r
+ CL_ASSERT( p_map );\r
+ CL_ASSERT( p_map->state == CL_INITIALIZED );\r
+ CL_ASSERT( p_insert_at );\r
+ CL_ASSERT( p_item );\r
+ CL_ASSERT( p_map->root.p_up == &p_map->root );\r
+ CL_ASSERT( p_map->root.color != CL_MAP_RED );\r
+ CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
+\r
+ p_item->p_left = &p_map->nil;\r
+ p_item->p_right = &p_map->nil;\r
+ p_item->color = CL_MAP_RED;\r
+\r
+ if( p_insert_at == cl_rbmap_end( p_map ) )\r
+ {\r
+ p_map->root.p_left = p_item;\r
+ p_item->p_up = &p_map->root;\r
+ }\r
+ else\r
+ {\r
+ if( left )\r
+ p_insert_at->p_left = p_item;\r
+ else\r
+ p_insert_at->p_right = p_item;\r
+\r
+ p_item->p_up = p_insert_at;\r
+ }\r
+\r
+ /* Increase the count. */\r
+ p_map->count++;\r
+\r
+ /*\r
+ * We have added depth to this section of the tree.\r
+ * Rebalance as necessary as we retrace our path through the tree\r
+ * and update colors.\r
+ */\r
+ __cl_rbmap_ins_bal( p_map, p_item );\r
+\r
+ cl_rbmap_root( p_map )->color = CL_MAP_BLACK;\r
+\r
+ /*\r
+ * Note that it is not necessary to re-color the nil node black because all\r
+ * red color assignments are made via the p_up pointer, and nil is never\r
+ * set as the value of a p_up pointer.\r
+ */\r
+\r
+#ifdef _DEBUG_\r
+ /* Set the pointer to the map in the map item for consistency checking. */\r
+ p_item->p_map = p_map;\r
+#endif\r
+}\r
+\r
+\r
+static void\r
+__cl_rbmap_del_bal(\r
+ IN cl_rbmap_t* const p_map,\r
+ IN cl_rbmap_item_t* p_item )\r
+{\r
+ cl_rbmap_item_t *p_uncle;\r
+\r
+ while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )\r
+ {\r
+ if( __cl_rbmap_is_left_child( p_item ) )\r
+ {\r
+ p_uncle = p_item->p_up->p_right;\r
+\r
+ if( p_uncle->color == CL_MAP_RED )\r
+ {\r
+ p_uncle->color = CL_MAP_BLACK;\r
+ p_item->p_up->color = CL_MAP_RED;\r
+ __cl_rbmap_rot_left( p_map, p_item->p_up );\r
+ p_uncle = p_item->p_up->p_right;\r
+ }\r
+\r
+ if( p_uncle->p_right->color != CL_MAP_RED )\r
+ {\r
+ if( p_uncle->p_left->color != CL_MAP_RED )\r
+ {\r
+ p_uncle->color = CL_MAP_RED;\r
+ p_item = p_item->p_up;\r
+ continue;\r
+ }\r
+\r
+ p_uncle->p_left->color = CL_MAP_BLACK;\r
+ p_uncle->color = CL_MAP_RED;\r
+ __cl_rbmap_rot_right( p_map, p_uncle );\r
+ p_uncle = p_item->p_up->p_right;\r
+ }\r
+ p_uncle->color = p_item->p_up->color;\r
+ p_item->p_up->color = CL_MAP_BLACK;\r
+ p_uncle->p_right->color = CL_MAP_BLACK;\r
+ __cl_rbmap_rot_left( p_map, p_item->p_up );\r
+ break;\r
+ }\r
+ else\r
+ {\r
+ p_uncle = p_item->p_up->p_left;\r
+\r
+ if( p_uncle->color == CL_MAP_RED )\r
+ {\r
+ p_uncle->color = CL_MAP_BLACK;\r
+ p_item->p_up->color = CL_MAP_RED;\r
+ __cl_rbmap_rot_right( p_map, p_item->p_up );\r
+ p_uncle = p_item->p_up->p_left;\r
+ }\r
+\r
+ if( p_uncle->p_left->color != CL_MAP_RED )\r
+ {\r
+ if( p_uncle->p_right->color != CL_MAP_RED )\r
+ {\r
+ p_uncle->color = CL_MAP_RED;\r
+ p_item = p_item->p_up;\r
+ continue;\r
+ }\r
+\r
+ p_uncle->p_right->color = CL_MAP_BLACK;\r
+ p_uncle->color = CL_MAP_RED;\r
+ __cl_rbmap_rot_left( p_map, p_uncle );\r
+ p_uncle = p_item->p_up->p_left;\r
+ }\r
+ p_uncle->color = p_item->p_up->color;\r
+ p_item->p_up->color = CL_MAP_BLACK;\r
+ p_uncle->p_left->color = CL_MAP_BLACK;\r
+ __cl_rbmap_rot_right( p_map, p_item->p_up );\r
+ break;\r
+ }\r
+ }\r
+ p_item->color = CL_MAP_BLACK;\r
+}\r
+\r
+\r
+void\r
+cl_rbmap_remove_item(\r
+ IN cl_rbmap_t* const p_map,\r
+ IN cl_rbmap_item_t* const p_item )\r
+{\r
+ cl_rbmap_item_t *p_child, *p_del_item;\r
+\r
+ CL_ASSERT( p_map );\r
+ CL_ASSERT( p_map->state == CL_INITIALIZED );\r
+ CL_ASSERT( p_item );\r
+ CL_ASSERT( p_item->p_map == p_map );\r
+\r
+ if( p_item == cl_rbmap_end( p_map ) )\r
+ return;\r
+\r
+ if( p_item->p_right == &p_map->nil )\r
+ {\r
+ /* The item being removed has children on at most its left. */\r
+ p_del_item = p_item;\r
+ p_child = p_del_item->p_left;\r
+ }\r
+ else if( p_item->p_left == &p_map->nil )\r
+ {\r
+ /* The item being removed has children on at most its right. */\r
+ p_del_item = p_item;\r
+ p_child = p_del_item->p_right;\r
+ }\r
+ else\r
+ {\r
+ /*\r
+ * The item being removed has children on both side.\r
+ * We select the item that will replace it. After removing\r
+ * the substitute item and rebalancing, the tree will have the\r
+ * correct topology. Exchanging the substitute for the item\r
+ * will finalize the removal.\r
+ */\r
+ p_del_item = p_item->p_right;\r
+ CL_ASSERT( p_del_item != &p_map->nil );\r
+ while( p_del_item->p_left != &p_map->nil )\r
+ p_del_item = p_del_item->p_left;\r
+ p_child = p_del_item->p_right;\r
+ }\r
+\r
+ /* Decrement the item count. */\r
+ p_map->count--;\r
+\r
+ /*\r
+ * This assignment may modify the parent pointer of the nil node.\r
+ * This is inconsequential.\r
+ */\r
+ p_child->p_up = p_del_item->p_up;\r
+ (*__cl_rbmap_get_parent_ptr_to_item( p_del_item )) = p_child; // 2 right = 5\r
+\r
+ if( p_del_item->color != CL_MAP_RED )\r
+ __cl_rbmap_del_bal( p_map, p_child );\r
+\r
+ /*\r
+ * Note that the splicing done below does not need to occur before\r
+ * the tree is balanced, since the actual topology changes are made by the\r
+ * preceding code. The topology is preserved by the color assignment made\r
+ * below (reader should be reminded that p_del_item == p_item in some cases).\r
+ */\r
+ if( p_del_item != p_item )\r
+ {\r
+ /*\r
+ * Finalize the removal of the specified item by exchanging it with\r
+ * the substitute which we removed above.\r
+ */\r
+ p_del_item->p_up = p_item->p_up;\r
+ p_del_item->p_left = p_item->p_left;\r
+ p_del_item->p_right = p_item->p_right;\r
+ (*__cl_rbmap_get_parent_ptr_to_item( p_item )) = p_del_item;\r
+ p_item->p_right->p_up = p_del_item;\r
+ p_item->p_left->p_up = p_del_item;\r
+ p_del_item->color = p_item->color;\r
+ }\r
+\r
+ CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
+\r
+#ifdef _DEBUG_\r
+ /* Clear the pointer to the map since the item has been removed. */\r
+ p_item->p_map = NULL;\r
+#endif\r
+}\r
+\r
+\r
/******************************************************************************\r
*******************************************************************************\r
************** ************\r