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