function lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position

From liblfds.org
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 );
}

See Also