Mercurial > hg > GearsTemplate

annotate src/parallel_execution/verifier/llrbContextWithVerifier.c @ 458:3025d00eb87d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Thu, 14 Dec 2017 07:44:58 +0900
parents e6bc0a4c2c36
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
105
870453d5b096 Reduce warnings
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 100
diff changeset
1 #include <stdio.h>
100
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include "llrbContextWithVerifier.h"
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 unsigned int min_height(struct Node* node, unsigned int height) {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 if ((node->left == NULL) && (node->right == NULL)) return height;
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 if (node->left == NULL) return min_height(node->right, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 if (node->right == NULL) return min_height(node->left, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 unsigned int left_min = min_height(node->left, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 unsigned int right_min = min_height(node->right, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 if (left_min < right_min) {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 return left_min;
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 } else {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 return right_min;
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 }
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 }
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 unsigned int max_height(struct Node* node, unsigned int height) {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 if ((node->left == NULL) && (node->right == NULL)) return height;
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 if (node->left == NULL) return max_height(node->right, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 if (node->right == NULL) return max_height(node->left, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 unsigned int left_max = max_height(node->left, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 unsigned int right_max = max_height(node->right, height+1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 if (left_max > right_max) {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 return left_max;
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 } else {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 return right_max;
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 }
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 }
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 void verify_tree_height(struct Node* root) {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 if (root == NULL) return;
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 unsigned int min_h = min_height(root, 1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 unsigned int max_h = max_height(root, 1);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 if (max_h >= 2*min_h) {
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 printf("llrb-condition violated.\n");
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 printf("\tmin-height %u", min_h);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 printf("\tmax-height %u", max_h);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 exit(EXIT_FAILURE);
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 }
3d7ecced7e14 Split functions which gets tree height
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 }