summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/mplibdir/avl.h
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/web2c/mplibdir/avl.h')
-rw-r--r--Build/source/texk/web2c/mplibdir/avl.h467
1 files changed, 467 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/mplibdir/avl.h b/Build/source/texk/web2c/mplibdir/avl.h
new file mode 100644
index 00000000000..a78d50b91cf
--- /dev/null
+++ b/Build/source/texk/web2c/mplibdir/avl.h
@@ -0,0 +1,467 @@
+
+/*
+ pyavl -- HEADER FILE "avl.h"
+ Interface to manipulate "objects" of type 'avl_tree' and 'avl_iterator'
+*/
+
+#ifndef __AVL__
+#define __AVL__
+
+#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_probe mp_avl_probe
+#define avl_create mp_avl_create
+#define avl_destroy mp_avl_destroy
+
+typedef enum
+{ avl_false, avl_true } avl_bool_t;
+
+#ifndef MPW_C
+#include <inttypes.h>
+typedef int8_t avl_code_t;
+typedef int8_t avl_bal_t;
+typedef uint32_t avl_size_t;
+#else
+#include <MacTypes.h>
+typedef SInt8 avl_code_t;
+typedef SInt8 avl_bal_t;
+typedef UInt32 avl_size_t;
+#endif
+
+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 *);
+
+#ifdef AVL_FOR_PYTHON
+#undef AVL_CMPERR
+#undef AVL_NULLCHECKS
+#define AVL_CMPERR 1
+#define AVL_NULLCHECKS 1
+#else
+#ifndef AVL_CMPERR
+#define AVL_CMPERR 0
+#endif
+#ifndef AVL_NULLCHECKS
+#define AVL_NULLCHECKS 0
+#endif
+#endif
+
+#if AVL_CMPERR != 0
+extern avl_code_t avl_errcmp_occurred(void *);
+#endif
+
+/* At minimum, shallow copy */
+
+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_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, *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);
+
+/*
+ --- VERIFICATION ---
+ Return avl_true iff 't' is a valid avl_tree.
+ Note that 'avl_verify(NULL)==avl_false'.
+*/
+
+#ifdef HAVE_AVL_VERIFY
+avl_bool_t avl_verify(avl_tree t);
+#endif /* HAVE_AVL_VERIFY */
+
+/*
+ --- 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 /* __AVL__ */