path: root/source/luametatex/source/libraries/avl/avl.h

/*
    This small C package is made of an independent set of routines dedicated to manipulating AVL
    trees (files avl.c, avl.h), and of an extension module for Python that builds upon it (file
    avlmodule.c). Unlike collectionsmodule.c, the latter file contains only Python bindings: it
    adds nothing to the underlying implementation.

    license: this package, pyavl, is donated to the public domain
    author : Richard McGraw
    email  : dasnar@fastmail.fm
*/

/*
    This file is reformatted a little. As there has not been any changed in the original we assume
    this is okay. No changes means that the code is fine and we never ran into issues.

    The avl code is used for hashing strings. It is also used in the backend of luatex but in
    luametatex we don't have that.
*/

# ifndef LIBRARIES_AVL_H
# define LIBRARIES_AVL_H

# include <stdarg.h>
# include <stdio.h>
# include <stdlib.h>

// # define avl_del     mp_avl_del
// # define avl_ins     mp_avl_ins
// # define avl_tree    mp_avl_tree
// # define avl_entry   mp_avl_entry
// # define avl_find    mp_avl_find
// # define avl_create  mp_avl_create
// # define avl_destroy mp_avl_destroy

typedef enum avl_bool_t {
    avl_false,
    avl_true
} avl_bool_t;

# include <inttypes.h>

typedef int8_t   avl_code_t;
typedef int8_t   avl_bal_t;
typedef uint32_t avl_size_t;

typedef int   (*avl_compare_func)      (void *param, const void *lhs, const void *rhs);
typedef void *(*avl_item_copy_func)    (const void *item);
typedef void *(*avl_item_dispose_func) (void *item);
typedef void  (*avl_item_func)         (const void *item, void *param);
typedef void *(*avl_alloc_func)        (size_t);
typedef void  (*avl_dealloc_func)      (void *);

/* At minimum, shallow copy */

const void *avl_default_item_copy    (const void *);
void       *avl_default_item_dispose (void *);

# define AVL_STACK_CAPACITY 32  /* for avl_split() function */

typedef enum avl_ini_t {
    AVL_ITERATOR_INI_PRE,
    AVL_ITERATOR_INI_POST,
    AVL_ITERATOR_INI_INTREE
} avl_ini_t;

typedef struct avl_tree_        *avl_tree;
typedef struct avl_iterator_    *avl_iterator;
typedef struct avl_itersource_   avl_itersource_struct;
typedef struct avl_itersource_  *avl_itersource;

struct avl_itersource_ {
    void *p;
    /* return nonzero on error */
    avl_code_t(*f) (avl_itersource from, void **to);
};

typedef struct {
    avl_compare_func      compare;
    avl_item_copy_func    copy;
    avl_item_dispose_func dispose;
    avl_alloc_func        alloc;
    avl_dealloc_func      dealloc;
} avl_config_struct, *avl_config;

/* Public Functions */

/*
    --- CREATE ---
    Return a new tree and set its config.
    Return NULL on allocation failure.
    * 'alloc' defaults to malloc from stdlib
    * 'dealloc' defaults to free from stdlib
    * 'param' user param/refcon
*/

avl_tree avl_create(
    avl_compare_func       compare,
    avl_item_copy_func     copy,
    avl_item_dispose_func  dispose,
    avl_alloc_func         alloc,
    avl_dealloc_func       dealloc,
    void                  *param
);

/*
    --- RESET ---
    Empty tree 't' as in 'avl_empty()' and modify its config.
*/

void avl_reset(
    avl_tree              t,
    avl_compare_func      compare,
    avl_item_copy_func    copy,
    avl_item_dispose_func dispose,
    avl_alloc_func        alloc,
    avl_dealloc_func      dealloc
);

/*
    --- EMPTY ---
    Empty tree 't', calling its dispose_func for each item in 't'. The config is
    untouched.
*/

void avl_empty(avl_tree t);

/*
    --- DESTROY ---
    Empty tree 't' and free the handle.
*/

void avl_destroy(avl_tree t);

/*
    --- DUPLICATE (COPY) ---
    Return a copy of tree 't', using its copy_func for each item in 't'. Upon
    failure to allocate room for some item, return NULL.
*/

avl_tree avl_dup(avl_tree t, void *param);

/*
    --- EMPTYNESS ---
    Return 'avl_true' iff tree 't' is empty (i.e. the handle is NULL or 't'
    contains no item).
*/

avl_bool_t avl_isempty(avl_tree t);

/*
    --- SIZE ---
    Return number of items contained in tree 't'.
*/

