TABLE OF CONTENTS

1. Component Library/Quick Map
2. Component Library: Quick Map/cl_is_qmap_empty
3. Component Library: Quick Map/cl_map_item_t
4. Component Library: Quick Map/cl_map_obj_t
5. Component Library: Quick Map/cl_pfn_qmap_apply_t
6. Component Library: Quick Map/cl_qmap_apply_func
7. Component Library: Quick Map/cl_qmap_count
8. Component Library: Quick Map/cl_qmap_delta
9. Component Library: Quick Map/cl_qmap_end
10. Component Library: Quick Map/cl_qmap_get
11. Component Library: Quick Map/cl_qmap_head
12. Component Library: Quick Map/cl_qmap_init
13. Component Library: Quick Map/cl_qmap_insert
14. Component Library: Quick Map/cl_qmap_key
15. Component Library: Quick Map/cl_qmap_merge
16. Component Library: Quick Map/cl_qmap_next
17. Component Library: Quick Map/cl_qmap_obj
18. Component Library: Quick Map/cl_qmap_prev
19. Component Library: Quick Map/cl_qmap_remove
20. Component Library: Quick Map/cl_qmap_remove_all
21. Component Library: Quick Map/cl_qmap_remove_item
22. Component Library: Quick Map/cl_qmap_set_obj
23. Component Library: Quick Map/cl_qmap_t
24. Component Library: Quick Map/cl_qmap_tail

Component Library/Quick Map

    Quick Map

    Quick map implements a binary tree that stores user provided cl_map_item_t
    structures.  Each item stored in a quick map has a unique 64-bit key
    (duplicates are not allowed).  Quick map provides the ability to
    efficiently search for an item given a key.

    Quick map does not allocate any memory, and can therefore not fail
    any operations due to insufficient memory.  Quick map can thus be useful
    in minimizing the error paths in code.

    Quick map is not thread safe, and users must provide serialization when
    adding and removing items from the map.

    The quick map functions operate on a cl_qmap_t structure which should be 
    treated as opaque and should be manipulated only through the provided 
    functions.

    Structures:
        cl_qmap_t, cl_map_item_t, cl_map_obj_t

    Callbacks:
        cl_pfn_qmap_apply_t

    Item Manipulation:
        cl_qmap_set_obj, cl_qmap_obj, cl_qmap_key

    Initialization:
        cl_qmap_init

    Iteration:
        cl_qmap_end, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev

    Manipulation:
        cl_qmap_insert, cl_qmap_get, cl_qmap_remove_item, cl_qmap_remove, 
        cl_qmap_remove_all, cl_qmap_merge, cl_qmap_delta

    Search:
        cl_qmap_apply_func

    Attributes:
        cl_qmap_count, cl_is_qmap_empty, 

Component Library: Quick Map/cl_is_qmap_empty

    cl_is_qmap_empty

    The cl_is_qmap_empty function returns whether a quick map is empty.

 boolean_t
