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