src/functional/qsort.c

   1 #include <inttypes.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include "test.h"
   6
   7 static int scmp(const void *a, const void *b)
   8 {
   9         return strcmp(*(char **)a, *(char **)b);
  10 }
  11
  12 static int icmp(const void *a, const void *b)
  13 {
  14         return *(int*)a - *(int*)b;
  15 }
  16
  17 static int ccmp(const void *a, const void *b)
  18 {
  19         return *(char*)a - *(char*)b;
  20 }
  21
  22 static int cmp64(const void *a, const void *b)
  23 {
  24         const uint64_t *ua = a, *ub = b;
  25         return *ua < *ub ? -1 : *ua != *ub;
  26 }
  27
  28 /* 26 items -- even */
  29 static const char *s[] = {
  30         "Bob", "Alice", "John", "Ceres",
  31         "Helga", "Drepper", "Emeralda", "Zoran",
  32         "Momo", "Frank", "Pema", "Xavier",
  33         "Yeva", "Gedun", "Irina", "Nono",
  34         "Wiener", "Vincent", "Tsering", "Karnica",
  35         "Lulu", "Quincy", "Osama", "Riley",
  36         "Ursula", "Sam"
  37 };
  38 static const char *s_sorted[] = {
  39         "Alice", "Bob", "Ceres", "Drepper",
  40         "Emeralda", "Frank", "Gedun", "Helga",
  41         "Irina", "John", "Karnica", "Lulu",
  42         "Momo", "Nono", "Osama", "Pema",
  43         "Quincy", "Riley", "Sam", "Tsering",
  44         "Ursula", "Vincent", "Wiener", "Xavier",
  45         "Yeva", "Zoran"
  46 };
  47
  48 /* 23 items -- odd, prime */
  49 static int n[] = {
  50         879045, 394, 99405644, 33434, 232323, 4334, 5454,
  51         343, 45545, 454, 324, 22, 34344, 233, 45345, 343,
  52         848405, 3434, 3434344, 3535, 93994, 2230404, 4334
  53 };
  54 static int n_sorted[] = {
  55         22, 233, 324, 343, 343, 394, 454, 3434,
  56         3535, 4334, 4334, 5454, 33434, 34344, 45345, 45545,
  57         93994, 232323, 848405, 879045, 2230404, 3434344, 99405644
  58 };
  59
  60 static void str_test(const char **a, const char **a_sorted, int len)
  61 {
  62         int i;
  63         qsort(a, len, sizeof *a, scmp);
  64         for (i=0; i<len; i++) {
  65                 if (strcmp(a[i], a_sorted[i]) != 0) {
  66                         t_error("string sort failed at index %d\n", i);
  67                         t_printf("\ti\tgot\twant\n");
  68                         for (i=0; i<len; i++)
  69                                 t_printf("\t%d\t%s\t%s\n", i, a[i], a_sorted[i]);
  70                         break;
  71                 }
  72         }
  73 }
  74
  75 static void int_test(int *a, int *a_sorted, int len)
  76 {
  77         int i;
  78         qsort(a, len, sizeof *a, icmp);
  79         for (i=0; i<len; i++) {
  80                 if (a[i] != a_sorted[i]) {
  81                         t_error("integer sort failed at index %d\n", i);
  82                         t_printf("\ti\tgot\twant\n");
  83                         for (i=0; i<len; i++)
  84                                 t_printf("\t%d\t%d\t%d\n", i, a[i], a_sorted[i]);
  85                         break;
  86                 }
  87         }
  88 }
  89
  90 static void uint64_gen(uint64_t *p, uint64_t *p_sorted, int n)
  91 {
  92         int i;
  93         uint64_t r = 0;
  94         t_randseed(n);
  95         for (i = 0; i < n; i++) {
  96                 r += t_randn(20);
  97                 p[i] = r;
  98         }
  99         memcpy(p_sorted, p, n * sizeof *p);
 100         t_shuffle(p, n);
 101 }
 102
 103 static void uint64_test(uint64_t *a, uint64_t *a_sorted, int len)
 104 {
 105         int i;
 106         qsort(a, len, sizeof *a, cmp64);
 107         for (i=0; i<len; i++) {
 108                 if (a[i] != a_sorted[i]) {
 109                         t_error("uint64 sort failed at index %d\n", i);
 110                         t_printf("\ti\tgot\twant\n");
 111                         for (i=0; i<len; i++)
 112                                 t_printf("\t%d\t%" PRIu64 "\t%" PRIu64 "\n", i, a[i], a_sorted[i]);
 113                         break;
 114                 }
 115         }
 116 }
 117
 118 #define T(a, a_sorted) do { \
 119         char p[] = a; \
 120         qsort(p, sizeof p - 1, 1, ccmp); \
 121         if (memcmp(p, a_sorted, sizeof p) != 0) { \
 122                 t_error("character sort failed\n"); \
 123                 t_printf("\tgot:  \"%s\"\n", p); \
 124                 t_printf("\twant: \"%s\"\n", a_sorted); \
 125         } \
 126 } while(0)
 127
 128 static void char_test(void)
 129 {
 130         T("", "");
 131         T("1", "1");
 132         T("11", "11");
 133         T("12", "12");
 134         T("21", "12");
 135         T("111", "111");
 136         T("211", "112");
 137         T("121", "112");
 138         T("112", "112");
 139         T("221", "122");
 140         T("212", "122");
 141         T("122", "122");
 142         T("123", "123");
 143         T("132", "123");
 144         T("213", "123");
 145         T("231", "123");
 146         T("321", "123");
 147         T("312", "123");
 148         T("1423", "1234");
 149         T("51342", "12345");
 150         T("261435", "123456");
 151         T("4517263", "1234567");
 152         T("37245618", "12345678");
 153         T("812436597", "123456789");
 154         T("987654321", "123456789");
 155         T("321321321", "111222333");
 156         T("49735862185236174", "11223344556677889");
 157 }
 158
 159 int main(void)
 160 {
 161         int i;
 162
 163         str_test(s, s_sorted, sizeof s/sizeof*s);
 164         int_test(n, n_sorted, sizeof n/sizeof*n);
 165         char_test();
 166         for (i = 1023; i<=1026; i++) {
 167                 uint64_t p[1026], p_sorted[1026];
 168                 uint64_gen(p, p_sorted, i);
 169                 uint64_test(p, p_sorted, i);
 170         }
 171         return t_status;
 172 }