Mercurial > hg > Members > innparusu > Gears
changeset 99:ca55f4be5f0f
Create verifier directory
author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 02 Feb 2016 16:02:55 +0900 |
parents | d400948dbbab |
children | 3d7ecced7e14 |
files | src/llrb/CMakeLists.txt src/llrb/verifier/verify_put_cs.c src/llrb/verify_put_cs.c |
diffstat | 3 files changed, 76 insertions(+), 76 deletions(-) [+] |
line wrap: on
line diff
--- a/src/llrb/CMakeLists.txt Mon Feb 01 18:03:43 2016 +0900 +++ b/src/llrb/CMakeLists.txt Tue Feb 02 16:02:55 2016 +0900 @@ -22,5 +22,5 @@ allocate.c compare.c stack.c - verify_put_cs.c + verifier/verify_put_cs.c )
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/llrb/verifier/verify_put_cs.c Tue Feb 02 16:02:55 2016 +0900 @@ -0,0 +1,75 @@ +/* Verification of LLRB-Tree height in put operations. + * LLRB-Tree allows (max-height) <= 2*(min-height). + */ + +#include <stdlib.h> +#include <stdio.h> +#include <time.h> +#include "../llrbContext.h" + +void verify_tree_height(struct Node*); + +__code meta(struct Context* context, enum Code next) { + if (next == Put) { + verify_tree_height(context->data[Tree]->tree.root); + } + goto (context->code[next])(context); +} + +__code start_code(struct Context* context, enum Code next) { + unsigned int seed = (unsigned int)time(NULL); + + printf("--- srand(%u)\n", seed); + goto meta(context, next); +} + +__code exit_code(struct Context* context) { + free(context->code); + free(context->data); + 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); + } +}
--- a/src/llrb/verify_put_cs.c Mon Feb 01 18:03:43 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,75 +0,0 @@ -/* Verification of LLRB-Tree height in put operations. - * LLRB-Tree allows (max-height) <= 2*(min-height). - */ - -#include <stdlib.h> -#include <stdio.h> -#include <time.h> -#include "llrbContext.h" - -void verify_tree_height(struct Node*); - -__code meta(struct Context* context, enum Code next) { - if (next == Put) { - verify_tree_height(context->data[Tree]->tree.root); - } - goto (context->code[next])(context); -} - -__code start_code(struct Context* context, enum Code next) { - unsigned int seed = (unsigned int)time(NULL); - - printf("--- srand(%u)\n", seed); - goto meta(context, next); -} - -__code exit_code(struct Context* context) { - free(context->code); - free(context->data); - 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); - } -}