winverbs: process connect and accept asynchronously
[mirror/winof/.git] / core / complib / cl_map.c
index 77a2bca..9af2471 100644 (file)
@@ -27,7 +27,7 @@
  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  * SOFTWARE.\r
  *\r
- * $Id:$\r
+ * $Id$\r
  */\r
 \r
 \r
@@ -39,8 +39,6 @@
  *\r
  * Environment:\r
  *     All\r
- *\r
- * $Revision$\r
  */\r
 \r
 \r
 *****************************************************************************/\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