1321936Shselasky/* 2321936Shselasky * Copyright (c) 2004-2009 Voltaire, Inc. All rights reserved. 3321936Shselasky * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved. 4321936Shselasky * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5321936Shselasky * 6321936Shselasky * This software is available to you under a choice of one of two 7321936Shselasky * licenses. You may choose to be licensed under the terms of the GNU 8321936Shselasky * General Public License (GPL) Version 2, available from the file 9321936Shselasky * COPYING in the main directory of this source tree, or the 10321936Shselasky * OpenIB.org BSD license below: 11321936Shselasky * 12321936Shselasky * Redistribution and use in source and binary forms, with or 13321936Shselasky * without modification, are permitted provided that the following 14321936Shselasky * conditions are met: 15321936Shselasky * 16321936Shselasky * - Redistributions of source code must retain the above 17321936Shselasky * copyright notice, this list of conditions and the following 18321936Shselasky * disclaimer. 19321936Shselasky * 20321936Shselasky * - Redistributions in binary form must reproduce the above 21321936Shselasky * copyright notice, this list of conditions and the following 22321936Shselasky * disclaimer in the documentation and/or other materials 23321936Shselasky * provided with the distribution. 24321936Shselasky * 25321936Shselasky * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26321936Shselasky * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27321936Shselasky * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28321936Shselasky * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29321936Shselasky * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30321936Shselasky * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31321936Shselasky * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32321936Shselasky * SOFTWARE. 33321936Shselasky * 34321936Shselasky */ 35321936Shselasky 36321936Shselasky/* 37321936Shselasky * Abstract: 38321936Shselasky * Implementation of quick map, a binary tree where the caller always 39321936Shselasky * provides all necessary storage. 40321936Shselasky * 41321936Shselasky */ 42321936Shselasky 43321936Shselasky/***************************************************************************** 44321936Shselasky* 45321936Shselasky* Map 46321936Shselasky* 47321936Shselasky* Map is an associative array. By providing a key, the caller can retrieve 48321936Shselasky* an object from the map. All objects in the map have an associated key, 49321936Shselasky* as specified by the caller when the object was inserted into the map. 50321936Shselasky* In addition to random access, the caller can traverse the map much like 51321936Shselasky* a linked list, either forwards from the first object or backwards from 52321936Shselasky* the last object. The objects in the map are always traversed in 53321936Shselasky* order since the nodes are stored sorted. 54321936Shselasky* 55321936Shselasky* This implementation of Map uses a red black tree verified against 56321936Shselasky* Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth 57321936Shselasky* printing, 1994. 58321936Shselasky* 59321936Shselasky*****************************************************************************/ 60321936Shselasky 61321936Shselasky#if HAVE_CONFIG_H 62321936Shselasky# include <config.h> 63321936Shselasky#endif /* HAVE_CONFIG_H */ 64321936Shselasky 65321936Shselasky#include <string.h> 66321936Shselasky#include <complib/cl_qmap.h> 67321936Shselasky#include <complib/cl_map.h> 68321936Shselasky#include <complib/cl_fleximap.h> 69321936Shselasky 70321936Shselasky/****************************************************************************** 71321936Shselasky IMPLEMENTATION OF QUICK MAP 72321936Shselasky******************************************************************************/ 73321936Shselasky 74321936Shselasky/* 75321936Shselasky * Get the root. 76321936Shselasky */ 77321936Shselaskystatic inline cl_map_item_t *__cl_map_root(IN const cl_qmap_t * const p_map) 78321936Shselasky{ 79321936Shselasky CL_ASSERT(p_map); 80321936Shselasky return (p_map->root.p_left); 81321936Shselasky} 82321936Shselasky 83321936Shselasky/* 84321936Shselasky * Returns whether a given item is on the left of its parent. 85321936Shselasky */ 86321936Shselaskystatic boolean_t __cl_map_is_left_child(IN const cl_map_item_t * const p_item) 87321936Shselasky{ 88321936Shselasky CL_ASSERT(p_item); 89321936Shselasky CL_ASSERT(p_item->p_up); 90321936Shselasky CL_ASSERT(p_item->p_up != p_item); 91321936Shselasky 92321936Shselasky return (p_item->p_up->p_left == p_item); 93321936Shselasky} 94321936Shselasky 95321936Shselasky/* 96321936Shselasky * Retrieve the pointer to the parent's pointer to an item. 97321936Shselasky */ 98321936Shselaskystatic cl_map_item_t **__cl_map_get_parent_ptr_to_item(IN cl_map_item_t * 99321936Shselasky const p_item) 100321936Shselasky{ 101321936Shselasky CL_ASSERT(p_item); 102321936Shselasky CL_ASSERT(p_item->p_up); 103321936Shselasky CL_ASSERT(p_item->p_up != p_item); 104321936Shselasky 105321936Shselasky if (__cl_map_is_left_child(p_item)) 106321936Shselasky return (&p_item->p_up->p_left); 107321936Shselasky 108321936Shselasky CL_ASSERT(p_item->p_up->p_right == p_item); 109321936Shselasky return (&p_item->p_up->p_right); 110321936Shselasky} 111321936Shselasky 112321936Shselasky/* 113321936Shselasky * Rotate a node to the left. This rotation affects the least number of links 114321936Shselasky * between nodes and brings the level of C up by one while increasing the depth 115321936Shselasky * of A one. Note that the links to/from W, X, Y, and Z are not affected. 116321936Shselasky * 117321936Shselasky * R R 118321936Shselasky * | | 119321936Shselasky * A C 120321936Shselasky * / \ / \ 121321936Shselasky * W C A Z 122321936Shselasky * / \ / \ 123321936Shselasky * B Z W B 124321936Shselasky * / \ / \ 125321936Shselasky * X Y X Y 126321936Shselasky */ 127321936Shselaskystatic void __cl_map_rot_left(IN cl_qmap_t * const p_map, 128321936Shselasky IN cl_map_item_t * const p_item) 129321936Shselasky{ 130321936Shselasky cl_map_item_t **pp_root; 131321936Shselasky 132321936Shselasky CL_ASSERT(p_map); 133321936Shselasky CL_ASSERT(p_item); 134321936Shselasky CL_ASSERT(p_item->p_right != &p_map->nil); 135321936Shselasky 136321936Shselasky pp_root = __cl_map_get_parent_ptr_to_item(p_item); 137321936Shselasky 138321936Shselasky /* Point R to C instead of A. */ 139321936Shselasky *pp_root = p_item->p_right; 140321936Shselasky /* Set C's parent to R. */ 141321936Shselasky (*pp_root)->p_up = p_item->p_up; 142321936Shselasky 143321936Shselasky /* Set A's right to B */ 144321936Shselasky p_item->p_right = (*pp_root)->p_left; 145321936Shselasky /* 146321936Shselasky * Set B's parent to A. We trap for B being NIL since the 147321936Shselasky * caller may depend on NIL not changing. 148321936Shselasky */ 149321936Shselasky if ((*pp_root)->p_left != &p_map->nil) 150321936Shselasky (*pp_root)->p_left->p_up = p_item; 151321936Shselasky 152321936Shselasky /* Set C's left to A. */ 153321936Shselasky (*pp_root)->p_left = p_item; 154321936Shselasky /* Set A's parent to C. */ 155321936Shselasky p_item->p_up = *pp_root; 156321936Shselasky} 157321936Shselasky 158321936Shselasky/* 159321936Shselasky * Rotate a node to the right. This rotation affects the least number of links 160321936Shselasky * between nodes and brings the level of A up by one while increasing the depth 161321936Shselasky * of C one. Note that the links to/from W, X, Y, and Z are not affected. 162321936Shselasky * 163321936Shselasky * R R 164321936Shselasky * | | 165321936Shselasky * C A 166321936Shselasky * / \ / \ 167321936Shselasky * A Z W C 168321936Shselasky * / \ / \ 169321936Shselasky * W B B Z 170321936Shselasky * / \ / \ 171321936Shselasky * X Y X Y 172321936Shselasky */ 173321936Shselaskystatic void __cl_map_rot_right(IN cl_qmap_t * const p_map, 174321936Shselasky IN cl_map_item_t * const p_item) 175321936Shselasky{ 176321936Shselasky cl_map_item_t **pp_root; 177321936Shselasky 178321936Shselasky CL_ASSERT(p_map); 179321936Shselasky CL_ASSERT(p_item); 180321936Shselasky CL_ASSERT(p_item->p_left != &p_map->nil); 181321936Shselasky 182321936Shselasky /* Point R to A instead of C. */ 183321936Shselasky pp_root = __cl_map_get_parent_ptr_to_item(p_item); 184321936Shselasky (*pp_root) = p_item->p_left; 185321936Shselasky /* Set A's parent to R. */ 186321936Shselasky (*pp_root)->p_up = p_item->p_up; 187321936Shselasky 188321936Shselasky /* Set C's left to B */ 189321936Shselasky p_item->p_left = (*pp_root)->p_right; 190321936Shselasky /* 191321936Shselasky * Set B's parent to C. We trap for B being NIL since the 192321936Shselasky * caller may depend on NIL not changing. 193321936Shselasky */ 194321936Shselasky if ((*pp_root)->p_right != &p_map->nil) 195321936Shselasky (*pp_root)->p_right->p_up = p_item; 196321936Shselasky 197321936Shselasky /* Set A's right to C. */ 198321936Shselasky (*pp_root)->p_right = p_item; 199321936Shselasky /* Set C's parent to A. */ 200321936Shselasky p_item->p_up = *pp_root; 201321936Shselasky} 202321936Shselasky 203321936Shselaskyvoid cl_qmap_init(IN cl_qmap_t * const p_map) 204321936Shselasky{ 205321936Shselasky CL_ASSERT(p_map); 206321936Shselasky 207321936Shselasky memset(p_map, 0, sizeof(cl_qmap_t)); 208321936Shselasky 209321936Shselasky /* special setup for the root node */ 210321936Shselasky p_map->root.p_up = &p_map->root; 211321936Shselasky p_map->root.p_left = &p_map->nil; 212321936Shselasky p_map->root.p_right = &p_map->nil; 213321936Shselasky p_map->root.color = CL_MAP_BLACK; 214321936Shselasky 215321936Shselasky /* Setup the node used as terminator for all leaves. */ 216321936Shselasky p_map->nil.p_up = &p_map->nil; 217321936Shselasky p_map->nil.p_left = &p_map->nil; 218321936Shselasky p_map->nil.p_right = &p_map->nil; 219321936Shselasky p_map->nil.color = CL_MAP_BLACK; 220321936Shselasky 221321936Shselasky p_map->state = CL_INITIALIZED; 222321936Shselasky 223321936Shselasky cl_qmap_remove_all(p_map); 224321936Shselasky} 225321936Shselasky 226321936Shselaskycl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map, 227321936Shselasky IN const uint64_t key) 228321936Shselasky{ 229321936Shselasky cl_map_item_t *p_item; 230321936Shselasky 231321936Shselasky CL_ASSERT(p_map); 232321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 233321936Shselasky 234321936Shselasky p_item = __cl_map_root(p_map); 235321936Shselasky 236321936Shselasky while (p_item != &p_map->nil) { 237321936Shselasky if (key == p_item->key) 238321936Shselasky break; /* just right */ 239321936Shselasky 240321936Shselasky if (key < p_item->key) 241321936Shselasky p_item = p_item->p_left; /* too small */ 242321936Shselasky else 243321936Shselasky p_item = p_item->p_right; /* too big */ 244321936Shselasky } 245321936Shselasky 246321936Shselasky return (p_item); 247321936Shselasky} 248321936Shselasky 249321936Shselaskycl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map, 250321936Shselasky IN const uint64_t key) 251321936Shselasky{ 252321936Shselasky cl_map_item_t *p_item; 253321936Shselasky cl_map_item_t *p_item_found; 254321936Shselasky 255321936Shselasky CL_ASSERT(p_map); 256321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 257321936Shselasky 258321936Shselasky p_item = __cl_map_root(p_map); 259321936Shselasky p_item_found = (cl_map_item_t *) & p_map->nil; 260321936Shselasky 261321936Shselasky while (p_item != &p_map->nil) { 262321936Shselasky if (key < p_item->key) { 263321936Shselasky p_item_found = p_item; 264321936Shselasky p_item = p_item->p_left; 265321936Shselasky } else { 266321936Shselasky p_item = p_item->p_right; 267321936Shselasky } 268321936Shselasky } 269321936Shselasky 270321936Shselasky return (p_item_found); 271321936Shselasky} 272321936Shselasky 273321936Shselaskyvoid cl_qmap_apply_func(IN const cl_qmap_t * const p_map, 274321936Shselasky IN cl_pfn_qmap_apply_t pfn_func, 275321936Shselasky IN const void *const context) 276321936Shselasky{ 277321936Shselasky cl_map_item_t *p_map_item; 278321936Shselasky 279321936Shselasky /* Note that context can have any arbitrary value. */ 280321936Shselasky CL_ASSERT(p_map); 281321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 282321936Shselasky CL_ASSERT(pfn_func); 283321936Shselasky 284321936Shselasky p_map_item = cl_qmap_head(p_map); 285321936Shselasky while (p_map_item != cl_qmap_end(p_map)) { 286321936Shselasky pfn_func(p_map_item, (void *)context); 287321936Shselasky p_map_item = cl_qmap_next(p_map_item); 288321936Shselasky } 289321936Shselasky} 290321936Shselasky 291321936Shselasky/* 292321936Shselasky * Balance a tree starting at a given item back to the root. 293321936Shselasky */ 294321936Shselaskystatic void __cl_map_ins_bal(IN cl_qmap_t * const p_map, 295321936Shselasky IN cl_map_item_t * p_item) 296321936Shselasky{ 297321936Shselasky cl_map_item_t *p_grand_uncle; 298321936Shselasky 299321936Shselasky CL_ASSERT(p_map); 300321936Shselasky CL_ASSERT(p_item); 301321936Shselasky CL_ASSERT(p_item != &p_map->root); 302321936Shselasky 303321936Shselasky while (p_item->p_up->color == CL_MAP_RED) { 304321936Shselasky if (__cl_map_is_left_child(p_item->p_up)) { 305321936Shselasky p_grand_uncle = p_item->p_up->p_up->p_right; 306321936Shselasky CL_ASSERT(p_grand_uncle); 307321936Shselasky if (p_grand_uncle->color == CL_MAP_RED) { 308321936Shselasky p_grand_uncle->color = CL_MAP_BLACK; 309321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 310321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 311321936Shselasky p_item = p_item->p_up->p_up; 312321936Shselasky continue; 313321936Shselasky } 314321936Shselasky 315321936Shselasky if (!__cl_map_is_left_child(p_item)) { 316321936Shselasky p_item = p_item->p_up; 317321936Shselasky __cl_map_rot_left(p_map, p_item); 318321936Shselasky } 319321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 320321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 321321936Shselasky __cl_map_rot_right(p_map, p_item->p_up->p_up); 322321936Shselasky } else { 323321936Shselasky p_grand_uncle = p_item->p_up->p_up->p_left; 324321936Shselasky CL_ASSERT(p_grand_uncle); 325321936Shselasky if (p_grand_uncle->color == CL_MAP_RED) { 326321936Shselasky p_grand_uncle->color = CL_MAP_BLACK; 327321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 328321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 329321936Shselasky p_item = p_item->p_up->p_up; 330321936Shselasky continue; 331321936Shselasky } 332321936Shselasky 333321936Shselasky if (__cl_map_is_left_child(p_item)) { 334321936Shselasky p_item = p_item->p_up; 335321936Shselasky __cl_map_rot_right(p_map, p_item); 336321936Shselasky } 337321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 338321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 339321936Shselasky __cl_map_rot_left(p_map, p_item->p_up->p_up); 340321936Shselasky } 341321936Shselasky } 342321936Shselasky} 343321936Shselasky 344321936Shselaskycl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map, 345321936Shselasky IN const uint64_t key, 346321936Shselasky IN cl_map_item_t * const p_item) 347321936Shselasky{ 348321936Shselasky cl_map_item_t *p_insert_at, *p_comp_item; 349321936Shselasky 350321936Shselasky CL_ASSERT(p_map); 351321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 352321936Shselasky CL_ASSERT(p_item); 353321936Shselasky CL_ASSERT(p_map->root.p_up == &p_map->root); 354321936Shselasky CL_ASSERT(p_map->root.color != CL_MAP_RED); 355321936Shselasky CL_ASSERT(p_map->nil.color != CL_MAP_RED); 356321936Shselasky 357321936Shselasky p_item->p_left = &p_map->nil; 358321936Shselasky p_item->p_right = &p_map->nil; 359321936Shselasky p_item->key = key; 360321936Shselasky p_item->color = CL_MAP_RED; 361321936Shselasky 362321936Shselasky /* Find the insertion location. */ 363321936Shselasky p_insert_at = &p_map->root; 364321936Shselasky p_comp_item = __cl_map_root(p_map); 365321936Shselasky 366321936Shselasky while (p_comp_item != &p_map->nil) { 367321936Shselasky p_insert_at = p_comp_item; 368321936Shselasky 369321936Shselasky if (key == p_insert_at->key) 370321936Shselasky return (p_insert_at); 371321936Shselasky 372321936Shselasky /* Traverse the tree until the correct insertion point is found. */ 373321936Shselasky if (key < p_insert_at->key) 374321936Shselasky p_comp_item = p_insert_at->p_left; 375321936Shselasky else 376321936Shselasky p_comp_item = p_insert_at->p_right; 377321936Shselasky } 378321936Shselasky 379321936Shselasky CL_ASSERT(p_insert_at != &p_map->nil); 380321936Shselasky CL_ASSERT(p_comp_item == &p_map->nil); 381321936Shselasky /* Insert the item. */ 382321936Shselasky if (p_insert_at == &p_map->root) { 383321936Shselasky p_insert_at->p_left = p_item; 384321936Shselasky /* 385321936Shselasky * Primitive insert places the new item in front of 386321936Shselasky * the existing item. 387321936Shselasky */ 388321936Shselasky __cl_primitive_insert(&p_map->nil.pool_item.list_item, 389321936Shselasky &p_item->pool_item.list_item); 390321936Shselasky } else if (key < p_insert_at->key) { 391321936Shselasky p_insert_at->p_left = p_item; 392321936Shselasky /* 393321936Shselasky * Primitive insert places the new item in front of 394321936Shselasky * the existing item. 395321936Shselasky */ 396321936Shselasky __cl_primitive_insert(&p_insert_at->pool_item.list_item, 397321936Shselasky &p_item->pool_item.list_item); 398321936Shselasky } else { 399321936Shselasky p_insert_at->p_right = p_item; 400321936Shselasky /* 401321936Shselasky * Primitive insert places the new item in front of 402321936Shselasky * the existing item. 403321936Shselasky */ 404321936Shselasky __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next, 405321936Shselasky &p_item->pool_item.list_item); 406321936Shselasky } 407321936Shselasky /* Increase the count. */ 408321936Shselasky p_map->count++; 409321936Shselasky 410321936Shselasky p_item->p_up = p_insert_at; 411321936Shselasky 412321936Shselasky /* 413321936Shselasky * We have added depth to this section of the tree. 414321936Shselasky * Rebalance as necessary as we retrace our path through the tree 415321936Shselasky * and update colors. 416321936Shselasky */ 417321936Shselasky __cl_map_ins_bal(p_map, p_item); 418321936Shselasky 419321936Shselasky __cl_map_root(p_map)->color = CL_MAP_BLACK; 420321936Shselasky 421321936Shselasky /* 422321936Shselasky * Note that it is not necessary to re-color the nil node black because all 423321936Shselasky * red color assignments are made via the p_up pointer, and nil is never 424321936Shselasky * set as the value of a p_up pointer. 425321936Shselasky */ 426321936Shselasky 427321936Shselasky#ifdef _DEBUG_ 428321936Shselasky /* Set the pointer to the map in the map item for consistency checking. */ 429321936Shselasky p_item->p_map = p_map; 430321936Shselasky#endif 431321936Shselasky 432321936Shselasky return (p_item); 433321936Shselasky} 434321936Shselasky 435321936Shselaskystatic void __cl_map_del_bal(IN cl_qmap_t * const p_map, 436321936Shselasky IN cl_map_item_t * p_item) 437321936Shselasky{ 438321936Shselasky cl_map_item_t *p_uncle; 439321936Shselasky 440321936Shselasky while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) { 441321936Shselasky if (__cl_map_is_left_child(p_item)) { 442321936Shselasky p_uncle = p_item->p_up->p_right; 443321936Shselasky 444321936Shselasky if (p_uncle->color == CL_MAP_RED) { 445321936Shselasky p_uncle->color = CL_MAP_BLACK; 446321936Shselasky p_item->p_up->color = CL_MAP_RED; 447321936Shselasky __cl_map_rot_left(p_map, p_item->p_up); 448321936Shselasky p_uncle = p_item->p_up->p_right; 449321936Shselasky } 450321936Shselasky 451321936Shselasky if (p_uncle->p_right->color != CL_MAP_RED) { 452321936Shselasky if (p_uncle->p_left->color != CL_MAP_RED) { 453321936Shselasky p_uncle->color = CL_MAP_RED; 454321936Shselasky p_item = p_item->p_up; 455321936Shselasky continue; 456321936Shselasky } 457321936Shselasky 458321936Shselasky p_uncle->p_left->color = CL_MAP_BLACK; 459321936Shselasky p_uncle->color = CL_MAP_RED; 460321936Shselasky __cl_map_rot_right(p_map, p_uncle); 461321936Shselasky p_uncle = p_item->p_up->p_right; 462321936Shselasky } 463321936Shselasky p_uncle->color = p_item->p_up->color; 464321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 465321936Shselasky p_uncle->p_right->color = CL_MAP_BLACK; 466321936Shselasky __cl_map_rot_left(p_map, p_item->p_up); 467321936Shselasky break; 468321936Shselasky } else { 469321936Shselasky p_uncle = p_item->p_up->p_left; 470321936Shselasky 471321936Shselasky if (p_uncle->color == CL_MAP_RED) { 472321936Shselasky p_uncle->color = CL_MAP_BLACK; 473321936Shselasky p_item->p_up->color = CL_MAP_RED; 474321936Shselasky __cl_map_rot_right(p_map, p_item->p_up); 475321936Shselasky p_uncle = p_item->p_up->p_left; 476321936Shselasky } 477321936Shselasky 478321936Shselasky if (p_uncle->p_left->color != CL_MAP_RED) { 479321936Shselasky if (p_uncle->p_right->color != CL_MAP_RED) { 480321936Shselasky p_uncle->color = CL_MAP_RED; 481321936Shselasky p_item = p_item->p_up; 482321936Shselasky continue; 483321936Shselasky } 484321936Shselasky 485321936Shselasky p_uncle->p_right->color = CL_MAP_BLACK; 486321936Shselasky p_uncle->color = CL_MAP_RED; 487321936Shselasky __cl_map_rot_left(p_map, p_uncle); 488321936Shselasky p_uncle = p_item->p_up->p_left; 489321936Shselasky } 490321936Shselasky p_uncle->color = p_item->p_up->color; 491321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 492321936Shselasky p_uncle->p_left->color = CL_MAP_BLACK; 493321936Shselasky __cl_map_rot_right(p_map, p_item->p_up); 494321936Shselasky break; 495321936Shselasky } 496321936Shselasky } 497321936Shselasky p_item->color = CL_MAP_BLACK; 498321936Shselasky} 499321936Shselasky 500321936Shselaskyvoid cl_qmap_remove_item(IN cl_qmap_t * const p_map, 501321936Shselasky IN cl_map_item_t * const p_item) 502321936Shselasky{ 503321936Shselasky cl_map_item_t *p_child, *p_del_item; 504321936Shselasky 505321936Shselasky CL_ASSERT(p_map); 506321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 507321936Shselasky CL_ASSERT(p_item); 508321936Shselasky 509321936Shselasky if (p_item == cl_qmap_end(p_map)) 510321936Shselasky return; 511321936Shselasky 512321936Shselasky /* must be checked after comparing to cl_qmap_end, since 513321936Shselasky the end is not a valid item. */ 514321936Shselasky CL_ASSERT(p_item->p_map == p_map); 515321936Shselasky 516321936Shselasky if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) { 517321936Shselasky /* The item being removed has children on at most on side. */ 518321936Shselasky p_del_item = p_item; 519321936Shselasky } else { 520321936Shselasky /* 521321936Shselasky * The item being removed has children on both side. 522321936Shselasky * We select the item that will replace it. After removing 523321936Shselasky * the substitute item and rebalancing, the tree will have the 524321936Shselasky * correct topology. Exchanging the substitute for the item 525321936Shselasky * will finalize the removal. 526321936Shselasky */ 527321936Shselasky p_del_item = cl_qmap_next(p_item); 528321936Shselasky CL_ASSERT(p_del_item != &p_map->nil); 529321936Shselasky } 530321936Shselasky 531321936Shselasky /* Remove the item from the list. */ 532321936Shselasky __cl_primitive_remove(&p_item->pool_item.list_item); 533321936Shselasky /* Decrement the item count. */ 534321936Shselasky p_map->count--; 535321936Shselasky 536321936Shselasky /* Get the pointer to the new root's child, if any. */ 537321936Shselasky if (p_del_item->p_left != &p_map->nil) 538321936Shselasky p_child = p_del_item->p_left; 539321936Shselasky else 540321936Shselasky p_child = p_del_item->p_right; 541321936Shselasky 542321936Shselasky /* 543321936Shselasky * This assignment may modify the parent pointer of the nil node. 544321936Shselasky * This is inconsequential. 545321936Shselasky */ 546321936Shselasky p_child->p_up = p_del_item->p_up; 547321936Shselasky (*__cl_map_get_parent_ptr_to_item(p_del_item)) = p_child; 548321936Shselasky 549321936Shselasky if (p_del_item->color != CL_MAP_RED) 550321936Shselasky __cl_map_del_bal(p_map, p_child); 551321936Shselasky 552321936Shselasky /* 553321936Shselasky * Note that the splicing done below does not need to occur before 554321936Shselasky * the tree is balanced, since the actual topology changes are made by the 555321936Shselasky * preceding code. The topology is preserved by the color assignment made 556321936Shselasky * below (reader should be reminded that p_del_item == p_item in some cases). 557321936Shselasky */ 558321936Shselasky if (p_del_item != p_item) { 559321936Shselasky /* 560321936Shselasky * Finalize the removal of the specified item by exchanging it with 561321936Shselasky * the substitute which we removed above. 562321936Shselasky */ 563321936Shselasky p_del_item->p_up = p_item->p_up; 564321936Shselasky p_del_item->p_left = p_item->p_left; 565321936Shselasky p_del_item->p_right = p_item->p_right; 566321936Shselasky (*__cl_map_get_parent_ptr_to_item(p_item)) = p_del_item; 567321936Shselasky p_item->p_right->p_up = p_del_item; 568321936Shselasky p_item->p_left->p_up = p_del_item; 569321936Shselasky p_del_item->color = p_item->color; 570321936Shselasky } 571321936Shselasky 572321936Shselasky CL_ASSERT(p_map->nil.color != CL_MAP_RED); 573321936Shselasky 574321936Shselasky#ifdef _DEBUG_ 575321936Shselasky /* Clear the pointer to the map since the item has been removed. */ 576321936Shselasky p_item->p_map = NULL; 577321936Shselasky#endif 578321936Shselasky} 579321936Shselasky 580321936Shselaskycl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, IN const uint64_t key) 581321936Shselasky{ 582321936Shselasky cl_map_item_t *p_item; 583321936Shselasky 584321936Shselasky CL_ASSERT(p_map); 585321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 586321936Shselasky 587321936Shselasky /* Seek the node with the specified key */ 588321936Shselasky p_item = cl_qmap_get(p_map, key); 589321936Shselasky 590321936Shselasky cl_qmap_remove_item(p_map, p_item); 591321936Shselasky 592321936Shselasky return (p_item); 593321936Shselasky} 594321936Shselasky 595321936Shselaskyvoid cl_qmap_merge(OUT cl_qmap_t * const p_dest_map, 596321936Shselasky IN OUT cl_qmap_t * const p_src_map) 597321936Shselasky{ 598321936Shselasky cl_map_item_t *p_item, *p_item2, *p_next; 599321936Shselasky 600321936Shselasky CL_ASSERT(p_dest_map); 601321936Shselasky CL_ASSERT(p_src_map); 602321936Shselasky 603321936Shselasky p_item = cl_qmap_head(p_src_map); 604321936Shselasky 605321936Shselasky while (p_item != cl_qmap_end(p_src_map)) { 606321936Shselasky p_next = cl_qmap_next(p_item); 607321936Shselasky 608321936Shselasky /* Remove the item from its current map. */ 609321936Shselasky cl_qmap_remove_item(p_src_map, p_item); 610321936Shselasky /* Insert the item into the destination map. */ 611321936Shselasky p_item2 = 612321936Shselasky cl_qmap_insert(p_dest_map, cl_qmap_key(p_item), p_item); 613321936Shselasky /* Check that the item was successfully inserted. */ 614321936Shselasky if (p_item2 != p_item) { 615321936Shselasky /* Put the item in back in the source map. */ 616321936Shselasky p_item2 = 617321936Shselasky cl_qmap_insert(p_src_map, cl_qmap_key(p_item), 618321936Shselasky p_item); 619321936Shselasky CL_ASSERT(p_item2 == p_item); 620321936Shselasky } 621321936Shselasky p_item = p_next; 622321936Shselasky } 623321936Shselasky} 624321936Shselasky 625321936Shselaskystatic void __cl_qmap_delta_move(IN OUT cl_qmap_t * const p_dest, 626321936Shselasky IN OUT cl_qmap_t * const p_src, 627321936Shselasky IN OUT cl_map_item_t ** const pp_item) 628321936Shselasky{ 629321936Shselasky cl_map_item_t __attribute__((__unused__)) *p_temp; 630321936Shselasky cl_map_item_t *p_next; 631321936Shselasky 632321936Shselasky /* 633321936Shselasky * Get the next item so that we can ensure that pp_item points to 634321936Shselasky * a valid item upon return from the function. 635321936Shselasky */ 636321936Shselasky p_next = cl_qmap_next(*pp_item); 637321936Shselasky /* Move the old item from its current map the the old map. */ 638321936Shselasky cl_qmap_remove_item(p_src, *pp_item); 639321936Shselasky p_temp = cl_qmap_insert(p_dest, cl_qmap_key(*pp_item), *pp_item); 640321936Shselasky /* We should never have duplicates. */ 641321936Shselasky CL_ASSERT(p_temp == *pp_item); 642321936Shselasky /* Point pp_item to a valid item in the source map. */ 643321936Shselasky (*pp_item) = p_next; 644321936Shselasky} 645321936Shselasky 646321936Shselaskyvoid cl_qmap_delta(IN OUT cl_qmap_t * const p_map1, 647321936Shselasky IN OUT cl_qmap_t * const p_map2, 648321936Shselasky OUT cl_qmap_t * const p_new, OUT cl_qmap_t * const p_old) 649321936Shselasky{ 650321936Shselasky cl_map_item_t *p_item1, *p_item2; 651321936Shselasky uint64_t key1, key2; 652321936Shselasky 653321936Shselasky CL_ASSERT(p_map1); 654321936Shselasky CL_ASSERT(p_map2); 655321936Shselasky CL_ASSERT(p_new); 656321936Shselasky CL_ASSERT(p_old); 657321936Shselasky CL_ASSERT(cl_is_qmap_empty(p_new)); 658321936Shselasky CL_ASSERT(cl_is_qmap_empty(p_old)); 659321936Shselasky 660321936Shselasky p_item1 = cl_qmap_head(p_map1); 661321936Shselasky p_item2 = cl_qmap_head(p_map2); 662321936Shselasky 663321936Shselasky while (p_item1 != cl_qmap_end(p_map1) && p_item2 != cl_qmap_end(p_map2)) { 664321936Shselasky key1 = cl_qmap_key(p_item1); 665321936Shselasky key2 = cl_qmap_key(p_item2); 666321936Shselasky if (key1 < key2) { 667321936Shselasky /* We found an old item. */ 668321936Shselasky __cl_qmap_delta_move(p_old, p_map1, &p_item1); 669321936Shselasky } else if (key1 > key2) { 670321936Shselasky /* We found a new item. */ 671321936Shselasky __cl_qmap_delta_move(p_new, p_map2, &p_item2); 672321936Shselasky } else { 673321936Shselasky /* Move both forward since they have the same key. */ 674321936Shselasky p_item1 = cl_qmap_next(p_item1); 675321936Shselasky p_item2 = cl_qmap_next(p_item2); 676321936Shselasky } 677321936Shselasky } 678321936Shselasky 679321936Shselasky /* Process the remainder if the end of either source map was reached. */ 680321936Shselasky while (p_item2 != cl_qmap_end(p_map2)) 681321936Shselasky __cl_qmap_delta_move(p_new, p_map2, &p_item2); 682321936Shselasky 683321936Shselasky while (p_item1 != cl_qmap_end(p_map1)) 684321936Shselasky __cl_qmap_delta_move(p_old, p_map1, &p_item1); 685321936Shselasky} 686321936Shselasky 687321936Shselasky/****************************************************************************** 688321936Shselasky IMPLEMENTATION OF MAP 689321936Shselasky******************************************************************************/ 690321936Shselasky 691321936Shselasky#define MAP_GROW_SIZE 32 692321936Shselasky 693321936Shselaskyvoid cl_map_construct(IN cl_map_t * const p_map) 694321936Shselasky{ 695321936Shselasky CL_ASSERT(p_map); 696321936Shselasky 697321936Shselasky cl_qpool_construct(&p_map->pool); 698321936Shselasky} 699321936Shselasky 700321936Shselaskycl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items) 701321936Shselasky{ 702321936Shselasky uint32_t grow_size; 703321936Shselasky 704321936Shselasky CL_ASSERT(p_map); 705321936Shselasky 706321936Shselasky cl_qmap_init(&p_map->qmap); 707321936Shselasky 708321936Shselasky /* 709321936Shselasky * We will grow by min_items/8 items at a time, with a minimum of 710321936Shselasky * MAP_GROW_SIZE. 711321936Shselasky */ 712321936Shselasky grow_size = min_items >> 3; 713321936Shselasky if (grow_size < MAP_GROW_SIZE) 714321936Shselasky grow_size = MAP_GROW_SIZE; 715321936Shselasky 716321936Shselasky return (cl_qpool_init(&p_map->pool, min_items, 0, grow_size, 717321936Shselasky sizeof(cl_map_obj_t), NULL, NULL, NULL)); 718321936Shselasky} 719321936Shselasky 720321936Shselaskyvoid cl_map_destroy(IN cl_map_t * const p_map) 721321936Shselasky{ 722321936Shselasky CL_ASSERT(p_map); 723321936Shselasky 724321936Shselasky cl_qpool_destroy(&p_map->pool); 725321936Shselasky} 726321936Shselasky 727321936Shselaskyvoid *cl_map_insert(IN cl_map_t * const p_map, 728321936Shselasky IN const uint64_t key, IN const void *const p_object) 729321936Shselasky{ 730321936Shselasky cl_map_obj_t *p_map_obj, *p_obj_at_key; 731321936Shselasky 732321936Shselasky CL_ASSERT(p_map); 733321936Shselasky 734321936Shselasky p_map_obj = (cl_map_obj_t *) cl_qpool_get(&p_map->pool); 735321936Shselasky 736321936Shselasky if (!p_map_obj) 737321936Shselasky return (NULL); 738321936Shselasky 739321936Shselasky cl_qmap_set_obj(p_map_obj, p_object); 740321936Shselasky 741321936Shselasky p_obj_at_key = 742321936Shselasky (cl_map_obj_t *) cl_qmap_insert(&p_map->qmap, key, 743321936Shselasky &p_map_obj->item); 744321936Shselasky 745321936Shselasky /* Return the item to the pool if insertion failed. */ 746321936Shselasky if (p_obj_at_key != p_map_obj) 747321936Shselasky cl_qpool_put(&p_map->pool, &p_map_obj->item.pool_item); 748321936Shselasky 749321936Shselasky return (cl_qmap_obj(p_obj_at_key)); 750321936Shselasky} 751321936Shselasky 752321936Shselaskyvoid *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key) 753321936Shselasky{ 754321936Shselasky cl_map_item_t *p_item; 755321936Shselasky 756321936Shselasky CL_ASSERT(p_map); 757321936Shselasky 758321936Shselasky p_item = cl_qmap_get(&p_map->qmap, key); 759321936Shselasky 760321936Shselasky if (p_item == cl_qmap_end(&p_map->qmap)) 761321936Shselasky return (NULL); 762321936Shselasky 763321936Shselasky return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item))); 764321936Shselasky} 765321936Shselasky 766321936Shselaskyvoid *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key) 767321936Shselasky{ 768321936Shselasky cl_map_item_t *p_item; 769321936Shselasky 770321936Shselasky CL_ASSERT(p_map); 771321936Shselasky 772321936Shselasky p_item = cl_qmap_get_next(&p_map->qmap, key); 773321936Shselasky 774321936Shselasky if (p_item == cl_qmap_end(&p_map->qmap)) 775321936Shselasky return (NULL); 776321936Shselasky 777321936Shselasky return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item))); 778321936Shselasky} 779321936Shselasky 780321936Shselaskyvoid cl_map_remove_item(IN cl_map_t * const p_map, 781321936Shselasky IN const cl_map_iterator_t itor) 782321936Shselasky{ 783321936Shselasky CL_ASSERT(itor->p_map == &p_map->qmap); 784321936Shselasky 785321936Shselasky if (itor == cl_map_end(p_map)) 786321936Shselasky return; 787321936Shselasky 788321936Shselasky cl_qmap_remove_item(&p_map->qmap, (cl_map_item_t *) itor); 789321936Shselasky cl_qpool_put(&p_map->pool, &((cl_map_item_t *) itor)->pool_item); 790321936Shselasky} 791321936Shselasky 792321936Shselaskyvoid *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key) 793321936Shselasky{ 794321936Shselasky cl_map_item_t *p_item; 795321936Shselasky void *p_obj; 796321936Shselasky 797321936Shselasky CL_ASSERT(p_map); 798321936Shselasky 799321936Shselasky p_item = cl_qmap_remove(&p_map->qmap, key); 800321936Shselasky 801321936Shselasky if (p_item == cl_qmap_end(&p_map->qmap)) 802321936Shselasky return (NULL); 803321936Shselasky 804321936Shselasky p_obj = cl_qmap_obj((cl_map_obj_t *) p_item); 805321936Shselasky cl_qpool_put(&p_map->pool, &p_item->pool_item); 806321936Shselasky 807321936Shselasky return (p_obj); 808321936Shselasky} 809321936Shselasky 810321936Shselaskyvoid cl_map_remove_all(IN cl_map_t * const p_map) 811321936Shselasky{ 812321936Shselasky cl_map_item_t *p_item; 813321936Shselasky 814321936Shselasky CL_ASSERT(p_map); 815321936Shselasky 816321936Shselasky /* Return all map items to the pool. */ 817321936Shselasky while (!cl_is_qmap_empty(&p_map->qmap)) { 818321936Shselasky p_item = cl_qmap_head(&p_map->qmap); 819321936Shselasky cl_qmap_remove_item(&p_map->qmap, p_item); 820321936Shselasky cl_qpool_put(&p_map->pool, &p_item->pool_item); 821321936Shselasky 822321936Shselasky if (!cl_is_qmap_empty(&p_map->qmap)) { 823321936Shselasky p_item = cl_qmap_tail(&p_map->qmap); 824321936Shselasky cl_qmap_remove_item(&p_map->qmap, p_item); 825321936Shselasky cl_qpool_put(&p_map->pool, &p_item->pool_item); 826321936Shselasky } 827321936Shselasky } 828321936Shselasky} 829321936Shselasky 830321936Shselaskycl_status_t cl_map_merge(OUT cl_map_t * const p_dest_map, 831321936Shselasky IN OUT cl_map_t * const p_src_map) 832321936Shselasky{ 833321936Shselasky cl_status_t status = CL_SUCCESS; 834321936Shselasky cl_map_iterator_t itor, next; 835321936Shselasky uint64_t key; 836321936Shselasky void *p_obj, *p_obj2; 837321936Shselasky 838321936Shselasky CL_ASSERT(p_dest_map); 839321936Shselasky CL_ASSERT(p_src_map); 840321936Shselasky 841321936Shselasky itor = cl_map_head(p_src_map); 842321936Shselasky while (itor != cl_map_end(p_src_map)) { 843321936Shselasky next = cl_map_next(itor); 844321936Shselasky 845321936Shselasky p_obj = cl_map_obj(itor); 846321936Shselasky key = cl_map_key(itor); 847321936Shselasky 848321936Shselasky cl_map_remove_item(p_src_map, itor); 849321936Shselasky 850321936Shselasky /* Insert the object into the destination map. */ 851321936Shselasky p_obj2 = cl_map_insert(p_dest_map, key, p_obj); 852321936Shselasky /* Trap for failure. */ 853321936Shselasky if (p_obj != p_obj2) { 854321936Shselasky if (!p_obj2) 855321936Shselasky status = CL_INSUFFICIENT_MEMORY; 856321936Shselasky /* Put the object back in the source map. This must succeed. */ 857321936Shselasky p_obj2 = cl_map_insert(p_src_map, key, p_obj); 858321936Shselasky CL_ASSERT(p_obj == p_obj2); 859321936Shselasky /* If the failure was due to insufficient memory, return. */ 860321936Shselasky if (status != CL_SUCCESS) 861321936Shselasky return (status); 862321936Shselasky } 863321936Shselasky itor = next; 864321936Shselasky } 865321936Shselasky 866321936Shselasky return (CL_SUCCESS); 867321936Shselasky} 868321936Shselasky 869321936Shselaskystatic void __cl_map_revert(IN OUT cl_map_t * const p_map1, 870321936Shselasky IN OUT cl_map_t * const p_map2, 871321936Shselasky IN OUT cl_map_t * const p_new, 872321936Shselasky IN OUT cl_map_t * const p_old) 873321936Shselasky{ 874321936Shselasky cl_status_t __attribute__((__unused__)) status; 875321936Shselasky 876321936Shselasky /* Restore the initial state. */ 877321936Shselasky status = cl_map_merge(p_map1, p_old); 878321936Shselasky CL_ASSERT(status == CL_SUCCESS); 879321936Shselasky status = cl_map_merge(p_map2, p_new); 880321936Shselasky CL_ASSERT(status == CL_SUCCESS); 881321936Shselasky} 882321936Shselasky 883321936Shselaskystatic cl_status_t __cl_map_delta_move(OUT cl_map_t * const p_dest, 884321936Shselasky IN OUT cl_map_t * const p_src, 885321936Shselasky IN OUT cl_map_iterator_t * const p_itor) 886321936Shselasky{ 887321936Shselasky cl_map_iterator_t next; 888321936Shselasky void *p_obj, *p_obj2; 889321936Shselasky uint64_t key; 890321936Shselasky 891321936Shselasky /* Get a valid iterator so we can continue the loop. */ 892321936Shselasky next = cl_map_next(*p_itor); 893321936Shselasky /* Get the pointer to the object for insertion. */ 894321936Shselasky p_obj = cl_map_obj(*p_itor); 895321936Shselasky /* Get the key for the object. */ 896321936Shselasky key = cl_map_key(*p_itor); 897321936Shselasky /* Move the object. */ 898321936Shselasky cl_map_remove_item(p_src, *p_itor); 899321936Shselasky p_obj2 = cl_map_insert(p_dest, key, p_obj); 900321936Shselasky /* Check for failure. We should never get a duplicate. */ 901321936Shselasky if (!p_obj2) { 902321936Shselasky p_obj2 = cl_map_insert(p_src, key, p_obj); 903321936Shselasky CL_ASSERT(p_obj2 == p_obj); 904321936Shselasky return (CL_INSUFFICIENT_MEMORY); 905321936Shselasky } 906321936Shselasky 907321936Shselasky /* We should never get a duplicate */ 908321936Shselasky CL_ASSERT(p_obj == p_obj2); 909321936Shselasky /* Update the iterator so that it is valid. */ 910321936Shselasky (*p_itor) = next; 911321936Shselasky 912321936Shselasky return (CL_SUCCESS); 913321936Shselasky} 914321936Shselasky 915321936Shselaskycl_status_t cl_map_delta(IN OUT cl_map_t * const p_map1, 916321936Shselasky IN OUT cl_map_t * const p_map2, 917321936Shselasky OUT cl_map_t * const p_new, OUT cl_map_t * const p_old) 918321936Shselasky{ 919321936Shselasky cl_map_iterator_t itor1, itor2; 920321936Shselasky uint64_t key1, key2; 921321936Shselasky cl_status_t status; 922321936Shselasky 923321936Shselasky CL_ASSERT(p_map1); 924321936Shselasky CL_ASSERT(p_map2); 925321936Shselasky CL_ASSERT(p_new); 926321936Shselasky CL_ASSERT(p_old); 927321936Shselasky CL_ASSERT(cl_is_map_empty(p_new)); 928321936Shselasky CL_ASSERT(cl_is_map_empty(p_old)); 929321936Shselasky 930321936Shselasky itor1 = cl_map_head(p_map1); 931321936Shselasky itor2 = cl_map_head(p_map2); 932321936Shselasky 933321936Shselasky /* 934321936Shselasky * Note that the check is for the end, since duplicate items will remain 935321936Shselasky * in their respective maps. 936321936Shselasky */ 937321936Shselasky while (itor1 != cl_map_end(p_map1) && itor2 != cl_map_end(p_map2)) { 938321936Shselasky key1 = cl_map_key(itor1); 939321936Shselasky key2 = cl_map_key(itor2); 940321936Shselasky if (key1 < key2) { 941321936Shselasky status = __cl_map_delta_move(p_old, p_map1, &itor1); 942321936Shselasky /* Check for failure. */ 943321936Shselasky if (status != CL_SUCCESS) { 944321936Shselasky /* Restore the initial state. */ 945321936Shselasky __cl_map_revert(p_map1, p_map2, p_new, p_old); 946321936Shselasky /* Return the failure status. */ 947321936Shselasky return (status); 948321936Shselasky } 949321936Shselasky } else if (key1 > key2) { 950321936Shselasky status = __cl_map_delta_move(p_new, p_map2, &itor2); 951321936Shselasky if (status != CL_SUCCESS) { 952321936Shselasky /* Restore the initial state. */ 953321936Shselasky __cl_map_revert(p_map1, p_map2, p_new, p_old); 954321936Shselasky /* Return the failure status. */ 955321936Shselasky return (status); 956321936Shselasky } 957321936Shselasky } else { 958321936Shselasky /* Move both forward since they have the same key. */ 959321936Shselasky itor1 = cl_map_next(itor1); 960321936Shselasky itor2 = cl_map_next(itor2); 961321936Shselasky } 962321936Shselasky } 963321936Shselasky 964321936Shselasky /* Process the remainder if either source map is empty. */ 965321936Shselasky while (itor2 != cl_map_end(p_map2)) { 966321936Shselasky status = __cl_map_delta_move(p_new, p_map2, &itor2); 967321936Shselasky if (status != CL_SUCCESS) { 968321936Shselasky /* Restore the initial state. */ 969321936Shselasky __cl_map_revert(p_map1, p_map2, p_new, p_old); 970321936Shselasky /* Return the failure status. */ 971321936Shselasky return (status); 972321936Shselasky } 973321936Shselasky } 974321936Shselasky 975321936Shselasky while (itor1 != cl_map_end(p_map1)) { 976321936Shselasky status = __cl_map_delta_move(p_old, p_map1, &itor1); 977321936Shselasky if (status != CL_SUCCESS) { 978321936Shselasky /* Restore the initial state. */ 979321936Shselasky __cl_map_revert(p_map1, p_map2, p_new, p_old); 980321936Shselasky /* Return the failure status. */ 981321936Shselasky return (status); 982321936Shselasky } 983321936Shselasky } 984321936Shselasky 985321936Shselasky return (CL_SUCCESS); 986321936Shselasky} 987321936Shselasky 988321936Shselasky/****************************************************************************** 989321936Shselasky IMPLEMENTATION OF FLEXI MAP 990321936Shselasky******************************************************************************/ 991321936Shselasky 992321936Shselasky/* 993321936Shselasky * Get the root. 994321936Shselasky */ 995321936Shselaskystatic inline cl_fmap_item_t *__cl_fmap_root(IN const cl_fmap_t * const p_map) 996321936Shselasky{ 997321936Shselasky CL_ASSERT(p_map); 998321936Shselasky return (p_map->root.p_left); 999321936Shselasky} 1000321936Shselasky 1001321936Shselasky/* 1002321936Shselasky * Returns whether a given item is on the left of its parent. 1003321936Shselasky */ 1004321936Shselaskystatic boolean_t __cl_fmap_is_left_child(IN const cl_fmap_item_t * const p_item) 1005321936Shselasky{ 1006321936Shselasky CL_ASSERT(p_item); 1007321936Shselasky CL_ASSERT(p_item->p_up); 1008321936Shselasky CL_ASSERT(p_item->p_up != p_item); 1009321936Shselasky 1010321936Shselasky return (p_item->p_up->p_left == p_item); 1011321936Shselasky} 1012321936Shselasky 1013321936Shselasky/* 1014321936Shselasky * Retrieve the pointer to the parent's pointer to an item. 1015321936Shselasky */ 1016321936Shselaskystatic cl_fmap_item_t **__cl_fmap_get_parent_ptr_to_item(IN cl_fmap_item_t * 1017321936Shselasky const p_item) 1018321936Shselasky{ 1019321936Shselasky CL_ASSERT(p_item); 1020321936Shselasky CL_ASSERT(p_item->p_up); 1021321936Shselasky CL_ASSERT(p_item->p_up != p_item); 1022321936Shselasky 1023321936Shselasky if (__cl_fmap_is_left_child(p_item)) 1024321936Shselasky return (&p_item->p_up->p_left); 1025321936Shselasky 1026321936Shselasky CL_ASSERT(p_item->p_up->p_right == p_item); 1027321936Shselasky return (&p_item->p_up->p_right); 1028321936Shselasky} 1029321936Shselasky 1030321936Shselasky/* 1031321936Shselasky * Rotate a node to the left. This rotation affects the least number of links 1032321936Shselasky * between nodes and brings the level of C up by one while increasing the depth 1033321936Shselasky * of A one. Note that the links to/from W, X, Y, and Z are not affected. 1034321936Shselasky * 1035321936Shselasky * R R 1036321936Shselasky * | | 1037321936Shselasky * A C 1038321936Shselasky * / \ / \ 1039321936Shselasky * W C A Z 1040321936Shselasky * / \ / \ 1041321936Shselasky * B Z W B 1042321936Shselasky * / \ / \ 1043321936Shselasky * X Y X Y 1044321936Shselasky */ 1045321936Shselaskystatic void __cl_fmap_rot_left(IN cl_fmap_t * const p_map, 1046321936Shselasky IN cl_fmap_item_t * const p_item) 1047321936Shselasky{ 1048321936Shselasky cl_fmap_item_t **pp_root; 1049321936Shselasky 1050321936Shselasky CL_ASSERT(p_map); 1051321936Shselasky CL_ASSERT(p_item); 1052321936Shselasky CL_ASSERT(p_item->p_right != &p_map->nil); 1053321936Shselasky 1054321936Shselasky pp_root = __cl_fmap_get_parent_ptr_to_item(p_item); 1055321936Shselasky 1056321936Shselasky /* Point R to C instead of A. */ 1057321936Shselasky *pp_root = p_item->p_right; 1058321936Shselasky /* Set C's parent to R. */ 1059321936Shselasky (*pp_root)->p_up = p_item->p_up; 1060321936Shselasky 1061321936Shselasky /* Set A's right to B */ 1062321936Shselasky p_item->p_right = (*pp_root)->p_left; 1063321936Shselasky /* 1064321936Shselasky * Set B's parent to A. We trap for B being NIL since the 1065321936Shselasky * caller may depend on NIL not changing. 1066321936Shselasky */ 1067321936Shselasky if ((*pp_root)->p_left != &p_map->nil) 1068321936Shselasky (*pp_root)->p_left->p_up = p_item; 1069321936Shselasky 1070321936Shselasky /* Set C's left to A. */ 1071321936Shselasky (*pp_root)->p_left = p_item; 1072321936Shselasky /* Set A's parent to C. */ 1073321936Shselasky p_item->p_up = *pp_root; 1074321936Shselasky} 1075321936Shselasky 1076321936Shselasky/* 1077321936Shselasky * Rotate a node to the right. This rotation affects the least number of links 1078321936Shselasky * between nodes and brings the level of A up by one while increasing the depth 1079321936Shselasky * of C one. Note that the links to/from W, X, Y, and Z are not affected. 1080321936Shselasky * 1081321936Shselasky * R R 1082321936Shselasky * | | 1083321936Shselasky * C A 1084321936Shselasky * / \ / \ 1085321936Shselasky * A Z W C 1086321936Shselasky * / \ / \ 1087321936Shselasky * W B B Z 1088321936Shselasky * / \ / \ 1089321936Shselasky * X Y X Y 1090321936Shselasky */ 1091321936Shselaskystatic void __cl_fmap_rot_right(IN cl_fmap_t * const p_map, 1092321936Shselasky IN cl_fmap_item_t * const p_item) 1093321936Shselasky{ 1094321936Shselasky cl_fmap_item_t **pp_root; 1095321936Shselasky 1096321936Shselasky CL_ASSERT(p_map); 1097321936Shselasky CL_ASSERT(p_item); 1098321936Shselasky CL_ASSERT(p_item->p_left != &p_map->nil); 1099321936Shselasky 1100321936Shselasky /* Point R to A instead of C. */ 1101321936Shselasky pp_root = __cl_fmap_get_parent_ptr_to_item(p_item); 1102321936Shselasky (*pp_root) = p_item->p_left; 1103321936Shselasky /* Set A's parent to R. */ 1104321936Shselasky (*pp_root)->p_up = p_item->p_up; 1105321936Shselasky 1106321936Shselasky /* Set C's left to B */ 1107321936Shselasky p_item->p_left = (*pp_root)->p_right; 1108321936Shselasky /* 1109321936Shselasky * Set B's parent to C. We trap for B being NIL since the 1110321936Shselasky * caller may depend on NIL not changing. 1111321936Shselasky */ 1112321936Shselasky if ((*pp_root)->p_right != &p_map->nil) 1113321936Shselasky (*pp_root)->p_right->p_up = p_item; 1114321936Shselasky 1115321936Shselasky /* Set A's right to C. */ 1116321936Shselasky (*pp_root)->p_right = p_item; 1117321936Shselasky /* Set C's parent to A. */ 1118321936Shselasky p_item->p_up = *pp_root; 1119321936Shselasky} 1120321936Shselasky 1121321936Shselaskyvoid cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare) 1122321936Shselasky{ 1123321936Shselasky CL_ASSERT(p_map); 1124321936Shselasky CL_ASSERT(pfn_compare); 1125321936Shselasky 1126321936Shselasky memset(p_map, 0, sizeof(cl_fmap_t)); 1127321936Shselasky 1128321936Shselasky /* special setup for the root node */ 1129321936Shselasky p_map->root.p_up = &p_map->root; 1130321936Shselasky p_map->root.p_left = &p_map->nil; 1131321936Shselasky p_map->root.p_right = &p_map->nil; 1132321936Shselasky p_map->root.color = CL_MAP_BLACK; 1133321936Shselasky 1134321936Shselasky /* Setup the node used as terminator for all leaves. */ 1135321936Shselasky p_map->nil.p_up = &p_map->nil; 1136321936Shselasky p_map->nil.p_left = &p_map->nil; 1137321936Shselasky p_map->nil.p_right = &p_map->nil; 1138321936Shselasky p_map->nil.color = CL_MAP_BLACK; 1139321936Shselasky 1140321936Shselasky /* Store the compare function pointer. */ 1141321936Shselasky p_map->pfn_compare = pfn_compare; 1142321936Shselasky 1143321936Shselasky p_map->state = CL_INITIALIZED; 1144321936Shselasky 1145321936Shselasky cl_fmap_remove_all(p_map); 1146321936Shselasky} 1147321936Shselasky 1148321936Shselaskycl_fmap_item_t *cl_fmap_match(IN const cl_fmap_t * const p_map, 1149321936Shselasky IN const void *const p_key, 1150321936Shselasky IN cl_pfn_fmap_cmp_t pfn_compare) 1151321936Shselasky{ 1152321936Shselasky cl_fmap_item_t *p_item; 1153321936Shselasky int cmp; 1154321936Shselasky 1155321936Shselasky CL_ASSERT(p_map); 1156321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 1157321936Shselasky 1158321936Shselasky p_item = __cl_fmap_root(p_map); 1159321936Shselasky 1160321936Shselasky while (p_item != &p_map->nil) { 1161321936Shselasky cmp = pfn_compare ? pfn_compare(p_key, p_item->p_key) : 1162321936Shselasky p_map->pfn_compare(p_key, p_item->p_key); 1163321936Shselasky 1164321936Shselasky if (!cmp) 1165321936Shselasky break; /* just right */ 1166321936Shselasky 1167321936Shselasky if (cmp < 0) 1168321936Shselasky p_item = p_item->p_left; /* too small */ 1169321936Shselasky else 1170321936Shselasky p_item = p_item->p_right; /* too big */ 1171321936Shselasky } 1172321936Shselasky 1173321936Shselasky return (p_item); 1174321936Shselasky} 1175321936Shselasky 1176321936Shselaskycl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map, 1177321936Shselasky IN const void *const p_key) 1178321936Shselasky{ 1179321936Shselasky return cl_fmap_match(p_map, p_key, p_map->pfn_compare); 1180321936Shselasky} 1181321936Shselasky 1182321936Shselaskycl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map, 1183321936Shselasky IN const void *const p_key) 1184321936Shselasky{ 1185321936Shselasky cl_fmap_item_t *p_item; 1186321936Shselasky cl_fmap_item_t *p_item_found; 1187321936Shselasky int cmp; 1188321936Shselasky 1189321936Shselasky CL_ASSERT(p_map); 1190321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 1191321936Shselasky 1192321936Shselasky p_item = __cl_fmap_root(p_map); 1193321936Shselasky p_item_found = (cl_fmap_item_t *) & p_map->nil; 1194321936Shselasky 1195321936Shselasky while (p_item != &p_map->nil) { 1196321936Shselasky cmp = p_map->pfn_compare(p_key, p_item->p_key); 1197321936Shselasky 1198321936Shselasky if (cmp < 0) { 1199321936Shselasky p_item_found = p_item; 1200321936Shselasky p_item = p_item->p_left; /* too small */ 1201321936Shselasky } else { 1202321936Shselasky p_item = p_item->p_right; /* too big or match */ 1203321936Shselasky } 1204321936Shselasky } 1205321936Shselasky 1206321936Shselasky return (p_item_found); 1207321936Shselasky} 1208321936Shselasky 1209321936Shselaskyvoid cl_fmap_apply_func(IN const cl_fmap_t * const p_map, 1210321936Shselasky IN cl_pfn_fmap_apply_t pfn_func, 1211321936Shselasky IN const void *const context) 1212321936Shselasky{ 1213321936Shselasky cl_fmap_item_t *p_fmap_item; 1214321936Shselasky 1215321936Shselasky /* Note that context can have any arbitrary value. */ 1216321936Shselasky CL_ASSERT(p_map); 1217321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 1218321936Shselasky CL_ASSERT(pfn_func); 1219321936Shselasky 1220321936Shselasky p_fmap_item = cl_fmap_head(p_map); 1221321936Shselasky while (p_fmap_item != cl_fmap_end(p_map)) { 1222321936Shselasky pfn_func(p_fmap_item, (void *)context); 1223321936Shselasky p_fmap_item = cl_fmap_next(p_fmap_item); 1224321936Shselasky } 1225321936Shselasky} 1226321936Shselasky 1227321936Shselasky/* 1228321936Shselasky * Balance a tree starting at a given item back to the root. 1229321936Shselasky */ 1230321936Shselaskystatic void __cl_fmap_ins_bal(IN cl_fmap_t * const p_map, 1231321936Shselasky IN cl_fmap_item_t * p_item) 1232321936Shselasky{ 1233321936Shselasky cl_fmap_item_t *p_grand_uncle; 1234321936Shselasky 1235321936Shselasky CL_ASSERT(p_map); 1236321936Shselasky CL_ASSERT(p_item); 1237321936Shselasky CL_ASSERT(p_item != &p_map->root); 1238321936Shselasky 1239321936Shselasky while (p_item->p_up->color == CL_MAP_RED) { 1240321936Shselasky if (__cl_fmap_is_left_child(p_item->p_up)) { 1241321936Shselasky p_grand_uncle = p_item->p_up->p_up->p_right; 1242321936Shselasky CL_ASSERT(p_grand_uncle); 1243321936Shselasky if (p_grand_uncle->color == CL_MAP_RED) { 1244321936Shselasky p_grand_uncle->color = CL_MAP_BLACK; 1245321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 1246321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 1247321936Shselasky p_item = p_item->p_up->p_up; 1248321936Shselasky continue; 1249321936Shselasky } 1250321936Shselasky 1251321936Shselasky if (!__cl_fmap_is_left_child(p_item)) { 1252321936Shselasky p_item = p_item->p_up; 1253321936Shselasky __cl_fmap_rot_left(p_map, p_item); 1254321936Shselasky } 1255321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 1256321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 1257321936Shselasky __cl_fmap_rot_right(p_map, p_item->p_up->p_up); 1258321936Shselasky } else { 1259321936Shselasky p_grand_uncle = p_item->p_up->p_up->p_left; 1260321936Shselasky CL_ASSERT(p_grand_uncle); 1261321936Shselasky if (p_grand_uncle->color == CL_MAP_RED) { 1262321936Shselasky p_grand_uncle->color = CL_MAP_BLACK; 1263321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 1264321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 1265321936Shselasky p_item = p_item->p_up->p_up; 1266321936Shselasky continue; 1267321936Shselasky } 1268321936Shselasky 1269321936Shselasky if (__cl_fmap_is_left_child(p_item)) { 1270321936Shselasky p_item = p_item->p_up; 1271321936Shselasky __cl_fmap_rot_right(p_map, p_item); 1272321936Shselasky } 1273321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 1274321936Shselasky p_item->p_up->p_up->color = CL_MAP_RED; 1275321936Shselasky __cl_fmap_rot_left(p_map, p_item->p_up->p_up); 1276321936Shselasky } 1277321936Shselasky } 1278321936Shselasky} 1279321936Shselasky 1280321936Shselaskycl_fmap_item_t *cl_fmap_insert(IN cl_fmap_t * const p_map, 1281321936Shselasky IN const void *const p_key, 1282321936Shselasky IN cl_fmap_item_t * const p_item) 1283321936Shselasky{ 1284321936Shselasky cl_fmap_item_t *p_insert_at, *p_comp_item; 1285321936Shselasky int cmp = 0; 1286321936Shselasky 1287321936Shselasky CL_ASSERT(p_map); 1288321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 1289321936Shselasky CL_ASSERT(p_item); 1290321936Shselasky CL_ASSERT(p_map->root.p_up == &p_map->root); 1291321936Shselasky CL_ASSERT(p_map->root.color != CL_MAP_RED); 1292321936Shselasky CL_ASSERT(p_map->nil.color != CL_MAP_RED); 1293321936Shselasky 1294321936Shselasky p_item->p_left = &p_map->nil; 1295321936Shselasky p_item->p_right = &p_map->nil; 1296321936Shselasky p_item->p_key = p_key; 1297321936Shselasky p_item->color = CL_MAP_RED; 1298321936Shselasky 1299321936Shselasky /* Find the insertion location. */ 1300321936Shselasky p_insert_at = &p_map->root; 1301321936Shselasky p_comp_item = __cl_fmap_root(p_map); 1302321936Shselasky 1303321936Shselasky while (p_comp_item != &p_map->nil) { 1304321936Shselasky p_insert_at = p_comp_item; 1305321936Shselasky 1306321936Shselasky cmp = p_map->pfn_compare(p_key, p_insert_at->p_key); 1307321936Shselasky 1308321936Shselasky if (!cmp) 1309321936Shselasky return (p_insert_at); 1310321936Shselasky 1311321936Shselasky /* Traverse the tree until the correct insertion point is found. */ 1312321936Shselasky if (cmp < 0) 1313321936Shselasky p_comp_item = p_insert_at->p_left; 1314321936Shselasky else 1315321936Shselasky p_comp_item = p_insert_at->p_right; 1316321936Shselasky } 1317321936Shselasky 1318321936Shselasky CL_ASSERT(p_insert_at != &p_map->nil); 1319321936Shselasky CL_ASSERT(p_comp_item == &p_map->nil); 1320321936Shselasky /* Insert the item. */ 1321321936Shselasky if (p_insert_at == &p_map->root) { 1322321936Shselasky p_insert_at->p_left = p_item; 1323321936Shselasky /* 1324321936Shselasky * Primitive insert places the new item in front of 1325321936Shselasky * the existing item. 1326321936Shselasky */ 1327321936Shselasky __cl_primitive_insert(&p_map->nil.pool_item.list_item, 1328321936Shselasky &p_item->pool_item.list_item); 1329321936Shselasky } else if (cmp < 0) { 1330321936Shselasky p_insert_at->p_left = p_item; 1331321936Shselasky /* 1332321936Shselasky * Primitive insert places the new item in front of 1333321936Shselasky * the existing item. 1334321936Shselasky */ 1335321936Shselasky __cl_primitive_insert(&p_insert_at->pool_item.list_item, 1336321936Shselasky &p_item->pool_item.list_item); 1337321936Shselasky } else { 1338321936Shselasky p_insert_at->p_right = p_item; 1339321936Shselasky /* 1340321936Shselasky * Primitive insert places the new item in front of 1341321936Shselasky * the existing item. 1342321936Shselasky */ 1343321936Shselasky __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next, 1344321936Shselasky &p_item->pool_item.list_item); 1345321936Shselasky } 1346321936Shselasky /* Increase the count. */ 1347321936Shselasky p_map->count++; 1348321936Shselasky 1349321936Shselasky p_item->p_up = p_insert_at; 1350321936Shselasky 1351321936Shselasky /* 1352321936Shselasky * We have added depth to this section of the tree. 1353321936Shselasky * Rebalance as necessary as we retrace our path through the tree 1354321936Shselasky * and update colors. 1355321936Shselasky */ 1356321936Shselasky __cl_fmap_ins_bal(p_map, p_item); 1357321936Shselasky 1358321936Shselasky __cl_fmap_root(p_map)->color = CL_MAP_BLACK; 1359321936Shselasky 1360321936Shselasky /* 1361321936Shselasky * Note that it is not necessary to re-color the nil node black because all 1362321936Shselasky * red color assignments are made via the p_up pointer, and nil is never 1363321936Shselasky * set as the value of a p_up pointer. 1364321936Shselasky */ 1365321936Shselasky 1366321936Shselasky#ifdef _DEBUG_ 1367321936Shselasky /* Set the pointer to the map in the map item for consistency checking. */ 1368321936Shselasky p_item->p_map = p_map; 1369321936Shselasky#endif 1370321936Shselasky 1371321936Shselasky return (p_item); 1372321936Shselasky} 1373321936Shselasky 1374321936Shselaskystatic void __cl_fmap_del_bal(IN cl_fmap_t * const p_map, 1375321936Shselasky IN cl_fmap_item_t * p_item) 1376321936Shselasky{ 1377321936Shselasky cl_fmap_item_t *p_uncle; 1378321936Shselasky 1379321936Shselasky while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) { 1380321936Shselasky if (__cl_fmap_is_left_child(p_item)) { 1381321936Shselasky p_uncle = p_item->p_up->p_right; 1382321936Shselasky 1383321936Shselasky if (p_uncle->color == CL_MAP_RED) { 1384321936Shselasky p_uncle->color = CL_MAP_BLACK; 1385321936Shselasky p_item->p_up->color = CL_MAP_RED; 1386321936Shselasky __cl_fmap_rot_left(p_map, p_item->p_up); 1387321936Shselasky p_uncle = p_item->p_up->p_right; 1388321936Shselasky } 1389321936Shselasky 1390321936Shselasky if (p_uncle->p_right->color != CL_MAP_RED) { 1391321936Shselasky if (p_uncle->p_left->color != CL_MAP_RED) { 1392321936Shselasky p_uncle->color = CL_MAP_RED; 1393321936Shselasky p_item = p_item->p_up; 1394321936Shselasky continue; 1395321936Shselasky } 1396321936Shselasky 1397321936Shselasky p_uncle->p_left->color = CL_MAP_BLACK; 1398321936Shselasky p_uncle->color = CL_MAP_RED; 1399321936Shselasky __cl_fmap_rot_right(p_map, p_uncle); 1400321936Shselasky p_uncle = p_item->p_up->p_right; 1401321936Shselasky } 1402321936Shselasky p_uncle->color = p_item->p_up->color; 1403321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 1404321936Shselasky p_uncle->p_right->color = CL_MAP_BLACK; 1405321936Shselasky __cl_fmap_rot_left(p_map, p_item->p_up); 1406321936Shselasky break; 1407321936Shselasky } else { 1408321936Shselasky p_uncle = p_item->p_up->p_left; 1409321936Shselasky 1410321936Shselasky if (p_uncle->color == CL_MAP_RED) { 1411321936Shselasky p_uncle->color = CL_MAP_BLACK; 1412321936Shselasky p_item->p_up->color = CL_MAP_RED; 1413321936Shselasky __cl_fmap_rot_right(p_map, p_item->p_up); 1414321936Shselasky p_uncle = p_item->p_up->p_left; 1415321936Shselasky } 1416321936Shselasky 1417321936Shselasky if (p_uncle->p_left->color != CL_MAP_RED) { 1418321936Shselasky if (p_uncle->p_right->color != CL_MAP_RED) { 1419321936Shselasky p_uncle->color = CL_MAP_RED; 1420321936Shselasky p_item = p_item->p_up; 1421321936Shselasky continue; 1422321936Shselasky } 1423321936Shselasky 1424321936Shselasky p_uncle->p_right->color = CL_MAP_BLACK; 1425321936Shselasky p_uncle->color = CL_MAP_RED; 1426321936Shselasky __cl_fmap_rot_left(p_map, p_uncle); 1427321936Shselasky p_uncle = p_item->p_up->p_left; 1428321936Shselasky } 1429321936Shselasky p_uncle->color = p_item->p_up->color; 1430321936Shselasky p_item->p_up->color = CL_MAP_BLACK; 1431321936Shselasky p_uncle->p_left->color = CL_MAP_BLACK; 1432321936Shselasky __cl_fmap_rot_right(p_map, p_item->p_up); 1433321936Shselasky break; 1434321936Shselasky } 1435321936Shselasky } 1436321936Shselasky p_item->color = CL_MAP_BLACK; 1437321936Shselasky} 1438321936Shselasky 1439321936Shselaskyvoid cl_fmap_remove_item(IN cl_fmap_t * const p_map, 1440321936Shselasky IN cl_fmap_item_t * const p_item) 1441321936Shselasky{ 1442321936Shselasky cl_fmap_item_t *p_child, *p_del_item; 1443321936Shselasky 1444321936Shselasky CL_ASSERT(p_map); 1445321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 1446321936Shselasky CL_ASSERT(p_item); 1447321936Shselasky CL_ASSERT(p_item->p_map == p_map); 1448321936Shselasky 1449321936Shselasky if (p_item == cl_fmap_end(p_map)) 1450321936Shselasky return; 1451321936Shselasky 1452321936Shselasky if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) { 1453321936Shselasky /* The item being removed has children on at most on side. */ 1454321936Shselasky p_del_item = p_item; 1455321936Shselasky } else { 1456321936Shselasky /* 1457321936Shselasky * The item being removed has children on both side. 1458321936Shselasky * We select the item that will replace it. After removing 1459321936Shselasky * the substitute item and rebalancing, the tree will have the 1460321936Shselasky * correct topology. Exchanging the substitute for the item 1461321936Shselasky * will finalize the removal. 1462321936Shselasky */ 1463321936Shselasky p_del_item = cl_fmap_next(p_item); 1464321936Shselasky CL_ASSERT(p_del_item != &p_map->nil); 1465321936Shselasky } 1466321936Shselasky 1467321936Shselasky /* Remove the item from the list. */ 1468321936Shselasky __cl_primitive_remove(&p_item->pool_item.list_item); 1469321936Shselasky /* Decrement the item count. */ 1470321936Shselasky p_map->count--; 1471321936Shselasky 1472321936Shselasky /* Get the pointer to the new root's child, if any. */ 1473321936Shselasky if (p_del_item->p_left != &p_map->nil) 1474321936Shselasky p_child = p_del_item->p_left; 1475321936Shselasky else 1476321936Shselasky p_child = p_del_item->p_right; 1477321936Shselasky 1478321936Shselasky /* 1479321936Shselasky * This assignment may modify the parent pointer of the nil node. 1480321936Shselasky * This is inconsequential. 1481321936Shselasky */ 1482321936Shselasky p_child->p_up = p_del_item->p_up; 1483321936Shselasky (*__cl_fmap_get_parent_ptr_to_item(p_del_item)) = p_child; 1484321936Shselasky 1485321936Shselasky if (p_del_item->color != CL_MAP_RED) 1486321936Shselasky __cl_fmap_del_bal(p_map, p_child); 1487321936Shselasky 1488321936Shselasky /* 1489321936Shselasky * Note that the splicing done below does not need to occur before 1490321936Shselasky * the tree is balanced, since the actual topology changes are made by the 1491321936Shselasky * preceding code. The topology is preserved by the color assignment made 1492321936Shselasky * below (reader should be reminded that p_del_item == p_item in some cases). 1493321936Shselasky */ 1494321936Shselasky if (p_del_item != p_item) { 1495321936Shselasky /* 1496321936Shselasky * Finalize the removal of the specified item by exchanging it with 1497321936Shselasky * the substitute which we removed above. 1498321936Shselasky */ 1499321936Shselasky p_del_item->p_up = p_item->p_up; 1500321936Shselasky p_del_item->p_left = p_item->p_left; 1501321936Shselasky p_del_item->p_right = p_item->p_right; 1502321936Shselasky (*__cl_fmap_get_parent_ptr_to_item(p_item)) = p_del_item; 1503321936Shselasky p_item->p_right->p_up = p_del_item; 1504321936Shselasky p_item->p_left->p_up = p_del_item; 1505321936Shselasky p_del_item->color = p_item->color; 1506321936Shselasky } 1507321936Shselasky 1508321936Shselasky CL_ASSERT(p_map->nil.color != CL_MAP_RED); 1509321936Shselasky 1510321936Shselasky#ifdef _DEBUG_ 1511321936Shselasky /* Clear the pointer to the map since the item has been removed. */ 1512321936Shselasky p_item->p_map = NULL; 1513321936Shselasky#endif 1514321936Shselasky} 1515321936Shselasky 1516321936Shselaskycl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map, 1517321936Shselasky IN const void *const p_key) 1518321936Shselasky{ 1519321936Shselasky cl_fmap_item_t *p_item; 1520321936Shselasky 1521321936Shselasky CL_ASSERT(p_map); 1522321936Shselasky CL_ASSERT(p_map->state == CL_INITIALIZED); 1523321936Shselasky 1524321936Shselasky /* Seek the node with the specified key */ 1525321936Shselasky p_item = cl_fmap_get(p_map, p_key); 1526321936Shselasky 1527321936Shselasky cl_fmap_remove_item(p_map, p_item); 1528321936Shselasky 1529321936Shselasky return (p_item); 1530321936Shselasky} 1531321936Shselasky 1532321936Shselaskyvoid cl_fmap_merge(OUT cl_fmap_t * const p_dest_map, 1533321936Shselasky IN OUT cl_fmap_t * const p_src_map) 1534321936Shselasky{ 1535321936Shselasky cl_fmap_item_t *p_item, *p_item2, *p_next; 1536321936Shselasky 1537321936Shselasky CL_ASSERT(p_dest_map); 1538321936Shselasky CL_ASSERT(p_src_map); 1539321936Shselasky 1540321936Shselasky p_item = cl_fmap_head(p_src_map); 1541321936Shselasky 1542321936Shselasky while (p_item != cl_fmap_end(p_src_map)) { 1543321936Shselasky p_next = cl_fmap_next(p_item); 1544321936Shselasky 1545321936Shselasky /* Remove the item from its current map. */ 1546321936Shselasky cl_fmap_remove_item(p_src_map, p_item); 1547321936Shselasky /* Insert the item into the destination map. */ 1548321936Shselasky p_item2 = 1549321936Shselasky cl_fmap_insert(p_dest_map, cl_fmap_key(p_item), p_item); 1550321936Shselasky /* Check that the item was successfully inserted. */ 1551321936Shselasky if (p_item2 != p_item) { 1552321936Shselasky /* Put the item in back in the source map. */ 1553321936Shselasky p_item2 = 1554321936Shselasky cl_fmap_insert(p_src_map, cl_fmap_key(p_item), 1555321936Shselasky p_item); 1556321936Shselasky CL_ASSERT(p_item2 == p_item); 1557321936Shselasky } 1558321936Shselasky p_item = p_next; 1559321936Shselasky } 1560321936Shselasky} 1561321936Shselasky 1562321936Shselaskystatic void __cl_fmap_delta_move(IN OUT cl_fmap_t * const p_dest, 1563321936Shselasky IN OUT cl_fmap_t * const p_src, 1564321936Shselasky IN OUT cl_fmap_item_t ** const pp_item) 1565321936Shselasky{ 1566321936Shselasky cl_fmap_item_t __attribute__((__unused__)) *p_temp; 1567321936Shselasky cl_fmap_item_t *p_next; 1568321936Shselasky 1569321936Shselasky /* 1570321936Shselasky * Get the next item so that we can ensure that pp_item points to 1571321936Shselasky * a valid item upon return from the function. 1572321936Shselasky */ 1573321936Shselasky p_next = cl_fmap_next(*pp_item); 1574321936Shselasky /* Move the old item from its current map the the old map. */ 1575321936Shselasky cl_fmap_remove_item(p_src, *pp_item); 1576321936Shselasky p_temp = cl_fmap_insert(p_dest, cl_fmap_key(*pp_item), *pp_item); 1577321936Shselasky /* We should never have duplicates. */ 1578321936Shselasky CL_ASSERT(p_temp == *pp_item); 1579321936Shselasky /* Point pp_item to a valid item in the source map. */ 1580321936Shselasky (*pp_item) = p_next; 1581321936Shselasky} 1582321936Shselasky 1583321936Shselaskyvoid cl_fmap_delta(IN OUT cl_fmap_t * const p_map1, 1584321936Shselasky IN OUT cl_fmap_t * const p_map2, 1585321936Shselasky OUT cl_fmap_t * const p_new, OUT cl_fmap_t * const p_old) 1586321936Shselasky{ 1587321936Shselasky cl_fmap_item_t *p_item1, *p_item2; 1588321936Shselasky int cmp; 1589321936Shselasky 1590321936Shselasky CL_ASSERT(p_map1); 1591321936Shselasky CL_ASSERT(p_map2); 1592321936Shselasky CL_ASSERT(p_new); 1593321936Shselasky CL_ASSERT(p_old); 1594321936Shselasky CL_ASSERT(cl_is_fmap_empty(p_new)); 1595321936Shselasky CL_ASSERT(cl_is_fmap_empty(p_old)); 1596321936Shselasky 1597321936Shselasky p_item1 = cl_fmap_head(p_map1); 1598321936Shselasky p_item2 = cl_fmap_head(p_map2); 1599321936Shselasky 1600321936Shselasky while (p_item1 != cl_fmap_end(p_map1) && p_item2 != cl_fmap_end(p_map2)) { 1601321936Shselasky cmp = p_map1->pfn_compare(cl_fmap_key(p_item1), 1602321936Shselasky cl_fmap_key(p_item2)); 1603321936Shselasky if (cmp < 0) { 1604321936Shselasky /* We found an old item. */ 1605321936Shselasky __cl_fmap_delta_move(p_old, p_map1, &p_item1); 1606321936Shselasky } else if (cmp > 0) { 1607321936Shselasky /* We found a new item. */ 1608321936Shselasky __cl_fmap_delta_move(p_new, p_map2, &p_item2); 1609321936Shselasky } else { 1610321936Shselasky /* Move both forward since they have the same key. */ 1611321936Shselasky p_item1 = cl_fmap_next(p_item1); 1612321936Shselasky p_item2 = cl_fmap_next(p_item2); 1613321936Shselasky } 1614321936Shselasky } 1615321936Shselasky 1616321936Shselasky /* Process the remainder if the end of either source map was reached. */ 1617321936Shselasky while (p_item2 != cl_fmap_end(p_map2)) 1618321936Shselasky __cl_fmap_delta_move(p_new, p_map2, &p_item2); 1619321936Shselasky 1620321936Shselasky while (p_item1 != cl_fmap_end(p_map1)) 1621321936Shselasky __cl_fmap_delta_move(p_old, p_map1, &p_item1); 1622321936Shselasky} 1623