source/texk/web2c/mplibdir/avl.h

   1
   2 /*
   3     pyavl -- HEADER FILE "avl.h"
   4     Interface to manipulate "objects" of type 'avl_tree' and 'avl_iterator'
   5 */
   6
   7 #ifndef __AVL__
   8 #define __AVL__
   9
  10 #include <stdarg.h>
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13
  14 #define avl_del mp_avl_del
  15 #define avl_ins mp_avl_ins
  16 #define avl_tree mp_avl_tree
  17 #define avl_entry mp_avl_entry
  18 #define avl_find mp_avl_find
  19 #define avl_create mp_avl_create
  20 #define avl_destroy mp_avl_destroy
  21
  22 typedef enum
  23 { avl_false, avl_true } avl_bool_t;
  24
  25 #ifndef MPW_C
  26 #include <inttypes.h>
  27 typedef int8_t avl_code_t;
  28 typedef int8_t avl_bal_t;
  29 typedef uint32_t avl_size_t;
  30 #else
  31 #include <MacTypes.h>
  32 typedef SInt8 avl_code_t;
  33 typedef SInt8 avl_bal_t;
  34 typedef UInt32 avl_size_t;
  35 #endif
  36
  37 typedef int (*avl_compare_func) (void *param, const void *lhs,
  38                                                                  const void *rhs);
  39 typedef void *(*avl_item_copy_func) (const void *item);
  40 typedef void *(*avl_item_dispose_func) (void *item);
  41 typedef void (*avl_item_func) (const void *item, void *param);
  42 typedef void *(*avl_alloc_func) (size_t);
  43 typedef void (*avl_dealloc_func) (void *);
  44
  45 #ifdef      AVL_FOR_PYTHON
  46 #undef        AVL_CMPERR
  47 #undef            AVL_NULLCHECKS
  48 #define       AVL_CMPERR 1
  49 #define       AVL_NULLCHECKS 1
  50 #else
  51 #ifndef         AVL_CMPERR
  52 #define       AVL_CMPERR 0
  53 #endif
  54 #ifndef         AVL_NULLCHECKS
  55 #define       AVL_NULLCHECKS 0
  56 #endif
  57 #endif
  58
  59 #if AVL_CMPERR != 0
  60 extern avl_code_t avl_errcmp_occurred(void *);
  61 #endif
  62
  63 /* At minimum, shallow copy */
  64
  65 const void *avl_default_item_copy(const void *);
  66 void *avl_default_item_dispose(void *);
  67
  68 #define AVL_STACK_CAPACITY  32  /* for avl_split() function */
  69
  70 typedef enum
  71 {
  72   AVL_ITERATOR_INI_PRE,
  73   AVL_ITERATOR_INI_POST,
  74   AVL_ITERATOR_INI_INTREE
  75 } avl_ini_t;
  76
  77 typedef struct avl_tree_ *avl_tree;
  78 typedef struct avl_iterator_ *avl_iterator;
  79
  80 typedef struct avl_itersource_ avl_itersource_struct, *avl_itersource;
  81
  82 struct avl_itersource_
  83 {
  84   void *p;
  85   /* return nonzero on error */
  86     avl_code_t(*f) (avl_itersource from, void **to);
  87 };
  88
  89 typedef struct
  90 {
  91   avl_compare_func compare;
  92   avl_item_copy_func copy;
  93   avl_item_dispose_func dispose;
  94   avl_alloc_func alloc;
  95   avl_dealloc_func dealloc;
  96 } avl_config_struct, *avl_config;
  97
  98 /* -------------------------------------------------------------------------------------------------/
  99                                         Public Functions
 100 ---------------------------------------------------------------------------------------------------*/
 101
 102 /*
 103     --- CREATE ---
 104     Return a new tree and set its config.
 105     Return NULL on allocation failure.
 106         * 'alloc' defaults to malloc from stdlib
 107         * 'dealloc' defaults to free from stdlib
 108         * 'param' user param/refcon
 109 */
 110
 111 avl_tree avl_create(avl_compare_func compare,
 112                                         avl_item_copy_func copy,
 113                                         avl_item_dispose_func dispose,
 114                                         avl_alloc_func alloc,
 115                                         avl_dealloc_func dealloc, void *param);
 116
 117 /*
 118     --- RESET ---
 119     Empty tree 't' as in 'avl_empty()' and modify its config.
 120 */
 121
 122 void
 123 avl_reset(avl_tree t,
 124                   avl_compare_func compare,
 125                   avl_item_copy_func copy,
 126                   avl_item_dispose_func dispose,
 127                   avl_alloc_func alloc, avl_dealloc_func dealloc);
 128
 129 /*
 130     --- EMPTY ---
 131     Empty tree 't', calling its dispose_func for each item in 't'.
 132     The config is untouched.
 133 */
 134
 135 void avl_empty(avl_tree t);
 136
 137 /*
 138     --- DESTROY ---
 139     Empty tree 't' and free the handle.
 140 */
 141
 142 void avl_destroy(avl_tree t);
 143
 144 /*
 145     --- DUPLICATE (COPY) ---
 146     Return a copy of tree 't', using its copy_func for each item in 't'.
 147     Upon failure to allocate room for some item, return NULL.
 148 */
 149
 150 avl_tree avl_dup(avl_tree t, void *param);
 151
 152 /*
 153     --- EMPTYNESS ---
 154     Return 'avl_true' iff tree 't' is empty (i.e. the handle is NULL or 't' contains no item).
 155 */
 156
 157 avl_bool_t avl_isempty(avl_tree t);
 158
 159 /*
 160     --- SIZE ---
 161     Return number of items contained in tree 't'.
 162 */
 163
 164 avl_size_t avl_size(avl_tree t);
 165
 166 /*
 167     --- FIRST (MINIMUM) ---
 168     Return first item in in-order traversal of 't'.
 169     Return NULL if 't' is empty.
 170 */
 171
 172 void *avl_first(avl_tree t);
 173
 174 /*
 175     --- LAST (MAXIMUM) ---
 176     Return last item in in-order traversal of 't'.
 177     Return NULL if 't' is empty.
 178 */
 179
 180 void *avl_last(avl_tree t);
 181
 182 /*
 183     --- FIND MATCHING ITEM ---
 184     Find item matching 'item' parameter in tree 't'.
 185     Return NULL if it's not found.
 186     If there are multiple matches, the first one that is encountered
 187     during the search is returned; it may not be the one with lowest rank.
 188 */
 189
 190 void *avl_find(const void *item, avl_tree t);
 191
 192 /*
 193     --- INDEX (RANK) OF ITEM ---
 194     Return smallest index 'i' s.t. 't[i]' matches 'item',
 195     or zero if 'item' is not found.
 196 */
 197
 198 avl_size_t avl_index(const void *item, avl_tree t);
 199
 200 /*
 201     --- SPAN ITEMS ---
 202     Return integers 'i,j' s.t. 't[i,j]'
 203     i smallest index s.t. t[i] >= lo_item, or t->count+1 and
 204     j greatest one s.t. t[j] <= hi_item, or 0.
 205     If 'hi_item' is less than 'lo_item' those are swapped.
 206     Return codes:
 207                  0              success
 208                 -1              error: tree had no root
 209                 -2              error: compare failed
 210 */
 211
 212 avl_code_t
 213 avl_span(const void *lo_item,
 214                  const void *hi_item,
 215                  avl_tree t, avl_size_t * lo_idx, avl_size_t * hi_idx);
 216
 217 /*
 218     --- FIND AT LEAST ---
 219     Return smallest item in 't' that is GEQ 'item', or NULL.
 220 */
 221
 222 void *avl_find_atleast(const void *item, avl_tree t);
 223
 224 /*
 225     --- FIND AT MOST ---
 226     Return largest item in 't' that is LEQ 'item', or NULL.
 227 */
 228
 229 void *avl_find_atmost(const void *item, avl_tree t);
 230
 231 /*
 232     --- FIND BY INDEX (RANK) ---
 233     Find item in 't' by index, that is return 't[idx]'.
 234     If 'idx' is not in '[1,avl_size(t)]' then return NULL.
 235         If a compare failed then return NULL.
 236 */
 237
 238 void *avl_find_index(avl_size_t idx, avl_tree t);
 239
 240 /*
 241     --- INSERTION ---
 242     Insert 'item' in tree 't' with regard to its compare_func.
 243     Say 'avl_ins(item,t,avl_true)' to insert 'item' in 't'
 244     even if it is there already.
 245     If 'item' is a duplicate and 'allow_duplicates' is avl_false,
 246     nothing is done.
 247     Return codes:
 248             -1      error: allocation of new node failed
 249                         -2              error: compare failed, tree unchanged
 250              0      nothing was done, no error
 251             +1      operation successful
 252             +2      the same and height(t) increased by one.
 253 */
 254
 255 avl_code_t avl_ins(void *item, avl_tree t, avl_bool_t allow_duplicates);
 256
 257 /*
 258     --- DELETION ---
 259     Remove 'item' from tree 't', calling its dispose_func.
 260     To make a backup of 'item' involving its copy_func,
 261     say 't(item,backup)' where 'backup' is some pointer to pointer to item.
 262     Otherwise set it to NULL.
 263     Return codes:
 264              0      item not found
 265                         -2              error: compare failed, tree unchanged
 266             +1      operation successful
 267             +2      the same and height(t) decreased by one.
 268 */
 269
 270 avl_code_t avl_del(void *item, avl_tree t, void **backup);
 271
 272 /*
 273     --- DELETE FIRST ---
 274     Remove first item in in-order traversal from tree 't'.
 275     Note that only one item is removed.
 276     Return +1 or +2 as above.
 277 */
 278
 279 avl_code_t avl_del_first(avl_tree t, void **backup);
 280
 281 /*
 282     --- DELETE LAST ---
 283     Remove last item in in-order traversal from tree 't'.
 284     Note that only one item is removed.
 285     Return +1 or +2 as above.
 286 */
 287
 288 avl_code_t avl_del_last(avl_tree t, void **backup);
 289
 290 /*
 291     --- INSERT IN FRONT OF INDEX ---
 292     Insert 'item' in tree 't' so that afterwards,
 293     't[idx]=item' except if 'idx<=0' or 'idx>size(t)+1'.
 294     To append 'item' to 't' regardless of order,
 295     say 'avl_ins_index(item,size+1,t)'.
 296 */
 297
 298 avl_code_t avl_ins_index(void *item, avl_size_t idx, avl_tree t);
 299
 300 /*
 301     --- DELETE ITEM BY INDEX ---
 302     Remove item of rank 'idx' from tree 't' and
 303     return +1 or +2 as above except if 'idx' is not in
 304     '[1,avl_size(t)]' in which case return 0.
 305 */
 306
 307 avl_code_t avl_del_index(avl_size_t idx, avl_tree t, void **backup);
 308
 309 /*
 310     --- IN-PLACE CONCATENATION ---
 311     Pre-condition: 't0' and 't1' are valid avl_trees
 312     Note that the code does not check whether the maximal item in 't0' is LEQ than
 313     the minimal item in 't1'.
 314     Post-condition: 't0' handles the concatenation of
 315     't0' and 't1' which becomes empty (but its config is untouched).
 316 */
 317
 318 void avl_cat(avl_tree t0, avl_tree t1);
 319
 320 /*
 321     --- SPLITTING ---
 322     Pre-condition: 't0' and 't1' are existing handles.
 323     Post-condition: items in 't0' all compare LEQ than 'item'
 324     and items in 't1' all compare GEQ than 'item'.
 325     This implementation removes one item.
 326         Return codes:
 327                  0              item not found, no-op
 328                 -2              compare failed, tree unchanged
 329                 +1              success
 330 */
 331
 332 avl_code_t avl_split(const void *item, avl_tree t, avl_tree t0, avl_tree t1);
 333
 334 /*
 335     --- IN-ORDER TRAVERSAL ---
 336     Walk tree 't' in in-order, applying 'proc' at each node.
 337     The 'param' pointer is passed to 'proc', like this:
 338     '(*proc) (item_at_node,param)'.
 339 */
 340
 341 void avl_walk(avl_tree t, avl_item_func proc, void *param);
 342
 343 /*
 344     --- SLICE ---
 345     Create a _new tree_ from the slice 't[lo_idx,hi_idx)'
 346     provided 'lo_idx <= hi_idx' and these indices
 347     are both in range. If a new tree can't be created
 348     or if some item can't be allocated, return NULL.
 349     Otherwise if the indices are inconsistent return NULL.
 350 */
 351
 352 avl_tree
 353 avl_slice(avl_tree t, avl_size_t lo_idx, avl_size_t hi_idx, void *param);
 354
 355 /* ----------------------------------------------------------/
 356                             ITERATORS
 357
 358     An iterator assigned to a tree 't' is still usable after
 359     any item is inserted into 't' and after any item
 360     not located at this iterator's current position is
 361     deleted. The 'avl_iterator_del()' function may be used
 362     to remove the item at the iterator's current position.
 363 ------------------------------------------------------------*/
 364
 365 /*
 366     --- ITERATOR --- SEEK
 367     Find 'item' in this iterator's tree as in 'avl_find()'
 368     and make it the current position.
 369 */
 370
 371 void avl_iterator_seek(const void *item, avl_iterator iter);
 372
 373 /*
 374     --- ITERATOR --- COUNT
 375     Return size of this iterator's tree
 376 */
 377
 378 avl_size_t avl_iterator_count(avl_iterator iter);
 379
 380 /*
 381     --- ITERATOR --- SEEK BY INDEX
 382     Set the current position of 'iter' to 't[idx]'
 383     where 't' is the tree that is iterated over.
 384 */
 385
 386 void avl_iterator_seek_index(avl_size_t idx, avl_iterator iter);
 387
 388 /*
 389     --- ITERATOR --- CURRENT POSITION
 390     Return item at current position of 'iter'.
 391 */
 392
 393 void *avl_iterator_cur(avl_iterator iter);
 394
 395 /*
 396     --- ITERATOR --- INDEX
 397     Return rank of current item of 'iter' (as a result of computation)
 398     except it returns 0 or size of tree plus one if 'iter' is a pre- or post- iterator.
 399 */
 400
 401 avl_size_t avl_iterator_index(avl_iterator iter);
 402
 403 /*
 404     --- ITERATOR --- CREATE
 405     Return a new cursor for tree 't'.
 406     If allocation of an iterator struct is impossible, return NULL.
 407     Say 'avl_iterator_new(t, ini)' with 'ini==AVL_ITERATOR_INI_PRE' or 'ini==AVL_ITERATOR_INI_POST'
 408     or say 'avl_iterator_new(t, AVL_ITERATOR_INI_INTREE, item_pointer)'
 409     to set the iterator's current position via 'avl_iterator_seek(item_pointer,the_iterator)'.
 410     In the latter case, the iterator is flagged
 411     as pre-iterator if the item is not found.
 412 */
 413
 414 avl_iterator avl_iterator_new(avl_tree t, avl_ini_t ini, ...);
 415
 416 /*
 417     --- ITERATOR --- KILL
 418     Cleanup: free the iterator struct.
 419 */
 420
 421 void avl_iterator_kill(avl_iterator iter);
 422
 423 /*
 424     --- ITERATOR --- SUCCESSOR
 425     Get next item pointer in iterator or NULL.
 426     'iter' is flagged as post-iterator if it's in post-position.
 427 */
 428
 429 void *avl_iterator_next(avl_iterator iter);
 430
 431 /*
 432     --- ITERATOR --- PREDECESSOR
 433     Get next item pointer in iterator or NULL.
 434     'iter' is flagged as pre-iterator if it's in pre-position.
 435 */
 436
 437 void *avl_iterator_prev(avl_iterator iter);
 438
 439 /*
 440     --- ITERATOR --- DELETION
 441     Remove item at current position of iterator 'iter' from its tree, if there is one.
 442     Current position is set to next item or iterator is flagged as post-iterator.
 443 */
 444
 445 avl_code_t avl_iterator_del(avl_iterator iter, void **backup);
 446
 447 /*
 448     --- VERIFICATION ---
 449     Return avl_true iff 't' is a valid avl_tree.
 450     Note that 'avl_verify(NULL)==avl_false'.
 451 */
 452
 453 #ifdef HAVE_AVL_VERIFY
 454 avl_bool_t avl_verify(avl_tree t);
 455 #endif /* HAVE_AVL_VERIFY */
 456
 457 /*
 458     --- LOAD ---
 459     More general version of avl_slice
 460 */
 461
 462 avl_tree
 463 avl_xload(avl_itersource src,
 464                   void **pres, avl_size_t len, avl_config conf, void *param);
 465
 466 #endif /* __AVL__ */