Program Listing for File bstree.h

↰ Return to documentation for file (rcsw/ds/bstree.h)

#pragma once

/*******************************************************************************
 * Includes
 ******************************************************************************/
#include "rcsw/ds/ds.h"
#include "rcsw/common/fpc.h"

/*******************************************************************************
 * Constant Definitions
 ******************************************************************************/
#define RCSW_BSTREE_NODE_KEYSIZE sizeof(int32_t)

enum bstree_traversal_type {
  ekTRAVERSE_PREORDER,
  ekTRAVERSE_INORDER,
  ekTRAVERSE_POSTORDER,
};

/*******************************************************************************
 * Macros
 ******************************************************************************/
#define RCSW_BSTREE_ROOT(tree) ((tree)->root->left)

/*******************************************************************************
 * Structure Definitions
 ******************************************************************************/
struct bstree_params {
  int (*cmpkey)(const void *const e1, const void *const e2);

  void (*printe)(const void *e);

  dptr_t *meta;

  dptr_t *elements;

  size_t elt_size;

  int max_elts;

  uint32_t flags;
};

struct RCSW_ATTR(packed, aligned (sizeof(dptr_t))) bstree_node {
  uint8_t key[RCSW_BSTREE_NODE_KEYSIZE];
  dptr_t *data;
  struct bstree_node *left;
  struct bstree_node *right;
  struct bstree_node *parent;

  bool_t red;

  /* extra padding added for compatibility with ostree_node and inttree_node */
  int32_t tmp;
};

struct bstree_space_mgmt {
  dptr_t*             datablocks;

  struct allocm_entry* db_map;

  struct bstree_node*  nodes;

  struct allocm_entry* node_map;
};

struct bstree {
  int (*cmpkey)(const void *const a, const void *const b);

  void (*printe)(const void *const e);

  struct bstree_space_mgmt space;

  size_t current;

  size_t depth;

  uint32_t flags;

  int max_elts;

  size_t elt_size;

  struct bstree_node *root;

  struct bstree_node *nil;
};

/*******************************************************************************
 * API Functions
 ******************************************************************************/
BEGIN_C_DECLS

/*******************************************************************************
 * RCSW Private Functions
 ******************************************************************************/
RCSW_LOCAL status_t bstree_insert_internal(struct bstree * tree,
                                void * key, void * data,
                                size_t node_size);
RCSW_LOCAL struct bstree *bstree_init_internal(struct bstree *tree_in,
                                    const struct bstree_params * params,
                                    size_t node_size) RCSW_WUR;


/*******************************************************************************
 * API Functions
 ******************************************************************************/
static inline bool_t bstree_isfull(const struct bstree* const bst) {
  RCSW_FPC_NV(false, NULL != bst);
  return (bst->current == (size_t)bst->max_elts);
}

static inline bool_t bstree_isempty(const struct bstree* const bst) {
  RCSW_FPC_NV(false, NULL != bst);
  return (bst->current == 0);
}

static inline size_t bstree_size(const struct bstree* const bst) {
  RCSW_FPC_NV(0, NULL != bst);
  return bst->current;
}

static inline size_t bstree_element_space(size_t max_elts, size_t elt_size) {
  return ds_elt_space_with_meta(max_elts+2, elt_size);
}

static inline size_t bstree_meta_space(size_t max_elts) {
  return ds_meta_space(max_elts+2) +
      ds_elt_space_simple(max_elts+2, sizeof(struct bstree_node));
}

RCSW_API status_t bstree_insert(struct bstree* tree,
                                void* const key,
                                void* const data);

RCSW_API struct bstree* bstree_init(struct bstree* tree_in,
                                    const struct bstree_params* const params);

RCSW_API void bstree_destroy(struct bstree *tree);


RCSW_API status_t bstree_remove(struct bstree * tree, const void * key);

RCSW_API status_t bstree_delete(struct bstree* tree, struct bstree_node* victim,
                       void * elt);

RCSW_API struct bstree_node *bstree_node_query(const struct bstree* tree,
                                      struct bstree_node* search_root,
                                      const void* key);

RCSW_API void *bstree_data_query(const struct bstree * tree, const void * key);

RCSW_API int bstree_traverse(struct bstree * tree,
                    int (*cb)(const struct bstree* tree,
                              struct bstree_node * node),
                    enum bstree_traversal_type type);

RCSW_API void bstree_print(struct bstree * tree);



END_C_DECLS