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