function lfds700_btree_au_query

Source Files

└───liblfds700
    ├───inc
    │   └───liblfds700
    │           lfds700_btree_addonly_unbalanced.h
    └───src
        └───lfds700_btree_addonly_unbalanced
                lfds700_btree_addonly_unbalanced_query.c

Opaque Structures

struct lfds700_btree_au_state;

Enums

enum lfds700_btree_au_query
{
  LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
  LFDS700_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE
};

Prototype

void lfds700_btree_au_query( struct lfds700_btree_au_state *baus,
                             enum lfds700_btree_au_query query_type,
                             void *query_input,
                             void *query_output );

Parameters

struct lfds700_btree_au_state *baus

A pointer to an initialized struct lfds700_btree_au_state.

enum lfds700_btree_au_query query_type

Indicates which query to perform.

void *query_input

A pointer to input data for the query, where the data varies by query;

LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT

query_input is NULL.

LFDS700_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE

This argument can be NULL, or can be a pointer to a struct lfds700_liblfds_validation_info, which specifies an expected min/max count, in which case validation also counts the number of elements and check they fall within the specified range. The walk is thread-safe, the count is not. See Notes.

void *query_output

A pointer to output store for the query, where the output varies by query;

LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT

Points to a lfds700_pal_uint_t, which is set to the number of elements in the tree.

LFDS700_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE

Points to an enum lfds700_misc_validity, which is set to indicate the result of the validation operation.

Notes

All SINGLETHREADED queries can only be safely performed if no insert operations occur while the operation runs. If insert operations do occur during the execution of a SINGLETHREADED query, it is theoretically possible for the query to enter an infinite loop or to access random memory. Do not do this.

The LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT query is non-atomic and walks the tree, counting elements; if new element are added during the count walk, they may not be seen. As such, the count is potentially inaccurate.

Example

#include <stdio.h>
#include "liblfds700.h"

struct test_data
{
  char
    key[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_link_result
    baulr;

  eunm lfds700_misc_validity
    v;

  int long long unsigned
    loop;

  lfds700_pal_uint_t
    element_count;

  struct lfds700_btree_au_element
    *buae = NULL;

  struct lfds700_btree_au_state
    baus;

  struct lfds700_misc_prng_state LFDS700_PAL_ALIGN( LFDS700_PAL_CACHE_LINE_LENGTH_IN_BYTES )
    ps;

  struct lfds700_misc_validation_info
    vi;

  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] );
    baulr = lfds700_btree_au_link( baus, &td[loop].baue, NULL, &ps );
    if( baulr != LFDS700_BTREE_AU_LINK_RESULT_SUCCESS )
      printf( "Well, bugger!  so much for quality control\n" );
  }

  lfds700_btree_au_query( &baus, LFDS700_BTREE_AU_QUERY_SINGLETHREADED_GET_COUNT, NULL, &element_count );

  printf( "element count = %llu\n", (int long long unsigned) element_count );

  vi.min_elements = 10;
  vi.max_elements = 10;

  lfds700_stack_query( &baus, LFDS700_BTREE_AU_QUERY_VALIDATE, (void *) &vi, (void *) &v );

  if( v == LFDS700_MISC_VALIDITY_VALID )
    printf( "Well thank goodness for that\n" );

  if( v != LFDS700_MISC_VALIDITY_VALID )
    printf( "Oh bugger\n" );

  lfds700_btree_au_cleanup( &baus );

  free( td );

  lfds700_misc_library_cleanup();

  return( EXIT_SUCCESS );
}

function lfds700_btree_au_query

Contents