avl_size_t avl_size(avl_tree t);

/*
    --- FIRST (MINIMUM) ---
    Return first item in in-order traversal of 't'. Return NULL if 't' is empty.
*/

void *avl_first(avl_tree t);

/*
    --- LAST (MAXIMUM) ---
    Return last item in in-order traversal of 't'. Return NULL if 't' is empty.
*/

void *avl_last(avl_tree t);

/*
    --- FIND MATCHING ITEM ---
    Find item matching 'item' parameter in tree 't'. Return NULL if it's not
    found. If there are multiple matches, the first one that is encountered
    during the search is returned; it may not be the one with lowest rank.
*/

void *avl_find(const void *item, avl_tree t);

/*
    --- INDEX (RANK) OF ITEM ---
    Return smallest index 'i' s.t. 't[i]' matches 'item', or zero if 'item' is
    not found.
*/

avl_size_t avl_index(const void *item, avl_tree t);

/*
    --- SPAN ITEMS ---
    Return integers 'i,j' s.t. 't[i,j]'
      i smallest index s.t. t[i] >= lo_item, or t->count+1 and
      j greatest one   s.t. t[j] <= hi_item, or 0.

    If 'hi_item' is less than 'lo_item' those are swapped.

    Return codes:
      0 success
     -1 error: tree had no root
     -2 error: compare failed
*/

avl_code_t avl_span(
    const void *lo_item,
    const void *hi_item,
    avl_tree    t,
    avl_size_t *lo_idx,
    avl_size_t *hi_idx
);

/*
    --- FIND AT LEAST ---
    Return smallest item in 't' that is GEQ 'item', or NULL.
*/

void *avl_find_atleast(const void *item, avl_tree t);

/*
    --- FIND AT MOST ---
    Return largest item in 't' that is LEQ 'item', or NULL.
*/

void *avl_find_atmost(const void *item, avl_tree t);

/*
    --- FIND BY INDEX (RANK) ---
    Find item in 't' by index, that is return 't[idx]'. If 'idx' is not in
    '[1,avl_size(t)]' then return NULL. If a compare failed then return NULL.
*/

void *avl_find_index(avl_size_t idx, avl_tree t);

/*
    --- INSERTION ---
    Insert 'item' in tree 't' with regard to its compare_func. Say
    'avl_ins(item,t,avl_true)' to insert 'item' in 't' even if it is there
    already. If 'item' is a duplicate and 'allow_duplicates' is avl_false,
    nothing is done.

    Return codes:
     -1 error: allocation of new node failed
     -2 error: compare failed, tree unchanged
      0 nothing was done, no error
     +1 operation successful
     +2 the same and height(t) increased by one.
*/

avl_code_t avl_ins(void *item, avl_tree t, avl_bool_t allow_duplicates);

/*
    --- DELETION ---
    Remove 'item' from tree 't', calling its dispose_func. To make a backup of
    'item' involving its copy_func, say 't(item,backup)' where 'backup' is some
    pointer to pointer to item. Otherwise set it to NULL.

    Return codes:
      0 item not found
     -2 error: compare failed, tree unchanged
     +1 operation successful
     +2 the same and height(t) decreased by one.
*/

avl_code_t avl_del(void *item, avl_tree t, void **backup);

/*
    --- DELETE FIRST ---
    Remove first item in in-order traversal from tree 't'. Note that only one
    item is removed. Return +1 or +2 as above.
*/

avl_code_t avl_del_first(avl_tree t, void **backup);

/*
    --- DELETE LAST ---
    Remove last item in in-order traversal from tree 't'. Note that only one item
    is removed. Return +1 or +2 as above.
*/

avl_code_t avl_del_last(avl_tree t, void **backup);

/*
    --- INSERT IN FRONT OF INDEX ---
    Insert 'item' in tree 't' so that afterwards, 't[idx]=item' except if
    'idx<=0' or 'idx>size(t)+1'. To append 'item' to 't' regardless of order, say
    'avl_ins_index(item,size+1,t)'.
*/

avl_code_t avl_ins_index(void *item, avl_size_t idx, avl_tree t);

/*
    --- DELETE ITEM BY INDEX ---
    Remove item of rank 'idx' from tree 't' and return +1 or +2 as above except
    if 'idx' is not in '[1,avl_size(t)]' in which case return 0.
*/

avl_code_t avl_del_index(avl_size_t idx, avl_tree t, void **backup);

