avl.h

// avl.h
#pragma once

enum { avl_none=-1 };

typedef struct avl_s {
    // internals
    int *LR;    // cells links storage
    void *items;// cells data storage
    int root;   // root element index or avl_null
    int count;  // count items in tree. cells_available=limit-count
    int size;   // size cell used.      erased_cells_count=size-count
    int tail;   // last erased cell or avl_null
    int limit;  // limit total cells allocated for tree
    // input parameters item_size,cmp,copy,ovf required
    int  item_size; // item size in bytes
    int  (*cmp) (void *ctx,void *lv,void *rv);   void *cmp_ctx;
    void (*copy)(void *ctx,void *dst,void *src); void *copy_ctx;
    void (*ovf) (void *ctx,struct avl_s *avl);   void *ovf_ctx;
    // ovf can be 0 called to handle limit overflow
} avl_t;

int  avl_init(avl_t *avl,int limit);      // allocate LR and items, require item_size
void avl_done(avl_t *avl);                // free LR and items
int  avl_find(avl_t *avl,void *item);     // check is item exist in tree
int  avl_insert(avl_t *avl,void *item);   // insert item if not exists
int  avl_remove(avl_t *avl,void *item);   // remove item from tree
int  avl_get(avl_t *avl,int n,void *item);// get item value for n position, return position or avl_null (item can be null)
int  avl_min(avl_t *avl,void *item);      // find min item, return position or avl_null (item can be null)
int  avl_max(avl_t *avl,void *item);      // find min item, return position or avl_null (item can be null)
int  avl_next(avl_t *avl,void *item);     // find item greater than input item, and store result in item
int  avl_prev(avl_t *avl,void *item);     // find item less than input item, and store result in item
int  avl_clear(avl_t *avl);               // clear tree
int  avl_available(avl_t *avl);           // return cells available
int  avl_count(avl_t *avl);               // return items count