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