1 /*
2 * Copyright (c) 2004, 2005 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 intn_t
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 key
466 * 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_get
623 * NAME
624 * cl_fmap_get
625 *
626 * DESCRIPTION
627 * The cl_fmap_get function returns the map item associated with a key.
628 *
629 * SYNOPSIS
630 */
631 cl_fmap_item_t *cl_fmap_get(IN const cl_fmap_t * const p_map,
632 IN const void *const p_key);
633 /*
634 * PARAMETERS
635 * p_map
636 * [in] Pointer to a cl_fmap_t structure from which to retrieve the
637 * item with the specified key.
638 *
639 * p_key
640 * [in] Pointer to a key value used to search for the desired map item.
641 *
642 * RETURN VALUES
643 * Pointer to the map item with the desired key value.
644 *
645 * Pointer to the map end if there was no item with the desired key value
646 * stored in the flexi map.
647 *
648 * NOTES
649 * cl_fmap_get does not remove the item from the flexi map.
650 *
651 * SEE ALSO
652 * Flexi Map, cl_fmap_remove, cl_fmap_get_next
653 *********/
654
655 /****f* Component Library: Flexi Map/cl_fmap_get_next
656 * NAME
657 * cl_fmap_get_next
658 *
659 * DESCRIPTION
660 * The cl_fmap_get_next function returns the first map item associated with a
661 * key > the key specified.
662 *
663 * SYNOPSIS
664 */
665 cl_fmap_item_t *cl_fmap_get_next(IN const cl_fmap_t * const p_map,
666 IN const void *const p_key);
667 /*
668 * PARAMETERS
669 * p_map
670 * [in] Pointer to a cl_fmap_t structure from which to retrieve the
671 * item with the specified key.
672 *
673 * p_key
674 * [in] Pointer to a key value used to search for the desired map item.
675 *
676 * RETURN VALUES
677 * Pointer to the first map item with a key > the desired key value.
678 *
679 * Pointer to the map end if there was no item with a key > the desired key
680 * value stored in the flexi map.
681 *
682 * NOTES
683 * cl_fmap_get_next does not remove the item from the flexi map.
684 *
685 * SEE ALSO
686 * Flexi Map, cl_fmap_remove, cl_fmap_get
687 *********/
688
689 /****f* Component Library: Flexi Map/cl_fmap_remove_item
690 * NAME
691 * cl_fmap_remove_item
692 *
693 * DESCRIPTION
694 * The cl_fmap_remove_item function removes the specified map item
695 * from a flexi map.
696 *
697 * SYNOPSIS
698 */
699 void
700 cl_fmap_remove_item(IN cl_fmap_t * const p_map,
701 IN cl_fmap_item_t * const p_item);
702 /*
703 * PARAMETERS
704 * p_item
705 * [in] Pointer to a map item to remove from its flexi map.
706 *
707 * RETURN VALUES
708 * This function does not return a value.
709 *
710 * In a debug build, cl_fmap_remove_item asserts that the item being
711 * removed es in the specified map.
712 *
713 * NOTES
714 * Removes the map item pointed to by p_item from its flexi map.
715 *
716 * SEE ALSO
717 * Flexi Map, cl_fmap_remove, cl_fmap_remove_all, cl_fmap_insert
718 *********/
719
720 /****f* Component Library: Flexi Map/cl_fmap_remove
721 * NAME
722 * cl_fmap_remove
723 *
724 * DESCRIPTION
725 * The cl_fmap_remove function removes the map item with the specified key
726 * from a flexi map.
727 *
728 * SYNOPSIS
729 */
730 cl_fmap_item_t *cl_fmap_remove(IN cl_fmap_t * const p_map,
731 IN const void *const p_key);
732 /*
733 * PARAMETERS
734 * p_map
735 * [in] Pointer to a cl_fmap_t structure from which to remove the
736 * item with the specified key.
737 *
738 * p_key
739 * [in] Pointer to the key value used to search for the map item
740 * to remove.
741 *
742 * RETURN VALUES
743 * Pointer to the removed map item if it was found.
744 *
745 * Pointer to the map end if no item with the specified key exists in the
746 * flexi map.
747 *
748 * SEE ALSO
749 * Flexi Map, cl_fmap_remove_item, cl_fmap_remove_all, cl_fmap_insert
750 *********/
751
752 /****f* Component Library: Flexi Map/cl_fmap_remove_all
753 * NAME
754 * cl_fmap_remove_all
755 *
756 * DESCRIPTION
757 * The cl_fmap_remove_all function removes all items in a flexi map,
758 * leaving it empty.
759 *
760 * SYNOPSIS
761 */
cl_fmap_remove_all(IN cl_fmap_t * const p_map)762 static inline void cl_fmap_remove_all(IN cl_fmap_t * const p_map)
763 {
764 CL_ASSERT(p_map);
765 CL_ASSERT(p_map->state == CL_INITIALIZED);
766
767 p_map->root.p_left = &p_map->nil;
768 p_map->nil.pool_item.list_item.p_next = &p_map->nil.pool_item.list_item;
769 p_map->nil.pool_item.list_item.p_prev = &p_map->nil.pool_item.list_item;
770 p_map->count = 0;
771 }
772
773 /*
774 * PARAMETERS
775 * p_map
776 * [in] Pointer to a cl_fmap_t structure to empty.
777 *
778 * RETURN VALUES
779 * This function does not return a value.
780 *
781 * SEE ALSO
782 * Flexi Map, cl_fmap_remove, cl_fmap_remove_item
783 *********/
784
785 /****f* Component Library: Flexi Map/cl_fmap_merge
786 * NAME
787 * cl_fmap_merge
788 *
789 * DESCRIPTION
790 * The cl_fmap_merge function moves all items from one map to another,
791 * excluding duplicates.
792 *
793 * SYNOPSIS
794 */
795 void
796 cl_fmap_merge(OUT cl_fmap_t * const p_dest_map,
797 IN OUT cl_fmap_t * const p_src_map);
798 /*
799 * PARAMETERS
800 * p_dest_map
801 * [out] Pointer to a cl_fmap_t structure to which items should be added.
802 *
803 * p_src_map
804 * [in/out] Pointer to a cl_fmap_t structure whose items to add
805 * to p_dest_map.
806 *
807 * RETURN VALUES
808 * This function does not return a value.
809 *
810 * NOTES
811 * Items are evaluated based on their keys only.
812 *
813 * Upon return from cl_fmap_merge, the flexi map referenced by p_src_map
814 * contains all duplicate items.
815 *
816 * SEE ALSO
817 * Flexi Map, cl_fmap_delta
818 *********/
819
820 /****f* Component Library: Flexi Map/cl_fmap_delta
821 * NAME
822 * cl_fmap_delta
823 *
824 * DESCRIPTION
825 * The cl_fmap_delta function computes the differences between two maps.
826 *
827 * SYNOPSIS
828 */
829 void
830 cl_fmap_delta(IN OUT cl_fmap_t * const p_map1,
831 IN OUT cl_fmap_t * const p_map2,
832 OUT cl_fmap_t * const p_new, OUT cl_fmap_t * const p_old);
833 /*
834 * PARAMETERS
835 * p_map1
836 * [in/out] Pointer to the first of two cl_fmap_t structures whose
837 * differences to compute.
838 *
839 * p_map2
840 * [in/out] Pointer to the second of two cl_fmap_t structures whose
841 * differences to compute.
842 *
843 * p_new
844 * [out] Pointer to an empty cl_fmap_t structure that contains the
845 * items unique to p_map2 upon return from the function.
846 *
847 * p_old
848 * [out] Pointer to an empty cl_fmap_t structure that contains the
849 * items unique to p_map1 upon return from the function.
850 *
851 * RETURN VALUES
852 * This function does not return a value.
853 *
854 * NOTES
855 * Items are evaluated based on their keys. Items that exist in both
856 * p_map1 and p_map2 remain in their respective maps. Items that
857 * exist only p_map1 are moved to p_old. Likewise, items that exist only
858 * in p_map2 are moved to p_new. This function can be useful in evaluating
859 * changes between two maps.
860 *
861 * Both maps pointed to by p_new and p_old must be empty on input. This
862 * requirement removes the possibility of failures.
863 *
864 * SEE ALSO
865 * Flexi Map, cl_fmap_merge
866 *********/
867
868 /****f* Component Library: Flexi Map/cl_fmap_apply_func
869 * NAME
870 * cl_fmap_apply_func
871 *
872 * DESCRIPTION
873 * The cl_fmap_apply_func function executes a specified function
874 * for every item stored in a flexi map.
875 *
876 * SYNOPSIS
877 */
878 void
879 cl_fmap_apply_func(IN const cl_fmap_t * const p_map,
880 IN cl_pfn_fmap_apply_t pfn_func,
881 IN const void *const context);
882 /*
883 * PARAMETERS
884 * p_map
885 * [in] Pointer to a cl_fmap_t structure.
886 *
887 * pfn_func
888 * [in] Function invoked for every item in the flexi map.
889 * See the cl_pfn_fmap_apply_t function type declaration for
890 * details about the callback function.
891 *
892 * context
893 * [in] Value to pass to the callback functions to provide context.
894 *
895 * RETURN VALUE
896 * This function does not return a value.
897 *
898 * NOTES
899 * The function provided must not perform any map operations, as these
900 * would corrupt the flexi map.
901 *
902 * SEE ALSO
903 * Flexi Map, cl_pfn_fmap_apply_t
904 *********/
905
906 END_C_DECLS
907 #endif /* _CL_FLEXIMAP_H_ */
908