108 lines
2.6 KiB
C
108 lines
2.6 KiB
C
#ifndef LSM_BT
|
|
#define LSM_BT
|
|
|
|
#include <stdbool.h>
|
|
|
|
#include "lsm.h"
|
|
|
|
/**
|
|
* A binary tree implementation using char values as keys
|
|
*/
|
|
typedef struct lsm_bt lsm_bt;
|
|
|
|
/**
|
|
* A node inside an `lsm_bt` binary tree.
|
|
*/
|
|
typedef struct lsm_bt_node lsm_bt_node;
|
|
|
|
/**
|
|
* Initialize a new binary tree
|
|
*
|
|
* @param ptr where to store newly allocated pointer
|
|
*/
|
|
lsm_error lsm_bt_init(lsm_bt **ptr);
|
|
|
|
/**
|
|
* Deallocate an entire binary tree, including all its nodes
|
|
*/
|
|
void lsm_bt_free(lsm_bt *bt);
|
|
|
|
/**
|
|
* Remove the binary tree's entire contents, but keep the struct allocated.
|
|
*/
|
|
void lsm_bt_clear(lsm_bt *bt);
|
|
|
|
/**
|
|
* Return the size of the binary tree
|
|
*/
|
|
uint64_t lsm_bt_size(const lsm_bt *bt);
|
|
|
|
/**
|
|
* Search for the data stored behind the given key.
|
|
*
|
|
* @param out pointer to store data pointer in
|
|
* @param bt binary tree to search
|
|
* @param key key to search
|
|
*/
|
|
lsm_error lsm_bt_search(void **out, const lsm_bt *bt, char key);
|
|
|
|
/**
|
|
* Insert a new data value into the tree with the given key.
|
|
*
|
|
* @param bt binary tree to insert into
|
|
* @param key key to insert
|
|
* @param data data to store
|
|
*/
|
|
lsm_error lsm_bt_insert(lsm_bt *bt, char key, void *data);
|
|
|
|
/**
|
|
* Remove the given key from the binary tree. Ownership of the data pointer is
|
|
* returned to the caller.
|
|
*
|
|
* @param out address to write data pointer to
|
|
* @param bt binary tree to remove from
|
|
* @param key key to remove
|
|
*/
|
|
lsm_error lsm_bt_remove(void **out, lsm_bt *bt, char key);
|
|
|
|
/**
|
|
* Replace the data at an existing key with new data, returning the old.
|
|
*
|
|
* @param out address to write old data pointer to
|
|
* @param bt binary tree to replace in
|
|
* @param key key to replace at
|
|
* @param data new data to store
|
|
*/
|
|
lsm_error lsm_bt_replace(void **out, lsm_bt *bt, char key, void *data);
|
|
|
|
/**
|
|
* Struct representing an in-flight iterator over the binary tree
|
|
*/
|
|
typedef struct lsm_bt_iterator {
|
|
lsm_bt_node *next;
|
|
} lsm_bt_iterator;
|
|
|
|
/**
|
|
* Initialize the given iterator for the binary tree.
|
|
*
|
|
* The iterator is explicitely allowed to be allocated by the user, as these are
|
|
* commonly used inside functions where they can simply be stored on the stack.
|
|
*
|
|
* @param out iterator to initialize
|
|
* @param bt binary tree to iterate
|
|
*/
|
|
void lsm_bt_iter(lsm_bt_iterator *out, const lsm_bt *bt);
|
|
|
|
/**
|
|
* Advance the iterator to the next element.
|
|
*
|
|
* @param out where to store pointer to data; ignored if NULL
|
|
* @param key_out where to store key; ignored if NULL
|
|
* @param iter iterator to advance
|
|
* @return true if a new entry was returned, false if the iterator has no more
|
|
* entries to return
|
|
*/
|
|
bool lsm_bt_iter_next(void **out, char *key_out, lsm_bt_iterator *iter);
|
|
|
|
#endif
|