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__ */ 467