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 *
changes_create_body(apr_size_t initial_count,apr_pool_t * result_pool)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 *
svn_fs_x__changes_create(apr_size_t initial_count,apr_pool_t * result_pool)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 *
append_change(svn_fs_x__changes_t * changes,svn_fs_x__change_t * change)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 *
svn_fs_x__changes_append_list(apr_size_t * list_index,svn_fs_x__changes_t * changes,apr_array_header_t * list)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 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
196 apr_size_t
svn_fs_x__changes_estimate_size(const svn_fs_x__changes_t * changes)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 *
svn_fs_x__changes_get_list(apr_array_header_t ** list,const svn_fs_x__changes_t * changes,apr_size_t idx,svn_fs_x__changes_context_t * context,apr_pool_t * result_pool)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 *
svn_fs_x__write_changes_container(svn_stream_t * stream,const svn_fs_x__changes_t * changes,apr_pool_t * scratch_pool)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 *
svn_fs_x__read_changes_container(svn_fs_x__changes_t ** changes_p,svn_stream_t * stream,apr_pool_t * result_pool,apr_pool_t * scratch_pool)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 *
svn_fs_x__serialize_changes_container(void ** data,apr_size_t * data_len,void * in,apr_pool_t * pool)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 *
svn_fs_x__deserialize_changes_container(void ** out,void * data,apr_size_t data_len,apr_pool_t * result_pool)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 *
svn_fs_x__changes_get_list_func(void ** out,const void * data,apr_size_t data_len,void * baton,apr_pool_t * pool)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 }
536