Version 0.2.1pkgtools-0.2.1

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_ */