Add more test cases for GptInit() and fixed some bugs

src/platform/vboot_reference/cgptlib/tests/quick_sort_test.c

Index: src/platform/vboot_reference/cgptlib/tests/quick_sort_test.c
diff --git a/src/platform/vboot_reference/cgptlib/tests/quick_sort_test.c b/src/platform/vboot_reference/cgptlib/tests/quick_sort_test.c
new file mode 100644
index 0000000000000000000000000000000000000000..325c2fa83ac38cdd073f24f33062a353a082453e
--- /dev/null
+++ b/src/platform/vboot_reference/cgptlib/tests/quick_sort_test.c
@@ -0,0 +1,137 @@
+/* Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "quick_sort_test.h"
+#include "cgpt_test.h"
+#include "quick_sort.h"
+#include "utility.h"
+
+#define MAX_NUMBER_OF_TEST_ELEMENTS 16
+
+/* callback function for QuickSort.
+ * To get ascent results, this function returns 1 if a < b.
+ * Returns 0 if a >= b. */
+int ascent_compare(const void *a_, const void *b_) {
+  const int *a = a_;
+  const int *b = b_;
+  if (*a < *b) return 1;
+  return 0;
+}
+
+/* Used to verify if an array is sorted as ascent which means
+ * 'a' (previous element) is smaller than 'b' (back element).
+ * Returns 1 for ture, 0 for false. */
+int ascent_verify(const int a, const int b) {
+  return (a <= b) ? 1 : 0;
+}
+
+/* callback function for QuickSort.
+ * To get descent results, this function returns 1 if a > b.
+ * Returns 0 if a <= b. */
+int descent_compare(const void *a_, const void *b_) {
+  const int *a = a_;
+  const int *b = b_;
+  if (*a > *b) return 1;
+  return 0;
+}
+
+/* Used to verify if an array is sorted as descent which means
+ * 'a' (previous element) is lager than 'b' (back element).
+ * Returns 1 for ture, 0 for false. */
+int descent_verify(const int a, const int b) {
+  return (a >= b) ? 1 : 0;
+}
+
+/* We provide 2 ways to sort the array. One for ascent, and another for descent.
+ */
+struct {
+  int (*compare)(const void *a, const void *b);
+  int (*verify)(const int a, const int b);
+} directions[] = {
+  { ascent_compare, ascent_verify, },
+  { descent_compare, descent_verify, },
+};
+
+/* Here are the fixed patterns to test. Especially those corner cases that
+ * random test cannot easily reproduce. */
+struct {
+  int number;  /* number of integers saved in array */
+  int unsorted[MAX_NUMBER_OF_TEST_ELEMENTS];
+} test_data[] = {
+  {0, {}, },
+  {1, {0, }, },
+  {2, {1, 1,}, },
+  {2, {1, 2,}, },
+  {2, {2, 1,}, },
+  {3, {1, 3, 2}, },
+  {3, {2, 1, 3}, },
+  {4, {1, 1, 3, 2}, },
+  {4, {3, 1, 2, 2}, },
+  {4, {1, 3, 3, 2}, },
+  {5, {1, 2, 3, 4, 5}, },
+  {5, {5, 5, 5, 3, 3}, },
+  {5, {5, 1, 3, 2, 4}, },
+  {5, {4, 5, 2, 3, 1}, },
+  {6, {5, 4, 3, 2, 1, 6}, },
+  {7, {5, 4, 3, 2, 1, 6, 7}, },
+  {7, {2, 5, 4, 6, 7, 1, 3}, },
+  {7, {7, 6, 1, 5, 3, 4, 2}, },
+};
+
+int TestQuickSortFixed() {
+  int data;
+  int dir;
+  int sorted[MAX_NUMBER_OF_TEST_ELEMENTS];
+
+  for (dir = 0; dir < ARRAY_SIZE(directions); ++dir) {
+    for (data = 0; data < ARRAY_SIZE(test_data); ++data) {
+      int i;
+      for (i = 0; i < test_data[data].number; ++i)
+        sorted[i] = test_data[data].unsorted[i];
+
+      QuickSort(sorted, test_data[data].number, sizeof(int),
+                directions[dir].compare);
+
+      for (i = 0; i < test_data[data].number - 1; ++i)
+        EXPECT(directions[dir].verify(sorted[i], sorted[i + 1]));
+    }
+  }
+
+  return TEST_OK;
+}
+
+/* Random test. We don't really need a truely random test. A pseudo-random
+ * pattern with large 'try_num' is good enough to test.
+ */
+static uint32_t Random() {
+  static uint32_t seed = 0x600613;  /* 'GOOGLE' :-) */
+  return (seed = seed * 701 + 179);
+}
+
+int TestQuickSortRandom() {
+  int try_num;
+  int i, dir;
+
+  for (dir = 0; dir < ARRAY_SIZE(directions); ++dir) {
+    for (try_num = 100000; try_num > 0; --try_num) {
+      int number_of_elements;
+      int *p;
+
+      number_of_elements = Random() % 181;
+      p = Malloc(sizeof(int) * number_of_elements);
+      for (i = 0; i < number_of_elements; ++i)
+        p[i] = Random() % 173;
+
+      QuickSort(p, number_of_elements, sizeof(int), directions[dir].compare);
+
+      for (i = 0; i < number_of_elements - 1; ++i)
+        EXPECT(directions[dir].verify(p[i], p[i + 1]));
+
+      Free(p);
+    }
+  }
+
+  return TEST_OK;
+}