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