cl_is_qmap_empty(
    IN  const cl_qmap_t* const  p_map ;

    p_map
        [in] Pointer to a cl_qmap_t structure to test for emptiness.

    TRUE if the quick map is empty.

    FALSE otherwise.

    Quick Map, cl_qmap_count, cl_qmap_remove_all

Component Library: Quick Map/cl_map_item_t

    cl_map_item_t

    The cl_map_item_t structure is used by maps to store objects.

    The cl_map_item_t structure should be treated as opaque and should
    be manipulated only through the provided functions.

typedef struct _cl_map_item
{
    /* Must be first to allow casting. */
    cl_pool_item_t          pool_item;
    struct _cl_map_item     *p_left;
    struct _cl_map_item     *p_right;
    struct _cl_map_item     *p_up;
    cl_map_color_t          color;
    uint64_t                key;
#ifdef _DEBUG_
    struct _cl_qmap         *p_map;
#endif

} cl_map_item_t;

    pool_item
        Used to store the item in a doubly linked list, allowing more
        efficient map traversal.

    p_left
        Pointer to the map item that is a child to the left of the node.

    p_right
        Pointer to the map item that is a child to the right of the node.

    p_up
        Pointer to the map item that is the parent of the node.

    p_nil
        Pointer to the map's NIL item, used as a terminator for leaves.
        The NIL sentinel is in the cl_qmap_t structure.

    color
        Indicates whether a node is red or black in the map.

    key
        Value that uniquely represents a node in a map.  This value is set by
        calling cl_qmap_insert and can be retrieved by calling cl_qmap_key.

    None of the fields of this structure should be manipulated by users, as
    they are crititcal to the proper operation of the map in which they
    are stored.

    To allow storing items in either a quick list, a quick pool, or a quick
    map, the map implementation guarantees that the map item can be safely
    cast to a pool item used for storing an object in a quick pool, or cast to
    a list item used for storing an object in a quick list.  This removes the
    need to embed a map item, a list item, and a pool item in objects that need
    to be stored in a quick list, a quick pool, and a quick map.

    Quick Map, cl_qmap_insert, cl_qmap_key, cl_pool_item_t, cl_list_item_t

Component Library: Quick Map/cl_map_obj_t

    cl_map_obj_t

    The cl_map_obj_t structure is used to store objects in maps.

    The cl_map_obj_t structure should be treated as opaque and should
    be manipulated only through the provided functions.

typedef struct _cl_map_obj
{
    cl_map_item_t           item;
    const void              *p_object;

} cl_map_obj_t;

    item
        Map item used by internally by the map to store an object.

    p_object
        User defined context. Users should not access this field directly.
        Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the value
        of this field.

    None of the fields of this structure should be manipulated by users, as
    they are crititcal to the proper operation of the map in which they
    are stored.

    Use cl_qmap_set_obj and cl_qmap_obj to set and retrieve the object
    stored in a map item, respectively.

    Quick Map, cl_qmap_set_obj, cl_qmap_obj, cl_map_item_t

Component Library: Quick Map/cl_pfn_qmap_apply_t

    cl_pfn_qmap_apply_t

    The cl_pfn_qmap_apply_t function type defines the prototype for functions
    used to iterate items in a quick map.

typedef void
(*cl_pfn_qmap_apply_t)(
    IN  cl_map_item_t* const    p_map_item,
    IN  void*                   context );

    p_map_item
        [in] Pointer to a cl_map_item_t structure.

    context
        [in] Value passed to the callback function.

    This function does not return a value.

    This function type is provided as function prototype reference for the
    function provided by users as a parameter to the cl_qmap_apply_func
    function.

    Quick Map, cl_qmap_apply_func

Component Library: Quick Map/cl_qmap_apply_func

    cl_qmap_apply_func

    The cl_qmap_apply_func function executes a specified function
    for every item stored in a quick map.

void
cl_qmap_apply_func(
    IN  const cl_qmap_t* const  p_map,
    IN  cl_pfn_qmap_apply_t     pfn_func,
    IN  const void* const       context );

    p_map
        [in] Pointer to a cl_qmap_t structure.

    pfn_func
        [in] Function invoked for every item in the quick map.
        See the cl_pfn_qmap_apply_t function type declaration for details
        about the callback function.

    context
        [in] Value to pass to the callback functions to provide context.

    This function does not return a value.

    The function provided must not perform any map operations, as these
    would corrupt the quick map.

    Quick Map, cl_pfn_qmap_apply_t

Component Library: Quick Map/cl_qmap_count

    cl_qmap_count

    The cl_qmap_count function returns the number of items stored
    in a quick map.

 size_t
cl_qmap_count(
    IN  const cl_qmap_t* const  p_map ;

    p_map
        [in] Pointer to a cl_qmap_t structure whose item count to return.

    Returns the number of items stored in the map.

    Quick Map, cl_is_qmap_empty

Component Library: Quick Map/cl_qmap_delta

    cl_qmap_delta

    The cl_qmap_delta function computes the differences between two maps.

void
cl_qmap_delta(
    IN OUT  cl_qmap_t* const    p_map1,
    IN OUT  cl_qmap_t* const    p_map2,
    OUT     cl_qmap_t* const    p_new,
    OUT     cl_qmap_t* const    p_old );

    p_map1
        [in/out] Pointer to the first of two cl_qmap_t structures whose 
        differences to compute.

    p_map2
        [in/out] Pointer to the second of two cl_qmap_t structures whose 
        differences to compute.

    p_new
        [out] Pointer to an empty cl_qmap_t structure that contains the items
        unique to p_map2 upon return from the function.

    p_old
        [out] Pointer to an empty cl_qmap_t structure that contains the items 
        unique to p_map1 upon return from the function.

    This function does not return a value.

    Items are evaluated based on their keys.  Items that exist in both
    p_map1 and p_map2 remain in their respective maps.  Items that
    exist only p_map1 are moved to p_old.  Likewise, items that exist only
    in p_map2 are moved to p_new.  This function can be usefull in evaluating
    changes between two maps.

    Both maps pointed to by p_new and p_old must be empty on input.  This 
    requirement removes the possibility of failures.

    Quick Map, cl_qmap_merge

Component Library: Quick Map/cl_qmap_end

    cl_qmap_end

    The cl_qmap_end function returns the end of a quick map.

 const cl_map_item_t* const
cl_qmap_end(
    IN  const cl_qmap_t* const  p_map ;

    p_map
        [in] Pointer to a cl_qmap_t structure whose end to return.

    Pointer to the end of the map.

    cl_qmap_end is useful for determining the validity of map items returned
    by cl_qmap_head, cl_qmap_tail, cl_qmap_next, or cl_qmap_prev.  If the map
    item pointer returned by any of these functions compares to the end, the
    end of the map was encoutered.
    When using cl_qmap_head or cl_qmap_tail, this condition indicates that
    the map is empty.

    Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_prev

Component Library: Quick Map/cl_qmap_get

    cl_qmap_get

    The cl_qmap_get function returns the map item associated with a key.

cl_map_item_t*
cl_qmap_get(
    IN  const cl_qmap_t* const  p_map,
    IN  const uint64_t          key );

    p_map
        [in] Pointer to a cl_qmap_t structure from which to retrieve the
        item with the specified key.

    key
        [in] Key value used to search for the desired map item.

    Pointer to the map item with the desired key value.

    Pointer to the map end if there was no item with the desired key value
    stored in the quick map.

    cl_qmap_get does not remove the item from the quick map.

    Quick Map, cl_qmap_remove

Component Library: Quick Map/cl_qmap_head

    cl_qmap_head

    The cl_qmap_head function returns the map item with the lowest key
    value stored in a quick map.

 cl_map_item_t*
cl_qmap_head(
    IN  const cl_qmap_t* const  p_map ;

    p_map
        [in] Pointer to a cl_qmap_t structure whose item with the lowest key
        is returned.

    Pointer to the map item with the lowest key in the quick map.

    Pointer to the map end if the quick map was empty.

    cl_qmap_head does not remove the item from the map.

    Quick Map, cl_qmap_tail, cl_qmap_next, cl_qmap_prev, cl_qmap_end,
    cl_qmap_item_t

Component Library: Quick Map/cl_qmap_init

    cl_qmap_init

    The cl_qmap_init function initialized a quick map for use.

void
cl_qmap_init(
    IN  cl_qmap_t* const    p_map );

    p_map
        [in] Pointer to a cl_qmap_t structure to initialize.

    This function does not return a value.

    Allows calling quick map manipulation functions.

    Quick Map, cl_qmap_insert, cl_qmap_remove

Component Library: Quick Map/cl_qmap_insert

    cl_qmap_insert

    The cl_qmap_insert function inserts a map item into a quick map.

cl_map_item_t*
cl_qmap_insert(
    IN  cl_qmap_t* const        p_map,
    IN  const uint64_t          key,
    IN  cl_map_item_t* const    p_item );

    p_map
        [in] Pointer to a cl_qmap_t structure into which to add the item.

    key
        [in] Value to assign to the item.

    p_item
        [in] Pointer to a cl_map_item_t stucture to insert into the quick map.

    Pointer to the item in the map with the specified key.  If insertion
    was successful, this is the pointer to the item.  If an item with the
    specified key already exists in the map, the pointer to that item is
    returned.

    Insertion operations may cause the quick map to rebalance.

    Quick Map, cl_qmap_remove, cl_map_item_t

Component Library: Quick Map/cl_qmap_key

    cl_qmap_key

    The cl_qmap_key function retrieves the key value of a map item.

 uint64_t
cl_qmap_key(
    IN  const cl_map_item_t* const  p_item ;

    p_item
        [in] Pointer to a map item whose key value to return.

    Returns the 64-bit key value for the specified map item.

    The key value is set in a call to cl_qmap_insert.

    Quick Map, cl_qmap_insert

Component Library: Quick Map/cl_qmap_merge

    cl_qmap_merge

    The cl_qmap_merge function moves all items from one map to another, 
    excluding duplicates.

void
cl_qmap_merge(
    OUT     cl_qmap_t* const    p_dest_map,
    IN OUT  cl_qmap_t* const    p_src_map );

    p_dest_map
        [out] Pointer to a cl_qmap_t structure to which items should be added.

    p_src_map
        [in/out] Pointer to a cl_qmap_t structure whose items to add 
        to p_dest_map.

    This function does not return a value.

    Items are evaluated based on their keys only.

    Upon return from cl_qmap_merge, the quick map referenced by p_src_map 
    contains all duplicate items.

    Quick Map, cl_qmap_delta

Component Library: Quick Map/cl_qmap_next

    cl_qmap_next

    The cl_qmap_next function returns the map item with the next higher
    key value than a specified map item.

 cl_map_item_t*
cl_qmap_next(
    IN  const cl_map_item_t* const  p_item ;

    p_item
        [in] Pointer to a map item whose successor to return.

    Pointer to the map item with the next higher key value in a quick map.

    Pointer to the map end if the specified item was the last item in
    the quick map.

    Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_prev, cl_qmap_end,
    cl_map_item_t

Component Library: Quick Map/cl_qmap_obj

    cl_qmap_obj

    The cl_qmap_obj function returns the object stored in a map object.

 void*
cl_qmap_obj(
    IN  const cl_map_obj_t* const   p_map_obj ;

    p_map_obj
        [in] Pointer to a map object stucture whose object pointer to return.

    Returns the value of the object pointer stored in the map object.

    Quick Map, cl_qmap_set_obj

Component Library: Quick Map/cl_qmap_prev

    cl_qmap_prev

    The cl_qmap_prev function returns the map item with the next lower
    key value than a precified map item.

 cl_map_item_t*
cl_qmap_prev(
    IN  const cl_map_item_t* const  p_item ;

    p_item
        [in] Pointer to a map item whose predecessor to return.

    Pointer to the map item with the next lower key value in a quick map.

    Pointer to the map end if the specifid item was the first item in
    the quick map.

    Quick Map, cl_qmap_head, cl_qmap_tail, cl_qmap_next, cl_qmap_end,
    cl_map_item_t

Component Library: Quick Map/cl_qmap_remove

    cl_qmap_remove

    The cl_qmap_remove function removes the map item with the specified key
    from a quick map.

cl_map_item_t*
cl_qmap_remove(
    IN  cl_qmap_t* const    p_map,
    IN  const uint64_t      key );

    p_map
        [in] Pointer to a cl_qmap_t structure from which to remove the item
        with the specified key.

    key
        [in] Key value used to search for the map item to remove.

    Pointer to the removed map item if it was found.

    Pointer to the map end if no item with the specified key exists in the
    quick map.

    Quick Map, cl_qmap_remove_item, cl_qmap_remove_all, cl_qmap_insert

Component Library: Quick Map/cl_qmap_remove_all

    cl_qmap_remove_all

    The cl_qmap_remove_all function removes all items in a quick map,
    leaving it empty.

 void
cl_qmap_remove_all(
    IN  cl_qmap_t* const    p_map ;

    p_map
        [in] Pointer to a cl_qmap_t structure to empty.

    This function does not return a value.

    Quick Map, cl_qmap_remove, cl_qmap_remove_item

Component Library: Quick Map/cl_qmap_remove_item

    cl_qmap_remove_item

    The cl_qmap_remove_item function removes the specified map item
    from a quick map.

void
cl_qmap_remove_item(
    IN  cl_qmap_t* const        p_map,
    IN  cl_map_item_t* const    p_item );

    p_item
        [in] Pointer to a map item to remove from its quick map.

    This function does not return a value.

    In a debug build, cl_qmap_remove_item asserts that the item being removed
    is in the specified map.

    Removes the map item pointed to by p_item from its quick map.

    Quick Map, cl_qmap_remove, cl_qmap_remove_all, cl_qmap_insert

Component Library: Quick Map/cl_qmap_set_obj

    cl_qmap_set_obj

    The cl_qmap_set_obj function sets the object stored in a map object.

 void
cl_qmap_set_obj(
    IN  cl_map_obj_t* const p_map_obj,
    IN  const void* const   p_object ;

    p_map_obj
        [in] Pointer to a map object stucture whose object pointer
        is to be set.

    p_object
        [in] User defined context.

    This function does not return a value.

    Quick Map, cl_qmap_obj

Component Library: Quick Map/cl_qmap_t

    cl_qmap_t

    Quick map structure.

    The cl_qmap_t structure should be treated as opaque and should
    be manipulated only through the provided functions.

typedef struct _cl_qmap
{
    cl_map_item_t   root;
    cl_map_item_t   nil;
    cl_state_t      state;
    size_t          count;

} cl_qmap_t;

    root
        Map item that serves as root of the map.  The root is set up to
        always have itself as parent.  The left pointer is set to point to
        the item at the root.

    nil
        Map item that serves as terminator for all leaves, as well as providing
        the list item used as quick list for storing map items in a list for
        faster traversal.

    state
        State of the map, used to verify that operations are permitted.

    count
        Number of items in the map.

    Quick Map

Component Library: Quick Map/cl_qmap_tail

    cl_qmap_tail

    The cl_qmap_tail function returns the map item with the highest key
    value stored in a quick map.

 cl_map_item_t*
cl_qmap_tail(
    IN  const cl_qmap_t* const  p_map ;

    p_map
        [in] Pointer to a cl_qmap_t structure whose item with the highest key
        is returned.

    Pointer to the map item with the highest key in the quick map.

    Pointer to the map end if the quick map was empty.

    cl_qmap_end does not remove the item from the map.

    Quick Map, cl_qmap_head, cl_qmap_next, cl_qmap_prev, cl_qmap_end,
    cl_qmap_item_t