function lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position
Jump to navigation
Jump to search
Source Files
└───liblfds700 ├───inc │ └───liblfds700 │ lfds700_btree_addonly_unbalanced.h └───src └───llfds700_btree_addonly_unbalanced lfds700_btree_addonly_unbalanced_get.c
Opaque Structures
struct lfds700_btree_au_element; struct lfds700_btree_au_state;
Enums
enum lfds700_btree_au_absolute_position { LFDS700_BTREE_AU_ABSOLUTE_POSITION_ROOT, LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS700_BTREE_AU_ABSOLUTE_POSITION_LARGEST_IN_TREE }; enum lfds700_btree_au_relative_position { LFDS700_BTREE_AU_RELATIVE_POSITION_UP, LFDS700_BTREE_AU_RELATIVE_POSITION_LEFT, LFDS700_BTREE_AU_RELATIVE_POSITION_RIGHT, LFDS700_BTREE_AU_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT, LFDS700_BTREE_AU_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT, LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_SMALLER_ELEMENT_IN_ENTIRE_TREE, LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE };
Prototypes
int lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position( struct lfds700_btree_au_state *baus, struct lfds700_btree_au_element **baue, enum lfds700_btree_au_absolute_position absolute_position, enum lfds700_btree_au_relative_position relative_position );
Parameters
struct lfds700_btree_au_state *baus
- A pointer to an initialized lfds700_btree_au_state.
struct lfds700_btree_au_element **baue
- If *baue is NULL, then this argument is set to point to the element indicated by position. If *baue is not NULL, then it must point to an element in a btree, and then this argument is set to the element indicated by the direction argument, using *baue* as the starting point.
enum lfds700_btree_au_absolute_position absolute_position
- Indicates which location in the btree to begin iterating from. Only used when *baue is NULL.
enum lfds700_btree_au_relative_position relative_position
- Indicates which direction the next iteration step should take. Only used when *baue is not NULL (and so points to an element in a tree).
Return Value
Returns 1 if an element was found, 0 if not, which occurs only on empty tree or on reaching end-of-tree (e.g. attempting to get the next largest element at the largest element).
Notes
This is a convenience function for iterating over btrees in a compact manner.
Expected use is in while() loops, to iterate over a btree, like so (here performing an in-order walk, smallest to largest);
struct lfds700_btree_au_element *baue = NULL; void *user_data while( lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position(&baus, &baue, LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) ) { user_data = LFDS700_BTREE_AU_GET_VALUE_FROM_ELEMENT( *baue ); // TRD : do work }
Example
#include <stdio.h> #include "liblfds700.h" struct test_data { int long long unsigned unique_id; char payload[64]; struct lfds700_btree_au_element buae; }; int key_compare_function( void const *new_key, void const *existing_key ) { int cr = 0; int long long unsigned *new_key = (int long long unsigned *) new_key, *existing_key = (int long long unsigned *) existing_key; if( *new_key > *existing_key ) cr = 1; if( *new_key < *existing_key ) cr = -1; return( cr ); } int main() { enum lfds700_btree_au_insert_result bauir; int long long unsigned loop; struct lfds700_btree_au_element *buae = NULL; struct lfds700_btree_au_state baus; struct lfds700_misc_prng_state ps; struct test_data *td, *temp_td; lfds700_misc_library_init_valid_on_current_logical_core(); lfds700_misc_prng_init( &ps ); lfds700_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS700_BTREE_AU_EXISTING_KEY_FAIL, NULL ); // TRD : allocate ten test elements, populate with dummy data and link to tree td = malloc( sizeof(struct test_data) * 10 ); for( loop = 0 ; loop < 10 ; loop++ ) { td[loop].unique_id = loop; sprintf( td[loop].payload, "the unique id is %llu", loop ); LFDS700_BTREE_AU_SET_KEY_IN_ELEMENT( td[loop].baue, &td[loop].unique_id ); LFDS700_BTREE_AU_SET_VALUE_IN_ELEMENT( td[loop].baue, &td[loop] ); bauir = lfds700_btree_au_insert( baus, &td[loop].baue, NULL, &ps ); if( bauir != LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS ) printf( "Well, bugger! so much for quality control\n" ); } // TRD : now in-order walk the tree while( lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position(baus, &baue, LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) ) { temp_td = LFDS700_BTREE_AU_GET_VALUE_FROM_ELEMENT( *baue ); printf( "element %llu has value \"%s\"\n", temp_td->unique_id, temp_id->payload ); } lfds700_btree_au_cleanup( &baus ); free( td ); lfds700_misc_library_cleanup(); return( EXIT_SUCCESS ); }