File Archive

 
Output of file : SORTLIST.H contained in archive : AVLBST11.ZIP

/* header file for sorted list data structure. elements of
the list must have a fixed size. each element must be associated
with a unique "key" value. the set of key values must have
well defined "equal", "greater than" and "less than" relations. */

#if !defined(SORTLIST_H)
#define SORTLIST_H

/* get definition of size_t */
#include

#include "align.h"
#include "stckallc.h"

/* sorted list data structure. all fields are private */
typedef struct
{
/* sizeof element */
size_t elem_size;
/* stack for tree nodes */
ALLOC_STACK node_alloc_stack;
/* pointer to element - element compare function */
int (*elem_elem_compare)(const void *elem1, const void *elem2);
/* pointer to key - element compare function */
int (*key_elem_compare)(const void *key, const void *elem);
/* pointer to tree */
void *tree;
}
SORT_LIST;

/* result codes for functions which access sorted list */
typedef enum
{
/* function was successful */
SL_SUCCESS,
/* function failed due to memory allocation error. if this
happens, a clear_sort_list() is the only valid subsequent
operation on the sorted list. */
SL_MEM_ALLOC_FAIL,
/* function failed because an attempt was made to add an
element with a duplicate key */
SL_DUP_KEY,
/* function failed because matching element not found */
SL_NO_MATCH,
/* function was aborted due to the return value of a caller-supplied
function */
SL_ABORT,
/* function failed because the sorted list was not empty */
SL_NOT_EMPTY
}
SL_RESULT;

/* initialize sorted list */
void init_sort_list
(
/* pointer to sorted list to initialize */
SORT_LIST *sl,
/* sizeof elements to be stored in list */
size_t elem_size,
/* pointer to element - element compare function. the two parameters
are pointers to elements. this function should return some
negative value if the key associated with the first element is
less than the key associated with the second element. it should
return 0 if the key associated with the first element is equal to
the key associated with the second element. it should return some
positive value if the key associated with the first element is
greater than the key associated with the second element. */
int (*e_e_compare)(const void *elem1, const void *elem2),
/* pointer to key - element compare function. the first paramter
is a pointer to a key. the second parameter is a pointer to
an element. this function should return some negative value
if the key passed as a parameter is less than the key associated
with the element parameter. it should return 0 if the key
parameter is equal to the key associated with the element
parameter. it should return some positive value if the key
parameter is greater than the key associated with the element
parameter. */
int (*k_e_compare)(const void *key, const void *elem)
);

/* add an element to a sorted list. memory will be allocated
for the element, and it will be copied to this memory using
memcpy(). the function returns SL_SUCCESS if successful. if the
allocation of memory for the copy of the element fails, the
function returns SL_MEM_ALLOC_FAIL. if an element with the
same key as the element to be added is already in the list,
SL_DUP_KEY is returned. */
SL_RESULT add_sort_list
(
/* sorted list to add element to */
SORT_LIST *sl,
/* element to add to list */
const void *elem
);

/* codes for type of match between a given key and the key of the
element searched for */

/* key of element searched for greatest key strickly less than given
key */
#define MATCH_LESS 1
/* key of element searched for equal to given key */
#define MATCH_EQUAL 2
/* key of element searched for least key strickly greater than given
key */
#define MATCH_GREATER 4
/* key of element searched for greatest key less than or equal to
given key */
#define MATCH_LESS_EQUAL (MATCH_LESS | MATCH_EQUAL)
/* key of element searched for least key greater than or equal to
given key */
#define MATCH_GREATER_EQUAL (MATCH_GREATER | MATCH_EQUAL)
/* find the element with the least key, regardless of the given
key value */
#define MATCH_LEAST 8
/* find the element with the greatest key, regardless of the given
key value */
#define MATCH_GREATEST 16

/* find the element which matches the given key based on the given
match type. returns pointer to element if match is found. returns
null if no match found. the calling code must not change the
key value associated with the element. */
void *find_sort_list
(
/* sorted list to search */
const SORT_LIST *sl,
/* code for type of match desired */
unsigned int match_type,
/* key to match. this parameter is a don't care if match_type
is MATCH_LEAST or MATCH_GREATEST. */
const void *key
);

/* visit each element in the list in ascending or descending order.
call a given function with the element being visited as a parameter.
if the given function returns non-zero, the traversal is interrupted.
returns the result of the last call to the given function, or 0 if
the list is empty. */
int apply_sort_list
(
/* sorted list to traverse */
const SORT_LIST *sl,
/* function to call. the first parameter is the element being
visited. the second parameter is supplied below. this function
can change element keys if and only if the next operation to
be performed on the sorted list is a clear. */
int (*apply)(void *elem, void *param),
void *param,
/* if this flag non-zero, list is traversed in ascending order,
otherwise descending */
int forward,
/* key which indicates which element to start the traversal
with. if forward flag set, start with least element greater
than or equal to this key. if traversal is backward, start with
the greatest element less than or equal to this key. if this
parameter is null, all elements are traversed. */
void *start_key
);

/* build a sorted list from an existing sorted sequence. the function
returns SL_SUCCESS if successful. returns SL_MEM_ALLOC_FAIL if
a memory allocation fails. returns SL_ABORT if the caller-supplied
function returns a non-zero value. returns SL_NOT_EMPTY if the
sorted list is not empty. */
SL_RESULT build_sort_list
(
/* sorted list. must be initialized but empty. if function does
not return SL_SUCCESS, the list will remain empty. */
SORT_LIST *sl,
/* number of elements in sequence */
size_t n_elems,
/* function to get next element is sequence which must be sorted
in ascending order. if this function returns a value other than
zero, the build operation is aborted and the sorted list is
empty. the first parameter to the function is a pointer to
the memory buffer to place the element in. the second parameter
is the void pointer value passed below */
int (*next_elem)(void *elem, void *other_param),
/* the other parameter to the "next_elem" function */
void *other_param
);

/* delete the element with the given key. returns SL_SUCCESS if
element is found. returns SL_NO_MATCH if element not found. */
SL_RESULT delete_sort_list
(
/* sorted list to search */
SORT_LIST *sl,
/* key to match */
const void *key,
/* pointer to variable to receive a copy of the element searched
for. if this pointer is null, the element is simply deleted
without being copied. */
void *elem
);

/* delete all the elements in a sorted list */
void clear_sort_list
(
/* sorted list to search */
SORT_LIST *sl
);

#endif