diff options
Diffstat (limited to 'src/btree.c')
-rw-r--r-- | src/btree.c | 1137 |
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 ); +} |