Radix cross Linux package tools

11c606a6 (kx 2023-04-11 01:18:34 +0300  1) 
11c606a6 (kx 2023-04-11 01:18:34 +0300  2) /**********************************************************************
11c606a6 (kx 2023-04-11 01:18:34 +0300  3) 
11c606a6 (kx 2023-04-11 01:18:34 +0300  4)   Copyright 2019 Andrey V.Kosteltsev
11c606a6 (kx 2023-04-11 01:18:34 +0300  5) 
11c606a6 (kx 2023-04-11 01:18:34 +0300  6)   Licensed under the Radix.pro License, Version 1.0 (the "License");
11c606a6 (kx 2023-04-11 01:18:34 +0300  7)   you may not use this file  except  in compliance with the License.
11c606a6 (kx 2023-04-11 01:18:34 +0300  8)   You may obtain a copy of the License at
11c606a6 (kx 2023-04-11 01:18:34 +0300  9) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 10)      https://radix.pro/licenses/LICENSE-1.0-en_US.txt
11c606a6 (kx 2023-04-11 01:18:34 +0300 11) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 12)   Unless required by applicable law or agreed to in writing, software
11c606a6 (kx 2023-04-11 01:18:34 +0300 13)   distributed under the License is distributed on an "AS IS" BASIS,
11c606a6 (kx 2023-04-11 01:18:34 +0300 14)   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
11c606a6 (kx 2023-04-11 01:18:34 +0300 15)   implied.
11c606a6 (kx 2023-04-11 01:18:34 +0300 16) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 17)  **********************************************************************/
11c606a6 (kx 2023-04-11 01:18:34 +0300 18) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 19) #ifndef _BTREE_H_
11c606a6 (kx 2023-04-11 01:18:34 +0300 20) #define _BTREE_H_
11c606a6 (kx 2023-04-11 01:18:34 +0300 21) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 22) #ifdef __cplusplus
11c606a6 (kx 2023-04-11 01:18:34 +0300 23) extern "C" {
11c606a6 (kx 2023-04-11 01:18:34 +0300 24) #endif
11c606a6 (kx 2023-04-11 01:18:34 +0300 25) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 26) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 27) struct btree {
11c606a6 (kx 2023-04-11 01:18:34 +0300 28)   struct btree *left, *right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 29)   int           ltag,  rtag;
11c606a6 (kx 2023-04-11 01:18:34 +0300 30)   int           lprn,  rprn;
11c606a6 (kx 2023-04-11 01:18:34 +0300 31) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 32)   struct btree *parent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 33) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 34)   void   *data;
11c606a6 (kx 2023-04-11 01:18:34 +0300 35) };
11c606a6 (kx 2023-04-11 01:18:34 +0300 36) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 37) typedef void (*TREE_FUNC)  ( void *data, void *user_data );
11c606a6 (kx 2023-04-11 01:18:34 +0300 38) typedef int  (*TREE_CMPF)  ( const void *a, const void *b );
11c606a6 (kx 2023-04-11 01:18:34 +0300 39) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 40) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 41) extern struct btree *__btree_alloc( void *data );
11c606a6 (kx 2023-04-11 01:18:34 +0300 42) extern struct btree *btree_insert_left( struct btree *tree, struct btree *node );
11c606a6 (kx 2023-04-11 01:18:34 +0300 43) extern struct btree *btree_insert_right( struct btree *tree, struct btree *node );
11c606a6 (kx 2023-04-11 01:18:34 +0300 44) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 45) extern void btree_preorder_traversal( struct btree *root, TREE_FUNC func, void *user_data );
11c606a6 (kx 2023-04-11 01:18:34 +0300 46) extern void btree_postorder_traversal( struct btree *root, TREE_FUNC func, void *user_data );
11c606a6 (kx 2023-04-11 01:18:34 +0300 47) extern void btree_endorder_traversal( struct btree *root, TREE_FUNC func, void *user_data );
11c606a6 (kx 2023-04-11 01:18:34 +0300 48) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 49) extern int btree_height( struct btree *root );
11c606a6 (kx 2023-04-11 01:18:34 +0300 50) extern int btree_width( struct btree *root );
11c606a6 (kx 2023-04-11 01:18:34 +0300 51) extern int btree_left_width( struct btree *root );
11c606a6 (kx 2023-04-11 01:18:34 +0300 52) extern int btree_right_width( struct btree *root );
11c606a6 (kx 2023-04-11 01:18:34 +0300 53) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 54) extern struct btree *btree_detach( struct btree *node );
11c606a6 (kx 2023-04-11 01:18:34 +0300 55) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 56) extern int btree_compare( struct btree *root_a, struct btree *root_b, TREE_CMPF cmp_func );
11c606a6 (kx 2023-04-11 01:18:34 +0300 57) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 58) void __btree_free( struct btree *root );
11c606a6 (kx 2023-04-11 01:18:34 +0300 59) void btree_free( struct btree *root, TREE_FUNC free_func );
11c606a6 (kx 2023-04-11 01:18:34 +0300 60) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 61) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 62) struct btree_stack {
11c606a6 (kx 2023-04-11 01:18:34 +0300 63)   void   *__mem;
11c606a6 (kx 2023-04-11 01:18:34 +0300 64)   void   *__cur_brk;
11c606a6 (kx 2023-04-11 01:18:34 +0300 65)   size_t  __mem_size;
11c606a6 (kx 2023-04-11 01:18:34 +0300 66)   size_t  __unit_size;
11c606a6 (kx 2023-04-11 01:18:34 +0300 67) };
11c606a6 (kx 2023-04-11 01:18:34 +0300 68) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 69) extern struct btree_stack *btree_stack_alloc( const size_t n, const size_t u );
11c606a6 (kx 2023-04-11 01:18:34 +0300 70) extern void btree_stack_free( struct btree_stack **pstack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 71) extern int btree_stack_push( struct btree_stack *stack, const void *unit );
11c606a6 (kx 2023-04-11 01:18:34 +0300 72) extern int btree_stack_pop( struct btree_stack *stack, void *unit );
11c606a6 (kx 2023-04-11 01:18:34 +0300 73) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 74) extern int btree_stack_is_empty( struct btree_stack *stack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 75) extern int btree_stack_depth( struct btree_stack *stack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 76) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 77) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 78) struct _bctx
11c606a6 (kx 2023-04-11 01:18:34 +0300 79) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 80)   FILE *output;
11c606a6 (kx 2023-04-11 01:18:34 +0300 81)   struct btree *node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 82)   int indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 83) };
11c606a6 (kx 2023-04-11 01:18:34 +0300 84) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 85) extern void btree_reduce( struct btree *root, TREE_CMPF cmp_func, TREE_FUNC func );
11c606a6 (kx 2023-04-11 01:18:34 +0300 86) extern void btree_print_json( FILE *output, struct btree *root, TREE_FUNC func );
11c606a6 (kx 2023-04-11 01:18:34 +0300 87) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 88) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 89) #ifdef __cplusplus
11c606a6 (kx 2023-04-11 01:18:34 +0300 90) }  /* ... extern "C" */
11c606a6 (kx 2023-04-11 01:18:34 +0300 91) #endif
11c606a6 (kx 2023-04-11 01:18:34 +0300 92) 
11c606a6 (kx 2023-04-11 01:18:34 +0300 93) #endif /* _BTREE_H_ */