contrib/subversion/subversion/libsvn_fs_x/changes.c

   1 /* changes.h --- FSX changed paths lists container
   2  *
   3  * ====================================================================
   4  *    Licensed to the Apache Software Foundation (ASF) under one
   5  *    or more contributor license agreements.  See the NOTICE file
   6  *    distributed with this work for additional information
   7  *    regarding copyright ownership.  The ASF licenses this file
   8  *    to you under the Apache License, Version 2.0 (the
   9  *    "License"); you may not use this file except in compliance
  10  *    with the License.  You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  *    Unless required by applicable law or agreed to in writing,
  15  *    software distributed under the License is distributed on an
  16  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  17  *    KIND, either express or implied.  See the License for the
  18  *    specific language governing permissions and limitations
  19  *    under the License.
  20  * ====================================================================
  21  */
  22
  23 #include "svn_private_config.h"
  24 #include "svn_sorts.h"
  25
  26 #include "private/svn_packed_data.h"
  27
  28 #include "changes.h"
  29 #include "string_table.h"
  30 #include "temp_serializer.h"
  31
  32 /* These flags will be used with the FLAGS field in binary_change_t.
  33  */
  34
  35 /* the change contains a text modification */
  36 #define CHANGE_TEXT_MOD     0x00001
  37
  38 /* the change contains a property modification */
  39 #define CHANGE_PROP_MOD     0x00002
  40
  41 /* the change contains a mergeinfo modification */
  42 #define CHANGE_MERGEINFO_MOD 0x00004
  43
  44 /* (flags & CHANGE_NODE_MASK) >> CHANGE_NODE_SHIFT extracts the node type */
  45 #define CHANGE_NODE_SHIFT   0x00003
  46 #define CHANGE_NODE_MASK    0x00018
  47
  48 /* node types according to svn_node_kind_t */
  49 #define CHANGE_NODE_NONE    0x00000
  50 #define CHANGE_NODE_FILE    0x00008
  51 #define CHANGE_NODE_DIR     0x00010
  52 #define CHANGE_NODE_UNKNOWN 0x00018
  53
  54 /* (flags & CHANGE_KIND_MASK) >> CHANGE_KIND_SHIFT extracts the change type */
  55 #define CHANGE_KIND_SHIFT   0x00005
  56 #define CHANGE_KIND_MASK    0x00060
  57
  58 /* node types according to svn_fs_path_change_kind_t */
  59 #define CHANGE_KIND_MODIFY  0x00000
  60 #define CHANGE_KIND_ADD     0x00020
  61 #define CHANGE_KIND_DELETE  0x00040
  62 #define CHANGE_KIND_REPLACE 0x00060
  63
  64 /* Our internal representation of a change */
  65 typedef struct binary_change_t
  66 {
  67   /* define the kind of change and what specific information is present */
  68   int flags;
  69
  70   /* Path of the change. */
  71   apr_size_t path;
  72
  73   /* copy-from information.
  74    * Not present if COPYFROM_REV is SVN_INVALID_REVNUM. */
  75   svn_revnum_t copyfrom_rev;
  76   apr_size_t copyfrom_path;
  77
  78 } binary_change_t;
  79
  80 /* The actual container object.  Change lists are concatenated into CHANGES
  81  * and and their begins and ends are stored in OFFSETS.
  82  */
  83 struct svn_fs_x__changes_t
  84 {
  85   /* The paths - either in 'builder' mode or finalized mode.
  86    * The respective other pointer will be NULL. */
  87   string_table_builder_t *builder;
  88   string_table_t *paths;
  89
  90   /* All changes of all change lists concatenated.
  91    * Array elements are binary_change_t.structs (not pointer!) */
  92   apr_array_header_t *changes;
  93
  94   /* [Offsets[index] .. Offsets[index+1]) is the range in CHANGES that
  95    * forms the contents of change list INDEX. */
  96   apr_array_header_t *offsets;
  97 };
  98
  99 /* Create and return a new container object, allocated in RESULT_POOL with
 100  * an initial capacity of INITIAL_COUNT changes.  The PATH and BUILDER
 101  * members must be initialized by the caller afterwards.
 102  */
 103 static svn_fs_x__changes_t *
 104 changes_create_body(apr_size_t initial_count,
 105                     apr_pool_t *result_pool)
 106 {
 107   svn_fs_x__changes_t *changes = apr_pcalloc(result_pool, sizeof(*changes));
 108
 109   changes->changes = apr_array_make(result_pool, (int)initial_count,
 110                                     sizeof(binary_change_t));
 111   changes->offsets = apr_array_make(result_pool, 16, sizeof(int));
 112   APR_ARRAY_PUSH(changes->offsets, int) = 0;
 113
 114   return changes;
 115 }
 116
 117 svn_fs_x__changes_t *
 118 svn_fs_x__changes_create(apr_size_t initial_count,
 119                          apr_pool_t *result_pool)
 120 {
 121   svn_fs_x__changes_t *changes = changes_create_body(initial_count,
 122                                                      result_pool);
 123   changes->builder = svn_fs_x__string_table_builder_create(result_pool);
 124
 125   return changes;
 126 }
 127
 128 /* Add CHANGE to the latest change list in CHANGES.
 129  */
 130 static svn_error_t *
 131 append_change(svn_fs_x__changes_t *changes,
 132               svn_fs_x__change_t *change)
 133 {
 134   binary_change_t binary_change = { 0 };
 135
 136   /* CHANGE must be sufficiently complete */
 137   SVN_ERR_ASSERT(change);
 138   SVN_ERR_ASSERT(change->path.data);
 139
 140   /* define the kind of change and what specific information is present */
 141   binary_change.flags = (change->text_mod ? CHANGE_TEXT_MOD : 0)
 142                       | (change->prop_mod ? CHANGE_PROP_MOD : 0)
 143                       | (change->mergeinfo_mod == svn_tristate_true
 144                                           ? CHANGE_MERGEINFO_MOD : 0)
 145                       | ((int)change->change_kind << CHANGE_KIND_SHIFT)
 146                       | ((int)change->node_kind << CHANGE_NODE_SHIFT);
 147
 148   /* Path of the change. */
 149   binary_change.path
 150     = svn_fs_x__string_table_builder_add(changes->builder,
 151                                          change->path.data,
 152                                          change->path.len);
 153
 154   /* copy-from information, if presence is indicated by FLAGS */
 155   if (SVN_IS_VALID_REVNUM(change->copyfrom_rev))
 156     {
 157       binary_change.copyfrom_rev = change->copyfrom_rev;
 158       binary_change.copyfrom_path
 159         = svn_fs_x__string_table_builder_add(changes->builder,
 160                                              change->copyfrom_path,
 161                                              0);
 162     }
 163   else
 164     {
 165       binary_change.copyfrom_rev = SVN_INVALID_REVNUM;
 166       binary_change.copyfrom_path = 0;
 167     }
 168
 169   APR_ARRAY_PUSH(changes->changes, binary_change_t) = binary_change;
 170
 171   return SVN_NO_ERROR;
 172 }
 173
 174 svn_error_t *
 175 svn_fs_x__changes_append_list(apr_size_t *list_index,
 176                               svn_fs_x__changes_t *changes,
 177                               apr_array_header_t *list)
 178 {
 179   int i;
 180
 181   /* CHANGES must be in 'builder' mode */
 182   SVN_ERR_ASSERT(changes->builder);
 183   SVN_ERR_ASSERT(changes->paths == NULL);
 184
 185   /* simply append the list and all changes */
 186   for (i = 0; i < list->nelts; ++i)
 187     append_change(changes, APR_ARRAY_IDX(list, i, svn_fs_x__change_t *));
 188
 189   /* terminate the list by storing the next changes offset */
 190   APR_ARRAY_PUSH(changes->offsets, int) = changes->changes->nelts;
 191   *list_index = (apr_size_t)(changes->offsets->nelts - 2);
 192
 193   return SVN_NO_ERROR;
 194 }
 195
 196 apr_size_t
 197 svn_fs_x__changes_estimate_size(const svn_fs_x__changes_t *changes)
 198 {
 199   /* CHANGES must be in 'builder' mode */
 200   if (changes->builder == NULL)
 201     return 0;
 202
 203   /* string table code makes its own prediction,
 204    * changes should be < 10 bytes each,
 205    * some static overhead should be assumed */
 206   return svn_fs_x__string_table_builder_estimate_size(changes->builder)
 207        + changes->changes->nelts * 10
 208        + 100;
 209 }
 210
 211 svn_error_t *
 212 svn_fs_x__changes_get_list(apr_array_header_t **list,
 213                            const svn_fs_x__changes_t *changes,
 214                            apr_size_t idx,
 215                            svn_fs_x__changes_context_t *context,
 216                            apr_pool_t *result_pool)
 217 {
 218   int list_first;
 219   int list_last;
 220   int first;
 221   int last;
 222   int i;
 223
 224   /* CHANGES must be in 'finalized' mode */
 225   SVN_ERR_ASSERT(changes->builder == NULL);
 226   SVN_ERR_ASSERT(changes->paths);
 227
 228   /* validate index */
 229   if (idx + 1 >= (apr_size_t)changes->offsets->nelts)
 230     return svn_error_createf(SVN_ERR_FS_CONTAINER_INDEX, NULL,
 231                              apr_psprintf(result_pool,
 232                                           _("Changes list index %%%s"
 233                                             " exceeds container size %%d"),
 234                                           APR_SIZE_T_FMT),
 235                              idx, changes->offsets->nelts - 1);
 236
 237   /* range of changes to return */
 238   list_first = APR_ARRAY_IDX(changes->offsets, (int)idx, int);
 239   list_last = APR_ARRAY_IDX(changes->offsets, (int)idx + 1, int);
 240
 241   /* Restrict it to the sub-range requested by the caller.
 242    * Clip the range to never exceed the list's content. */
 243   first = MIN(context->next + list_first, list_last);
 244   last = MIN(first + SVN_FS_X__CHANGES_BLOCK_SIZE, list_last);
 245
 246   /* Indicate to the caller whether the end of the list has been reached. */
 247   context->eol = last == list_last;
 248
 249   /* construct result */
 250   *list = apr_array_make(result_pool, last - first,
 251                          sizeof(svn_fs_x__change_t*));
 252   for (i = first; i < last; ++i)
 253     {
 254       const binary_change_t *binary_change
 255         = &APR_ARRAY_IDX(changes->changes, i, binary_change_t);
 256
 257       /* convert BINARY_CHANGE into a standard FSX svn_fs_x__change_t */
 258       svn_fs_x__change_t *change = apr_pcalloc(result_pool, sizeof(*change));
 259       change->path.data = svn_fs_x__string_table_get(changes->paths,
 260                                                      binary_change->path,
 261                                                      &change->path.len,
 262                                                      result_pool);
 263
 264       change->change_kind = (svn_fs_path_change_kind_t)
 265         ((binary_change->flags & CHANGE_KIND_MASK) >> CHANGE_KIND_SHIFT);
 266       change->text_mod = (binary_change->flags & CHANGE_TEXT_MOD) != 0;
 267       change->prop_mod = (binary_change->flags & CHANGE_PROP_MOD) != 0;
 268       change->mergeinfo_mod = (binary_change->flags & CHANGE_MERGEINFO_MOD)
 269                             ? svn_tristate_true
 270                             : svn_tristate_false;
 271       change->node_kind = (svn_node_kind_t)
 272         ((binary_change->flags & CHANGE_NODE_MASK) >> CHANGE_NODE_SHIFT);
 273
 274       change->copyfrom_rev = binary_change->copyfrom_rev;
 275       change->copyfrom_known = TRUE;
 276       if (SVN_IS_VALID_REVNUM(binary_change->copyfrom_rev))
 277         change->copyfrom_path
 278           = svn_fs_x__string_table_get(changes->paths,
 279                                         binary_change->copyfrom_path,
 280                                         NULL,
 281                                         result_pool);
 282
 283       /* add it to the result */
 284       APR_ARRAY_PUSH(*list, svn_fs_x__change_t*) = change;
 285     }
 286
 287   return SVN_NO_ERROR;
 288 }
 289
 290 svn_error_t *
 291 svn_fs_x__write_changes_container(svn_stream_t *stream,
 292                                   const svn_fs_x__changes_t *changes,
 293                                   apr_pool_t *scratch_pool)
 294 {
 295   int i;
 296
 297   string_table_t *paths = changes->paths
 298                         ? changes->paths
 299                         : svn_fs_x__string_table_create(changes->builder,
 300                                                         scratch_pool);
 301
 302   svn_packed__data_root_t *root = svn_packed__data_create_root(scratch_pool);
 303
 304   /* one top-level stream for each array */
 305   svn_packed__int_stream_t *offsets_stream
 306     = svn_packed__create_int_stream(root, TRUE, FALSE);
 307   svn_packed__int_stream_t *changes_stream
 308     = svn_packed__create_int_stream(root, FALSE, FALSE);
 309
 310   /* structure the CHANGES_STREAM such we can extract much of the redundancy
 311    * from the binary_change_t structs */
 312   svn_packed__create_int_substream(changes_stream, TRUE, FALSE);
 313   svn_packed__create_int_substream(changes_stream, TRUE, FALSE);
 314   svn_packed__create_int_substream(changes_stream, TRUE, TRUE);
 315   svn_packed__create_int_substream(changes_stream, TRUE, FALSE);
 316
 317   /* serialize offsets array */
 318   for (i = 0; i < changes->offsets->nelts; ++i)
 319     svn_packed__add_uint(offsets_stream,
 320                          APR_ARRAY_IDX(changes->offsets, i, int));
 321
 322   /* serialize changes array */
 323   for (i = 0; i < changes->changes->nelts; ++i)
 324     {
 325       const binary_change_t *change
 326         = &APR_ARRAY_IDX(changes->changes, i, binary_change_t);
 327
 328       svn_packed__add_uint(changes_stream, change->flags);
 329       svn_packed__add_uint(changes_stream, change->path);
 330
 331       svn_packed__add_int(changes_stream, change->copyfrom_rev);
 332       svn_packed__add_uint(changes_stream, change->copyfrom_path);
 333     }
 334
 335   /* write to disk */
 336   SVN_ERR(svn_fs_x__write_string_table(stream, paths, scratch_pool));
 337   SVN_ERR(svn_packed__data_write(stream, root, scratch_pool));
 338
 339   return SVN_NO_ERROR;
 340 }
 341
 342 svn_error_t *
 343 svn_fs_x__read_changes_container(svn_fs_x__changes_t **changes_p,
 344                                  svn_stream_t *stream,
 345                                  apr_pool_t *result_pool,
 346                                  apr_pool_t *scratch_pool)
 347 {
 348   apr_size_t i;
 349   apr_size_t count;
 350
 351   svn_fs_x__changes_t *changes = apr_pcalloc(result_pool, sizeof(*changes));
 352
 353   svn_packed__data_root_t *root;
 354   svn_packed__int_stream_t *offsets_stream;
 355   svn_packed__int_stream_t *changes_stream;
 356
 357   /* read from disk */
 358   SVN_ERR(svn_fs_x__read_string_table(&changes->paths, stream,
 359                                       result_pool, scratch_pool));
 360
 361   SVN_ERR(svn_packed__data_read(&root, stream, result_pool, scratch_pool));
 362   offsets_stream = svn_packed__first_int_stream(root);
 363   changes_stream = svn_packed__next_int_stream(offsets_stream);
 364
 365   /* read offsets array */
 366   count = svn_packed__int_count(offsets_stream);
 367   changes->offsets = apr_array_make(result_pool, (int)count, sizeof(int));
 368   for (i = 0; i < count; ++i)
 369     APR_ARRAY_PUSH(changes->offsets, int)
 370       = (int)svn_packed__get_uint(offsets_stream);
 371
 372   /* read changes array */
 373   count
 374     = svn_packed__int_count(svn_packed__first_int_substream(changes_stream));
 375   changes->changes
 376     = apr_array_make(result_pool, (int)count, sizeof(binary_change_t));
 377   for (i = 0; i < count; ++i)
 378     {
 379       binary_change_t change;
 380
 381       change.flags = (int)svn_packed__get_uint(changes_stream);
 382       change.path = (apr_size_t)svn_packed__get_uint(changes_stream);
 383
 384       change.copyfrom_rev = (svn_revnum_t)svn_packed__get_int(changes_stream);
 385       change.copyfrom_path = (apr_size_t)svn_packed__get_uint(changes_stream);
 386
 387       APR_ARRAY_PUSH(changes->changes, binary_change_t) = change;
 388     }
 389
 390   *changes_p = changes;
 391
 392   return SVN_NO_ERROR;
 393 }
 394
 395 svn_error_t *
 396 svn_fs_x__serialize_changes_container(void **data,
 397                                       apr_size_t *data_len,
 398                                       void *in,
 399                                       apr_pool_t *pool)
 400 {
 401   svn_fs_x__changes_t *changes = in;
 402   svn_stringbuf_t *serialized;
 403
 404   /* make a guesstimate on the size of the serialized data.  Erring on the
 405    * low side will cause the serializer to re-alloc its buffer. */
 406   apr_size_t size
 407     = changes->changes->elt_size * changes->changes->nelts
 408     + changes->offsets->elt_size * changes->offsets->nelts
 409     + 10 * changes->changes->elt_size
 410     + 100;
 411
 412   /* serialize array header and all its elements */
 413   svn_temp_serializer__context_t *context
 414     = svn_temp_serializer__init(changes, sizeof(*changes), size, pool);
 415
 416   /* serialize sub-structures */
 417   svn_fs_x__serialize_string_table(context, &changes->paths);
 418   svn_fs_x__serialize_apr_array(context, &changes->changes);
 419   svn_fs_x__serialize_apr_array(context, &changes->offsets);
 420
 421   /* return the serialized result */
 422   serialized = svn_temp_serializer__get(context);
 423
 424   *data = serialized->data;
 425   *data_len = serialized->len;
 426
 427   return SVN_NO_ERROR;
 428 }
 429
 430 svn_error_t *
 431 svn_fs_x__deserialize_changes_container(void **out,
 432                                          void *data,
 433                                          apr_size_t data_len,
 434                                          apr_pool_t *result_pool)
 435 {
 436   svn_fs_x__changes_t *changes = (svn_fs_x__changes_t *)data;
 437
 438   /* de-serialize sub-structures */
 439   svn_fs_x__deserialize_string_table(changes, &changes->paths);
 440   svn_fs_x__deserialize_apr_array(changes, &changes->changes, result_pool);
 441   svn_fs_x__deserialize_apr_array(changes, &changes->offsets, result_pool);
 442
 443   /* done */
 444   *out = changes;
 445
 446   return SVN_NO_ERROR;
 447 }
 448
 449 svn_error_t *
 450 svn_fs_x__changes_get_list_func(void **out,
 451                                 const void *data,
 452                                 apr_size_t data_len,
 453                                 void *baton,
 454                                 apr_pool_t *pool)
 455 {
 456   int first;
 457   int last;
 458   int i;
 459   apr_array_header_t *list;
 460
 461   svn_fs_x__changes_get_list_baton_t *b = baton;
 462   apr_uint32_t idx = b->sub_item;
 463   const svn_fs_x__changes_t *container = data;
 464
 465   /* resolve all the sub-container pointers we need */
 466   const string_table_t *paths
 467     = svn_temp_deserializer__ptr(container,
 468                                  (const void *const *)&container->paths);
 469   const apr_array_header_t *serialized_offsets
 470     = svn_temp_deserializer__ptr(container,
 471                                  (const void *const *)&container->offsets);
 472   const apr_array_header_t *serialized_changes
 473     = svn_temp_deserializer__ptr(container,
 474                                  (const void *const *)&container->changes);
 475   const int *offsets
 476     = svn_temp_deserializer__ptr(serialized_offsets,
 477                               (const void *const *)&serialized_offsets->elts);
 478   const binary_change_t *changes
 479     = svn_temp_deserializer__ptr(serialized_changes,
 480                               (const void *const *)&serialized_changes->elts);
 481
 482   /* validate index */
 483   if (idx + 1 >= (apr_size_t)serialized_offsets->nelts)
 484     return svn_error_createf(SVN_ERR_FS_CONTAINER_INDEX, NULL,
 485                              _("Changes list index %u exceeds container "
 486                                "size %d"),
 487                              (unsigned)idx, serialized_offsets->nelts - 1);
 488
 489   /* range of changes to return */
 490   first = offsets[idx];
 491   last = offsets[idx+1];
 492
 493   /* Restrict range to the block requested by the BATON.
 494    * Tell the caller whether we reached the end of the list. */
 495   first = MIN(first + b->start, last);
 496   last = MIN(first + SVN_FS_X__CHANGES_BLOCK_SIZE, last);
 497   *b->eol = last == offsets[idx+1];
 498
 499   /* construct result */
 500   list = apr_array_make(pool, last - first, sizeof(svn_fs_x__change_t*));
 501
 502   for (i = first; i < last; ++i)
 503     {
 504       const binary_change_t *binary_change = &changes[i];
 505
 506       /* convert BINARY_CHANGE into a standard FSX svn_fs_x__change_t */
 507       svn_fs_x__change_t *change = apr_pcalloc(pool, sizeof(*change));
 508       change->path.data
 509         = svn_fs_x__string_table_get_func(paths, binary_change->path,
 510                                           &change->path.len, pool);
 511
 512       change->change_kind = (svn_fs_path_change_kind_t)
 513         ((binary_change->flags & CHANGE_KIND_MASK) >> CHANGE_KIND_SHIFT);
 514       change->text_mod = (binary_change->flags & CHANGE_TEXT_MOD) != 0;
 515       change->prop_mod = (binary_change->flags & CHANGE_PROP_MOD) != 0;
 516       change->node_kind = (svn_node_kind_t)
 517         ((binary_change->flags & CHANGE_NODE_MASK) >> CHANGE_NODE_SHIFT);
 518
 519       change->copyfrom_rev = binary_change->copyfrom_rev;
 520       change->copyfrom_known = TRUE;
 521       if (SVN_IS_VALID_REVNUM(binary_change->copyfrom_rev))
 522         change->copyfrom_path
 523           = svn_fs_x__string_table_get_func(paths,
 524                                             binary_change->copyfrom_path,
 525                                             NULL,
 526                                             pool);
 527
 528       /* add it to the result */
 529       APR_ARRAY_PUSH(list, svn_fs_x__change_t*) = change;
 530     }
 531
 532   *out = list;
 533
 534   return SVN_NO_ERROR;
 535 }