Program Listing for File inttree.h

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

#pragma once

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


/*******************************************************************************
 * Macros
 ******************************************************************************/
#define RCSW_INTTREE_ROOT(tree) ((struct inttree_node*)RCSW_BSTREE_ROOT(tree))

/*******************************************************************************
 * Structure Definitions
 ******************************************************************************/
struct RCSW_ATTR(packed, aligned (sizeof(dptr_t))) interval_data  {
    int32_t high;
    int32_t low;
};

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

    int32_t max_high;
};

/*******************************************************************************
 * RCSW Private Functions
 ******************************************************************************/
RCSW_LOCAL void inttree_init_helper(const struct bstree* tree);

RCSW_LOCAL void inttree_high_fixup(const struct bstree* tree,
                                   struct inttree_node* node);

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

BEGIN_C_DECLS
static inline bool_t inttree_isfull(const struct bstree* const tree) {
    return bstree_isfull(tree);
}

static inline bool_t inttree_isempty(const struct bstree* const tree) {
    return bstree_isempty(tree);
}

static inline size_t inttree_size(const struct bstree* const tree) {
    return bstree_size(tree);
}

static inline size_t inttree_element_space(size_t max_elts) {
    return bstree_element_space(max_elts, sizeof(struct interval_data));
}

static inline size_t inttree_meta_space(size_t max_elts) {
    return bstree_meta_space(max_elts);
}

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

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

RCSW_API status_t inttree_insert(struct bstree* tree,
                                 struct interval_data* interval);

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


RCSW_API struct inttree_node* inttree_overlap_search(
    const struct bstree * tree,
    struct inttree_node * root,
    const struct interval_data * interval);


END_C_DECLS