1219820Sjeff/* 2219820Sjeff * Copyright (c) 2004-2006 Voltaire, Inc. All rights reserved. 3219820Sjeff * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved. 4219820Sjeff * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. 5219820Sjeff * 6219820Sjeff * This software is available to you under a choice of one of two 7219820Sjeff * licenses. You may choose to be licensed under the terms of the GNU 8219820Sjeff * General Public License (GPL) Version 2, available from the file 9219820Sjeff * COPYING in the main directory of this source tree, or the 10219820Sjeff * OpenIB.org BSD license below: 11219820Sjeff * 12219820Sjeff * Redistribution and use in source and binary forms, with or 13219820Sjeff * without modification, are permitted provided that the following 14219820Sjeff * conditions are met: 15219820Sjeff * 16219820Sjeff * - Redistributions of source code must retain the above 17219820Sjeff * copyright notice, this list of conditions and the following 18219820Sjeff * disclaimer. 19219820Sjeff * 20219820Sjeff * - Redistributions in binary form must reproduce the above 21219820Sjeff * copyright notice, this list of conditions and the following 22219820Sjeff * disclaimer in the documentation and/or other materials 23219820Sjeff * provided with the distribution. 24219820Sjeff * 25219820Sjeff * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 26219820Sjeff * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 27219820Sjeff * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 28219820Sjeff * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 29219820Sjeff * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 30219820Sjeff * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31219820Sjeff * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 32219820Sjeff * SOFTWARE. 33219820Sjeff * 34219820Sjeff */ 35219820Sjeff 36219820Sjeff/* 37219820Sjeff * Abstract: 38219820Sjeff * Implementation of quick map, a binary tree where the caller always 39219820Sjeff * provides all necessary storage. 40219820Sjeff * 41219820Sjeff */ 42219820Sjeff 43219820Sjeff/***************************************************************************** 44219820Sjeff* 45219820Sjeff* Map 46219820Sjeff* 47219820Sjeff* Map is an associative array. By providing a key, the caller can retrieve 48219820Sjeff* an object from the map. All objects in the map have an associated key, 49219820Sjeff* as specified by the caller when the object was inserted into the map. 50219820Sjeff* In addition to random access, the caller can traverse the map much like 51219820Sjeff* a linked list, either forwards from the first object or backwards from 52219820Sjeff* the last object. The objects in the map are always traversed in 53219820Sjeff* order since the nodes are stored sorted. 54219820Sjeff* 55219820Sjeff* This implementation of Map uses a red black tree verified against 56219820Sjeff* Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth 57219820Sjeff* printing, 1994. 58219820Sjeff* 59219820Sjeff*****************************************************************************/ 60219820Sjeff 61219820Sjeff#if HAVE_CONFIG_H 62219820Sjeff# include <config.h> 63219820Sjeff#endif /* HAVE_CONFIG_H */ 64219820Sjeff 65219820Sjeff#include <string.h> 66219820Sjeff#include <complib/cl_qmap.h> 67219820Sjeff#include <complib/cl_map.h> 68219820Sjeff#include <complib/cl_fleximap.h> 69219820Sjeff 70219820Sjeff/****************************************************************************** 71219820Sjeff******************************************************************************* 72219820Sjeff************** ************ 73219820Sjeff************** IMPLEMENTATION OF QUICK MAP ************ 74219820Sjeff************** ************ 75219820Sjeff******************************************************************************* 76219820Sjeff******************************************************************************/ 77219820Sjeff 78219820Sjeff/* 79219820Sjeff * Get the root. 80219820Sjeff */ 81219820Sjeffstatic inline cl_map_item_t *__cl_map_root(IN const cl_qmap_t * const p_map) 82219820Sjeff{ 83219820Sjeff CL_ASSERT(p_map); 84219820Sjeff return (p_map->root.p_left); 85219820Sjeff} 86219820Sjeff 87219820Sjeff/* 88219820Sjeff * Returns whether a given item is on the left of its parent. 89219820Sjeff */ 90219820Sjeffstatic boolean_t __cl_map_is_left_child(IN const cl_map_item_t * const p_item) 91219820Sjeff{ 92219820Sjeff CL_ASSERT(p_item); 93219820Sjeff CL_ASSERT(p_item->p_up); 94219820Sjeff CL_ASSERT(p_item->p_up != p_item); 95219820Sjeff 96219820Sjeff return (p_item->p_up->p_left == p_item); 97219820Sjeff} 98219820Sjeff 99219820Sjeff/* 100219820Sjeff * Retrieve the pointer to the parent's pointer to an item. 101219820Sjeff */ 102219820Sjeffstatic cl_map_item_t **__cl_map_get_parent_ptr_to_item(IN cl_map_item_t * 103219820Sjeff const p_item) 104219820Sjeff{ 105219820Sjeff CL_ASSERT(p_item); 106219820Sjeff CL_ASSERT(p_item->p_up); 107219820Sjeff CL_ASSERT(p_item->p_up != p_item); 108219820Sjeff 109219820Sjeff if (__cl_map_is_left_child(p_item)) 110219820Sjeff return (&p_item->p_up->p_left); 111219820Sjeff 112219820Sjeff CL_ASSERT(p_item->p_up->p_right == p_item); 113219820Sjeff return (&p_item->p_up->p_right); 114219820Sjeff} 115219820Sjeff 116219820Sjeff/* 117219820Sjeff * Rotate a node to the left. This rotation affects the least number of links 118219820Sjeff * between nodes and brings the level of C up by one while increasing the depth 119219820Sjeff * of A one. Note that the links to/from W, X, Y, and Z are not affected. 120219820Sjeff * 121219820Sjeff * R R 122219820Sjeff * | | 123219820Sjeff * A C 124219820Sjeff * / \ / \ 125219820Sjeff * W C A Z 126219820Sjeff * / \ / \ 127219820Sjeff * B Z W B 128219820Sjeff * / \ / \ 129219820Sjeff * X Y X Y 130219820Sjeff */ 131219820Sjeffstatic void 132219820Sjeff__cl_map_rot_left(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item) 133219820Sjeff{ 134219820Sjeff cl_map_item_t **pp_root; 135219820Sjeff 136219820Sjeff CL_ASSERT(p_map); 137219820Sjeff CL_ASSERT(p_item); 138219820Sjeff CL_ASSERT(p_item->p_right != &p_map->nil); 139219820Sjeff 140219820Sjeff pp_root = __cl_map_get_parent_ptr_to_item(p_item); 141219820Sjeff 142219820Sjeff /* Point R to C instead of A. */ 143219820Sjeff *pp_root = p_item->p_right; 144219820Sjeff /* Set C's parent to R. */ 145219820Sjeff (*pp_root)->p_up = p_item->p_up; 146219820Sjeff 147219820Sjeff /* Set A's right to B */ 148219820Sjeff p_item->p_right = (*pp_root)->p_left; 149219820Sjeff /* 150219820Sjeff * Set B's parent to A. We trap for B being NIL since the 151219820Sjeff * caller may depend on NIL not changing. 152219820Sjeff */ 153219820Sjeff if ((*pp_root)->p_left != &p_map->nil) 154219820Sjeff (*pp_root)->p_left->p_up = p_item; 155219820Sjeff 156219820Sjeff /* Set C's left to A. */ 157219820Sjeff (*pp_root)->p_left = p_item; 158219820Sjeff /* Set A's parent to C. */ 159219820Sjeff p_item->p_up = *pp_root; 160219820Sjeff} 161219820Sjeff 162219820Sjeff/* 163219820Sjeff * Rotate a node to the right. This rotation affects the least number of links 164219820Sjeff * between nodes and brings the level of A up by one while increasing the depth 165219820Sjeff * of C one. Note that the links to/from W, X, Y, and Z are not affected. 166219820Sjeff * 167219820Sjeff * R R 168219820Sjeff * | | 169219820Sjeff * C A 170219820Sjeff * / \ / \ 171219820Sjeff * A Z W C 172219820Sjeff * / \ / \ 173219820Sjeff * W B B Z 174219820Sjeff * / \ / \ 175219820Sjeff * X Y X Y 176219820Sjeff */ 177219820Sjeffstatic void 178219820Sjeff__cl_map_rot_right(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item) 179219820Sjeff{ 180219820Sjeff cl_map_item_t **pp_root; 181219820Sjeff 182219820Sjeff CL_ASSERT(p_map); 183219820Sjeff CL_ASSERT(p_item); 184219820Sjeff CL_ASSERT(p_item->p_left != &p_map->nil); 185219820Sjeff 186219820Sjeff /* Point R to A instead of C. */ 187219820Sjeff pp_root = __cl_map_get_parent_ptr_to_item(p_item); 188219820Sjeff (*pp_root) = p_item->p_left; 189219820Sjeff /* Set A's parent to R. */ 190219820Sjeff (*pp_root)->p_up = p_item->p_up; 191219820Sjeff 192219820Sjeff /* Set C's left to B */ 193219820Sjeff p_item->p_left = (*pp_root)->p_right; 194219820Sjeff /* 195219820Sjeff * Set B's parent to C. We trap for B being NIL since the 196219820Sjeff * caller may depend on NIL not changing. 197219820Sjeff */ 198219820Sjeff if ((*pp_root)->p_right != &p_map->nil) 199219820Sjeff (*pp_root)->p_right->p_up = p_item; 200219820Sjeff 201219820Sjeff /* Set A's right to C. */ 202219820Sjeff (*pp_root)->p_right = p_item; 203219820Sjeff /* Set C's parent to A. */ 204219820Sjeff p_item->p_up = *pp_root; 205219820Sjeff} 206219820Sjeff 207219820Sjeffvoid cl_qmap_init(IN cl_qmap_t * const p_map) 208219820Sjeff{ 209219820Sjeff CL_ASSERT(p_map); 210219820Sjeff 211219820Sjeff memset(p_map, 0, sizeof(cl_qmap_t)); 212219820Sjeff 213219820Sjeff /* special setup for the root node */ 214219820Sjeff p_map->root.p_up = &p_map->root; 215219820Sjeff p_map->root.p_left = &p_map->nil; 216219820Sjeff p_map->root.p_right = &p_map->nil; 217219820Sjeff p_map->root.color = CL_MAP_BLACK; 218219820Sjeff 219219820Sjeff /* Setup the node used as terminator for all leaves. */ 220219820Sjeff p_map->nil.p_up = &p_map->nil; 221219820Sjeff p_map->nil.p_left = &p_map->nil; 222219820Sjeff p_map->nil.p_right = &p_map->nil; 223219820Sjeff p_map->nil.color = CL_MAP_BLACK; 224219820Sjeff 225219820Sjeff p_map->state = CL_INITIALIZED; 226219820Sjeff 227219820Sjeff cl_qmap_remove_all(p_map); 228219820Sjeff} 229219820Sjeff 230219820Sjeffcl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map, 231219820Sjeff IN const uint64_t key) 232219820Sjeff{ 233219820Sjeff cl_map_item_t *p_item; 234219820Sjeff 235219820Sjeff CL_ASSERT(p_map); 236219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 237219820Sjeff 238219820Sjeff p_item = __cl_map_root(p_map); 239219820Sjeff 240219820Sjeff while (p_item != &p_map->nil) { 241219820Sjeff if (key == p_item->key) 242219820Sjeff break; /* just right */ 243219820Sjeff 244219820Sjeff if (key < p_item->key) 245219820Sjeff p_item = p_item->p_left; /* too small */ 246219820Sjeff else 247219820Sjeff p_item = p_item->p_right; /* too big */ 248219820Sjeff } 249219820Sjeff 250219820Sjeff return (p_item); 251219820Sjeff} 252219820Sjeff 253219820Sjeffcl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map, 254219820Sjeff IN const uint64_t key) 255219820Sjeff{ 256219820Sjeff cl_map_item_t *p_item; 257219820Sjeff cl_map_item_t *p_item_found; 258219820Sjeff 259219820Sjeff CL_ASSERT(p_map); 260219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 261219820Sjeff 262219820Sjeff p_item = __cl_map_root(p_map); 263219820Sjeff p_item_found = (cl_map_item_t *) & p_map->nil; 264219820Sjeff 265219820Sjeff while (p_item != &p_map->nil) { 266219820Sjeff if (key < p_item->key) { 267219820Sjeff p_item_found = p_item; 268219820Sjeff p_item = p_item->p_left; 269219820Sjeff } else { 270219820Sjeff p_item = p_item->p_right; 271219820Sjeff } 272219820Sjeff } 273219820Sjeff 274219820Sjeff return (p_item_found); 275219820Sjeff} 276219820Sjeff 277219820Sjeffvoid 278219820Sjeffcl_qmap_apply_func(IN const cl_qmap_t * const p_map, 279219820Sjeff IN cl_pfn_qmap_apply_t pfn_func, 280219820Sjeff IN const void *const context) 281219820Sjeff{ 282219820Sjeff cl_map_item_t *p_map_item; 283219820Sjeff 284219820Sjeff /* Note that context can have any arbitrary value. */ 285219820Sjeff CL_ASSERT(p_map); 286219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 287219820Sjeff CL_ASSERT(pfn_func); 288219820Sjeff 289219820Sjeff p_map_item = cl_qmap_head(p_map); 290219820Sjeff while (p_map_item != cl_qmap_end(p_map)) { 291219820Sjeff pfn_func(p_map_item, (void *)context); 292219820Sjeff p_map_item = cl_qmap_next(p_map_item); 293219820Sjeff } 294219820Sjeff} 295219820Sjeff 296219820Sjeff/* 297219820Sjeff * Balance a tree starting at a given item back to the root. 298219820Sjeff */ 299219820Sjeffstatic void 300219820Sjeff__cl_map_ins_bal(IN cl_qmap_t * const p_map, IN cl_map_item_t * p_item) 301219820Sjeff{ 302219820Sjeff cl_map_item_t *p_grand_uncle; 303219820Sjeff 304219820Sjeff CL_ASSERT(p_map); 305219820Sjeff CL_ASSERT(p_item); 306219820Sjeff CL_ASSERT(p_item != &p_map->root); 307219820Sjeff 308219820Sjeff while (p_item->p_up->color == CL_MAP_RED) { 309219820Sjeff if (__cl_map_is_left_child(p_item->p_up)) { 310219820Sjeff p_grand_uncle = p_item->p_up->p_up->p_right; 311219820Sjeff CL_ASSERT(p_grand_uncle); 312219820Sjeff if (p_grand_uncle->color == CL_MAP_RED) { 313219820Sjeff p_grand_uncle->color = CL_MAP_BLACK; 314219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 315219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 316219820Sjeff p_item = p_item->p_up->p_up; 317219820Sjeff continue; 318219820Sjeff } 319219820Sjeff 320219820Sjeff if (!__cl_map_is_left_child(p_item)) { 321219820Sjeff p_item = p_item->p_up; 322219820Sjeff __cl_map_rot_left(p_map, p_item); 323219820Sjeff } 324219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 325219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 326219820Sjeff __cl_map_rot_right(p_map, p_item->p_up->p_up); 327219820Sjeff } else { 328219820Sjeff p_grand_uncle = p_item->p_up->p_up->p_left; 329219820Sjeff CL_ASSERT(p_grand_uncle); 330219820Sjeff if (p_grand_uncle->color == CL_MAP_RED) { 331219820Sjeff p_grand_uncle->color = CL_MAP_BLACK; 332219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 333219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 334219820Sjeff p_item = p_item->p_up->p_up; 335219820Sjeff continue; 336219820Sjeff } 337219820Sjeff 338219820Sjeff if (__cl_map_is_left_child(p_item)) { 339219820Sjeff p_item = p_item->p_up; 340219820Sjeff __cl_map_rot_right(p_map, p_item); 341219820Sjeff } 342219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 343219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 344219820Sjeff __cl_map_rot_left(p_map, p_item->p_up->p_up); 345219820Sjeff } 346219820Sjeff } 347219820Sjeff} 348219820Sjeff 349219820Sjeffcl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map, 350219820Sjeff IN const uint64_t key, 351219820Sjeff IN cl_map_item_t * const p_item) 352219820Sjeff{ 353219820Sjeff cl_map_item_t *p_insert_at, *p_comp_item; 354219820Sjeff 355219820Sjeff CL_ASSERT(p_map); 356219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 357219820Sjeff CL_ASSERT(p_item); 358219820Sjeff CL_ASSERT(p_map->root.p_up == &p_map->root); 359219820Sjeff CL_ASSERT(p_map->root.color != CL_MAP_RED); 360219820Sjeff CL_ASSERT(p_map->nil.color != CL_MAP_RED); 361219820Sjeff 362219820Sjeff p_item->p_left = &p_map->nil; 363219820Sjeff p_item->p_right = &p_map->nil; 364219820Sjeff p_item->key = key; 365219820Sjeff p_item->color = CL_MAP_RED; 366219820Sjeff 367219820Sjeff /* Find the insertion location. */ 368219820Sjeff p_insert_at = &p_map->root; 369219820Sjeff p_comp_item = __cl_map_root(p_map); 370219820Sjeff 371219820Sjeff while (p_comp_item != &p_map->nil) { 372219820Sjeff p_insert_at = p_comp_item; 373219820Sjeff 374219820Sjeff if (key == p_insert_at->key) 375219820Sjeff return (p_insert_at); 376219820Sjeff 377219820Sjeff /* Traverse the tree until the correct insertion point is found. */ 378219820Sjeff if (key < p_insert_at->key) 379219820Sjeff p_comp_item = p_insert_at->p_left; 380219820Sjeff else 381219820Sjeff p_comp_item = p_insert_at->p_right; 382219820Sjeff } 383219820Sjeff 384219820Sjeff CL_ASSERT(p_insert_at != &p_map->nil); 385219820Sjeff CL_ASSERT(p_comp_item == &p_map->nil); 386219820Sjeff /* Insert the item. */ 387219820Sjeff if (p_insert_at == &p_map->root) { 388219820Sjeff p_insert_at->p_left = p_item; 389219820Sjeff /* 390219820Sjeff * Primitive insert places the new item in front of 391219820Sjeff * the existing item. 392219820Sjeff */ 393219820Sjeff __cl_primitive_insert(&p_map->nil.pool_item.list_item, 394219820Sjeff &p_item->pool_item.list_item); 395219820Sjeff } else if (key < p_insert_at->key) { 396219820Sjeff p_insert_at->p_left = p_item; 397219820Sjeff /* 398219820Sjeff * Primitive insert places the new item in front of 399219820Sjeff * the existing item. 400219820Sjeff */ 401219820Sjeff __cl_primitive_insert(&p_insert_at->pool_item.list_item, 402219820Sjeff &p_item->pool_item.list_item); 403219820Sjeff } else { 404219820Sjeff p_insert_at->p_right = p_item; 405219820Sjeff /* 406219820Sjeff * Primitive insert places the new item in front of 407219820Sjeff * the existing item. 408219820Sjeff */ 409219820Sjeff __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next, 410219820Sjeff &p_item->pool_item.list_item); 411219820Sjeff } 412219820Sjeff /* Increase the count. */ 413219820Sjeff p_map->count++; 414219820Sjeff 415219820Sjeff p_item->p_up = p_insert_at; 416219820Sjeff 417219820Sjeff /* 418219820Sjeff * We have added depth to this section of the tree. 419219820Sjeff * Rebalance as necessary as we retrace our path through the tree 420219820Sjeff * and update colors. 421219820Sjeff */ 422219820Sjeff __cl_map_ins_bal(p_map, p_item); 423219820Sjeff 424219820Sjeff __cl_map_root(p_map)->color = CL_MAP_BLACK; 425219820Sjeff 426219820Sjeff /* 427219820Sjeff * Note that it is not necessary to re-color the nil node black because all 428219820Sjeff * red color assignments are made via the p_up pointer, and nil is never 429219820Sjeff * set as the value of a p_up pointer. 430219820Sjeff */ 431219820Sjeff 432219820Sjeff#ifdef _DEBUG_ 433219820Sjeff /* Set the pointer to the map in the map item for consistency checking. */ 434219820Sjeff p_item->p_map = p_map; 435219820Sjeff#endif 436219820Sjeff 437219820Sjeff return (p_item); 438219820Sjeff} 439219820Sjeff 440219820Sjeffstatic void 441219820Sjeff__cl_map_del_bal(IN cl_qmap_t * const p_map, IN cl_map_item_t * p_item) 442219820Sjeff{ 443219820Sjeff cl_map_item_t *p_uncle; 444219820Sjeff 445219820Sjeff while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) { 446219820Sjeff if (__cl_map_is_left_child(p_item)) { 447219820Sjeff p_uncle = p_item->p_up->p_right; 448219820Sjeff 449219820Sjeff if (p_uncle->color == CL_MAP_RED) { 450219820Sjeff p_uncle->color = CL_MAP_BLACK; 451219820Sjeff p_item->p_up->color = CL_MAP_RED; 452219820Sjeff __cl_map_rot_left(p_map, p_item->p_up); 453219820Sjeff p_uncle = p_item->p_up->p_right; 454219820Sjeff } 455219820Sjeff 456219820Sjeff if (p_uncle->p_right->color != CL_MAP_RED) { 457219820Sjeff if (p_uncle->p_left->color != CL_MAP_RED) { 458219820Sjeff p_uncle->color = CL_MAP_RED; 459219820Sjeff p_item = p_item->p_up; 460219820Sjeff continue; 461219820Sjeff } 462219820Sjeff 463219820Sjeff p_uncle->p_left->color = CL_MAP_BLACK; 464219820Sjeff p_uncle->color = CL_MAP_RED; 465219820Sjeff __cl_map_rot_right(p_map, p_uncle); 466219820Sjeff p_uncle = p_item->p_up->p_right; 467219820Sjeff } 468219820Sjeff p_uncle->color = p_item->p_up->color; 469219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 470219820Sjeff p_uncle->p_right->color = CL_MAP_BLACK; 471219820Sjeff __cl_map_rot_left(p_map, p_item->p_up); 472219820Sjeff break; 473219820Sjeff } else { 474219820Sjeff p_uncle = p_item->p_up->p_left; 475219820Sjeff 476219820Sjeff if (p_uncle->color == CL_MAP_RED) { 477219820Sjeff p_uncle->color = CL_MAP_BLACK; 478219820Sjeff p_item->p_up->color = CL_MAP_RED; 479219820Sjeff __cl_map_rot_right(p_map, p_item->p_up); 480219820Sjeff p_uncle = p_item->p_up->p_left; 481219820Sjeff } 482219820Sjeff 483219820Sjeff if (p_uncle->p_left->color != CL_MAP_RED) { 484219820Sjeff if (p_uncle->p_right->color != CL_MAP_RED) { 485219820Sjeff p_uncle->color = CL_MAP_RED; 486219820Sjeff p_item = p_item->p_up; 487219820Sjeff continue; 488219820Sjeff } 489219820Sjeff 490219820Sjeff p_uncle->p_right->color = CL_MAP_BLACK; 491219820Sjeff p_uncle->color = CL_MAP_RED; 492219820Sjeff __cl_map_rot_left(p_map, p_uncle); 493219820Sjeff p_uncle = p_item->p_up->p_left; 494219820Sjeff } 495219820Sjeff p_uncle->color = p_item->p_up->color; 496219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 497219820Sjeff p_uncle->p_left->color = CL_MAP_BLACK; 498219820Sjeff __cl_map_rot_right(p_map, p_item->p_up); 499219820Sjeff break; 500219820Sjeff } 501219820Sjeff } 502219820Sjeff p_item->color = CL_MAP_BLACK; 503219820Sjeff} 504219820Sjeff 505219820Sjeffvoid 506219820Sjeffcl_qmap_remove_item(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item) 507219820Sjeff{ 508219820Sjeff cl_map_item_t *p_child, *p_del_item; 509219820Sjeff 510219820Sjeff CL_ASSERT(p_map); 511219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 512219820Sjeff CL_ASSERT(p_item); 513219820Sjeff 514219820Sjeff if (p_item == cl_qmap_end(p_map)) 515219820Sjeff return; 516219820Sjeff 517219820Sjeff /* must be checked after comparing to cl_qmap_end, since 518219820Sjeff the end is not a valid item. */ 519219820Sjeff CL_ASSERT(p_item->p_map == p_map); 520219820Sjeff 521219820Sjeff if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) { 522219820Sjeff /* The item being removed has children on at most on side. */ 523219820Sjeff p_del_item = p_item; 524219820Sjeff } else { 525219820Sjeff /* 526219820Sjeff * The item being removed has children on both side. 527219820Sjeff * We select the item that will replace it. After removing 528219820Sjeff * the substitute item and rebalancing, the tree will have the 529219820Sjeff * correct topology. Exchanging the substitute for the item 530219820Sjeff * will finalize the removal. 531219820Sjeff */ 532219820Sjeff p_del_item = cl_qmap_next(p_item); 533219820Sjeff CL_ASSERT(p_del_item != &p_map->nil); 534219820Sjeff } 535219820Sjeff 536219820Sjeff /* Remove the item from the list. */ 537219820Sjeff __cl_primitive_remove(&p_item->pool_item.list_item); 538219820Sjeff /* Decrement the item count. */ 539219820Sjeff p_map->count--; 540219820Sjeff 541219820Sjeff /* Get the pointer to the new root's child, if any. */ 542219820Sjeff if (p_del_item->p_left != &p_map->nil) 543219820Sjeff p_child = p_del_item->p_left; 544219820Sjeff else 545219820Sjeff p_child = p_del_item->p_right; 546219820Sjeff 547219820Sjeff /* 548219820Sjeff * This assignment may modify the parent pointer of the nil node. 549219820Sjeff * This is inconsequential. 550219820Sjeff */ 551219820Sjeff p_child->p_up = p_del_item->p_up; 552219820Sjeff (*__cl_map_get_parent_ptr_to_item(p_del_item)) = p_child; 553219820Sjeff 554219820Sjeff if (p_del_item->color != CL_MAP_RED) 555219820Sjeff __cl_map_del_bal(p_map, p_child); 556219820Sjeff 557219820Sjeff /* 558219820Sjeff * Note that the splicing done below does not need to occur before 559219820Sjeff * the tree is balanced, since the actual topology changes are made by the 560219820Sjeff * preceding code. The topology is preserved by the color assignment made 561219820Sjeff * below (reader should be reminded that p_del_item == p_item in some cases). 562219820Sjeff */ 563219820Sjeff if (p_del_item != p_item) { 564219820Sjeff /* 565219820Sjeff * Finalize the removal of the specified item by exchanging it with 566219820Sjeff * the substitute which we removed above. 567219820Sjeff */ 568219820Sjeff p_del_item->p_up = p_item->p_up; 569219820Sjeff p_del_item->p_left = p_item->p_left; 570219820Sjeff p_del_item->p_right = p_item->p_right; 571219820Sjeff (*__cl_map_get_parent_ptr_to_item(p_item)) = p_del_item; 572219820Sjeff p_item->p_right->p_up = p_del_item; 573219820Sjeff p_item->p_left->p_up = p_del_item; 574219820Sjeff p_del_item->color = p_item->color; 575219820Sjeff } 576219820Sjeff 577219820Sjeff CL_ASSERT(p_map->nil.color != CL_MAP_RED); 578219820Sjeff 579219820Sjeff#ifdef _DEBUG_ 580219820Sjeff /* Clear the pointer to the map since the item has been removed. */ 581219820Sjeff p_item->p_map = NULL; 582219820Sjeff#endif 583219820Sjeff} 584219820Sjeff 585219820Sjeffcl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, IN const uint64_t key) 586219820Sjeff{ 587219820Sjeff cl_map_item_t *p_item; 588219820Sjeff 589219820Sjeff CL_ASSERT(p_map); 590219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 591219820Sjeff 592219820Sjeff /* Seek the node with the specified key */ 593219820Sjeff p_item = cl_qmap_get(p_map, key); 594219820Sjeff 595219820Sjeff cl_qmap_remove_item(p_map, p_item); 596219820Sjeff 597219820Sjeff return (p_item); 598219820Sjeff} 599219820Sjeff 600219820Sjeffvoid 601219820Sjeffcl_qmap_merge(OUT cl_qmap_t * const p_dest_map, 602219820Sjeff IN OUT cl_qmap_t * const p_src_map) 603219820Sjeff{ 604219820Sjeff cl_map_item_t *p_item, *p_item2, *p_next; 605219820Sjeff 606219820Sjeff CL_ASSERT(p_dest_map); 607219820Sjeff CL_ASSERT(p_src_map); 608219820Sjeff 609219820Sjeff p_item = cl_qmap_head(p_src_map); 610219820Sjeff 611219820Sjeff while (p_item != cl_qmap_end(p_src_map)) { 612219820Sjeff p_next = cl_qmap_next(p_item); 613219820Sjeff 614219820Sjeff /* Remove the item from its current map. */ 615219820Sjeff cl_qmap_remove_item(p_src_map, p_item); 616219820Sjeff /* Insert the item into the destination map. */ 617219820Sjeff p_item2 = 618219820Sjeff cl_qmap_insert(p_dest_map, cl_qmap_key(p_item), p_item); 619219820Sjeff /* Check that the item was successfully inserted. */ 620219820Sjeff if (p_item2 != p_item) { 621219820Sjeff /* Put the item in back in the source map. */ 622219820Sjeff p_item2 = 623219820Sjeff cl_qmap_insert(p_src_map, cl_qmap_key(p_item), 624219820Sjeff p_item); 625219820Sjeff CL_ASSERT(p_item2 == p_item); 626219820Sjeff } 627219820Sjeff p_item = p_next; 628219820Sjeff } 629219820Sjeff} 630219820Sjeff 631219820Sjeffstatic void 632219820Sjeff__cl_qmap_delta_move(IN OUT cl_qmap_t * const p_dest, 633219820Sjeff IN OUT cl_qmap_t * const p_src, 634219820Sjeff IN OUT cl_map_item_t ** const pp_item) 635219820Sjeff{ 636219820Sjeff cl_map_item_t *p_temp, *p_next; 637219820Sjeff 638219820Sjeff /* 639219820Sjeff * Get the next item so that we can ensure that pp_item points to 640219820Sjeff * a valid item upon return from the function. 641219820Sjeff */ 642219820Sjeff p_next = cl_qmap_next(*pp_item); 643219820Sjeff /* Move the old item from its current map the the old map. */ 644219820Sjeff cl_qmap_remove_item(p_src, *pp_item); 645219820Sjeff p_temp = cl_qmap_insert(p_dest, cl_qmap_key(*pp_item), *pp_item); 646219820Sjeff /* We should never have duplicates. */ 647219820Sjeff CL_ASSERT(p_temp == *pp_item); 648219820Sjeff /* Point pp_item to a valid item in the source map. */ 649219820Sjeff (*pp_item) = p_next; 650219820Sjeff} 651219820Sjeff 652219820Sjeffvoid 653219820Sjeffcl_qmap_delta(IN OUT cl_qmap_t * const p_map1, 654219820Sjeff IN OUT cl_qmap_t * const p_map2, 655219820Sjeff OUT cl_qmap_t * const p_new, OUT cl_qmap_t * const p_old) 656219820Sjeff{ 657219820Sjeff cl_map_item_t *p_item1, *p_item2; 658219820Sjeff uint64_t key1, key2; 659219820Sjeff 660219820Sjeff CL_ASSERT(p_map1); 661219820Sjeff CL_ASSERT(p_map2); 662219820Sjeff CL_ASSERT(p_new); 663219820Sjeff CL_ASSERT(p_old); 664219820Sjeff CL_ASSERT(cl_is_qmap_empty(p_new)); 665219820Sjeff CL_ASSERT(cl_is_qmap_empty(p_old)); 666219820Sjeff 667219820Sjeff p_item1 = cl_qmap_head(p_map1); 668219820Sjeff p_item2 = cl_qmap_head(p_map2); 669219820Sjeff 670219820Sjeff while (p_item1 != cl_qmap_end(p_map1) && p_item2 != cl_qmap_end(p_map2)) { 671219820Sjeff key1 = cl_qmap_key(p_item1); 672219820Sjeff key2 = cl_qmap_key(p_item2); 673219820Sjeff if (key1 < key2) { 674219820Sjeff /* We found an old item. */ 675219820Sjeff __cl_qmap_delta_move(p_old, p_map1, &p_item1); 676219820Sjeff } else if (key1 > key2) { 677219820Sjeff /* We found a new item. */ 678219820Sjeff __cl_qmap_delta_move(p_new, p_map2, &p_item2); 679219820Sjeff } else { 680219820Sjeff /* Move both forward since they have the same key. */ 681219820Sjeff p_item1 = cl_qmap_next(p_item1); 682219820Sjeff p_item2 = cl_qmap_next(p_item2); 683219820Sjeff } 684219820Sjeff } 685219820Sjeff 686219820Sjeff /* Process the remainder if the end of either source map was reached. */ 687219820Sjeff while (p_item2 != cl_qmap_end(p_map2)) 688219820Sjeff __cl_qmap_delta_move(p_new, p_map2, &p_item2); 689219820Sjeff 690219820Sjeff while (p_item1 != cl_qmap_end(p_map1)) 691219820Sjeff __cl_qmap_delta_move(p_old, p_map1, &p_item1); 692219820Sjeff} 693219820Sjeff 694219820Sjeff/****************************************************************************** 695219820Sjeff******************************************************************************* 696219820Sjeff************** ************ 697219820Sjeff************** IMPLEMENTATION OF MAP ************ 698219820Sjeff************** ************ 699219820Sjeff******************************************************************************* 700219820Sjeff******************************************************************************/ 701219820Sjeff 702219820Sjeff#define MAP_GROW_SIZE 32 703219820Sjeff 704219820Sjeffvoid cl_map_construct(IN cl_map_t * const p_map) 705219820Sjeff{ 706219820Sjeff CL_ASSERT(p_map); 707219820Sjeff 708219820Sjeff cl_qpool_construct(&p_map->pool); 709219820Sjeff} 710219820Sjeff 711219820Sjeffcl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items) 712219820Sjeff{ 713219820Sjeff uint32_t grow_size; 714219820Sjeff 715219820Sjeff CL_ASSERT(p_map); 716219820Sjeff 717219820Sjeff cl_qmap_init(&p_map->qmap); 718219820Sjeff 719219820Sjeff /* 720219820Sjeff * We will grow by min_items/8 items at a time, with a minimum of 721219820Sjeff * MAP_GROW_SIZE. 722219820Sjeff */ 723219820Sjeff grow_size = min_items >> 3; 724219820Sjeff if (grow_size < MAP_GROW_SIZE) 725219820Sjeff grow_size = MAP_GROW_SIZE; 726219820Sjeff 727219820Sjeff return (cl_qpool_init(&p_map->pool, min_items, 0, grow_size, 728219820Sjeff sizeof(cl_map_obj_t), NULL, NULL, NULL)); 729219820Sjeff} 730219820Sjeff 731219820Sjeffvoid cl_map_destroy(IN cl_map_t * const p_map) 732219820Sjeff{ 733219820Sjeff CL_ASSERT(p_map); 734219820Sjeff 735219820Sjeff cl_qpool_destroy(&p_map->pool); 736219820Sjeff} 737219820Sjeff 738219820Sjeffvoid *cl_map_insert(IN cl_map_t * const p_map, 739219820Sjeff IN const uint64_t key, IN const void *const p_object) 740219820Sjeff{ 741219820Sjeff cl_map_obj_t *p_map_obj, *p_obj_at_key; 742219820Sjeff 743219820Sjeff CL_ASSERT(p_map); 744219820Sjeff 745219820Sjeff p_map_obj = (cl_map_obj_t *) cl_qpool_get(&p_map->pool); 746219820Sjeff 747219820Sjeff if (!p_map_obj) 748219820Sjeff return (NULL); 749219820Sjeff 750219820Sjeff cl_qmap_set_obj(p_map_obj, p_object); 751219820Sjeff 752219820Sjeff p_obj_at_key = 753219820Sjeff (cl_map_obj_t *) cl_qmap_insert(&p_map->qmap, key, 754219820Sjeff &p_map_obj->item); 755219820Sjeff 756219820Sjeff /* Return the item to the pool if insertion failed. */ 757219820Sjeff if (p_obj_at_key != p_map_obj) 758219820Sjeff cl_qpool_put(&p_map->pool, &p_map_obj->item.pool_item); 759219820Sjeff 760219820Sjeff return (cl_qmap_obj(p_obj_at_key)); 761219820Sjeff} 762219820Sjeff 763219820Sjeffvoid *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key) 764219820Sjeff{ 765219820Sjeff cl_map_item_t *p_item; 766219820Sjeff 767219820Sjeff CL_ASSERT(p_map); 768219820Sjeff 769219820Sjeff p_item = cl_qmap_get(&p_map->qmap, key); 770219820Sjeff 771219820Sjeff if (p_item == cl_qmap_end(&p_map->qmap)) 772219820Sjeff return (NULL); 773219820Sjeff 774219820Sjeff return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item))); 775219820Sjeff} 776219820Sjeff 777219820Sjeffvoid *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key) 778219820Sjeff{ 779219820Sjeff cl_map_item_t *p_item; 780219820Sjeff 781219820Sjeff CL_ASSERT(p_map); 782219820Sjeff 783219820Sjeff p_item = cl_qmap_get_next(&p_map->qmap, key); 784219820Sjeff 785219820Sjeff if (p_item == cl_qmap_end(&p_map->qmap)) 786219820Sjeff return (NULL); 787219820Sjeff 788219820Sjeff return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item))); 789219820Sjeff} 790219820Sjeff 791219820Sjeffvoid 792219820Sjeffcl_map_remove_item(IN cl_map_t * const p_map, IN const cl_map_iterator_t itor) 793219820Sjeff{ 794219820Sjeff CL_ASSERT(itor->p_map == &p_map->qmap); 795219820Sjeff 796219820Sjeff if (itor == cl_map_end(p_map)) 797219820Sjeff return; 798219820Sjeff 799219820Sjeff cl_qmap_remove_item(&p_map->qmap, (cl_map_item_t *) itor); 800219820Sjeff cl_qpool_put(&p_map->pool, &((cl_map_item_t *) itor)->pool_item); 801219820Sjeff} 802219820Sjeff 803219820Sjeffvoid *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key) 804219820Sjeff{ 805219820Sjeff cl_map_item_t *p_item; 806219820Sjeff void *p_obj; 807219820Sjeff 808219820Sjeff CL_ASSERT(p_map); 809219820Sjeff 810219820Sjeff p_item = cl_qmap_remove(&p_map->qmap, key); 811219820Sjeff 812219820Sjeff if (p_item == cl_qmap_end(&p_map->qmap)) 813219820Sjeff return (NULL); 814219820Sjeff 815219820Sjeff p_obj = cl_qmap_obj((cl_map_obj_t *) p_item); 816219820Sjeff cl_qpool_put(&p_map->pool, &p_item->pool_item); 817219820Sjeff 818219820Sjeff return (p_obj); 819219820Sjeff} 820219820Sjeff 821219820Sjeffvoid cl_map_remove_all(IN cl_map_t * const p_map) 822219820Sjeff{ 823219820Sjeff cl_map_item_t *p_item; 824219820Sjeff 825219820Sjeff CL_ASSERT(p_map); 826219820Sjeff 827219820Sjeff /* Return all map items to the pool. */ 828219820Sjeff while (!cl_is_qmap_empty(&p_map->qmap)) { 829219820Sjeff p_item = cl_qmap_head(&p_map->qmap); 830219820Sjeff cl_qmap_remove_item(&p_map->qmap, p_item); 831219820Sjeff cl_qpool_put(&p_map->pool, &p_item->pool_item); 832219820Sjeff 833219820Sjeff if (!cl_is_qmap_empty(&p_map->qmap)) { 834219820Sjeff p_item = cl_qmap_tail(&p_map->qmap); 835219820Sjeff cl_qmap_remove_item(&p_map->qmap, p_item); 836219820Sjeff cl_qpool_put(&p_map->pool, &p_item->pool_item); 837219820Sjeff } 838219820Sjeff } 839219820Sjeff} 840219820Sjeff 841219820Sjeffcl_status_t 842219820Sjeffcl_map_merge(OUT cl_map_t * const p_dest_map, IN OUT cl_map_t * const p_src_map) 843219820Sjeff{ 844219820Sjeff cl_status_t status = CL_SUCCESS; 845219820Sjeff cl_map_iterator_t itor, next; 846219820Sjeff uint64_t key; 847219820Sjeff void *p_obj, *p_obj2; 848219820Sjeff 849219820Sjeff CL_ASSERT(p_dest_map); 850219820Sjeff CL_ASSERT(p_src_map); 851219820Sjeff 852219820Sjeff itor = cl_map_head(p_src_map); 853219820Sjeff while (itor != cl_map_end(p_src_map)) { 854219820Sjeff next = cl_map_next(itor); 855219820Sjeff 856219820Sjeff p_obj = cl_map_obj(itor); 857219820Sjeff key = cl_map_key(itor); 858219820Sjeff 859219820Sjeff cl_map_remove_item(p_src_map, itor); 860219820Sjeff 861219820Sjeff /* Insert the object into the destination map. */ 862219820Sjeff p_obj2 = cl_map_insert(p_dest_map, key, p_obj); 863219820Sjeff /* Trap for failure. */ 864219820Sjeff if (p_obj != p_obj2) { 865219820Sjeff if (!p_obj2) 866219820Sjeff status = CL_INSUFFICIENT_MEMORY; 867219820Sjeff /* Put the object back in the source map. This must succeed. */ 868219820Sjeff p_obj2 = cl_map_insert(p_src_map, key, p_obj); 869219820Sjeff CL_ASSERT(p_obj == p_obj2); 870219820Sjeff /* If the failure was due to insufficient memory, return. */ 871219820Sjeff if (status != CL_SUCCESS) 872219820Sjeff return (status); 873219820Sjeff } 874219820Sjeff itor = next; 875219820Sjeff } 876219820Sjeff 877219820Sjeff return (CL_SUCCESS); 878219820Sjeff} 879219820Sjeff 880219820Sjeffstatic void 881219820Sjeff__cl_map_revert(IN OUT cl_map_t * const p_map1, 882219820Sjeff IN OUT cl_map_t * const p_map2, 883219820Sjeff IN OUT cl_map_t * const p_new, IN OUT cl_map_t * const p_old) 884219820Sjeff{ 885219820Sjeff cl_status_t status; 886219820Sjeff 887219820Sjeff /* Restore the initial state. */ 888219820Sjeff status = cl_map_merge(p_map1, p_old); 889219820Sjeff CL_ASSERT(status == CL_SUCCESS); 890219820Sjeff status = cl_map_merge(p_map2, p_new); 891219820Sjeff CL_ASSERT(status == CL_SUCCESS); 892219820Sjeff} 893219820Sjeff 894219820Sjeffstatic cl_status_t 895219820Sjeff__cl_map_delta_move(OUT cl_map_t * const p_dest, 896219820Sjeff IN OUT cl_map_t * const p_src, 897219820Sjeff IN OUT cl_map_iterator_t * const p_itor) 898219820Sjeff{ 899219820Sjeff cl_map_iterator_t next; 900219820Sjeff void *p_obj, *p_obj2; 901219820Sjeff uint64_t key; 902219820Sjeff 903219820Sjeff /* Get a valid iterator so we can continue the loop. */ 904219820Sjeff next = cl_map_next(*p_itor); 905219820Sjeff /* Get the pointer to the object for insertion. */ 906219820Sjeff p_obj = cl_map_obj(*p_itor); 907219820Sjeff /* Get the key for the object. */ 908219820Sjeff key = cl_map_key(*p_itor); 909219820Sjeff /* Move the object. */ 910219820Sjeff cl_map_remove_item(p_src, *p_itor); 911219820Sjeff p_obj2 = cl_map_insert(p_dest, key, p_obj); 912219820Sjeff /* Check for failure. We should never get a duplicate. */ 913219820Sjeff if (!p_obj2) { 914219820Sjeff p_obj2 = cl_map_insert(p_src, key, p_obj); 915219820Sjeff CL_ASSERT(p_obj2 == p_obj); 916219820Sjeff return (CL_INSUFFICIENT_MEMORY); 917219820Sjeff } 918219820Sjeff 919219820Sjeff /* We should never get a duplicate */ 920219820Sjeff CL_ASSERT(p_obj == p_obj2); 921219820Sjeff /* Update the iterator so that it is valid. */ 922219820Sjeff (*p_itor) = next; 923219820Sjeff 924219820Sjeff return (CL_SUCCESS); 925219820Sjeff} 926219820Sjeff 927219820Sjeffcl_status_t 928219820Sjeffcl_map_delta(IN OUT cl_map_t * const p_map1, 929219820Sjeff IN OUT cl_map_t * const p_map2, 930219820Sjeff OUT cl_map_t * const p_new, OUT cl_map_t * const p_old) 931219820Sjeff{ 932219820Sjeff cl_map_iterator_t itor1, itor2; 933219820Sjeff uint64_t key1, key2; 934219820Sjeff cl_status_t status; 935219820Sjeff 936219820Sjeff CL_ASSERT(p_map1); 937219820Sjeff CL_ASSERT(p_map2); 938219820Sjeff CL_ASSERT(p_new); 939219820Sjeff CL_ASSERT(p_old); 940219820Sjeff CL_ASSERT(cl_is_map_empty(p_new)); 941219820Sjeff CL_ASSERT(cl_is_map_empty(p_old)); 942219820Sjeff 943219820Sjeff itor1 = cl_map_head(p_map1); 944219820Sjeff itor2 = cl_map_head(p_map2); 945219820Sjeff 946219820Sjeff /* 947219820Sjeff * Note that the check is for the end, since duplicate items will remain 948219820Sjeff * in their respective maps. 949219820Sjeff */ 950219820Sjeff while (itor1 != cl_map_end(p_map1) && itor2 != cl_map_end(p_map2)) { 951219820Sjeff key1 = cl_map_key(itor1); 952219820Sjeff key2 = cl_map_key(itor2); 953219820Sjeff if (key1 < key2) { 954219820Sjeff status = __cl_map_delta_move(p_old, p_map1, &itor1); 955219820Sjeff /* Check for failure. */ 956219820Sjeff if (status != CL_SUCCESS) { 957219820Sjeff /* Restore the initial state. */ 958219820Sjeff __cl_map_revert(p_map1, p_map2, p_new, p_old); 959219820Sjeff /* Return the failure status. */ 960219820Sjeff return (status); 961219820Sjeff } 962219820Sjeff } else if (key1 > key2) { 963219820Sjeff status = __cl_map_delta_move(p_new, p_map2, &itor2); 964219820Sjeff if (status != CL_SUCCESS) { 965219820Sjeff /* Restore the initial state. */ 966219820Sjeff __cl_map_revert(p_map1, p_map2, p_new, p_old); 967219820Sjeff /* Return the failure status. */ 968219820Sjeff return (status); 969219820Sjeff } 970219820Sjeff } else { 971219820Sjeff /* Move both forward since they have the same key. */ 972219820Sjeff itor1 = cl_map_next(itor1); 973219820Sjeff itor2 = cl_map_next(itor2); 974219820Sjeff } 975219820Sjeff } 976219820Sjeff 977219820Sjeff /* Process the remainder if either source map is empty. */ 978219820Sjeff while (itor2 != cl_map_end(p_map2)) { 979219820Sjeff status = __cl_map_delta_move(p_new, p_map2, &itor2); 980219820Sjeff if (status != CL_SUCCESS) { 981219820Sjeff /* Restore the initial state. */ 982219820Sjeff __cl_map_revert(p_map1, p_map2, p_new, p_old); 983219820Sjeff /* Return the failure status. */ 984219820Sjeff return (status); 985219820Sjeff } 986219820Sjeff } 987219820Sjeff 988219820Sjeff while (itor1 != cl_map_end(p_map1)) { 989219820Sjeff status = __cl_map_delta_move(p_old, p_map1, &itor1); 990219820Sjeff if (status != CL_SUCCESS) { 991219820Sjeff /* Restore the initial state. */ 992219820Sjeff __cl_map_revert(p_map1, p_map2, p_new, p_old); 993219820Sjeff /* Return the failure status. */ 994219820Sjeff return (status); 995219820Sjeff } 996219820Sjeff } 997219820Sjeff 998219820Sjeff return (CL_SUCCESS); 999219820Sjeff} 1000219820Sjeff 1001219820Sjeff/****************************************************************************** 1002219820Sjeff******************************************************************************* 1003219820Sjeff************** ************ 1004219820Sjeff************** IMPLEMENTATION OF FLEXI MAP ************ 1005219820Sjeff************** ************ 1006219820Sjeff******************************************************************************* 1007219820Sjeff******************************************************************************/ 1008219820Sjeff 1009219820Sjeff/* 1010219820Sjeff * Get the root. 1011219820Sjeff */ 1012219820Sjeffstatic inline cl_fmap_item_t *__cl_fmap_root(IN const cl_fmap_t * const p_map) 1013219820Sjeff{ 1014219820Sjeff CL_ASSERT(p_map); 1015219820Sjeff return (p_map->root.p_left); 1016219820Sjeff} 1017219820Sjeff 1018219820Sjeff/* 1019219820Sjeff * Returns whether a given item is on the left of its parent. 1020219820Sjeff */ 1021219820Sjeffstatic boolean_t __cl_fmap_is_left_child(IN const cl_fmap_item_t * const p_item) 1022219820Sjeff{ 1023219820Sjeff CL_ASSERT(p_item); 1024219820Sjeff CL_ASSERT(p_item->p_up); 1025219820Sjeff CL_ASSERT(p_item->p_up != p_item); 1026219820Sjeff 1027219820Sjeff return (p_item->p_up->p_left == p_item); 1028219820Sjeff} 1029219820Sjeff 1030219820Sjeff/* 1031219820Sjeff * Retrieve the pointer to the parent's pointer to an item. 1032219820Sjeff */ 1033219820Sjeffstatic cl_fmap_item_t **__cl_fmap_get_parent_ptr_to_item(IN cl_fmap_item_t * 1034219820Sjeff const p_item) 1035219820Sjeff{ 1036219820Sjeff CL_ASSERT(p_item); 1037219820Sjeff CL_ASSERT(p_item->p_up); 1038219820Sjeff CL_ASSERT(p_item->p_up != p_item); 1039219820Sjeff 1040219820Sjeff if (__cl_fmap_is_left_child(p_item)) 1041219820Sjeff return (&p_item->p_up->p_left); 1042219820Sjeff 1043219820Sjeff CL_ASSERT(p_item->p_up->p_right == p_item); 1044219820Sjeff return (&p_item->p_up->p_right); 1045219820Sjeff} 1046219820Sjeff 1047219820Sjeff/* 1048219820Sjeff * Rotate a node to the left. This rotation affects the least number of links 1049219820Sjeff * between nodes and brings the level of C up by one while increasing the depth 1050219820Sjeff * of A one. Note that the links to/from W, X, Y, and Z are not affected. 1051219820Sjeff * 1052219820Sjeff * R R 1053219820Sjeff * | | 1054219820Sjeff * A C 1055219820Sjeff * / \ / \ 1056219820Sjeff * W C A Z 1057219820Sjeff * / \ / \ 1058219820Sjeff * B Z W B 1059219820Sjeff * / \ / \ 1060219820Sjeff * X Y X Y 1061219820Sjeff */ 1062219820Sjeffstatic void 1063219820Sjeff__cl_fmap_rot_left(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * const p_item) 1064219820Sjeff{ 1065219820Sjeff cl_fmap_item_t **pp_root; 1066219820Sjeff 1067219820Sjeff CL_ASSERT(p_map); 1068219820Sjeff CL_ASSERT(p_item); 1069219820Sjeff CL_ASSERT(p_item->p_right != &p_map->nil); 1070219820Sjeff 1071219820Sjeff pp_root = __cl_fmap_get_parent_ptr_to_item(p_item); 1072219820Sjeff 1073219820Sjeff /* Point R to C instead of A. */ 1074219820Sjeff *pp_root = p_item->p_right; 1075219820Sjeff /* Set C's parent to R. */ 1076219820Sjeff (*pp_root)->p_up = p_item->p_up; 1077219820Sjeff 1078219820Sjeff /* Set A's right to B */ 1079219820Sjeff p_item->p_right = (*pp_root)->p_left; 1080219820Sjeff /* 1081219820Sjeff * Set B's parent to A. We trap for B being NIL since the 1082219820Sjeff * caller may depend on NIL not changing. 1083219820Sjeff */ 1084219820Sjeff if ((*pp_root)->p_left != &p_map->nil) 1085219820Sjeff (*pp_root)->p_left->p_up = p_item; 1086219820Sjeff 1087219820Sjeff /* Set C's left to A. */ 1088219820Sjeff (*pp_root)->p_left = p_item; 1089219820Sjeff /* Set A's parent to C. */ 1090219820Sjeff p_item->p_up = *pp_root; 1091219820Sjeff} 1092219820Sjeff 1093219820Sjeff/* 1094219820Sjeff * Rotate a node to the right. This rotation affects the least number of links 1095219820Sjeff * between nodes and brings the level of A up by one while increasing the depth 1096219820Sjeff * of C one. Note that the links to/from W, X, Y, and Z are not affected. 1097219820Sjeff * 1098219820Sjeff * R R 1099219820Sjeff * | | 1100219820Sjeff * C A 1101219820Sjeff * / \ / \ 1102219820Sjeff * A Z W C 1103219820Sjeff * / \ / \ 1104219820Sjeff * W B B Z 1105219820Sjeff * / \ / \ 1106219820Sjeff * X Y X Y 1107219820Sjeff */ 1108219820Sjeffstatic void 1109219820Sjeff__cl_fmap_rot_right(IN cl_fmap_t * const p_map, 1110219820Sjeff IN cl_fmap_item_t * const p_item) 1111219820Sjeff{ 1112219820Sjeff cl_fmap_item_t **pp_root; 1113219820Sjeff 1114219820Sjeff CL_ASSERT(p_map); 1115219820Sjeff CL_ASSERT(p_item); 1116219820Sjeff CL_ASSERT(p_item->p_left != &p_map->nil); 1117219820Sjeff 1118219820Sjeff /* Point R to A instead of C. */ 1119219820Sjeff pp_root = __cl_fmap_get_parent_ptr_to_item(p_item); 1120219820Sjeff (*pp_root) = p_item->p_left; 1121219820Sjeff /* Set A's parent to R. */ 1122219820Sjeff (*pp_root)->p_up = p_item->p_up; 1123219820Sjeff 1124219820Sjeff /* Set C's left to B */ 1125219820Sjeff p_item->p_left = (*pp_root)->p_right; 1126219820Sjeff /* 1127219820Sjeff * Set B's parent to C. We trap for B being NIL since the 1128219820Sjeff * caller may depend on NIL not changing. 1129219820Sjeff */ 1130219820Sjeff if ((*pp_root)->p_right != &p_map->nil) 1131219820Sjeff (*pp_root)->p_right->p_up = p_item; 1132219820Sjeff 1133219820Sjeff /* Set A's right to C. */ 1134219820Sjeff (*pp_root)->p_right = p_item; 1135219820Sjeff /* Set C's parent to A. */ 1136219820Sjeff p_item->p_up = *pp_root; 1137219820Sjeff} 1138219820Sjeff 1139219820Sjeffvoid cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare) 1140219820Sjeff{ 1141219820Sjeff CL_ASSERT(p_map); 1142219820Sjeff CL_ASSERT(pfn_compare); 1143219820Sjeff 1144219820Sjeff memset(p_map, 0, sizeof(cl_fmap_t)); 1145219820Sjeff 1146219820Sjeff /* special setup for the root node */ 1147219820Sjeff p_map->root.p_up = &p_map->root; 1148219820Sjeff p_map->root.p_left = &p_map->nil; 1149219820Sjeff p_map->root.p_right = &p_map->nil; 1150219820Sjeff p_map->root.color = CL_MAP_BLACK; 1151219820Sjeff 1152219820Sjeff /* Setup the node used as terminator for all leaves. */ 1153219820Sjeff p_map->nil.p_up = &p_map->nil; 1154219820Sjeff p_map->nil.p_left = &p_map->nil; 1155219820Sjeff p_map->nil.p_right = &p_map->nil; 1156219820Sjeff p_map->nil.color = CL_MAP_BLACK; 1157219820Sjeff 1158219820Sjeff /* Store the compare function pointer. */ 1159219820Sjeff p_map->pfn_compare = pfn_compare; 1160219820Sjeff 1161219820Sjeff p_map->state = CL_INITIALIZED; 1162219820Sjeff 1163219820Sjeff cl_fmap_remove_all(p_map); 1164219820Sjeff} 1165219820Sjeff 1166219820Sjeffcl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map, 1167219820Sjeff IN const void *const p_key) 1168219820Sjeff{ 1169219820Sjeff cl_fmap_item_t *p_item; 1170219820Sjeff intn_t cmp; 1171219820Sjeff 1172219820Sjeff CL_ASSERT(p_map); 1173219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 1174219820Sjeff 1175219820Sjeff p_item = __cl_fmap_root(p_map); 1176219820Sjeff 1177219820Sjeff while (p_item != &p_map->nil) { 1178219820Sjeff cmp = p_map->pfn_compare(p_key, p_item->p_key); 1179219820Sjeff 1180219820Sjeff if (!cmp) 1181219820Sjeff break; /* just right */ 1182219820Sjeff 1183219820Sjeff if (cmp < 0) 1184219820Sjeff p_item = p_item->p_left; /* too small */ 1185219820Sjeff else 1186219820Sjeff p_item = p_item->p_right; /* too big */ 1187219820Sjeff } 1188219820Sjeff 1189219820Sjeff return (p_item); 1190219820Sjeff} 1191219820Sjeff 1192219820Sjeffcl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map, 1193219820Sjeff IN const void *const p_key) 1194219820Sjeff{ 1195219820Sjeff cl_fmap_item_t *p_item; 1196219820Sjeff cl_fmap_item_t *p_item_found; 1197219820Sjeff intn_t cmp; 1198219820Sjeff 1199219820Sjeff CL_ASSERT(p_map); 1200219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 1201219820Sjeff 1202219820Sjeff p_item = __cl_fmap_root(p_map); 1203219820Sjeff p_item_found = (cl_fmap_item_t *) & p_map->nil; 1204219820Sjeff 1205219820Sjeff while (p_item != &p_map->nil) { 1206219820Sjeff cmp = p_map->pfn_compare(p_key, p_item->p_key); 1207219820Sjeff 1208219820Sjeff if (cmp < 0) { 1209219820Sjeff p_item_found = p_item; 1210219820Sjeff p_item = p_item->p_left; /* too small */ 1211219820Sjeff } else { 1212219820Sjeff p_item = p_item->p_right; /* too big or match */ 1213219820Sjeff } 1214219820Sjeff } 1215219820Sjeff 1216219820Sjeff return (p_item_found); 1217219820Sjeff} 1218219820Sjeff 1219219820Sjeffvoid 1220219820Sjeffcl_fmap_apply_func(IN const cl_fmap_t * const p_map, 1221219820Sjeff IN cl_pfn_fmap_apply_t pfn_func, 1222219820Sjeff IN const void *const context) 1223219820Sjeff{ 1224219820Sjeff cl_fmap_item_t *p_fmap_item; 1225219820Sjeff 1226219820Sjeff /* Note that context can have any arbitrary value. */ 1227219820Sjeff CL_ASSERT(p_map); 1228219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 1229219820Sjeff CL_ASSERT(pfn_func); 1230219820Sjeff 1231219820Sjeff p_fmap_item = cl_fmap_head(p_map); 1232219820Sjeff while (p_fmap_item != cl_fmap_end(p_map)) { 1233219820Sjeff pfn_func(p_fmap_item, (void *)context); 1234219820Sjeff p_fmap_item = cl_fmap_next(p_fmap_item); 1235219820Sjeff } 1236219820Sjeff} 1237219820Sjeff 1238219820Sjeff/* 1239219820Sjeff * Balance a tree starting at a given item back to the root. 1240219820Sjeff */ 1241219820Sjeffstatic void 1242219820Sjeff__cl_fmap_ins_bal(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * p_item) 1243219820Sjeff{ 1244219820Sjeff cl_fmap_item_t *p_grand_uncle; 1245219820Sjeff 1246219820Sjeff CL_ASSERT(p_map); 1247219820Sjeff CL_ASSERT(p_item); 1248219820Sjeff CL_ASSERT(p_item != &p_map->root); 1249219820Sjeff 1250219820Sjeff while (p_item->p_up->color == CL_MAP_RED) { 1251219820Sjeff if (__cl_fmap_is_left_child(p_item->p_up)) { 1252219820Sjeff p_grand_uncle = p_item->p_up->p_up->p_right; 1253219820Sjeff CL_ASSERT(p_grand_uncle); 1254219820Sjeff if (p_grand_uncle->color == CL_MAP_RED) { 1255219820Sjeff p_grand_uncle->color = CL_MAP_BLACK; 1256219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 1257219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 1258219820Sjeff p_item = p_item->p_up->p_up; 1259219820Sjeff continue; 1260219820Sjeff } 1261219820Sjeff 1262219820Sjeff if (!__cl_fmap_is_left_child(p_item)) { 1263219820Sjeff p_item = p_item->p_up; 1264219820Sjeff __cl_fmap_rot_left(p_map, p_item); 1265219820Sjeff } 1266219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 1267219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 1268219820Sjeff __cl_fmap_rot_right(p_map, p_item->p_up->p_up); 1269219820Sjeff } else { 1270219820Sjeff p_grand_uncle = p_item->p_up->p_up->p_left; 1271219820Sjeff CL_ASSERT(p_grand_uncle); 1272219820Sjeff if (p_grand_uncle->color == CL_MAP_RED) { 1273219820Sjeff p_grand_uncle->color = CL_MAP_BLACK; 1274219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 1275219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 1276219820Sjeff p_item = p_item->p_up->p_up; 1277219820Sjeff continue; 1278219820Sjeff } 1279219820Sjeff 1280219820Sjeff if (__cl_fmap_is_left_child(p_item)) { 1281219820Sjeff p_item = p_item->p_up; 1282219820Sjeff __cl_fmap_rot_right(p_map, p_item); 1283219820Sjeff } 1284219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 1285219820Sjeff p_item->p_up->p_up->color = CL_MAP_RED; 1286219820Sjeff __cl_fmap_rot_left(p_map, p_item->p_up->p_up); 1287219820Sjeff } 1288219820Sjeff } 1289219820Sjeff} 1290219820Sjeff 1291219820Sjeffcl_fmap_item_t *cl_fmap_insert(IN cl_fmap_t * const p_map, 1292219820Sjeff IN const void *const p_key, 1293219820Sjeff IN cl_fmap_item_t * const p_item) 1294219820Sjeff{ 1295219820Sjeff cl_fmap_item_t *p_insert_at, *p_comp_item; 1296219820Sjeff intn_t cmp = 0; 1297219820Sjeff 1298219820Sjeff CL_ASSERT(p_map); 1299219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 1300219820Sjeff CL_ASSERT(p_item); 1301219820Sjeff CL_ASSERT(p_map->root.p_up == &p_map->root); 1302219820Sjeff CL_ASSERT(p_map->root.color != CL_MAP_RED); 1303219820Sjeff CL_ASSERT(p_map->nil.color != CL_MAP_RED); 1304219820Sjeff 1305219820Sjeff p_item->p_left = &p_map->nil; 1306219820Sjeff p_item->p_right = &p_map->nil; 1307219820Sjeff p_item->p_key = p_key; 1308219820Sjeff p_item->color = CL_MAP_RED; 1309219820Sjeff 1310219820Sjeff /* Find the insertion location. */ 1311219820Sjeff p_insert_at = &p_map->root; 1312219820Sjeff p_comp_item = __cl_fmap_root(p_map); 1313219820Sjeff 1314219820Sjeff while (p_comp_item != &p_map->nil) { 1315219820Sjeff p_insert_at = p_comp_item; 1316219820Sjeff 1317219820Sjeff cmp = p_map->pfn_compare(p_key, p_insert_at->p_key); 1318219820Sjeff 1319219820Sjeff if (!cmp) 1320219820Sjeff return (p_insert_at); 1321219820Sjeff 1322219820Sjeff /* Traverse the tree until the correct insertion point is found. */ 1323219820Sjeff if (cmp < 0) 1324219820Sjeff p_comp_item = p_insert_at->p_left; 1325219820Sjeff else 1326219820Sjeff p_comp_item = p_insert_at->p_right; 1327219820Sjeff } 1328219820Sjeff 1329219820Sjeff CL_ASSERT(p_insert_at != &p_map->nil); 1330219820Sjeff CL_ASSERT(p_comp_item == &p_map->nil); 1331219820Sjeff /* Insert the item. */ 1332219820Sjeff if (p_insert_at == &p_map->root) { 1333219820Sjeff p_insert_at->p_left = p_item; 1334219820Sjeff /* 1335219820Sjeff * Primitive insert places the new item in front of 1336219820Sjeff * the existing item. 1337219820Sjeff */ 1338219820Sjeff __cl_primitive_insert(&p_map->nil.pool_item.list_item, 1339219820Sjeff &p_item->pool_item.list_item); 1340219820Sjeff } else if (cmp < 0) { 1341219820Sjeff p_insert_at->p_left = p_item; 1342219820Sjeff /* 1343219820Sjeff * Primitive insert places the new item in front of 1344219820Sjeff * the existing item. 1345219820Sjeff */ 1346219820Sjeff __cl_primitive_insert(&p_insert_at->pool_item.list_item, 1347219820Sjeff &p_item->pool_item.list_item); 1348219820Sjeff } else { 1349219820Sjeff p_insert_at->p_right = p_item; 1350219820Sjeff /* 1351219820Sjeff * Primitive insert places the new item in front of 1352219820Sjeff * the existing item. 1353219820Sjeff */ 1354219820Sjeff __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next, 1355219820Sjeff &p_item->pool_item.list_item); 1356219820Sjeff } 1357219820Sjeff /* Increase the count. */ 1358219820Sjeff p_map->count++; 1359219820Sjeff 1360219820Sjeff p_item->p_up = p_insert_at; 1361219820Sjeff 1362219820Sjeff /* 1363219820Sjeff * We have added depth to this section of the tree. 1364219820Sjeff * Rebalance as necessary as we retrace our path through the tree 1365219820Sjeff * and update colors. 1366219820Sjeff */ 1367219820Sjeff __cl_fmap_ins_bal(p_map, p_item); 1368219820Sjeff 1369219820Sjeff __cl_fmap_root(p_map)->color = CL_MAP_BLACK; 1370219820Sjeff 1371219820Sjeff /* 1372219820Sjeff * Note that it is not necessary to re-color the nil node black because all 1373219820Sjeff * red color assignments are made via the p_up pointer, and nil is never 1374219820Sjeff * set as the value of a p_up pointer. 1375219820Sjeff */ 1376219820Sjeff 1377219820Sjeff#ifdef _DEBUG_ 1378219820Sjeff /* Set the pointer to the map in the map item for consistency checking. */ 1379219820Sjeff p_item->p_map = p_map; 1380219820Sjeff#endif 1381219820Sjeff 1382219820Sjeff return (p_item); 1383219820Sjeff} 1384219820Sjeff 1385219820Sjeffstatic void 1386219820Sjeff__cl_fmap_del_bal(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * p_item) 1387219820Sjeff{ 1388219820Sjeff cl_fmap_item_t *p_uncle; 1389219820Sjeff 1390219820Sjeff while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) { 1391219820Sjeff if (__cl_fmap_is_left_child(p_item)) { 1392219820Sjeff p_uncle = p_item->p_up->p_right; 1393219820Sjeff 1394219820Sjeff if (p_uncle->color == CL_MAP_RED) { 1395219820Sjeff p_uncle->color = CL_MAP_BLACK; 1396219820Sjeff p_item->p_up->color = CL_MAP_RED; 1397219820Sjeff __cl_fmap_rot_left(p_map, p_item->p_up); 1398219820Sjeff p_uncle = p_item->p_up->p_right; 1399219820Sjeff } 1400219820Sjeff 1401219820Sjeff if (p_uncle->p_right->color != CL_MAP_RED) { 1402219820Sjeff if (p_uncle->p_left->color != CL_MAP_RED) { 1403219820Sjeff p_uncle->color = CL_MAP_RED; 1404219820Sjeff p_item = p_item->p_up; 1405219820Sjeff continue; 1406219820Sjeff } 1407219820Sjeff 1408219820Sjeff p_uncle->p_left->color = CL_MAP_BLACK; 1409219820Sjeff p_uncle->color = CL_MAP_RED; 1410219820Sjeff __cl_fmap_rot_right(p_map, p_uncle); 1411219820Sjeff p_uncle = p_item->p_up->p_right; 1412219820Sjeff } 1413219820Sjeff p_uncle->color = p_item->p_up->color; 1414219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 1415219820Sjeff p_uncle->p_right->color = CL_MAP_BLACK; 1416219820Sjeff __cl_fmap_rot_left(p_map, p_item->p_up); 1417219820Sjeff break; 1418219820Sjeff } else { 1419219820Sjeff p_uncle = p_item->p_up->p_left; 1420219820Sjeff 1421219820Sjeff if (p_uncle->color == CL_MAP_RED) { 1422219820Sjeff p_uncle->color = CL_MAP_BLACK; 1423219820Sjeff p_item->p_up->color = CL_MAP_RED; 1424219820Sjeff __cl_fmap_rot_right(p_map, p_item->p_up); 1425219820Sjeff p_uncle = p_item->p_up->p_left; 1426219820Sjeff } 1427219820Sjeff 1428219820Sjeff if (p_uncle->p_left->color != CL_MAP_RED) { 1429219820Sjeff if (p_uncle->p_right->color != CL_MAP_RED) { 1430219820Sjeff p_uncle->color = CL_MAP_RED; 1431219820Sjeff p_item = p_item->p_up; 1432219820Sjeff continue; 1433219820Sjeff } 1434219820Sjeff 1435219820Sjeff p_uncle->p_right->color = CL_MAP_BLACK; 1436219820Sjeff p_uncle->color = CL_MAP_RED; 1437219820Sjeff __cl_fmap_rot_left(p_map, p_uncle); 1438219820Sjeff p_uncle = p_item->p_up->p_left; 1439219820Sjeff } 1440219820Sjeff p_uncle->color = p_item->p_up->color; 1441219820Sjeff p_item->p_up->color = CL_MAP_BLACK; 1442219820Sjeff p_uncle->p_left->color = CL_MAP_BLACK; 1443219820Sjeff __cl_fmap_rot_right(p_map, p_item->p_up); 1444219820Sjeff break; 1445219820Sjeff } 1446219820Sjeff } 1447219820Sjeff p_item->color = CL_MAP_BLACK; 1448219820Sjeff} 1449219820Sjeff 1450219820Sjeffvoid 1451219820Sjeffcl_fmap_remove_item(IN cl_fmap_t * const p_map, 1452219820Sjeff IN cl_fmap_item_t * const p_item) 1453219820Sjeff{ 1454219820Sjeff cl_fmap_item_t *p_child, *p_del_item; 1455219820Sjeff 1456219820Sjeff CL_ASSERT(p_map); 1457219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 1458219820Sjeff CL_ASSERT(p_item); 1459219820Sjeff CL_ASSERT(p_item->p_map == p_map); 1460219820Sjeff 1461219820Sjeff if (p_item == cl_fmap_end(p_map)) 1462219820Sjeff return; 1463219820Sjeff 1464219820Sjeff if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) { 1465219820Sjeff /* The item being removed has children on at most on side. */ 1466219820Sjeff p_del_item = p_item; 1467219820Sjeff } else { 1468219820Sjeff /* 1469219820Sjeff * The item being removed has children on both side. 1470219820Sjeff * We select the item that will replace it. After removing 1471219820Sjeff * the substitute item and rebalancing, the tree will have the 1472219820Sjeff * correct topology. Exchanging the substitute for the item 1473219820Sjeff * will finalize the removal. 1474219820Sjeff */ 1475219820Sjeff p_del_item = cl_fmap_next(p_item); 1476219820Sjeff CL_ASSERT(p_del_item != &p_map->nil); 1477219820Sjeff } 1478219820Sjeff 1479219820Sjeff /* Remove the item from the list. */ 1480219820Sjeff __cl_primitive_remove(&p_item->pool_item.list_item); 1481219820Sjeff /* Decrement the item count. */ 1482219820Sjeff p_map->count--; 1483219820Sjeff 1484219820Sjeff /* Get the pointer to the new root's child, if any. */ 1485219820Sjeff if (p_del_item->p_left != &p_map->nil) 1486219820Sjeff p_child = p_del_item->p_left; 1487219820Sjeff else 1488219820Sjeff p_child = p_del_item->p_right; 1489219820Sjeff 1490219820Sjeff /* 1491219820Sjeff * This assignment may modify the parent pointer of the nil node. 1492219820Sjeff * This is inconsequential. 1493219820Sjeff */ 1494219820Sjeff p_child->p_up = p_del_item->p_up; 1495219820Sjeff (*__cl_fmap_get_parent_ptr_to_item(p_del_item)) = p_child; 1496219820Sjeff 1497219820Sjeff if (p_del_item->color != CL_MAP_RED) 1498219820Sjeff __cl_fmap_del_bal(p_map, p_child); 1499219820Sjeff 1500219820Sjeff /* 1501219820Sjeff * Note that the splicing done below does not need to occur before 1502219820Sjeff * the tree is balanced, since the actual topology changes are made by the 1503219820Sjeff * preceding code. The topology is preserved by the color assignment made 1504219820Sjeff * below (reader should be reminded that p_del_item == p_item in some cases). 1505219820Sjeff */ 1506219820Sjeff if (p_del_item != p_item) { 1507219820Sjeff /* 1508219820Sjeff * Finalize the removal of the specified item by exchanging it with 1509219820Sjeff * the substitute which we removed above. 1510219820Sjeff */ 1511219820Sjeff p_del_item->p_up = p_item->p_up; 1512219820Sjeff p_del_item->p_left = p_item->p_left; 1513219820Sjeff p_del_item->p_right = p_item->p_right; 1514219820Sjeff (*__cl_fmap_get_parent_ptr_to_item(p_item)) = p_del_item; 1515219820Sjeff p_item->p_right->p_up = p_del_item; 1516219820Sjeff p_item->p_left->p_up = p_del_item; 1517219820Sjeff p_del_item->color = p_item->color; 1518219820Sjeff } 1519219820Sjeff 1520219820Sjeff CL_ASSERT(p_map->nil.color != CL_MAP_RED); 1521219820Sjeff 1522219820Sjeff#ifdef _DEBUG_ 1523219820Sjeff /* Clear the pointer to the map since the item has been removed. */ 1524219820Sjeff p_item->p_map = NULL; 1525219820Sjeff#endif 1526219820Sjeff} 1527219820Sjeff 1528219820Sjeffcl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map, 1529219820Sjeff IN const void *const p_key) 1530219820Sjeff{ 1531219820Sjeff cl_fmap_item_t *p_item; 1532219820Sjeff 1533219820Sjeff CL_ASSERT(p_map); 1534219820Sjeff CL_ASSERT(p_map->state == CL_INITIALIZED); 1535219820Sjeff 1536219820Sjeff /* Seek the node with the specified key */ 1537219820Sjeff p_item = cl_fmap_get(p_map, p_key); 1538219820Sjeff 1539219820Sjeff cl_fmap_remove_item(p_map, p_item); 1540219820Sjeff 1541219820Sjeff return (p_item); 1542219820Sjeff} 1543219820Sjeff 1544219820Sjeffvoid 1545219820Sjeffcl_fmap_merge(OUT cl_fmap_t * const p_dest_map, 1546219820Sjeff IN OUT cl_fmap_t * const p_src_map) 1547219820Sjeff{ 1548219820Sjeff cl_fmap_item_t *p_item, *p_item2, *p_next; 1549219820Sjeff 1550219820Sjeff CL_ASSERT(p_dest_map); 1551219820Sjeff CL_ASSERT(p_src_map); 1552219820Sjeff 1553219820Sjeff p_item = cl_fmap_head(p_src_map); 1554219820Sjeff 1555219820Sjeff while (p_item != cl_fmap_end(p_src_map)) { 1556219820Sjeff p_next = cl_fmap_next(p_item); 1557219820Sjeff 1558219820Sjeff /* Remove the item from its current map. */ 1559219820Sjeff cl_fmap_remove_item(p_src_map, p_item); 1560219820Sjeff /* Insert the item into the destination map. */ 1561219820Sjeff p_item2 = 1562219820Sjeff cl_fmap_insert(p_dest_map, cl_fmap_key(p_item), p_item); 1563219820Sjeff /* Check that the item was successfully inserted. */ 1564219820Sjeff if (p_item2 != p_item) { 1565219820Sjeff /* Put the item in back in the source map. */ 1566219820Sjeff p_item2 = 1567219820Sjeff cl_fmap_insert(p_src_map, cl_fmap_key(p_item), 1568219820Sjeff p_item); 1569219820Sjeff CL_ASSERT(p_item2 == p_item); 1570219820Sjeff } 1571219820Sjeff p_item = p_next; 1572219820Sjeff } 1573219820Sjeff} 1574219820Sjeff 1575219820Sjeffstatic void 1576219820Sjeff__cl_fmap_delta_move(IN OUT cl_fmap_t * const p_dest, 1577219820Sjeff IN OUT cl_fmap_t * const p_src, 1578219820Sjeff IN OUT cl_fmap_item_t ** const pp_item) 1579219820Sjeff{ 1580219820Sjeff cl_fmap_item_t *p_temp, *p_next; 1581219820Sjeff 1582219820Sjeff /* 1583219820Sjeff * Get the next item so that we can ensure that pp_item points to 1584219820Sjeff * a valid item upon return from the function. 1585219820Sjeff */ 1586219820Sjeff p_next = cl_fmap_next(*pp_item); 1587219820Sjeff /* Move the old item from its current map the the old map. */ 1588219820Sjeff cl_fmap_remove_item(p_src, *pp_item); 1589219820Sjeff p_temp = cl_fmap_insert(p_dest, cl_fmap_key(*pp_item), *pp_item); 1590219820Sjeff /* We should never have duplicates. */ 1591219820Sjeff CL_ASSERT(p_temp == *pp_item); 1592219820Sjeff /* Point pp_item to a valid item in the source map. */ 1593219820Sjeff (*pp_item) = p_next; 1594219820Sjeff} 1595219820Sjeff 1596219820Sjeffvoid 1597219820Sjeffcl_fmap_delta(IN OUT cl_fmap_t * const p_map1, 1598219820Sjeff IN OUT cl_fmap_t * const p_map2, 1599219820Sjeff OUT cl_fmap_t * const p_new, OUT cl_fmap_t * const p_old) 1600219820Sjeff{ 1601219820Sjeff cl_fmap_item_t *p_item1, *p_item2; 1602219820Sjeff intn_t cmp; 1603219820Sjeff 1604219820Sjeff CL_ASSERT(p_map1); 1605219820Sjeff CL_ASSERT(p_map2); 1606219820Sjeff CL_ASSERT(p_new); 1607219820Sjeff CL_ASSERT(p_old); 1608219820Sjeff CL_ASSERT(cl_is_fmap_empty(p_new)); 1609219820Sjeff CL_ASSERT(cl_is_fmap_empty(p_old)); 1610219820Sjeff 1611219820Sjeff p_item1 = cl_fmap_head(p_map1); 1612219820Sjeff p_item2 = cl_fmap_head(p_map2); 1613219820Sjeff 1614219820Sjeff while (p_item1 != cl_fmap_end(p_map1) && p_item2 != cl_fmap_end(p_map2)) { 1615219820Sjeff cmp = p_map1->pfn_compare(cl_fmap_key(p_item1), 1616219820Sjeff cl_fmap_key(p_item2)); 1617219820Sjeff if (cmp < 0) { 1618219820Sjeff /* We found an old item. */ 1619219820Sjeff __cl_fmap_delta_move(p_old, p_map1, &p_item1); 1620219820Sjeff } else if (cmp > 0) { 1621219820Sjeff /* We found a new item. */ 1622219820Sjeff __cl_fmap_delta_move(p_new, p_map2, &p_item2); 1623219820Sjeff } else { 1624219820Sjeff /* Move both forward since they have the same key. */ 1625219820Sjeff p_item1 = cl_fmap_next(p_item1); 1626219820Sjeff p_item2 = cl_fmap_next(p_item2); 1627219820Sjeff } 1628219820Sjeff } 1629219820Sjeff 1630219820Sjeff /* Process the remainder if the end of either source map was reached. */ 1631219820Sjeff while (p_item2 != cl_fmap_end(p_map2)) 1632219820Sjeff __cl_fmap_delta_move(p_new, p_map2, &p_item2); 1633219820Sjeff 1634219820Sjeff while (p_item1 != cl_fmap_end(p_map1)) 1635219820Sjeff __cl_fmap_delta_move(p_old, p_map1, &p_item1); 1636219820Sjeff} 1637