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