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 */ 65typedef 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 */ 83struct 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 */ 103static svn_fs_x__changes_t * 104changes_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 117svn_fs_x__changes_t * 118svn_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 */ 130static svn_error_t * 131append_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 174svn_error_t * 175svn_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 SVN_ERR(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 196apr_size_t 197svn_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 211svn_error_t * 212svn_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 290svn_error_t * 291svn_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 342svn_error_t * 343svn_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 395svn_error_t * 396svn_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 430svn_error_t * 431svn_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 449svn_error_t * 450svn_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} 536