libc/test/src/stdlib/qsort_r_test.cpp

   1 //===-- Unittests for qsort_r ---------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "src/stdlib/qsort_r.h"
  10
  11 #include "test/UnitTest/Test.h"
  12
  13 #include <stdlib.h>
  14
  15 static int int_compare_count(const void *l, const void *r, void *count_arg) {
  16   int li = *reinterpret_cast<const int *>(l);
  17   int ri = *reinterpret_cast<const int *>(r);
  18   size_t *count = reinterpret_cast<size_t *>(count_arg);
  19   *count = *count + 1;
  20   if (li == ri)
  21     return 0;
  22   else if (li > ri)
  23     return 1;
  24   else
  25     return -1;
  26 }
  27
  28 TEST(LlvmLibcQsortRTest, SortedArray) {
  29   int array[25] = {10,   23,   33,   35,   55,   70,    71,   100,  110,
  30                    123,  133,  135,  155,  170,  171,   1100, 1110, 1123,
  31                    1133, 1135, 1155, 1170, 1171, 11100, 12310};
  32   constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
  33
  34   size_t count = 0;
  35
  36   LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count,
  37                           &count);
  38
  39   ASSERT_LE(array[0], 10);
  40   ASSERT_LE(array[1], 23);
  41   ASSERT_LE(array[2], 33);
  42   ASSERT_LE(array[3], 35);
  43   ASSERT_LE(array[4], 55);
  44   ASSERT_LE(array[5], 70);
  45   ASSERT_LE(array[6], 71);
  46   ASSERT_LE(array[7], 100);
  47   ASSERT_LE(array[8], 110);
  48   ASSERT_LE(array[9], 123);
  49   ASSERT_LE(array[10], 133);
  50   ASSERT_LE(array[11], 135);
  51   ASSERT_LE(array[12], 155);
  52   ASSERT_LE(array[13], 170);
  53   ASSERT_LE(array[14], 171);
  54   ASSERT_LE(array[15], 1100);
  55   ASSERT_LE(array[16], 1110);
  56   ASSERT_LE(array[17], 1123);
  57   ASSERT_LE(array[18], 1133);
  58   ASSERT_LE(array[19], 1135);
  59   ASSERT_LE(array[20], 1155);
  60   ASSERT_LE(array[21], 1170);
  61   ASSERT_LE(array[22], 1171);
  62   ASSERT_LE(array[23], 11100);
  63   ASSERT_LE(array[24], 12310);
  64
  65   // This is a sorted list, but there still have to have been at least N
  66   // comparisons made.
  67   ASSERT_GE(count, ARRAY_SIZE);
  68 }
  69
  70 TEST(LlvmLibcQsortRTest, ReverseSortedArray) {
  71   int array[25] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
  72                    12, 11, 10, 9,  8,  7,  6,  5,  4,  3,  2,  1};
  73   constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(int);
  74
  75   size_t count = 0;
  76
  77   LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(int), int_compare_count,
  78                           &count);
  79
  80   for (int i = 0; i < int(ARRAY_SIZE - 1); ++i)
  81     ASSERT_LE(array[i], i + 1);
  82
  83   ASSERT_GE(count, ARRAY_SIZE);
  84 }
  85
  86 // The following test is intended to mimic the CPP library pattern of having a
  87 // comparison function that takes a specific type, which is passed to a library
  88 // that then needs to sort an array of that type. The library can't safely pass
  89 // the comparison function to qsort because a function that takes const T*
  90 // being cast to a function that takes const void* is undefined behavior. The
  91 // safer pattern is to pass a type erased comparator that calls into the typed
  92 // comparator to qsort_r.
  93
  94 struct PriorityVal {
  95   int priority;
  96   int size;
  97 };
  98
  99 static int compare_priority_val(const PriorityVal *l, const PriorityVal *r) {
 100   // Subtracting the priorities is unsafe, but it's fine for this test.
 101   int priority_diff = l->priority - r->priority;
 102   if (priority_diff != 0) {
 103     return priority_diff;
 104   }
 105   if (l->size == r->size) {
 106     return 0;
 107   } else if (l->size > r->size) {
 108     return 1;
 109   } else {
 110     return -1;
 111   }
 112 }
 113
 114 template <typename T>
 115 static int type_erased_comp(const void *l, const void *r,
 116                             void *erased_func_ptr) {
 117   typedef int (*TypedComp)(const T *, const T *);
 118   TypedComp typed_func_ptr = reinterpret_cast<TypedComp>(erased_func_ptr);
 119   const T *lt = reinterpret_cast<const T *>(l);
 120   const T *rt = reinterpret_cast<const T *>(r);
 121   return typed_func_ptr(lt, rt);
 122 }
 123
 124 TEST(LlvmLibcQsortRTest, SafeTypeErasure) {
 125   PriorityVal array[5] = {
 126       {10, 3}, {1, 10}, {-1, 100}, {10, 0}, {3, 3},
 127   };
 128   constexpr size_t ARRAY_SIZE = sizeof(array) / sizeof(PriorityVal);
 129
 130   LIBC_NAMESPACE::qsort_r(array, ARRAY_SIZE, sizeof(PriorityVal),
 131                           type_erased_comp<PriorityVal>,
 132                           reinterpret_cast<void *>(compare_priority_val));
 133
 134   EXPECT_EQ(array[0].priority, -1);
 135   EXPECT_EQ(array[0].size, 100);
 136   EXPECT_EQ(array[1].priority, 1);
 137   EXPECT_EQ(array[1].size, 10);
 138   EXPECT_EQ(array[2].priority, 3);
 139   EXPECT_EQ(array[2].size, 3);
 140   EXPECT_EQ(array[3].priority, 10);
 141   EXPECT_EQ(array[3].size, 0);
 142   EXPECT_EQ(array[4].priority, 10);
 143   EXPECT_EQ(array[4].size, 3);
 144 }