[DAPL2] sync with WinOF 2.1 branch
[mirror/winof/.git] / inc / complib / cl_fleximap.h
1 /*\r
2  * Copyright (c) 2005 SilverStorm Technologies.  All rights reserved.\r
3  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. \r
4  * Portions Copyright (c) 2008 Microsoft Corporation.  All rights reserved.\r
5  *\r
6  * This software is available to you under the OpenIB.org BSD license\r
7  * below:\r
8  *\r
9  *     Redistribution and use in source and binary forms, with or\r
10  *     without modification, are permitted provided that the following\r
11  *     conditions are met:\r
12  *\r
13  *      - Redistributions of source code must retain the above\r
14  *        copyright notice, this list of conditions and the following\r
15  *        disclaimer.\r
16  *\r
17  *      - Redistributions in binary form must reproduce the above\r
18  *        copyright notice, this list of conditions and the following\r
19  *        disclaimer in the documentation and/or other materials\r
20  *        provided with the distribution.\r
21  *\r
22  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
23  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
24  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
25  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
26  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
27  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
28  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
29  * SOFTWARE.\r
30  *\r
31  * $Id$\r
32  */\r
33 \r
34 \r
35 /*\r
36  * Abstract:\r
37  *      Declaration of flexi 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 #ifndef _CL_FLEXIMAP_H_\r
46 #define _CL_FLEXIMAP_H_\r
47 \r
48 \r
49 #include <complib/cl_qmap.h>\r
50 \r
51 \r
52 /****h* Component Library/Flexi Map\r
53 * NAME\r
54 *       Flexi Map\r
55 *\r
56 * DESCRIPTION\r
57 *       Flexi map implements a binary tree that stores user provided cl_fmap_item_t\r
58 *       structures.  Each item stored in a flexi map has a unique user defined key\r
59 *       (duplicates are not allowed).  Flexi map provides the ability to\r
60 *       efficiently search for an item given a key.  Flexi map allows user defined\r
61 *       keys of any size.  Storage for keys and a comparisson function are provided\r
62 *       by users to allow flexi map to store items with arbitrary key values.\r
63 *\r
64 *       Flexi map does not allocate any memory, and can therefore not fail\r
65 *       any operations due to insufficient memory.  Flexi map can thus be useful\r
66 *       in minimizing the error paths in code.\r
67 *\r
68 *       Flexi map is not thread safe, and users must provide serialization when\r
69 *       adding and removing items from the map.\r
70 *\r
71 *       The flexi map functions operate on a cl_fmap_t structure which should\r
72 *       be treated as opaque and should be manipulated only through the provided\r
73 *       functions.\r
74 *\r
75 * SEE ALSO\r
76 *       Structures:\r
77 *               cl_fmap_t, cl_fmap_item_t\r
78 *\r
79 *       Callbacks:\r
80 *               cl_pfn_fmap_apply_t\r
81 *\r
82 *       Item Manipulation:\r
83 *               cl_fmap_key\r
84 *\r
85 *       Initialization:\r
86 *               cl_fmap_init\r
87 *\r
88 *       Iteration:\r
89 *               cl_fmap_end, cl_fmap_head, cl_fmap_tail, cl_fmap_next, cl_fmap_prev\r
90 *\r
91 *       Manipulation:\r
92 *               cl_fmap_insert, cl_fmap_get, cl_fmap_remove_item, cl_fmap_remove,\r
93 *               cl_fmap_remove_all, cl_fmap_merge, cl_fmap_delta\r
94 *\r
95 *       Search:\r
96 *               cl_fmap_apply_func\r
97 *\r
98 *       Attributes:\r
99 *               cl_fmap_count, cl_is_fmap_empty,\r
100 *********/\r
101 \r
102 \r
103 /****s* Component Library: Flexi Map/cl_fmap_item_t\r
104 * NAME\r
105 *       cl_fmap_item_t\r
106 *\r
107 * DESCRIPTION\r
108 *       The cl_fmap_item_t structure is used by maps to store objects.\r
109 *\r
110 *       The cl_fmap_item_t structure should be treated as opaque and should\r
111 *       be manipulated only through the provided functions.\r
112 *\r
113 * SYNOPSIS\r
114 */\r
115 typedef struct _cl_fmap_item\r
116 {\r
117         /* Must be first to allow casting. */\r
118         cl_pool_item_t                  pool_item;\r
119         struct _cl_fmap_item    *p_left;\r
120         struct _cl_fmap_item    *p_right;\r
121         struct _cl_fmap_item    *p_up;\r
122         cl_map_color_t                  color;\r
123         const void*                             p_key;\r
124 #ifdef _DEBUG_\r
125         struct _cl_fmap                 *p_map;\r
126 #endif\r
127 \r
128 } cl_fmap_item_t;\r
129 /*\r
130 * FIELDS\r
131 *       pool_item\r
132 *               Used to store the item in a doubly linked list, allowing more\r
133 *               efficient map traversal.\r
134 *\r
135 *       p_left\r
136 *               Pointer to the map item that is a child to the left of the node.\r
137 *\r
138 *       p_right\r
139 *               Pointer to the map item that is a child to the right of the node.\r
140 *\r
141 *       p_up\r
142 *               Pointer to the map item that is the parent of the node.\r
143 *\r
144 *       p_nil\r
145 *               Pointer to the map's NIL item, used as a terminator for leaves.\r
146 *               The NIL sentinel is in the cl_fmap_t structure.\r
147 *\r
148 *       color\r
149 *               Indicates whether a node is red or black in the map.\r
150 *\r
151 *       p_key\r
152 *               Pointer to the value that uniquely represents a node in a map.  This\r
153 *               pointer is set by calling cl_fmap_insert and can be retrieved by\r
154 *               calling cl_fmap_key.\r
155 *\r
156 * NOTES\r
157 *       None of the fields of this structure should be manipulated by users, as\r
158 *       they are crititcal to the proper operation of the map in which they\r
159 *       are stored.\r
160 *\r
161 *       To allow storing items in either a quick list, a quick pool, or a flexi\r
162 *       map, the map implementation guarantees that the map item can be safely\r
163 *       cast to a pool item used for storing an object in a quick pool, or cast to\r
164 *       a list item used for storing an object in a quick list.  This removes the\r
165 *       need to embed a flexi map item, a list item, and a pool item in objects\r
166 *       that need to be stored in a quick list, a quick pool, and a flexi map.\r
167 *\r
168 *       The flexi map item is defined to be identical in layout as a map item.\r
169 *\r
170 * SEE ALSO\r
171 *       Flexi Map, cl_fmap_insert, cl_fmap_key, cl_pool_item_t, cl_list_item_t\r
172 *********/\r
173 \r
174 \r
175 /****d* Component Library: Flexi Map/cl_pfn_fmap_cmp_t\r
176 * NAME\r
177 *       cl_pfn_fmap_cmp_t\r
178 *\r
179 * DESCRIPTION\r
180 *       The cl_pfn_fmap_cmp_t function type defines the prototype for functions\r
181 *       used to compare item keys in a flexi map.\r
182 *\r
183 * SYNOPSIS\r
184 */\r
185 typedef intn_t\r
186 (CL_API *cl_pfn_fmap_cmp_t)(\r
187         IN      const void* const               p_key1,\r
188         IN      const void*     const           p_key2 );\r
189 /*\r
190 * PARAMETERS\r
191 *       p_key1\r
192 *               [in] Pointer to the first of two keys to compare.\r
193 *\r
194 *       p_key2\r
195 *               [in] Pointer to the second of two keys to compare.\r
196 *\r
197 * RETURN VALUE\r
198 *       Returns 0 if the keys match.\r
199 *       Returns less than 0 if p_key1 is less than p_key2.\r
200 *       Returns greater than 0 if p_key1 is greater than p_key2.\r
201 *\r
202 * NOTES\r
203 *       This function type is provided as function prototype reference for the\r
204 *       function provided by users as a parameter to the cl_fmap_init function.\r
205 *\r
206 * SEE ALSO\r
207 *       Flexi Map, cl_fmap_init\r
208 *********/\r
209 \r
210 \r
211 /****s* Component Library: Flexi Map/cl_fmap_t\r
212 * NAME\r
213 *       cl_fmap_t\r
214 *\r
215 * DESCRIPTION\r
216 *       Flexi map structure.\r
217 *\r
218 *       The cl_fmap_t structure should be treated as opaque and should\r
219 *       be manipulated only through the provided functions.\r
220 *\r
221 * SYNOPSIS\r
222 */\r
223 typedef struct _cl_fmap\r
224 {\r
225         cl_fmap_item_t          root;\r
226         cl_fmap_item_t          nil;\r
227         cl_state_t                      state;\r
228         size_t                          count;\r
229         cl_pfn_fmap_cmp_t       pfn_compare;\r
230 \r
231 } cl_fmap_t;\r
232 /*\r
233 * PARAMETERS\r
234 *       root\r
235 *               Map item that serves as root of the map.  The root is set up to\r
236 *               always have itself as parent.  The left pointer is set to point to\r
237 *               the item at the root.\r
238 *\r
239 *       nil\r
240 *               Map item that serves as terminator for all leaves, as well as providing\r
241 *               the list item used as quick list for storing map items in a list for\r
242 *               faster traversal.\r
243 *\r
244 *       state\r
245 *               State of the map, used to verify that operations are permitted.\r
246 *\r
247 *       count\r
248 *               Number of items in the map.\r
249 *\r
250 *       pfn_compare\r
251 *               Pointer to a compare function to invoke to compare the keys of\r
252 *               items in the map.\r
253 *\r
254 * SEE ALSO\r
255 *       Flexi Map, cl_pfn_fmap_cmp_t\r
256 *********/\r
257 \r
258 \r
259 /****d* Component Library: Flexi Map/cl_pfn_fmap_apply_t\r
260 * NAME\r
261 *       cl_pfn_fmap_apply_t\r
262 *\r
263 * DESCRIPTION\r
264 *       The cl_pfn_fmap_apply_t function type defines the prototype for functions\r
265 *       used to iterate items in a flexi map.\r
266 *\r
267 * SYNOPSIS\r
268 */\r
269 typedef void\r
270 (CL_API *cl_pfn_fmap_apply_t)(\r
271         IN      cl_fmap_item_t* const   p_map_item,\r
272         IN      void*                                   context );\r
273 /*\r
274 * PARAMETERS\r
275 *       p_map_item\r
276 *               [in] Pointer to a cl_fmap_item_t structure.\r
277 *\r
278 *       context\r
279 *               [in] Value passed to the callback function.\r
280 *\r
281 * RETURN VALUE\r
282 *       This function does not return a value.\r
283 *\r
284 * NOTES\r
285 *       This function type is provided as function prototype reference for the\r
286 *       function provided by users as a parameter to the cl_fmap_apply_func\r
287 *       function.\r
288 *\r
289 * SEE ALSO\r
290 *       Flexi Map, cl_fmap_apply_func\r
291 *********/\r
292 \r
293 \r
294 #ifdef __cplusplus\r
295 extern "C" {\r
296 #endif\r
297 \r
298 \r
299 /****f* Component Library: Flexi Map/cl_fmap_count\r
300 * NAME\r
301 *       cl_fmap_count\r
302 *\r
303 * DESCRIPTION\r
304 *       The cl_fmap_count function returns the number of items stored\r
305 *       in a flexi map.\r
306 *\r
307 * SYNOPSIS\r
308 */\r
309 CL_INLINE size_t CL_API\r
310 cl_fmap_count(\r
311         IN      const cl_fmap_t* const  p_map )\r
312 {\r
313         CL_ASSERT( p_map );\r
314         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
315         return( p_map->count );\r
316 }\r
317 /*\r
318 * PARAMETERS\r
319 *       p_map\r
320 *               [in] Pointer to a cl_fmap_t structure whose item count to return.\r
321 *\r
322 * RETURN VALUE\r
323 *       Returns the number of items stored in the map.\r
324 *\r
325 * SEE ALSO\r
326 *       Flexi Map, cl_is_fmap_empty\r
327 *********/\r
328 \r
329 \r
330 /****f* Component Library: Flexi Map/cl_is_fmap_empty\r
331 * NAME\r
332 *       cl_is_fmap_empty\r
333 *\r
334 * DESCRIPTION\r
335 *       The cl_is_fmap_empty function returns whether a flexi map is empty.\r
336 *\r
337 * SYNOPSIS\r
338 */\r
339 CL_INLINE boolean_t CL_API\r
340 cl_is_fmap_empty(\r
341         IN      const cl_fmap_t* const  p_map )\r
342 {\r
343         CL_ASSERT( p_map );\r
344         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
345 \r
346         return( p_map->count == 0 );\r
347 }\r
348 /*\r
349 * PARAMETERS\r
350 *       p_map\r
351 *               [in] Pointer to a cl_fmap_t structure to test for emptiness.\r
352 *\r
353 * RETURN VALUES\r
354 *       TRUE if the flexi map is empty.\r
355 *\r
356 *       FALSE otherwise.\r
357 *\r
358 * SEE ALSO\r
359 *       Flexi Map, cl_fmap_count, cl_fmap_remove_all\r
360 *********/\r
361 \r
362 \r
363 /****f* Component Library: Flexi Map/cl_fmap_key\r
364 * NAME\r
365 *       cl_fmap_key\r
366 *\r
367 * DESCRIPTION\r
368 *       The cl_fmap_key function retrieves the key value of a map item.\r
369 *\r
370 * SYNOPSIS\r
371 */\r
372 #pragma warning (push)\r
373 #pragma warning (disable :4244)\r
374 CL_INLINE const void* CL_API\r
375 cl_fmap_key(\r
376         IN      const cl_fmap_item_t* const     p_item )\r
377 {\r
378         CL_ASSERT( p_item );\r
379         return( p_item->p_key );\r
380 }\r
381 #pragma warning (pop )\r
382 /*\r
383 * PARAMETERS\r
384 *       p_item\r
385 *               [in] Pointer to a map item whose key value to return.\r
386 *\r
387 * RETURN VALUE\r
388 *       Returns the a pointer to the key value for the specified map item.\r
389 *       The key value should not be modified to insure proper flexi map operation.\r
390 *\r
391 * NOTES\r
392 *       The key value is set in a call to cl_fmap_insert.\r
393 *\r
394 * SEE ALSO\r
395 *       Flexi Map, cl_fmap_insert\r
396 *********/\r
397 \r
398 \r
399 /****f* Component Library: Flexi Map/cl_fmap_init\r
400 * NAME\r
401 *       cl_fmap_init\r
402 *\r
403 * DESCRIPTION\r
404 *       The cl_fmap_init function initialized a flexi map for use.\r
405 *\r
406 * SYNOPSIS\r
407 */\r
408 CL_EXPORT void CL_API\r
409 cl_fmap_init(\r
410         IN      cl_fmap_t* const        p_map,\r
411         IN      cl_pfn_fmap_cmp_t       pfn_compare );\r
412 /*\r
413 * PARAMETERS\r
414 *       p_map\r
415 *               [in] Pointer to a cl_fmap_t structure to initialize.\r
416 *\r
417 *       pfn_compare\r
418 *               [in] Pointer to the compare function used to compare keys.\r
419 *               See the cl_pfn_fmap_cmp_t function type declaration for details\r
420 *               about the callback function.\r
421 *\r
422 * RETURN VALUES\r
423 *       This function does not return a value.\r
424 *\r
425 * NOTES\r
426 *       Allows calling flexi map manipulation functions.\r
427 *\r
428 * SEE ALSO\r
429 *       Flexi Map, cl_fmap_insert, cl_fmap_remove\r
430 *********/\r
431 \r
432 \r
433 /****f* Component Library: Flexi Map/cl_fmap_end\r
434 * NAME\r
435 *       cl_fmap_end\r
436 *\r
437 * DESCRIPTION\r
438 *       The cl_fmap_end function returns the end of a flexi map.\r
439 *\r
440 * SYNOPSIS\r
441 */\r
442 CL_INLINE const cl_fmap_item_t* const CL_API\r
443 cl_fmap_end(\r
444         IN      const cl_fmap_t* const  p_map )\r
445 {\r
446         CL_ASSERT( p_map );\r
447         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
448         /* Nil is the end of the map. */\r
449         return( &p_map->nil );\r
450 }\r
451 /*\r
452 * PARAMETERS\r
453 *       p_map\r
454 *               [in] Pointer to a cl_fmap_t structure whose end to return.\r
455 *\r
456 * RETURN VALUE\r
457 *       Pointer to the end of the map.\r
458 *\r
459 * NOTES\r
460 *       cl_fmap_end is useful for determining the validity of map items returned\r
461 *       by cl_fmap_head, cl_fmap_tail, cl_fmap_next, or cl_fmap_prev.  If the map\r
462 *       item pointer returned by any of these functions compares to the end, the\r
463 *       end of the map was encoutered.\r
464 *       When using cl_fmap_head or cl_fmap_tail, this condition indicates that\r
465 *       the map is empty.\r
466 *\r
467 * SEE ALSO\r
468 *       Flexi Map, cl_fmap_head, cl_fmap_tail, cl_fmap_next, cl_fmap_prev\r
469 *********/\r
470 \r
471 \r
472 /****f* Component Library: Flexi Map/cl_fmap_head\r
473 * NAME\r
474 *       cl_fmap_head\r
475 *\r
476 * DESCRIPTION\r
477 *       The cl_fmap_head function returns the map item with the lowest key\r
478 *       value stored in a flexi map.\r
479 *\r
480 * SYNOPSIS\r
481 */\r
482 CL_INLINE cl_fmap_item_t* CL_API\r
483 cl_fmap_head(\r
484         IN      const cl_fmap_t* const  p_map )\r
485 {\r
486         CL_ASSERT( p_map );\r
487         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
488         return( (cl_fmap_item_t*)p_map->nil.pool_item.list_item.p_next );\r
489 }\r
490 /*\r
491 * PARAMETERS\r
492 *       p_map\r
493 *               [in] Pointer to a cl_fmap_t structure whose item with the lowest key\r
494 *               is returned.\r
495 *\r
496 * RETURN VALUES\r
497 *       Pointer to the map item with the lowest key in the flexi map.\r
498 *\r
499 *       Pointer to the map end if the flexi map was empty.\r
500 *\r
501 * NOTES\r
502 *       cl_fmap_head does not remove the item from the map.\r
503 *\r
504 * SEE ALSO\r
505 *       Flexi Map, cl_fmap_tail, cl_fmap_next, cl_fmap_prev, cl_fmap_end,\r
506 *       cl_fmap_item_t\r
507 *********/\r
508 \r
509 \r
510 /****f* Component Library: Flexi Map/cl_fmap_tail\r
511 * NAME\r
512 *       cl_fmap_tail\r
513 *\r
514 * DESCRIPTION\r
515 *       The cl_fmap_tail function returns the map item with the highest key\r
516 *       value stored in a flexi map.\r
517 *\r
518 * SYNOPSIS\r
519 */\r
520 CL_INLINE cl_fmap_item_t* CL_API\r
521 cl_fmap_tail(\r
522         IN      const cl_fmap_t* const  p_map )\r
523 {\r
524         CL_ASSERT( p_map );\r
525         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
526         return( (cl_fmap_item_t*)p_map->nil.pool_item.list_item.p_prev );\r
527 }\r
528 /*\r
529 * PARAMETERS\r
530 *       p_map\r
531 *               [in] Pointer to a cl_fmap_t structure whose item with the highest key\r
532 *               is returned.\r
533 *\r
534 * RETURN VALUES\r
535 *       Pointer to the map item with the highest key in the flexi map.\r
536 *\r
537 *       Pointer to the map end if the flexi map was empty.\r
538 *\r
539 * NOTES\r
540 *       cl_fmap_end does not remove the item from the map.\r
541 *\r
542 * SEE ALSO\r
543 *       Flexi Map, cl_fmap_head, cl_fmap_next, cl_fmap_prev, cl_fmap_end,\r
544 *       cl_fmap_item_t\r
545 *********/\r
546 \r
547 \r
548 /****f* Component Library: Flexi Map/cl_fmap_next\r
549 * NAME\r
550 *       cl_fmap_next\r
551 *\r
552 * DESCRIPTION\r
553 *       The cl_fmap_next function returns the map item with the next higher\r
554 *       key value than a specified map item.\r
555 *\r
556 * SYNOPSIS\r
557 */\r
558 CL_INLINE cl_fmap_item_t* CL_API\r
559 cl_fmap_next(\r
560         IN      const cl_fmap_item_t* const     p_item )\r
561 {\r
562         CL_ASSERT( p_item );\r
563         return( (cl_fmap_item_t*)p_item->pool_item.list_item.p_next );\r
564 }\r
565 /*\r
566 * PARAMETERS\r
567 *       p_item\r
568 *               [in] Pointer to a map item whose successor to return.\r
569 *\r
570 * RETURN VALUES\r
571 *       Pointer to the map item with the next higher key value in a flexi map.\r
572 *\r
573 *       Pointer to the map end if the specified item was the last item in\r
574 *       the flexi map.\r
575 *\r
576 * SEE ALSO\r
577 *       Flexi Map, cl_fmap_head, cl_fmap_tail, cl_fmap_prev, cl_fmap_end,\r
578 *       cl_fmap_item_t\r
579 *********/\r
580 \r
581 \r
582 /****f* Component Library: Flexi Map/cl_fmap_prev\r
583 * NAME\r
584 *       cl_fmap_prev\r
585 *\r
586 * DESCRIPTION\r
587 *       The cl_fmap_prev function returns the map item with the next lower\r
588 *       key value than a precified map item.\r
589 *\r
590 * SYNOPSIS\r
591 */\r
592 CL_INLINE cl_fmap_item_t* CL_API\r
593 cl_fmap_prev(\r
594         IN      const cl_fmap_item_t* const     p_item )\r
595 {\r
596         CL_ASSERT( p_item );\r
597         return( (cl_fmap_item_t*)p_item->pool_item.list_item.p_prev );\r
598 }\r
599 /*\r
600 * PARAMETERS\r
601 *       p_item\r
602 *               [in] Pointer to a map item whose predecessor to return.\r
603 *\r
604 * RETURN VALUES\r
605 *       Pointer to the map item with the next lower key value in a flexi map.\r
606 *\r
607 *       Pointer to the map end if the specifid item was the first item in\r
608 *       the flexi map.\r
609 *\r
610 * SEE ALSO\r
611 *       Flexi Map, cl_fmap_head, cl_fmap_tail, cl_fmap_next, cl_fmap_end,\r
612 *       cl_fmap_item_t\r
613 *********/\r
614 \r
615 \r
616 /****f* Component Library: Flexi Map/cl_fmap_insert\r
617 * NAME\r
618 *       cl_fmap_insert\r
619 *\r
620 * DESCRIPTION\r
621 *       The cl_fmap_insert function inserts a map item into a flexi map.\r
622 *\r
623 * SYNOPSIS\r
624 */\r
625 CL_EXPORT cl_fmap_item_t* CL_API\r
626 cl_fmap_insert(\r
627         IN      cl_fmap_t* const                p_map,\r
628         IN      const void* const               p_key,\r
629         IN      cl_fmap_item_t* const   p_item );\r
630 /*\r
631 * PARAMETERS\r
632 *       p_map\r
633 *               [in] Pointer to a cl_fmap_t structure into which to add the item.\r
634 *\r
635 *       p_key\r
636 *               [in] Pointer to the key value to assign to the item.  Storage for\r
637 *               the key must be persistant, as only the pointer is stored.  Users\r
638 *               are responsible for maintaining the validity of key pointers while\r
639 *               they are in use.\r
640 *\r
641 *       p_item\r
642 *               [in] Pointer to a cl_fmap_item_t stucture to insert into the flexi map.\r
643 *\r
644 * RETURN VALUE\r
645 *       Pointer to the item in the map with the specified key.  If insertion\r
646 *       was successful, this is the pointer to the item.  If an item with the\r
647 *       specified key already exists in the map, the pointer to that item is\r
648 *       returned.\r
649 *\r
650 * NOTES\r
651 *       Insertion operations may cause the flexi map to rebalance.\r
652 *\r
653 * SEE ALSO\r
654 *       Flexi Map, cl_fmap_remove, cl_fmap_item_t\r
655 *********/\r
656 \r
657 \r
658 /****f* Component Library: Flexi Map/cl_fmap_get\r
659 * NAME\r
660 *       cl_fmap_get\r
661 *\r
662 * DESCRIPTION\r
663 *       The cl_fmap_get function returns the map item associated with a key.\r
664 *\r
665 * SYNOPSIS\r
666 */\r
667 CL_EXPORT cl_fmap_item_t* CL_API\r
668 cl_fmap_get(\r
669         IN      const cl_fmap_t* const  p_map,\r
670         IN      const void* const               p_key );\r
671 /*\r
672 * PARAMETERS\r
673 *       p_map\r
674 *               [in] Pointer to a cl_fmap_t structure from which to retrieve the\r
675 *               item with the specified key.\r
676 *\r
677 *       p_key\r
678 *               [in] Pointer to a key value used to search for the desired map item.\r
679 *\r
680 * RETURN VALUES\r
681 *       Pointer to the map item with the desired key value.\r
682 *\r
683 *       Pointer to the map end if there was no item with the desired key value\r
684 *       stored in the flexi map.\r
685 *\r
686 * NOTES\r
687 *       cl_fmap_get does not remove the item from the flexi map.\r
688 *\r
689 * SEE ALSO\r
690 *       Flexi Map, cl_fmap_remove\r
691 *********/\r
692 \r
693 \r
694 /****f* Component Library: Flexi Map/cl_fmap_remove_item\r
695 * NAME\r
696 *       cl_fmap_remove_item\r
697 *\r
698 * DESCRIPTION\r
699 *       The cl_fmap_remove_item function removes the specified map item\r
700 *       from a flexi map.\r
701 *\r
702 * SYNOPSIS\r
703 */\r
704 CL_EXPORT void CL_API\r
705 cl_fmap_remove_item(\r
706         IN      cl_fmap_t* const                p_map,\r
707         IN      cl_fmap_item_t* const   p_item );\r
708 /*\r
709 * PARAMETERS\r
710 *       p_item\r
711 *               [in] Pointer to a map item to remove from its flexi map.\r
712 *\r
713 * RETURN VALUES\r
714 *       This function does not return a value.\r
715 *\r
716 *       In a debug build, cl_fmap_remove_item asserts that the item being removed\r
717 *       is in the specified map.\r
718 *\r
719 * NOTES\r
720 *       Removes the map item pointed to by p_item from its flexi map.\r
721 *\r
722 * SEE ALSO\r
723 *       Flexi Map, cl_fmap_remove, cl_fmap_remove_all, cl_fmap_insert\r
724 *********/\r
725 \r
726 \r
727 /****f* Component Library: Flexi Map/cl_fmap_remove\r
728 * NAME\r
729 *       cl_fmap_remove\r
730 *\r
731 * DESCRIPTION\r
732 *       The cl_fmap_remove function removes the map item with the specified key\r
733 *       from a flexi map.\r
734 *\r
735 * SYNOPSIS\r
736 */\r
737 CL_EXPORT cl_fmap_item_t* CL_API\r
738 cl_fmap_remove(\r
739         IN      cl_fmap_t* const        p_map,\r
740         IN      const void* const       p_key );\r
741 /*\r
742 * PARAMETERS\r
743 *       p_map\r
744 *               [in] Pointer to a cl_fmap_t structure from which to remove the item\r
745 *               with the specified key.\r
746 *\r
747 *       p_key\r
748 *               [in] Pointer to the key value used to search for the map item\r
749 *               to remove.\r
750 *\r
751 * RETURN VALUES\r
752 *       Pointer to the removed map item if it was found.\r
753 *\r
754 *       Pointer to the map end if no item with the specified key exists in the\r
755 *       flexi map.\r
756 *\r
757 * SEE ALSO\r
758 *       Flexi Map, cl_fmap_remove_item, cl_fmap_remove_all, cl_fmap_insert\r
759 *********/\r
760 \r
761 \r
762 /****f* Component Library: Flexi Map/cl_fmap_remove_all\r
763 * NAME\r
764 *       cl_fmap_remove_all\r
765 *\r
766 * DESCRIPTION\r
767 *       The cl_fmap_remove_all function removes all items in a flexi map,\r
768 *       leaving it empty.\r
769 *\r
770 * SYNOPSIS\r
771 */\r
772 CL_INLINE void CL_API\r
773 cl_fmap_remove_all(\r
774         IN      cl_fmap_t* const        p_map )\r
775 {\r
776         CL_ASSERT( p_map );\r
777         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
778 \r
779         p_map->root.p_left = &p_map->nil;\r
780         p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item;\r
781         p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item;\r
782         p_map->count = 0;\r
783 }\r
784 /*\r
785 * PARAMETERS\r
786 *       p_map\r
787 *               [in] Pointer to a cl_fmap_t structure to empty.\r
788 *\r
789 * RETURN VALUES\r
790 *       This function does not return a value.\r
791 *\r
792 * SEE ALSO\r
793 *       Flexi Map, cl_fmap_remove, cl_fmap_remove_item\r
794 *********/\r
795 \r
796 \r
797 /****f* Component Library: Flexi Map/cl_fmap_merge\r
798 * NAME\r
799 *       cl_fmap_merge\r
800 *\r
801 * DESCRIPTION\r
802 *       The cl_fmap_merge function moves all items from one map to another,\r
803 *       excluding duplicates.\r
804 *\r
805 * SYNOPSIS\r
806 */\r
807 CL_EXPORT void CL_API\r
808 cl_fmap_merge(\r
809         OUT             cl_fmap_t* const        p_dest_map,\r
810         IN OUT  cl_fmap_t* const        p_src_map );\r
811 /*\r
812 * PARAMETERS\r
813 *       p_dest_map\r
814 *               [out] Pointer to a cl_fmap_t structure to which items should be added.\r
815 *\r
816 *       p_src_map\r
817 *               [in/out] Pointer to a cl_fmap_t structure whose items to add\r
818 *               to p_dest_map.\r
819 *\r
820 * RETURN VALUES\r
821 *       This function does not return a value.\r
822 *\r
823 * NOTES\r
824 *       Items are evaluated based on their keys only.\r
825 *\r
826 *       Upon return from cl_fmap_merge, the flexi map referenced by p_src_map\r
827 *       contains all duplicate items.\r
828 *\r
829 * SEE ALSO\r
830 *       Flexi Map, cl_fmap_delta\r
831 *********/\r
832 \r
833 \r
834 /****f* Component Library: Flexi Map/cl_fmap_delta\r
835 * NAME\r
836 *       cl_fmap_delta\r
837 *\r
838 * DESCRIPTION\r
839 *       The cl_fmap_delta function computes the differences between two maps.\r
840 *\r
841 * SYNOPSIS\r
842 */\r
843 CL_EXPORT void CL_API\r
844 cl_fmap_delta(\r
845         IN OUT  cl_fmap_t* const        p_map1,\r
846         IN OUT  cl_fmap_t* const        p_map2,\r
847         OUT             cl_fmap_t* const        p_new,\r
848         OUT             cl_fmap_t* const        p_old );\r
849 /*\r
850 * PARAMETERS\r
851 *       p_map1\r
852 *               [in/out] Pointer to the first of two cl_fmap_t structures whose\r
853 *               differences to compute.\r
854 *\r
855 *       p_map2\r
856 *               [in/out] Pointer to the second of two cl_fmap_t structures whose\r
857 *               differences to compute.\r
858 *\r
859 *       p_new\r
860 *               [out] Pointer to an empty cl_fmap_t structure that contains the items\r
861 *               unique to p_map2 upon return from the function.\r
862 *\r
863 *       p_old\r
864 *               [out] Pointer to an empty cl_fmap_t structure that contains the items\r
865 *               unique to p_map1 upon return from the function.\r
866 *\r
867 * RETURN VALUES\r
868 *       This function does not return a value.\r
869 *\r
870 * NOTES\r
871 *       Items are evaluated based on their keys.  Items that exist in both\r
872 *       p_map1 and p_map2 remain in their respective maps.  Items that\r
873 *       exist only p_map1 are moved to p_old.  Likewise, items that exist only\r
874 *       in p_map2 are moved to p_new.  This function can be usefull in evaluating\r
875 *       changes between two maps.\r
876 *\r
877 *       Both maps pointed to by p_new and p_old must be empty on input.  This\r
878 *       requirement removes the possibility of failures.\r
879 *\r
880 * SEE ALSO\r
881 *       Flexi Map, cl_fmap_merge\r
882 *********/\r
883 \r
884 \r
885 /****f* Component Library: Flexi Map/cl_fmap_apply_func\r
886 * NAME\r
887 *       cl_fmap_apply_func\r
888 *\r
889 * DESCRIPTION\r
890 *       The cl_fmap_apply_func function executes a specified function\r
891 *       for every item stored in a flexi map.\r
892 *\r
893 * SYNOPSIS\r
894 */\r
895 CL_EXPORT void CL_API\r
896 cl_fmap_apply_func(\r
897         IN      const cl_fmap_t* const  p_map,\r
898         IN      cl_pfn_fmap_apply_t             pfn_func,\r
899         IN      const void* const               context );\r
900 /*\r
901 * PARAMETERS\r
902 *       p_map\r
903 *               [in] Pointer to a cl_fmap_t structure.\r
904 *\r
905 *       pfn_func\r
906 *               [in] Function invoked for every item in the flexi map.\r
907 *               See the cl_pfn_fmap_apply_t function type declaration for details\r
908 *               about the callback function.\r
909 *\r
910 *       context\r
911 *               [in] Value to pass to the callback functions to provide context.\r
912 *\r
913 * RETURN VALUE\r
914 *       This function does not return a value.\r
915 *\r
916 * NOTES\r
917 *       The function provided must not perform any map operations, as these\r
918 *       would corrupt the flexi map.\r
919 *\r
920 * SEE ALSO\r
921 *       Flexi Map, cl_pfn_fmap_apply_t\r
922 *********/\r
923 \r
924 #ifdef __cplusplus\r
925 }\r
926 #endif\r
927 \r
928 \r
929 #endif  /* _CL_FLEXIMAP_H_ */\r