diff options
Diffstat (limited to 'src/btree.h')
-rw-r--r-- | src/btree.h | 93 |
1 files changed, 93 insertions, 0 deletions
diff --git a/src/btree.h b/src/btree.h new file mode 100644 index 0000000..982e57a --- /dev/null +++ b/src/btree.h @@ -0,0 +1,93 @@ + +/********************************************************************** + + Copyright 2019 Andrey V.Kosteltsev + + Licensed under the Radix.pro License, Version 1.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + https://radix.pro/licenses/LICENSE-1.0-en_US.txt + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied. + + **********************************************************************/ + +#ifndef _BTREE_H_ +#define _BTREE_H_ + +#ifdef __cplusplus +extern "C" { +#endif + + +struct btree { + struct btree *left, *right; + int ltag, rtag; + int lprn, rprn; + + struct btree *parent; + + void *data; +}; + +typedef void (*TREE_FUNC) ( void *data, void *user_data ); +typedef int (*TREE_CMPF) ( const void *a, const void *b ); + + +extern struct btree *__btree_alloc( void *data ); +extern struct btree *btree_insert_left( struct btree *tree, struct btree *node ); +extern struct btree *btree_insert_right( struct btree *tree, struct btree *node ); + +extern void btree_preorder_traversal( struct btree *root, TREE_FUNC func, void *user_data ); +extern void btree_postorder_traversal( struct btree *root, TREE_FUNC func, void *user_data ); +extern void btree_endorder_traversal( struct btree *root, TREE_FUNC func, void *user_data ); + +extern int btree_height( struct btree *root ); +extern int btree_width( struct btree *root ); +extern int btree_left_width( struct btree *root ); +extern int btree_right_width( struct btree *root ); + +extern struct btree *btree_detach( struct btree *node ); + +extern int btree_compare( struct btree *root_a, struct btree *root_b, TREE_CMPF cmp_func ); + +void __btree_free( struct btree *root ); +void btree_free( struct btree *root, TREE_FUNC free_func ); + + +struct btree_stack { + void *__mem; + void *__cur_brk; + size_t __mem_size; + size_t __unit_size; +}; + +extern struct btree_stack *btree_stack_alloc( const size_t n, const size_t u ); +extern void btree_stack_free( struct btree_stack **pstack ); +extern int btree_stack_push( struct btree_stack *stack, const void *unit ); +extern int btree_stack_pop( struct btree_stack *stack, void *unit ); + +extern int btree_stack_is_empty( struct btree_stack *stack ); +extern int btree_stack_depth( struct btree_stack *stack ); + + +struct _bctx +{ + FILE *output; + struct btree *node; + int indent; +}; + +extern void btree_reduce( struct btree *root, TREE_CMPF cmp_func, TREE_FUNC func ); +extern void btree_print_json( FILE *output, struct btree *root, TREE_FUNC func ); + + +#ifdef __cplusplus +} /* ... extern "C" */ +#endif + +#endif /* _BTREE_H_ */ |