# Category : C Source Code

Archive : AVLBST11.ZIP

Filename : SORTLIST.H

/* 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