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, 825 insertions, 0 deletions
diff --git a/src/btree.c b/src/btree.c
new file mode 100644
index 0000000..e64ef7e
--- /dev/null
+++ b/src/btree.c
@@ -0,0 +1,1137 @@
+
+/**********************************************************************
+
+ 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.
+
+ **********************************************************************/
+
+#include <config.h>
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <stddef.h>
+#include <linux/limits.h>
+
+#include <msglog.h>
+
+#include <btree.h>
+
+struct btree *__btree_alloc( void *data )
+{
+ struct btree *node = NULL;
+
+ node = (struct btree *)malloc( sizeof( struct btree ) );
+ if( !node ) { FATAL_ERROR( "Cannot allocate memory" ); }
+
+ bzero( (void *)node, sizeof( struct btree ) );
+ node->left = node->right = node;
+
+ if( data ) node->data = data;
+
+ return node;
+}
+
+struct btree *btree_insert_left( struct btree *tree, struct btree *node )
+{
+ if( !tree ) return node;
+ if( !node ) return tree;
+
+ node->left = tree->left;
+ node->ltag = tree->ltag;
+ tree->left = node;
+ tree->ltag = 1;
+ node->right = tree;
+ node->rtag = 0;
+
+ node->parent = tree;
+
+ if( node->ltag )
+ {
+ node->left->right = node;
+ }
+
+ return node;
+}
+
+struct btree *btree_insert_right( struct btree *tree, struct btree *node )
+{
+ if( !tree ) return node;
+ if( !node ) return tree;
+
+ node->right = tree->right;
+ node->rtag = tree->rtag;
+ tree->right = node;
+ tree->rtag = 1;
+ node->left = tree;
+ node->ltag = 0;
+
+ node->parent = tree;
+
+ if( node->rtag )
+ {
+ node->right->left = node;
+ }
+
+ return node;
+}
+
+
+static struct btree *__next_preorder( struct btree *node )
+{
+ struct btree *next = node;
+
+ if( !next ) return next;
+
+ if( next->ltag )
+ return next->left;
+
+ if( next->rtag )
+ return next->right;
+
+ while( !next->rtag && next != next->right )
+ next = next->right;
+
+ if( next->ltag && next->rtag )
+ next = next->right;
+
+ return next;
+}
+
+void btree_preorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
+{
+ struct btree *next = root;
+
+ if( !next ) return;
+
+ do
+ {
+ if( func ) { func( next->data, user_data ); }
+
+ next = __next_preorder( next );
+
+ if( next == root || next == root->right ) break;
+
+ } while( next );
+
+ if( next == root ) return;
+
+ do
+ {
+ if( func ) { func( next->data, user_data ); }
+
+ next = __next_preorder( next );
+
+ if( next == root || next == root->right ) break;
+
+ } while( next );
+}
+
+
+static struct btree *__next_postorder( struct btree *node )
+{
+ struct btree *next = NULL;
+
+ if( !node ) return next;
+
+ next = node->right;
+
+ if( !node->rtag )
+ return next;
+
+ while( next->ltag )
+ next = next->left;
+
+ return next;
+}
+
+void btree_postorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
+{
+ struct btree *next = root;
+
+ if( !next ) return;
+
+ while( next->ltag )
+ next = next->left;
+
+ for( ; next ; next = __next_postorder( next ) )
+ {
+ if( func ) { func( next->data, user_data ); }
+
+ if( next == root ) break;
+ }
+
+ next = __next_postorder( next );
+
+ for( ; next ; next = __next_postorder( next ) )
+ {
+ if( next == root ) break;
+
+ if( func ) { func( next->data, user_data ); }
+ }
+
+}
+
+
+static struct btree *__start_endorder( struct btree *node )
+{
+ struct btree *next = node;
+
+ if( !next ) return next;
+
+ do
+ {
+ while( next->ltag )
+ next = next->left;
+
+ if( !next->rtag )
+ return next;
+ else
+ next = next->right;
+
+ while( next->ltag )
+ next = next->left;
+
+ } while( next->rtag );
+
+ return next;
+}
+
+static struct btree *__next_endorder( struct btree *node )
+{
+ struct btree *next = node;
+
+ if( !next ) return next;
+
+ if( next->parent->rtag && (next != next->parent->right) )
+ next = __start_endorder( next->parent->right );
+ else
+ next = next->parent;
+
+ return next;
+}
+
+void btree_endorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
+{
+ struct btree *next = root;
+
+ if( !next ) return;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ if( func ) { func( next->data, user_data ); }
+
+ if( next == root ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+}
+
+
+#if ! defined( max )
+#define max(a,b) \
+ ({ typeof (a) _a = (a); \
+ typeof (b) _b = (b); \
+ _a > _b ? _a : _b; })
+#endif
+
+/************************************
+ Tree height and width calculation:
+ ─────────────────────────────────
+
+ height:
+ ┬
+ A │ 1
+ | \ ├
+ B D │ 2
+ | | ├
+ C E │ 3
+ | | \ ├
+ K H F │ 4
+ | \ ├
+ J G │ 5
+ ├──┬──┬──┬──┼
+ width: 1 2 3 4
+
+ ************************************/
+
+int btree_height( struct btree *root )
+{
+ struct btree *next = root;
+ int height = 0;
+
+ if( !next ) return height;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ struct btree *p = next;
+ int h = 0;
+
+ while( p->parent ) { ++h; p = p->parent; }
+ height = max( height, h );
+
+ if( next == root ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+
+ return height + 1;
+}
+
+int btree_width( struct btree *root )
+{
+ int ret = 0, lw = 0, rw = 0;
+ struct btree *next = NULL, *left = NULL, *right = NULL;
+
+ if( !root ) return ret;
+
+ left = next = ( root->ltag ) ? root->left : NULL;
+
+ if( next )
+ {
+ ++lw;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ if( next->ltag && next->rtag )
+ ++lw;
+
+ if( next == left ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+ }
+
+ right = next = ( root->rtag ) ? root->right : NULL;
+
+ if( next )
+ {
+ ++rw;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ if( next->ltag && next->rtag )
+ ++rw;
+
+ if( next == right ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+ }
+
+ ret = lw + rw;
+
+ return (ret) ? ret : 1;
+}
+
+int btree_left_width( struct btree *root )
+{
+ int lw = 0;
+ struct btree *next = NULL, *left = NULL;
+
+ if( !root ) return lw;
+
+ left = next = ( root->ltag ) ? root->left : NULL;
+
+ if( next )
+ {
+ ++lw;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ if( next->ltag && next->rtag )
+ ++lw;
+
+ if( next == left ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+ }
+
+ return (lw) ? lw : 1;
+}
+
+int btree_right_width( struct btree *root )
+{
+ int rw = 0;
+ struct btree *next = NULL, *right = NULL;
+
+ if( !root ) return rw;
+
+ right = next = ( root->rtag ) ? root->right : NULL;
+
+ if( next )
+ {
+ ++rw;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ if( next->ltag && next->rtag )
+ ++rw;
+
+ if( next == right ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+ }
+
+ return (rw) ? rw : 1;
+}
+
+
+struct btree *btree_detach( struct btree *node )
+{
+ struct btree *parent = node->parent;
+
+ if( !node ) return node;
+
+ if( parent->right == node )
+ {
+ struct btree *rlink = node;
+
+ while( rlink->rtag )
+ rlink = rlink->right;
+ rlink = rlink->right;
+
+ parent->right = rlink;
+ parent->rtag = 0;
+ }
+ else
+ {
+ struct btree *llink = node;
+
+ while( llink->ltag )
+ llink = llink->left;
+ llink = llink->left;
+
+ parent->left = llink;
+ parent->ltag = 0;
+ }
+
+ return node;
+}
+
+
+void __btree_free( struct btree *root )
+{
+ struct btree *next = root;
+
+ if( !next ) return;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ struct btree *tmp = next;
+
+ if( next == root )
+ {
+ free( tmp );
+ break;
+ }
+ next = __next_endorder( next );
+ free( tmp );
+
+ } while( next );
+}
+
+void btree_free( struct btree *root, TREE_FUNC free_func )
+{
+ btree_endorder_traversal( root, free_func, NULL );
+ __btree_free( root );
+}
+
+
+/*******************************************************************
+ Stack functions:
+ */
+struct btree_stack *btree_stack_alloc( const size_t n, const size_t u )
+{
+ struct btree_stack *stack = NULL;
+
+ if( !n || !u ) return stack;
+
+ stack = (struct btree_stack *)malloc( sizeof( struct btree_stack ) );
+ if( !stack ) { FATAL_ERROR( "Cannot allocate memory" ); }
+ bzero( (void *)stack, sizeof( struct btree_stack ) );
+
+ stack->__mem_size = n * u;
+ stack->__unit_size = u;
+
+ stack->__mem = malloc( stack->__mem_size );
+ if( !stack->__mem ) { FATAL_ERROR( "Cannot allocate memory" ); }
+
+ bzero( stack->__mem, stack->__mem_size );
+ stack->__cur_brk = stack->__mem;
+
+ return stack;
+}
+
+void btree_stack_free( struct btree_stack **pstack )
+{
+ struct btree_stack *stack = NULL;
+
+ if( !pstack ) return;
+
+ stack = *pstack;
+
+ if( !stack ) return;
+ if( stack->__mem ) free( stack->__mem );
+
+ free( stack );
+
+ *pstack = (struct btree_stack *)NULL;
+}
+
+int btree_stack_is_empty( struct btree_stack *stack )
+{
+ if( !stack ) return 1;
+ if( stack->__mem == stack->__cur_brk ) return 1;
+ return 0;
+}
+
+int btree_stack_depth( struct btree_stack *stack )
+{
+ if( !stack ) return -1;
+ if( btree_stack_is_empty( stack ) )
+ return 0;
+
+ return (stack->__cur_brk - stack->__mem) / stack->__unit_size;
+}
+
+static int __stack_brk( struct btree_stack *stack, void *end_d )
+{
+ void *ptr = NULL;
+
+ if( !stack ) return -1;
+
+ ptr = stack->__mem;
+ if( !ptr ) return -1;
+
+ if( end_d < ptr )
+ {
+ return -1;
+ }
+ if( end_d > ptr + stack->__mem_size )
+ {
+ size_t size = stack->__mem_size + stack->__mem_size;
+
+ if( (end_d - (ptr + stack->__mem_size)) < stack->__mem_size )
+ {
+ ptrdiff_t offset = stack->__cur_brk - stack->__mem;
+ stack->__mem = realloc( stack->__mem, size );
+ if( !stack->__mem ) { FATAL_ERROR( "Cannot allocate memory" ); }
+ stack->__mem_size = size;
+ stack->__cur_brk = stack->__mem + offset;
+ ptr = stack->__mem;
+ return 0;
+ }
+ else
+ return -1;
+ }
+
+ /*
+ __cur_brk = end_d;
+
+ The function __stack_brk() only checks boundaries of
+ memory. The value of __cur_brk is set by __stack_sbrk()
+ function.
+ *********************************************************/
+
+ return 0;
+
+} /* End of __stack_brk() */
+
+static void *__stack_sbrk( struct btree_stack *stack, int incr )
+{
+ void *ptr = NULL;
+ int rc;
+
+ if( !stack ) return ptr;
+
+ ptr = stack->__cur_brk;
+
+ if( incr == 0 ) return( ptr );
+
+ rc = __stack_brk( stack, ptr + incr );
+ if( rc == -1 )
+ {
+ /* errno is set into __mpu_brk() */
+ return NULL;
+ }
+
+ ptr = stack->__cur_brk;
+ stack->__cur_brk = ptr + (int)incr;
+
+ return ptr;
+
+} /* End of __stack_sbrk() */
+
+
+int btree_stack_push( struct btree_stack *stack, const void *unit )
+{
+ void *uptr, *ptr = NULL;
+
+ if( !stack ) return -1;
+
+ ptr = __stack_sbrk( stack, stack->__unit_size );
+
+ if( ptr )
+ {
+ uptr = memcpy( ptr, unit, stack->__unit_size );
+ if( !uptr )
+ {
+ return -1;
+ }
+ }
+ else
+ {
+ return -1;
+ }
+
+ return 0;
+}
+
+int btree_stack_pop( struct btree_stack *stack, void *unit )
+{
+ void *uptr, *ptr = NULL;
+
+ if( !stack ) return -1;
+
+ ptr = __stack_sbrk( stack, -(int)stack->__unit_size );
+
+ if( ptr )
+ {
+ ptr -= stack->__unit_size;
+ uptr = memcpy( unit, (const void *)ptr, stack->__unit_size );
+ if( !uptr )
+ {
+ bzero( unit, stack->__unit_size );
+ return -1;
+ }
+ }
+ else
+ {
+ bzero( unit, stack->__unit_size );
+ return -1;
+ }
+
+ return 0;
+}
+/*
+ End of stack functions.
+ *******************************************************************/
+
+static void btree_print_line( const char *line, int indent, const struct _bctx *ctx )
+{
+ char *p, buf[PATH_MAX*2];
+ int depth = 0, max_depth = PATH_MAX + PATH_MAX / 2;
+
+ if( !line || !ctx ) return;
+
+ if( !indent )
+ {
+ buf[0] = '\0';
+ p = (char *)&buf[0];
+ depth = 0;
+ }
+ else
+ {
+ buf[0] = ' ';
+ buf[1] = '\0';
+ p = (char *)&buf[1];
+ depth = ctx->indent;
+ }
+
+ if( depth < 1 ) depth = 0;
+ if( depth > max_depth ) depth = max_depth;
+
+ while( depth )
+ {
+ (void)sprintf( p, " " ); --depth; ++p; *p = '\0';
+ }
+
+ (void)sprintf( p, "%s", line );
+
+ fprintf( ctx->output, (char *)&buf[0] );
+ fflush( ctx->output );
+}
+
+
+static void __btree_clean_prn_flags( struct btree *root )
+{
+ struct btree *next = root;
+
+ if( !next ) return;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ next->lprn = 0;
+ next->rprn = 0;
+
+ if( next == root ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+}
+
+void btree_print_json( FILE *output, struct btree *root, TREE_FUNC func )
+{
+ struct btree *next = root;
+ struct _bctx ctx;
+
+ struct btree_stack *stack;
+ struct btree_stack *lstack;
+
+ if( !output || !next || !func ) return;
+
+ bzero( (void *)&ctx, sizeof(struct _bctx) );
+
+ stack = btree_stack_alloc( (const size_t)btree_height(next), sizeof(struct _bctx) );
+
+ ctx.output = output;
+ ctx.node = next;
+ ctx.indent = 0;
+
+ __btree_clean_prn_flags( root );
+
+ btree_stack_push( stack, (const void *)&ctx );
+
+ do
+ {
+
+ btree_stack_pop( stack, (void *)&ctx );
+
+ func( next->data, (void *)&ctx );
+
+ if( ctx.node->ltag || ctx.node->rtag )
+ {
+ btree_print_line( ",\n", 0, &ctx );
+ btree_print_line( "\"children\": [\n", 1, &ctx );
+ btree_print_line( " {\n", 1, &ctx );
+ ctx.indent += 2;
+ btree_stack_push( stack, (const void *)&ctx );
+ }
+ else
+ {
+ btree_stack_push( stack, (const void *)&ctx );
+
+ if( !ctx.node->ltag && !ctx.node->rtag )
+ {
+ if( ctx.node->parent )
+ {
+ struct _bctx cctx;
+
+ btree_stack_pop( stack, (void *)&ctx );
+
+ memcpy( (void *)&cctx, (const void *)&ctx, sizeof(struct _bctx) );
+
+ if( (ctx.node->lprn == ctx.node->ltag) && (ctx.node->rprn == ctx.node->rtag) )
+ {
+ if( ctx.node->parent->ltag && ctx.node->parent->left == ctx.node )
+ ctx.node->parent->lprn = 1;
+ if( ctx.node->parent->rtag && ctx.node->parent->right == ctx.node )
+ ctx.node->parent->rprn = 1;
+ }
+
+ if( btree_stack_depth( stack ) > 0 )
+ {
+ struct btree_stack *pstack = btree_stack_alloc( (const size_t)btree_height(root), sizeof(struct _bctx) );
+ struct _bctx pctx;
+
+ do
+ {
+ btree_stack_pop( stack, (void *)&pctx );
+
+ if( (cctx.node->lprn == cctx.node->ltag) && (cctx.node->rprn == cctx.node->rtag) )
+ {
+ if( cctx.node->parent && cctx.node->parent->ltag && cctx.node->parent->left == cctx.node )
+ {
+ cctx.node->parent->lprn = 1;
+
+ if( cctx.node->parent->rtag )
+ {
+ if( !cctx.node->ltag && !cctx.node->rtag )
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+ --ctx.indent;
+ btree_print_line( "},\n", 1, &ctx );
+ btree_print_line( "{\n", 1, &ctx );
+ }
+ else
+ {
+ if( !cctx.node->ltag && !cctx.node->rtag )
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+ --ctx.indent;
+ btree_print_line( "}\n", 1, &ctx );
+ --ctx.indent;
+ btree_print_line( "]\n", 1, &ctx );
+ }
+ }
+ if( cctx.node->parent && cctx.node->parent->rtag && cctx.node->parent->right == cctx.node )
+ {
+ cctx.node->parent->rprn = 1;
+
+ if( !cctx.node->ltag && !cctx.node->rtag )
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+ --ctx.indent;
+ btree_print_line( "}\n", 1, &ctx );
+ --ctx.indent;
+ btree_print_line( "]\n", 1, &ctx );
+ }
+
+ }
+
+ memcpy( (void *)&cctx, (const void *)&pctx, sizeof(struct _bctx) );
+
+ if( (pctx.node->ltag && (pctx.node->lprn < pctx.node->ltag)) || (pctx.node->rtag && (pctx.node->rprn < pctx.node->rtag)) )
+ {
+ btree_stack_push( pstack, (const void *)&pctx );
+ }
+
+ } while( !btree_stack_is_empty( stack ) );
+
+ while( btree_stack_pop( pstack, (void *)&pctx ) == 0 )
+ {
+ btree_stack_push( stack, (const void *)&pctx );
+ }
+
+ btree_stack_free( &pstack );
+ }
+ else
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+
+ } /* End if( parent ) */
+ else
+ {
+ btree_stack_pop( stack, (void *)&ctx );
+ }
+
+ } /* End if( no children ) */
+
+ } /* End if( any child ) */
+
+
+ next = __next_preorder( next );
+
+
+ if( next != root )
+ {
+ btree_stack_pop( stack, (void *)&ctx );
+ btree_stack_push( stack, (const void *)&ctx );
+
+ ctx.output = output;
+ ctx.node = next;
+
+ if( btree_stack_push( stack, (const void *)&ctx ) == -1 ) FATAL_ERROR( "btree stack is destroyed" );
+ }
+
+ if( next == root || next == root->right ) break;
+
+ } while( next );
+
+
+ if( next == root )
+ {
+ struct _bctx ctx;
+
+ ctx.output = output;
+ ctx.node = root;
+ ctx.indent = 2;
+
+ /* If we in root node then there is no right subtree */
+ if( !root->ltag && !root->rtag )
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+
+ if( root->ltag && (root->lprn < root->ltag) )
+ {
+ root->lprn = 1;
+
+ --ctx.indent;
+ btree_print_line( "}\n", 1, &ctx );
+ --ctx.indent;
+ btree_print_line( "]\n", 1, &ctx );
+ }
+ }
+
+ if( next == root )
+ {
+ btree_stack_free( &stack );
+ return;
+ }
+
+ do
+ {
+
+ btree_stack_pop( stack, (void *)&ctx );
+
+ func( next->data, (void *)&ctx );
+
+ if( ctx.node->ltag || ctx.node->rtag )
+ {
+ btree_print_line( ",\n", 0, &ctx );
+ btree_print_line( "\"children\": [\n", 1, &ctx );
+ btree_print_line( " {\n", 1, &ctx );
+ ctx.indent += 2;
+ btree_stack_push( stack, (const void *)&ctx );
+ }
+ else
+ {
+ btree_stack_push( stack, (const void *)&ctx );
+
+ if( !ctx.node->ltag && !ctx.node->rtag )
+ {
+ if( ctx.node->parent )
+ {
+ struct _bctx cctx;
+
+ btree_stack_pop( stack, (void *)&ctx );
+
+ memcpy( (void *)&cctx, (const void *)&ctx, sizeof(struct _bctx) );
+
+ if( (ctx.node->lprn == ctx.node->ltag) && (ctx.node->rprn == ctx.node->rtag) )
+ {
+ if( ctx.node->parent->ltag && ctx.node->parent->left == ctx.node )
+ ctx.node->parent->lprn = 1;
+ if( ctx.node->parent->rtag && ctx.node->parent->right == ctx.node )
+ ctx.node->parent->rprn = 1;
+ }
+
+ if( btree_stack_depth( stack ) > 0 )
+ {
+ struct btree_stack *pstack = btree_stack_alloc( (const size_t)btree_height(root), sizeof(struct _bctx) );
+ struct _bctx pctx;
+
+ do
+ {
+ btree_stack_pop( stack, (void *)&pctx );
+
+ if( (cctx.node->lprn == cctx.node->ltag) && (cctx.node->rprn == cctx.node->rtag) )
+ {
+ if( cctx.node->parent && cctx.node->parent->ltag && cctx.node->parent->left == cctx.node )
+ {
+ cctx.node->parent->lprn = 1;
+
+ if( cctx.node->parent->rtag )
+ {
+ if( !cctx.node->ltag && !cctx.node->rtag )
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+ --ctx.indent;
+ btree_print_line( "},\n", 1, &ctx );
+ btree_print_line( "{\n", 1, &ctx );
+ }
+ else
+ {
+ if( !cctx.node->ltag && !cctx.node->rtag )
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+ --ctx.indent;
+ btree_print_line( "}\n", 1, &ctx );
+ --ctx.indent;
+ btree_print_line( "]\n", 1, &ctx );
+ }
+ }
+ if( cctx.node->parent && cctx.node->parent->rtag && cctx.node->parent->right == cctx.node )
+ {
+ cctx.node->parent->rprn = 1;
+
+ if( !cctx.node->ltag && !cctx.node->rtag )
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+ --ctx.indent;
+ btree_print_line( "}\n", 1, &ctx );
+ --ctx.indent;
+ btree_print_line( "]\n", 1, &ctx );
+ }
+
+ }
+
+ memcpy( (void *)&cctx, (const void *)&pctx, sizeof(struct _bctx) );
+
+ if( (pctx.node->ltag && (pctx.node->lprn < pctx.node->ltag)) || (pctx.node->rtag && (pctx.node->rprn < pctx.node->rtag)) )
+ {
+ btree_stack_push( pstack, (const void *)&pctx );
+ }
+
+ } while( !btree_stack_is_empty( stack ) );
+
+ while( btree_stack_pop( pstack, (void *)&pctx ) == 0 )
+ {
+ btree_stack_push( stack, (const void *)&pctx );
+ }
+
+ btree_stack_free( &pstack );
+ }
+ else
+ {
+ btree_print_line( "\n", 0, &ctx );
+ }
+
+ } /* End if( parent ) */
+ else
+ {
+ btree_stack_pop( stack, (void *)&ctx );
+ }
+
+ } /* End if( no children ) */
+
+ } /* End if( any child ) */
+
+
+ next = __next_preorder( next );
+
+
+ if( next != root )
+ {
+ btree_stack_pop( stack, (void *)&ctx );
+ btree_stack_push( stack, (const void *)&ctx );
+
+ ctx.output = output;
+ ctx.node = next;
+
+ if( btree_stack_push( stack, (const void *)&ctx ) == -1 ) FATAL_ERROR( "btree stack is destroyed" );
+ }
+
+ if( next == root || next == root->right ) break;
+
+ } while( next );
+
+ btree_stack_free( &stack );
+}
+
+
+int btree_compare( struct btree *root_a, struct btree *root_b, TREE_CMPF cmp_func )
+{
+ struct btree *next_a = root_a, *next_b = root_b;
+
+ if( !next_a || !next_b || !cmp_func ) return 1;
+
+ next_a = __start_endorder( next_a );
+ next_b = __start_endorder( next_b );
+
+ do
+ {
+ if( cmp_func( next_a->data, next_b->data ) )
+ {
+ return 1;
+ }
+
+ if( next_a == root_a || next_b == root_b )
+ {
+ if( (next_a == root_a) && (next_b == root_b) )
+ break;
+ else
+ return 1;
+ }
+
+ next_a = __next_endorder( next_a );
+ next_b = __next_endorder( next_b );
+
+ } while( next_a && next_b );
+
+ return 0;
+}
+
+
+static void __remove_duplicates( struct btree *root, struct btree *node, TREE_CMPF cmp_func, TREE_FUNC free_func )
+{
+ struct btree *next = NULL, *rem = NULL;
+
+ if( !root || !node || !cmp_func || node == root ) return;
+
+
+ next = __next_endorder( node );
+
+ if( next == root ) return;
+
+ do
+ {
+ if( !cmp_func( node->data, next->data ) )
+ rem = next;
+ else
+ rem = NULL;
+
+ if( next == root ) break;
+
+ next = __next_endorder( next );
+
+ if( rem && !rem->ltag && !rem->rtag )
+ {
+ struct btree *node = btree_detach( rem );
+
+ if( free_func )
+ {
+ btree_free( node, free_func );
+ }
+ else
+ {
+ __btree_free( node );
+ }
+ }
+
+ } while( next );
+}
+
+void btree_reduce( struct btree *root, TREE_CMPF cmp_func, TREE_FUNC free_func )
+{
+ struct btree *next = root;
+
+ if( !next || ! cmp_func ) return;
+
+ next = __start_endorder( next );
+
+ do
+ {
+ __remove_duplicates( root, next, cmp_func, free_func );
+
+ if( next == root ) break;
+
+ next = __next_endorder( next );
+
+ } while( next );
+}