1 /*
2 * Copyright (c) 2004-2006 Voltaire, Inc. All rights reserved.
3 * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved.
4 * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.
5 *
6 * This software is available to you under a choice of one of two
7 * licenses. You may choose to be licensed under the terms of the GNU
8 * General Public License (GPL) Version 2, available from the file
9 * COPYING in the main directory of this source tree, or the
10 * OpenIB.org BSD license below:
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
18 * disclaimer.
19 *
20 * - Redistributions in binary form must reproduce the above
21 * copyright notice, this list of conditions and the following
22 * disclaimer in the documentation and/or other materials
23 * provided with the distribution.
24 *
25 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
26 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
27 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
29 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
30 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
31 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
32 * SOFTWARE.
33 *
34 */
35
36 /*
37 * Abstract:
38 * Implementation of quick map, a binary tree where the caller always
39 * provides all necessary storage.
40 *
41 */
42
43 /*****************************************************************************
44 *
45 * Map
46 *
47 * Map is an associative array. By providing a key, the caller can retrieve
48 * an object from the map. All objects in the map have an associated key,
49 * as specified by the caller when the object was inserted into the map.
50 * In addition to random access, the caller can traverse the map much like
51 * a linked list, either forwards from the first object or backwards from
52 * the last object. The objects in the map are always traversed in
53 * order since the nodes are stored sorted.
54 *
55 * This implementation of Map uses a red black tree verified against
56 * Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth
57 * printing, 1994.
58 *
59 *****************************************************************************/
60
61 #if HAVE_CONFIG_H
62 # include <config.h>
63 #endif /* HAVE_CONFIG_H */
64
65 #include <string.h>
66 #include <complib/cl_qmap.h>
67 #include <complib/cl_map.h>
68 #include <complib/cl_fleximap.h>
69
70 /******************************************************************************
71 *******************************************************************************
72 ************** ************
73 ************** IMPLEMENTATION OF QUICK MAP ************
74 ************** ************
75 *******************************************************************************
76 ******************************************************************************/
77
78 /*
79 * Get the root.
80 */
__cl_map_root(IN const cl_qmap_t * const p_map)81 static inline cl_map_item_t *__cl_map_root(IN const cl_qmap_t * const p_map)
82 {
83 CL_ASSERT(p_map);
84 return (p_map->root.p_left);
85 }
86
87 /*
88 * Returns whether a given item is on the left of its parent.
89 */
__cl_map_is_left_child(IN const cl_map_item_t * const p_item)90 static boolean_t __cl_map_is_left_child(IN const cl_map_item_t * const p_item)
91 {
92 CL_ASSERT(p_item);
93 CL_ASSERT(p_item->p_up);
94 CL_ASSERT(p_item->p_up != p_item);
95
96 return (p_item->p_up->p_left == p_item);
97 }
98
99 /*
100 * Retrieve the pointer to the parent's pointer to an item.
101 */
__cl_map_get_parent_ptr_to_item(IN cl_map_item_t * const p_item)102 static cl_map_item_t **__cl_map_get_parent_ptr_to_item(IN cl_map_item_t *
103 const p_item)
104 {
105 CL_ASSERT(p_item);
106 CL_ASSERT(p_item->p_up);
107 CL_ASSERT(p_item->p_up != p_item);
108
109 if (__cl_map_is_left_child(p_item))
110 return (&p_item->p_up->p_left);
111
112 CL_ASSERT(p_item->p_up->p_right == p_item);
113 return (&p_item->p_up->p_right);
114 }
115
116 /*
117 * Rotate a node to the left. This rotation affects the least number of links
118 * between nodes and brings the level of C up by one while increasing the depth
119 * of A one. Note that the links to/from W, X, Y, and Z are not affected.
120 *
121 * R R
122 * | |
123 * A C
124 * / \ / \
125 * W C A Z
126 * / \ / \
127 * B Z W B
128 * / \ / \
129 * X Y X Y
130 */
131 static void
__cl_map_rot_left(IN cl_qmap_t * const p_map,IN cl_map_item_t * const p_item)132 __cl_map_rot_left(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item)
133 {
134 cl_map_item_t **pp_root;
135
136 CL_ASSERT(p_map);
137 CL_ASSERT(p_item);
138 CL_ASSERT(p_item->p_right != &p_map->nil);
139
140 pp_root = __cl_map_get_parent_ptr_to_item(p_item);
141
142 /* Point R to C instead of A. */
143 *pp_root = p_item->p_right;
144 /* Set C's parent to R. */
145 (*pp_root)->p_up = p_item->p_up;
146
147 /* Set A's right to B */
148 p_item->p_right = (*pp_root)->p_left;
149 /*
150 * Set B's parent to A. We trap for B being NIL since the
151 * caller may depend on NIL not changing.
152 */
153 if ((*pp_root)->p_left != &p_map->nil)
154 (*pp_root)->p_left->p_up = p_item;
155
156 /* Set C's left to A. */
157 (*pp_root)->p_left = p_item;
158 /* Set A's parent to C. */
159 p_item->p_up = *pp_root;
160 }
161
162 /*
163 * Rotate a node to the right. This rotation affects the least number of links
164 * between nodes and brings the level of A up by one while increasing the depth
165 * of C one. Note that the links to/from W, X, Y, and Z are not affected.
166 *
167 * R R
168 * | |
169 * C A
170 * / \ / \
171 * A Z W C
172 * / \ / \
173 * W B B Z
174 * / \ / \
175 * X Y X Y
176 */
177 static void
__cl_map_rot_right(IN cl_qmap_t * const p_map,IN cl_map_item_t * const p_item)178 __cl_map_rot_right(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item)
179 {
180 cl_map_item_t **pp_root;
181
182 CL_ASSERT(p_map);
183 CL_ASSERT(p_item);
184 CL_ASSERT(p_item->p_left != &p_map->nil);
185
186 /* Point R to A instead of C. */
187 pp_root = __cl_map_get_parent_ptr_to_item(p_item);
188 (*pp_root) = p_item->p_left;
189 /* Set A's parent to R. */
190 (*pp_root)->p_up = p_item->p_up;
191
192 /* Set C's left to B */
193 p_item->p_left = (*pp_root)->p_right;
194 /*
195 * Set B's parent to C. We trap for B being NIL since the
196 * caller may depend on NIL not changing.
197 */
198 if ((*pp_root)->p_right != &p_map->nil)
199 (*pp_root)->p_right->p_up = p_item;
200
201 /* Set A's right to C. */
202 (*pp_root)->p_right = p_item;
203 /* Set C's parent to A. */
204 p_item->p_up = *pp_root;
205 }
206
cl_qmap_init(IN cl_qmap_t * const p_map)207 void cl_qmap_init(IN cl_qmap_t * const p_map)
208 {
209 CL_ASSERT(p_map);
210
211 memset(p_map, 0, sizeof(cl_qmap_t));
212
213 /* special setup for the root node */
214 p_map->root.p_up = &p_map->root;
215 p_map->root.p_left = &p_map->nil;
216 p_map->root.p_right = &p_map->nil;
217 p_map->root.color = CL_MAP_BLACK;
218
219 /* Setup the node used as terminator for all leaves. */
220 p_map->nil.p_up = &p_map->nil;
221 p_map->nil.p_left = &p_map->nil;
222 p_map->nil.p_right = &p_map->nil;
223 p_map->nil.color = CL_MAP_BLACK;
224
225 p_map->state = CL_INITIALIZED;
226
227 cl_qmap_remove_all(p_map);
228 }
229
cl_qmap_get(IN const cl_qmap_t * const p_map,IN const uint64_t key)230 cl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map,
231 IN const uint64_t key)
232 {
233 cl_map_item_t *p_item;
234
235 CL_ASSERT(p_map);
236 CL_ASSERT(p_map->state == CL_INITIALIZED);
237
238 p_item = __cl_map_root(p_map);
239
240 while (p_item != &p_map->nil) {
241 if (key == p_item->key)
242 break; /* just right */
243
244 if (key < p_item->key)
245 p_item = p_item->p_left; /* too small */
246 else
247 p_item = p_item->p_right; /* too big */
248 }
249
250 return (p_item);
251 }
252
cl_qmap_get_next(IN const cl_qmap_t * const p_map,IN const uint64_t key)253 cl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map,
254 IN const uint64_t key)
255 {
256 cl_map_item_t *p_item;
257 cl_map_item_t *p_item_found;
258
259 CL_ASSERT(p_map);
260 CL_ASSERT(p_map->state == CL_INITIALIZED);
261
262 p_item = __cl_map_root(p_map);
263 p_item_found = (cl_map_item_t *) & p_map->nil;
264
265 while (p_item != &p_map->nil) {
266 if (key < p_item->key) {
267 p_item_found = p_item;
268 p_item = p_item->p_left;
269 } else {
270 p_item = p_item->p_right;
271 }
272 }
273
274 return (p_item_found);
275 }
276
277 void
cl_qmap_apply_func(IN const cl_qmap_t * const p_map,IN cl_pfn_qmap_apply_t pfn_func,IN const void * const context)278 cl_qmap_apply_func(IN const cl_qmap_t * const p_map,
279 IN cl_pfn_qmap_apply_t pfn_func,
280 IN const void *const context)
281 {
282 cl_map_item_t *p_map_item;
283
284 /* Note that context can have any arbitrary value. */
285 CL_ASSERT(p_map);
286 CL_ASSERT(p_map->state == CL_INITIALIZED);
287 CL_ASSERT(pfn_func);
288
289 p_map_item = cl_qmap_head(p_map);
290 while (p_map_item != cl_qmap_end(p_map)) {
291 pfn_func(p_map_item, (void *)context);
292 p_map_item = cl_qmap_next(p_map_item);
293 }
294 }
295
296 /*
297 * Balance a tree starting at a given item back to the root.
298 */
299 static void
__cl_map_ins_bal(IN cl_qmap_t * const p_map,IN cl_map_item_t * p_item)300 __cl_map_ins_bal(IN cl_qmap_t * const p_map, IN cl_map_item_t * p_item)
301 {
302 cl_map_item_t *p_grand_uncle;
303
304 CL_ASSERT(p_map);
305 CL_ASSERT(p_item);
306 CL_ASSERT(p_item != &p_map->root);
307
308 while (p_item->p_up->color == CL_MAP_RED) {
309 if (__cl_map_is_left_child(p_item->p_up)) {
310 p_grand_uncle = p_item->p_up->p_up->p_right;
311 CL_ASSERT(p_grand_uncle);
312 if (p_grand_uncle->color == CL_MAP_RED) {
313 p_grand_uncle->color = CL_MAP_BLACK;
314 p_item->p_up->color = CL_MAP_BLACK;
315 p_item->p_up->p_up->color = CL_MAP_RED;
316 p_item = p_item->p_up->p_up;
317 continue;
318 }
319
320 if (!__cl_map_is_left_child(p_item)) {
321 p_item = p_item->p_up;
322 __cl_map_rot_left(p_map, p_item);
323 }
324 p_item->p_up->color = CL_MAP_BLACK;
325 p_item->p_up->p_up->color = CL_MAP_RED;
326 __cl_map_rot_right(p_map, p_item->p_up->p_up);
327 } else {
328 p_grand_uncle = p_item->p_up->p_up->p_left;
329 CL_ASSERT(p_grand_uncle);
330 if (p_grand_uncle->color == CL_MAP_RED) {
331 p_grand_uncle->color = CL_MAP_BLACK;
332 p_item->p_up->color = CL_MAP_BLACK;
333 p_item->p_up->p_up->color = CL_MAP_RED;
334 p_item = p_item->p_up->p_up;
335 continue;
336 }
337
338 if (__cl_map_is_left_child(p_item)) {
339 p_item = p_item->p_up;
340 __cl_map_rot_right(p_map, p_item);
341 }
342 p_item->p_up->color = CL_MAP_BLACK;
343 p_item->p_up->p_up->color = CL_MAP_RED;
344 __cl_map_rot_left(p_map, p_item->p_up->p_up);
345 }
346 }
347 }
348
cl_qmap_insert(IN cl_qmap_t * const p_map,IN const uint64_t key,IN cl_map_item_t * const p_item)349 cl_map_item_t *cl_qmap_insert(IN cl_qmap_t * const p_map,
350 IN const uint64_t key,
351 IN cl_map_item_t * const p_item)
352 {
353 cl_map_item_t *p_insert_at, *p_comp_item;
354
355 CL_ASSERT(p_map);
356 CL_ASSERT(p_map->state == CL_INITIALIZED);
357 CL_ASSERT(p_item);
358 CL_ASSERT(p_map->root.p_up == &p_map->root);
359 CL_ASSERT(p_map->root.color != CL_MAP_RED);
360 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
361
362 p_item->p_left = &p_map->nil;
363 p_item->p_right = &p_map->nil;
364 p_item->key = key;
365 p_item->color = CL_MAP_RED;
366
367 /* Find the insertion location. */
368 p_insert_at = &p_map->root;
369 p_comp_item = __cl_map_root(p_map);
370
371 while (p_comp_item != &p_map->nil) {
372 p_insert_at = p_comp_item;
373
374 if (key == p_insert_at->key)
375 return (p_insert_at);
376
377 /* Traverse the tree until the correct insertion point is found. */
378 if (key < p_insert_at->key)
379 p_comp_item = p_insert_at->p_left;
380 else
381 p_comp_item = p_insert_at->p_right;
382 }
383
384 CL_ASSERT(p_insert_at != &p_map->nil);
385 CL_ASSERT(p_comp_item == &p_map->nil);
386 /* Insert the item. */
387 if (p_insert_at == &p_map->root) {
388 p_insert_at->p_left = p_item;
389 /*
390 * Primitive insert places the new item in front of
391 * the existing item.
392 */
393 __cl_primitive_insert(&p_map->nil.pool_item.list_item,
394 &p_item->pool_item.list_item);
395 } else if (key < p_insert_at->key) {
396 p_insert_at->p_left = p_item;
397 /*
398 * Primitive insert places the new item in front of
399 * the existing item.
400 */
401 __cl_primitive_insert(&p_insert_at->pool_item.list_item,
402 &p_item->pool_item.list_item);
403 } else {
404 p_insert_at->p_right = p_item;
405 /*
406 * Primitive insert places the new item in front of
407 * the existing item.
408 */
409 __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next,
410 &p_item->pool_item.list_item);
411 }
412 /* Increase the count. */
413 p_map->count++;
414
415 p_item->p_up = p_insert_at;
416
417 /*
418 * We have added depth to this section of the tree.
419 * Rebalance as necessary as we retrace our path through the tree
420 * and update colors.
421 */
422 __cl_map_ins_bal(p_map, p_item);
423
424 __cl_map_root(p_map)->color = CL_MAP_BLACK;
425
426 /*
427 * Note that it is not necessary to re-color the nil node black because all
428 * red color assignments are made via the p_up pointer, and nil is never
429 * set as the value of a p_up pointer.
430 */
431
432 #ifdef _DEBUG_
433 /* Set the pointer to the map in the map item for consistency checking. */
434 p_item->p_map = p_map;
435 #endif
436
437 return (p_item);
438 }
439
440 static void
__cl_map_del_bal(IN cl_qmap_t * const p_map,IN cl_map_item_t * p_item)441 __cl_map_del_bal(IN cl_qmap_t * const p_map, IN cl_map_item_t * p_item)
442 {
443 cl_map_item_t *p_uncle;
444
445 while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) {
446 if (__cl_map_is_left_child(p_item)) {
447 p_uncle = p_item->p_up->p_right;
448
449 if (p_uncle->color == CL_MAP_RED) {
450 p_uncle->color = CL_MAP_BLACK;
451 p_item->p_up->color = CL_MAP_RED;
452 __cl_map_rot_left(p_map, p_item->p_up);
453 p_uncle = p_item->p_up->p_right;
454 }
455
456 if (p_uncle->p_right->color != CL_MAP_RED) {
457 if (p_uncle->p_left->color != CL_MAP_RED) {
458 p_uncle->color = CL_MAP_RED;
459 p_item = p_item->p_up;
460 continue;
461 }
462
463 p_uncle->p_left->color = CL_MAP_BLACK;
464 p_uncle->color = CL_MAP_RED;
465 __cl_map_rot_right(p_map, p_uncle);
466 p_uncle = p_item->p_up->p_right;
467 }
468 p_uncle->color = p_item->p_up->color;
469 p_item->p_up->color = CL_MAP_BLACK;
470 p_uncle->p_right->color = CL_MAP_BLACK;
471 __cl_map_rot_left(p_map, p_item->p_up);
472 break;
473 } else {
474 p_uncle = p_item->p_up->p_left;
475
476 if (p_uncle->color == CL_MAP_RED) {
477 p_uncle->color = CL_MAP_BLACK;
478 p_item->p_up->color = CL_MAP_RED;
479 __cl_map_rot_right(p_map, p_item->p_up);
480 p_uncle = p_item->p_up->p_left;
481 }
482
483 if (p_uncle->p_left->color != CL_MAP_RED) {
484 if (p_uncle->p_right->color != CL_MAP_RED) {
485 p_uncle->color = CL_MAP_RED;
486 p_item = p_item->p_up;
487 continue;
488 }
489
490 p_uncle->p_right->color = CL_MAP_BLACK;
491 p_uncle->color = CL_MAP_RED;
492 __cl_map_rot_left(p_map, p_uncle);
493 p_uncle = p_item->p_up->p_left;
494 }
495 p_uncle->color = p_item->p_up->color;
496 p_item->p_up->color = CL_MAP_BLACK;
497 p_uncle->p_left->color = CL_MAP_BLACK;
498 __cl_map_rot_right(p_map, p_item->p_up);
499 break;
500 }
501 }
502 p_item->color = CL_MAP_BLACK;
503 }
504
505 void
cl_qmap_remove_item(IN cl_qmap_t * const p_map,IN cl_map_item_t * const p_item)506 cl_qmap_remove_item(IN cl_qmap_t * const p_map, IN cl_map_item_t * const p_item)
507 {
508 cl_map_item_t *p_child, *p_del_item;
509
510 CL_ASSERT(p_map);
511 CL_ASSERT(p_map->state == CL_INITIALIZED);
512 CL_ASSERT(p_item);
513
514 if (p_item == cl_qmap_end(p_map))
515 return;
516
517 /* must be checked after comparing to cl_qmap_end, since
518 the end is not a valid item. */
519 CL_ASSERT(p_item->p_map == p_map);
520
521 if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) {
522 /* The item being removed has children on at most on side. */
523 p_del_item = p_item;
524 } else {
525 /*
526 * The item being removed has children on both side.
527 * We select the item that will replace it. After removing
528 * the substitute item and rebalancing, the tree will have the
529 * correct topology. Exchanging the substitute for the item
530 * will finalize the removal.
531 */
532 p_del_item = cl_qmap_next(p_item);
533 CL_ASSERT(p_del_item != &p_map->nil);
534 }
535
536 /* Remove the item from the list. */
537 __cl_primitive_remove(&p_item->pool_item.list_item);
538 /* Decrement the item count. */
539 p_map->count--;
540
541 /* Get the pointer to the new root's child, if any. */
542 if (p_del_item->p_left != &p_map->nil)
543 p_child = p_del_item->p_left;
544 else
545 p_child = p_del_item->p_right;
546
547 /*
548 * This assignment may modify the parent pointer of the nil node.
549 * This is inconsequential.
550 */
551 p_child->p_up = p_del_item->p_up;
552 (*__cl_map_get_parent_ptr_to_item(p_del_item)) = p_child;
553
554 if (p_del_item->color != CL_MAP_RED)
555 __cl_map_del_bal(p_map, p_child);
556
557 /*
558 * Note that the splicing done below does not need to occur before
559 * the tree is balanced, since the actual topology changes are made by the
560 * preceding code. The topology is preserved by the color assignment made
561 * below (reader should be reminded that p_del_item == p_item in some cases).
562 */
563 if (p_del_item != p_item) {
564 /*
565 * Finalize the removal of the specified item by exchanging it with
566 * the substitute which we removed above.
567 */
568 p_del_item->p_up = p_item->p_up;
569 p_del_item->p_left = p_item->p_left;
570 p_del_item->p_right = p_item->p_right;
571 (*__cl_map_get_parent_ptr_to_item(p_item)) = p_del_item;
572 p_item->p_right->p_up = p_del_item;
573 p_item->p_left->p_up = p_del_item;
574 p_del_item->color = p_item->color;
575 }
576
577 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
578
579 #ifdef _DEBUG_
580 /* Clear the pointer to the map since the item has been removed. */
581 p_item->p_map = NULL;
582 #endif
583 }
584
cl_qmap_remove(IN cl_qmap_t * const p_map,IN const uint64_t key)585 cl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, IN const uint64_t key)
586 {
587 cl_map_item_t *p_item;
588
589 CL_ASSERT(p_map);
590 CL_ASSERT(p_map->state == CL_INITIALIZED);
591
592 /* Seek the node with the specified key */
593 p_item = cl_qmap_get(p_map, key);
594
595 cl_qmap_remove_item(p_map, p_item);
596
597 return (p_item);
598 }
599
600 void
cl_qmap_merge(OUT cl_qmap_t * const p_dest_map,IN OUT cl_qmap_t * const p_src_map)601 cl_qmap_merge(OUT cl_qmap_t * const p_dest_map,
602 IN OUT cl_qmap_t * const p_src_map)
603 {
604 cl_map_item_t *p_item, *p_item2, *p_next;
605
606 CL_ASSERT(p_dest_map);
607 CL_ASSERT(p_src_map);
608
609 p_item = cl_qmap_head(p_src_map);
610
611 while (p_item != cl_qmap_end(p_src_map)) {
612 p_next = cl_qmap_next(p_item);
613
614 /* Remove the item from its current map. */
615 cl_qmap_remove_item(p_src_map, p_item);
616 /* Insert the item into the destination map. */
617 p_item2 =
618 cl_qmap_insert(p_dest_map, cl_qmap_key(p_item), p_item);
619 /* Check that the item was successfully inserted. */
620 if (p_item2 != p_item) {
621 /* Put the item in back in the source map. */
622 p_item2 =
623 cl_qmap_insert(p_src_map, cl_qmap_key(p_item),
624 p_item);
625 CL_ASSERT(p_item2 == p_item);
626 }
627 p_item = p_next;
628 }
629 }
630
631 static void
__cl_qmap_delta_move(IN OUT cl_qmap_t * const p_dest,IN OUT cl_qmap_t * const p_src,IN OUT cl_map_item_t ** const pp_item)632 __cl_qmap_delta_move(IN OUT cl_qmap_t * const p_dest,
633 IN OUT cl_qmap_t * const p_src,
634 IN OUT cl_map_item_t ** const pp_item)
635 {
636 cl_map_item_t *p_temp, *p_next;
637
638 /*
639 * Get the next item so that we can ensure that pp_item points to
640 * a valid item upon return from the function.
641 */
642 p_next = cl_qmap_next(*pp_item);
643 /* Move the old item from its current map the the old map. */
644 cl_qmap_remove_item(p_src, *pp_item);
645 p_temp = cl_qmap_insert(p_dest, cl_qmap_key(*pp_item), *pp_item);
646 /* We should never have duplicates. */
647 CL_ASSERT(p_temp == *pp_item);
648 /* Point pp_item to a valid item in the source map. */
649 (*pp_item) = p_next;
650 }
651
652 void
cl_qmap_delta(IN OUT cl_qmap_t * const p_map1,IN OUT cl_qmap_t * const p_map2,OUT cl_qmap_t * const p_new,OUT cl_qmap_t * const p_old)653 cl_qmap_delta(IN OUT cl_qmap_t * const p_map1,
654 IN OUT cl_qmap_t * const p_map2,
655 OUT cl_qmap_t * const p_new, OUT cl_qmap_t * const p_old)
656 {
657 cl_map_item_t *p_item1, *p_item2;
658 uint64_t key1, key2;
659
660 CL_ASSERT(p_map1);
661 CL_ASSERT(p_map2);
662 CL_ASSERT(p_new);
663 CL_ASSERT(p_old);
664 CL_ASSERT(cl_is_qmap_empty(p_new));
665 CL_ASSERT(cl_is_qmap_empty(p_old));
666
667 p_item1 = cl_qmap_head(p_map1);
668 p_item2 = cl_qmap_head(p_map2);
669
670 while (p_item1 != cl_qmap_end(p_map1) && p_item2 != cl_qmap_end(p_map2)) {
671 key1 = cl_qmap_key(p_item1);
672 key2 = cl_qmap_key(p_item2);
673 if (key1 < key2) {
674 /* We found an old item. */
675 __cl_qmap_delta_move(p_old, p_map1, &p_item1);
676 } else if (key1 > key2) {
677 /* We found a new item. */
678 __cl_qmap_delta_move(p_new, p_map2, &p_item2);
679 } else {
680 /* Move both forward since they have the same key. */
681 p_item1 = cl_qmap_next(p_item1);
682 p_item2 = cl_qmap_next(p_item2);
683 }
684 }
685
686 /* Process the remainder if the end of either source map was reached. */
687 while (p_item2 != cl_qmap_end(p_map2))
688 __cl_qmap_delta_move(p_new, p_map2, &p_item2);
689
690 while (p_item1 != cl_qmap_end(p_map1))
691 __cl_qmap_delta_move(p_old, p_map1, &p_item1);
692 }
693
694 /******************************************************************************
695 *******************************************************************************
696 ************** ************
697 ************** IMPLEMENTATION OF MAP ************
698 ************** ************
699 *******************************************************************************
700 ******************************************************************************/
701
702 #define MAP_GROW_SIZE 32
703
cl_map_construct(IN cl_map_t * const p_map)704 void cl_map_construct(IN cl_map_t * const p_map)
705 {
706 CL_ASSERT(p_map);
707
708 cl_qpool_construct(&p_map->pool);
709 }
710
cl_map_init(IN cl_map_t * const p_map,IN const uint32_t min_items)711 cl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items)
712 {
713 uint32_t grow_size;
714
715 CL_ASSERT(p_map);
716
717 cl_qmap_init(&p_map->qmap);
718
719 /*
720 * We will grow by min_items/8 items at a time, with a minimum of
721 * MAP_GROW_SIZE.
722 */
723 grow_size = min_items >> 3;
724 if (grow_size < MAP_GROW_SIZE)
725 grow_size = MAP_GROW_SIZE;
726
727 return (cl_qpool_init(&p_map->pool, min_items, 0, grow_size,
728 sizeof(cl_map_obj_t), NULL, NULL, NULL));
729 }
730
cl_map_destroy(IN cl_map_t * const p_map)731 void cl_map_destroy(IN cl_map_t * const p_map)
732 {
733 CL_ASSERT(p_map);
734
735 cl_qpool_destroy(&p_map->pool);
736 }
737
cl_map_insert(IN cl_map_t * const p_map,IN const uint64_t key,IN const void * const p_object)738 void *cl_map_insert(IN cl_map_t * const p_map,
739 IN const uint64_t key, IN const void *const p_object)
740 {
741 cl_map_obj_t *p_map_obj, *p_obj_at_key;
742
743 CL_ASSERT(p_map);
744
745 p_map_obj = (cl_map_obj_t *) cl_qpool_get(&p_map->pool);
746
747 if (!p_map_obj)
748 return (NULL);
749
750 cl_qmap_set_obj(p_map_obj, p_object);
751
752 p_obj_at_key =
753 (cl_map_obj_t *) cl_qmap_insert(&p_map->qmap, key,
754 &p_map_obj->item);
755
756 /* Return the item to the pool if insertion failed. */
757 if (p_obj_at_key != p_map_obj)
758 cl_qpool_put(&p_map->pool, &p_map_obj->item.pool_item);
759
760 return (cl_qmap_obj(p_obj_at_key));
761 }
762
cl_map_get(IN const cl_map_t * const p_map,IN const uint64_t key)763 void *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key)
764 {
765 cl_map_item_t *p_item;
766
767 CL_ASSERT(p_map);
768
769 p_item = cl_qmap_get(&p_map->qmap, key);
770
771 if (p_item == cl_qmap_end(&p_map->qmap))
772 return (NULL);
773
774 return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item)));
775 }
776
cl_map_get_next(IN const cl_map_t * const p_map,IN const uint64_t key)777 void *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key)
778 {
779 cl_map_item_t *p_item;
780
781 CL_ASSERT(p_map);
782
783 p_item = cl_qmap_get_next(&p_map->qmap, key);
784
785 if (p_item == cl_qmap_end(&p_map->qmap))
786 return (NULL);
787
788 return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item)));
789 }
790
791 void
cl_map_remove_item(IN cl_map_t * const p_map,IN const cl_map_iterator_t itor)792 cl_map_remove_item(IN cl_map_t * const p_map, IN const cl_map_iterator_t itor)
793 {
794 CL_ASSERT(itor->p_map == &p_map->qmap);
795
796 if (itor == cl_map_end(p_map))
797 return;
798
799 cl_qmap_remove_item(&p_map->qmap, (cl_map_item_t *) itor);
800 cl_qpool_put(&p_map->pool, &((cl_map_item_t *) itor)->pool_item);
801 }
802
cl_map_remove(IN cl_map_t * const p_map,IN const uint64_t key)803 void *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key)
804 {
805 cl_map_item_t *p_item;
806 void *p_obj;
807
808 CL_ASSERT(p_map);
809
810 p_item = cl_qmap_remove(&p_map->qmap, key);
811
812 if (p_item == cl_qmap_end(&p_map->qmap))
813 return (NULL);
814
815 p_obj = cl_qmap_obj((cl_map_obj_t *) p_item);
816 cl_qpool_put(&p_map->pool, &p_item->pool_item);
817
818 return (p_obj);
819 }
820
cl_map_remove_all(IN cl_map_t * const p_map)821 void cl_map_remove_all(IN cl_map_t * const p_map)
822 {
823 cl_map_item_t *p_item;
824
825 CL_ASSERT(p_map);
826
827 /* Return all map items to the pool. */
828 while (!cl_is_qmap_empty(&p_map->qmap)) {
829 p_item = cl_qmap_head(&p_map->qmap);
830 cl_qmap_remove_item(&p_map->qmap, p_item);
831 cl_qpool_put(&p_map->pool, &p_item->pool_item);
832
833 if (!cl_is_qmap_empty(&p_map->qmap)) {
834 p_item = cl_qmap_tail(&p_map->qmap);
835 cl_qmap_remove_item(&p_map->qmap, p_item);
836 cl_qpool_put(&p_map->pool, &p_item->pool_item);
837 }
838 }
839 }
840
841 cl_status_t
cl_map_merge(OUT cl_map_t * const p_dest_map,IN OUT cl_map_t * const p_src_map)842 cl_map_merge(OUT cl_map_t * const p_dest_map, IN OUT cl_map_t * const p_src_map)
843 {
844 cl_status_t status = CL_SUCCESS;
845 cl_map_iterator_t itor, next;
846 uint64_t key;
847 void *p_obj, *p_obj2;
848
849 CL_ASSERT(p_dest_map);
850 CL_ASSERT(p_src_map);
851
852 itor = cl_map_head(p_src_map);
853 while (itor != cl_map_end(p_src_map)) {
854 next = cl_map_next(itor);
855
856 p_obj = cl_map_obj(itor);
857 key = cl_map_key(itor);
858
859 cl_map_remove_item(p_src_map, itor);
860
861 /* Insert the object into the destination map. */
862 p_obj2 = cl_map_insert(p_dest_map, key, p_obj);
863 /* Trap for failure. */
864 if (p_obj != p_obj2) {
865 if (!p_obj2)
866 status = CL_INSUFFICIENT_MEMORY;
867 /* Put the object back in the source map. This must succeed. */
868 p_obj2 = cl_map_insert(p_src_map, key, p_obj);
869 CL_ASSERT(p_obj == p_obj2);
870 /* If the failure was due to insufficient memory, return. */
871 if (status != CL_SUCCESS)
872 return (status);
873 }
874 itor = next;
875 }
876
877 return (CL_SUCCESS);
878 }
879
880 static void
__cl_map_revert(IN OUT cl_map_t * const p_map1,IN OUT cl_map_t * const p_map2,IN OUT cl_map_t * const p_new,IN OUT cl_map_t * const p_old)881 __cl_map_revert(IN OUT cl_map_t * const p_map1,
882 IN OUT cl_map_t * const p_map2,
883 IN OUT cl_map_t * const p_new, IN OUT cl_map_t * const p_old)
884 {
885 cl_status_t status;
886
887 /* Restore the initial state. */
888 status = cl_map_merge(p_map1, p_old);
889 CL_ASSERT(status == CL_SUCCESS);
890 status = cl_map_merge(p_map2, p_new);
891 CL_ASSERT(status == CL_SUCCESS);
892 }
893
894 static cl_status_t
__cl_map_delta_move(OUT cl_map_t * const p_dest,IN OUT cl_map_t * const p_src,IN OUT cl_map_iterator_t * const p_itor)895 __cl_map_delta_move(OUT cl_map_t * const p_dest,
896 IN OUT cl_map_t * const p_src,
897 IN OUT cl_map_iterator_t * const p_itor)
898 {
899 cl_map_iterator_t next;
900 void *p_obj, *p_obj2;
901 uint64_t key;
902
903 /* Get a valid iterator so we can continue the loop. */
904 next = cl_map_next(*p_itor);
905 /* Get the pointer to the object for insertion. */
906 p_obj = cl_map_obj(*p_itor);
907 /* Get the key for the object. */
908 key = cl_map_key(*p_itor);
909 /* Move the object. */
910 cl_map_remove_item(p_src, *p_itor);
911 p_obj2 = cl_map_insert(p_dest, key, p_obj);
912 /* Check for failure. We should never get a duplicate. */
913 if (!p_obj2) {
914 p_obj2 = cl_map_insert(p_src, key, p_obj);
915 CL_ASSERT(p_obj2 == p_obj);
916 return (CL_INSUFFICIENT_MEMORY);
917 }
918
919 /* We should never get a duplicate */
920 CL_ASSERT(p_obj == p_obj2);
921 /* Update the iterator so that it is valid. */
922 (*p_itor) = next;
923
924 return (CL_SUCCESS);
925 }
926
927 cl_status_t
cl_map_delta(IN OUT cl_map_t * const p_map1,IN OUT cl_map_t * const p_map2,OUT cl_map_t * const p_new,OUT cl_map_t * const p_old)928 cl_map_delta(IN OUT cl_map_t * const p_map1,
929 IN OUT cl_map_t * const p_map2,
930 OUT cl_map_t * const p_new, OUT cl_map_t * const p_old)
931 {
932 cl_map_iterator_t itor1, itor2;
933 uint64_t key1, key2;
934 cl_status_t status;
935
936 CL_ASSERT(p_map1);
937 CL_ASSERT(p_map2);
938 CL_ASSERT(p_new);
939 CL_ASSERT(p_old);
940 CL_ASSERT(cl_is_map_empty(p_new));
941 CL_ASSERT(cl_is_map_empty(p_old));
942
943 itor1 = cl_map_head(p_map1);
944 itor2 = cl_map_head(p_map2);
945
946 /*
947 * Note that the check is for the end, since duplicate items will remain
948 * in their respective maps.
949 */
950 while (itor1 != cl_map_end(p_map1) && itor2 != cl_map_end(p_map2)) {
951 key1 = cl_map_key(itor1);
952 key2 = cl_map_key(itor2);
953 if (key1 < key2) {
954 status = __cl_map_delta_move(p_old, p_map1, &itor1);
955 /* Check for failure. */
956 if (status != CL_SUCCESS) {
957 /* Restore the initial state. */
958 __cl_map_revert(p_map1, p_map2, p_new, p_old);
959 /* Return the failure status. */
960 return (status);
961 }
962 } else if (key1 > key2) {
963 status = __cl_map_delta_move(p_new, p_map2, &itor2);
964 if (status != CL_SUCCESS) {
965 /* Restore the initial state. */
966 __cl_map_revert(p_map1, p_map2, p_new, p_old);
967 /* Return the failure status. */
968 return (status);
969 }
970 } else {
971 /* Move both forward since they have the same key. */
972 itor1 = cl_map_next(itor1);
973 itor2 = cl_map_next(itor2);
974 }
975 }
976
977 /* Process the remainder if either source map is empty. */
978 while (itor2 != cl_map_end(p_map2)) {
979 status = __cl_map_delta_move(p_new, p_map2, &itor2);
980 if (status != CL_SUCCESS) {
981 /* Restore the initial state. */
982 __cl_map_revert(p_map1, p_map2, p_new, p_old);
983 /* Return the failure status. */
984 return (status);
985 }
986 }
987
988 while (itor1 != cl_map_end(p_map1)) {
989 status = __cl_map_delta_move(p_old, p_map1, &itor1);
990 if (status != CL_SUCCESS) {
991 /* Restore the initial state. */
992 __cl_map_revert(p_map1, p_map2, p_new, p_old);
993 /* Return the failure status. */
994 return (status);
995 }
996 }
997
998 return (CL_SUCCESS);
999 }
1000
1001 /******************************************************************************
1002 *******************************************************************************
1003 ************** ************
1004 ************** IMPLEMENTATION OF FLEXI MAP ************
1005 ************** ************
1006 *******************************************************************************
1007 ******************************************************************************/
1008
1009 /*
1010 * Get the root.
1011 */
__cl_fmap_root(IN const cl_fmap_t * const p_map)1012 static inline cl_fmap_item_t *__cl_fmap_root(IN const cl_fmap_t * const p_map)
1013 {
1014 CL_ASSERT(p_map);
1015 return (p_map->root.p_left);
1016 }
1017
1018 /*
1019 * Returns whether a given item is on the left of its parent.
1020 */
__cl_fmap_is_left_child(IN const cl_fmap_item_t * const p_item)1021 static boolean_t __cl_fmap_is_left_child(IN const cl_fmap_item_t * const p_item)
1022 {
1023 CL_ASSERT(p_item);
1024 CL_ASSERT(p_item->p_up);
1025 CL_ASSERT(p_item->p_up != p_item);
1026
1027 return (p_item->p_up->p_left == p_item);
1028 }
1029
1030 /*
1031 * Retrieve the pointer to the parent's pointer to an item.
1032 */
__cl_fmap_get_parent_ptr_to_item(IN cl_fmap_item_t * const p_item)1033 static cl_fmap_item_t **__cl_fmap_get_parent_ptr_to_item(IN cl_fmap_item_t *
1034 const p_item)
1035 {
1036 CL_ASSERT(p_item);
1037 CL_ASSERT(p_item->p_up);
1038 CL_ASSERT(p_item->p_up != p_item);
1039
1040 if (__cl_fmap_is_left_child(p_item))
1041 return (&p_item->p_up->p_left);
1042
1043 CL_ASSERT(p_item->p_up->p_right == p_item);
1044 return (&p_item->p_up->p_right);
1045 }
1046
1047 /*
1048 * Rotate a node to the left. This rotation affects the least number of links
1049 * between nodes and brings the level of C up by one while increasing the depth
1050 * of A one. Note that the links to/from W, X, Y, and Z are not affected.
1051 *
1052 * R R
1053 * | |
1054 * A C
1055 * / \ / \
1056 * W C A Z
1057 * / \ / \
1058 * B Z W B
1059 * / \ / \
1060 * X Y X Y
1061 */
1062 static void
__cl_fmap_rot_left(IN cl_fmap_t * const p_map,IN cl_fmap_item_t * const p_item)1063 __cl_fmap_rot_left(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * const p_item)
1064 {
1065 cl_fmap_item_t **pp_root;
1066
1067 CL_ASSERT(p_map);
1068 CL_ASSERT(p_item);
1069 CL_ASSERT(p_item->p_right != &p_map->nil);
1070
1071 pp_root = __cl_fmap_get_parent_ptr_to_item(p_item);
1072
1073 /* Point R to C instead of A. */
1074 *pp_root = p_item->p_right;
1075 /* Set C's parent to R. */
1076 (*pp_root)->p_up = p_item->p_up;
1077
1078 /* Set A's right to B */
1079 p_item->p_right = (*pp_root)->p_left;
1080 /*
1081 * Set B's parent to A. We trap for B being NIL since the
1082 * caller may depend on NIL not changing.
1083 */
1084 if ((*pp_root)->p_left != &p_map->nil)
1085 (*pp_root)->p_left->p_up = p_item;
1086
1087 /* Set C's left to A. */
1088 (*pp_root)->p_left = p_item;
1089 /* Set A's parent to C. */
1090 p_item->p_up = *pp_root;
1091 }
1092
1093 /*
1094 * Rotate a node to the right. This rotation affects the least number of links
1095 * between nodes and brings the level of A up by one while increasing the depth
1096 * of C one. Note that the links to/from W, X, Y, and Z are not affected.
1097 *
1098 * R R
1099 * | |
1100 * C A
1101 * / \ / \
1102 * A Z W C
1103 * / \ / \
1104 * W B B Z
1105 * / \ / \
1106 * X Y X Y
1107 */
1108 static void
__cl_fmap_rot_right(IN cl_fmap_t * const p_map,IN cl_fmap_item_t * const p_item)1109 __cl_fmap_rot_right(IN cl_fmap_t * const p_map,
1110 IN cl_fmap_item_t * const p_item)
1111 {
1112 cl_fmap_item_t **pp_root;
1113
1114 CL_ASSERT(p_map);
1115 CL_ASSERT(p_item);
1116 CL_ASSERT(p_item->p_left != &p_map->nil);
1117
1118 /* Point R to A instead of C. */
1119 pp_root = __cl_fmap_get_parent_ptr_to_item(p_item);
1120 (*pp_root) = p_item->p_left;
1121 /* Set A's parent to R. */
1122 (*pp_root)->p_up = p_item->p_up;
1123
1124 /* Set C's left to B */
1125 p_item->p_left = (*pp_root)->p_right;
1126 /*
1127 * Set B's parent to C. We trap for B being NIL since the
1128 * caller may depend on NIL not changing.
1129 */
1130 if ((*pp_root)->p_right != &p_map->nil)
1131 (*pp_root)->p_right->p_up = p_item;
1132
1133 /* Set A's right to C. */
1134 (*pp_root)->p_right = p_item;
1135 /* Set C's parent to A. */
1136 p_item->p_up = *pp_root;
1137 }
1138
cl_fmap_init(IN cl_fmap_t * const p_map,IN cl_pfn_fmap_cmp_t pfn_compare)1139 void cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare)
1140 {
1141 CL_ASSERT(p_map);
1142 CL_ASSERT(pfn_compare);
1143
1144 memset(p_map, 0, sizeof(cl_fmap_t));
1145
1146 /* special setup for the root node */
1147 p_map->root.p_up = &p_map->root;
1148 p_map->root.p_left = &p_map->nil;
1149 p_map->root.p_right = &p_map->nil;
1150 p_map->root.color = CL_MAP_BLACK;
1151
1152 /* Setup the node used as terminator for all leaves. */
1153 p_map->nil.p_up = &p_map->nil;
1154 p_map->nil.p_left = &p_map->nil;
1155 p_map->nil.p_right = &p_map->nil;
1156 p_map->nil.color = CL_MAP_BLACK;
1157
1158 /* Store the compare function pointer. */
1159 p_map->pfn_compare = pfn_compare;
1160
1161 p_map->state = CL_INITIALIZED;
1162
1163 cl_fmap_remove_all(p_map);
1164 }
1165
cl_fmap_get(IN const cl_fmap_t * const p_map,IN const void * const p_key)1166 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map,
1167 IN const void *const p_key)
1168 {
1169 cl_fmap_item_t *p_item;
1170 intn_t cmp;
1171
1172 CL_ASSERT(p_map);
1173 CL_ASSERT(p_map->state == CL_INITIALIZED);
1174
1175 p_item = __cl_fmap_root(p_map);
1176
1177 while (p_item != &p_map->nil) {
1178 cmp = p_map->pfn_compare(p_key, p_item->p_key);
1179
1180 if (!cmp)
1181 break; /* just right */
1182
1183 if (cmp < 0)
1184 p_item = p_item->p_left; /* too small */
1185 else
1186 p_item = p_item->p_right; /* too big */
1187 }
1188
1189 return (p_item);
1190 }
1191
cl_fmap_get_next(IN const cl_fmap_t * const p_map,IN const void * const p_key)1192 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map,
1193 IN const void *const p_key)
1194 {
1195 cl_fmap_item_t *p_item;
1196 cl_fmap_item_t *p_item_found;
1197 intn_t cmp;
1198
1199 CL_ASSERT(p_map);
1200 CL_ASSERT(p_map->state == CL_INITIALIZED);
1201
1202 p_item = __cl_fmap_root(p_map);
1203 p_item_found = (cl_fmap_item_t *) & p_map->nil;
1204
1205 while (p_item != &p_map->nil) {
1206 cmp = p_map->pfn_compare(p_key, p_item->p_key);
1207
1208 if (cmp < 0) {
1209 p_item_found = p_item;
1210 p_item = p_item->p_left; /* too small */
1211 } else {
1212 p_item = p_item->p_right; /* too big or match */
1213 }
1214 }
1215
1216 return (p_item_found);
1217 }
1218
1219 void
cl_fmap_apply_func(IN const cl_fmap_t * const p_map,IN cl_pfn_fmap_apply_t pfn_func,IN const void * const context)1220 cl_fmap_apply_func(IN const cl_fmap_t * const p_map,
1221 IN cl_pfn_fmap_apply_t pfn_func,
1222 IN const void *const context)
1223 {
1224 cl_fmap_item_t *p_fmap_item;
1225
1226 /* Note that context can have any arbitrary value. */
1227 CL_ASSERT(p_map);
1228 CL_ASSERT(p_map->state == CL_INITIALIZED);
1229 CL_ASSERT(pfn_func);
1230
1231 p_fmap_item = cl_fmap_head(p_map);
1232 while (p_fmap_item != cl_fmap_end(p_map)) {
1233 pfn_func(p_fmap_item, (void *)context);
1234 p_fmap_item = cl_fmap_next(p_fmap_item);
1235 }
1236 }
1237
1238 /*
1239 * Balance a tree starting at a given item back to the root.
1240 */
1241 static void
__cl_fmap_ins_bal(IN cl_fmap_t * const p_map,IN cl_fmap_item_t * p_item)1242 __cl_fmap_ins_bal(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * p_item)
1243 {
1244 cl_fmap_item_t *p_grand_uncle;
1245
1246 CL_ASSERT(p_map);
1247 CL_ASSERT(p_item);
1248 CL_ASSERT(p_item != &p_map->root);
1249
1250 while (p_item->p_up->color == CL_MAP_RED) {
1251 if (__cl_fmap_is_left_child(p_item->p_up)) {
1252 p_grand_uncle = p_item->p_up->p_up->p_right;
1253 CL_ASSERT(p_grand_uncle);
1254 if (p_grand_uncle->color == CL_MAP_RED) {
1255 p_grand_uncle->color = CL_MAP_BLACK;
1256 p_item->p_up->color = CL_MAP_BLACK;
1257 p_item->p_up->p_up->color = CL_MAP_RED;
1258 p_item = p_item->p_up->p_up;
1259 continue;
1260 }
1261
1262 if (!__cl_fmap_is_left_child(p_item)) {
1263 p_item = p_item->p_up;
1264 __cl_fmap_rot_left(p_map, p_item);
1265 }
1266 p_item->p_up->color = CL_MAP_BLACK;
1267 p_item->p_up->p_up->color = CL_MAP_RED;
1268 __cl_fmap_rot_right(p_map, p_item->p_up->p_up);
1269 } else {
1270 p_grand_uncle = p_item->p_up->p_up->p_left;
1271 CL_ASSERT(p_grand_uncle);
1272 if (p_grand_uncle->color == CL_MAP_RED) {
1273 p_grand_uncle->color = CL_MAP_BLACK;
1274 p_item->p_up->color = CL_MAP_BLACK;
1275 p_item->p_up->p_up->color = CL_MAP_RED;
1276 p_item = p_item->p_up->p_up;
1277 continue;
1278 }
1279
1280 if (__cl_fmap_is_left_child(p_item)) {
1281 p_item = p_item->p_up;
1282 __cl_fmap_rot_right(p_map, p_item);
1283 }
1284 p_item->p_up->color = CL_MAP_BLACK;
1285 p_item->p_up->p_up->color = CL_MAP_RED;
1286 __cl_fmap_rot_left(p_map, p_item->p_up->p_up);
1287 }
1288 }
1289 }
1290
cl_fmap_insert(IN cl_fmap_t * const p_map,IN const void * const p_key,IN cl_fmap_item_t * const p_item)1291 cl_fmap_item_t *cl_fmap_insert(IN cl_fmap_t * const p_map,
1292 IN const void *const p_key,
1293 IN cl_fmap_item_t * const p_item)
1294 {
1295 cl_fmap_item_t *p_insert_at, *p_comp_item;
1296 intn_t cmp = 0;
1297
1298 CL_ASSERT(p_map);
1299 CL_ASSERT(p_map->state == CL_INITIALIZED);
1300 CL_ASSERT(p_item);
1301 CL_ASSERT(p_map->root.p_up == &p_map->root);
1302 CL_ASSERT(p_map->root.color != CL_MAP_RED);
1303 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
1304
1305 p_item->p_left = &p_map->nil;
1306 p_item->p_right = &p_map->nil;
1307 p_item->p_key = p_key;
1308 p_item->color = CL_MAP_RED;
1309
1310 /* Find the insertion location. */
1311 p_insert_at = &p_map->root;
1312 p_comp_item = __cl_fmap_root(p_map);
1313
1314 while (p_comp_item != &p_map->nil) {
1315 p_insert_at = p_comp_item;
1316
1317 cmp = p_map->pfn_compare(p_key, p_insert_at->p_key);
1318
1319 if (!cmp)
1320 return (p_insert_at);
1321
1322 /* Traverse the tree until the correct insertion point is found. */
1323 if (cmp < 0)
1324 p_comp_item = p_insert_at->p_left;
1325 else
1326 p_comp_item = p_insert_at->p_right;
1327 }
1328
1329 CL_ASSERT(p_insert_at != &p_map->nil);
1330 CL_ASSERT(p_comp_item == &p_map->nil);
1331 /* Insert the item. */
1332 if (p_insert_at == &p_map->root) {
1333 p_insert_at->p_left = p_item;
1334 /*
1335 * Primitive insert places the new item in front of
1336 * the existing item.
1337 */
1338 __cl_primitive_insert(&p_map->nil.pool_item.list_item,
1339 &p_item->pool_item.list_item);
1340 } else if (cmp < 0) {
1341 p_insert_at->p_left = p_item;
1342 /*
1343 * Primitive insert places the new item in front of
1344 * the existing item.
1345 */
1346 __cl_primitive_insert(&p_insert_at->pool_item.list_item,
1347 &p_item->pool_item.list_item);
1348 } else {
1349 p_insert_at->p_right = p_item;
1350 /*
1351 * Primitive insert places the new item in front of
1352 * the existing item.
1353 */
1354 __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next,
1355 &p_item->pool_item.list_item);
1356 }
1357 /* Increase the count. */
1358 p_map->count++;
1359
1360 p_item->p_up = p_insert_at;
1361
1362 /*
1363 * We have added depth to this section of the tree.
1364 * Rebalance as necessary as we retrace our path through the tree
1365 * and update colors.
1366 */
1367 __cl_fmap_ins_bal(p_map, p_item);
1368
1369 __cl_fmap_root(p_map)->color = CL_MAP_BLACK;
1370
1371 /*
1372 * Note that it is not necessary to re-color the nil node black because all
1373 * red color assignments are made via the p_up pointer, and nil is never
1374 * set as the value of a p_up pointer.
1375 */
1376
1377 #ifdef _DEBUG_
1378 /* Set the pointer to the map in the map item for consistency checking. */
1379 p_item->p_map = p_map;
1380 #endif
1381
1382 return (p_item);
1383 }
1384
1385 static void
__cl_fmap_del_bal(IN cl_fmap_t * const p_map,IN cl_fmap_item_t * p_item)1386 __cl_fmap_del_bal(IN cl_fmap_t * const p_map, IN cl_fmap_item_t * p_item)
1387 {
1388 cl_fmap_item_t *p_uncle;
1389
1390 while ((p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root)) {
1391 if (__cl_fmap_is_left_child(p_item)) {
1392 p_uncle = p_item->p_up->p_right;
1393
1394 if (p_uncle->color == CL_MAP_RED) {
1395 p_uncle->color = CL_MAP_BLACK;
1396 p_item->p_up->color = CL_MAP_RED;
1397 __cl_fmap_rot_left(p_map, p_item->p_up);
1398 p_uncle = p_item->p_up->p_right;
1399 }
1400
1401 if (p_uncle->p_right->color != CL_MAP_RED) {
1402 if (p_uncle->p_left->color != CL_MAP_RED) {
1403 p_uncle->color = CL_MAP_RED;
1404 p_item = p_item->p_up;
1405 continue;
1406 }
1407
1408 p_uncle->p_left->color = CL_MAP_BLACK;
1409 p_uncle->color = CL_MAP_RED;
1410 __cl_fmap_rot_right(p_map, p_uncle);
1411 p_uncle = p_item->p_up->p_right;
1412 }
1413 p_uncle->color = p_item->p_up->color;
1414 p_item->p_up->color = CL_MAP_BLACK;
1415 p_uncle->p_right->color = CL_MAP_BLACK;
1416 __cl_fmap_rot_left(p_map, p_item->p_up);
1417 break;
1418 } else {
1419 p_uncle = p_item->p_up->p_left;
1420
1421 if (p_uncle->color == CL_MAP_RED) {
1422 p_uncle->color = CL_MAP_BLACK;
1423 p_item->p_up->color = CL_MAP_RED;
1424 __cl_fmap_rot_right(p_map, p_item->p_up);
1425 p_uncle = p_item->p_up->p_left;
1426 }
1427
1428 if (p_uncle->p_left->color != CL_MAP_RED) {
1429 if (p_uncle->p_right->color != CL_MAP_RED) {
1430 p_uncle->color = CL_MAP_RED;
1431 p_item = p_item->p_up;
1432 continue;
1433 }
1434
1435 p_uncle->p_right->color = CL_MAP_BLACK;
1436 p_uncle->color = CL_MAP_RED;
1437 __cl_fmap_rot_left(p_map, p_uncle);
1438 p_uncle = p_item->p_up->p_left;
1439 }
1440 p_uncle->color = p_item->p_up->color;
1441 p_item->p_up->color = CL_MAP_BLACK;
1442 p_uncle->p_left->color = CL_MAP_BLACK;
1443 __cl_fmap_rot_right(p_map, p_item->p_up);
1444 break;
1445 }
1446 }
1447 p_item->color = CL_MAP_BLACK;
1448 }
1449
1450 void
cl_fmap_remove_item(IN cl_fmap_t * const p_map,IN cl_fmap_item_t * const p_item)1451 cl_fmap_remove_item(IN cl_fmap_t * const p_map,
1452 IN cl_fmap_item_t * const p_item)
1453 {
1454 cl_fmap_item_t *p_child, *p_del_item;
1455
1456 CL_ASSERT(p_map);
1457 CL_ASSERT(p_map->state == CL_INITIALIZED);
1458 CL_ASSERT(p_item);
1459 CL_ASSERT(p_item->p_map == p_map);
1460
1461 if (p_item == cl_fmap_end(p_map))
1462 return;
1463
1464 if ((p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil)) {
1465 /* The item being removed has children on at most on side. */
1466 p_del_item = p_item;
1467 } else {
1468 /*
1469 * The item being removed has children on both side.
1470 * We select the item that will replace it. After removing
1471 * the substitute item and rebalancing, the tree will have the
1472 * correct topology. Exchanging the substitute for the item
1473 * will finalize the removal.
1474 */
1475 p_del_item = cl_fmap_next(p_item);
1476 CL_ASSERT(p_del_item != &p_map->nil);
1477 }
1478
1479 /* Remove the item from the list. */
1480 __cl_primitive_remove(&p_item->pool_item.list_item);
1481 /* Decrement the item count. */
1482 p_map->count--;
1483
1484 /* Get the pointer to the new root's child, if any. */
1485 if (p_del_item->p_left != &p_map->nil)
1486 p_child = p_del_item->p_left;
1487 else
1488 p_child = p_del_item->p_right;
1489
1490 /*
1491 * This assignment may modify the parent pointer of the nil node.
1492 * This is inconsequential.
1493 */
1494 p_child->p_up = p_del_item->p_up;
1495 (*__cl_fmap_get_parent_ptr_to_item(p_del_item)) = p_child;
1496
1497 if (p_del_item->color != CL_MAP_RED)
1498 __cl_fmap_del_bal(p_map, p_child);
1499
1500 /*
1501 * Note that the splicing done below does not need to occur before
1502 * the tree is balanced, since the actual topology changes are made by the
1503 * preceding code. The topology is preserved by the color assignment made
1504 * below (reader should be reminded that p_del_item == p_item in some cases).
1505 */
1506 if (p_del_item != p_item) {
1507 /*
1508 * Finalize the removal of the specified item by exchanging it with
1509 * the substitute which we removed above.
1510 */
1511 p_del_item->p_up = p_item->p_up;
1512 p_del_item->p_left = p_item->p_left;
1513 p_del_item->p_right = p_item->p_right;
1514 (*__cl_fmap_get_parent_ptr_to_item(p_item)) = p_del_item;
1515 p_item->p_right->p_up = p_del_item;
1516 p_item->p_left->p_up = p_del_item;
1517 p_del_item->color = p_item->color;
1518 }
1519
1520 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
1521
1522 #ifdef _DEBUG_
1523 /* Clear the pointer to the map since the item has been removed. */
1524 p_item->p_map = NULL;
1525 #endif
1526 }
1527
cl_fmap_remove(IN cl_fmap_t * const p_map,IN const void * const p_key)1528 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map,
1529 IN const void *const p_key)
1530 {
1531 cl_fmap_item_t *p_item;
1532
1533 CL_ASSERT(p_map);
1534 CL_ASSERT(p_map->state == CL_INITIALIZED);
1535
1536 /* Seek the node with the specified key */
1537 p_item = cl_fmap_get(p_map, p_key);
1538
1539 cl_fmap_remove_item(p_map, p_item);
1540
1541 return (p_item);
1542 }
1543
1544 void
cl_fmap_merge(OUT cl_fmap_t * const p_dest_map,IN OUT cl_fmap_t * const p_src_map)1545 cl_fmap_merge(OUT cl_fmap_t * const p_dest_map,
1546 IN OUT cl_fmap_t * const p_src_map)
1547 {
1548 cl_fmap_item_t *p_item, *p_item2, *p_next;
1549
1550 CL_ASSERT(p_dest_map);
1551 CL_ASSERT(p_src_map);
1552
1553 p_item = cl_fmap_head(p_src_map);
1554
1555 while (p_item != cl_fmap_end(p_src_map)) {
1556 p_next = cl_fmap_next(p_item);
1557
1558 /* Remove the item from its current map. */
1559 cl_fmap_remove_item(p_src_map, p_item);
1560 /* Insert the item into the destination map. */
1561 p_item2 =
1562 cl_fmap_insert(p_dest_map, cl_fmap_key(p_item), p_item);
1563 /* Check that the item was successfully inserted. */
1564 if (p_item2 != p_item) {
1565 /* Put the item in back in the source map. */
1566 p_item2 =
1567 cl_fmap_insert(p_src_map, cl_fmap_key(p_item),
1568 p_item);
1569 CL_ASSERT(p_item2 == p_item);
1570 }
1571 p_item = p_next;
1572 }
1573 }
1574
1575 static void
__cl_fmap_delta_move(IN OUT cl_fmap_t * const p_dest,IN OUT cl_fmap_t * const p_src,IN OUT cl_fmap_item_t ** const pp_item)1576 __cl_fmap_delta_move(IN OUT cl_fmap_t * const p_dest,
1577 IN OUT cl_fmap_t * const p_src,
1578 IN OUT cl_fmap_item_t ** const pp_item)
1579 {
1580 cl_fmap_item_t *p_temp, *p_next;
1581
1582 /*
1583 * Get the next item so that we can ensure that pp_item points to
1584 * a valid item upon return from the function.
1585 */
1586 p_next = cl_fmap_next(*pp_item);
1587 /* Move the old item from its current map the the old map. */
1588 cl_fmap_remove_item(p_src, *pp_item);
1589 p_temp = cl_fmap_insert(p_dest, cl_fmap_key(*pp_item), *pp_item);
1590 /* We should never have duplicates. */
1591 CL_ASSERT(p_temp == *pp_item);
1592 /* Point pp_item to a valid item in the source map. */
1593 (*pp_item) = p_next;
1594 }
1595
1596 void
cl_fmap_delta(IN OUT cl_fmap_t * const p_map1,IN OUT cl_fmap_t * const p_map2,OUT cl_fmap_t * const p_new,OUT cl_fmap_t * const p_old)1597 cl_fmap_delta(IN OUT cl_fmap_t * const p_map1,
1598 IN OUT cl_fmap_t * const p_map2,
1599 OUT cl_fmap_t * const p_new, OUT cl_fmap_t * const p_old)
1600 {
1601 cl_fmap_item_t *p_item1, *p_item2;
1602 intn_t cmp;
1603
1604 CL_ASSERT(p_map1);
1605 CL_ASSERT(p_map2);
1606 CL_ASSERT(p_new);
1607 CL_ASSERT(p_old);
1608 CL_ASSERT(cl_is_fmap_empty(p_new));
1609 CL_ASSERT(cl_is_fmap_empty(p_old));
1610
1611 p_item1 = cl_fmap_head(p_map1);
1612 p_item2 = cl_fmap_head(p_map2);
1613
1614 while (p_item1 != cl_fmap_end(p_map1) && p_item2 != cl_fmap_end(p_map2)) {
1615 cmp = p_map1->pfn_compare(cl_fmap_key(p_item1),
1616 cl_fmap_key(p_item2));
1617 if (cmp < 0) {
1618 /* We found an old item. */
1619 __cl_fmap_delta_move(p_old, p_map1, &p_item1);
1620 } else if (cmp > 0) {
1621 /* We found a new item. */
1622 __cl_fmap_delta_move(p_new, p_map2, &p_item2);
1623 } else {
1624 /* Move both forward since they have the same key. */
1625 p_item1 = cl_fmap_next(p_item1);
1626 p_item2 = cl_fmap_next(p_item2);
1627 }
1628 }
1629
1630 /* Process the remainder if the end of either source map was reached. */
1631 while (p_item2 != cl_fmap_end(p_map2))
1632 __cl_fmap_delta_move(p_new, p_map2, &p_item2);
1633
1634 while (p_item1 != cl_fmap_end(p_map1))
1635 __cl_fmap_delta_move(p_old, p_map1, &p_item1);
1636 }
1637