common/utils/test-vector.c

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #include <config.h>
  34
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <stdbool.h>
  38 #include <stdint.h>
  39 #include <string.h>
  40 #include <errno.h>
  41
  42 #undef NDEBUG /* Keep test strong even for nbdkit built without assertions */
  43 #include <assert.h>
  44
  45 #include "bench.h"
  46 #include "const-string-vector.h"
  47 #include "nbdkit-string.h"
  48 #include "string-vector.h"
  49 #include "vector.h"
  50
  51 #define APPENDS 1000000
  52
  53 DEFINE_VECTOR_TYPE (int64_vector, int64_t);
  54 DEFINE_VECTOR_TYPE (uint32_vector, uint32_t);
  55
  56 static int
  57 compare (const int64_t *a, const int64_t *b)
  58 {
  59   return (*a > *b) - (*a < *b);
  60 }
  61
  62 static void
  63 test_int64_vector (void)
  64 {
  65   int64_vector v = empty_vector;
  66   size_t i;
  67   int64_t tmp, *p;
  68
  69   for (i = 0; i < 10; ++i) {
  70     int r = int64_vector_insert (&v, i, 0);
  71     assert (r == 0);
  72   }
  73
  74   for (i = 0; i < 10; ++i)
  75     assert (v.ptr[i] == 9 - i);
  76   int64_vector_sort (&v, compare);
  77   for (i = 0; i < 10; ++i)
  78     assert (v.ptr[i] == i);
  79
  80   int64_vector_remove (&v, 1);
  81   assert (v.len == 9);
  82   assert (v.ptr[1] == 2);
  83
  84   tmp = 10;
  85   p = int64_vector_search (&v, &tmp, (void*) compare);
  86   assert (p == NULL);
  87   tmp = 8;
  88   p = int64_vector_search (&v, &tmp, (void*) compare);
  89   assert (p == &v.ptr[7]);
  90
  91   free (v.ptr);
  92 }
  93
  94 static void
  95 test_string_concat (string *s, const char *append)
  96 {
  97   const size_t len = strlen (append);
  98   size_t i;
  99   int r;
 100
 101   r = string_reserve (s, len);
 102   assert (r == 0);
 103
 104   /* The contract is that after calling string_reserve with 'n', we
 105    * can append up to 'n' items to the vector without failing.
 106    */
 107   for (i = 0; i < len; ++i) {
 108     r = string_append (s, append[i]);
 109     assert (r == 0);
 110   }
 111 }
 112
 113 static void
 114 test_string (void)
 115 {
 116   string s = empty_vector;
 117   int r;
 118   char nul = 0;
 119
 120   test_string_concat (&s, "hello");
 121   test_string_concat (&s, " world");
 122   r = string_append (&s, nul);
 123   assert (r == 0);
 124
 125   assert (strcmp (s.ptr, "hello world") == 0);
 126   assert (s.len == 12); /* hello + space + world + \0 */
 127   free (s.ptr);
 128 }
 129
 130 static void
 131 test_string_vector (void)
 132 {
 133   CLEANUP_FREE_STRING_VECTOR string_vector v = empty_vector;
 134   size_t i;
 135   int r;
 136
 137   for (i = 0; i < 10; ++i) {
 138     char *s;
 139
 140     r = asprintf (&s, "number %zu", i);
 141     assert (r >= 0);
 142     r = string_vector_append (&v, s);
 143     assert (r == 0);
 144   }
 145   /* NULL-terminate the strings. */
 146   r = string_vector_append (&v, NULL);
 147   assert (r == 0);
 148
 149   /* Now print them. */
 150   for (i = 0; v.ptr[i] != NULL; ++i)
 151     printf ("%s\n", v.ptr[i]);
 152   assert (i == 10);
 153 }
 154
 155 static void
 156 test_const_string_vector (void)
 157 {
 158   CLEANUP_FREE_CONST_STRING_VECTOR const_string_vector v = empty_vector;
 159   size_t i;
 160   int r;
 161
 162   r = const_string_vector_append (&v, "abc");
 163   assert (r >= 0);
 164   r = const_string_vector_append (&v, "def");
 165   assert (r >= 0);
 166   r = const_string_vector_append (&v, "ghi");
 167   assert (r >= 0);
 168   r = const_string_vector_append (&v, "jkl");
 169   assert (r >= 0);
 170
 171   /* NULL-terminate the strings. */
 172   r = const_string_vector_append (&v, NULL);
 173   assert (r == 0);
 174
 175   /* Now print them. */
 176   for (i = 0; v.ptr[i] != NULL; ++i)
 177     printf ("%s\n", v.ptr[i]);
 178   assert (i == 4);
 179 }
 180
 181 /* Test size_t overflow. */
 182 static void
 183 test_overflow (void)
 184 {
 185   string s = empty_vector;
 186   int r;
 187
 188   /* It should be impossible to reserve SIZE_MAX - epsilon. */
 189   r = string_reserve (&s, SIZE_MAX - 10000);
 190   assert (r == -1);
 191   assert (errno == ENOMEM);
 192 }
 193
 194 static void
 195 bench_reserve (void)
 196 {
 197   uint32_vector v = empty_vector;
 198   struct bench b;
 199   uint32_t i;
 200
 201   bench_start (&b);
 202
 203   uint32_vector_reserve (&v, APPENDS);
 204
 205   for (i = 0; i < APPENDS; i++) {
 206     uint32_vector_append (&v, i);
 207   }
 208
 209   bench_stop (&b);
 210
 211   assert (v.ptr[APPENDS-1] == APPENDS-1);
 212   free (v.ptr);
 213
 214   printf ("bench_reserve: %d appends in %.6f s\n", APPENDS, bench_sec (&b));
 215 }
 216
 217 static void
 218 bench_append (void)
 219 {
 220   uint32_vector v = empty_vector;
 221   struct bench b;
 222   uint32_t i;
 223
 224   bench_start (&b);
 225
 226   for (i = 0; i < APPENDS; i++) {
 227     uint32_vector_append (&v, i);
 228   }
 229
 230   bench_stop (&b);
 231
 232   assert (v.ptr[APPENDS - 1] == APPENDS - 1);
 233   free (v.ptr);
 234
 235   printf ("bench_append: %d appends in %.6f s\n", APPENDS, bench_sec (&b));
 236 }
 237
 238 int
 239 main (int argc, char *argv[])
 240 {
 241   const char *s;
 242   bool bench;
 243
 244   s = getenv ("NBDKIT_BENCH");
 245   bench = s && strcmp (s, "1") == 0;
 246
 247   if (!bench) {
 248     /* Do normal tests. */
 249     test_int64_vector ();
 250     test_string ();
 251     test_string_vector ();
 252     test_const_string_vector ();
 253     test_overflow ();
 254   }
 255
 256   else {
 257     /* Do benchmarks. */
 258     bench_reserve ();
 259     bench_append ();
 260   }
 261
 262   return 0;
 263 }