Mercurial > hg > Gears > GearsAgda

comparison src/parallel_execution/verifier/llrbContextWithVerifier.c @ 284:e6bc0a4c2c36

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
generate C_start_code and C_exit_code
author mir3636
date Sun, 05 Feb 2017 19:08:22 +0900
parents src/llrb/verifier/llrbContextWithVerifier.c@870453d5b096
children
comparison
equal deleted inserted replaced
283:2b41bd298fe8 284:e6bc0a4c2c36
1 #include <stdio.h>
2 #include "llrbContextWithVerifier.h"
3
4 unsigned int min_height(struct Node* node, unsigned int height) {
5 if ((node->left == NULL) && (node->right == NULL)) return height;
6 if (node->left == NULL) return min_height(node->right, height+1);
7 if (node->right == NULL) return min_height(node->left, height+1);
8
9 unsigned int left_min = min_height(node->left, height+1);
10 unsigned int right_min = min_height(node->right, height+1);
11
12 if (left_min < right_min) {
13 return left_min;
14 } else {
15 return right_min;
16 }
17 }
18
19 unsigned int max_height(struct Node* node, unsigned int height) {
20 if ((node->left == NULL) && (node->right == NULL)) return height;
21 if (node->left == NULL) return max_height(node->right, height+1);
22 if (node->right == NULL) return max_height(node->left, height+1);
23
24 unsigned int left_max = max_height(node->left, height+1);
25 unsigned int right_max = max_height(node->right, height+1);
26
27 if (left_max > right_max) {
28 return left_max;
29 } else {
30 return right_max;
31 }
32 }
33
34 void verify_tree_height(struct Node* root) {
35 if (root == NULL) return;
36
37 unsigned int min_h = min_height(root, 1);
38 unsigned int max_h = max_height(root, 1);
39
40 if (max_h >= 2*min_h) {
41 printf("llrb-condition violated.\n");
42 printf("\tmin-height %u", min_h);
43 printf("\tmax-height %u", max_h);
44 exit(EXIT_FAILURE);
45 }
46 }