function lfds700_btree_au_insert

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_insert.c

Opaque Structures

struct lfds700_btree_au_element;
struct lfds700_btree_au_state;
struct lfds700_misc_prng_state;

Enums

enum lfds700_btree_au_insert_result
{
  LFDS700_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY,
  LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE,
  LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS
};

Prototype

enum lfds700_btree_au_insert_result lfds700_btree_au_insert_element( struct lfds700_btree_au_state *baus,
                                                                     struct lfds700_btree_au_element *baue,
                                                                     struct lfds700_btree_au_element **existing_baue,
                                                                     struct lfds700_liblfds_misc_prng_state *ps );

Parameters

struct lfds700_btree_au_state *baus

A pointer to an initialized lfds700_btree_au_state.

struct lfds700_btree_au_element *baue

A pointer a user-allocated LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES aligned lfds700_btree_au_element. Stack declared variables will automatically be correctly aligned by the compiler, due to the information in the structure definitions; nothing has to be done. Heap allocated variables however will by no means be correctly aligned and an aligned malloc must be used.

struct lfds700_btree_au_element **existing_baue

If on link the key already exists, *existing_baue is set to point to the existing element. This argument can be NULL (and then is unused).

struct lfds700_misc_prng_state *ps

A pointer to an initialized struct lfds700_misc_prng_state.

Return Value

The return value is an enum lfds700_btree_au_insert_result.

If the key did not exist in the btree, and so was successfully linked, the return value is LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS.

If the key already exists in the btree, but LFDS700_BTREE_AU_EXISTING_KEY_OVERWRITE was specified to lfds700_btree_au_init_valid_on_current_logical_core when initializing the btree, the return value is LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE (and the value in the existing key will have been overwritten with the value in the new key).

If the key already exists in the btree, but LFDS700_BTREE_AU_EXISTING_KEY_FAIL was specified to lfds700_btree_au_init_valid_on_current_logical_core when initializing the btree, the return value is LFDS700_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY (and the value in the existing key will be unchanged).

Notes

This function takes a user allocated struct lfds700_btree_au_element, which the user has with the btree macros populated with a key (and typically but optionally with a value), and inserts this element into the tree, using the key_compare_function callback to compare btree element keys to find the correct position in the btree.

If when linking a new element the key is already present in the btree, the argument *existing_baue, if not NULL, will be set to point to the existing element.

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()
{
  struct lfds700_btree_au_state
    baus;

  struct lfds700_misc_prng_state
    ps;

  struct test_data
    td = { 15, "de Pijpe" };

  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 );

  LFDS700_BTREE_AU_SET_KEY_IN_ELEMENT( td.baue, &td.unique_id );
  LFDS700_BTREE_AU_SET_VALUE_IN_ELEMENT( td.baue, &td );
  lfds700_btree_au_insert( baus, &td.baue, NULL, &ps );
 
  lfds700_btree_au_cleanup( &baus );

  lfds700_misc_library_cleanup();

  return( EXIT_SUCCESS );
}

See Also