avl.h

Go to the documentation of this file.

#pragma once
 
 
#include <stddef.h>
#include <stdbool.h>
 
#include <crater/container.h>
#include <crater/sla.h>
 
typedef struct cr8r_avl_node cr8r_avl_node;
struct cr8r_avl_node{
    cr8r_avl_node *left;
    cr8r_avl_node *right;
    cr8r_avl_node *parent;
    signed char balance;
    char data[];
};
 
typedef struct{
    cr8r_base_ft base;
    int (*cmp)(const cr8r_base_ft*, const void*, const void*);
    int (*add)(cr8r_base_ft*, void*, void*);
    void *(*alloc)(cr8r_base_ft*);
    void (*free)(cr8r_base_ft*, void*);
} cr8r_avl_ft;
 
typedef enum{
    CR8R_AVL_FAILED = 0,
    CR8R_AVL_INSERTED = 1,
    CR8R_AVL_UPDATED = 2
} cr8r_map_insert_result;
 
bool cr8r_avl_ft_init(cr8r_avl_ft*,
    void *data, uint64_t size,
    int (*cmp)(const cr8r_base_ft*, const void*, const void*),
    int (*add)(cr8r_base_ft*, void*, void*),
    void *(*alloc)(cr8r_base_ft*),
    void (*free)(cr8r_base_ft*, void*)
);
 
bool cr8r_avl_ft_initsla(cr8r_avl_ft*,
    cr8r_sla *sla, uint64_t size, uint64_t reserve,
    int (*cmp)(const cr8r_base_ft*, const void*, const void*),
    int (*add)(cr8r_base_ft*, void*, void*)
);
 
cr8r_avl_node *cr8r_avl_new(void *key, cr8r_avl_node *left, cr8r_avl_node *right, cr8r_avl_node *parent, char balance, cr8r_avl_ft*);
 
int cr8r_avl_insert(cr8r_avl_node **r, void *key, cr8r_avl_ft*);
 
int cr8r_avl_remove(cr8r_avl_node **r, void *key, cr8r_avl_ft*);
 
int cr8r_avl_insert_update(cr8r_avl_node **r, void *key, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_remove_node(cr8r_avl_node *n, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_attach(cr8r_avl_node *r, cr8r_avl_node *n, cr8r_avl_ft*, int *is_duplicate);
 
cr8r_avl_node *cr8r_avl_attach_exclusive(cr8r_avl_node *r, cr8r_avl_node *n, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_detach(cr8r_avl_node *n, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_get(cr8r_avl_node *r, void *key, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_search(cr8r_avl_node *r, void *key, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_root(cr8r_avl_node *n);
 
cr8r_avl_node *cr8r_avl_first(cr8r_avl_node *r);
 
cr8r_avl_node *cr8r_avl_next(cr8r_avl_node *n);
 
cr8r_avl_node *cr8r_avl_last(cr8r_avl_node *n);
 
cr8r_avl_node *cr8r_avl_prev(cr8r_avl_node *n);
 
cr8r_avl_node *cr8r_avl_lower_bound(cr8r_avl_node *r, void *key, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_upper_bound(cr8r_avl_node *r, void *key, cr8r_avl_ft*);
 
void cr8r_avl_delete(cr8r_avl_node *r, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_decrease(cr8r_avl_node *n, cr8r_avl_ft*, int *is_duplicate);
 
cr8r_avl_node *cr8r_avl_increase(cr8r_avl_node *n, cr8r_avl_ft*, int *is_duplicate);
 
cr8r_avl_node *cr8r_avl_first_post(cr8r_avl_node *r);
 
cr8r_avl_node *cr8r_avl_next_post(cr8r_avl_node *n);
 
void cr8r_avl_sift_down(cr8r_avl_node *r, cr8r_avl_ft*); 
 
void cr8r_avl_heapify(cr8r_avl_node *r, cr8r_avl_ft*);
 
cr8r_avl_node *cr8r_avl_heappop_node(cr8r_avl_node **r, cr8r_avl_ft*);
 
void cr8r_avl_reorder(cr8r_avl_node *r, cr8r_avl_ft*);
 
#define CR8R_AVL_DATA(T, n) CR8R_FLA_CAST(T, (char*)((cr8r_avl_node*)(n))->data)