compiler-rt/test/sanitizer_common/TestCases/Posix/recursion-in-qsort.cpp

   1 // Check that a qsort() comparator that calls qsort() works as expected
   2 // RUN: %clangxx -O2 %s -o %t
   3 // RUN: %run %t 2>&1 | FileCheck %s
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 struct Foo {
   9   int array[2];
  10 };
  11 int global_array[12] = {7, 11, 9, 10, 1, 2, 4, 3, 6, 5, 8, 12};
  12
  13 #define array_size(x) (sizeof(x) / sizeof(x[0]))
  14
  15 int ascending_compare_ints(const void *a, const void *b) {
  16   return *(const int *)a - *(const int *)b;
  17 }
  18
  19 int descending_compare_ints(const void *a, const void *b) {
  20   // Add another qsort() call to check more than one level of recursion
  21   qsort(global_array, array_size(global_array), sizeof(int), &ascending_compare_ints);
  22   return *(const int *)b - *(const int *)a;
  23 }
  24
  25 int sort_and_compare(const void *a, const void *b) {
  26   struct Foo *f1 = (struct Foo *)a;
  27   struct Foo *f2 = (struct Foo *)b;
  28   printf("sort_and_compare({%d, %d}, {%d, %d})\n", f1->array[0], f1->array[1],
  29          f2->array[0], f2->array[1]);
  30   // Call qsort from within qsort() to check that interceptors handle this case:
  31   qsort(&f1->array, array_size(f1->array), sizeof(int), &descending_compare_ints);
  32   qsort(&f2->array, array_size(f2->array), sizeof(int), &descending_compare_ints);
  33   // Sort by second array element:
  34   return f1->array[1] - f2->array[1];
  35 }
  36
  37 int main() {
  38   // Note: 16 elements should be large enough to trigger a recursive qsort() call.
  39   struct Foo qsortArg[16] = {
  40       {1, 99},
  41       {2, 3},
  42       {17, 5},
  43       {8, 6},
  44       {11, 4},
  45       {3, 3},
  46       {16, 17},
  47       {7, 9},
  48       {21, 12},
  49       {32, 23},
  50       {13, 8},
  51       {99, 98},
  52       {41, 42},
  53       {42, 43},
  54       {44, 45},
  55       {0, 1},
  56   };
  57   // Sort the individual arrays in descending order and the over all struct
  58   // Foo array in ascending order of the second array element.
  59   qsort(qsortArg, array_size(qsortArg), sizeof(qsortArg[0]), &sort_and_compare);
  60
  61   printf("Sorted result:");
  62   for (const auto &f : qsortArg) {
  63     printf(" {%d,%d}", f.array[0], f.array[1]);
  64   }
  65   printf("\n");
  66   // CHECK: Sorted result: {1,0} {99,1} {3,2} {3,3} {11,4} {17,5} {8,6} {9,7} {13,8} {21,12} {17,16} {32,23} {42,41} {43,42} {45,44} {99,98}
  67   printf("Sorted global_array:");
  68   for (int i : global_array) {
  69     printf(" %d", i);
  70   }
  71   printf("\n");
  72   // CHECK: Sorted global_array: 1 2 3 4 5 6 7 8 9 10 11 12
  73 }