diff options
Diffstat (limited to 'source/luametatex/source/libraries/avl/avl.h')
| -rw-r--r-- | source/luametatex/source/libraries/avl/avl.h | 445 |
1 files changed, 445 insertions, 0 deletions
diff --git a/source/luametatex/source/libraries/avl/avl.h b/source/luametatex/source/libraries/avl/avl.h new file mode 100644 index 000000000..03a1384b7 --- /dev/null +++ b/source/luametatex/source/libraries/avl/avl.h @@ -0,0 +1,445 @@ +/* + 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 |