subversion/tests/libsvn_delta/range-index-test.h

   1 /*
   2  * range-index-test.c: An extension for random-test.
   3  *
   4  * ====================================================================
   5  * Copyright (c) 2000-2004 CollabNet.  All rights reserved.
   6  *
   7  * This software is licensed as described in the file COPYING, which
   8  * you should have received as part of this distribution.  The terms
   9  * are also available at http://subversion.tigris.org/license-1.html.
  10  * If newer versions of this license are posted there, you may use a
  11  * newer version instead, at your option.
  12  *
  13  * This software consists of voluntary contributions made by many
  14  * individuals.  For exact contribution history, see the revision
  15  * history and logs, available at http://subversion.tigris.org/.
  16  * ====================================================================
  17  */
  18
  19 #ifndef SVN_RANGE_INDEX_TEST_H
  20 #define SVN_RANGE_INDEX_TEST_H
  21
  22 #include "../../libsvn_delta/compose_delta.c"
  23
  24 static range_index_node_t *prev_node, *prev_prev_node;
  25 static apr_off_t
  26 walk_range_index(range_index_node_t *node, const char **msg)
  27 {
  28   apr_off_t ret;
  29
  30   if (node == NULL)
  31     return 0;
  32
  33   ret = walk_range_index(node->left, msg);
  34   if (ret > 0)
  35     return ret;
  36
  37   if (prev_node != NULL
  38       && node->target_offset > 0
  39       && (prev_node->offset >= node->offset
  40           || (prev_node->limit >= node->limit)))
  41     {
  42       ret = node->target_offset;
  43       node->target_offset = -node->target_offset;
  44       *msg = "Oops, the previous node ate me.";
  45       return ret;
  46     }
  47   if (prev_prev_node != NULL
  48       && prev_node->target_offset > 0
  49       && prev_prev_node->limit > node->offset)
  50     {
  51       ret = prev_node->target_offset;
  52       prev_node->target_offset = -prev_node->target_offset;
  53       *msg = "Arrgh, my neighbours are conspiring against me.";
  54       return ret;
  55     }
  56   prev_prev_node = prev_node;
  57   prev_node = node;
  58
  59   return walk_range_index(node->right, msg);
  60 }
  61
  62
  63 static void
  64 print_node_data(range_index_node_t *node, const char *msg, apr_off_t ndx)
  65 {
  66   if (-node->target_offset == ndx)
  67     {
  68       printf("   * Node: [%3"APR_OFF_T_FMT
  69              ",%3"APR_OFF_T_FMT
  70              ") = %-5"APR_OFF_T_FMT"%s\n",
  71              node->offset, node->limit, -node->target_offset, msg);
  72     }
  73   else
  74     {
  75       printf("     Node: [%3"APR_OFF_T_FMT
  76              ",%3"APR_OFF_T_FMT
  77              ") = %"APR_OFF_T_FMT"\n",
  78              node->offset, node->limit,
  79              (node->target_offset < 0
  80               ? -node->target_offset : node->target_offset));
  81     }
  82 }
  83
  84 static void
  85 print_range_index_r(range_index_node_t *node, const char *msg, apr_off_t ndx)
  86 {
  87   if (node == NULL)
  88     return;
  89
  90   print_range_index_r(node->left, msg, ndx);
  91   print_node_data(node, msg, ndx);
  92   print_range_index_r(node->right, msg, ndx);
  93 }
  94
  95 static void
  96 print_range_index_i(range_index_node_t *node, const char *msg, apr_off_t ndx)
  97 {
  98   if (node == NULL)
  99     return;
 100
 101   while (node->prev)
 102     node = node->prev;
 103
 104   do
 105     {
 106       print_node_data(node, msg, ndx);
 107       node = node->next;
 108     }
 109   while (node);
 110 }
 111
 112 static void
 113 print_range_index(range_index_node_t *node, const char *msg, apr_off_t ndx)
 114 {
 115   printf("  (recursive)\n");
 116   print_range_index_r(node, msg, ndx);
 117   printf("  (iterative)\n");
 118   print_range_index_i(node, msg, ndx);
 119 }
 120
 121
 122 static void
 123 check_copy_count(int src_cp, int tgt_cp)
 124 {
 125   printf("Source copies: %d  Target copies: %d\n", src_cp, tgt_cp);
 126   if (src_cp > tgt_cp)
 127     printf("WARN: More source than target copies; inefficient combiner?\n");
 128 }
 129
 130
 131 static svn_error_t *
 132 random_range_index_test(const char **msg,
 133                         svn_boolean_t msg_only,
 134                         apr_pool_t *pool)
 135 {
 136   static char msg_buff[256];
 137
 138   unsigned long seed, bytes_range;
 139   int i, maxlen, iterations, dump_files, print_windows;
 140   const char *random_bytes;
 141   range_index_t *ndx;
 142   int tgt_cp = 0, src_cp = 0;
 143
 144   /* Initialize parameters and print out the seed in case we dump core
 145      or something. */
 146   init_params(&seed, &maxlen, &iterations, &dump_files, &print_windows,
 147               &random_bytes, &bytes_range, pool);
 148   sprintf(msg_buff, "random range index test, seed = %lu", seed);
 149   *msg = msg_buff;
 150
 151   /* ### This test is expected to fail randomly at the moment, so don't
 152      enable it by default. --xbc */
 153   if (msg_only)
 154     return SVN_NO_ERROR;
 155   else
 156     printf("SEED: %s\n", msg_buff);
 157
 158   ndx = create_range_index(pool);
 159   for (i = 1; i <= iterations; ++i)
 160     {
 161       apr_off_t offset = myrand(&seed) % 47;
 162       apr_off_t limit = offset + myrand(&seed) % 16 + 1;
 163       range_list_node_t *list, *r;
 164       apr_off_t ret;
 165       const char *msg2;
 166
 167       printf("%3d: Inserting [%3"APR_OFF_T_FMT",%3"APR_OFF_T_FMT") ...",
 168              i, offset, limit);
 169       splay_range_index(offset, ndx);
 170       list = build_range_list(offset, limit, ndx);
 171       insert_range(offset, limit, i, ndx);
 172       prev_prev_node = prev_node = NULL;
 173       ret = walk_range_index(ndx->tree, &msg2);
 174       if (ret == 0)
 175         {
 176           for (r = list; r; r = r->next)
 177             printf(" %s[%3"APR_OFF_T_FMT",%3"APR_OFF_T_FMT")",
 178                    (r->kind == range_from_source ?
 179                     (++src_cp, "S") : (++tgt_cp, "T")),
 180                    r->offset, r->limit);
 181           free_range_list(list, ndx);
 182           printf(" OK\n");
 183         }
 184       else
 185         {
 186           printf(" Ooops!\n");
 187           print_range_index(ndx->tree, msg2, ret);
 188           check_copy_count(src_cp, tgt_cp);
 189           return svn_error_create(SVN_ERR_TEST_FAILED, 0, NULL, pool,
 190                                   "insert_range");
 191         }
 192     }
 193
 194   printf("Final tree state:\n");
 195   print_range_index(ndx->tree, "", iterations + 1);
 196   check_copy_count(src_cp, tgt_cp);
 197   return SVN_NO_ERROR;
 198 }
 199
 200
 201 #endif /* SVN_RANGE_INDEX_TEST_H */