Mercurial > hg > Members > innparusu > Gears
changeset 100:3d7ecced7e14
Split functions which gets tree height
author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 02 Feb 2016 16:12:34 +0900 |
parents | ca55f4be5f0f |
children | 8987cf13d5bb |
files | src/llrb/CMakeLists.txt src/llrb/verifier/llrbContextWithVerifier.c src/llrb/verifier/llrbContextWithVerifier.h src/llrb/verifier/verify_put_cs.c |
diffstat | 4 files changed, 52 insertions(+), 47 deletions(-) [+] |
line wrap: on
line diff
--- a/src/llrb/CMakeLists.txt Tue Feb 02 16:02:55 2016 +0900 +++ b/src/llrb/CMakeLists.txt Tue Feb 02 16:12:34 2016 +0900 @@ -22,5 +22,6 @@ allocate.c compare.c stack.c + verifier/llrbContextWithVerifier.c verifier/verify_put_cs.c )
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/llrb/verifier/llrbContextWithVerifier.c Tue Feb 02 16:12:34 2016 +0900 @@ -0,0 +1,45 @@ +#include "llrbContextWithVerifier.h" + +unsigned int min_height(struct Node* node, unsigned int height) { + if ((node->left == NULL) && (node->right == NULL)) return height; + if (node->left == NULL) return min_height(node->right, height+1); + if (node->right == NULL) return min_height(node->left, height+1); + + unsigned int left_min = min_height(node->left, height+1); + unsigned int right_min = min_height(node->right, height+1); + + if (left_min < right_min) { + return left_min; + } else { + return right_min; + } +} + +unsigned int max_height(struct Node* node, unsigned int height) { + if ((node->left == NULL) && (node->right == NULL)) return height; + if (node->left == NULL) return max_height(node->right, height+1); + if (node->right == NULL) return max_height(node->left, height+1); + + unsigned int left_max = max_height(node->left, height+1); + unsigned int right_max = max_height(node->right, height+1); + + if (left_max > right_max) { + return left_max; + } else { + return right_max; + } +} + +void verify_tree_height(struct Node* root) { + if (root == NULL) return; + + unsigned int min_h = min_height(root, 1); + unsigned int max_h = max_height(root, 1); + + if (max_h >= 2*min_h) { + printf("llrb-condition violated.\n"); + printf("\tmin-height %u", min_h); + printf("\tmax-height %u", max_h); + exit(EXIT_FAILURE); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/llrb/verifier/llrbContextWithVerifier.h Tue Feb 02 16:12:34 2016 +0900 @@ -0,0 +1,5 @@ +#include "../llrbContext.h" + +unsigned int min_height(struct Node* node, unsigned int height); +unsigned int max_height(struct Node* node, unsigned int height); +void verify_tree_height(struct Node* root);
--- a/src/llrb/verifier/verify_put_cs.c Tue Feb 02 16:02:55 2016 +0900 +++ b/src/llrb/verifier/verify_put_cs.c Tue Feb 02 16:12:34 2016 +0900 @@ -5,9 +5,7 @@ #include <stdlib.h> #include <stdio.h> #include <time.h> -#include "../llrbContext.h" - -void verify_tree_height(struct Node*); +#include "llrbContextWithVerifier.h" __code meta(struct Context* context, enum Code next) { if (next == Put) { @@ -29,47 +27,3 @@ free(context->heapStart); goto exit(0); } - -unsigned int min_height(struct Node* node, unsigned int height) { - if ((node->left == NULL) && (node->right == NULL)) return height; - if (node->left == NULL) return min_height(node->right, height+1); - if (node->right == NULL) return min_height(node->left, height+1); - - unsigned int left_min = min_height(node->left, height+1); - unsigned int right_min = min_height(node->right, height+1); - - if (left_min < right_min) { - return left_min; - } else { - return right_min; - } -} - -unsigned int max_height(struct Node* node, unsigned int height) { - if ((node->left == NULL) && (node->right == NULL)) return height; - if (node->left == NULL) return max_height(node->right, height+1); - if (node->right == NULL) return max_height(node->left, height+1); - - unsigned int left_max = max_height(node->left, height+1); - unsigned int right_max = max_height(node->right, height+1); - - if (left_max > right_max) { - return left_max; - } else { - return right_max; - } -} - -void verify_tree_height(struct Node* root) { - if (root == NULL) return; - - unsigned int min_h = min_height(root, 1); - unsigned int max_h = max_height(root, 1); - - if (max_h >= 2*min_h) { - printf("llrb-condition violated.\n"); - printf("\tmin-height %u", min_h); - printf("\tmax-height %u", max_h); - exit(EXIT_FAILURE); - } -}