/*
    --- IN-PLACE CONCATENATION ---
    Pre-condition: 't0' and 't1' are valid avl_trees Note that the code does not
    check whether the maximal item in 't0' is LEQ than the minimal item in 't1'.
    Post-condition: 't0' handles the concatenation of 't0' and 't1' which becomes
    empty (but its config is untouched).
*/

void avl_cat(avl_tree t0, avl_tree t1);

/*
    --- SPLITTING ---
    Pre-condition: 't0' and 't1' are existing handles. Post-condition: items in
    't0' all compare LEQ than 'item' and items in 't1' all compare GEQ than
    'item'. This implementation removes one item.

    Return codes:
     0 item not found, no-op
    -2 compare failed, tree unchanged
    +1 success
*/

avl_code_t avl_split(const void *item, avl_tree t, avl_tree t0, avl_tree t1);

/*
    --- IN-ORDER TRAVERSAL ---
    Walk tree 't' in in-order, applying 'proc' at each node. The 'param' pointer
    is passed to 'proc', like this: '(*proc) (item_at_node,param)'.
*/

void avl_walk(avl_tree t, avl_item_func proc, void *param);

/*
    --- SLICE ---
    Create a _new tree_ from the slice 't[lo_idx,hi_idx)' provided 'lo_idx <=
    hi_idx' and these indices are both in range. If a new tree can't be created
    or if some item can't be allocated, return NULL. Otherwise if the indices are
    inconsistent return NULL.
*/

avl_tree avl_slice(avl_tree t, avl_size_t lo_idx, avl_size_t hi_idx, void *param);

/*
    ITERATORS

    An iterator assigned to a tree 't' is still usable after any item is inserted
    into 't' and after any item not located at this iterator's current position
    is deleted. The 'avl_iterator_del()' function may be used to remove the item
    at the iterator's current position.

*/

/*
    --- ITERATOR --- SEEK
    Find 'item' in this iterator's tree as in 'avl_find()' and make it the
    current position.
*/

void avl_iterator_seek(const void *item, avl_iterator iter);

/*
    --- ITERATOR --- COUNT
    Return size of this iterator's tree
*/

avl_size_t avl_iterator_count(avl_iterator iter);

/*
    --- ITERATOR --- SEEK BY INDEX
    Set the current position of 'iter' to 't[idx]' where 't' is the tree that is
    iterated over.
*/

void avl_iterator_seek_index(avl_size_t idx, avl_iterator iter);

/*
    --- ITERATOR --- CURRENT POSITION
    Return item at current position of 'iter'.
*/

void *avl_iterator_cur(avl_iterator iter);

/*
    --- ITERATOR --- INDEX
    Return rank of current item of 'iter' (as a result of computation) except it
    returns 0 or size of tree plus one if 'iter' is a pre- or post- iterator.
*/

avl_size_t avl_iterator_index(avl_iterator iter);

/*
    --- ITERATOR --- CREATE
    Return a new cursor for tree 't'. If allocation of an iterator struct is
    impossible, return NULL. Say 'avl_iterator_new(t, ini)' with
    'ini==AVL_ITERATOR_INI_PRE' or 'ini==AVL_ITERATOR_INI_POST' or say
    'avl_iterator_new(t, AVL_ITERATOR_INI_INTREE, item_pointer)' to set the
    iterator's current position via
    'avl_iterator_seek(item_pointer,the_iterator)'. In the latter case, the
    iterator is flagged as pre-iterator if the item is not found.
*/

avl_iterator avl_iterator_new(avl_tree t, avl_ini_t ini, ...);

/*
    --- ITERATOR --- KILL
    Cleanup: free the iterator struct.
*/

void avl_iterator_kill(avl_iterator iter);

/*
    --- ITERATOR --- SUCCESSOR
    Get next item pointer in iterator or NULL. 'iter' is flagged as post-iterator
    if it's in post-position.
*/

void *avl_iterator_next(avl_iterator iter);

/*
    --- ITERATOR --- PREDECESSOR
    Get next item pointer in iterator or NULL. 'iter' is flagged as pre-iterator
    if it's in pre-position.
*/

void *avl_iterator_prev(avl_iterator iter);

/*
    --- ITERATOR --- DELETION
    Remove item at current position of iterator 'iter' from its tree, if there is
    one. Current position is set to next item or iterator is flagged as
    post-iterator.
*/

avl_code_t avl_iterator_del(avl_iterator iter, void **backup);

/*
    --- LOAD ---
    More general version of avl_slice
*/

avl_tree avl_xload(
    avl_itersource   src,
    void           **pres,
    avl_size_t       len,
    avl_config       conf,
    void            *param
);

# endif