Radix cross Linux package tools

/**********************************************************************

  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 );
}