[DAPL2] sync with WinOF 2.1 branch
[mirror/winof/.git] / inc / complib / cl_rbmap.h
1 /*++\r
2 Copyright © InfiniCon Systems, Inc.  All rights reserved.\r
3 \r
4 THIS SOFTWARE IS PROVIDED BY INFINICON SYSTEMS, INC. ("INFINICON") TO EACH\r
5 PERSON OR COMPANY ("RECIPIENT") ON AN "AS IS" BASIS.  ANY EXPRESS OR IMPLIED\r
6 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF\r
7 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
8 IN NO EVENT SHALL INFINICON BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\r
9 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,\r
10 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;\r
11 OR BUSINESS INTERRUPTION) HOWEVER CAUSED OR ON ANY THEORY OF LIABILITY,\r
12 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR\r
13 OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED\r
14 OF THE POSSIBILITY OF SUCH DAMAGE.\r
15 \r
16 Any agreements between InfiniCon and the Recipient shall apply to Recipient's\r
17 use of the Software.\r
18 --*/\r
19 \r
20 \r
21 /*\r
22  * Abstract:\r
23  *      Declaration of primitive red/black map, a red/black tree where the caller\r
24  *      always provides all necessary storage.\r
25  *\r
26  *      This tree implementation exposes functions required for the client to\r
27  *      manually walk the map, allowing clients to implement various methods\r
28  *      of comparisson.\r
29  *\r
30  * Environment:\r
31  *      All\r
32  *\r
33  * $Revision$\r
34  */\r
35 \r
36 \r
37 #ifndef _CL_RBMAP_H_\r
38 #define _CL_RBMAP_H_\r
39 \r
40 \r
41 #include <complib/cl_types.h>\r
42 \r
43 \r
44 /****h* Component Library/RB Map\r
45 * NAME\r
46 *       RB Map\r
47 *\r
48 * DESCRIPTION\r
49 *       RB map implements a binary tree that stores user provided cl_rbmap_item_t\r
50 *       structures.  Each item stored in a RB map has a unique key\r
51 *       (duplicates are not allowed).  RB map provides the ability to\r
52 *       efficiently search for an item given a key.\r
53 *\r
54 *       RB map does not allocate any memory, and can therefore not fail\r
55 *       any operations due to insufficient memory.  RB map can thus be useful\r
56 *       in minimizing the error paths in code.\r
57 *\r
58 *       RB map is not thread safe, and users must provide serialization when\r
59 *       adding and removing items from the map.\r
60 *\r
61 *       The RB map functions operate on a cl_rbmap_t structure which should be\r
62 *       treated as opaque and should be manipulated only through the provided\r
63 *       functions.\r
64 *\r
65 * SEE ALSO\r
66 *       Structures:\r
67 *               cl_rbmap_t, cl_rbmap_item_t\r
68 *\r
69 *       Initialization:\r
70 *               cl_rbmap_init\r
71 *\r
72 *       Iteration:\r
73 *               cl_rbmap_root, cl_rbmap_end, cl_rbmap_left, cl_rbmap_right, cl_rbmap_up\r
74 *\r
75 *       Manipulation:\r
76 *               cl_rbmap_insert, cl_rbmap_get, cl_rbmap_remove_item, cl_rbmap_remove,\r
77 *               cl_rbmap_reset, cl_rbmap_merge, cl_rbmap_delta\r
78 *\r
79 *       Search:\r
80 *               cl_rbmap_apply_func\r
81 *\r
82 *       Attributes:\r
83 *               cl_rbmap_count, cl_is_rbmap_empty,\r
84 *********/\r
85 \r
86 \r
87 /****i* Component Library: RB Map/cl_map_color_t\r
88 * NAME\r
89 *       cl_map_color_t\r
90 *\r
91 * DESCRIPTION\r
92 *       The cl_map_color_t enumerated type is used to note the color of\r
93 *       nodes in a map.\r
94 *\r
95 * SYNOPSIS\r
96 */\r
97 typedef enum _cl_map_color\r
98 {\r
99         CL_MAP_RED,\r
100         CL_MAP_BLACK\r
101 \r
102 } cl_map_color_t;\r
103 /*\r
104 * VALUES\r
105 *       CL_MAP_RED\r
106 *               The node in the map is red.\r
107 *\r
108 *       CL_MAP_BLACK\r
109 *               The node in the map is black.\r
110 *\r
111 * SEE ALSO\r
112 *       RB Map, cl_rbmap_item_t\r
113 *********/\r
114 \r
115 \r
116 /****s* Component Library: RB Map/cl_rbmap_item_t\r
117 * NAME\r
118 *       cl_rbmap_item_t\r
119 *\r
120 * DESCRIPTION\r
121 *       The cl_rbmap_item_t structure is used by maps to store objects.\r
122 *\r
123 *       The cl_rbmap_item_t structure should be treated as opaque and should\r
124 *       be manipulated only through the provided functions.\r
125 *\r
126 * SYNOPSIS\r
127 */\r
128 typedef struct _cl_rbmap_item\r
129 {\r
130         struct _cl_rbmap_item           *p_left;\r
131         struct _cl_rbmap_item           *p_right;\r
132         struct _cl_rbmap_item           *p_up;\r
133         cl_map_color_t                          color;\r
134 #ifdef _DEBUG_\r
135         struct _cl_rbmap                        *p_map;\r
136 #endif\r
137 \r
138 } cl_rbmap_item_t;\r
139 /*\r
140 * FIELDS\r
141 *       p_left\r
142 *               Pointer to the map item that is a child to the left of the node.\r
143 *\r
144 *       p_right\r
145 *               Pointer to the map item that is a child to the right of the node.\r
146 *\r
147 *       p_up\r
148 *               Pointer to the map item that is the parent of the node.\r
149 *\r
150 *       color\r
151 *               Indicates whether a node is red or black in the map.\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 RB map.\r
164 *\r
165 * SEE ALSO\r
166 *       RB Map, cl_rbmap_insert, cl_rbmap_key, cl_pool_item_t, cl_list_item_t\r
167 *********/\r
168 \r
169 \r
170 /****s* Component Library: RB Map/cl_rbmap_t\r
171 * NAME\r
172 *       cl_rbmap_t\r
173 *\r
174 * DESCRIPTION\r
175 *       Quick map structure.\r
176 *\r
177 *       The cl_rbmap_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_rbmap\r
183 {\r
184         cl_rbmap_item_t root;\r
185         cl_rbmap_item_t nil;\r
186         cl_state_t              state;\r
187         size_t                  count;\r
188 \r
189 } cl_rbmap_t;\r
190 /*\r
191 * PARAMETERS\r
192 *       root\r
193 *               Map item that serves as root of the map.  The root is set up to\r
194 *               always have itself as parent.  The left pointer is set to point to\r
195 *               the item at the root.\r
196 *\r
197 *       nil\r
198 *               Map item that serves as terminator for all leaves, as well as providing\r
199 *               the list item used as quick list for storing map items in a list for\r
200 *               faster traversal.\r
201 *\r
202 *       state\r
203 *               State of the map, used to verify that operations are permitted.\r
204 *\r
205 *       count\r
206 *               Number of items in the map.\r
207 *\r
208 * SEE ALSO\r
209 *       RB Map\r
210 *********/\r
211 \r
212 \r
213 #ifdef __cplusplus\r
214 extern "C" {\r
215 #endif\r
216 \r
217 \r
218 /****f* Component Library: RB Map/cl_rbmap_count\r
219 * NAME\r
220 *       cl_rbmap_count\r
221 *\r
222 * DESCRIPTION\r
223 *       The cl_rbmap_count function returns the number of items stored\r
224 *       in a RB map.\r
225 *\r
226 * SYNOPSIS\r
227 */\r
228 CL_INLINE size_t CL_API\r
229 cl_rbmap_count(\r
230         IN      const cl_rbmap_t* const p_map )\r
231 {\r
232         CL_ASSERT( p_map );\r
233         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
234         return( p_map->count );\r
235 }\r
236 /*\r
237 * PARAMETERS\r
238 *       p_map\r
239 *               [in] Pointer to a cl_rbmap_t structure whose item count to return.\r
240 *\r
241 * RETURN VALUE\r
242 *       Returns the number of items stored in the map.\r
243 *\r
244 * SEE ALSO\r
245 *       RB Map, cl_is_rbmap_empty\r
246 *********/\r
247 \r
248 \r
249 /****f* Component Library: RB Map/cl_is_rbmap_empty\r
250 * NAME\r
251 *       cl_is_rbmap_empty\r
252 *\r
253 * DESCRIPTION\r
254 *       The cl_is_rbmap_empty function returns whether a RB map is empty.\r
255 *\r
256 * SYNOPSIS\r
257 */\r
258 CL_INLINE boolean_t CL_API\r
259 cl_is_rbmap_empty(\r
260         IN      const cl_rbmap_t* const p_map )\r
261 {\r
262         CL_ASSERT( p_map );\r
263         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
264 \r
265         return( p_map->count == 0 );\r
266 }\r
267 /*\r
268 * PARAMETERS\r
269 *       p_map\r
270 *               [in] Pointer to a cl_rbmap_t structure to test for emptiness.\r
271 *\r
272 * RETURN VALUES\r
273 *       TRUE if the RB map is empty.\r
274 *\r
275 *       FALSE otherwise.\r
276 *\r
277 * SEE ALSO\r
278 *       RB Map, cl_rbmap_count, cl_rbmap_reset\r
279 *********/\r
280 \r
281 \r
282 /****f* Component Library: RB Map/cl_rbmap_reset\r
283 * NAME\r
284 *       cl_rbmap_reset\r
285 *\r
286 * DESCRIPTION\r
287 *       The cl_rbmap_reset function removes all items in a RB map,\r
288 *       leaving it empty.\r
289 *\r
290 * SYNOPSIS\r
291 */\r
292 CL_INLINE void CL_API\r
293 cl_rbmap_reset(\r
294         IN      cl_rbmap_t* const       p_map )\r
295 {\r
296         CL_ASSERT( p_map );\r
297         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
298 \r
299         p_map->root.p_left = &p_map->nil;\r
300         p_map->count = 0;\r
301 }\r
302 /*\r
303 * PARAMETERS\r
304 *       p_map\r
305 *               [in] Pointer to a cl_rbmap_t structure to empty.\r
306 *\r
307 * RETURN VALUES\r
308 *       This function does not return a value.\r
309 *\r
310 * SEE ALSO\r
311 *       RB Map, cl_rbmap_remove, cl_rbmap_remove_item\r
312 *********/\r
313 \r
314 \r
315 /****f* Component Library: RB Map/cl_rbmap_init\r
316 * NAME\r
317 *       cl_rbmap_init\r
318 *\r
319 * DESCRIPTION\r
320 *       The cl_rbmap_init function initialized a RB map for use.\r
321 *\r
322 * SYNOPSIS\r
323 */\r
324 CL_INLINE void CL_API\r
325 cl_rbmap_init(\r
326         IN      cl_rbmap_t* const       p_map )\r
327 {\r
328         CL_ASSERT( p_map );\r
329 \r
330         /* special setup for the root node */\r
331         p_map->root.p_left = &p_map->nil;\r
332         p_map->root.p_right = &p_map->nil;\r
333         p_map->root.p_up = &p_map->root;\r
334         p_map->root.color = CL_MAP_BLACK;\r
335 \r
336         /* Setup the node used as terminator for all leaves. */\r
337         p_map->nil.p_left = &p_map->nil;\r
338         p_map->nil.p_right = &p_map->nil;\r
339         p_map->nil.p_up = &p_map->nil;\r
340         p_map->nil.color = CL_MAP_BLACK;\r
341 \r
342 #ifdef _DEBUG_\r
343         p_map->root.p_map = p_map;\r
344         p_map->nil.p_map = p_map;\r
345 #endif\r
346 \r
347         p_map->state = CL_INITIALIZED;\r
348 \r
349         p_map->count = 0;\r
350 }\r
351 /*\r
352 * PARAMETERS\r
353 *       p_map\r
354 *               [in] Pointer to a cl_rbmap_t structure to initialize.\r
355 *\r
356 * RETURN VALUES\r
357 *       This function does not return a value.\r
358 *\r
359 * NOTES\r
360 *       Allows calling RB map manipulation functions.\r
361 *\r
362 * SEE ALSO\r
363 *       RB Map, cl_rbmap_insert, cl_rbmap_remove\r
364 *********/\r
365 \r
366 \r
367 /****f* Component Library: RB Map/cl_rbmap_root\r
368 * NAME\r
369 *       cl_rbmap_root\r
370 *\r
371 * DESCRIPTION\r
372 *       The cl_rbmap_root function returns the root of a RB map.\r
373 *\r
374 * SYNOPSIS\r
375 */\r
376 CL_INLINE cl_rbmap_item_t* const CL_API\r
377 cl_rbmap_root(\r
378         IN      const cl_rbmap_t* const p_map )\r
379 {\r
380         CL_ASSERT( p_map );\r
381         return( p_map->root.p_left );\r
382 }\r
383 /*\r
384 * PARAMETERS\r
385 *       p_map\r
386 *               [in] Pointer to a cl_rbmap_t structure whose root to return.\r
387 *\r
388 * RETURN VALUE\r
389 *       Pointer to the end of the map.\r
390 *\r
391 * NOTES\r
392 *       cl_rbmap_end is useful for determining the validity of map items returned\r
393 *       by cl_rbmap_head, cl_rbmap_tail, cl_rbmap_next, or cl_rbmap_prev.  If the map\r
394 *       item pointer returned by any of these functions compares to the end, the\r
395 *       end of the map was encoutered.\r
396 *       When using cl_rbmap_head or cl_rbmap_tail, this condition indicates that\r
397 *       the map is empty.\r
398 *\r
399 * SEE ALSO\r
400 *       RB Map, cl_rbmap_head, cl_rbmap_tail, cl_rbmap_next, cl_rbmap_prev,\r
401 *       cl_rbmap_end, cl_rbmap_left, cl_rbmap_right, cl_rbmap_up\r
402 *********/\r
403 \r
404 \r
405 /****f* Component Library: RB Map/cl_rbmap_end\r
406 * NAME\r
407 *       cl_rbmap_end\r
408 *\r
409 * DESCRIPTION\r
410 *       The cl_rbmap_end function returns the end of a RB map.\r
411 *\r
412 * SYNOPSIS\r
413 */\r
414 CL_INLINE const cl_rbmap_item_t* const CL_API\r
415 cl_rbmap_end(\r
416         IN      const cl_rbmap_t* const p_map )\r
417 {\r
418         CL_ASSERT( p_map );\r
419         CL_ASSERT( p_map->state == CL_INITIALIZED );\r
420         /* Nil is the end of the map. */\r
421         return( &p_map->nil );\r
422 }\r
423 /*\r
424 * PARAMETERS\r
425 *       p_map\r
426 *               [in] Pointer to a cl_rbmap_t structure whose end to return.\r
427 *\r
428 * RETURN VALUE\r
429 *       Pointer to the end of the map.\r
430 *\r
431 * NOTES\r
432 *       cl_rbmap_end is useful for determining the validity of map items returned\r
433 *       by cl_rbmap_head, cl_rbmap_tail, cl_rbmap_next, or cl_rbmap_prev.  If the map\r
434 *       item pointer returned by any of these functions compares to the end, the\r
435 *       end of the map was encoutered.\r
436 *       When using cl_rbmap_head or cl_rbmap_tail, this condition indicates that\r
437 *       the map is empty.\r
438 *\r
439 * SEE ALSO\r
440 *       RB Map, cl_rbmap_head, cl_rbmap_tail, cl_rbmap_next, cl_rbmap_prev\r
441 *       cl_rbmap_root, cl_rbmap_left, cl_rbmap_right, cl_rbmap_up\r
442 *********/\r
443 \r
444 \r
445 /****f* Component Library: RB Map/cl_rbmap_left\r
446 * NAME\r
447 *       cl_rbmap_left\r
448 *\r
449 * DESCRIPTION\r
450 *       The cl_rbmap_left function returns the map item to the left\r
451 *       of the specified map item.\r
452 *\r
453 * SYNOPSIS\r
454 */\r
455 CL_INLINE cl_rbmap_item_t* CL_API\r
456 cl_rbmap_left(\r
457         IN      const cl_rbmap_item_t* const    p_item )\r
458 {\r
459         CL_ASSERT( p_item );\r
460         return( (cl_rbmap_item_t*)p_item->p_left );\r
461 }\r
462 /*\r
463 * PARAMETERS\r
464 *       p_item\r
465 *               [in] Pointer to a map item whose predecessor to return.\r
466 *\r
467 * RETURN VALUES\r
468 *       Pointer to the map item to the left in a RB map.\r
469 *\r
470 *       Pointer to the map end if no item is to the left.\r
471 *\r
472 * SEE ALSO\r
473 *       RB Map, cl_rbmap_head, cl_rbmap_tail, cl_rbmap_next, cl_rbmap_end,\r
474 *       cl_rbmap_item_t\r
475 *********/\r
476 \r
477 \r
478 /****f* Component Library: RB Map/cl_rbmap_right\r
479 * NAME\r
480 *       cl_rbmap_right\r
481 *\r
482 * DESCRIPTION\r
483 *       The cl_rbmap_right function returns the map item to the right\r
484 *       of the specified map item.\r
485 *\r
486 * SYNOPSIS\r
487 */\r
488 CL_INLINE cl_rbmap_item_t* CL_API\r
489 cl_rbmap_right(\r
490         IN      const cl_rbmap_item_t* const    p_item )\r
491 {\r
492         CL_ASSERT( p_item );\r
493         return( (cl_rbmap_item_t*)p_item->p_right );\r
494 }\r
495 /*\r
496 * PARAMETERS\r
497 *       p_item\r
498 *               [in] Pointer to a map item whose predecessor to return.\r
499 *\r
500 * RETURN VALUES\r
501 *       Pointer to the map item to the right in a RB map.\r
502 *\r
503 *       Pointer to the map end if no item is to the right.\r
504 *\r
505 * SEE ALSO\r
506 *       RB Map, cl_rbmap_head, cl_rbmap_tail, cl_rbmap_next, cl_rbmap_end,\r
507 *       cl_rbmap_item_t\r
508 *********/\r
509 \r
510 \r
511 /****f* Component Library: RB Map/cl_rbmap_insert\r
512 * NAME\r
513 *       cl_rbmap_insert\r
514 *\r
515 * DESCRIPTION\r
516 *       The cl_rbmap_insert function inserts a map item into a RB map.\r
517 *\r
518 * SYNOPSIS\r
519 */\r
520 CL_EXPORT void CL_API\r
521 cl_rbmap_insert(\r
522         IN      cl_rbmap_t* const               p_map,\r
523         IN      cl_rbmap_item_t* const  p_insert_at,\r
524         IN      cl_rbmap_item_t* const  p_item,\r
525         IN      boolean_t                               left );\r
526 /*\r
527 * PARAMETERS\r
528 *       p_map\r
529 *               [in] Pointer to a cl_rbmap_t structure into which to add the item.\r
530 *\r
531 *       p_insert_at\r
532 *               [in] Pointer to a cl_rbmap_item_t structure to serve as parent\r
533 *               to p_item.\r
534 *\r
535 *       p_item\r
536 *               [in] Pointer to a cl_rbmap_item_t stucture to insert into the RB map.\r
537 *\r
538 *       left\r
539 *               [in] Indicates that p_item should be inserted to the left of p_insert_at.\r
540 *\r
541 * RETURN VALUE\r
542 *       Pointer to the item in the map with the specified key.  If insertion\r
543 *       was successful, this is the pointer to the item.  If an item with the\r
544 *       specified key already exists in the map, the pointer to that item is\r
545 *       returned.\r
546 *\r
547 * NOTES\r
548 *       Insertion operations may cause the RB map to rebalance.\r
549 *\r
550 * SEE ALSO\r
551 *       RB Map, cl_rbmap_remove, cl_rbmap_item_t\r
552 *********/\r
553 \r
554 \r
555 /****f* Component Library: RB Map/cl_rbmap_remove_item\r
556 * NAME\r
557 *       cl_rbmap_remove_item\r
558 *\r
559 * DESCRIPTION\r
560 *       The cl_rbmap_remove_item function removes the specified map item\r
561 *       from a RB map.\r
562 *\r
563 * SYNOPSIS\r
564 */\r
565 CL_EXPORT void CL_API\r
566 cl_rbmap_remove_item(\r
567         IN      cl_rbmap_t* const               p_map,\r
568         IN      cl_rbmap_item_t* const  p_item );\r
569 /*\r
570 * PARAMETERS\r
571 *       p_item\r
572 *               [in] Pointer to a map item to remove from its RB map.\r
573 *\r
574 * RETURN VALUES\r
575 *       This function does not return a value.\r
576 *\r
577 *       In a debug build, cl_rbmap_remove_item asserts that the item being removed\r
578 *       is in the specified map.\r
579 *\r
580 * NOTES\r
581 *       Removes the map item pointed to by p_item from its RB map.\r
582 *\r
583 * SEE ALSO\r
584 *       RB Map, cl_rbmap_remove, cl_rbmap_reset, cl_rbmap_insert\r
585 *********/\r
586 \r
587 \r
588 #ifdef __cplusplus\r
589 }\r
590 #endif\r
591 \r
592 \r
593 #endif  /* _CL_RBMAP_H_ */\r