Version 0.2.1pkgtools-0.2.1

1 files changed, 1137 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 );
+}