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