diff options
author | Zhizhou Yang <zhizhouy@google.com> | 2017-07-21 16:06:55 -0700 |
---|---|---|
committer | Zhizhou Yang <zhizhouy@google.com> | 2017-07-21 16:10:53 -0700 |
commit | 4307f4735e9a4e3189e8d43f7493bb677a4d06ba (patch) | |
tree | bf139ee25415cecde142e95791edba3803b2452a /binary_search_tool/full_bisect_test | |
parent | 7091edfaa0ec531905b7d914e9307cd74caf02ea (diff) | |
parent | 978b96a8b02935d40e3a2c57cd033dbedd8980e9 (diff) | |
download | toolchain-utils-4307f4735e9a4e3189e8d43f7493bb677a4d06ba.tar.gz |
Merge branch 'aosp/mirror-chromium-master' into update_utilsandroid-o-iot-preview-5o-iot-preview-5
Update toolchain_utils from ChromeOS side, which includes: initializing
Android toolchain benchmark suite and other changes since last merging.
Bug: None.
Test: None.
Change-Id: I9cd74f4377a8109872414636342be0b9f5df2db5
Diffstat (limited to 'binary_search_tool/full_bisect_test')
29 files changed, 835 insertions, 0 deletions
diff --git a/binary_search_tool/full_bisect_test/bad-objects-permanent/_LIST b/binary_search_tool/full_bisect_test/bad-objects-permanent/_LIST new file mode 100644 index 00000000..07bc1aa9 --- /dev/null +++ b/binary_search_tool/full_bisect_test/bad-objects-permanent/_LIST @@ -0,0 +1,7 @@ +build.o +inorder_norecurse.o +inorder.o +main.o +preorder_norecurse.o +preorder.o +stack.o diff --git a/binary_search_tool/full_bisect_test/bad-output-1.txt b/binary_search_tool/full_bisect_test/bad-output-1.txt new file mode 100644 index 00000000..dfd0bfc6 --- /dev/null +++ b/binary_search_tool/full_bisect_test/bad-output-1.txt @@ -0,0 +1,11 @@ +pre-order traversal, with recursion: +35 28 20 25 23 26 30 60 70 65 64 68 + +pre-order traversal, without recursion: +35 28 20 25 23 26 30 60 70 65 64 68 + +in-order traversal, with recursion: +20 23 25 26 28 30 35 60 64 65 68 70 + +in-order traversal, without recursion: +28 30 35 60 65 68 70 diff --git a/binary_search_tool/full_bisect_test/bad-output-2.txt b/binary_search_tool/full_bisect_test/bad-output-2.txt new file mode 100644 index 00000000..e35ebddc --- /dev/null +++ b/binary_search_tool/full_bisect_test/bad-output-2.txt @@ -0,0 +1,11 @@ +pre-order traversal, with recursion: +35 28 20 25 23 26 30 60 70 65 64 68 + +pre-order traversal, without recursion: +35 60 70 + +in-order traversal, with recursion: +20 23 25 26 28 30 35 60 64 65 68 70 + +in-order traversal, without recursion: +20 23 25 26 28 30 35 60 64 65 68 70 diff --git a/binary_search_tool/full_bisect_test/bad-output-3.txt b/binary_search_tool/full_bisect_test/bad-output-3.txt new file mode 100644 index 00000000..5f3bfef5 --- /dev/null +++ b/binary_search_tool/full_bisect_test/bad-output-3.txt @@ -0,0 +1,11 @@ +pre-order traversal, with recursion: +35 28 20 25 23 26 30 60 70 65 64 68 + +pre-order traversal, without recursion: +35 60 70 + +in-order traversal, with recursion: +20 23 25 26 28 30 35 60 64 65 68 70 + +in-order traversal, without recursion: +28 30 35 60 65 68 70 diff --git a/binary_search_tool/full_bisect_test/bin-trees.h b/binary_search_tool/full_bisect_test/bin-trees.h new file mode 100644 index 00000000..1c4fa199 --- /dev/null +++ b/binary_search_tool/full_bisect_test/bin-trees.h @@ -0,0 +1,29 @@ +#ifndef _BIN_TREES_H +#define _BIN_TREES_H + + +struct bin_tree_struct { + int data; + char c_data; + struct bin_tree_struct *left; + struct bin_tree_struct *right; +}; + +typedef struct bin_tree_struct * tree_ptr; + + +struct stack_struct { + tree_ptr data; + struct stack_struct *next; +}; + + +void search_tree_insert (tree_ptr *, int); +void pre_order_traverse (tree_ptr); +void pre_order_traverse_no_recurse (tree_ptr); +void in_order_traverse (tree_ptr); +void in_order_traverse_no_recurse (tree_ptr); +void push (struct stack_struct **, tree_ptr); +tree_ptr pop (struct stack_struct **); + +#endif /* _BIN_TREES_H */ diff --git a/binary_search_tool/full_bisect_test/build.c b/binary_search_tool/full_bisect_test/build.c new file mode 100644 index 00000000..ea1c8b49 --- /dev/null +++ b/binary_search_tool/full_bisect_test/build.c @@ -0,0 +1,23 @@ +#include <stdlib.h> +#include "bin-trees.h" + +tree_ptr +new_node (int value) +{ + tree_ptr node = (tree_ptr) malloc (sizeof (tree_ptr)); + node->data = value; + node->left = NULL; + node->right = NULL; + return node; +} + +void +search_tree_insert (tree_ptr *root, int value) +{ + if (*root == NULL) + *root = new_node (value); + else if (value < (*root)->data) + search_tree_insert (&((*root)->left), value); + else if (value > (*root)->data) + search_tree_insert (&((*root)->right), value); +} diff --git a/binary_search_tool/full_bisect_test/build.sh b/binary_search_tool/full_bisect_test/build.sh new file mode 100755 index 00000000..9d40fb55 --- /dev/null +++ b/binary_search_tool/full_bisect_test/build.sh @@ -0,0 +1,22 @@ +#!/bin/bash + +# This file compiles all the source files into .o files, then links them to form +# the test binary, 'bin-trees'. The .o files all go into the 'work' directory. +# There are 'good' and 'bad' versions of inorder_norecurse and preorder_norecurse +# (e.g. inorder_norecurse.c.good and inorder_norecurse.c.bad). This script +# assumes that the desired versions of those files have been copied into +# inorder_norecurse.c and preorder_norecurse.c. The script files +# make_sources_good.sh and make_sources_bad.sh are meant to handle this. +# +# This script is meant to be run directly in the full_bisect_test directory. +# Most other scripts assume they are being run from the parent directory. + +gcc -c build.c -o work/build.o +gcc -c preorder.c -o work/preorder.o +gcc -c inorder.c -o work/inorder.o +gcc -c main.c -o work/main.o +gcc -c stack.c -o work/stack.o +gcc -c preorder_norecurse.c -o work/preorder_norecurse.o +gcc -c inorder_norecurse.c -o work/inorder_norecurse.o +gcc -o bin-trees work/main.o work/preorder.o work/inorder.o work/build.o work/preorder_norecurse.o work/inorder_norecurse.o work/stack.o + diff --git a/binary_search_tool/full_bisect_test/chromeos_build.sh b/binary_search_tool/full_bisect_test/chromeos_build.sh new file mode 100755 index 00000000..f072bd07 --- /dev/null +++ b/binary_search_tool/full_bisect_test/chromeos_build.sh @@ -0,0 +1,21 @@ +#!/bin/bash + +# This file compiles all the source files into .o files, then links them to form +# the test binary, 'bin-trees'. The .o files all go into the 'work' directory. +# There are 'good' and 'bad' versions of inorder_norecurse and preorder_norecurse +# (e.g. inorder_norecurse.c.good and inorder_norecurse.c.bad). This script +# assumes that the desired versions of those files have been copied into +# inorder_norecurse.c and preorder_norecurse.c. The script files +# make_sources_good.sh and make_sources_bad.sh are meant to handle this. +# +# This script is meant to be run directly in the full_bisect_test directory. +# Most other scripts assume they are being run from the parent directory. + +x86_64-cros-linux-gnu-gcc -c build.c -o work/build.o +x86_64-cros-linux-gnu-gcc -c preorder.c -o work/preorder.o +x86_64-cros-linux-gnu-gcc -c inorder.c -o work/inorder.o +x86_64-cros-linux-gnu-gcc -c main.c -o work/main.o +x86_64-cros-linux-gnu-gcc -c stack.c -o work/stack.o +x86_64-cros-linux-gnu-gcc -c preorder_norecurse.c -o work/preorder_norecurse.o +x86_64-cros-linux-gnu-gcc -c inorder_norecurse.c -o work/inorder_norecurse.o +x86_64-cros-linux-gnu-gcc -o bin-trees work/main.o work/preorder.o work/inorder.o work/build.o work/preorder_norecurse.o work/inorder_norecurse.o work/stack.o diff --git a/binary_search_tool/full_bisect_test/cleanup.sh b/binary_search_tool/full_bisect_test/cleanup.sh new file mode 100755 index 00000000..48b44f30 --- /dev/null +++ b/binary_search_tool/full_bisect_test/cleanup.sh @@ -0,0 +1,8 @@ +#!/bin/bash + +# In keeping with the normal way of doing bisectin, this script is meant to +# remove files specific to the particular run of the bisector. +# +# This file is called from main-bisect-test.sh + +rm full_bisect_test/common.sh diff --git a/binary_search_tool/full_bisect_test/get_initial_items.sh b/binary_search_tool/full_bisect_test/get_initial_items.sh new file mode 100755 index 00000000..4c4043f1 --- /dev/null +++ b/binary_search_tool/full_bisect_test/get_initial_items.sh @@ -0,0 +1,9 @@ +#!/bin/bash -u +# +# This is one of the test scripts that needs to be passed to +# binary_search_state.py. + +source full_bisect_test/common.sh + +cat ${BISECT_GOOD_BUILD}/_LIST + diff --git a/binary_search_tool/full_bisect_test/good-objects-permanent/_LIST b/binary_search_tool/full_bisect_test/good-objects-permanent/_LIST new file mode 100644 index 00000000..07bc1aa9 --- /dev/null +++ b/binary_search_tool/full_bisect_test/good-objects-permanent/_LIST @@ -0,0 +1,7 @@ +build.o +inorder_norecurse.o +inorder.o +main.o +preorder_norecurse.o +preorder.o +stack.o diff --git a/binary_search_tool/full_bisect_test/good-output.txt b/binary_search_tool/full_bisect_test/good-output.txt new file mode 100644 index 00000000..4db15eb2 --- /dev/null +++ b/binary_search_tool/full_bisect_test/good-output.txt @@ -0,0 +1,11 @@ +pre-order traversal, with recursion: +35 28 20 25 23 26 30 60 70 65 64 68 + +pre-order traversal, without recursion: +35 28 20 25 23 26 30 60 70 65 64 68 + +in-order traversal, with recursion: +20 23 25 26 28 30 35 60 64 65 68 70 + +in-order traversal, without recursion: +20 23 25 26 28 30 35 60 64 65 68 70 diff --git a/binary_search_tool/full_bisect_test/inorder.c b/binary_search_tool/full_bisect_test/inorder.c new file mode 100644 index 00000000..ad093f3c --- /dev/null +++ b/binary_search_tool/full_bisect_test/inorder.c @@ -0,0 +1,22 @@ +#include <stdio.h> +#include <stdlib.h> +#include "bin-trees.h" + +static void +real_inorder (tree_ptr root) +{ + if (root == NULL) + return; + + real_inorder (root->left); + printf ("%d ", root->data); + real_inorder (root->right); +} + +void +in_order_traverse (tree_ptr root) +{ + printf ("in-order traversal, with recursion: \n"); + real_inorder (root); + printf ("\n"); +} diff --git a/binary_search_tool/full_bisect_test/inorder_norecurse.c.bad b/binary_search_tool/full_bisect_test/inorder_norecurse.c.bad new file mode 100644 index 00000000..27f0bb16 --- /dev/null +++ b/binary_search_tool/full_bisect_test/inorder_norecurse.c.bad @@ -0,0 +1,42 @@ +#include <stdlib.h> +#include <stdio.h> +#include "bin-trees.h" + +static void +real_in_order_traverse_no_recurse (tree_ptr root) +{ + struct stack_struct *stack = NULL; + tree_ptr current= root; + int going_left = 1; /* boolean variable */ + while (current != NULL) + { + if ((current->left != NULL) && going_left) + { + push (&stack, current); + current = current->left; + } + + printf ("%d ", current->data); + if (current->right) + { + current = current->right; + going_left = 1; + } + else if (stack != NULL) + { + current = pop(&stack); + going_left = 0; + } + else + current = NULL; + } +} + +void +in_order_traverse_no_recurse (tree_ptr root) +{ + printf ("in-order traversal, without recursion: \n"); + real_in_order_traverse_no_recurse (root); + printf ("\n"); + return; +} diff --git a/binary_search_tool/full_bisect_test/inorder_norecurse.c.good b/binary_search_tool/full_bisect_test/inorder_norecurse.c.good new file mode 100644 index 00000000..a03f4818 --- /dev/null +++ b/binary_search_tool/full_bisect_test/inorder_norecurse.c.good @@ -0,0 +1,42 @@ +#include <stdlib.h> +#include <stdio.h> +#include "bin-trees.h" + +static void +real_in_order_traverse_no_recurse (tree_ptr root) +{ + struct stack_struct *stack = NULL; + tree_ptr current= root; + int going_left = 1; /* boolean variable */ + while (current != NULL) + { + while ((current->left != NULL) && going_left) + { + push (&stack, current); + current = current->left; + } + + printf ("%d ", current->data); + if (current->right) + { + current = current->right; + going_left = 1; + } + else if (stack != NULL) + { + current = pop(&stack); + going_left = 0; + } + else + current = NULL; + } +} + +void +in_order_traverse_no_recurse (tree_ptr root) +{ + printf ("in-order traversal, without recursion: \n"); + real_in_order_traverse_no_recurse (root); + printf ("\n"); + return; +} diff --git a/binary_search_tool/full_bisect_test/interactive_test.sh b/binary_search_tool/full_bisect_test/interactive_test.sh new file mode 100755 index 00000000..064e4ae5 --- /dev/null +++ b/binary_search_tool/full_bisect_test/interactive_test.sh @@ -0,0 +1,56 @@ +#!/bin/bash -u +# +# This script is one of the required scripts that get passed to +# binary_search_state.py. It's job is to test the executable that +# was generated by mixing/matching good & bad object files, and determine +# whether the resulting binary is good or bad. +# +# In this particular case, the generated binary is 'bin-trees'. This +# script runs the binary, captures its output, and compares the output +# to a file containg the correct (good) output, and three files containing +# what the bad output might look like, depending on if one of the two +# possile bad .o files was used, or if both bad .o files were used. +# +# If the output matches the known good output, this returns 0. +# If the output matches any known bad output, this returns 1. +# If the output does not match the good or bad outputs, this returns 125. +# + +source full_bisect_test/common.sh + +full_bisect_test/bin-trees > full_bisect_test/temp_output.txt + +diff full_bisect_test/temp_output.txt full_bisect_test/good-output.txt &> /dev/null +retval=$? + +if [[ ${retval} -eq 0 ]]; then + rm -f full_bisect_test/temp_output.txt + exit 0 +fi + +diff full_bisect_test/temp_output.txt full_bisect_test/bad-output-1.txt &> /dev/null +retval=$? + +if [[ ${retval} -eq 0 ]]; then + rm -f full_bisect_test/temp_output.txt + exit 1 +else + diff full_bisect_test/temp_output.txt full_bisect_test/bad-output-2.txt &> /dev/null + retval=$? + if [[ ${retval} -eq 0 ]]; then + rm -f full_bisect_test/temp_output.txt + exit 1 + else + diff full_bisect_test/temp_output.txt full_bisect_test/bad-output-3.txt &> /dev/null + retval=$? + if [[ ${retval} -eq 0 ]]; then + rm -f full_bisect_test/temp_output.txt + exit 1 + fi + fi +fi + +rm -f full_bisect_test/temp_output.txt +exit 125 + + diff --git a/binary_search_tool/full_bisect_test/main-bisect-test.sh b/binary_search_tool/full_bisect_test/main-bisect-test.sh new file mode 100755 index 00000000..af01c19c --- /dev/null +++ b/binary_search_tool/full_bisect_test/main-bisect-test.sh @@ -0,0 +1,104 @@ +#!/bin/bash +# +# This script is the heart of the bisection test. It assumes the good-objects +# and bad-objects directories have been created and populated. It runs three +# bisection tests: +# Test 1. use --file_args, and no pruning, which passes the object file list +# in a file, and stops as soon as it finds the first bad file. +# Test 2. do not use --file_args, and no pruning. The object files are passed +# directly on the command line; stop as soon as it finds the first +# bad file. +# Test 3. use --file_args and --prune. Pass the object file list in a file +# and run until it finds ALL the bad files (there are two of them). +# + +SAVE_DIR=`pwd` + +DIR=full_bisect_test + +# Make sure you are running this script from the parent directory. +if [[ ! -f "${DIR}/setup.sh" ]] ; then + echo "Cannot find ${DIR}/setup.sh. You are running this from the wrong directory." + echo "You need to run this from toolchain-utils/binary_search_tool ." + exit 1 +fi + +# Run Test 1. +${DIR}/setup.sh + +./binary_search_state.py --get_initial_items="${DIR}/get_initial_items.sh" \ + --switch_to_good="${DIR}/switch_to_good.sh" \ + --switch_to_bad="${DIR}/switch_to_bad.sh" \ + --test_setup_script="${DIR}/test_setup.sh" \ + --test_script="${DIR}/interactive_test.sh" \ + --file_args &> /tmp/full_bisect_test.log + +${DIR}/cleanup.sh + +grep "Search complete. First bad version: " /tmp/full_bisect_test.log &> /dev/null +test_status=$? + +if [[ ${test_status} -ne 0 ]] ; then + echo "Test 1 FAILED. See /tmp/full_bisect_test.log for details." + exit 1 +else + echo "Test 1 passed." +fi + +cd ${SAVE_DIR} + +# Run Test 2. +${DIR}/setup.sh + +./binary_search_state.py --get_initial_items="${DIR}/get_initial_items.sh" \ + --switch_to_good="${DIR}/switch_to_good.sh" \ + --switch_to_bad="${DIR}/switch_to_bad.sh" \ + --test_setup_script="${DIR}/test_setup.sh" \ + --test_script="${DIR}/interactive_test.sh" \ + &> /tmp/full_bisect_test.log + +${DIR}/cleanup.sh + +grep "Search complete. First bad version: " /tmp/full_bisect_test.log &> /dev/null +test_status=$? + +if [[ ${test_status} -ne 0 ]] ; then + echo "Test 2 FAILED. See /tmp/full_bisect_test.log for details." + exit 1 +else + echo "Test 2 passed." +fi + +cd ${SAVE_DIR} + +# Run Test 3. +${DIR}/setup.sh + +./binary_search_state.py --get_initial_items="${DIR}/get_initial_items.sh" \ + --switch_to_good="${DIR}/switch_to_good.sh" \ + --switch_to_bad="${DIR}/switch_to_bad.sh" \ + --test_setup_script="${DIR}/test_setup.sh" \ + --test_script="${DIR}/interactive_test.sh" \ + --file_args --prune &> /tmp/full_bisect_test.log + +${DIR}/cleanup.sh + +grep "Bad items are: " /tmp/full_bisect_test.log | grep inorder_norecurse.o &> /dev/null +test_status_1=$? + +grep "Bad items are: " /tmp/full_bisect_test.log | grep preorder_norecurse.o &> /dev/null +test_status_2=$? + +if [[ ${test_status_1} -ne 0 ]] ; then + echo "Test 3 FAILED. See /tmp/full_bisect_test.log for details." + exit 1 +elif [[ ${test_status_2} -ne 0 ]] ; then + echo "Test 3 FAILED. See /tmp/full_bisect_test.log for details." + exit 1 +else + echo "Test 3 passed." +fi + +# All tests passed! +exit 0 + diff --git a/binary_search_tool/full_bisect_test/main.c b/binary_search_tool/full_bisect_test/main.c new file mode 100644 index 00000000..55abc44b --- /dev/null +++ b/binary_search_tool/full_bisect_test/main.c @@ -0,0 +1,30 @@ +#include <stdlib.h> +#include <stdio.h> +#include "bin-trees.h" + +int integers[] = {35, 28, 20, 30, 25, 23, 26, 60, 70, 65, 64, 68 }; + +char pre_order[] = { '/', '-', '+', '*', 'a', '^', 'x', '2', '&', 'b', 'y', + 'c', '3' }; +char in_order[] = { 'a', '*', 'x', '^', '2', '+', 'b', '&', 'y', '-', 'c', + '/', '3' }; + +int +main (int argc, char ** argv) +{ + int intlist_size = 12; + int i; + tree_ptr root = NULL; + for (i = 0; i < intlist_size; ++i) + { + search_tree_insert (&root, integers[i]); + } + pre_order_traverse (root); + printf ("\n"); + pre_order_traverse_no_recurse (root); + printf ("\n"); + in_order_traverse (root); + printf ("\n"); + in_order_traverse_no_recurse (root); + return 0; +} diff --git a/binary_search_tool/full_bisect_test/make_sources_bad.sh b/binary_search_tool/full_bisect_test/make_sources_bad.sh new file mode 100755 index 00000000..507e8ca8 --- /dev/null +++ b/binary_search_tool/full_bisect_test/make_sources_bad.sh @@ -0,0 +1,15 @@ +#!/bin/bash -u +# +# There are two versions (good & bad) of inorder_norecurse.c and +# preorder_norecurse.c. This script makes sure the bad versions +# are copied into the .c files that will be built and copied into +# the bad-objects directory, for the bisection test. It is called +# from run-test-nowrapper.sh. +# + +pushd full_bisect_test + +cp inorder_norecurse.c.bad inorder_norecurse.c +cp preorder_norecurse.c.bad preorder_norecurse.c + +popd diff --git a/binary_search_tool/full_bisect_test/make_sources_good.sh b/binary_search_tool/full_bisect_test/make_sources_good.sh new file mode 100755 index 00000000..611e9442 --- /dev/null +++ b/binary_search_tool/full_bisect_test/make_sources_good.sh @@ -0,0 +1,15 @@ +#!/bin/bash -u +# +# There are two versions (good & bad) of inorder_norecurse.c and +# preorder_norecurse.c. This script makes sure the good versions +# are copied into the .c files that will be built and copied into +# the good-objects directory, for the bisection test. It is called +# from run-test-nowrapper.sh. +# + +pushd full_bisect_test + +cp inorder_norecurse.c.good inorder_norecurse.c +cp preorder_norecurse.c.good preorder_norecurse.c + +popd diff --git a/binary_search_tool/full_bisect_test/preorder.c b/binary_search_tool/full_bisect_test/preorder.c new file mode 100644 index 00000000..11fe93a3 --- /dev/null +++ b/binary_search_tool/full_bisect_test/preorder.c @@ -0,0 +1,23 @@ +#include <stdio.h> +#include <stdlib.h> +#include "bin-trees.h" + +static void +real_preorder (tree_ptr root) +{ + if (root == NULL) + return; + + printf ("%d ", root->data); + real_preorder (root->left); + real_preorder (root->right); +} + + +void +pre_order_traverse (tree_ptr root) +{ + printf ("pre-order traversal, with recursion: \n"); + real_preorder (root) ; + printf ("\n"); +} diff --git a/binary_search_tool/full_bisect_test/preorder_norecurse.c.bad b/binary_search_tool/full_bisect_test/preorder_norecurse.c.bad new file mode 100644 index 00000000..a8b4b487 --- /dev/null +++ b/binary_search_tool/full_bisect_test/preorder_norecurse.c.bad @@ -0,0 +1,29 @@ +#include <stdlib.h> +#include <stdio.h> +#include "bin-trees.h" + +static void +real_pre_order_traverse_no_recurse (tree_ptr root) +{ + struct stack_struct *stack = NULL; + + if (root != NULL) + push (&stack, root); + + while (stack != NULL) + { + tree_ptr current = pop (&stack); + printf ("%d ", current->data); + if (current->right != NULL) + push (&stack, current->right); + } + return; +} + +void +pre_order_traverse_no_recurse (tree_ptr root) +{ + printf ("pre-order traversal, without recursion: \n"); + real_pre_order_traverse_no_recurse (root); + printf ("\n"); +} diff --git a/binary_search_tool/full_bisect_test/preorder_norecurse.c.good b/binary_search_tool/full_bisect_test/preorder_norecurse.c.good new file mode 100644 index 00000000..98f40913 --- /dev/null +++ b/binary_search_tool/full_bisect_test/preorder_norecurse.c.good @@ -0,0 +1,31 @@ +#include <stdlib.h> +#include <stdio.h> +#include "bin-trees.h" + +static void +real_pre_order_traverse_no_recurse (tree_ptr root) +{ + struct stack_struct *stack = NULL; + + if (root != NULL) + push (&stack, root); + + while (stack != NULL) + { + tree_ptr current = pop (&stack); + printf ("%d ", current->data); + if (current->right != NULL) + push (&stack, current->right); + if (current->left != NULL) + push (&stack, current->left); + } + return; +} + +void +pre_order_traverse_no_recurse (tree_ptr root) +{ + printf ("pre-order traversal, without recursion: \n"); + real_pre_order_traverse_no_recurse (root); + printf ("\n"); +} diff --git a/binary_search_tool/full_bisect_test/run-test-nowrapper.sh b/binary_search_tool/full_bisect_test/run-test-nowrapper.sh new file mode 100755 index 00000000..afc4a446 --- /dev/null +++ b/binary_search_tool/full_bisect_test/run-test-nowrapper.sh @@ -0,0 +1,68 @@ +#!/bin/bash +# +# This script is one of the two main driver scripts for testing the bisector. +# It should be used to test the bisection tool, if you do NOT want to test +# the compiler wrapper (e.g. don't bother with POPULATE_GOOD & POPULATE_BAD +# stages). +# +# It makes sure the good & bad object directories exist (soft links); checks +# to see if it needs to compile the good & bad sources & populate the +# directories; does so if needed. +# +# Then it calls main-bisect-test, which runs the actual bisection tests. This +# script assumes it is being run from the parent directory. +# +# NOTE: Your PYTHONPATH environment variable needs to include both the +# toolchain-utils directory and the +# toolchain-utils/binary_search_tool directory for these testers to work. +# + +SAVE_DIR=`pwd` + +DIR=full_bisect_test + +if [[ ! -d "${DIR}" ]] ; then + echo "Cannot find ${DIR}; you are running this script from the wrong place." + echo "You need to run this from toolchain-utils/binary_search_tool ." + exit 1 +fi + +# Set up object file soft links +cd ${DIR} + +rm -f good-objects +rm -f bad-objects + +ln -s good-objects-permanent good-objects +ln -s bad-objects-permanent bad-objects + +if [[ ! -d work ]] ; then + mkdir work +fi + +# Check to see if the object files need to be built. +if [[ ! -f good-objects-permanent/build.o ]] ; then + # 'make clean' + rm -f work/*.o + # skip populate stages in bisect wrapper + unset BISECT_STAGE + # Set up the 'good' source files. + cd .. + ${DIR}/make_sources_good.sh + cd ${DIR} + # Build the 'good' .o files & copy to appropriate directory. + ./build.sh + mv work/*.o good-objects-permanent/. + # Set up the 'bad' source files. + cd .. + ${DIR}/make_sources_bad.sh + cd ${DIR} + # Build the 'bad' .o files & copy to appropriate directory. + ./build.sh + mv work/*.o bad-objects-permanent/. +fi + +# Now we're ready for the main test. + +cd ${SAVE_DIR} +${DIR}/main-bisect-test.sh diff --git a/binary_search_tool/full_bisect_test/setup.sh b/binary_search_tool/full_bisect_test/setup.sh new file mode 100755 index 00000000..1214de92 --- /dev/null +++ b/binary_search_tool/full_bisect_test/setup.sh @@ -0,0 +1,36 @@ +#!/bin/bash +# +# This script creates common.sh, which will be sourced by all the other +# scripts, to set up the necessary environment variables for the bisection +# to work properly. It is called from main-bisect-test.sh. +# + +DIR=`pwd`/"full_bisect_test" + +GOOD_BUILD=${DIR}/good-objects +BAD_BUILD=${DIR}/bad-objects + +mkdir -p ${DIR}/work + +WORK_BUILD=${DIR}/work + +rm -f ${WORK_BUILD}/* + +COMMON_FILE="${DIR}/common.sh" + +cat <<-EOF > ${COMMON_FILE} + +BISECT_GOOD_BUILD=${GOOD_BUILD} +BISECT_BAD_BUILD=${BAD_BUILD} +BISECT_WORK_BUILD=${WORK_BUILD} + +BISECT_GOOD_SET=${GOOD_BUILD}/_LIST +BISECT_BAD_BAD=${BAD_BUILD}/_LIST + +BISECT_STAGE="TRIAGE" + +EOF + +chmod 755 ${COMMON_FILE} + +exit 0 diff --git a/binary_search_tool/full_bisect_test/stack.c b/binary_search_tool/full_bisect_test/stack.c new file mode 100644 index 00000000..f8d0568f --- /dev/null +++ b/binary_search_tool/full_bisect_test/stack.c @@ -0,0 +1,25 @@ +#include <stdlib.h> +#include <stdio.h> +#include "bin-trees.h" + +tree_ptr +pop (struct stack_struct **stack) +{ + if (*stack == NULL) + return NULL; + else + { + tree_ptr value = (*stack)->data; + (*stack) = (*stack)->next; + return value; + } +} + +void +push (struct stack_struct **stack, tree_ptr value) +{ + struct stack_struct *new_node = (struct stack_struct *) malloc (sizeof (struct stack_struct *)); + new_node->data = value; + new_node->next = *stack; + *stack = new_node; +} diff --git a/binary_search_tool/full_bisect_test/switch_to_bad.sh b/binary_search_tool/full_bisect_test/switch_to_bad.sh new file mode 100755 index 00000000..d88a4aa2 --- /dev/null +++ b/binary_search_tool/full_bisect_test/switch_to_bad.sh @@ -0,0 +1,54 @@ +#!/bin/bash -u +# +# This is one of the scripts that is passed to binary_search_state.py to do +# the bisection. This one takes a list of object files (either a real list or +# a file containing the list) and copies the files from the bad objects +# directory to the working directory. +# + +source full_bisect_test/common.sh + +pushd ${BISECT_WORK_BUILD} +chmod 644 * + +OBJ_LIST_FILES=$1 +FILE_ARGS=0 + +if [[ -f ${OBJ_LIST_FILES} ]] ; then + file ${OBJ_LIST_FILES} &> ${BISECT_WORK_BUILD}/file_type.tmp + grep "ASCII text" ${BISECT_WORK_BUILD}/file_type.tmp + result=$? + if [[ ${result} -eq 0 ]] ; then + FILE_ARGS=1 + fi + rm ${BISECT_WORK_BUILD}/file_type.tmp +fi + +overall_status=0 + +if [[ ${FILE_ARGS} -eq 1 ]] ; then + while read obj || [[ -n "${obj}" ]]; + do + cp ${BISECT_BAD_BUILD}/${obj} ${BISECT_WORK_BUILD} + status=$? + if [[ ${status} -ne 0 ]] ; then + echo "Failed to copy ${obj} to work build tree." + overall_status=2 + fi + done < ${OBJ_LIST_FILES} +else + + for o in "$@" + do + cp ${BISECT_BAD_BUILD}/${o} ${BISECT_WORK_BUILD} + status=$? + if [[ ${status} -ne 0 ]] ; then + echo "Failed to copy ${o} to work build tree." + overall_status=2 + fi + done +fi + +popd + +exit ${overall_status} diff --git a/binary_search_tool/full_bisect_test/switch_to_good.sh b/binary_search_tool/full_bisect_test/switch_to_good.sh new file mode 100755 index 00000000..9d8c29bc --- /dev/null +++ b/binary_search_tool/full_bisect_test/switch_to_good.sh @@ -0,0 +1,57 @@ +#!/bin/bash -u +# +# This is one of the scripts that is passed to binary_search_state.py to do +# the bisection. This one takes a list of object files (either a real list or +# a file containing the list) and copies the files from the good objects +# directory to the working directory. +# + + +source full_bisect_test/common.sh + +pushd ${BISECT_WORK_BUILD} +chmod 644 * + +OBJ_LIST_FILES=$1 +FILE_ARGS=0 + +if [[ -f ${OBJ_LIST_FILES} ]] ; then + file ${OBJ_LIST_FILES} &> ${BISECT_WORK_BUILD}/file_type.tmp + grep "ASCII text" ${BISECT_WORK_BUILD}/file_type.tmp + result=$? + if [[ ${result} -eq 0 ]] ; then + FILE_ARGS=1 + fi + rm ${BISECT_WORK_BUILD}/file_type.tmp +fi + +overall_status=0 + +if [[ ${FILE_ARGS} -eq 1 ]] ; then + while read obj || [[ -n "${obj}" ]]; + do + echo "Copying {BISECT_GOOD_BUILD}/${obj} to ${BISECT_WORK_BUILD}" + cp ${BISECT_GOOD_BUILD}/${obj} ${BISECT_WORK_BUILD} +# cp ${obj} ${BISECT_WORK_BUILD}/. + status=$? + if [[ ${status} -ne 0 ]] ; then + echo "Failed to copy ${obj} to work build tree." + overall_status=2 + fi + done < ${OBJ_LIST_FILES} +else + + for o in "$@" + do + cp ${BISECT_GOOD_BUILD}/${o} ${BISECT_WORK_BUILD} + status=$? + if [[ ${status} -ne 0 ]] ; then + echo "Failed to copy ${o} to work build tree." + overall_status=2 + fi + done +fi + +popd + +exit ${overall_status} diff --git a/binary_search_tool/full_bisect_test/test_setup.sh b/binary_search_tool/full_bisect_test/test_setup.sh new file mode 100755 index 00000000..bb313831 --- /dev/null +++ b/binary_search_tool/full_bisect_test/test_setup.sh @@ -0,0 +1,16 @@ +#!/bin/bash +# +# This is one of the scripts that gets passed to binary_search_state.py. +# It's supposed to generate the binary to be tested, from the mix of +# good & bad object files. +# +source full_bisect_test/common.sh + +WD=`pwd` + +cd full_bisect_test + +echo "BUILDING IMAGE" + +gcc -o bin-trees work/*.o + |