author: kx <kx@radix.pro> 2023-04-11 01:18:34 +0300
committer: kx <kx@radix.pro> 2023-04-11 01:18:34 +0300
commit: 11c606a6888dc269ef018359469a7276c3ad8f67
parent: 8c55752ed5b29a22fdab9faaa6ff27b7cafa6791
Commit Summary:
Diffstat:
1 file changed, 63 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_ */