Mercurial > hg > GearsTemplate
diff src/llrb/verifier/verify_put_cs.c @ 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 |
line wrap: on
line diff
--- 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); - } -}