Category : C Source Code
Archive : AVLBST11.ZIP
Filename : SLBUILD.C
Output of file : SLBUILD.C contained in archive : AVLBST11.ZIP
function for sorted list data structure. */
#include
#include "align.h"
#include "stckallc.h"
#include "sortlist.h"
#include "slintrnl.h"
/* macro which returns non-zero if argument is power of 2,
otherwise 0. */
#define POWER_OF_2(NN) (!((NN) & ((NN) - 1)))
/* structure which groups unchanging parameters to minimize
stack usage by recursive function */
typedef struct
{
/* function to get next element is sequence which must be sorted
in ascending order */
int (*next_elem)(void *elem, void *other_param);
/* the other parameter to the "next_elem" function */
void *other_param;
/* pointer to node allocation stack */
ALLOC_STACK *node_as;
}
CONST_PARAM;
/* recursive function to build a tree */
static SL_RESULT build_tree
(
/* pointer to pointer to set to root of tree */
void **tree,
/* number of elements in sequence */
size_t n_elems,
CONST_PARAM *param
)
{
if (n_elems == 0)
*tree = (void *) 0;
else
{
SL_RESULT r;
if (!(*tree = get_alloc_stack(param->node_as)))
return(SL_MEM_ALLOC_FAIL);
r = build_tree(&(NODE(*tree)->branch[LESS_BRANCH]),
(n_elems - 1) >> 1, param);
if (r != SL_SUCCESS)
return(r);
if ((*(param->next_elem))(ELEM_IN_NODE(*tree), param->other_param))
return(SL_ABORT);
r = build_tree(&(NODE(*tree)->branch[GREATER_BRANCH]),
n_elems >> 1, param);
if (r != SL_SUCCESS)
return(r);
/* the two subtrees will have the same depth unless the
total number of elemenets is a power of 2 greater than
1 */
NODE(*tree)->balance = n_elems == 1 ? 0 :
POWER_OF_2(n_elems) ? 1 : 0;
}
return(SL_SUCCESS);
}
/* 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
)
{
CONST_PARAM param;
SL_RESULT r;
if (sl->tree)
return(SL_NOT_EMPTY);
param.next_elem = next_elem;
param.other_param = other_param;
param.node_as = &(sl->node_alloc_stack);
r = build_tree(&(sl->tree), n_elems, ¶m);
if (r != SL_SUCCESS)
{
sl->tree = (void *) 0;
clear_alloc_stack(&(sl->node_alloc_stack));
}
return(r);
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/