git-svn-id: svn://openib.tc.cornell.edu/gen1/branches/WOF2-0@1528 ad392aa1-c5ef-ae45...
[mirror/winof/.git] / core / complib / cl_map.c
1 /*\r
2  * Copyright (c) 2005 SilverStorm Technologies.  All rights reserved.\r
3  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. \r
4  *\r
5  * This software is available to you under the OpenIB.org BSD license\r
6  * below:\r
7  *\r
8  *     Redistribution and use in source and binary forms, with or\r
9  *     without modification, are permitted provided that the following\r
10  *     conditions are met:\r
11  *\r
12  *      - Redistributions of source code must retain the above\r
13  *        copyright notice, this list of conditions and the following\r
14  *        disclaimer.\r
15  *\r
16  *      - Redistributions in binary form must reproduce the above\r
17  *        copyright notice, this list of conditions and the following\r
18  *        disclaimer in the documentation and/or other materials\r
19  *        provided with the distribution.\r
20  *\r
21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
24  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
25  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
26  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
27  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
28  * SOFTWARE.\r
29  *\r
30  * $Id$\r
31  */\r
32 \r
33 \r
34 \r
35 /*\r
36  * Abstract:\r
37  *      Implementation of quick map, a binary tree where the caller always provides\r
38  *      all necessary storage.\r
39  *\r
40  * Environment:\r
41  *      All\r
42  */\r
43 \r
44 \r
45 /*****************************************************************************\r
46 *\r
47 * Map\r
48 *\r
49 * Map is an associative array.  By providing a key, the caller can retrieve\r
50 * an object from the map.  All objects in the map have an associated key,\r
51 * as specified by the caller when the object was inserted into the map.\r
52 * In addition to random access, the caller can traverse the map much like\r
53 * a linked list, either forwards from the first object or backwards from\r
54 * the last object.  The objects in the map are always traversed in\r
55 * order since the nodes are stored sorted.\r
56 *\r
57 * This implementation of Map uses a red black tree verified against\r
58 * Cormen-Leiserson-Rivest text, McGraw-Hill Edition, fourteenth\r
59 * printing, 1994.\r
60 *\r
61 *****************************************************************************/\r
62 \r
63 \r
64 #include <complib/cl_rbmap.h>\r
65 #include <complib/cl_qmap.h>\r
66 #include <complib/cl_map.h>\r
67 #include <complib/cl_fleximap.h>\r
68 #include <complib/cl_memory.h>\r
69 \r
70 \r
71 /******************************************************************************\r
72 *******************************************************************************\r
73 **************                                                                                                     ************\r
74 **************                   IMPLEMENTATION OF RB MAP                                  ************\r
75 **************                                                                                                     ************\r
76 *******************************************************************************\r
77 ******************************************************************************/\r
78 \r
79 \r
80 /*\r
81  * Returns whether a given item is on the left of its parent.\r
82  */\r
83 static boolean_t\r
84 __cl_rbmap_is_left_child(\r
85         IN      const cl_rbmap_item_t* const    p_item )\r
86 {\r
87         CL_ASSERT( p_item );\r
88         CL_ASSERT( p_item->p_up );\r
89         CL_ASSERT( p_item->p_up != p_item );\r
90 \r
91         return( p_item->p_up->p_left == p_item );\r
92 }\r
93 \r
94 \r
95 /*\r
96  * Retrieve the pointer to the parent's pointer to an item.\r
97  */\r
98 static cl_rbmap_item_t**\r
99 __cl_rbmap_get_parent_ptr_to_item(\r
100         IN      cl_rbmap_item_t* const  p_item )\r
101 {\r
102         CL_ASSERT( p_item );\r
103         CL_ASSERT( p_item->p_up );\r
104         CL_ASSERT( p_item->p_up != p_item );\r
105 \r
106         if( __cl_rbmap_is_left_child( p_item ) )\r
107                 return( &p_item->p_up->p_left );\r
108 \r
109         CL_ASSERT( p_item->p_up->p_right == p_item );\r
110         return( &p_item->p_up->p_right );\r
111 }\r
112 \r
113 \r
114 /*\r
115  * Rotate a node to the left.  This rotation affects the least number of links\r
116  * between nodes and brings the level of C up by one while increasing the depth\r
117  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.\r
118  *\r
119  *          R                                 R\r
120  *          |                                 |\r
121  *          A                                 C\r
122  *        /   \                         /   \\r
123  *      W       C                         A       Z\r
124  *             / \                       / \\r
125  *            B   Z                     W   B\r
126  *           / \                           / \\r
127  *          X   Y                         X   Y\r
128  */\r
129 static void\r
130 __cl_rbmap_rot_left(\r
131         IN      cl_rbmap_t* const               p_map,\r
132         IN      cl_rbmap_item_t* const  p_item )\r
133 {\r
134         cl_rbmap_item_t **pp_root;\r
135 \r
136         CL_ASSERT( p_map );\r
137         CL_ASSERT( p_item );\r
138         CL_ASSERT( p_item->p_right != &p_map->nil );\r
139 \r
140         pp_root = __cl_rbmap_get_parent_ptr_to_item( p_item );\r
141 \r
142         /* Point R to C instead of A. */\r
143         *pp_root = p_item->p_right;\r
144         /* Set C's parent to R. */\r
145         (*pp_root)->p_up = p_item->p_up;\r
146 \r
147         /* Set A's right to B */\r
148         p_item->p_right = (*pp_root)->p_left;\r
149         /*\r
150          * Set B's parent to A.  We trap for B being NIL since the\r
151          * caller may depend on NIL not changing.\r
152          */\r
153         if( (*pp_root)->p_left != &p_map->nil )\r
154                 (*pp_root)->p_left->p_up = p_item;\r
155 \r
156         /* Set C's left to A. */\r
157         (*pp_root)->p_left = p_item;\r
158         /* Set A's parent to C. */\r
159         p_item->p_up = *pp_root;\r
160 }\r
161 \r
162 \r
163 /*\r
164  * Rotate a node to the right.  This rotation affects the least number of links\r
165  * between nodes and brings the level of A up by one while increasing the depth\r
166  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.\r
167  *\r
168  *              R                                    R\r
169  *              |                                    |\r
170  *              C                                    A\r
171  *            /   \                                /   \\r
172  *          A       Z                    W       C\r
173  *         / \                                          / \\r
174  *        W   B                                        B   Z\r
175  *           / \                                      / \\r
176  *          X   Y                                    X   Y\r
177  */\r
178 static void\r
179 __cl_rbmap_rot_right(\r
180         IN      cl_rbmap_t* const               p_map,\r
181         IN      cl_rbmap_item_t* const  p_item )\r
182 {\r
183         cl_rbmap_item_t **pp_root;\r
184 \r
185         CL_ASSERT( p_map );\r
186         CL_ASSERT( p_item );\r
187         CL_ASSERT( p_item->p_left != &p_map->nil );\r
188 \r
189         /* Point R to A instead of C. */\r
190         pp_root = __cl_rbmap_get_parent_ptr_to_item( p_item );\r
191         (*pp_root) = p_item->p_left;\r
192         /* Set A's parent to R. */\r
193         (*pp_root)->p_up = p_item->p_up;\r
194 \r
195         /* Set C's left to B */\r
196         p_item->p_left = (*pp_root)->p_right;\r
197         /*\r
198          * Set B's parent to C.  We trap for B being NIL since the\r
199          * caller may depend on NIL not changing.\r
200          */\r
201         if( (*pp_root)->p_right != &p_map->nil )\r
202                 (*pp_root)->p_right->p_up = p_item;\r
203 \r
204         /* Set A's right to C. */\r
205         (*pp_root)->p_right = p_item;\r
206         /* Set C's parent to A. */\r
207         p_item->p_up = *pp_root;\r
208 }\r
209 \r
210 \r
211 /*\r
212  * Balance a tree starting at a given item back to the root.\r
213  */\r
214 static void\r
215 __cl_rbmap_ins_bal(\r
216         IN      cl_rbmap_t* const       p_map,\r
217         IN      cl_rbmap_item_t*        p_item )\r
218 {\r
219         cl_rbmap_item_t*                p_grand_uncle;\r
220 \r
221         CL_ASSERT( p_map );\r
222         CL_ASSERT( p_item );\r
223         CL_ASSERT( p_item != &p_map->root );\r
224 \r
225         while( p_item->p_up->color == CL_MAP_RED )\r
226         {\r
227                 if( __cl_rbmap_is_left_child( p_item->p_up ) )\r
228                 {\r
229                         p_grand_uncle = p_item->p_up->p_up->p_right;\r
230                         CL_ASSERT( p_grand_uncle );\r
231                         if( p_grand_uncle->color == CL_MAP_RED )\r
232                         {\r
233                                 p_grand_uncle->color = CL_MAP_BLACK;\r
234                                 p_item->p_up->color = CL_MAP_BLACK;\r
235                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
236                                 p_item = p_item->p_up->p_up;\r
237                                 continue;\r
238                         }\r
239 \r
240                         if( !__cl_rbmap_is_left_child( p_item ) )\r
241                         {\r
242                                 p_item = p_item->p_up;\r
243                                 __cl_rbmap_rot_left( p_map, p_item );\r
244                         }\r
245                         p_item->p_up->color = CL_MAP_BLACK;\r
246                         p_item->p_up->p_up->color = CL_MAP_RED;\r
247                         __cl_rbmap_rot_right( p_map, p_item->p_up->p_up );\r
248                 }\r
249                 else\r
250                 {\r
251                         p_grand_uncle = p_item->p_up->p_up->p_left;\r
252                         CL_ASSERT( p_grand_uncle );\r
253                         if( p_grand_uncle->color == CL_MAP_RED )\r
254                         {\r
255                                 p_grand_uncle->color = CL_MAP_BLACK;\r
256                                 p_item->p_up->color = CL_MAP_BLACK;\r
257                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
258                                 p_item = p_item->p_up->p_up;\r
259                                 continue;\r
260                         }\r
261 \r
262                         if( __cl_rbmap_is_left_child( p_item ) )\r
263                         {\r
264                                 p_item = p_item->p_up;\r
265                                 __cl_rbmap_rot_right( p_map, p_item );\r
266                         }\r
267                         p_item->p_up->color = CL_MAP_BLACK;\r
268                         p_item->p_up->p_up->color = CL_MAP_RED;\r
269                         __cl_rbmap_rot_left( p_map, p_item->p_up->p_up );\r
270                 }\r
271         }\r
272 }\r
273 \r
274 \r
275 void\r
276 cl_rbmap_insert(\r
277         IN      cl_rbmap_t* const               p_map,\r
278         IN      cl_rbmap_item_t* const  p_insert_at,\r
279         IN      cl_rbmap_item_t* const  p_item,\r
280         IN      boolean_t                               left )\r
281 {\r
282         CL_ASSERT( p_map );\r
283         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
284         CL_ASSERT( p_insert_at );\r
285         CL_ASSERT( p_item );\r
286         CL_ASSERT( p_map->root.p_up == &p_map->root );\r
287         CL_ASSERT( p_map->root.color != CL_MAP_RED );\r
288         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
289 \r
290         p_item->p_left = &p_map->nil;\r
291         p_item->p_right = &p_map->nil;\r
292         p_item->color = CL_MAP_RED;\r
293 \r
294         if( p_insert_at == cl_rbmap_end( p_map ) )\r
295         {\r
296                 p_map->root.p_left = p_item;\r
297                 p_item->p_up = &p_map->root;\r
298         }\r
299         else\r
300         {\r
301                 if( left )\r
302                         p_insert_at->p_left = p_item;\r
303                 else\r
304                         p_insert_at->p_right = p_item;\r
305 \r
306                 p_item->p_up = p_insert_at;\r
307         }\r
308 \r
309         /* Increase the count. */\r
310         p_map->count++;\r
311 \r
312         /*\r
313          * We have added depth to this section of the tree.\r
314          * Rebalance as necessary as we retrace our path through the tree\r
315          * and update colors.\r
316          */\r
317         __cl_rbmap_ins_bal( p_map, p_item );\r
318 \r
319         cl_rbmap_root( p_map )->color = CL_MAP_BLACK;\r
320 \r
321         /*\r
322          * Note that it is not necessary to re-color the nil node black because all\r
323          * red color assignments are made via the p_up pointer, and nil is never\r
324          * set as the value of a p_up pointer.\r
325          */\r
326 \r
327 #ifdef _DEBUG_\r
328         /* Set the pointer to the map in the map item for consistency checking. */\r
329         p_item->p_map = p_map;\r
330 #endif\r
331 }\r
332 \r
333 \r
334 static void\r
335 __cl_rbmap_del_bal(\r
336         IN      cl_rbmap_t* const       p_map,\r
337         IN      cl_rbmap_item_t*        p_item )\r
338 {\r
339         cl_rbmap_item_t         *p_uncle;\r
340 \r
341         while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )\r
342         {\r
343                 if( __cl_rbmap_is_left_child( p_item ) )\r
344                 {\r
345                         p_uncle = p_item->p_up->p_right;\r
346 \r
347                         if( p_uncle->color == CL_MAP_RED )\r
348                         {\r
349                                 p_uncle->color = CL_MAP_BLACK;\r
350                                 p_item->p_up->color = CL_MAP_RED;\r
351                                 __cl_rbmap_rot_left( p_map, p_item->p_up );\r
352                                 p_uncle = p_item->p_up->p_right;\r
353                         }\r
354 \r
355                         if( p_uncle->p_right->color != CL_MAP_RED )\r
356                         {\r
357                                 if( p_uncle->p_left->color != CL_MAP_RED )\r
358                                 {\r
359                                         p_uncle->color = CL_MAP_RED;\r
360                                         p_item = p_item->p_up;\r
361                                         continue;\r
362                                 }\r
363 \r
364                                 p_uncle->p_left->color = CL_MAP_BLACK;\r
365                                 p_uncle->color = CL_MAP_RED;\r
366                                 __cl_rbmap_rot_right( p_map, p_uncle );\r
367                                 p_uncle = p_item->p_up->p_right;\r
368                         }\r
369                         p_uncle->color = p_item->p_up->color;\r
370                         p_item->p_up->color = CL_MAP_BLACK;\r
371                         p_uncle->p_right->color = CL_MAP_BLACK;\r
372                         __cl_rbmap_rot_left( p_map, p_item->p_up );\r
373                         break;\r
374                 }\r
375                 else\r
376                 {\r
377                         p_uncle = p_item->p_up->p_left;\r
378 \r
379                         if( p_uncle->color == CL_MAP_RED )\r
380                         {\r
381                                 p_uncle->color = CL_MAP_BLACK;\r
382                                 p_item->p_up->color = CL_MAP_RED;\r
383                                 __cl_rbmap_rot_right( p_map, p_item->p_up );\r
384                                 p_uncle = p_item->p_up->p_left;\r
385                         }\r
386 \r
387                         if( p_uncle->p_left->color != CL_MAP_RED )\r
388                         {\r
389                                 if( p_uncle->p_right->color != CL_MAP_RED )\r
390                                 {\r
391                                         p_uncle->color = CL_MAP_RED;\r
392                                         p_item = p_item->p_up;\r
393                                         continue;\r
394                                 }\r
395 \r
396                                 p_uncle->p_right->color = CL_MAP_BLACK;\r
397                                 p_uncle->color = CL_MAP_RED;\r
398                                 __cl_rbmap_rot_left( p_map, p_uncle );\r
399                                 p_uncle = p_item->p_up->p_left;\r
400                         }\r
401                         p_uncle->color = p_item->p_up->color;\r
402                         p_item->p_up->color = CL_MAP_BLACK;\r
403                         p_uncle->p_left->color = CL_MAP_BLACK;\r
404                         __cl_rbmap_rot_right( p_map, p_item->p_up );\r
405                         break;\r
406                 }\r
407         }\r
408         p_item->color = CL_MAP_BLACK;\r
409 }\r
410 \r
411 \r
412 void\r
413 cl_rbmap_remove_item(\r
414         IN      cl_rbmap_t* const               p_map,\r
415         IN      cl_rbmap_item_t* const  p_item )\r
416 {\r
417         cl_rbmap_item_t *p_child, *p_del_item;\r
418 \r
419         CL_ASSERT( p_map );\r
420         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
421         CL_ASSERT( p_item );\r
422         CL_ASSERT( p_item->p_map == p_map );\r
423 \r
424         if( p_item == cl_rbmap_end( p_map ) )\r
425                 return;\r
426 \r
427         if( p_item->p_right == &p_map->nil )\r
428         {\r
429                 /* The item being removed has children on at most its left. */\r
430                 p_del_item = p_item;\r
431                 p_child = p_del_item->p_left;\r
432         }\r
433         else if( p_item->p_left == &p_map->nil )\r
434         {\r
435                 /* The item being removed has children on at most its right. */\r
436                 p_del_item = p_item;\r
437                 p_child = p_del_item->p_right;\r
438         }\r
439         else\r
440         {\r
441                 /*\r
442                  * The item being removed has children on both side.\r
443                  * We select the item that will replace it.  After removing\r
444                  * the substitute item and rebalancing, the tree will have the\r
445                  * correct topology.  Exchanging the substitute for the item\r
446                  * will finalize the removal.\r
447                  */\r
448                 p_del_item = p_item->p_right;\r
449                 CL_ASSERT( p_del_item != &p_map->nil );\r
450                 while( p_del_item->p_left != &p_map->nil )\r
451                         p_del_item = p_del_item->p_left;\r
452                 p_child = p_del_item->p_right;\r
453         }\r
454 \r
455         /* Decrement the item count. */\r
456         p_map->count--;\r
457 \r
458         /*\r
459          * This assignment may modify the parent pointer of the nil node.\r
460          * This is inconsequential.\r
461          */\r
462         p_child->p_up = p_del_item->p_up;\r
463         (*__cl_rbmap_get_parent_ptr_to_item( p_del_item )) = p_child; // 2 right = 5\r
464 \r
465         if( p_del_item->color != CL_MAP_RED )\r
466                 __cl_rbmap_del_bal( p_map, p_child );\r
467 \r
468         /*\r
469          * Note that the splicing done below does not need to occur before\r
470          * the tree is balanced, since the actual topology changes are made by the\r
471          * preceding code.  The topology is preserved by the color assignment made\r
472          * below (reader should be reminded that p_del_item == p_item in some cases).\r
473          */\r
474         if( p_del_item != p_item )\r
475         {\r
476                 /*\r
477                  * Finalize the removal of the specified item by exchanging it with\r
478                  * the substitute which we removed above.\r
479                  */\r
480                 p_del_item->p_up = p_item->p_up;\r
481                 p_del_item->p_left = p_item->p_left;\r
482                 p_del_item->p_right = p_item->p_right;\r
483                 (*__cl_rbmap_get_parent_ptr_to_item( p_item )) = p_del_item;\r
484                 p_item->p_right->p_up = p_del_item;\r
485                 p_item->p_left->p_up = p_del_item;\r
486                 p_del_item->color = p_item->color;\r
487         }\r
488 \r
489         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
490 \r
491 #ifdef _DEBUG_\r
492         /* Clear the pointer to the map since the item has been removed. */\r
493         p_item->p_map = NULL;\r
494 #endif\r
495 }\r
496 \r
497 \r
498 /******************************************************************************\r
499 *******************************************************************************\r
500 **************                                                                                                     ************\r
501 **************                   IMPLEMENTATION OF QUICK MAP                       ************\r
502 **************                                                                                                     ************\r
503 *******************************************************************************\r
504 ******************************************************************************/\r
505 \r
506 /*\r
507  * Get the root.\r
508  */\r
509 static inline cl_map_item_t*\r
510 __cl_map_root(\r
511         IN      const cl_qmap_t* const  p_map )\r
512 {\r
513         CL_ASSERT( p_map );\r
514         return( p_map->root.p_left );\r
515 }\r
516 \r
517 \r
518 /*\r
519  * Returns whether a given item is on the left of its parent.\r
520  */\r
521 static boolean_t\r
522 __cl_map_is_left_child(\r
523         IN      const cl_map_item_t* const      p_item )\r
524 {\r
525         CL_ASSERT( p_item );\r
526         CL_ASSERT( p_item->p_up );\r
527         CL_ASSERT( p_item->p_up != p_item );\r
528 \r
529         return( p_item->p_up->p_left == p_item );\r
530 }\r
531 \r
532 \r
533 /*\r
534  * Retrieve the pointer to the parent's pointer to an item.\r
535  */\r
536 static cl_map_item_t**\r
537 __cl_map_get_parent_ptr_to_item(\r
538         IN      cl_map_item_t* const    p_item )\r
539 {\r
540         CL_ASSERT( p_item );\r
541         CL_ASSERT( p_item->p_up );\r
542         CL_ASSERT( p_item->p_up != p_item );\r
543 \r
544         if( __cl_map_is_left_child( p_item ) )\r
545                 return( &p_item->p_up->p_left );\r
546 \r
547         CL_ASSERT( p_item->p_up->p_right == p_item );\r
548         return( &p_item->p_up->p_right );\r
549 }\r
550 \r
551 \r
552 /*\r
553  * Rotate a node to the left.  This rotation affects the least number of links\r
554  * between nodes and brings the level of C up by one while increasing the depth\r
555  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.\r
556  *\r
557  *          R                                 R\r
558  *          |                                 |\r
559  *          A                                 C\r
560  *        /   \                         /   \\r
561  *      W       C                         A       Z\r
562  *             / \                       / \\r
563  *            B   Z                     W   B\r
564  *           / \                           / \\r
565  *          X   Y                         X   Y\r
566  */\r
567 static void\r
568 __cl_map_rot_left(\r
569         IN      cl_qmap_t* const                p_map,\r
570         IN      cl_map_item_t* const    p_item )\r
571 {\r
572         cl_map_item_t   **pp_root;\r
573 \r
574         CL_ASSERT( p_map );\r
575         CL_ASSERT( p_item );\r
576         CL_ASSERT( p_item->p_right != &p_map->nil );\r
577 \r
578         pp_root = __cl_map_get_parent_ptr_to_item( p_item );\r
579 \r
580         /* Point R to C instead of A. */\r
581         *pp_root = p_item->p_right;\r
582         /* Set C's parent to R. */\r
583         (*pp_root)->p_up = p_item->p_up;\r
584 \r
585         /* Set A's right to B */\r
586         p_item->p_right = (*pp_root)->p_left;\r
587         /*\r
588          * Set B's parent to A.  We trap for B being NIL since the\r
589          * caller may depend on NIL not changing.\r
590          */\r
591         if( (*pp_root)->p_left != &p_map->nil )\r
592                 (*pp_root)->p_left->p_up = p_item;\r
593 \r
594         /* Set C's left to A. */\r
595         (*pp_root)->p_left = p_item;\r
596         /* Set A's parent to C. */\r
597         p_item->p_up = *pp_root;\r
598 }\r
599 \r
600 \r
601 /*\r
602  * Rotate a node to the right.  This rotation affects the least number of links\r
603  * between nodes and brings the level of A up by one while increasing the depth\r
604  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.\r
605  *\r
606  *              R                                    R\r
607  *              |                                    |\r
608  *              C                                    A\r
609  *            /   \                                /   \\r
610  *          A       Z                    W       C\r
611  *         / \                                          / \\r
612  *        W   B                                        B   Z\r
613  *           / \                                      / \\r
614  *          X   Y                                    X   Y\r
615  */\r
616 static void\r
617 __cl_map_rot_right(\r
618         IN      cl_qmap_t* const                p_map,\r
619         IN      cl_map_item_t* const    p_item )\r
620 {\r
621         cl_map_item_t   **pp_root;\r
622 \r
623         CL_ASSERT( p_map );\r
624         CL_ASSERT( p_item );\r
625         CL_ASSERT( p_item->p_left != &p_map->nil );\r
626 \r
627         /* Point R to A instead of C. */\r
628         pp_root = __cl_map_get_parent_ptr_to_item( p_item );\r
629         (*pp_root) = p_item->p_left;\r
630         /* Set A's parent to R. */\r
631         (*pp_root)->p_up = p_item->p_up;\r
632 \r
633         /* Set C's left to B */\r
634         p_item->p_left = (*pp_root)->p_right;\r
635         /*\r
636          * Set B's parent to C.  We trap for B being NIL since the\r
637          * caller may depend on NIL not changing.\r
638          */\r
639         if( (*pp_root)->p_right != &p_map->nil )\r
640                 (*pp_root)->p_right->p_up = p_item;\r
641 \r
642         /* Set A's right to C. */\r
643         (*pp_root)->p_right = p_item;\r
644         /* Set C's parent to A. */\r
645         p_item->p_up = *pp_root;\r
646 }\r
647 \r
648 \r
649 void\r
650 cl_qmap_init(\r
651         IN      cl_qmap_t* const        p_map )\r
652 {\r
653         CL_ASSERT( p_map );\r
654 \r
655         cl_memclr( p_map, sizeof(cl_qmap_t) );\r
656 \r
657         /* special setup for the root node */\r
658         p_map->root.p_up = &p_map->root;\r
659         p_map->root.p_left = &p_map->nil;\r
660         p_map->root.p_right = &p_map->nil;\r
661         p_map->root.color = CL_MAP_BLACK;\r
662 \r
663         /* Setup the node used as terminator for all leaves. */\r
664         p_map->nil.p_up = &p_map->nil;\r
665         p_map->nil.p_left = &p_map->nil;\r
666         p_map->nil.p_right = &p_map->nil;\r
667         p_map->nil.color = CL_MAP_BLACK;\r
668 \r
669 #ifdef _DEBUG_\r
670         p_map->root.p_map = p_map;\r
671         p_map->nil.p_map = p_map;\r
672 #endif\r
673 \r
674         p_map->state = CL_INITIALIZED;\r
675 \r
676         cl_qmap_remove_all( p_map );\r
677 }\r
678 \r
679 \r
680 cl_map_item_t*\r
681 cl_qmap_get(\r
682         IN      const cl_qmap_t* const  p_map,\r
683         IN      const uint64_t                  key )\r
684 {\r
685         cl_map_item_t   *p_item;\r
686 \r
687         CL_ASSERT( p_map );\r
688         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
689 \r
690         p_item = __cl_map_root( p_map );\r
691 \r
692         while( p_item != &p_map->nil )\r
693         {\r
694                 if( key == p_item->key )\r
695                         break;                                          /* just right */\r
696 \r
697                 if( key < p_item->key )\r
698                         p_item = p_item->p_left;        /* too small */\r
699                 else\r
700                         p_item = p_item->p_right;       /* too big */\r
701         }\r
702 \r
703         return( p_item );\r
704 }\r
705 \r
706 \r
707 void\r
708 cl_qmap_apply_func(\r
709         IN      const cl_qmap_t* const  p_map,\r
710         IN      cl_pfn_qmap_apply_t             pfn_func,\r
711         IN      const void* const               context )\r
712 {\r
713         cl_map_item_t*  p_map_item;\r
714 \r
715         /* Note that context can have any arbitrary value. */\r
716         CL_ASSERT( p_map );\r
717         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
718         CL_ASSERT( pfn_func );\r
719 \r
720         p_map_item = cl_qmap_head( p_map );\r
721         while( p_map_item != cl_qmap_end( p_map ) )\r
722         {\r
723                 pfn_func( p_map_item, (void*)context );\r
724                 p_map_item = cl_qmap_next( p_map_item );\r
725         }\r
726 }\r
727 \r
728 \r
729 /*\r
730  * Balance a tree starting at a given item back to the root.\r
731  */\r
732 static void\r
733 __cl_map_ins_bal(\r
734         IN      cl_qmap_t* const        p_map,\r
735         IN      cl_map_item_t*          p_item )\r
736 {\r
737         cl_map_item_t*          p_grand_uncle;\r
738 \r
739         CL_ASSERT( p_map );\r
740         CL_ASSERT( p_item );\r
741         CL_ASSERT( p_item != &p_map->root );\r
742 \r
743         while( p_item->p_up->color == CL_MAP_RED )\r
744         {\r
745                 if( __cl_map_is_left_child( p_item->p_up ) )\r
746                 {\r
747                         p_grand_uncle = p_item->p_up->p_up->p_right;\r
748                         CL_ASSERT( p_grand_uncle );\r
749                         if( p_grand_uncle->color == CL_MAP_RED )\r
750                         {\r
751                                 p_grand_uncle->color = CL_MAP_BLACK;\r
752                                 p_item->p_up->color = CL_MAP_BLACK;\r
753                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
754                                 p_item = p_item->p_up->p_up;\r
755                                 continue;\r
756                         }\r
757 \r
758                         if( !__cl_map_is_left_child( p_item ) )\r
759                         {\r
760                                 p_item = p_item->p_up;\r
761                                 __cl_map_rot_left( p_map, p_item );\r
762                         }\r
763                         p_item->p_up->color = CL_MAP_BLACK;\r
764                         p_item->p_up->p_up->color = CL_MAP_RED;\r
765                         __cl_map_rot_right( p_map, p_item->p_up->p_up );\r
766                 }\r
767                 else\r
768                 {\r
769                         p_grand_uncle = p_item->p_up->p_up->p_left;\r
770                         CL_ASSERT( p_grand_uncle );\r
771                         if( p_grand_uncle->color == CL_MAP_RED )\r
772                         {\r
773                                 p_grand_uncle->color = CL_MAP_BLACK;\r
774                                 p_item->p_up->color = CL_MAP_BLACK;\r
775                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
776                                 p_item = p_item->p_up->p_up;\r
777                                 continue;\r
778                         }\r
779 \r
780                         if( __cl_map_is_left_child( p_item ) )\r
781                         {\r
782                                 p_item = p_item->p_up;\r
783                                 __cl_map_rot_right( p_map, p_item );\r
784                         }\r
785                         p_item->p_up->color = CL_MAP_BLACK;\r
786                         p_item->p_up->p_up->color = CL_MAP_RED;\r
787                         __cl_map_rot_left( p_map, p_item->p_up->p_up );\r
788                 }\r
789         }\r
790 }\r
791 \r
792 \r
793 cl_map_item_t*\r
794 cl_qmap_insert(\r
795         IN      cl_qmap_t* const                p_map,\r
796         IN      const uint64_t                  key,\r
797         IN      cl_map_item_t* const    p_item )\r
798 {\r
799         cl_map_item_t   *p_insert_at, *p_comp_item;\r
800 \r
801         CL_ASSERT( p_map );\r
802         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
803         CL_ASSERT( p_item );\r
804         CL_ASSERT( p_map->root.p_up == &p_map->root );\r
805         CL_ASSERT( p_map->root.color != CL_MAP_RED );\r
806         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
807 \r
808         p_item->p_left = &p_map->nil;\r
809         p_item->p_right = &p_map->nil;\r
810         p_item->key = key;\r
811         p_item->color = CL_MAP_RED;\r
812 \r
813         /* Find the insertion location. */\r
814         p_insert_at = &p_map->root;\r
815         p_comp_item = __cl_map_root( p_map );\r
816 \r
817         while( p_comp_item != &p_map->nil )\r
818         {\r
819                 p_insert_at = p_comp_item;\r
820 \r
821                 if( key == p_insert_at->key )\r
822                         return( p_insert_at );\r
823 \r
824                 /* Traverse the tree until the correct insertion point is found. */\r
825                 if( key < p_insert_at->key )\r
826                         p_comp_item = p_insert_at->p_left;\r
827                 else\r
828                         p_comp_item = p_insert_at->p_right;\r
829         }\r
830 \r
831         CL_ASSERT( p_insert_at != &p_map->nil );\r
832         CL_ASSERT( p_comp_item == &p_map->nil );\r
833         /* Insert the item. */\r
834         if( p_insert_at == &p_map->root )\r
835         {\r
836                 p_insert_at->p_left = p_item;\r
837                 /*\r
838                  * Primitive insert places the new item in front of\r
839                  * the existing item.\r
840                  */\r
841                 __cl_primitive_insert( &p_map->nil.pool_item.list_item,\r
842                         &p_item->pool_item.list_item );\r
843         }\r
844         else if( key < p_insert_at->key )\r
845         {\r
846                 p_insert_at->p_left = p_item;\r
847                 /*\r
848                  * Primitive insert places the new item in front of\r
849                  * the existing item.\r
850                  */\r
851                 __cl_primitive_insert( &p_insert_at->pool_item.list_item,\r
852                         &p_item->pool_item.list_item );\r
853         }\r
854         else\r
855         {\r
856                 p_insert_at->p_right = p_item;\r
857                 /*\r
858                  * Primitive insert places the new item in front of\r
859                  * the existing item.\r
860                  */\r
861                 __cl_primitive_insert( p_insert_at->pool_item.list_item.p_next,\r
862                         &p_item->pool_item.list_item );\r
863         }\r
864         /* Increase the count. */\r
865         p_map->count++;\r
866 \r
867         p_item->p_up = p_insert_at;\r
868 \r
869         /*\r
870          * We have added depth to this section of the tree.\r
871          * Rebalance as necessary as we retrace our path through the tree\r
872          * and update colors.\r
873          */\r
874         __cl_map_ins_bal( p_map, p_item );\r
875 \r
876         __cl_map_root( p_map )->color = CL_MAP_BLACK;\r
877 \r
878         /*\r
879          * Note that it is not necessary to re-color the nil node black because all\r
880          * red color assignments are made via the p_up pointer, and nil is never\r
881          * set as the value of a p_up pointer.\r
882          */\r
883 \r
884 #ifdef _DEBUG_\r
885         /* Set the pointer to the map in the map item for consistency checking. */\r
886         p_item->p_map = p_map;\r
887 #endif\r
888 \r
889         return( p_item );\r
890 }\r
891 \r
892 \r
893 static void\r
894 __cl_map_del_bal(\r
895         IN      cl_qmap_t* const        p_map,\r
896         IN      cl_map_item_t*          p_item )\r
897 {\r
898         cl_map_item_t           *p_uncle;\r
899 \r
900         while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )\r
901         {\r
902                 if( __cl_map_is_left_child( p_item ) )\r
903                 {\r
904                         p_uncle = p_item->p_up->p_right;\r
905 \r
906                         if( p_uncle->color == CL_MAP_RED )\r
907                         {\r
908                                 p_uncle->color = CL_MAP_BLACK;\r
909                                 p_item->p_up->color = CL_MAP_RED;\r
910                                 __cl_map_rot_left( p_map, p_item->p_up );\r
911                                 p_uncle = p_item->p_up->p_right;\r
912                         }\r
913 \r
914                         if( p_uncle->p_right->color != CL_MAP_RED )\r
915                         {\r
916                                 if( p_uncle->p_left->color != CL_MAP_RED )\r
917                                 {\r
918                                         p_uncle->color = CL_MAP_RED;\r
919                                         p_item = p_item->p_up;\r
920                                         continue;\r
921                                 }\r
922 \r
923                                 p_uncle->p_left->color = CL_MAP_BLACK;\r
924                                 p_uncle->color = CL_MAP_RED;\r
925                                 __cl_map_rot_right( p_map, p_uncle );\r
926                                 p_uncle = p_item->p_up->p_right;\r
927                         }\r
928                         p_uncle->color = p_item->p_up->color;\r
929                         p_item->p_up->color = CL_MAP_BLACK;\r
930                         p_uncle->p_right->color = CL_MAP_BLACK;\r
931                         __cl_map_rot_left( p_map, p_item->p_up );\r
932                         break;\r
933                 }\r
934                 else\r
935                 {\r
936                         p_uncle = p_item->p_up->p_left;\r
937 \r
938                         if( p_uncle->color == CL_MAP_RED )\r
939                         {\r
940                                 p_uncle->color = CL_MAP_BLACK;\r
941                                 p_item->p_up->color = CL_MAP_RED;\r
942                                 __cl_map_rot_right( p_map, p_item->p_up );\r
943                                 p_uncle = p_item->p_up->p_left;\r
944                         }\r
945 \r
946                         if( p_uncle->p_left->color != CL_MAP_RED )\r
947                         {\r
948                                 if( p_uncle->p_right->color != CL_MAP_RED )\r
949                                 {\r
950                                         p_uncle->color = CL_MAP_RED;\r
951                                         p_item = p_item->p_up;\r
952                                         continue;\r
953                                 }\r
954 \r
955                                 p_uncle->p_right->color = CL_MAP_BLACK;\r
956                                 p_uncle->color = CL_MAP_RED;\r
957                                 __cl_map_rot_left( p_map, p_uncle );\r
958                                 p_uncle = p_item->p_up->p_left;\r
959                         }\r
960                         p_uncle->color = p_item->p_up->color;\r
961                         p_item->p_up->color = CL_MAP_BLACK;\r
962                         p_uncle->p_left->color = CL_MAP_BLACK;\r
963                         __cl_map_rot_right( p_map, p_item->p_up );\r
964                         break;\r
965                 }\r
966         }\r
967         p_item->color = CL_MAP_BLACK;\r
968 }\r
969 \r
970 \r
971 void\r
972 cl_qmap_remove_item(\r
973         IN      cl_qmap_t* const                p_map,\r
974         IN      cl_map_item_t* const    p_item )\r
975 {\r
976         cl_map_item_t   *p_child, *p_del_item;\r
977 \r
978         CL_ASSERT( p_map );\r
979         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
980         CL_ASSERT( p_item );\r
981         CL_ASSERT( p_item->p_map == p_map );\r
982 \r
983         if( p_item == cl_qmap_end( p_map ) )\r
984                 return;\r
985 \r
986         if( (p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil ) )\r
987         {\r
988                 /* The item being removed has children on at most on side. */\r
989                 p_del_item = p_item;\r
990         }\r
991         else\r
992         {\r
993                 /*\r
994                  * The item being removed has children on both side.\r
995                  * We select the item that will replace it.  After removing\r
996                  * the substitute item and rebalancing, the tree will have the\r
997                  * correct topology.  Exchanging the substitute for the item\r
998                  * will finalize the removal.\r
999                  */\r
1000                 p_del_item = cl_qmap_next( p_item );\r
1001                 CL_ASSERT( p_del_item != &p_map->nil );\r
1002         }\r
1003 \r
1004         /* Remove the item from the list. */\r
1005         __cl_primitive_remove( &p_item->pool_item.list_item );\r
1006         /* Decrement the item count. */\r
1007         p_map->count--;\r
1008 \r
1009         /* Get the pointer to the new root's child, if any. */\r
1010         if( p_del_item->p_left != &p_map->nil )\r
1011                 p_child = p_del_item->p_left;\r
1012         else\r
1013                 p_child = p_del_item->p_right;\r
1014 \r
1015         /*\r
1016          * This assignment may modify the parent pointer of the nil node.\r
1017          * This is inconsequential.\r
1018          */\r
1019         p_child->p_up = p_del_item->p_up;\r
1020         (*__cl_map_get_parent_ptr_to_item( p_del_item )) = p_child;\r
1021 \r
1022         if( p_del_item->color != CL_MAP_RED )\r
1023                 __cl_map_del_bal( p_map, p_child );\r
1024 \r
1025         /*\r
1026          * Note that the splicing done below does not need to occur before\r
1027          * the tree is balanced, since the actual topology changes are made by the\r
1028          * preceding code.  The topology is preserved by the color assignment made\r
1029          * below (reader should be reminded that p_del_item == p_item in some cases).\r
1030          */\r
1031         if( p_del_item != p_item )\r
1032         {\r
1033                 /*\r
1034                  * Finalize the removal of the specified item by exchanging it with\r
1035                  * the substitute which we removed above.\r
1036                  */\r
1037                 p_del_item->p_up = p_item->p_up;\r
1038                 p_del_item->p_left = p_item->p_left;\r
1039                 p_del_item->p_right = p_item->p_right;\r
1040                 (*__cl_map_get_parent_ptr_to_item( p_item )) = p_del_item;\r
1041                 p_item->p_right->p_up = p_del_item;\r
1042                 p_item->p_left->p_up = p_del_item;\r
1043                 p_del_item->color = p_item->color;\r
1044         }\r
1045 \r
1046         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
1047 \r
1048 #ifdef _DEBUG_\r
1049         /* Clear the pointer to the map since the item has been removed. */\r
1050         p_item->p_map = NULL;\r
1051 #endif\r
1052 }\r
1053 \r
1054 \r
1055 cl_map_item_t*\r
1056 cl_qmap_remove(\r
1057         IN      cl_qmap_t* const        p_map,\r
1058         IN      const uint64_t          key )\r
1059 {\r
1060         cl_map_item_t   *p_item;\r
1061 \r
1062         CL_ASSERT( p_map );\r
1063         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1064 \r
1065         /* Seek the node with the specified key */\r
1066         p_item = cl_qmap_get( p_map, key );\r
1067 \r
1068         cl_qmap_remove_item( p_map, p_item );\r
1069 \r
1070         return( p_item );\r
1071 }\r
1072 \r
1073 \r
1074 void\r
1075 cl_qmap_merge(\r
1076         OUT             cl_qmap_t* const        p_dest_map,\r
1077         IN OUT  cl_qmap_t* const        p_src_map )\r
1078 {\r
1079         cl_map_item_t           *p_item, *p_item2, *p_next;\r
1080 \r
1081         CL_ASSERT( p_dest_map );\r
1082         CL_ASSERT( p_src_map );\r
1083 \r
1084         p_item = cl_qmap_head( p_src_map );\r
1085 \r
1086         while( p_item != cl_qmap_end( p_src_map ) )\r
1087         {\r
1088                 p_next = cl_qmap_next( p_item );\r
1089 \r
1090                 /* Remove the item from its current map. */\r
1091                 cl_qmap_remove_item( p_src_map, p_item );\r
1092                 /* Insert the item into the destination map. */\r
1093                 p_item2 = cl_qmap_insert( p_dest_map, cl_qmap_key( p_item ), p_item );\r
1094                 /* Check that the item was successfully inserted. */\r
1095                 if( p_item2 != p_item )\r
1096                 {\r
1097                         /* Put the item in back in the source map. */\r
1098                         p_item2 =\r
1099                                 cl_qmap_insert( p_src_map, cl_qmap_key( p_item ), p_item );\r
1100                         CL_ASSERT( p_item2 == p_item );\r
1101                 }\r
1102                 p_item = p_next;\r
1103         }\r
1104 }\r
1105 \r
1106 \r
1107 static void\r
1108 __cl_qmap_delta_move(\r
1109         IN OUT  cl_qmap_t* const                p_dest,\r
1110         IN OUT  cl_qmap_t* const                p_src,\r
1111         IN OUT  cl_map_item_t** const   pp_item )\r
1112 {\r
1113         cl_map_item_t           *p_temp, *p_next;\r
1114 \r
1115         /*\r
1116          * Get the next item so that we can ensure that pp_item points to\r
1117          * a valid item upon return from the function.\r
1118          */\r
1119         p_next = cl_qmap_next( *pp_item );\r
1120         /* Move the old item from its current map the the old map. */\r
1121         cl_qmap_remove_item( p_src, *pp_item );\r
1122         p_temp = cl_qmap_insert( p_dest, cl_qmap_key( *pp_item ), *pp_item );\r
1123         /* We should never have duplicates. */\r
1124         CL_ASSERT( p_temp == *pp_item );\r
1125         /* Point pp_item to a valid item in the source map. */\r
1126         (*pp_item) = p_next;\r
1127 }\r
1128 \r
1129 \r
1130 void\r
1131 cl_qmap_delta(\r
1132         IN OUT  cl_qmap_t* const        p_map1,\r
1133         IN OUT  cl_qmap_t* const        p_map2,\r
1134         OUT             cl_qmap_t* const        p_new,\r
1135         OUT             cl_qmap_t* const        p_old )\r
1136 {\r
1137         cl_map_item_t           *p_item1, *p_item2;\r
1138         uint64_t                        key1, key2;\r
1139 \r
1140         CL_ASSERT( p_map1 );\r
1141         CL_ASSERT( p_map2 );\r
1142         CL_ASSERT( p_new );\r
1143         CL_ASSERT( p_old );\r
1144         CL_ASSERT( cl_is_qmap_empty( p_new ) );\r
1145         CL_ASSERT( cl_is_qmap_empty( p_old ) );\r
1146 \r
1147         p_item1 = cl_qmap_head( p_map1 );\r
1148         p_item2 = cl_qmap_head( p_map2 );\r
1149 \r
1150         while( p_item1 != cl_qmap_end( p_map1 ) &&\r
1151                 p_item2 != cl_qmap_end( p_map2 ) )\r
1152         {\r
1153                 key1 = cl_qmap_key( p_item1 );\r
1154                 key2 = cl_qmap_key( p_item2 );\r
1155                 if( key1 < key2 )\r
1156                 {\r
1157                         /* We found an old item. */\r
1158                         __cl_qmap_delta_move( p_old, p_map1, &p_item1 );\r
1159                 }\r
1160                 else if( key1 > key2 )\r
1161                 {\r
1162                         /* We found a new item. */\r
1163                         __cl_qmap_delta_move( p_new, p_map2, &p_item2 );\r
1164                 }\r
1165                 else\r
1166                 {\r
1167                         /* Move both forward since they have the same key. */\r
1168                         p_item1 = cl_qmap_next( p_item1 );\r
1169                         p_item2 = cl_qmap_next( p_item2 );\r
1170                 }\r
1171         }\r
1172 \r
1173         /* Process the remainder if the end of either source map was reached. */\r
1174         while( p_item2 != cl_qmap_end( p_map2 ) )\r
1175                 __cl_qmap_delta_move( p_new, p_map2, &p_item2 );\r
1176 \r
1177         while( p_item1 != cl_qmap_end( p_map1 ) )\r
1178                 __cl_qmap_delta_move( p_old, p_map1, &p_item1 );\r
1179 }\r
1180 \r
1181 \r
1182 /******************************************************************************\r
1183 *******************************************************************************\r
1184 **************                                                                                                     ************\r
1185 **************                          IMPLEMENTATION OF MAP                              ************\r
1186 **************                                                                                                     ************\r
1187 *******************************************************************************\r
1188 ******************************************************************************/\r
1189 \r
1190 \r
1191 #define MAP_GROW_SIZE 32\r
1192 \r
1193 \r
1194 void\r
1195 cl_map_construct(\r
1196         IN      cl_map_t* const p_map )\r
1197 {\r
1198         CL_ASSERT( p_map );\r
1199 \r
1200         cl_qpool_construct( &p_map->pool );\r
1201 }\r
1202 \r
1203 \r
1204 cl_status_t\r
1205 cl_map_init(\r
1206         IN      cl_map_t* const p_map,\r
1207         IN      const size_t    min_items )\r
1208 {\r
1209         size_t  grow_size;\r
1210 \r
1211         CL_ASSERT( p_map );\r
1212 \r
1213         cl_qmap_init( &p_map->qmap );\r
1214 \r
1215         /*\r
1216          * We will grow by min_items/8 items at a time, with a minimum of\r
1217          * MAP_GROW_SIZE.\r
1218          */\r
1219         grow_size = min_items >> 3;\r
1220         if( grow_size < MAP_GROW_SIZE )\r
1221                 grow_size = MAP_GROW_SIZE;\r
1222 \r
1223         return( cl_qpool_init( &p_map->pool, min_items, 0, grow_size,\r
1224                 sizeof(cl_map_obj_t), NULL, NULL, NULL ) );\r
1225 }\r
1226 \r
1227 \r
1228 void\r
1229 cl_map_destroy(\r
1230         IN      cl_map_t* const p_map )\r
1231 {\r
1232         CL_ASSERT( p_map );\r
1233 \r
1234         cl_qpool_destroy( &p_map->pool );\r
1235 }\r
1236 \r
1237 \r
1238 void*\r
1239 cl_map_insert(\r
1240         IN      cl_map_t* const         p_map,\r
1241         IN      const uint64_t          key,\r
1242         IN      const void* const       p_object )\r
1243 {\r
1244         cl_map_obj_t    *p_map_obj, *p_obj_at_key;\r
1245 \r
1246         CL_ASSERT( p_map );\r
1247 \r
1248         p_map_obj = (cl_map_obj_t*)cl_qpool_get( &p_map->pool );\r
1249 \r
1250         if( !p_map_obj )\r
1251                 return( NULL );\r
1252 \r
1253         cl_qmap_set_obj( p_map_obj, p_object );\r
1254 \r
1255         p_obj_at_key =\r
1256                 (cl_map_obj_t*)cl_qmap_insert( &p_map->qmap, key, &p_map_obj->item );\r
1257 \r
1258         /* Return the item to the pool if insertion failed. */\r
1259         if( p_obj_at_key != p_map_obj )\r
1260                 cl_qpool_put( &p_map->pool, &p_map_obj->item.pool_item );\r
1261 \r
1262         return( cl_qmap_obj( p_obj_at_key ) );\r
1263 }\r
1264 \r
1265 \r
1266 void*\r
1267 cl_map_get(\r
1268         IN      const cl_map_t* const   p_map,\r
1269         IN      const uint64_t                  key )\r
1270 {\r
1271         cl_map_item_t   *p_item;\r
1272 \r
1273         CL_ASSERT( p_map );\r
1274 \r
1275         p_item = cl_qmap_get( &p_map->qmap, key );\r
1276 \r
1277         if( p_item == cl_qmap_end( &p_map->qmap ) )\r
1278                 return( NULL );\r
1279 \r
1280         return( cl_qmap_obj( PARENT_STRUCT( p_item, cl_map_obj_t, item ) ) );\r
1281 }\r
1282 \r
1283 \r
1284 void\r
1285 cl_map_remove_item(\r
1286         IN      cl_map_t* const                 p_map,\r
1287         IN      const cl_map_iterator_t itor )\r
1288 {\r
1289         CL_ASSERT( itor->p_map == &p_map->qmap );\r
1290 \r
1291         if( itor == cl_map_end( p_map ) )\r
1292                 return;\r
1293 \r
1294         cl_qmap_remove_item( &p_map->qmap, (cl_map_item_t*)itor );\r
1295         cl_qpool_put( &p_map->pool, &((cl_map_item_t*)itor)->pool_item );\r
1296 }\r
1297 \r
1298 \r
1299 void*\r
1300 cl_map_remove(\r
1301         IN      cl_map_t* const p_map,\r
1302         IN      const uint64_t  key )\r
1303 {\r
1304         cl_map_item_t   *p_item;\r
1305 \r
1306         CL_ASSERT( p_map );\r
1307 \r
1308         p_item = cl_qmap_remove( &p_map->qmap, key );\r
1309 \r
1310         if( p_item == cl_qmap_end( &p_map->qmap ) )\r
1311                 return( NULL );\r
1312 \r
1313         cl_qpool_put( &p_map->pool, &p_item->pool_item );\r
1314 \r
1315         return( cl_qmap_obj( (cl_map_obj_t*)p_item ) );\r
1316 }\r
1317 \r
1318 \r
1319 void\r
1320 cl_map_remove_all(\r
1321         IN      cl_map_t* const p_map )\r
1322 {\r
1323         cl_map_item_t   *p_item;\r
1324 \r
1325         CL_ASSERT( p_map );\r
1326 \r
1327         /* Return all map items to the pool. */\r
1328         while( !cl_is_qmap_empty( &p_map->qmap ) )\r
1329         {\r
1330                 p_item = cl_qmap_head( &p_map->qmap );\r
1331                 cl_qmap_remove_item( &p_map->qmap, p_item );\r
1332                 cl_qpool_put( &p_map->pool, &p_item->pool_item );\r
1333 \r
1334                 if( !cl_is_qmap_empty( &p_map->qmap ) )\r
1335                 {\r
1336                         p_item = cl_qmap_tail( &p_map->qmap );\r
1337                         cl_qmap_remove_item( &p_map->qmap, p_item );\r
1338                         cl_qpool_put( &p_map->pool, &p_item->pool_item );\r
1339                 }\r
1340         }\r
1341 }\r
1342 \r
1343 \r
1344 cl_status_t\r
1345 cl_map_merge(\r
1346         OUT             cl_map_t* const p_dest_map,\r
1347         IN OUT  cl_map_t* const p_src_map )\r
1348 {\r
1349         cl_status_t                     status = CL_SUCCESS;\r
1350         cl_map_iterator_t       itor, next;\r
1351         uint64_t                        key;\r
1352         void                            *p_obj, *p_obj2;\r
1353 \r
1354         CL_ASSERT( p_dest_map );\r
1355         CL_ASSERT( p_src_map );\r
1356 \r
1357         itor = cl_map_head( p_src_map );\r
1358         while( itor != cl_map_end( p_src_map ) )\r
1359         {\r
1360                 next = cl_map_next( itor );\r
1361 \r
1362                 p_obj = cl_map_obj( itor );\r
1363                 key = cl_map_key( itor );\r
1364 \r
1365                 cl_map_remove_item( p_src_map, itor );\r
1366 \r
1367                 /* Insert the object into the destination map. */\r
1368                 p_obj2 = cl_map_insert( p_dest_map, key, p_obj );\r
1369                 /* Trap for failure. */\r
1370                 if( p_obj != p_obj2 )\r
1371                 {\r
1372                         if( !p_obj2 )\r
1373                                 status = CL_INSUFFICIENT_MEMORY;\r
1374                         /* Put the object back in the source map.  This must succeed. */\r
1375                         p_obj2 = cl_map_insert( p_src_map, key, p_obj );\r
1376                         CL_ASSERT( p_obj == p_obj2 );\r
1377                         /* If the failure was due to insufficient memory, return. */\r
1378                         if( status != CL_SUCCESS )\r
1379                                 return( status );\r
1380                 }\r
1381                 itor = next;\r
1382         }\r
1383 \r
1384         return( CL_SUCCESS );\r
1385 }\r
1386 \r
1387 \r
1388 static void\r
1389 __cl_map_revert(\r
1390         IN OUT  cl_map_t* const p_map1,\r
1391         IN OUT  cl_map_t* const p_map2,\r
1392         IN OUT  cl_map_t* const p_new,\r
1393         IN OUT  cl_map_t* const p_old )\r
1394 {\r
1395         cl_status_t             status;\r
1396 \r
1397         /* Restore the initial state. */\r
1398         status = cl_map_merge( p_map1, p_old );\r
1399         CL_ASSERT( status == CL_SUCCESS );\r
1400         status = cl_map_merge( p_map2, p_new );\r
1401         CL_ASSERT( status == CL_SUCCESS );\r
1402 }\r
1403 \r
1404 \r
1405 static cl_status_t\r
1406 __cl_map_delta_move(\r
1407         OUT             cl_map_t* const                         p_dest,\r
1408         IN OUT  cl_map_t* const                         p_src,\r
1409         IN OUT  cl_map_iterator_t* const        p_itor )\r
1410 {\r
1411         cl_map_iterator_t       next;\r
1412         void                            *p_obj, *p_obj2;\r
1413         uint64_t                        key;\r
1414 \r
1415         /* Get a valid iterator so we can continue the loop. */\r
1416         next = cl_map_next( *p_itor );\r
1417         /* Get the pointer to the object for insertion. */\r
1418         p_obj = cl_map_obj( *p_itor );\r
1419         /* Get the key for the object. */\r
1420         key = cl_map_key( *p_itor );\r
1421         /* Move the object. */\r
1422         cl_map_remove_item( p_src, *p_itor );\r
1423         p_obj2 = cl_map_insert( p_dest, key, p_obj );\r
1424         /* Check for failure. We should never get a duplicate. */\r
1425         if( !p_obj2 )\r
1426         {\r
1427                 p_obj2 = cl_map_insert( p_src, key, p_obj );\r
1428                 CL_ASSERT( p_obj2 == p_obj );\r
1429                 return( CL_INSUFFICIENT_MEMORY );\r
1430         }\r
1431 \r
1432         /* We should never get a duplicate */\r
1433         CL_ASSERT( p_obj == p_obj2 );\r
1434         /* Update the iterator so that it is valid. */\r
1435         (*p_itor) = next;\r
1436 \r
1437         return( CL_SUCCESS );\r
1438 }\r
1439 \r
1440 \r
1441 cl_status_t\r
1442 cl_map_delta(\r
1443         IN OUT  cl_map_t* const p_map1,\r
1444         IN OUT  cl_map_t* const p_map2,\r
1445         OUT             cl_map_t* const p_new,\r
1446         OUT             cl_map_t* const p_old )\r
1447 {\r
1448         cl_map_iterator_t       itor1, itor2;\r
1449         uint64_t                        key1, key2;\r
1450         cl_status_t                     status;\r
1451 \r
1452         CL_ASSERT( p_map1 );\r
1453         CL_ASSERT( p_map2 );\r
1454         CL_ASSERT( p_new );\r
1455         CL_ASSERT( p_old );\r
1456         CL_ASSERT( cl_is_map_empty( p_new ) );\r
1457         CL_ASSERT( cl_is_map_empty( p_old ) );\r
1458 \r
1459         itor1 = cl_map_head( p_map1 );\r
1460         itor2 = cl_map_head( p_map2 );\r
1461 \r
1462         /*\r
1463          * Note that the check is for the end, since duplicate items will remain\r
1464          * in their respective maps.\r
1465          */\r
1466         while( itor1 != cl_map_end( p_map1 ) &&\r
1467                 itor2 != cl_map_end( p_map2 ) )\r
1468         {\r
1469                 key1 = cl_map_key( itor1 );\r
1470                 key2 = cl_map_key( itor2 );\r
1471                 if( key1 < key2 )\r
1472                 {\r
1473                         status = __cl_map_delta_move( p_old, p_map1, &itor1 );\r
1474                         /* Check for failure. */\r
1475                         if( status != CL_SUCCESS )\r
1476                         {\r
1477                                 /* Restore the initial state. */\r
1478                                 __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1479                                 /* Return the failure status. */\r
1480                                 return( status );\r
1481                         }\r
1482                 }\r
1483                 else if( key1 > key2 )\r
1484                 {\r
1485                         status = __cl_map_delta_move( p_new, p_map2, &itor2 );\r
1486                         if( status != CL_SUCCESS )\r
1487                         {\r
1488                                 /* Restore the initial state. */\r
1489                                 __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1490                                 /* Return the failure status. */\r
1491                                 return( status );\r
1492                         }\r
1493                 }\r
1494                 else\r
1495                 {\r
1496                         /* Move both forward since they have the same key. */\r
1497                         itor1 = cl_map_next( itor1 );\r
1498                         itor2 = cl_map_next( itor2 );\r
1499                 }\r
1500         }\r
1501 \r
1502         /* Process the remainder if either source map is empty. */\r
1503         while( itor2 != cl_map_end( p_map2 ) )\r
1504         {\r
1505                 status = __cl_map_delta_move( p_new, p_map2, &itor2 );\r
1506                 if( status != CL_SUCCESS )\r
1507                 {\r
1508                         /* Restore the initial state. */\r
1509                         __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1510                         /* Return the failure status. */\r
1511                         return( status );\r
1512                 }\r
1513         }\r
1514 \r
1515         while( itor1 != cl_map_end( p_map1 ) )\r
1516         {\r
1517                 status = __cl_map_delta_move( p_old, p_map1, &itor1 );\r
1518                 if( status != CL_SUCCESS )\r
1519                 {\r
1520                         /* Restore the initial state. */\r
1521                         __cl_map_revert( p_map1, p_map2, p_new, p_old );\r
1522                         /* Return the failure status. */\r
1523                         return( status );\r
1524                 }\r
1525         }\r
1526 \r
1527         return( CL_SUCCESS );\r
1528 }\r
1529 \r
1530 \r
1531 /******************************************************************************\r
1532 *******************************************************************************\r
1533 **************                                                                                                     ************\r
1534 **************                   IMPLEMENTATION OF FLEXI MAP                       ************\r
1535 **************                                                                                                     ************\r
1536 *******************************************************************************\r
1537 ******************************************************************************/\r
1538 \r
1539 /*\r
1540  * Get the root.\r
1541  */\r
1542 static inline cl_fmap_item_t*\r
1543 __cl_fmap_root(\r
1544         IN      const cl_fmap_t* const  p_map )\r
1545 {\r
1546         CL_ASSERT( p_map );\r
1547         return( p_map->root.p_left );\r
1548 }\r
1549 \r
1550 \r
1551 /*\r
1552  * Returns whether a given item is on the left of its parent.\r
1553  */\r
1554 static boolean_t\r
1555 __cl_fmap_is_left_child(\r
1556         IN      const cl_fmap_item_t* const     p_item )\r
1557 {\r
1558         CL_ASSERT( p_item );\r
1559         CL_ASSERT( p_item->p_up );\r
1560         CL_ASSERT( p_item->p_up != p_item );\r
1561 \r
1562         return( p_item->p_up->p_left == p_item );\r
1563 }\r
1564 \r
1565 \r
1566 /*\r
1567  * Retrieve the pointer to the parent's pointer to an item.\r
1568  */\r
1569 static cl_fmap_item_t**\r
1570 __cl_fmap_get_parent_ptr_to_item(\r
1571         IN      cl_fmap_item_t* const   p_item )\r
1572 {\r
1573         CL_ASSERT( p_item );\r
1574         CL_ASSERT( p_item->p_up );\r
1575         CL_ASSERT( p_item->p_up != p_item );\r
1576 \r
1577         if( __cl_fmap_is_left_child( p_item ) )\r
1578                 return( &p_item->p_up->p_left );\r
1579 \r
1580         CL_ASSERT( p_item->p_up->p_right == p_item );\r
1581         return( &p_item->p_up->p_right );\r
1582 }\r
1583 \r
1584 \r
1585 /*\r
1586  * Rotate a node to the left.  This rotation affects the least number of links\r
1587  * between nodes and brings the level of C up by one while increasing the depth\r
1588  * of A one.  Note that the links to/from W, X, Y, and Z are not affected.\r
1589  *\r
1590  *          R                                 R\r
1591  *          |                                 |\r
1592  *          A                                 C\r
1593  *        /   \                         /   \\r
1594  *      W       C                         A       Z\r
1595  *             / \                       / \\r
1596  *            B   Z                     W   B\r
1597  *           / \                           / \\r
1598  *          X   Y                         X   Y\r
1599  */\r
1600 static void\r
1601 __cl_fmap_rot_left(\r
1602         IN      cl_fmap_t* const                p_map,\r
1603         IN      cl_fmap_item_t* const   p_item )\r
1604 {\r
1605         cl_fmap_item_t  **pp_root;\r
1606 \r
1607         CL_ASSERT( p_map );\r
1608         CL_ASSERT( p_item );\r
1609         CL_ASSERT( p_item->p_right != &p_map->nil );\r
1610 \r
1611         pp_root = __cl_fmap_get_parent_ptr_to_item( p_item );\r
1612 \r
1613         /* Point R to C instead of A. */\r
1614         *pp_root = p_item->p_right;\r
1615         /* Set C's parent to R. */\r
1616         (*pp_root)->p_up = p_item->p_up;\r
1617 \r
1618         /* Set A's right to B */\r
1619         p_item->p_right = (*pp_root)->p_left;\r
1620         /*\r
1621          * Set B's parent to A.  We trap for B being NIL since the\r
1622          * caller may depend on NIL not changing.\r
1623          */\r
1624         if( (*pp_root)->p_left != &p_map->nil )\r
1625                 (*pp_root)->p_left->p_up = p_item;\r
1626 \r
1627         /* Set C's left to A. */\r
1628         (*pp_root)->p_left = p_item;\r
1629         /* Set A's parent to C. */\r
1630         p_item->p_up = *pp_root;\r
1631 }\r
1632 \r
1633 \r
1634 /*\r
1635  * Rotate a node to the right.  This rotation affects the least number of links\r
1636  * between nodes and brings the level of A up by one while increasing the depth\r
1637  * of C one.  Note that the links to/from W, X, Y, and Z are not affected.\r
1638  *\r
1639  *              R                                    R\r
1640  *              |                                    |\r
1641  *              C                                    A\r
1642  *            /   \                                /   \\r
1643  *          A       Z                    W       C\r
1644  *         / \                                          / \\r
1645  *        W   B                                        B   Z\r
1646  *           / \                                      / \\r
1647  *          X   Y                                    X   Y\r
1648  */\r
1649 static void\r
1650 __cl_fmap_rot_right(\r
1651         IN      cl_fmap_t* const                p_map,\r
1652         IN      cl_fmap_item_t* const   p_item )\r
1653 {\r
1654         cl_fmap_item_t  **pp_root;\r
1655 \r
1656         CL_ASSERT( p_map );\r
1657         CL_ASSERT( p_item );\r
1658         CL_ASSERT( p_item->p_left != &p_map->nil );\r
1659 \r
1660         /* Point R to A instead of C. */\r
1661         pp_root = __cl_fmap_get_parent_ptr_to_item( p_item );\r
1662         (*pp_root) = p_item->p_left;\r
1663         /* Set A's parent to R. */\r
1664         (*pp_root)->p_up = p_item->p_up;\r
1665 \r
1666         /* Set C's left to B */\r
1667         p_item->p_left = (*pp_root)->p_right;\r
1668         /*\r
1669          * Set B's parent to C.  We trap for B being NIL since the\r
1670          * caller may depend on NIL not changing.\r
1671          */\r
1672         if( (*pp_root)->p_right != &p_map->nil )\r
1673                 (*pp_root)->p_right->p_up = p_item;\r
1674 \r
1675         /* Set A's right to C. */\r
1676         (*pp_root)->p_right = p_item;\r
1677         /* Set C's parent to A. */\r
1678         p_item->p_up = *pp_root;\r
1679 }\r
1680 \r
1681 \r
1682 void\r
1683 cl_fmap_init(\r
1684         IN      cl_fmap_t* const        p_map,\r
1685         IN      cl_pfn_fmap_cmp_t       pfn_compare )\r
1686 {\r
1687         CL_ASSERT( p_map );\r
1688         CL_ASSERT( pfn_compare );\r
1689 \r
1690         cl_memclr( p_map, sizeof(cl_fmap_t) );\r
1691 \r
1692         /* special setup for the root node */\r
1693         p_map->root.p_up = &p_map->root;\r
1694         p_map->root.p_left = &p_map->nil;\r
1695         p_map->root.p_right = &p_map->nil;\r
1696         p_map->root.color = CL_MAP_BLACK;\r
1697 \r
1698         /* Setup the node used as terminator for all leaves. */\r
1699         p_map->nil.p_up = &p_map->nil;\r
1700         p_map->nil.p_left = &p_map->nil;\r
1701         p_map->nil.p_right = &p_map->nil;\r
1702         p_map->nil.color = CL_MAP_BLACK;\r
1703 \r
1704         /* Store the compare function pointer. */\r
1705         p_map->pfn_compare = pfn_compare;\r
1706 \r
1707         p_map->state = CL_INITIALIZED;\r
1708 \r
1709         cl_fmap_remove_all( p_map );\r
1710 }\r
1711 \r
1712 \r
1713 cl_fmap_item_t*\r
1714 cl_fmap_get(\r
1715         IN      const cl_fmap_t* const  p_map,\r
1716         IN      const void* const               p_key )\r
1717 {\r
1718         cl_fmap_item_t  *p_item;\r
1719         intn_t                  cmp;\r
1720 \r
1721         CL_ASSERT( p_map );\r
1722         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1723 \r
1724         p_item = __cl_fmap_root( p_map );\r
1725 \r
1726         while( p_item != &p_map->nil )\r
1727         {\r
1728                 cmp = p_map->pfn_compare( p_key, p_item->p_key );\r
1729 \r
1730                 if( !cmp )\r
1731                         break;                                          /* just right */\r
1732 \r
1733                 if( cmp < 0 )\r
1734                         p_item = p_item->p_left;        /* too small */\r
1735                 else\r
1736                         p_item = p_item->p_right;       /* too big */\r
1737         }\r
1738 \r
1739         return( p_item );\r
1740 }\r
1741 \r
1742 \r
1743 void\r
1744 cl_fmap_apply_func(\r
1745         IN      const cl_fmap_t* const  p_map,\r
1746         IN      cl_pfn_fmap_apply_t             pfn_func,\r
1747         IN      const void* const               context )\r
1748 {\r
1749         cl_fmap_item_t* p_fmap_item;\r
1750 \r
1751         /* Note that context can have any arbitrary value. */\r
1752         CL_ASSERT( p_map );\r
1753         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1754         CL_ASSERT( pfn_func );\r
1755 \r
1756         p_fmap_item = cl_fmap_head( p_map );\r
1757         while( p_fmap_item != cl_fmap_end( p_map ) )\r
1758         {\r
1759                 pfn_func( p_fmap_item, (void*)context );\r
1760                 p_fmap_item = cl_fmap_next( p_fmap_item );\r
1761         }\r
1762 }\r
1763 \r
1764 \r
1765 /*\r
1766  * Balance a tree starting at a given item back to the root.\r
1767  */\r
1768 static void\r
1769 __cl_fmap_ins_bal(\r
1770         IN      cl_fmap_t* const        p_map,\r
1771         IN      cl_fmap_item_t*         p_item )\r
1772 {\r
1773         cl_fmap_item_t*         p_grand_uncle;\r
1774 \r
1775         CL_ASSERT( p_map );\r
1776         CL_ASSERT( p_item );\r
1777         CL_ASSERT( p_item != &p_map->root );\r
1778 \r
1779         while( p_item->p_up->color == CL_MAP_RED )\r
1780         {\r
1781                 if( __cl_fmap_is_left_child( p_item->p_up ) )\r
1782                 {\r
1783                         p_grand_uncle = p_item->p_up->p_up->p_right;\r
1784                         CL_ASSERT( p_grand_uncle );\r
1785                         if( p_grand_uncle->color == CL_MAP_RED )\r
1786                         {\r
1787                                 p_grand_uncle->color = CL_MAP_BLACK;\r
1788                                 p_item->p_up->color = CL_MAP_BLACK;\r
1789                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
1790                                 p_item = p_item->p_up->p_up;\r
1791                                 continue;\r
1792                         }\r
1793 \r
1794                         if( !__cl_fmap_is_left_child( p_item ) )\r
1795                         {\r
1796                                 p_item = p_item->p_up;\r
1797                                 __cl_fmap_rot_left( p_map, p_item );\r
1798                         }\r
1799                         p_item->p_up->color = CL_MAP_BLACK;\r
1800                         p_item->p_up->p_up->color = CL_MAP_RED;\r
1801                         __cl_fmap_rot_right( p_map, p_item->p_up->p_up );\r
1802                 }\r
1803                 else\r
1804                 {\r
1805                         p_grand_uncle = p_item->p_up->p_up->p_left;\r
1806                         CL_ASSERT( p_grand_uncle );\r
1807                         if( p_grand_uncle->color == CL_MAP_RED )\r
1808                         {\r
1809                                 p_grand_uncle->color = CL_MAP_BLACK;\r
1810                                 p_item->p_up->color = CL_MAP_BLACK;\r
1811                                 p_item->p_up->p_up->color = CL_MAP_RED;\r
1812                                 p_item = p_item->p_up->p_up;\r
1813                                 continue;\r
1814                         }\r
1815 \r
1816                         if( __cl_fmap_is_left_child( p_item ) )\r
1817                         {\r
1818                                 p_item = p_item->p_up;\r
1819                                 __cl_fmap_rot_right( p_map, p_item );\r
1820                         }\r
1821                         p_item->p_up->color = CL_MAP_BLACK;\r
1822                         p_item->p_up->p_up->color = CL_MAP_RED;\r
1823                         __cl_fmap_rot_left( p_map, p_item->p_up->p_up );\r
1824                 }\r
1825         }\r
1826 }\r
1827 \r
1828 \r
1829 cl_fmap_item_t*\r
1830 cl_fmap_insert(\r
1831         IN      cl_fmap_t* const                p_map,\r
1832         IN      const void* const               p_key,\r
1833         IN      cl_fmap_item_t* const   p_item )\r
1834 {\r
1835         cl_fmap_item_t  *p_insert_at, *p_comp_item;\r
1836         intn_t                  cmp = 0;\r
1837 \r
1838         CL_ASSERT( p_map );\r
1839         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
1840         CL_ASSERT( p_item );\r
1841         CL_ASSERT( p_map->root.p_up == &p_map->root );\r
1842         CL_ASSERT( p_map->root.color != CL_MAP_RED );\r
1843         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
1844 \r
1845         p_item->p_left = &p_map->nil;\r
1846         p_item->p_right = &p_map->nil;\r
1847         p_item->p_key = p_key;\r
1848         p_item->color = CL_MAP_RED;\r
1849 \r
1850         /* Find the insertion location. */\r
1851         p_insert_at = &p_map->root;\r
1852         p_comp_item = __cl_fmap_root( p_map );\r
1853 \r
1854         while( p_comp_item != &p_map->nil )\r
1855         {\r
1856                 p_insert_at = p_comp_item;\r
1857 \r
1858                 cmp = p_map->pfn_compare( p_key, p_insert_at->p_key );\r
1859 \r
1860                 if( !cmp )\r
1861                         return( p_insert_at );\r
1862 \r
1863                 /* Traverse the tree until the correct insertion point is found. */\r
1864                 if( cmp < 0 )\r
1865                         p_comp_item = p_insert_at->p_left;\r
1866                 else\r
1867                         p_comp_item = p_insert_at->p_right;\r
1868         }\r
1869 \r
1870         CL_ASSERT( p_insert_at != &p_map->nil );\r
1871         CL_ASSERT( p_comp_item == &p_map->nil );\r
1872         /* Insert the item. */\r
1873         if( p_insert_at == &p_map->root )\r
1874         {\r
1875                 p_insert_at->p_left = p_item;\r
1876                 /*\r
1877                  * Primitive insert places the new item in front of\r
1878                  * the existing item.\r
1879                  */\r
1880                 __cl_primitive_insert( &p_map->nil.pool_item.list_item,\r
1881                         &p_item->pool_item.list_item );\r
1882         }\r
1883         else if( cmp < 0 )\r
1884         {\r
1885                 p_insert_at->p_left = p_item;\r
1886                 /*\r
1887                  * Primitive insert places the new item in front of\r
1888                  * the existing item.\r
1889                  */\r
1890                 __cl_primitive_insert( &p_insert_at->pool_item.list_item,\r
1891                         &p_item->pool_item.list_item );\r
1892         }\r
1893         else\r
1894         {\r
1895                 p_insert_at->p_right = p_item;\r
1896                 /*\r
1897                  * Primitive insert places the new item in front of\r
1898                  * the existing item.\r
1899                  */\r
1900                 __cl_primitive_insert( p_insert_at->pool_item.list_item.p_next,\r
1901                         &p_item->pool_item.list_item );\r
1902         }\r
1903         /* Increase the count. */\r
1904         p_map->count++;\r
1905 \r
1906         p_item->p_up = p_insert_at;\r
1907 \r
1908         /*\r
1909          * We have added depth to this section of the tree.\r
1910          * Rebalance as necessary as we retrace our path through the tree\r
1911          * and update colors.\r
1912          */\r
1913         __cl_fmap_ins_bal( p_map, p_item );\r
1914 \r
1915         __cl_fmap_root( p_map )->color = CL_MAP_BLACK;\r
1916 \r
1917         /*\r
1918          * Note that it is not necessary to re-color the nil node black because all\r
1919          * red color assignments are made via the p_up pointer, and nil is never\r
1920          * set as the value of a p_up pointer.\r
1921          */\r
1922 \r
1923 #ifdef _DEBUG_\r
1924         /* Set the pointer to the map in the map item for consistency checking. */\r
1925         p_item->p_map = p_map;\r
1926 #endif\r
1927 \r
1928         return( p_item );\r
1929 }\r
1930 \r
1931 \r
1932 static void\r
1933 __cl_fmap_del_bal(\r
1934         IN      cl_fmap_t* const        p_map,\r
1935         IN      cl_fmap_item_t*         p_item )\r
1936 {\r
1937         cl_fmap_item_t          *p_uncle;\r
1938 \r
1939         while( (p_item->color != CL_MAP_RED) && (p_item->p_up != &p_map->root) )\r
1940         {\r
1941                 if( __cl_fmap_is_left_child( p_item ) )\r
1942                 {\r
1943                         p_uncle = p_item->p_up->p_right;\r
1944 \r
1945                         if( p_uncle->color == CL_MAP_RED )\r
1946                         {\r
1947                                 p_uncle->color = CL_MAP_BLACK;\r
1948                                 p_item->p_up->color = CL_MAP_RED;\r
1949                                 __cl_fmap_rot_left( p_map, p_item->p_up );\r
1950                                 p_uncle = p_item->p_up->p_right;\r
1951                         }\r
1952 \r
1953                         if( p_uncle->p_right->color != CL_MAP_RED )\r
1954                         {\r
1955                                 if( p_uncle->p_left->color != CL_MAP_RED )\r
1956                                 {\r
1957                                         p_uncle->color = CL_MAP_RED;\r
1958                                         p_item = p_item->p_up;\r
1959                                         continue;\r
1960                                 }\r
1961 \r
1962                                 p_uncle->p_left->color = CL_MAP_BLACK;\r
1963                                 p_uncle->color = CL_MAP_RED;\r
1964                                 __cl_fmap_rot_right( p_map, p_uncle );\r
1965                                 p_uncle = p_item->p_up->p_right;\r
1966                         }\r
1967                         p_uncle->color = p_item->p_up->color;\r
1968                         p_item->p_up->color = CL_MAP_BLACK;\r
1969                         p_uncle->p_right->color = CL_MAP_BLACK;\r
1970                         __cl_fmap_rot_left( p_map, p_item->p_up );\r
1971                         break;\r
1972                 }\r
1973                 else\r
1974                 {\r
1975                         p_uncle = p_item->p_up->p_left;\r
1976 \r
1977                         if( p_uncle->color == CL_MAP_RED )\r
1978                         {\r
1979                                 p_uncle->color = CL_MAP_BLACK;\r
1980                                 p_item->p_up->color = CL_MAP_RED;\r
1981                                 __cl_fmap_rot_right( p_map, p_item->p_up );\r
1982                                 p_uncle = p_item->p_up->p_left;\r
1983                         }\r
1984 \r
1985                         if( p_uncle->p_left->color != CL_MAP_RED )\r
1986                         {\r
1987                                 if( p_uncle->p_right->color != CL_MAP_RED )\r
1988                                 {\r
1989                                         p_uncle->color = CL_MAP_RED;\r
1990                                         p_item = p_item->p_up;\r
1991                                         continue;\r
1992                                 }\r
1993 \r
1994                                 p_uncle->p_right->color = CL_MAP_BLACK;\r
1995                                 p_uncle->color = CL_MAP_RED;\r
1996                                 __cl_fmap_rot_left( p_map, p_uncle );\r
1997                                 p_uncle = p_item->p_up->p_left;\r
1998                         }\r
1999                         p_uncle->color = p_item->p_up->color;\r
2000                         p_item->p_up->color = CL_MAP_BLACK;\r
2001                         p_uncle->p_left->color = CL_MAP_BLACK;\r
2002                         __cl_fmap_rot_right( p_map, p_item->p_up );\r
2003                         break;\r
2004                 }\r
2005         }\r
2006         p_item->color = CL_MAP_BLACK;\r
2007 }\r
2008 \r
2009 \r
2010 void\r
2011 cl_fmap_remove_item(\r
2012         IN      cl_fmap_t* const                p_map,\r
2013         IN      cl_fmap_item_t* const   p_item )\r
2014 {\r
2015         cl_fmap_item_t  *p_child, *p_del_item;\r
2016 \r
2017         CL_ASSERT( p_map );\r
2018         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
2019         CL_ASSERT( p_item );\r
2020         CL_ASSERT( p_item->p_map == p_map );\r
2021 \r
2022         if( p_item == cl_fmap_end( p_map ) )\r
2023                 return;\r
2024 \r
2025         if( (p_item->p_right == &p_map->nil) || (p_item->p_left == &p_map->nil ) )\r
2026         {\r
2027                 /* The item being removed has children on at most on side. */\r
2028                 p_del_item = p_item;\r
2029         }\r
2030         else\r
2031         {\r
2032                 /*\r
2033                  * The item being removed has children on both side.\r
2034                  * We select the item that will replace it.  After removing\r
2035                  * the substitute item and rebalancing, the tree will have the\r
2036                  * correct topology.  Exchanging the substitute for the item\r
2037                  * will finalize the removal.\r
2038                  */\r
2039                 p_del_item = cl_fmap_next( p_item );\r
2040                 CL_ASSERT( p_del_item != &p_map->nil );\r
2041         }\r
2042 \r
2043         /* Remove the item from the list. */\r
2044         __cl_primitive_remove( &p_item->pool_item.list_item );\r
2045         /* Decrement the item count. */\r
2046         p_map->count--;\r
2047 \r
2048         /* Get the pointer to the new root's child, if any. */\r
2049         if( p_del_item->p_left != &p_map->nil )\r
2050                 p_child = p_del_item->p_left;\r
2051         else\r
2052                 p_child = p_del_item->p_right;\r
2053 \r
2054         /*\r
2055          * This assignment may modify the parent pointer of the nil node.\r
2056          * This is inconsequential.\r
2057          */\r
2058         p_child->p_up = p_del_item->p_up;\r
2059         (*__cl_fmap_get_parent_ptr_to_item( p_del_item )) = p_child;\r
2060 \r
2061         if( p_del_item->color != CL_MAP_RED )\r
2062                 __cl_fmap_del_bal( p_map, p_child );\r
2063 \r
2064         /*\r
2065          * Note that the splicing done below does not need to occur before\r
2066          * the tree is balanced, since the actual topology changes are made by the\r
2067          * preceding code.  The topology is preserved by the color assignment made\r
2068          * below (reader should be reminded that p_del_item == p_item in some cases).\r
2069          */\r
2070         if( p_del_item != p_item )\r
2071         {\r
2072                 /*\r
2073                  * Finalize the removal of the specified item by exchanging it with\r
2074                  * the substitute which we removed above.\r
2075                  */\r
2076                 p_del_item->p_up = p_item->p_up;\r
2077                 p_del_item->p_left = p_item->p_left;\r
2078                 p_del_item->p_right = p_item->p_right;\r
2079                 (*__cl_fmap_get_parent_ptr_to_item( p_item )) = p_del_item;\r
2080                 p_item->p_right->p_up = p_del_item;\r
2081                 p_item->p_left->p_up = p_del_item;\r
2082                 p_del_item->color = p_item->color;\r
2083         }\r
2084 \r
2085         CL_ASSERT( p_map->nil.color != CL_MAP_RED );\r
2086 \r
2087 #ifdef _DEBUG_\r
2088         /* Clear the pointer to the map since the item has been removed. */\r
2089         p_item->p_map = NULL;\r
2090 #endif\r
2091 }\r
2092 \r
2093 \r
2094 cl_fmap_item_t*\r
2095 cl_fmap_remove(\r
2096         IN      cl_fmap_t* const        p_map,\r
2097         IN      const void* const       p_key )\r
2098 {\r
2099         cl_fmap_item_t  *p_item;\r
2100 \r
2101         CL_ASSERT( p_map );\r
2102         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
2103 \r
2104         /* Seek the node with the specified key */\r
2105         p_item = cl_fmap_get( p_map, p_key );\r
2106 \r
2107         cl_fmap_remove_item( p_map, p_item );\r
2108 \r
2109         return( p_item );\r
2110 }\r
2111 \r
2112 \r
2113 void\r
2114 cl_fmap_merge(\r
2115         OUT             cl_fmap_t* const        p_dest_map,\r
2116         IN OUT  cl_fmap_t* const        p_src_map )\r
2117 {\r
2118         cl_fmap_item_t          *p_item, *p_item2, *p_next;\r
2119 \r
2120         CL_ASSERT( p_dest_map );\r
2121         CL_ASSERT( p_src_map );\r
2122 \r
2123         p_item = cl_fmap_head( p_src_map );\r
2124 \r
2125         while( p_item != cl_fmap_end( p_src_map ) )\r
2126         {\r
2127                 p_next = cl_fmap_next( p_item );\r
2128 \r
2129                 /* Remove the item from its current map. */\r
2130                 cl_fmap_remove_item( p_src_map, p_item );\r
2131                 /* Insert the item into the destination map. */\r
2132                 p_item2 = cl_fmap_insert( p_dest_map, cl_fmap_key( p_item ), p_item );\r
2133                 /* Check that the item was successfully inserted. */\r
2134                 if( p_item2 != p_item )\r
2135                 {\r
2136                         /* Put the item in back in the source map. */\r
2137                         p_item2 =\r
2138                                 cl_fmap_insert( p_src_map, cl_fmap_key( p_item ), p_item );\r
2139                         CL_ASSERT( p_item2 == p_item );\r
2140                 }\r
2141                 p_item = p_next;\r
2142         }\r
2143 }\r
2144 \r
2145 \r
2146 static void\r
2147 __cl_fmap_delta_move(\r
2148         IN OUT  cl_fmap_t* const                p_dest,\r
2149         IN OUT  cl_fmap_t* const                p_src,\r
2150         IN OUT  cl_fmap_item_t** const  pp_item )\r
2151 {\r
2152         cl_fmap_item_t          *p_temp, *p_next;\r
2153 \r
2154         /*\r
2155          * Get the next item so that we can ensure that pp_item points to\r
2156          * a valid item upon return from the function.\r
2157          */\r
2158         p_next = cl_fmap_next( *pp_item );\r
2159         /* Move the old item from its current map the the old map. */\r
2160         cl_fmap_remove_item( p_src, *pp_item );\r
2161         p_temp = cl_fmap_insert( p_dest, cl_fmap_key( *pp_item ), *pp_item );\r
2162         /* We should never have duplicates. */\r
2163         CL_ASSERT( p_temp == *pp_item );\r
2164         /* Point pp_item to a valid item in the source map. */\r
2165         (*pp_item) = p_next;\r
2166 }\r
2167 \r
2168 \r
2169 void\r
2170 cl_fmap_delta(\r
2171         IN OUT  cl_fmap_t* const        p_map1,\r
2172         IN OUT  cl_fmap_t* const        p_map2,\r
2173         OUT             cl_fmap_t* const        p_new,\r
2174         OUT             cl_fmap_t* const        p_old )\r
2175 {\r
2176         cl_fmap_item_t          *p_item1, *p_item2;\r
2177         intn_t                          cmp;\r
2178 \r
2179         CL_ASSERT( p_map1 );\r
2180         CL_ASSERT( p_map2 );\r
2181         CL_ASSERT( p_new );\r
2182         CL_ASSERT( p_old );\r
2183         CL_ASSERT( cl_is_fmap_empty( p_new ) );\r
2184         CL_ASSERT( cl_is_fmap_empty( p_old ) );\r
2185 \r
2186         p_item1 = cl_fmap_head( p_map1 );\r
2187         p_item2 = cl_fmap_head( p_map2 );\r
2188 \r
2189         while( p_item1 != cl_fmap_end( p_map1 ) &&\r
2190                 p_item2 != cl_fmap_end( p_map2 ) )\r
2191         {\r
2192                 cmp = p_map1->pfn_compare( cl_fmap_key( p_item1 ),\r
2193                         cl_fmap_key( p_item2 ) );\r
2194                 if( cmp < 0 )\r
2195                 {\r
2196                         /* We found an old item. */\r
2197                         __cl_fmap_delta_move( p_old, p_map1, &p_item1 );\r
2198                 }\r
2199                 else if( cmp > 0 )\r
2200                 {\r
2201                         /* We found a new item. */\r
2202                         __cl_fmap_delta_move( p_new, p_map2, &p_item2 );\r
2203                 }\r
2204                 else\r
2205                 {\r
2206                         /* Move both forward since they have the same key. */\r
2207                         p_item1 = cl_fmap_next( p_item1 );\r
2208                         p_item2 = cl_fmap_next( p_item2 );\r
2209                 }\r
2210         }\r
2211 \r
2212         /* Process the remainder if the end of either source map was reached. */\r
2213         while( p_item2 != cl_fmap_end( p_map2 ) )\r
2214                 __cl_fmap_delta_move( p_new, p_map2, &p_item2 );\r
2215 \r
2216         while( p_item1 != cl_fmap_end( p_map1 ) )\r
2217                 __cl_fmap_delta_move( p_old, p_map1, &p_item1 );\r
2218 }\r