Program Listing for File ostree.h

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

#pragma once

/*******************************************************************************
 * Includes
 ******************************************************************************/
#include "rcsw/ds/bstree.h"

/*******************************************************************************
 * Macros
 ******************************************************************************/
#define RCSW_OSTREE_ROOT(tree) ((struct ostree_node*)RCSW_BSTREE_ROOT(tree))

/*******************************************************************************
 * Structure Definitions
 ******************************************************************************/
struct RCSW_ATTR(packed, aligned (sizeof(dptr_t))) ostree_node {
    uint8_t key[RCSW_BSTREE_NODE_KEYSIZE];
    dptr_t *data;
    struct ostree_node *left;
    struct ostree_node *right;
    struct ostree_node *parent;
    bool_t red;

    int32_t count;
};



/*******************************************************************************
 * RCSW Private Functions
 ******************************************************************************/
BEGIN_C_DECLS
RCSW_LOCAL void ostree_init_helper(struct bstree* tree);

/*******************************************************************************
 * API Functions
 *
 * There are other bstree functions that you can use besides these; however,
 * given that you are using an Order Statistics tree, these are really the only
 * operations you should be doing (besides insert/delete). I don't wrap the
 * bstree API here for that reason.
 *
 ******************************************************************************/

static inline size_t ostree_element_space(size_t max_elts, size_t elt_size) {
  return bstree_element_space(max_elts, elt_size);
}

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

static inline status_t ostree_delete(struct bstree* tree,
                                     struct ostree_node* victim,
                                     void* elt) {
  return bstree_delete(tree, (struct bstree_node*)victim, elt);
}

static inline status_t ostree_remove(struct bstree* tree, const void* key) {
  return bstree_remove(tree, key);
}

static inline void ostree_destroy(struct bstree* tree) {
  return bstree_destroy(tree);
}

static inline struct ostree_node* ostree_node_query(const struct bstree* const tree,
                                                    struct ostree_node* search_root,
                                                    const void* const key) {
  return (struct ostree_node*)bstree_node_query(tree,
                                                (struct bstree_node*)search_root,
                                                key);
}

RCSW_API struct ostree_node* ostree_select(const struct bstree* tree,
                                           struct ostree_node * node_in,
                                           int i);

RCSW_API int ostree_rank(const struct bstree * tree,
                         const struct ostree_node* node);


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


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


END_C_DECLS