11c606a6 (kx 2023-04-11 01:18:34 +0300 1)
11c606a6 (kx 2023-04-11 01:18:34 +0300 2) /**********************************************************************
11c606a6 (kx 2023-04-11 01:18:34 +0300 3)
11c606a6 (kx 2023-04-11 01:18:34 +0300 4) Copyright 2019 Andrey V.Kosteltsev
11c606a6 (kx 2023-04-11 01:18:34 +0300 5)
11c606a6 (kx 2023-04-11 01:18:34 +0300 6) Licensed under the Radix.pro License, Version 1.0 (the "License");
11c606a6 (kx 2023-04-11 01:18:34 +0300 7) you may not use this file except in compliance with the License.
11c606a6 (kx 2023-04-11 01:18:34 +0300 8) You may obtain a copy of the License at
11c606a6 (kx 2023-04-11 01:18:34 +0300 9)
11c606a6 (kx 2023-04-11 01:18:34 +0300 10) https://radix.pro/licenses/LICENSE-1.0-en_US.txt
11c606a6 (kx 2023-04-11 01:18:34 +0300 11)
11c606a6 (kx 2023-04-11 01:18:34 +0300 12) Unless required by applicable law or agreed to in writing, software
11c606a6 (kx 2023-04-11 01:18:34 +0300 13) distributed under the License is distributed on an "AS IS" BASIS,
11c606a6 (kx 2023-04-11 01:18:34 +0300 14) WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
11c606a6 (kx 2023-04-11 01:18:34 +0300 15) implied.
11c606a6 (kx 2023-04-11 01:18:34 +0300 16)
11c606a6 (kx 2023-04-11 01:18:34 +0300 17) **********************************************************************/
11c606a6 (kx 2023-04-11 01:18:34 +0300 18)
11c606a6 (kx 2023-04-11 01:18:34 +0300 19) #include <config.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 20)
11c606a6 (kx 2023-04-11 01:18:34 +0300 21) #include <stdlib.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 22) #include <stdio.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 23) #include <string.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 24) #include <stddef.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 25) #include <linux/limits.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 26)
11c606a6 (kx 2023-04-11 01:18:34 +0300 27) #include <msglog.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 28)
11c606a6 (kx 2023-04-11 01:18:34 +0300 29) #include <btree.h>
11c606a6 (kx 2023-04-11 01:18:34 +0300 30)
11c606a6 (kx 2023-04-11 01:18:34 +0300 31) struct btree *__btree_alloc( void *data )
11c606a6 (kx 2023-04-11 01:18:34 +0300 32) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 33) struct btree *node = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 34)
11c606a6 (kx 2023-04-11 01:18:34 +0300 35) node = (struct btree *)malloc( sizeof( struct btree ) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 36) if( !node ) { FATAL_ERROR( "Cannot allocate memory" ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 37)
11c606a6 (kx 2023-04-11 01:18:34 +0300 38) bzero( (void *)node, sizeof( struct btree ) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 39) node->left = node->right = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 40)
11c606a6 (kx 2023-04-11 01:18:34 +0300 41) if( data ) node->data = data;
11c606a6 (kx 2023-04-11 01:18:34 +0300 42)
11c606a6 (kx 2023-04-11 01:18:34 +0300 43) return node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 44) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 45)
11c606a6 (kx 2023-04-11 01:18:34 +0300 46) struct btree *btree_insert_left( struct btree *tree, struct btree *node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 47) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 48) if( !tree ) return node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 49) if( !node ) return tree;
11c606a6 (kx 2023-04-11 01:18:34 +0300 50)
11c606a6 (kx 2023-04-11 01:18:34 +0300 51) node->left = tree->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 52) node->ltag = tree->ltag;
11c606a6 (kx 2023-04-11 01:18:34 +0300 53) tree->left = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 54) tree->ltag = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 55) node->right = tree;
11c606a6 (kx 2023-04-11 01:18:34 +0300 56) node->rtag = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 57)
11c606a6 (kx 2023-04-11 01:18:34 +0300 58) node->parent = tree;
11c606a6 (kx 2023-04-11 01:18:34 +0300 59)
11c606a6 (kx 2023-04-11 01:18:34 +0300 60) if( node->ltag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 61) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 62) node->left->right = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 63) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 64)
11c606a6 (kx 2023-04-11 01:18:34 +0300 65) return node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 66) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 67)
11c606a6 (kx 2023-04-11 01:18:34 +0300 68) struct btree *btree_insert_right( struct btree *tree, struct btree *node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 69) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 70) if( !tree ) return node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 71) if( !node ) return tree;
11c606a6 (kx 2023-04-11 01:18:34 +0300 72)
11c606a6 (kx 2023-04-11 01:18:34 +0300 73) node->right = tree->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 74) node->rtag = tree->rtag;
11c606a6 (kx 2023-04-11 01:18:34 +0300 75) tree->right = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 76) tree->rtag = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 77) node->left = tree;
11c606a6 (kx 2023-04-11 01:18:34 +0300 78) node->ltag = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 79)
11c606a6 (kx 2023-04-11 01:18:34 +0300 80) node->parent = tree;
11c606a6 (kx 2023-04-11 01:18:34 +0300 81)
11c606a6 (kx 2023-04-11 01:18:34 +0300 82) if( node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 83) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 84) node->right->left = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 85) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 86)
11c606a6 (kx 2023-04-11 01:18:34 +0300 87) return node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 88) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 89)
11c606a6 (kx 2023-04-11 01:18:34 +0300 90)
11c606a6 (kx 2023-04-11 01:18:34 +0300 91) static struct btree *__next_preorder( struct btree *node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 92) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 93) struct btree *next = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 94)
11c606a6 (kx 2023-04-11 01:18:34 +0300 95) if( !next ) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 96)
11c606a6 (kx 2023-04-11 01:18:34 +0300 97) if( next->ltag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 98) return next->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 99)
11c606a6 (kx 2023-04-11 01:18:34 +0300 100) if( next->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 101) return next->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 102)
11c606a6 (kx 2023-04-11 01:18:34 +0300 103) while( !next->rtag && next != next->right )
11c606a6 (kx 2023-04-11 01:18:34 +0300 104) next = next->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 105)
11c606a6 (kx 2023-04-11 01:18:34 +0300 106) if( next->ltag && next->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 107) next = next->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 108)
11c606a6 (kx 2023-04-11 01:18:34 +0300 109) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 110) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 111)
11c606a6 (kx 2023-04-11 01:18:34 +0300 112) void btree_preorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
11c606a6 (kx 2023-04-11 01:18:34 +0300 113) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 114) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 115)
11c606a6 (kx 2023-04-11 01:18:34 +0300 116) if( !next ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 117)
11c606a6 (kx 2023-04-11 01:18:34 +0300 118) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 119) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 120) if( func ) { func( next->data, user_data ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 121)
11c606a6 (kx 2023-04-11 01:18:34 +0300 122) next = __next_preorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 123)
11c606a6 (kx 2023-04-11 01:18:34 +0300 124) if( next == root || next == root->right ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 125)
11c606a6 (kx 2023-04-11 01:18:34 +0300 126) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 127)
11c606a6 (kx 2023-04-11 01:18:34 +0300 128) if( next == root ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 129)
11c606a6 (kx 2023-04-11 01:18:34 +0300 130) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 131) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 132) if( func ) { func( next->data, user_data ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 133)
11c606a6 (kx 2023-04-11 01:18:34 +0300 134) next = __next_preorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 135)
11c606a6 (kx 2023-04-11 01:18:34 +0300 136) if( next == root || next == root->right ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 137)
11c606a6 (kx 2023-04-11 01:18:34 +0300 138) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 139) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 140)
11c606a6 (kx 2023-04-11 01:18:34 +0300 141)
11c606a6 (kx 2023-04-11 01:18:34 +0300 142) static struct btree *__next_postorder( struct btree *node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 143) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 144) struct btree *next = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 145)
11c606a6 (kx 2023-04-11 01:18:34 +0300 146) if( !node ) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 147)
11c606a6 (kx 2023-04-11 01:18:34 +0300 148) next = node->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 149)
11c606a6 (kx 2023-04-11 01:18:34 +0300 150) if( !node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 151) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 152)
11c606a6 (kx 2023-04-11 01:18:34 +0300 153) while( next->ltag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 154) next = next->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 155)
11c606a6 (kx 2023-04-11 01:18:34 +0300 156) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 157) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 158)
11c606a6 (kx 2023-04-11 01:18:34 +0300 159) void btree_postorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
11c606a6 (kx 2023-04-11 01:18:34 +0300 160) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 161) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 162)
11c606a6 (kx 2023-04-11 01:18:34 +0300 163) if( !next ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 164)
11c606a6 (kx 2023-04-11 01:18:34 +0300 165) while( next->ltag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 166) next = next->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 167)
11c606a6 (kx 2023-04-11 01:18:34 +0300 168) for( ; next ; next = __next_postorder( next ) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 169) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 170) if( func ) { func( next->data, user_data ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 171)
11c606a6 (kx 2023-04-11 01:18:34 +0300 172) if( next == root ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 173) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 174)
11c606a6 (kx 2023-04-11 01:18:34 +0300 175) next = __next_postorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 176)
11c606a6 (kx 2023-04-11 01:18:34 +0300 177) for( ; next ; next = __next_postorder( next ) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 178) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 179) if( next == root ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 180)
11c606a6 (kx 2023-04-11 01:18:34 +0300 181) if( func ) { func( next->data, user_data ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 182) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 183)
11c606a6 (kx 2023-04-11 01:18:34 +0300 184) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 185)
11c606a6 (kx 2023-04-11 01:18:34 +0300 186)
11c606a6 (kx 2023-04-11 01:18:34 +0300 187) static struct btree *__start_endorder( struct btree *node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 188) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 189) struct btree *next = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 190)
11c606a6 (kx 2023-04-11 01:18:34 +0300 191) if( !next ) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 192)
11c606a6 (kx 2023-04-11 01:18:34 +0300 193) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 194) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 195) while( next->ltag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 196) next = next->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 197)
11c606a6 (kx 2023-04-11 01:18:34 +0300 198) if( !next->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 199) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 200) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 201) next = next->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 202)
11c606a6 (kx 2023-04-11 01:18:34 +0300 203) while( next->ltag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 204) next = next->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 205)
11c606a6 (kx 2023-04-11 01:18:34 +0300 206) } while( next->rtag );
11c606a6 (kx 2023-04-11 01:18:34 +0300 207)
11c606a6 (kx 2023-04-11 01:18:34 +0300 208) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 209) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 210)
11c606a6 (kx 2023-04-11 01:18:34 +0300 211) static struct btree *__next_endorder( struct btree *node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 212) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 213) struct btree *next = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 214)
11c606a6 (kx 2023-04-11 01:18:34 +0300 215) if( !next ) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 216)
11c606a6 (kx 2023-04-11 01:18:34 +0300 217) if( next->parent->rtag && (next != next->parent->right) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 218) next = __start_endorder( next->parent->right );
11c606a6 (kx 2023-04-11 01:18:34 +0300 219) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 220) next = next->parent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 221)
11c606a6 (kx 2023-04-11 01:18:34 +0300 222) return next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 223) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 224)
11c606a6 (kx 2023-04-11 01:18:34 +0300 225) void btree_endorder_traversal( struct btree *root, TREE_FUNC func, void *user_data )
11c606a6 (kx 2023-04-11 01:18:34 +0300 226) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 227) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 228)
11c606a6 (kx 2023-04-11 01:18:34 +0300 229) if( !next ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 230)
11c606a6 (kx 2023-04-11 01:18:34 +0300 231) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 232)
11c606a6 (kx 2023-04-11 01:18:34 +0300 233) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 234) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 235) if( func ) { func( next->data, user_data ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 236)
11c606a6 (kx 2023-04-11 01:18:34 +0300 237) if( next == root ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 238)
11c606a6 (kx 2023-04-11 01:18:34 +0300 239) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 240)
11c606a6 (kx 2023-04-11 01:18:34 +0300 241) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 242) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 243)
11c606a6 (kx 2023-04-11 01:18:34 +0300 244)
11c606a6 (kx 2023-04-11 01:18:34 +0300 245) #if ! defined( max )
11c606a6 (kx 2023-04-11 01:18:34 +0300 246) #define max(a,b) \
11c606a6 (kx 2023-04-11 01:18:34 +0300 247) ({ typeof (a) _a = (a); \
11c606a6 (kx 2023-04-11 01:18:34 +0300 248) typeof (b) _b = (b); \
11c606a6 (kx 2023-04-11 01:18:34 +0300 249) _a > _b ? _a : _b; })
11c606a6 (kx 2023-04-11 01:18:34 +0300 250) #endif
11c606a6 (kx 2023-04-11 01:18:34 +0300 251)
11c606a6 (kx 2023-04-11 01:18:34 +0300 252) /************************************
11c606a6 (kx 2023-04-11 01:18:34 +0300 253) Tree height and width calculation:
11c606a6 (kx 2023-04-11 01:18:34 +0300 254) ─────────────────────────────────
11c606a6 (kx 2023-04-11 01:18:34 +0300 255)
11c606a6 (kx 2023-04-11 01:18:34 +0300 256) height:
11c606a6 (kx 2023-04-11 01:18:34 +0300 257) ┬
11c606a6 (kx 2023-04-11 01:18:34 +0300 258) A │ 1
11c606a6 (kx 2023-04-11 01:18:34 +0300 259) | \ ├
11c606a6 (kx 2023-04-11 01:18:34 +0300 260) B D │ 2
11c606a6 (kx 2023-04-11 01:18:34 +0300 261) | | ├
11c606a6 (kx 2023-04-11 01:18:34 +0300 262) C E │ 3
11c606a6 (kx 2023-04-11 01:18:34 +0300 263) | | \ ├
11c606a6 (kx 2023-04-11 01:18:34 +0300 264) K H F │ 4
11c606a6 (kx 2023-04-11 01:18:34 +0300 265) | \ ├
11c606a6 (kx 2023-04-11 01:18:34 +0300 266) J G │ 5
11c606a6 (kx 2023-04-11 01:18:34 +0300 267) ├──┬──┬──┬──┼
11c606a6 (kx 2023-04-11 01:18:34 +0300 268) width: 1 2 3 4
11c606a6 (kx 2023-04-11 01:18:34 +0300 269)
11c606a6 (kx 2023-04-11 01:18:34 +0300 270) ************************************/
11c606a6 (kx 2023-04-11 01:18:34 +0300 271)
11c606a6 (kx 2023-04-11 01:18:34 +0300 272) int btree_height( struct btree *root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 273) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 274) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 275) int height = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 276)
11c606a6 (kx 2023-04-11 01:18:34 +0300 277) if( !next ) return height;
11c606a6 (kx 2023-04-11 01:18:34 +0300 278)
11c606a6 (kx 2023-04-11 01:18:34 +0300 279) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 280)
11c606a6 (kx 2023-04-11 01:18:34 +0300 281) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 282) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 283) struct btree *p = next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 284) int h = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 285)
11c606a6 (kx 2023-04-11 01:18:34 +0300 286) while( p->parent ) { ++h; p = p->parent; }
11c606a6 (kx 2023-04-11 01:18:34 +0300 287) height = max( height, h );
11c606a6 (kx 2023-04-11 01:18:34 +0300 288)
11c606a6 (kx 2023-04-11 01:18:34 +0300 289) if( next == root ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 290)
11c606a6 (kx 2023-04-11 01:18:34 +0300 291) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 292)
11c606a6 (kx 2023-04-11 01:18:34 +0300 293) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 294)
11c606a6 (kx 2023-04-11 01:18:34 +0300 295) return height + 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 296) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 297)
11c606a6 (kx 2023-04-11 01:18:34 +0300 298) int btree_width( struct btree *root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 299) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 300) int ret = 0, lw = 0, rw = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 301) struct btree *next = NULL, *left = NULL, *right = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 302)
11c606a6 (kx 2023-04-11 01:18:34 +0300 303) if( !root ) return ret;
11c606a6 (kx 2023-04-11 01:18:34 +0300 304)
11c606a6 (kx 2023-04-11 01:18:34 +0300 305) left = next = ( root->ltag ) ? root->left : NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 306)
11c606a6 (kx 2023-04-11 01:18:34 +0300 307) if( next )
11c606a6 (kx 2023-04-11 01:18:34 +0300 308) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 309) ++lw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 310)
11c606a6 (kx 2023-04-11 01:18:34 +0300 311) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 312)
11c606a6 (kx 2023-04-11 01:18:34 +0300 313) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 314) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 315) if( next->ltag && next->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 316) ++lw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 317)
11c606a6 (kx 2023-04-11 01:18:34 +0300 318) if( next == left ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 319)
11c606a6 (kx 2023-04-11 01:18:34 +0300 320) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 321)
11c606a6 (kx 2023-04-11 01:18:34 +0300 322) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 323) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 324)
11c606a6 (kx 2023-04-11 01:18:34 +0300 325) right = next = ( root->rtag ) ? root->right : NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 326)
11c606a6 (kx 2023-04-11 01:18:34 +0300 327) if( next )
11c606a6 (kx 2023-04-11 01:18:34 +0300 328) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 329) ++rw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 330)
11c606a6 (kx 2023-04-11 01:18:34 +0300 331) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 332)
11c606a6 (kx 2023-04-11 01:18:34 +0300 333) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 334) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 335) if( next->ltag && next->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 336) ++rw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 337)
11c606a6 (kx 2023-04-11 01:18:34 +0300 338) if( next == right ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 339)
11c606a6 (kx 2023-04-11 01:18:34 +0300 340) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 341)
11c606a6 (kx 2023-04-11 01:18:34 +0300 342) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 343) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 344)
11c606a6 (kx 2023-04-11 01:18:34 +0300 345) ret = lw + rw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 346)
11c606a6 (kx 2023-04-11 01:18:34 +0300 347) return (ret) ? ret : 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 348) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 349)
11c606a6 (kx 2023-04-11 01:18:34 +0300 350) int btree_left_width( struct btree *root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 351) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 352) int lw = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 353) struct btree *next = NULL, *left = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 354)
11c606a6 (kx 2023-04-11 01:18:34 +0300 355) if( !root ) return lw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 356)
11c606a6 (kx 2023-04-11 01:18:34 +0300 357) left = next = ( root->ltag ) ? root->left : NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 358)
11c606a6 (kx 2023-04-11 01:18:34 +0300 359) if( next )
11c606a6 (kx 2023-04-11 01:18:34 +0300 360) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 361) ++lw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 362)
11c606a6 (kx 2023-04-11 01:18:34 +0300 363) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 364)
11c606a6 (kx 2023-04-11 01:18:34 +0300 365) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 366) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 367) if( next->ltag && next->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 368) ++lw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 369)
11c606a6 (kx 2023-04-11 01:18:34 +0300 370) if( next == left ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 371)
11c606a6 (kx 2023-04-11 01:18:34 +0300 372) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 373)
11c606a6 (kx 2023-04-11 01:18:34 +0300 374) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 375) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 376)
11c606a6 (kx 2023-04-11 01:18:34 +0300 377) return (lw) ? lw : 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 378) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 379)
11c606a6 (kx 2023-04-11 01:18:34 +0300 380) int btree_right_width( struct btree *root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 381) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 382) int rw = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 383) struct btree *next = NULL, *right = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 384)
11c606a6 (kx 2023-04-11 01:18:34 +0300 385) if( !root ) return rw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 386)
11c606a6 (kx 2023-04-11 01:18:34 +0300 387) right = next = ( root->rtag ) ? root->right : NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 388)
11c606a6 (kx 2023-04-11 01:18:34 +0300 389) if( next )
11c606a6 (kx 2023-04-11 01:18:34 +0300 390) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 391) ++rw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 392)
11c606a6 (kx 2023-04-11 01:18:34 +0300 393) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 394)
11c606a6 (kx 2023-04-11 01:18:34 +0300 395) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 396) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 397) if( next->ltag && next->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 398) ++rw;
11c606a6 (kx 2023-04-11 01:18:34 +0300 399)
11c606a6 (kx 2023-04-11 01:18:34 +0300 400) if( next == right ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 401)
11c606a6 (kx 2023-04-11 01:18:34 +0300 402) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 403)
11c606a6 (kx 2023-04-11 01:18:34 +0300 404) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 405) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 406)
11c606a6 (kx 2023-04-11 01:18:34 +0300 407) return (rw) ? rw : 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 408) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 409)
11c606a6 (kx 2023-04-11 01:18:34 +0300 410)
11c606a6 (kx 2023-04-11 01:18:34 +0300 411) struct btree *btree_detach( struct btree *node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 412) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 413) struct btree *parent = node->parent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 414)
11c606a6 (kx 2023-04-11 01:18:34 +0300 415) if( !node ) return node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 416)
11c606a6 (kx 2023-04-11 01:18:34 +0300 417) if( parent->right == node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 418) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 419) struct btree *rlink = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 420)
11c606a6 (kx 2023-04-11 01:18:34 +0300 421) while( rlink->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 422) rlink = rlink->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 423) rlink = rlink->right;
11c606a6 (kx 2023-04-11 01:18:34 +0300 424)
11c606a6 (kx 2023-04-11 01:18:34 +0300 425) parent->right = rlink;
11c606a6 (kx 2023-04-11 01:18:34 +0300 426) parent->rtag = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 427) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 428) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 429) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 430) struct btree *llink = node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 431)
11c606a6 (kx 2023-04-11 01:18:34 +0300 432) while( llink->ltag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 433) llink = llink->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 434) llink = llink->left;
11c606a6 (kx 2023-04-11 01:18:34 +0300 435)
11c606a6 (kx 2023-04-11 01:18:34 +0300 436) parent->left = llink;
11c606a6 (kx 2023-04-11 01:18:34 +0300 437) parent->ltag = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 438) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 439)
11c606a6 (kx 2023-04-11 01:18:34 +0300 440) return node;
11c606a6 (kx 2023-04-11 01:18:34 +0300 441) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 442)
11c606a6 (kx 2023-04-11 01:18:34 +0300 443)
11c606a6 (kx 2023-04-11 01:18:34 +0300 444) void __btree_free( struct btree *root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 445) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 446) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 447)
11c606a6 (kx 2023-04-11 01:18:34 +0300 448) if( !next ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 449)
11c606a6 (kx 2023-04-11 01:18:34 +0300 450) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 451)
11c606a6 (kx 2023-04-11 01:18:34 +0300 452) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 453) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 454) struct btree *tmp = next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 455)
11c606a6 (kx 2023-04-11 01:18:34 +0300 456) if( next == root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 457) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 458) free( tmp );
11c606a6 (kx 2023-04-11 01:18:34 +0300 459) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 460) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 461) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 462) free( tmp );
11c606a6 (kx 2023-04-11 01:18:34 +0300 463)
11c606a6 (kx 2023-04-11 01:18:34 +0300 464) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 465) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 466)
11c606a6 (kx 2023-04-11 01:18:34 +0300 467) void btree_free( struct btree *root, TREE_FUNC free_func )
11c606a6 (kx 2023-04-11 01:18:34 +0300 468) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 469) btree_endorder_traversal( root, free_func, NULL );
11c606a6 (kx 2023-04-11 01:18:34 +0300 470) __btree_free( root );
11c606a6 (kx 2023-04-11 01:18:34 +0300 471) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 472)
11c606a6 (kx 2023-04-11 01:18:34 +0300 473)
11c606a6 (kx 2023-04-11 01:18:34 +0300 474) /*******************************************************************
11c606a6 (kx 2023-04-11 01:18:34 +0300 475) Stack functions:
11c606a6 (kx 2023-04-11 01:18:34 +0300 476) */
11c606a6 (kx 2023-04-11 01:18:34 +0300 477) struct btree_stack *btree_stack_alloc( const size_t n, const size_t u )
11c606a6 (kx 2023-04-11 01:18:34 +0300 478) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 479) struct btree_stack *stack = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 480)
11c606a6 (kx 2023-04-11 01:18:34 +0300 481) if( !n || !u ) return stack;
11c606a6 (kx 2023-04-11 01:18:34 +0300 482)
11c606a6 (kx 2023-04-11 01:18:34 +0300 483) stack = (struct btree_stack *)malloc( sizeof( struct btree_stack ) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 484) if( !stack ) { FATAL_ERROR( "Cannot allocate memory" ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 485) bzero( (void *)stack, sizeof( struct btree_stack ) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 486)
11c606a6 (kx 2023-04-11 01:18:34 +0300 487) stack->__mem_size = n * u;
11c606a6 (kx 2023-04-11 01:18:34 +0300 488) stack->__unit_size = u;
11c606a6 (kx 2023-04-11 01:18:34 +0300 489)
11c606a6 (kx 2023-04-11 01:18:34 +0300 490) stack->__mem = malloc( stack->__mem_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 491) if( !stack->__mem ) { FATAL_ERROR( "Cannot allocate memory" ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 492)
11c606a6 (kx 2023-04-11 01:18:34 +0300 493) bzero( stack->__mem, stack->__mem_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 494) stack->__cur_brk = stack->__mem;
11c606a6 (kx 2023-04-11 01:18:34 +0300 495)
11c606a6 (kx 2023-04-11 01:18:34 +0300 496) return stack;
11c606a6 (kx 2023-04-11 01:18:34 +0300 497) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 498)
11c606a6 (kx 2023-04-11 01:18:34 +0300 499) void btree_stack_free( struct btree_stack **pstack )
11c606a6 (kx 2023-04-11 01:18:34 +0300 500) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 501) struct btree_stack *stack = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 502)
11c606a6 (kx 2023-04-11 01:18:34 +0300 503) if( !pstack ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 504)
11c606a6 (kx 2023-04-11 01:18:34 +0300 505) stack = *pstack;
11c606a6 (kx 2023-04-11 01:18:34 +0300 506)
11c606a6 (kx 2023-04-11 01:18:34 +0300 507) if( !stack ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 508) if( stack->__mem ) free( stack->__mem );
11c606a6 (kx 2023-04-11 01:18:34 +0300 509)
11c606a6 (kx 2023-04-11 01:18:34 +0300 510) free( stack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 511)
11c606a6 (kx 2023-04-11 01:18:34 +0300 512) *pstack = (struct btree_stack *)NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 513) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 514)
11c606a6 (kx 2023-04-11 01:18:34 +0300 515) int btree_stack_is_empty( struct btree_stack *stack )
11c606a6 (kx 2023-04-11 01:18:34 +0300 516) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 517) if( !stack ) return 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 518) if( stack->__mem == stack->__cur_brk ) return 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 519) return 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 520) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 521)
11c606a6 (kx 2023-04-11 01:18:34 +0300 522) int btree_stack_depth( struct btree_stack *stack )
11c606a6 (kx 2023-04-11 01:18:34 +0300 523) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 524) if( !stack ) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 525) if( btree_stack_is_empty( stack ) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 526) return 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 527)
11c606a6 (kx 2023-04-11 01:18:34 +0300 528) return (stack->__cur_brk - stack->__mem) / stack->__unit_size;
11c606a6 (kx 2023-04-11 01:18:34 +0300 529) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 530)
11c606a6 (kx 2023-04-11 01:18:34 +0300 531) static int __stack_brk( struct btree_stack *stack, void *end_d )
11c606a6 (kx 2023-04-11 01:18:34 +0300 532) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 533) void *ptr = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 534)
11c606a6 (kx 2023-04-11 01:18:34 +0300 535) if( !stack ) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 536)
11c606a6 (kx 2023-04-11 01:18:34 +0300 537) ptr = stack->__mem;
11c606a6 (kx 2023-04-11 01:18:34 +0300 538) if( !ptr ) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 539)
11c606a6 (kx 2023-04-11 01:18:34 +0300 540) if( end_d < ptr )
11c606a6 (kx 2023-04-11 01:18:34 +0300 541) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 542) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 543) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 544) if( end_d > ptr + stack->__mem_size )
11c606a6 (kx 2023-04-11 01:18:34 +0300 545) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 546) size_t size = stack->__mem_size + stack->__mem_size;
11c606a6 (kx 2023-04-11 01:18:34 +0300 547)
11c606a6 (kx 2023-04-11 01:18:34 +0300 548) if( (end_d - (ptr + stack->__mem_size)) < stack->__mem_size )
11c606a6 (kx 2023-04-11 01:18:34 +0300 549) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 550) ptrdiff_t offset = stack->__cur_brk - stack->__mem;
11c606a6 (kx 2023-04-11 01:18:34 +0300 551) stack->__mem = realloc( stack->__mem, size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 552) if( !stack->__mem ) { FATAL_ERROR( "Cannot allocate memory" ); }
11c606a6 (kx 2023-04-11 01:18:34 +0300 553) stack->__mem_size = size;
11c606a6 (kx 2023-04-11 01:18:34 +0300 554) stack->__cur_brk = stack->__mem + offset;
11c606a6 (kx 2023-04-11 01:18:34 +0300 555) ptr = stack->__mem;
11c606a6 (kx 2023-04-11 01:18:34 +0300 556) return 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 557) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 558) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 559) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 560) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 561)
11c606a6 (kx 2023-04-11 01:18:34 +0300 562) /*
11c606a6 (kx 2023-04-11 01:18:34 +0300 563) __cur_brk = end_d;
11c606a6 (kx 2023-04-11 01:18:34 +0300 564)
11c606a6 (kx 2023-04-11 01:18:34 +0300 565) The function __stack_brk() only checks boundaries of
11c606a6 (kx 2023-04-11 01:18:34 +0300 566) memory. The value of __cur_brk is set by __stack_sbrk()
11c606a6 (kx 2023-04-11 01:18:34 +0300 567) function.
11c606a6 (kx 2023-04-11 01:18:34 +0300 568) *********************************************************/
11c606a6 (kx 2023-04-11 01:18:34 +0300 569)
11c606a6 (kx 2023-04-11 01:18:34 +0300 570) return 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 571)
11c606a6 (kx 2023-04-11 01:18:34 +0300 572) } /* End of __stack_brk() */
11c606a6 (kx 2023-04-11 01:18:34 +0300 573)
11c606a6 (kx 2023-04-11 01:18:34 +0300 574) static void *__stack_sbrk( struct btree_stack *stack, int incr )
11c606a6 (kx 2023-04-11 01:18:34 +0300 575) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 576) void *ptr = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 577) int rc;
11c606a6 (kx 2023-04-11 01:18:34 +0300 578)
11c606a6 (kx 2023-04-11 01:18:34 +0300 579) if( !stack ) return ptr;
11c606a6 (kx 2023-04-11 01:18:34 +0300 580)
11c606a6 (kx 2023-04-11 01:18:34 +0300 581) ptr = stack->__cur_brk;
11c606a6 (kx 2023-04-11 01:18:34 +0300 582)
11c606a6 (kx 2023-04-11 01:18:34 +0300 583) if( incr == 0 ) return( ptr );
11c606a6 (kx 2023-04-11 01:18:34 +0300 584)
11c606a6 (kx 2023-04-11 01:18:34 +0300 585) rc = __stack_brk( stack, ptr + incr );
11c606a6 (kx 2023-04-11 01:18:34 +0300 586) if( rc == -1 )
11c606a6 (kx 2023-04-11 01:18:34 +0300 587) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 588) /* errno is set into __mpu_brk() */
11c606a6 (kx 2023-04-11 01:18:34 +0300 589) return NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 590) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 591)
11c606a6 (kx 2023-04-11 01:18:34 +0300 592) ptr = stack->__cur_brk;
11c606a6 (kx 2023-04-11 01:18:34 +0300 593) stack->__cur_brk = ptr + (int)incr;
11c606a6 (kx 2023-04-11 01:18:34 +0300 594)
11c606a6 (kx 2023-04-11 01:18:34 +0300 595) return ptr;
11c606a6 (kx 2023-04-11 01:18:34 +0300 596)
11c606a6 (kx 2023-04-11 01:18:34 +0300 597) } /* End of __stack_sbrk() */
11c606a6 (kx 2023-04-11 01:18:34 +0300 598)
11c606a6 (kx 2023-04-11 01:18:34 +0300 599)
11c606a6 (kx 2023-04-11 01:18:34 +0300 600) int btree_stack_push( struct btree_stack *stack, const void *unit )
11c606a6 (kx 2023-04-11 01:18:34 +0300 601) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 602) void *uptr, *ptr = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 603)
11c606a6 (kx 2023-04-11 01:18:34 +0300 604) if( !stack ) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 605)
11c606a6 (kx 2023-04-11 01:18:34 +0300 606) ptr = __stack_sbrk( stack, stack->__unit_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 607)
11c606a6 (kx 2023-04-11 01:18:34 +0300 608) if( ptr )
11c606a6 (kx 2023-04-11 01:18:34 +0300 609) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 610) uptr = memcpy( ptr, unit, stack->__unit_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 611) if( !uptr )
11c606a6 (kx 2023-04-11 01:18:34 +0300 612) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 613) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 614) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 615) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 616) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 617) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 618) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 619) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 620)
11c606a6 (kx 2023-04-11 01:18:34 +0300 621) return 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 622) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 623)
11c606a6 (kx 2023-04-11 01:18:34 +0300 624) int btree_stack_pop( struct btree_stack *stack, void *unit )
11c606a6 (kx 2023-04-11 01:18:34 +0300 625) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 626) void *uptr, *ptr = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 627)
11c606a6 (kx 2023-04-11 01:18:34 +0300 628) if( !stack ) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 629)
11c606a6 (kx 2023-04-11 01:18:34 +0300 630) ptr = __stack_sbrk( stack, -(int)stack->__unit_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 631)
11c606a6 (kx 2023-04-11 01:18:34 +0300 632) if( ptr )
11c606a6 (kx 2023-04-11 01:18:34 +0300 633) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 634) ptr -= stack->__unit_size;
11c606a6 (kx 2023-04-11 01:18:34 +0300 635) uptr = memcpy( unit, (const void *)ptr, stack->__unit_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 636) if( !uptr )
11c606a6 (kx 2023-04-11 01:18:34 +0300 637) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 638) bzero( unit, stack->__unit_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 639) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 640) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 641) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 642) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 643) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 644) bzero( unit, stack->__unit_size );
11c606a6 (kx 2023-04-11 01:18:34 +0300 645) return -1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 646) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 647)
11c606a6 (kx 2023-04-11 01:18:34 +0300 648) return 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 649) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 650) /*
11c606a6 (kx 2023-04-11 01:18:34 +0300 651) End of stack functions.
11c606a6 (kx 2023-04-11 01:18:34 +0300 652) *******************************************************************/
11c606a6 (kx 2023-04-11 01:18:34 +0300 653)
11c606a6 (kx 2023-04-11 01:18:34 +0300 654) static void btree_print_line( const char *line, int indent, const struct _bctx *ctx )
11c606a6 (kx 2023-04-11 01:18:34 +0300 655) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 656) char *p, buf[PATH_MAX*2];
11c606a6 (kx 2023-04-11 01:18:34 +0300 657) int depth = 0, max_depth = PATH_MAX + PATH_MAX / 2;
11c606a6 (kx 2023-04-11 01:18:34 +0300 658)
11c606a6 (kx 2023-04-11 01:18:34 +0300 659) if( !line || !ctx ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 660)
11c606a6 (kx 2023-04-11 01:18:34 +0300 661) if( !indent )
11c606a6 (kx 2023-04-11 01:18:34 +0300 662) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 663) buf[0] = '\0';
11c606a6 (kx 2023-04-11 01:18:34 +0300 664) p = (char *)&buf[0];
11c606a6 (kx 2023-04-11 01:18:34 +0300 665) depth = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 666) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 667) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 668) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 669) buf[0] = ' ';
11c606a6 (kx 2023-04-11 01:18:34 +0300 670) buf[1] = '\0';
11c606a6 (kx 2023-04-11 01:18:34 +0300 671) p = (char *)&buf[1];
11c606a6 (kx 2023-04-11 01:18:34 +0300 672) depth = ctx->indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 673) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 674)
11c606a6 (kx 2023-04-11 01:18:34 +0300 675) if( depth < 1 ) depth = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 676) if( depth > max_depth ) depth = max_depth;
11c606a6 (kx 2023-04-11 01:18:34 +0300 677)
11c606a6 (kx 2023-04-11 01:18:34 +0300 678) while( depth )
11c606a6 (kx 2023-04-11 01:18:34 +0300 679) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 680) (void)sprintf( p, " " ); --depth; ++p; *p = '\0';
11c606a6 (kx 2023-04-11 01:18:34 +0300 681) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 682)
11c606a6 (kx 2023-04-11 01:18:34 +0300 683) (void)sprintf( p, "%s", line );
11c606a6 (kx 2023-04-11 01:18:34 +0300 684)
11c606a6 (kx 2023-04-11 01:18:34 +0300 685) fprintf( ctx->output, (char *)&buf[0] );
11c606a6 (kx 2023-04-11 01:18:34 +0300 686) fflush( ctx->output );
11c606a6 (kx 2023-04-11 01:18:34 +0300 687) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 688)
11c606a6 (kx 2023-04-11 01:18:34 +0300 689)
11c606a6 (kx 2023-04-11 01:18:34 +0300 690) static void __btree_clean_prn_flags( struct btree *root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 691) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 692) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 693)
11c606a6 (kx 2023-04-11 01:18:34 +0300 694) if( !next ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 695)
11c606a6 (kx 2023-04-11 01:18:34 +0300 696) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 697)
11c606a6 (kx 2023-04-11 01:18:34 +0300 698) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 699) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 700) next->lprn = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 701) next->rprn = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 702)
11c606a6 (kx 2023-04-11 01:18:34 +0300 703) if( next == root ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 704)
11c606a6 (kx 2023-04-11 01:18:34 +0300 705) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 706)
11c606a6 (kx 2023-04-11 01:18:34 +0300 707) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 708) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 709)
11c606a6 (kx 2023-04-11 01:18:34 +0300 710) void btree_print_json( FILE *output, struct btree *root, TREE_FUNC func )
11c606a6 (kx 2023-04-11 01:18:34 +0300 711) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 712) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 713) struct _bctx ctx;
11c606a6 (kx 2023-04-11 01:18:34 +0300 714)
11c606a6 (kx 2023-04-11 01:18:34 +0300 715) struct btree_stack *stack;
11c606a6 (kx 2023-04-11 01:18:34 +0300 716) struct btree_stack *lstack;
11c606a6 (kx 2023-04-11 01:18:34 +0300 717)
11c606a6 (kx 2023-04-11 01:18:34 +0300 718) if( !output || !next || !func ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 719)
11c606a6 (kx 2023-04-11 01:18:34 +0300 720) bzero( (void *)&ctx, sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 721)
11c606a6 (kx 2023-04-11 01:18:34 +0300 722) stack = btree_stack_alloc( (const size_t)btree_height(next), sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 723)
11c606a6 (kx 2023-04-11 01:18:34 +0300 724) ctx.output = output;
11c606a6 (kx 2023-04-11 01:18:34 +0300 725) ctx.node = next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 726) ctx.indent = 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 727)
11c606a6 (kx 2023-04-11 01:18:34 +0300 728) __btree_clean_prn_flags( root );
11c606a6 (kx 2023-04-11 01:18:34 +0300 729)
11c606a6 (kx 2023-04-11 01:18:34 +0300 730) btree_stack_push( stack, (const void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 731)
11c606a6 (kx 2023-04-11 01:18:34 +0300 732) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 733) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 734)
11c606a6 (kx 2023-04-11 01:18:34 +0300 735) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 736)
11c606a6 (kx 2023-04-11 01:18:34 +0300 737) func( next->data, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 738)
11c606a6 (kx 2023-04-11 01:18:34 +0300 739) if( ctx.node->ltag || ctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 740) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 741) btree_print_line( ",\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 742) btree_print_line( "\"children\": [\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 743) btree_print_line( " {\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 744) ctx.indent += 2;
11c606a6 (kx 2023-04-11 01:18:34 +0300 745) btree_stack_push( stack, (const void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 746) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 747) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 748) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 749) btree_stack_push( stack, (const void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 750)
11c606a6 (kx 2023-04-11 01:18:34 +0300 751) if( !ctx.node->ltag && !ctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 752) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 753) if( ctx.node->parent )
11c606a6 (kx 2023-04-11 01:18:34 +0300 754) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 755) struct _bctx cctx;
11c606a6 (kx 2023-04-11 01:18:34 +0300 756)
11c606a6 (kx 2023-04-11 01:18:34 +0300 757) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 758)
11c606a6 (kx 2023-04-11 01:18:34 +0300 759) memcpy( (void *)&cctx, (const void *)&ctx, sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 760)
11c606a6 (kx 2023-04-11 01:18:34 +0300 761) if( (ctx.node->lprn == ctx.node->ltag) && (ctx.node->rprn == ctx.node->rtag) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 762) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 763) if( ctx.node->parent->ltag && ctx.node->parent->left == ctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 764) ctx.node->parent->lprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 765) if( ctx.node->parent->rtag && ctx.node->parent->right == ctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 766) ctx.node->parent->rprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 767) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 768)
11c606a6 (kx 2023-04-11 01:18:34 +0300 769) if( btree_stack_depth( stack ) > 0 )
11c606a6 (kx 2023-04-11 01:18:34 +0300 770) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 771) struct btree_stack *pstack = btree_stack_alloc( (const size_t)btree_height(root), sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 772) struct _bctx pctx;
11c606a6 (kx 2023-04-11 01:18:34 +0300 773)
11c606a6 (kx 2023-04-11 01:18:34 +0300 774) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 775) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 776) btree_stack_pop( stack, (void *)&pctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 777)
11c606a6 (kx 2023-04-11 01:18:34 +0300 778) if( (cctx.node->lprn == cctx.node->ltag) && (cctx.node->rprn == cctx.node->rtag) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 779) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 780) if( cctx.node->parent && cctx.node->parent->ltag && cctx.node->parent->left == cctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 781) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 782) cctx.node->parent->lprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 783)
11c606a6 (kx 2023-04-11 01:18:34 +0300 784) if( cctx.node->parent->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 785) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 786) if( !cctx.node->ltag && !cctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 787) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 788) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 789) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 790) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 791) btree_print_line( "},\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 792) btree_print_line( "{\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 793) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 794) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 795) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 796) if( !cctx.node->ltag && !cctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 797) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 798) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 799) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 800) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 801) btree_print_line( "}\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 802) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 803) btree_print_line( "]\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 804) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 805) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 806) if( cctx.node->parent && cctx.node->parent->rtag && cctx.node->parent->right == cctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 807) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 808) cctx.node->parent->rprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 809)
11c606a6 (kx 2023-04-11 01:18:34 +0300 810) if( !cctx.node->ltag && !cctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 811) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 812) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 813) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 814) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 815) btree_print_line( "}\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 816) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 817) btree_print_line( "]\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 818) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 819)
11c606a6 (kx 2023-04-11 01:18:34 +0300 820) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 821)
11c606a6 (kx 2023-04-11 01:18:34 +0300 822) memcpy( (void *)&cctx, (const void *)&pctx, sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 823)
11c606a6 (kx 2023-04-11 01:18:34 +0300 824) if( (pctx.node->ltag && (pctx.node->lprn < pctx.node->ltag)) || (pctx.node->rtag && (pctx.node->rprn < pctx.node->rtag)) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 825) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 826) btree_stack_push( pstack, (const void *)&pctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 827) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 828)
11c606a6 (kx 2023-04-11 01:18:34 +0300 829) } while( !btree_stack_is_empty( stack ) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 830)
11c606a6 (kx 2023-04-11 01:18:34 +0300 831) while( btree_stack_pop( pstack, (void *)&pctx ) == 0 )
11c606a6 (kx 2023-04-11 01:18:34 +0300 832) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 833) btree_stack_push( stack, (const void *)&pctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 834) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 835)
11c606a6 (kx 2023-04-11 01:18:34 +0300 836) btree_stack_free( &pstack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 837) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 838) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 839) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 840) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 841) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 842)
11c606a6 (kx 2023-04-11 01:18:34 +0300 843) } /* End if( parent ) */
11c606a6 (kx 2023-04-11 01:18:34 +0300 844) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 845) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 846) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 847) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 848)
11c606a6 (kx 2023-04-11 01:18:34 +0300 849) } /* End if( no children ) */
11c606a6 (kx 2023-04-11 01:18:34 +0300 850)
11c606a6 (kx 2023-04-11 01:18:34 +0300 851) } /* End if( any child ) */
11c606a6 (kx 2023-04-11 01:18:34 +0300 852)
11c606a6 (kx 2023-04-11 01:18:34 +0300 853)
11c606a6 (kx 2023-04-11 01:18:34 +0300 854) next = __next_preorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 855)
11c606a6 (kx 2023-04-11 01:18:34 +0300 856)
11c606a6 (kx 2023-04-11 01:18:34 +0300 857) if( next != root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 858) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 859) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 860) btree_stack_push( stack, (const void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 861)
11c606a6 (kx 2023-04-11 01:18:34 +0300 862) ctx.output = output;
11c606a6 (kx 2023-04-11 01:18:34 +0300 863) ctx.node = next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 864)
11c606a6 (kx 2023-04-11 01:18:34 +0300 865) if( btree_stack_push( stack, (const void *)&ctx ) == -1 ) FATAL_ERROR( "btree stack is destroyed" );
11c606a6 (kx 2023-04-11 01:18:34 +0300 866) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 867)
11c606a6 (kx 2023-04-11 01:18:34 +0300 868) if( next == root || next == root->right ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 869)
11c606a6 (kx 2023-04-11 01:18:34 +0300 870) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 871)
11c606a6 (kx 2023-04-11 01:18:34 +0300 872)
11c606a6 (kx 2023-04-11 01:18:34 +0300 873) if( next == root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 874) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 875) struct _bctx ctx;
11c606a6 (kx 2023-04-11 01:18:34 +0300 876)
11c606a6 (kx 2023-04-11 01:18:34 +0300 877) ctx.output = output;
11c606a6 (kx 2023-04-11 01:18:34 +0300 878) ctx.node = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 879) ctx.indent = 2;
11c606a6 (kx 2023-04-11 01:18:34 +0300 880)
11c606a6 (kx 2023-04-11 01:18:34 +0300 881) /* If we in root node then there is no right subtree */
11c606a6 (kx 2023-04-11 01:18:34 +0300 882) if( !root->ltag && !root->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 883) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 884) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 885) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 886)
11c606a6 (kx 2023-04-11 01:18:34 +0300 887) if( root->ltag && (root->lprn < root->ltag) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 888) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 889) root->lprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 890)
11c606a6 (kx 2023-04-11 01:18:34 +0300 891) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 892) btree_print_line( "}\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 893) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 894) btree_print_line( "]\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 895) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 896) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 897)
11c606a6 (kx 2023-04-11 01:18:34 +0300 898) if( next == root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 899) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 900) btree_stack_free( &stack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 901) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 902) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 903)
11c606a6 (kx 2023-04-11 01:18:34 +0300 904) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 905) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 906)
11c606a6 (kx 2023-04-11 01:18:34 +0300 907) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 908)
11c606a6 (kx 2023-04-11 01:18:34 +0300 909) func( next->data, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 910)
11c606a6 (kx 2023-04-11 01:18:34 +0300 911) if( ctx.node->ltag || ctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 912) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 913) btree_print_line( ",\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 914) btree_print_line( "\"children\": [\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 915) btree_print_line( " {\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 916) ctx.indent += 2;
11c606a6 (kx 2023-04-11 01:18:34 +0300 917) btree_stack_push( stack, (const void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 918) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 919) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 920) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 921) btree_stack_push( stack, (const void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 922)
11c606a6 (kx 2023-04-11 01:18:34 +0300 923) if( !ctx.node->ltag && !ctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 924) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 925) if( ctx.node->parent )
11c606a6 (kx 2023-04-11 01:18:34 +0300 926) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 927) struct _bctx cctx;
11c606a6 (kx 2023-04-11 01:18:34 +0300 928)
11c606a6 (kx 2023-04-11 01:18:34 +0300 929) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 930)
11c606a6 (kx 2023-04-11 01:18:34 +0300 931) memcpy( (void *)&cctx, (const void *)&ctx, sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 932)
11c606a6 (kx 2023-04-11 01:18:34 +0300 933) if( (ctx.node->lprn == ctx.node->ltag) && (ctx.node->rprn == ctx.node->rtag) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 934) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 935) if( ctx.node->parent->ltag && ctx.node->parent->left == ctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 936) ctx.node->parent->lprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 937) if( ctx.node->parent->rtag && ctx.node->parent->right == ctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 938) ctx.node->parent->rprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 939) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 940)
11c606a6 (kx 2023-04-11 01:18:34 +0300 941) if( btree_stack_depth( stack ) > 0 )
11c606a6 (kx 2023-04-11 01:18:34 +0300 942) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 943) struct btree_stack *pstack = btree_stack_alloc( (const size_t)btree_height(root), sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 944) struct _bctx pctx;
11c606a6 (kx 2023-04-11 01:18:34 +0300 945)
11c606a6 (kx 2023-04-11 01:18:34 +0300 946) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 947) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 948) btree_stack_pop( stack, (void *)&pctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 949)
11c606a6 (kx 2023-04-11 01:18:34 +0300 950) if( (cctx.node->lprn == cctx.node->ltag) && (cctx.node->rprn == cctx.node->rtag) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 951) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 952) if( cctx.node->parent && cctx.node->parent->ltag && cctx.node->parent->left == cctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 953) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 954) cctx.node->parent->lprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 955)
11c606a6 (kx 2023-04-11 01:18:34 +0300 956) if( cctx.node->parent->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 957) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 958) if( !cctx.node->ltag && !cctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 959) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 960) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 961) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 962) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 963) btree_print_line( "},\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 964) btree_print_line( "{\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 965) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 966) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 967) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 968) if( !cctx.node->ltag && !cctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 969) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 970) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 971) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 972) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 973) btree_print_line( "}\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 974) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 975) btree_print_line( "]\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 976) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 977) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 978) if( cctx.node->parent && cctx.node->parent->rtag && cctx.node->parent->right == cctx.node )
11c606a6 (kx 2023-04-11 01:18:34 +0300 979) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 980) cctx.node->parent->rprn = 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 981)
11c606a6 (kx 2023-04-11 01:18:34 +0300 982) if( !cctx.node->ltag && !cctx.node->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 983) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 984) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 985) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 986) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 987) btree_print_line( "}\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 988) --ctx.indent;
11c606a6 (kx 2023-04-11 01:18:34 +0300 989) btree_print_line( "]\n", 1, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 990) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 991)
11c606a6 (kx 2023-04-11 01:18:34 +0300 992) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 993)
11c606a6 (kx 2023-04-11 01:18:34 +0300 994) memcpy( (void *)&cctx, (const void *)&pctx, sizeof(struct _bctx) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 995)
11c606a6 (kx 2023-04-11 01:18:34 +0300 996) if( (pctx.node->ltag && (pctx.node->lprn < pctx.node->ltag)) || (pctx.node->rtag && (pctx.node->rprn < pctx.node->rtag)) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 997) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 998) btree_stack_push( pstack, (const void *)&pctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 999) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1000)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1001) } while( !btree_stack_is_empty( stack ) );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1002)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1003) while( btree_stack_pop( pstack, (void *)&pctx ) == 0 )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1004) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1005) btree_stack_push( stack, (const void *)&pctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1006) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1007)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1008) btree_stack_free( &pstack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1009) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1010) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 1011) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1012) btree_print_line( "\n", 0, &ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1013) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1014)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1015) } /* End if( parent ) */
11c606a6 (kx 2023-04-11 01:18:34 +0300 1016) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 1017) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1018) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1019) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1020)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1021) } /* End if( no children ) */
11c606a6 (kx 2023-04-11 01:18:34 +0300 1022)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1023) } /* End if( any child ) */
11c606a6 (kx 2023-04-11 01:18:34 +0300 1024)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1025)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1026) next = __next_preorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1027)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1028)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1029) if( next != root )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1030) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1031) btree_stack_pop( stack, (void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1032) btree_stack_push( stack, (const void *)&ctx );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1033)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1034) ctx.output = output;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1035) ctx.node = next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1036)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1037) if( btree_stack_push( stack, (const void *)&ctx ) == -1 ) FATAL_ERROR( "btree stack is destroyed" );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1038) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1039)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1040) if( next == root || next == root->right ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1041)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1042) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1043)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1044) btree_stack_free( &stack );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1045) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1046)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1047)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1048) int btree_compare( struct btree *root_a, struct btree *root_b, TREE_CMPF cmp_func )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1049) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1050) struct btree *next_a = root_a, *next_b = root_b;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1051)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1052) if( !next_a || !next_b || !cmp_func ) return 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1053)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1054) next_a = __start_endorder( next_a );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1055) next_b = __start_endorder( next_b );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1056)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1057) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 1058) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1059) if( cmp_func( next_a->data, next_b->data ) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1060) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1061) return 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1062) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1063)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1064) if( next_a == root_a || next_b == root_b )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1065) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1066) if( (next_a == root_a) && (next_b == root_b) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1067) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1068) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 1069) return 1;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1070) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1071)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1072) next_a = __next_endorder( next_a );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1073) next_b = __next_endorder( next_b );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1074)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1075) } while( next_a && next_b );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1076)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1077) return 0;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1078) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1079)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1080)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1081) static void __remove_duplicates( struct btree *root, struct btree *node, TREE_CMPF cmp_func, TREE_FUNC free_func )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1082) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1083) struct btree *next = NULL, *rem = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1084)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1085) if( !root || !node || !cmp_func || node == root ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1086)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1087)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1088) next = __next_endorder( node );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1089)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1090) if( next == root ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1091)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1092) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 1093) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1094) if( !cmp_func( node->data, next->data ) )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1095) rem = next;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1096) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 1097) rem = NULL;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1098)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1099) if( next == root ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1100)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1101) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1102)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1103) if( rem && !rem->ltag && !rem->rtag )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1104) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1105) struct btree *node = btree_detach( rem );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1106)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1107) if( free_func )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1108) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1109) btree_free( node, free_func );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1110) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1111) else
11c606a6 (kx 2023-04-11 01:18:34 +0300 1112) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1113) __btree_free( node );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1114) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1115) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1116)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1117) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1118) }
11c606a6 (kx 2023-04-11 01:18:34 +0300 1119)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1120) void btree_reduce( struct btree *root, TREE_CMPF cmp_func, TREE_FUNC free_func )
11c606a6 (kx 2023-04-11 01:18:34 +0300 1121) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1122) struct btree *next = root;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1123)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1124) if( !next || ! cmp_func ) return;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1125)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1126) next = __start_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1127)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1128) do
11c606a6 (kx 2023-04-11 01:18:34 +0300 1129) {
11c606a6 (kx 2023-04-11 01:18:34 +0300 1130) __remove_duplicates( root, next, cmp_func, free_func );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1131)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1132) if( next == root ) break;
11c606a6 (kx 2023-04-11 01:18:34 +0300 1133)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1134) next = __next_endorder( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1135)
11c606a6 (kx 2023-04-11 01:18:34 +0300 1136) } while( next );
11c606a6 (kx 2023-04-11 01:18:34 +0300 1137) }
Radix cross Linux package tools
Package Tools – is a set of utilities to create, install, and update RcL packages
3 Commits
0 Branches
2 Tags