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.
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:
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
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.
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
38 * Implementation of quick map, a binary tree where the caller always
39 * provides all necessary storage.
43 /*****************************************************************************
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.
55 * This implementation of Map uses a red black tree verified against
56 * Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth
59 *****************************************************************************/
63 #endif /* HAVE_CONFIG_H */
66 #include <complib/cl_qmap.h>
67 #include <complib/cl_map.h>
68 #include <complib/cl_fleximap.h>
70 /******************************************************************************
71 IMPLEMENTATION OF QUICK MAP
72 ******************************************************************************/
77 static inline cl_map_item_t *__cl_map_root(IN const cl_qmap_t * const p_map)
80 return (p_map->root.p_left);
84 * Returns whether a given item is on the left of its parent.
86 static boolean_t __cl_map_is_left_child(IN const cl_map_item_t * const p_item)
89 CL_ASSERT(p_item->p_up);
90 CL_ASSERT(p_item->p_up != p_item);
92 return (p_item->p_up->p_left == p_item);
96 * Retrieve the pointer to the parent's pointer to an item.
98 static cl_map_item_t **__cl_map_get_parent_ptr_to_item(IN cl_map_item_t *
102 CL_ASSERT(p_item->p_up);
103 CL_ASSERT(p_item->p_up != p_item);
105 if (__cl_map_is_left_child(p_item))
106 return (&p_item->p_up->p_left);
108 CL_ASSERT(p_item->p_up->p_right == p_item);
109 return (&p_item->p_up->p_right);
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.
127 static void __cl_map_rot_left(IN cl_qmap_t * const p_map,
128 IN cl_map_item_t * const p_item)
130 cl_map_item_t **pp_root;
134 CL_ASSERT(p_item->p_right != &p_map->nil);
136 pp_root = __cl_map_get_parent_ptr_to_item(p_item);
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;
143 /* Set A's right to B */
144 p_item->p_right = (*pp_root)->p_left;
146 * Set B's parent to A. We trap for B being NIL since the
147 * caller may depend on NIL not changing.
149 if ((*pp_root)->p_left != &p_map->nil)
150 (*pp_root)->p_left->p_up = p_item;
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;
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.
173 static void __cl_map_rot_right(IN cl_qmap_t * const p_map,
174 IN cl_map_item_t * const p_item)
176 cl_map_item_t **pp_root;
180 CL_ASSERT(p_item->p_left != &p_map->nil);
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;
188 /* Set C's left to B */
189 p_item->p_left = (*pp_root)->p_right;
191 * Set B's parent to C. We trap for B being NIL since the
192 * caller may depend on NIL not changing.
194 if ((*pp_root)->p_right != &p_map->nil)
195 (*pp_root)->p_right->p_up = p_item;
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;
203 void cl_qmap_init(IN cl_qmap_t * const p_map)
207 memset(p_map, 0, sizeof(cl_qmap_t));
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;
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;
221 p_map->state = CL_INITIALIZED;
223 cl_qmap_remove_all(p_map);
226 cl_map_item_t *cl_qmap_get(IN const cl_qmap_t * const p_map,
227 IN const uint64_t key)
229 cl_map_item_t *p_item;
232 CL_ASSERT(p_map->state == CL_INITIALIZED);
234 p_item = __cl_map_root(p_map);
236 while (p_item != &p_map->nil) {
237 if (key == p_item->key)
238 break; /* just right */
240 if (key < p_item->key)
241 p_item = p_item->p_left; /* too small */
243 p_item = p_item->p_right; /* too big */
249 cl_map_item_t *cl_qmap_get_next(IN const cl_qmap_t * const p_map,
250 IN const uint64_t key)
252 cl_map_item_t *p_item;
253 cl_map_item_t *p_item_found;
256 CL_ASSERT(p_map->state == CL_INITIALIZED);
258 p_item = __cl_map_root(p_map);
259 p_item_found = (cl_map_item_t *) & p_map->nil;
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;
266 p_item = p_item->p_right;
270 return (p_item_found);
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)
277 cl_map_item_t *p_map_item;
279 /* Note that context can have any arbitrary value. */
281 CL_ASSERT(p_map->state == CL_INITIALIZED);
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);
292 * Balance a tree starting at a given item back to the root.
294 static void __cl_map_ins_bal(IN cl_qmap_t * const p_map,
295 IN cl_map_item_t * p_item)
297 cl_map_item_t *p_grand_uncle;
301 CL_ASSERT(p_item != &p_map->root);
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;
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);
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);
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;
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);
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);
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)
348 cl_map_item_t *p_insert_at, *p_comp_item;
351 CL_ASSERT(p_map->state == CL_INITIALIZED);
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);
357 p_item->p_left = &p_map->nil;
358 p_item->p_right = &p_map->nil;
360 p_item->color = CL_MAP_RED;
362 /* Find the insertion location. */
363 p_insert_at = &p_map->root;
364 p_comp_item = __cl_map_root(p_map);
366 while (p_comp_item != &p_map->nil) {
367 p_insert_at = p_comp_item;
369 if (key == p_insert_at->key)
370 return (p_insert_at);
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;
376 p_comp_item = p_insert_at->p_right;
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;
385 * Primitive insert places the new item in front of
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;
393 * Primitive insert places the new item in front of
396 __cl_primitive_insert(&p_insert_at->pool_item.list_item,
397 &p_item->pool_item.list_item);
399 p_insert_at->p_right = p_item;
401 * Primitive insert places the new item in front of
404 __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next,
405 &p_item->pool_item.list_item);
407 /* Increase the count. */
410 p_item->p_up = p_insert_at;
413 * We have added depth to this section of the tree.
414 * Rebalance as necessary as we retrace our path through the tree
417 __cl_map_ins_bal(p_map, p_item);
419 __cl_map_root(p_map)->color = CL_MAP_BLACK;
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.
428 /* Set the pointer to the map in the map item for consistency checking. */
429 p_item->p_map = p_map;
435 static void __cl_map_del_bal(IN cl_qmap_t * const p_map,
436 IN cl_map_item_t * p_item)
438 cl_map_item_t *p_uncle;
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;
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;
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;
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;
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);
469 p_uncle = p_item->p_up->p_left;
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;
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;
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;
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);
497 p_item->color = CL_MAP_BLACK;
500 void cl_qmap_remove_item(IN cl_qmap_t * const p_map,
501 IN cl_map_item_t * const p_item)
503 cl_map_item_t *p_child, *p_del_item;
506 CL_ASSERT(p_map->state == CL_INITIALIZED);
509 if (p_item == cl_qmap_end(p_map))
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);
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. */
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.
527 p_del_item = cl_qmap_next(p_item);
528 CL_ASSERT(p_del_item != &p_map->nil);
531 /* Remove the item from the list. */
532 __cl_primitive_remove(&p_item->pool_item.list_item);
533 /* Decrement the item count. */
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;
540 p_child = p_del_item->p_right;
543 * This assignment may modify the parent pointer of the nil node.
544 * This is inconsequential.
546 p_child->p_up = p_del_item->p_up;
547 (*__cl_map_get_parent_ptr_to_item(p_del_item)) = p_child;
549 if (p_del_item->color != CL_MAP_RED)
550 __cl_map_del_bal(p_map, p_child);
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).
558 if (p_del_item != p_item) {
560 * Finalize the removal of the specified item by exchanging it with
561 * the substitute which we removed above.
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;
572 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
575 /* Clear the pointer to the map since the item has been removed. */
576 p_item->p_map = NULL;
580 cl_map_item_t *cl_qmap_remove(IN cl_qmap_t * const p_map, IN const uint64_t key)
582 cl_map_item_t *p_item;
585 CL_ASSERT(p_map->state == CL_INITIALIZED);
587 /* Seek the node with the specified key */
588 p_item = cl_qmap_get(p_map, key);
590 cl_qmap_remove_item(p_map, p_item);
595 void cl_qmap_merge(OUT cl_qmap_t * const p_dest_map,
596 IN OUT cl_qmap_t * const p_src_map)
598 cl_map_item_t *p_item, *p_item2, *p_next;
600 CL_ASSERT(p_dest_map);
601 CL_ASSERT(p_src_map);
603 p_item = cl_qmap_head(p_src_map);
605 while (p_item != cl_qmap_end(p_src_map)) {
606 p_next = cl_qmap_next(p_item);
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. */
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. */
617 cl_qmap_insert(p_src_map, cl_qmap_key(p_item),
619 CL_ASSERT(p_item2 == p_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)
629 cl_map_item_t __attribute__((__unused__)) *p_temp;
630 cl_map_item_t *p_next;
633 * Get the next item so that we can ensure that pp_item points to
634 * a valid item upon return from the function.
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. */
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)
650 cl_map_item_t *p_item1, *p_item2;
657 CL_ASSERT(cl_is_qmap_empty(p_new));
658 CL_ASSERT(cl_is_qmap_empty(p_old));
660 p_item1 = cl_qmap_head(p_map1);
661 p_item2 = cl_qmap_head(p_map2);
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);
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);
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);
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);
683 while (p_item1 != cl_qmap_end(p_map1))
684 __cl_qmap_delta_move(p_old, p_map1, &p_item1);
687 /******************************************************************************
688 IMPLEMENTATION OF MAP
689 ******************************************************************************/
691 #define MAP_GROW_SIZE 32
693 void cl_map_construct(IN cl_map_t * const p_map)
697 cl_qpool_construct(&p_map->pool);
700 cl_status_t cl_map_init(IN cl_map_t * const p_map, IN const uint32_t min_items)
706 cl_qmap_init(&p_map->qmap);
709 * We will grow by min_items/8 items at a time, with a minimum of
712 grow_size = min_items >> 3;
713 if (grow_size < MAP_GROW_SIZE)
714 grow_size = MAP_GROW_SIZE;
716 return (cl_qpool_init(&p_map->pool, min_items, 0, grow_size,
717 sizeof(cl_map_obj_t), NULL, NULL, NULL));
720 void cl_map_destroy(IN cl_map_t * const p_map)
724 cl_qpool_destroy(&p_map->pool);
727 void *cl_map_insert(IN cl_map_t * const p_map,
728 IN const uint64_t key, IN const void *const p_object)
730 cl_map_obj_t *p_map_obj, *p_obj_at_key;
734 p_map_obj = (cl_map_obj_t *) cl_qpool_get(&p_map->pool);
739 cl_qmap_set_obj(p_map_obj, p_object);
742 (cl_map_obj_t *) cl_qmap_insert(&p_map->qmap, key,
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);
749 return (cl_qmap_obj(p_obj_at_key));
752 void *cl_map_get(IN const cl_map_t * const p_map, IN const uint64_t key)
754 cl_map_item_t *p_item;
758 p_item = cl_qmap_get(&p_map->qmap, key);
760 if (p_item == cl_qmap_end(&p_map->qmap))
763 return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item)));
766 void *cl_map_get_next(IN const cl_map_t * const p_map, IN const uint64_t key)
768 cl_map_item_t *p_item;
772 p_item = cl_qmap_get_next(&p_map->qmap, key);
774 if (p_item == cl_qmap_end(&p_map->qmap))
777 return (cl_qmap_obj(PARENT_STRUCT(p_item, cl_map_obj_t, item)));
780 void cl_map_remove_item(IN cl_map_t * const p_map,
781 IN const cl_map_iterator_t itor)
783 CL_ASSERT(itor->p_map == &p_map->qmap);
785 if (itor == cl_map_end(p_map))
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);
792 void *cl_map_remove(IN cl_map_t * const p_map, IN const uint64_t key)
794 cl_map_item_t *p_item;
799 p_item = cl_qmap_remove(&p_map->qmap, key);
801 if (p_item == cl_qmap_end(&p_map->qmap))
804 p_obj = cl_qmap_obj((cl_map_obj_t *) p_item);
805 cl_qpool_put(&p_map->pool, &p_item->pool_item);
810 void cl_map_remove_all(IN cl_map_t * const p_map)
812 cl_map_item_t *p_item;
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);
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);
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)
833 cl_status_t status = CL_SUCCESS;
834 cl_map_iterator_t itor, next;
836 void *p_obj, *p_obj2;
838 CL_ASSERT(p_dest_map);
839 CL_ASSERT(p_src_map);
841 itor = cl_map_head(p_src_map);
842 while (itor != cl_map_end(p_src_map)) {
843 next = cl_map_next(itor);
845 p_obj = cl_map_obj(itor);
846 key = cl_map_key(itor);
848 cl_map_remove_item(p_src_map, itor);
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) {
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)
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)
874 cl_status_t __attribute__((__unused__)) status;
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);
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)
887 cl_map_iterator_t next;
888 void *p_obj, *p_obj2;
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. */
902 p_obj2 = cl_map_insert(p_src, key, p_obj);
903 CL_ASSERT(p_obj2 == p_obj);
904 return (CL_INSUFFICIENT_MEMORY);
907 /* We should never get a duplicate */
908 CL_ASSERT(p_obj == p_obj2);
909 /* Update the iterator so that it is valid. */
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)
919 cl_map_iterator_t itor1, itor2;
927 CL_ASSERT(cl_is_map_empty(p_new));
928 CL_ASSERT(cl_is_map_empty(p_old));
930 itor1 = cl_map_head(p_map1);
931 itor2 = cl_map_head(p_map2);
934 * Note that the check is for the end, since duplicate items will remain
935 * in their respective maps.
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);
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. */
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. */
958 /* Move both forward since they have the same key. */
959 itor1 = cl_map_next(itor1);
960 itor2 = cl_map_next(itor2);
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. */
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. */
988 /******************************************************************************
989 IMPLEMENTATION OF FLEXI MAP
990 ******************************************************************************/
995 static inline cl_fmap_item_t *__cl_fmap_root(IN const cl_fmap_t * const p_map)
998 return (p_map->root.p_left);
1002 * Returns whether a given item is on the left of its parent.
1004 static boolean_t __cl_fmap_is_left_child(IN const cl_fmap_item_t * const p_item)
1007 CL_ASSERT(p_item->p_up);
1008 CL_ASSERT(p_item->p_up != p_item);
1010 return (p_item->p_up->p_left == p_item);
1014 * Retrieve the pointer to the parent's pointer to an item.
1016 static cl_fmap_item_t **__cl_fmap_get_parent_ptr_to_item(IN cl_fmap_item_t *
1020 CL_ASSERT(p_item->p_up);
1021 CL_ASSERT(p_item->p_up != p_item);
1023 if (__cl_fmap_is_left_child(p_item))
1024 return (&p_item->p_up->p_left);
1026 CL_ASSERT(p_item->p_up->p_right == p_item);
1027 return (&p_item->p_up->p_right);
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.
1045 static void __cl_fmap_rot_left(IN cl_fmap_t * const p_map,
1046 IN cl_fmap_item_t * const p_item)
1048 cl_fmap_item_t **pp_root;
1052 CL_ASSERT(p_item->p_right != &p_map->nil);
1054 pp_root = __cl_fmap_get_parent_ptr_to_item(p_item);
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;
1061 /* Set A's right to B */
1062 p_item->p_right = (*pp_root)->p_left;
1064 * Set B's parent to A. We trap for B being NIL since the
1065 * caller may depend on NIL not changing.
1067 if ((*pp_root)->p_left != &p_map->nil)
1068 (*pp_root)->p_left->p_up = p_item;
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;
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.
1091 static void __cl_fmap_rot_right(IN cl_fmap_t * const p_map,
1092 IN cl_fmap_item_t * const p_item)
1094 cl_fmap_item_t **pp_root;
1098 CL_ASSERT(p_item->p_left != &p_map->nil);
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;
1106 /* Set C's left to B */
1107 p_item->p_left = (*pp_root)->p_right;
1109 * Set B's parent to C. We trap for B being NIL since the
1110 * caller may depend on NIL not changing.
1112 if ((*pp_root)->p_right != &p_map->nil)
1113 (*pp_root)->p_right->p_up = p_item;
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;
1121 void cl_fmap_init(IN cl_fmap_t * const p_map, IN cl_pfn_fmap_cmp_t pfn_compare)
1124 CL_ASSERT(pfn_compare);
1126 memset(p_map, 0, sizeof(cl_fmap_t));
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;
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;
1140 /* Store the compare function pointer. */
1141 p_map->pfn_compare = pfn_compare;
1143 p_map->state = CL_INITIALIZED;
1145 cl_fmap_remove_all(p_map);
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)
1152 cl_fmap_item_t *p_item;
1156 CL_ASSERT(p_map->state == CL_INITIALIZED);
1158 p_item = __cl_fmap_root(p_map);
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);
1165 break; /* just right */
1168 p_item = p_item->p_left; /* too small */
1170 p_item = p_item->p_right; /* too big */
1176 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map,
1177 IN const void *const p_key)
1179 return cl_fmap_match(p_map, p_key, p_map->pfn_compare);
1182 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map,
1183 IN const void *const p_key)
1185 cl_fmap_item_t *p_item;
1186 cl_fmap_item_t *p_item_found;
1190 CL_ASSERT(p_map->state == CL_INITIALIZED);
1192 p_item = __cl_fmap_root(p_map);
1193 p_item_found = (cl_fmap_item_t *) & p_map->nil;
1195 while (p_item != &p_map->nil) {
1196 cmp = p_map->pfn_compare(p_key, p_item->p_key);
1199 p_item_found = p_item;
1200 p_item = p_item->p_left; /* too small */
1202 p_item = p_item->p_right; /* too big or match */
1206 return (p_item_found);
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)
1213 cl_fmap_item_t *p_fmap_item;
1215 /* Note that context can have any arbitrary value. */
1217 CL_ASSERT(p_map->state == CL_INITIALIZED);
1218 CL_ASSERT(pfn_func);
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);
1228 * Balance a tree starting at a given item back to the root.
1230 static void __cl_fmap_ins_bal(IN cl_fmap_t * const p_map,
1231 IN cl_fmap_item_t * p_item)
1233 cl_fmap_item_t *p_grand_uncle;
1237 CL_ASSERT(p_item != &p_map->root);
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;
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);
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);
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;
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);
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);
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)
1284 cl_fmap_item_t *p_insert_at, *p_comp_item;
1288 CL_ASSERT(p_map->state == CL_INITIALIZED);
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);
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;
1299 /* Find the insertion location. */
1300 p_insert_at = &p_map->root;
1301 p_comp_item = __cl_fmap_root(p_map);
1303 while (p_comp_item != &p_map->nil) {
1304 p_insert_at = p_comp_item;
1306 cmp = p_map->pfn_compare(p_key, p_insert_at->p_key);
1309 return (p_insert_at);
1311 /* Traverse the tree until the correct insertion point is found. */
1313 p_comp_item = p_insert_at->p_left;
1315 p_comp_item = p_insert_at->p_right;
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;
1324 * Primitive insert places the new item in front of
1325 * the existing item.
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;
1332 * Primitive insert places the new item in front of
1333 * the existing item.
1335 __cl_primitive_insert(&p_insert_at->pool_item.list_item,
1336 &p_item->pool_item.list_item);
1338 p_insert_at->p_right = p_item;
1340 * Primitive insert places the new item in front of
1341 * the existing item.
1343 __cl_primitive_insert(p_insert_at->pool_item.list_item.p_next,
1344 &p_item->pool_item.list_item);
1346 /* Increase the count. */
1349 p_item->p_up = p_insert_at;
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.
1356 __cl_fmap_ins_bal(p_map, p_item);
1358 __cl_fmap_root(p_map)->color = CL_MAP_BLACK;
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.
1367 /* Set the pointer to the map in the map item for consistency checking. */
1368 p_item->p_map = p_map;
1374 static void __cl_fmap_del_bal(IN cl_fmap_t * const p_map,
1375 IN cl_fmap_item_t * p_item)
1377 cl_fmap_item_t *p_uncle;
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;
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;
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;
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;
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);
1408 p_uncle = p_item->p_up->p_left;
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;
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;
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;
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);
1436 p_item->color = CL_MAP_BLACK;
1439 void cl_fmap_remove_item(IN cl_fmap_t * const p_map,
1440 IN cl_fmap_item_t * const p_item)
1442 cl_fmap_item_t *p_child, *p_del_item;
1445 CL_ASSERT(p_map->state == CL_INITIALIZED);
1447 CL_ASSERT(p_item->p_map == p_map);
1449 if (p_item == cl_fmap_end(p_map))
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;
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.
1463 p_del_item = cl_fmap_next(p_item);
1464 CL_ASSERT(p_del_item != &p_map->nil);
1467 /* Remove the item from the list. */
1468 __cl_primitive_remove(&p_item->pool_item.list_item);
1469 /* Decrement the item count. */
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;
1476 p_child = p_del_item->p_right;
1479 * This assignment may modify the parent pointer of the nil node.
1480 * This is inconsequential.
1482 p_child->p_up = p_del_item->p_up;
1483 (*__cl_fmap_get_parent_ptr_to_item(p_del_item)) = p_child;
1485 if (p_del_item->color != CL_MAP_RED)
1486 __cl_fmap_del_bal(p_map, p_child);
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).
1494 if (p_del_item != p_item) {
1496 * Finalize the removal of the specified item by exchanging it with
1497 * the substitute which we removed above.
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;
1508 CL_ASSERT(p_map->nil.color != CL_MAP_RED);
1511 /* Clear the pointer to the map since the item has been removed. */
1512 p_item->p_map = NULL;
1516 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map,
1517 IN const void *const p_key)
1519 cl_fmap_item_t *p_item;
1522 CL_ASSERT(p_map->state == CL_INITIALIZED);
1524 /* Seek the node with the specified key */
1525 p_item = cl_fmap_get(p_map, p_key);
1527 cl_fmap_remove_item(p_map, p_item);
1532 void cl_fmap_merge(OUT cl_fmap_t * const p_dest_map,
1533 IN OUT cl_fmap_t * const p_src_map)
1535 cl_fmap_item_t *p_item, *p_item2, *p_next;
1537 CL_ASSERT(p_dest_map);
1538 CL_ASSERT(p_src_map);
1540 p_item = cl_fmap_head(p_src_map);
1542 while (p_item != cl_fmap_end(p_src_map)) {
1543 p_next = cl_fmap_next(p_item);
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. */
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. */
1554 cl_fmap_insert(p_src_map, cl_fmap_key(p_item),
1556 CL_ASSERT(p_item2 == p_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)
1566 cl_fmap_item_t __attribute__((__unused__)) *p_temp;
1567 cl_fmap_item_t *p_next;
1570 * Get the next item so that we can ensure that pp_item points to
1571 * a valid item upon return from the function.
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;
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)
1587 cl_fmap_item_t *p_item1, *p_item2;
1594 CL_ASSERT(cl_is_fmap_empty(p_new));
1595 CL_ASSERT(cl_is_fmap_empty(p_old));
1597 p_item1 = cl_fmap_head(p_map1);
1598 p_item2 = cl_fmap_head(p_map2);
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));
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);
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);
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);
1620 while (p_item1 != cl_fmap_end(p_map1))
1621 __cl_fmap_delta_move(p_old, p_map1, &p_item1);