5 kx
5 kx /**********************************************************************
5 kx
5 kx Copyright 2019 Andrey V.Kosteltsev
5 kx
5 kx Licensed under the Radix.pro License, Version 1.0 (the "License");
5 kx you may not use this file except in compliance with the License.
5 kx You may obtain a copy of the License at
5 kx
5 kx https://radix.pro/licenses/LICENSE-1.0-en_US.txt
5 kx
5 kx Unless required by applicable law or agreed to in writing, software
5 kx distributed under the License is distributed on an "AS IS" BASIS,
5 kx WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
5 kx implied.
5 kx
5 kx **********************************************************************/
5 kx
5 kx #include <config.h>
5 kx
5 kx #include <stdlib.h>
5 kx #include <stdio.h>
5 kx #include <string.h>
5 kx #include <stddef.h>
5 kx #include <linux/limits.h>
5 kx
5 kx #include <msglog.h>
5 kx
5 kx #include <btree.h>
5 kx
5 kx struct btree *__btree_alloc( void *data )
5 kx {
5 kx struct btree *node = NULL;
5 kx
5 kx node = (struct btree *)malloc( sizeof( struct btree ) );
5 kx if( !node ) { FATAL_ERROR( "Cannot allocate memory" ); }
5 kx
5 kx bzero( (void *)node, sizeof( struct btree ) );
5 kx node->left = node->right = node;
5 kx
5 kx if( data ) node->data = data;
5 kx
5 kx return node;
5 kx }
5 kx
5 kx struct btree *btree_insert_left( struct btree *tree, struct btree *node )
5 kx {
5 kx if( !tree ) return node;
5 kx if( !node ) return tree;
5 kx
5 kx node->left = tree->left;
5 kx node->ltag = tree->ltag;
5 kx tree->left = node;
5 kx tree->ltag = 1;
5 kx node->right = tree;
5 kx node->rtag = 0;
5 kx
5 kx node->parent = tree;
5 kx
5 kx if( node->ltag )
5 kx {
5 kx node->left->right = node;
5 kx }
5 kx
5 kx return node;
5 kx }
5 kx
5 kx struct btree *btree_insert_right( struct btree *tree, struct btree *node )
5 kx {
5 kx if( !tree ) return node;
5 kx if( !node ) return tree;
5 kx
5 kx node->right = tree->right;
5 kx node->rtag = tree->rtag;
5 kx tree->right = node;
5 kx tree->rtag = 1;
5 kx node->left = tree;
5 kx node->ltag = 0;
5 kx
5 kx node->parent = tree;
5 kx
5 kx if( node->rtag )
5 kx {
5 kx node->right->left = node;
5 kx }
5 kx
5 kx return node;
5 kx }
5 kx
5 kx
5 kx static struct btree *__next_preorder( struct btree *node )
5 kx {
5 kx struct btree *next = node;
5 kx
5 kx if( !next ) return next;
5 kx
5 kx if( next->ltag )
5 kx return next->left;
5 kx
5 kx if( next->rtag )
5 kx return next->right;
5 kx
5 kx while( !next->rtag && next != next->right )
5 kx next = next->right;
5 kx
5 kx if( next->ltag && next->rtag )
5 kx next = next->right;
5 kx
5 kx return next;
5 kx }
5 kx
5 kx void btree_preorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
5 kx {
5 kx struct btree *next = root;
5 kx
5 kx if( !next ) return;
5 kx
5 kx do
5 kx {
5 kx if( func ) { func( next->data, user_data ); }
5 kx
5 kx next = __next_preorder( next );
5 kx
5 kx if( next == root || next == root->right ) break;
5 kx
5 kx } while( next );
5 kx
5 kx if( next == root ) return;
5 kx
5 kx do
5 kx {
5 kx if( func ) { func( next->data, user_data ); }
5 kx
5 kx next = __next_preorder( next );
5 kx
5 kx if( next == root || next == root->right ) break;
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx
5 kx static struct btree *__next_postorder( struct btree *node )
5 kx {
5 kx struct btree *next = NULL;
5 kx
5 kx if( !node ) return next;
5 kx
5 kx next = node->right;
5 kx
5 kx if( !node->rtag )
5 kx return next;
5 kx
5 kx while( next->ltag )
5 kx next = next->left;
5 kx
5 kx return next;
5 kx }
5 kx
5 kx void btree_postorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
5 kx {
5 kx struct btree *next = root;
5 kx
5 kx if( !next ) return;
5 kx
5 kx while( next->ltag )
5 kx next = next->left;
5 kx
5 kx for( ; next ; next = __next_postorder( next ) )
5 kx {
5 kx if( func ) { func( next->data, user_data ); }
5 kx
5 kx if( next == root ) break;
5 kx }
5 kx
5 kx next = __next_postorder( next );
5 kx
5 kx for( ; next ; next = __next_postorder( next ) )
5 kx {
5 kx if( next == root ) break;
5 kx
5 kx if( func ) { func( next->data, user_data ); }
5 kx }
5 kx
5 kx }
5 kx
5 kx
5 kx static struct btree *__start_endorder( struct btree *node )
5 kx {
5 kx struct btree *next = node;
5 kx
5 kx if( !next ) return next;
5 kx
5 kx do
5 kx {
5 kx while( next->ltag )
5 kx next = next->left;
5 kx
5 kx if( !next->rtag )
5 kx return next;
5 kx else
5 kx next = next->right;
5 kx
5 kx while( next->ltag )
5 kx next = next->left;
5 kx
5 kx } while( next->rtag );
5 kx
5 kx return next;
5 kx }
5 kx
5 kx static struct btree *__next_endorder( struct btree *node )
5 kx {
5 kx struct btree *next = node;
5 kx
5 kx if( !next ) return next;
5 kx
5 kx if( next->parent->rtag && (next != next->parent->right) )
5 kx next = __start_endorder( next->parent->right );
5 kx else
5 kx next = next->parent;
5 kx
5 kx return next;
5 kx }
5 kx
5 kx void btree_endorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
5 kx {
5 kx struct btree *next = root;
5 kx
5 kx if( !next ) return;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx if( func ) { func( next->data, user_data ); }
5 kx
5 kx if( next == root ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx
5 kx #if ! defined( max )
5 kx #define max(a,b) \
5 kx ({ typeof (a) _a = (a); \
5 kx typeof (b) _b = (b); \
5 kx _a > _b ? _a : _b; })
5 kx #endif
5 kx
5 kx /************************************
5 kx Tree height and width calculation:
5 kx ─────────────────────────────────
5 kx
5 kx height:
5 kx ┬
5 kx A │ 1
5 kx | \ ├
5 kx B D │ 2
5 kx | | ├
5 kx C E │ 3
5 kx | | \ ├
5 kx K H F │ 4
5 kx | \ ├
5 kx J G │ 5
5 kx ├──┬──┬──┬──┼
5 kx width: 1 2 3 4
5 kx
5 kx ************************************/
5 kx
5 kx int btree_height( struct btree *root )
5 kx {
5 kx struct btree *next = root;
5 kx int height = 0;
5 kx
5 kx if( !next ) return height;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx struct btree *p = next;
5 kx int h = 0;
5 kx
5 kx while( p->parent ) { ++h; p = p->parent; }
5 kx height = max( height, h );
5 kx
5 kx if( next == root ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx
5 kx return height + 1;
5 kx }
5 kx
5 kx int btree_width( struct btree *root )
5 kx {
5 kx int ret = 0, lw = 0, rw = 0;
5 kx struct btree *next = NULL, *left = NULL, *right = NULL;
5 kx
5 kx if( !root ) return ret;
5 kx
5 kx left = next = ( root->ltag ) ? root->left : NULL;
5 kx
5 kx if( next )
5 kx {
5 kx ++lw;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx if( next->ltag && next->rtag )
5 kx ++lw;
5 kx
5 kx if( next == left ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx right = next = ( root->rtag ) ? root->right : NULL;
5 kx
5 kx if( next )
5 kx {
5 kx ++rw;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx if( next->ltag && next->rtag )
5 kx ++rw;
5 kx
5 kx if( next == right ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx ret = lw + rw;
5 kx
5 kx return (ret) ? ret : 1;
5 kx }
5 kx
5 kx int btree_left_width( struct btree *root )
5 kx {
5 kx int lw = 0;
5 kx struct btree *next = NULL, *left = NULL;
5 kx
5 kx if( !root ) return lw;
5 kx
5 kx left = next = ( root->ltag ) ? root->left : NULL;
5 kx
5 kx if( next )
5 kx {
5 kx ++lw;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx if( next->ltag && next->rtag )
5 kx ++lw;
5 kx
5 kx if( next == left ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx return (lw) ? lw : 1;
5 kx }
5 kx
5 kx int btree_right_width( struct btree *root )
5 kx {
5 kx int rw = 0;
5 kx struct btree *next = NULL, *right = NULL;
5 kx
5 kx if( !root ) return rw;
5 kx
5 kx right = next = ( root->rtag ) ? root->right : NULL;
5 kx
5 kx if( next )
5 kx {
5 kx ++rw;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx if( next->ltag && next->rtag )
5 kx ++rw;
5 kx
5 kx if( next == right ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx return (rw) ? rw : 1;
5 kx }
5 kx
5 kx
5 kx struct btree *btree_detach( struct btree *node )
5 kx {
5 kx struct btree *parent = node->parent;
5 kx
5 kx if( !node ) return node;
5 kx
5 kx if( parent->right == node )
5 kx {
5 kx struct btree *rlink = node;
5 kx
5 kx while( rlink->rtag )
5 kx rlink = rlink->right;
5 kx rlink = rlink->right;
5 kx
5 kx parent->right = rlink;
5 kx parent->rtag = 0;
5 kx }
5 kx else
5 kx {
5 kx struct btree *llink = node;
5 kx
5 kx while( llink->ltag )
5 kx llink = llink->left;
5 kx llink = llink->left;
5 kx
5 kx parent->left = llink;
5 kx parent->ltag = 0;
5 kx }
5 kx
5 kx return node;
5 kx }
5 kx
5 kx
5 kx void __btree_free( struct btree *root )
5 kx {
5 kx struct btree *next = root;
5 kx
5 kx if( !next ) return;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx struct btree *tmp = next;
5 kx
5 kx if( next == root )
5 kx {
5 kx free( tmp );
5 kx break;
5 kx }
5 kx next = __next_endorder( next );
5 kx free( tmp );
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx void btree_free( struct btree *root, TREE_FUNC free_func )
5 kx {
5 kx btree_endorder_traversal( root, free_func, NULL );
5 kx __btree_free( root );
5 kx }
5 kx
5 kx
5 kx /*******************************************************************
5 kx Stack functions:
5 kx */
5 kx struct btree_stack *btree_stack_alloc( const size_t n, const size_t u )
5 kx {
5 kx struct btree_stack *stack = NULL;
5 kx
5 kx if( !n || !u ) return stack;
5 kx
5 kx stack = (struct btree_stack *)malloc( sizeof( struct btree_stack ) );
5 kx if( !stack ) { FATAL_ERROR( "Cannot allocate memory" ); }
5 kx bzero( (void *)stack, sizeof( struct btree_stack ) );
5 kx
5 kx stack->__mem_size = n * u;
5 kx stack->__unit_size = u;
5 kx
5 kx stack->__mem = malloc( stack->__mem_size );
5 kx if( !stack->__mem ) { FATAL_ERROR( "Cannot allocate memory" ); }
5 kx
5 kx bzero( stack->__mem, stack->__mem_size );
5 kx stack->__cur_brk = stack->__mem;
5 kx
5 kx return stack;
5 kx }
5 kx
5 kx void btree_stack_free( struct btree_stack **pstack )
5 kx {
5 kx struct btree_stack *stack = NULL;
5 kx
5 kx if( !pstack ) return;
5 kx
5 kx stack = *pstack;
5 kx
5 kx if( !stack ) return;
5 kx if( stack->__mem ) free( stack->__mem );
5 kx
5 kx free( stack );
5 kx
5 kx *pstack = (struct btree_stack *)NULL;
5 kx }
5 kx
5 kx int btree_stack_is_empty( struct btree_stack *stack )
5 kx {
5 kx if( !stack ) return 1;
5 kx if( stack->__mem == stack->__cur_brk ) return 1;
5 kx return 0;
5 kx }
5 kx
5 kx int btree_stack_depth( struct btree_stack *stack )
5 kx {
5 kx if( !stack ) return -1;
5 kx if( btree_stack_is_empty( stack ) )
5 kx return 0;
5 kx
5 kx return (stack->__cur_brk - stack->__mem) / stack->__unit_size;
5 kx }
5 kx
5 kx static int __stack_brk( struct btree_stack *stack, void *end_d )
5 kx {
5 kx void *ptr = NULL;
5 kx
5 kx if( !stack ) return -1;
5 kx
5 kx ptr = stack->__mem;
5 kx if( !ptr ) return -1;
5 kx
5 kx if( end_d < ptr )
5 kx {
5 kx return -1;
5 kx }
5 kx if( end_d > ptr + stack->__mem_size )
5 kx {
5 kx size_t size = stack->__mem_size + stack->__mem_size;
5 kx
5 kx if( (end_d - (ptr + stack->__mem_size)) < stack->__mem_size )
5 kx {
5 kx ptrdiff_t offset = stack->__cur_brk - stack->__mem;
5 kx stack->__mem = realloc( stack->__mem, size );
5 kx if( !stack->__mem ) { FATAL_ERROR( "Cannot allocate memory" ); }
5 kx stack->__mem_size = size;
5 kx stack->__cur_brk = stack->__mem + offset;
5 kx ptr = stack->__mem;
5 kx return 0;
5 kx }
5 kx else
5 kx return -1;
5 kx }
5 kx
5 kx /*
5 kx __cur_brk = end_d;
5 kx
5 kx The function __stack_brk() only checks boundaries of
5 kx memory. The value of __cur_brk is set by __stack_sbrk()
5 kx function.
5 kx *********************************************************/
5 kx
5 kx return 0;
5 kx
5 kx } /* End of __stack_brk() */
5 kx
5 kx static void *__stack_sbrk( struct btree_stack *stack, int incr )
5 kx {
5 kx void *ptr = NULL;
5 kx int rc;
5 kx
5 kx if( !stack ) return ptr;
5 kx
5 kx ptr = stack->__cur_brk;
5 kx
5 kx if( incr == 0 ) return( ptr );
5 kx
5 kx rc = __stack_brk( stack, ptr + incr );
5 kx if( rc == -1 )
5 kx {
5 kx /* errno is set into __mpu_brk() */
5 kx return NULL;
5 kx }
5 kx
5 kx ptr = stack->__cur_brk;
5 kx stack->__cur_brk = ptr + (int)incr;
5 kx
5 kx return ptr;
5 kx
5 kx } /* End of __stack_sbrk() */
5 kx
5 kx
5 kx int btree_stack_push( struct btree_stack *stack, const void *unit )
5 kx {
5 kx void *uptr, *ptr = NULL;
5 kx
5 kx if( !stack ) return -1;
5 kx
5 kx ptr = __stack_sbrk( stack, stack->__unit_size );
5 kx
5 kx if( ptr )
5 kx {
5 kx uptr = memcpy( ptr, unit, stack->__unit_size );
5 kx if( !uptr )
5 kx {
5 kx return -1;
5 kx }
5 kx }
5 kx else
5 kx {
5 kx return -1;
5 kx }
5 kx
5 kx return 0;
5 kx }
5 kx
5 kx int btree_stack_pop( struct btree_stack *stack, void *unit )
5 kx {
5 kx void *uptr, *ptr = NULL;
5 kx
5 kx if( !stack ) return -1;
5 kx
5 kx ptr = __stack_sbrk( stack, -(int)stack->__unit_size );
5 kx
5 kx if( ptr )
5 kx {
5 kx ptr -= stack->__unit_size;
5 kx uptr = memcpy( unit, (const void *)ptr, stack->__unit_size );
5 kx if( !uptr )
5 kx {
5 kx bzero( unit, stack->__unit_size );
5 kx return -1;
5 kx }
5 kx }
5 kx else
5 kx {
5 kx bzero( unit, stack->__unit_size );
5 kx return -1;
5 kx }
5 kx
5 kx return 0;
5 kx }
5 kx /*
5 kx End of stack functions.
5 kx *******************************************************************/
5 kx
5 kx static void btree_print_line( const char *line, int indent, const struct _bctx *ctx )
5 kx {
5 kx char *p, buf[PATH_MAX*2];
5 kx int depth = 0, max_depth = PATH_MAX + PATH_MAX / 2;
5 kx
5 kx if( !line || !ctx ) return;
5 kx
5 kx if( !indent )
5 kx {
5 kx buf[0] = '\0';
5 kx p = (char *)&buf[0];
5 kx depth = 0;
5 kx }
5 kx else
5 kx {
5 kx buf[0] = ' ';
5 kx buf[1] = '\0';
5 kx p = (char *)&buf[1];
5 kx depth = ctx->indent;
5 kx }
5 kx
5 kx if( depth < 1 ) depth = 0;
5 kx if( depth > max_depth ) depth = max_depth;
5 kx
5 kx while( depth )
5 kx {
5 kx (void)sprintf( p, " " ); --depth; ++p; *p = '\0';
5 kx }
5 kx
5 kx (void)sprintf( p, "%s", line );
5 kx
5 kx fprintf( ctx->output, (char *)&buf[0] );
5 kx fflush( ctx->output );
5 kx }
5 kx
5 kx
5 kx static void __btree_clean_prn_flags( struct btree *root )
5 kx {
5 kx struct btree *next = root;
5 kx
5 kx if( !next ) return;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx next->lprn = 0;
5 kx next->rprn = 0;
5 kx
5 kx if( next == root ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx void btree_print_json( FILE *output, struct btree *root, TREE_FUNC func )
5 kx {
5 kx struct btree *next = root;
5 kx struct _bctx ctx;
5 kx
5 kx struct btree_stack *stack;
5 kx struct btree_stack *lstack;
5 kx
5 kx if( !output || !next || !func ) return;
5 kx
5 kx bzero( (void *)&ctx, sizeof(struct _bctx) );
5 kx
5 kx stack = btree_stack_alloc( (const size_t)btree_height(next), sizeof(struct _bctx) );
5 kx
5 kx ctx.output = output;
5 kx ctx.node = next;
5 kx ctx.indent = 0;
5 kx
5 kx __btree_clean_prn_flags( root );
5 kx
5 kx btree_stack_push( stack, (const void *)&ctx );
5 kx
5 kx do
5 kx {
5 kx
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx
5 kx func( next->data, (void *)&ctx );
5 kx
5 kx if( ctx.node->ltag || ctx.node->rtag )
5 kx {
5 kx btree_print_line( ",\n", 0, &ctx );
5 kx btree_print_line( "\"children\": [\n", 1, &ctx );
5 kx btree_print_line( " {\n", 1, &ctx );
5 kx ctx.indent += 2;
5 kx btree_stack_push( stack, (const void *)&ctx );
5 kx }
5 kx else
5 kx {
5 kx btree_stack_push( stack, (const void *)&ctx );
5 kx
5 kx if( !ctx.node->ltag && !ctx.node->rtag )
5 kx {
5 kx if( ctx.node->parent )
5 kx {
5 kx struct _bctx cctx;
5 kx
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx
5 kx memcpy( (void *)&cctx, (const void *)&ctx, sizeof(struct _bctx) );
5 kx
5 kx if( (ctx.node->lprn == ctx.node->ltag) && (ctx.node->rprn == ctx.node->rtag) )
5 kx {
5 kx if( ctx.node->parent->ltag && ctx.node->parent->left == ctx.node )
5 kx ctx.node->parent->lprn = 1;
5 kx if( ctx.node->parent->rtag && ctx.node->parent->right == ctx.node )
5 kx ctx.node->parent->rprn = 1;
5 kx }
5 kx
5 kx if( btree_stack_depth( stack ) > 0 )
5 kx {
5 kx struct btree_stack *pstack = btree_stack_alloc( (const size_t)btree_height(root), sizeof(struct _bctx) );
5 kx struct _bctx pctx;
5 kx
5 kx do
5 kx {
5 kx btree_stack_pop( stack, (void *)&pctx );
5 kx
5 kx if( (cctx.node->lprn == cctx.node->ltag) && (cctx.node->rprn == cctx.node->rtag) )
5 kx {
5 kx if( cctx.node->parent && cctx.node->parent->ltag && cctx.node->parent->left == cctx.node )
5 kx {
5 kx cctx.node->parent->lprn = 1;
5 kx
5 kx if( cctx.node->parent->rtag )
5 kx {
5 kx if( !cctx.node->ltag && !cctx.node->rtag )
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx --ctx.indent;
5 kx btree_print_line( "},\n", 1, &ctx );
5 kx btree_print_line( "{\n", 1, &ctx );
5 kx }
5 kx else
5 kx {
5 kx if( !cctx.node->ltag && !cctx.node->rtag )
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx --ctx.indent;
5 kx btree_print_line( "}\n", 1, &ctx );
5 kx --ctx.indent;
5 kx btree_print_line( "]\n", 1, &ctx );
5 kx }
5 kx }
5 kx if( cctx.node->parent && cctx.node->parent->rtag && cctx.node->parent->right == cctx.node )
5 kx {
5 kx cctx.node->parent->rprn = 1;
5 kx
5 kx if( !cctx.node->ltag && !cctx.node->rtag )
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx --ctx.indent;
5 kx btree_print_line( "}\n", 1, &ctx );
5 kx --ctx.indent;
5 kx btree_print_line( "]\n", 1, &ctx );
5 kx }
5 kx
5 kx }
5 kx
5 kx memcpy( (void *)&cctx, (const void *)&pctx, sizeof(struct _bctx) );
5 kx
5 kx if( (pctx.node->ltag && (pctx.node->lprn < pctx.node->ltag)) || (pctx.node->rtag && (pctx.node->rprn < pctx.node->rtag)) )
5 kx {
5 kx btree_stack_push( pstack, (const void *)&pctx );
5 kx }
5 kx
5 kx } while( !btree_stack_is_empty( stack ) );
5 kx
5 kx while( btree_stack_pop( pstack, (void *)&pctx ) == 0 )
5 kx {
5 kx btree_stack_push( stack, (const void *)&pctx );
5 kx }
5 kx
5 kx btree_stack_free( &pstack );
5 kx }
5 kx else
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx
5 kx } /* End if( parent ) */
5 kx else
5 kx {
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx }
5 kx
5 kx } /* End if( no children ) */
5 kx
5 kx } /* End if( any child ) */
5 kx
5 kx
5 kx next = __next_preorder( next );
5 kx
5 kx
5 kx if( next != root )
5 kx {
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx btree_stack_push( stack, (const void *)&ctx );
5 kx
5 kx ctx.output = output;
5 kx ctx.node = next;
5 kx
5 kx if( btree_stack_push( stack, (const void *)&ctx ) == -1 ) FATAL_ERROR( "btree stack is destroyed" );
5 kx }
5 kx
5 kx if( next == root || next == root->right ) break;
5 kx
5 kx } while( next );
5 kx
5 kx
5 kx if( next == root )
5 kx {
5 kx struct _bctx ctx;
5 kx
5 kx ctx.output = output;
5 kx ctx.node = root;
5 kx ctx.indent = 2;
5 kx
5 kx /* If we in root node then there is no right subtree */
5 kx if( !root->ltag && !root->rtag )
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx
5 kx if( root->ltag && (root->lprn < root->ltag) )
5 kx {
5 kx root->lprn = 1;
5 kx
5 kx --ctx.indent;
5 kx btree_print_line( "}\n", 1, &ctx );
5 kx --ctx.indent;
5 kx btree_print_line( "]\n", 1, &ctx );
5 kx }
5 kx }
5 kx
5 kx if( next == root )
5 kx {
5 kx btree_stack_free( &stack );
5 kx return;
5 kx }
5 kx
5 kx do
5 kx {
5 kx
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx
5 kx func( next->data, (void *)&ctx );
5 kx
5 kx if( ctx.node->ltag || ctx.node->rtag )
5 kx {
5 kx btree_print_line( ",\n", 0, &ctx );
5 kx btree_print_line( "\"children\": [\n", 1, &ctx );
5 kx btree_print_line( " {\n", 1, &ctx );
5 kx ctx.indent += 2;
5 kx btree_stack_push( stack, (const void *)&ctx );
5 kx }
5 kx else
5 kx {
5 kx btree_stack_push( stack, (const void *)&ctx );
5 kx
5 kx if( !ctx.node->ltag && !ctx.node->rtag )
5 kx {
5 kx if( ctx.node->parent )
5 kx {
5 kx struct _bctx cctx;
5 kx
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx
5 kx memcpy( (void *)&cctx, (const void *)&ctx, sizeof(struct _bctx) );
5 kx
5 kx if( (ctx.node->lprn == ctx.node->ltag) && (ctx.node->rprn == ctx.node->rtag) )
5 kx {
5 kx if( ctx.node->parent->ltag && ctx.node->parent->left == ctx.node )
5 kx ctx.node->parent->lprn = 1;
5 kx if( ctx.node->parent->rtag && ctx.node->parent->right == ctx.node )
5 kx ctx.node->parent->rprn = 1;
5 kx }
5 kx
5 kx if( btree_stack_depth( stack ) > 0 )
5 kx {
5 kx struct btree_stack *pstack = btree_stack_alloc( (const size_t)btree_height(root), sizeof(struct _bctx) );
5 kx struct _bctx pctx;
5 kx
5 kx do
5 kx {
5 kx btree_stack_pop( stack, (void *)&pctx );
5 kx
5 kx if( (cctx.node->lprn == cctx.node->ltag) && (cctx.node->rprn == cctx.node->rtag) )
5 kx {
5 kx if( cctx.node->parent && cctx.node->parent->ltag && cctx.node->parent->left == cctx.node )
5 kx {
5 kx cctx.node->parent->lprn = 1;
5 kx
5 kx if( cctx.node->parent->rtag )
5 kx {
5 kx if( !cctx.node->ltag && !cctx.node->rtag )
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx --ctx.indent;
5 kx btree_print_line( "},\n", 1, &ctx );
5 kx btree_print_line( "{\n", 1, &ctx );
5 kx }
5 kx else
5 kx {
5 kx if( !cctx.node->ltag && !cctx.node->rtag )
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx --ctx.indent;
5 kx btree_print_line( "}\n", 1, &ctx );
5 kx --ctx.indent;
5 kx btree_print_line( "]\n", 1, &ctx );
5 kx }
5 kx }
5 kx if( cctx.node->parent && cctx.node->parent->rtag && cctx.node->parent->right == cctx.node )
5 kx {
5 kx cctx.node->parent->rprn = 1;
5 kx
5 kx if( !cctx.node->ltag && !cctx.node->rtag )
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx --ctx.indent;
5 kx btree_print_line( "}\n", 1, &ctx );
5 kx --ctx.indent;
5 kx btree_print_line( "]\n", 1, &ctx );
5 kx }
5 kx
5 kx }
5 kx
5 kx memcpy( (void *)&cctx, (const void *)&pctx, sizeof(struct _bctx) );
5 kx
5 kx if( (pctx.node->ltag && (pctx.node->lprn < pctx.node->ltag)) || (pctx.node->rtag && (pctx.node->rprn < pctx.node->rtag)) )
5 kx {
5 kx btree_stack_push( pstack, (const void *)&pctx );
5 kx }
5 kx
5 kx } while( !btree_stack_is_empty( stack ) );
5 kx
5 kx while( btree_stack_pop( pstack, (void *)&pctx ) == 0 )
5 kx {
5 kx btree_stack_push( stack, (const void *)&pctx );
5 kx }
5 kx
5 kx btree_stack_free( &pstack );
5 kx }
5 kx else
5 kx {
5 kx btree_print_line( "\n", 0, &ctx );
5 kx }
5 kx
5 kx } /* End if( parent ) */
5 kx else
5 kx {
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx }
5 kx
5 kx } /* End if( no children ) */
5 kx
5 kx } /* End if( any child ) */
5 kx
5 kx
5 kx next = __next_preorder( next );
5 kx
5 kx
5 kx if( next != root )
5 kx {
5 kx btree_stack_pop( stack, (void *)&ctx );
5 kx btree_stack_push( stack, (const void *)&ctx );
5 kx
5 kx ctx.output = output;
5 kx ctx.node = next;
5 kx
5 kx if( btree_stack_push( stack, (const void *)&ctx ) == -1 ) FATAL_ERROR( "btree stack is destroyed" );
5 kx }
5 kx
5 kx if( next == root || next == root->right ) break;
5 kx
5 kx } while( next );
5 kx
5 kx btree_stack_free( &stack );
5 kx }
5 kx
5 kx
5 kx int btree_compare( struct btree *root_a, struct btree *root_b, TREE_CMPF cmp_func )
5 kx {
5 kx struct btree *next_a = root_a, *next_b = root_b;
5 kx
5 kx if( !next_a || !next_b || !cmp_func ) return 1;
5 kx
5 kx next_a = __start_endorder( next_a );
5 kx next_b = __start_endorder( next_b );
5 kx
5 kx do
5 kx {
5 kx if( cmp_func( next_a->data, next_b->data ) )
5 kx {
5 kx return 1;
5 kx }
5 kx
5 kx if( next_a == root_a || next_b == root_b )
5 kx {
5 kx if( (next_a == root_a) && (next_b == root_b) )
5 kx break;
5 kx else
5 kx return 1;
5 kx }
5 kx
5 kx next_a = __next_endorder( next_a );
5 kx next_b = __next_endorder( next_b );
5 kx
5 kx } while( next_a && next_b );
5 kx
5 kx return 0;
5 kx }
5 kx
5 kx
5 kx static void __remove_duplicates( struct btree *root, struct btree *node, TREE_CMPF cmp_func, TREE_FUNC free_func )
5 kx {
5 kx struct btree *next = NULL, *rem = NULL;
5 kx
5 kx if( !root || !node || !cmp_func || node == root ) return;
5 kx
5 kx
5 kx next = __next_endorder( node );
5 kx
5 kx if( next == root ) return;
5 kx
5 kx do
5 kx {
5 kx if( !cmp_func( node->data, next->data ) )
5 kx rem = next;
5 kx else
5 kx rem = NULL;
5 kx
5 kx if( next == root ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx if( rem && !rem->ltag && !rem->rtag )
5 kx {
5 kx struct btree *node = btree_detach( rem );
5 kx
5 kx if( free_func )
5 kx {
5 kx btree_free( node, free_func );
5 kx }
5 kx else
5 kx {
5 kx __btree_free( node );
5 kx }
5 kx }
5 kx
5 kx } while( next );
5 kx }
5 kx
5 kx void btree_reduce( struct btree *root, TREE_CMPF cmp_func, TREE_FUNC free_func )
5 kx {
5 kx struct btree *next = root;
5 kx
5 kx if( !next || ! cmp_func ) return;
5 kx
5 kx next = __start_endorder( next );
5 kx
5 kx do
5 kx {
5 kx __remove_duplicates( root, next, cmp_func, free_func );
5 kx
5 kx if( next == root ) break;
5 kx
5 kx next = __next_endorder( next );
5 kx
5 kx } while( next );
5 kx }
Radix cross Linux Package Tools
Package Tools – is a set of utilities to create, install, and update RcL packages
8 Commits
0 Branches
2 Tags