/* 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 # include # include // # 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 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