1 /* string_table.c : operations on string tables
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 <assert.h>
24 #include <string.h>
25 #include <apr_tables.h>
26
27 #include "svn_string.h"
28 #include "svn_sorts.h"
29 #include "private/svn_dep_compat.h"
30 #include "private/svn_string_private.h"
31 #include "private/svn_subr_private.h"
32 #include "private/svn_packed_data.h"
33 #include "string_table.h"
34
35
36
37 #define MAX_DATA_SIZE 0xffff
38 #define MAX_SHORT_STRING_LEN (MAX_DATA_SIZE / 4)
39 #define TABLE_SHIFT 13
40 #define MAX_STRINGS_PER_TABLE (1 << (TABLE_SHIFT - 1))
41 #define LONG_STRING_MASK (1 << (TABLE_SHIFT - 1))
42 #define STRING_INDEX_MASK ((1 << (TABLE_SHIFT - 1)) - 1)
43 #define PADDING (sizeof(apr_uint64_t))
44
45
46 typedef struct builder_string_t
47 {
48 svn_string_t string;
49 int position;
50 apr_size_t depth;
51 struct builder_string_t *previous;
52 struct builder_string_t *next;
53 apr_size_t previous_match_len;
54 apr_size_t next_match_len;
55 struct builder_string_t *left;
56 struct builder_string_t *right;
57 } builder_string_t;
58
59 typedef struct builder_table_t
60 {
61 apr_size_t max_data_size;
62 builder_string_t *top;
63 builder_string_t *first;
64 builder_string_t *last;
65 apr_array_header_t *short_strings;
66 apr_array_header_t *long_strings;
67 apr_hash_t *long_string_dict;
68 apr_size_t long_string_size;
69 } builder_table_t;
70
71 struct string_table_builder_t
72 {
73 apr_pool_t *pool;
74 apr_array_header_t *tables;
75 };
76
77 typedef struct string_header_t
78 {
79 apr_uint16_t head_string;
80 apr_uint16_t head_length;
81 apr_uint16_t tail_start;
82 apr_uint16_t tail_length;
83 } string_header_t;
84
85 typedef struct string_sub_table_t
86 {
87 const char *data;
88 apr_size_t data_size;
89
90 string_header_t *short_strings;
91 apr_size_t short_string_count;
92
93 svn_string_t *long_strings;
94 apr_size_t long_string_count;
95 } string_sub_table_t;
96
97 struct string_table_t
98 {
99 apr_size_t size;
100 string_sub_table_t *sub_tables;
101 };
102
103
104 /* Accessing ID Pieces. */
105
106 static builder_table_t *
add_table(string_table_builder_t * builder)107 add_table(string_table_builder_t *builder)
108 {
109 builder_table_t *table = apr_pcalloc(builder->pool, sizeof(*table));
110 table->max_data_size = MAX_DATA_SIZE - PADDING; /* ensure there remain a few
111 unused bytes at the end */
112 table->short_strings = apr_array_make(builder->pool, 64,
113 sizeof(builder_string_t *));
114 table->long_strings = apr_array_make(builder->pool, 0,
115 sizeof(svn_string_t));
116 table->long_string_dict = svn_hash__make(builder->pool);
117
118 APR_ARRAY_PUSH(builder->tables, builder_table_t *) = table;
119
120 return table;
121 }
122
123 string_table_builder_t *
svn_fs_x__string_table_builder_create(apr_pool_t * result_pool)124 svn_fs_x__string_table_builder_create(apr_pool_t *result_pool)
125 {
126 string_table_builder_t *result = apr_palloc(result_pool, sizeof(*result));
127 result->pool = result_pool;
128 result->tables = apr_array_make(result_pool, 1, sizeof(builder_table_t *));
129
130 add_table(result);
131
132 return result;
133 }
134
135 static void
balance(builder_table_t * table,builder_string_t ** parent,builder_string_t * node)136 balance(builder_table_t *table,
137 builder_string_t **parent,
138 builder_string_t *node)
139 {
140 apr_size_t left_height = node->left ? node->left->depth + 1 : 0;
141 apr_size_t right_height = node->right ? node->right->depth + 1 : 0;
142
143 if (left_height > right_height + 1)
144 {
145 builder_string_t *temp = node->left->right;
146 node->left->right = node;
147 *parent = node->left;
148 node->left = temp;
149
150 --left_height;
151 }
152 else if (left_height + 1 < right_height)
153 {
154 builder_string_t *temp = node->right->left;
155 *parent = node->right;
156 node->right->left = node;
157 node->right = temp;
158
159 --right_height;
160 }
161
162 node->depth = MAX(left_height, right_height);
163 }
164
165 static apr_uint16_t
match_length(const svn_string_t * lhs,const svn_string_t * rhs)166 match_length(const svn_string_t *lhs,
167 const svn_string_t *rhs)
168 {
169 apr_size_t len = MIN(lhs->len, rhs->len);
170 return (apr_uint16_t)svn_cstring__match_length(lhs->data, rhs->data, len);
171 }
172
173 static apr_uint16_t
insert_string(builder_table_t * table,builder_string_t ** parent,builder_string_t * to_insert)174 insert_string(builder_table_t *table,
175 builder_string_t **parent,
176 builder_string_t *to_insert)
177 {
178 apr_uint16_t result;
179 builder_string_t *current = *parent;
180 int diff = strcmp(current->string.data, to_insert->string.data);
181 if (diff == 0)
182 {
183 apr_array_pop(table->short_strings);
184 return current->position;
185 }
186
187 if (diff < 0)
188 {
189 if (current->left == NULL)
190 {
191 current->left = to_insert;
192
193 to_insert->previous = current->previous;
194 to_insert->next = current;
195
196 if (to_insert->previous == NULL)
197 {
198 table->first = to_insert;
199 }
200 else
201 {
202 builder_string_t *previous = to_insert->previous;
203 to_insert->previous_match_len
204 = match_length(&previous->string, &to_insert->string);
205
206 previous->next = to_insert;
207 previous->next_match_len = to_insert->previous_match_len;
208 }
209
210 current->previous = to_insert;
211 to_insert->next_match_len
212 = match_length(¤t->string, &to_insert->string);
213 current->previous_match_len = to_insert->next_match_len;
214
215 table->max_data_size -= to_insert->string.len;
216 if (to_insert->previous == NULL)
217 table->max_data_size += to_insert->next_match_len;
218 else
219 table->max_data_size += MIN(to_insert->previous_match_len,
220 to_insert->next_match_len);
221
222 return to_insert->position;
223 }
224 else
225 result = insert_string(table, ¤t->left, to_insert);
226 }
227 else
228 {
229 if (current->right == NULL)
230 {
231 current->right = to_insert;
232
233 to_insert->next = current->next;
234 to_insert->previous = current;
235
236 if (to_insert->next == NULL)
237 {
238 table->last = to_insert;
239 }
240 else
241 {
242 builder_string_t *next = to_insert->next;
243 to_insert->next_match_len
244 = match_length(&next->string, &to_insert->string);
245
246 next->previous = to_insert;
247 next->previous_match_len = to_insert->next_match_len;
248 }
249
250 current->next = current->right;
251 to_insert->previous_match_len
252 = match_length(¤t->string, &to_insert->string);
253 current->next_match_len = to_insert->previous_match_len;
254
255 table->max_data_size -= to_insert->string.len;
256 if (to_insert->next == NULL)
257 table->max_data_size += to_insert->previous_match_len;
258 else
259 table->max_data_size += MIN(to_insert->previous_match_len,
260 to_insert->next_match_len);
261
262 return to_insert->position;
263 }
264 else
265 result = insert_string(table, ¤t->right, to_insert);
266 }
267
268 balance(table, parent, current);
269 return result;
270 }
271
272 apr_size_t
svn_fs_x__string_table_builder_add(string_table_builder_t * builder,const char * string,apr_size_t len)273 svn_fs_x__string_table_builder_add(string_table_builder_t *builder,
274 const char *string,
275 apr_size_t len)
276 {
277 apr_size_t result;
278 builder_table_t *table = APR_ARRAY_IDX(builder->tables,
279 builder->tables->nelts - 1,
280 builder_table_t *);
281 if (len == 0)
282 len = strlen(string);
283
284 string = apr_pstrmemdup(builder->pool, string, len);
285 if (len > MAX_SHORT_STRING_LEN)
286 {
287 void *idx_void;
288 svn_string_t item;
289 item.data = string;
290 item.len = len;
291
292 idx_void = apr_hash_get(table->long_string_dict, string, len);
293 result = (apr_uintptr_t)idx_void;
294 if (result)
295 return result - 1
296 + LONG_STRING_MASK
297 + (((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT);
298
299 if (table->long_strings->nelts == MAX_STRINGS_PER_TABLE)
300 table = add_table(builder);
301
302 result = table->long_strings->nelts
303 + LONG_STRING_MASK
304 + (((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT);
305 APR_ARRAY_PUSH(table->long_strings, svn_string_t) = item;
306 apr_hash_set(table->long_string_dict, string, len,
307 (void*)(apr_uintptr_t)table->long_strings->nelts);
308
309 table->long_string_size += len;
310 }
311 else
312 {
313 builder_string_t *item = apr_pcalloc(builder->pool, sizeof(*item));
314 item->string.data = string;
315 item->string.len = len;
316 item->previous_match_len = 0;
317 item->next_match_len = 0;
318
319 if ( table->short_strings->nelts == MAX_STRINGS_PER_TABLE
320 || table->max_data_size < len)
321 table = add_table(builder);
322
323 item->position = table->short_strings->nelts;
324 APR_ARRAY_PUSH(table->short_strings, builder_string_t *) = item;
325
326 if (table->top == NULL)
327 {
328 table->max_data_size -= len;
329 table->top = item;
330 table->first = item;
331 table->last = item;
332
333 result = ((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT;
334 }
335 else
336 {
337 result = insert_string(table, &table->top, item)
338 + (((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT);
339 }
340 }
341
342 return result;
343 }
344
345 apr_size_t
svn_fs_x__string_table_builder_estimate_size(string_table_builder_t * builder)346 svn_fs_x__string_table_builder_estimate_size(string_table_builder_t *builder)
347 {
348 apr_size_t total = 0;
349 int i;
350
351 for (i = 0; i < builder->tables->nelts; ++i)
352 {
353 builder_table_t *table
354 = APR_ARRAY_IDX(builder->tables, i, builder_table_t*);
355
356 /* total number of chars to store,
357 * 8 bytes per short string table entry
358 * 4 bytes per long string table entry
359 * some static overhead */
360 apr_size_t table_size
361 = MAX_DATA_SIZE - table->max_data_size
362 + table->long_string_size
363 + table->short_strings->nelts * 8
364 + table->long_strings->nelts * 4
365 + 10;
366
367 total += table_size;
368 }
369
370 /* ZIP compression should give us a 50% reduction.
371 * add some static overhead */
372 return 200 + total / 2;
373
374 }
375
376 static void
create_table(string_sub_table_t * target,builder_table_t * source,apr_pool_t * pool,apr_pool_t * scratch_pool)377 create_table(string_sub_table_t *target,
378 builder_table_t *source,
379 apr_pool_t *pool,
380 apr_pool_t *scratch_pool)
381 {
382 int i = 0;
383 apr_hash_t *tails = svn_hash__make(scratch_pool);
384 svn_stringbuf_t *data
385 = svn_stringbuf_create_ensure(MAX_DATA_SIZE - source->max_data_size,
386 scratch_pool);
387
388 /* pack sub-strings */
389 target->short_string_count = (apr_size_t)source->short_strings->nelts;
390 target->short_strings = apr_palloc(pool, sizeof(*target->short_strings) *
391 target->short_string_count);
392 for (i = 0; i < source->short_strings->nelts; ++i)
393 {
394 const builder_string_t *string
395 = APR_ARRAY_IDX(source->short_strings, i, const builder_string_t *);
396
397 string_header_t *entry = &target->short_strings[i];
398 const char *tail = string->string.data + string->previous_match_len;
399 string_header_t *tail_match;
400 apr_size_t head_length = string->previous_match_len;
401
402 /* Minimize the number of strings to visit when reconstructing the
403 string head. So, skip all predecessors that don't contribute to
404 first HEAD_LENGTH chars of our string. */
405 if (head_length)
406 {
407 const builder_string_t *furthest_prev = string->previous;
408 while (furthest_prev->previous_match_len >= head_length)
409 furthest_prev = furthest_prev->previous;
410 entry->head_string = furthest_prev->position;
411 }
412 else
413 entry->head_string = 0;
414
415 /* head & tail length are known */
416 entry->head_length = (apr_uint16_t)head_length;
417 entry->tail_length
418 = (apr_uint16_t)(string->string.len - entry->head_length);
419
420 /* try to reuse an existing tail segment */
421 tail_match = apr_hash_get(tails, tail, entry->tail_length);
422 if (tail_match)
423 {
424 entry->tail_start = tail_match->tail_start;
425 }
426 else
427 {
428 entry->tail_start = (apr_uint16_t)data->len;
429 svn_stringbuf_appendbytes(data, tail, entry->tail_length);
430 apr_hash_set(tails, tail, entry->tail_length, entry);
431 }
432 }
433
434 /* pack long strings */
435 target->long_string_count = (apr_size_t)source->long_strings->nelts;
436 target->long_strings = apr_palloc(pool, sizeof(*target->long_strings) *
437 target->long_string_count);
438 for (i = 0; i < source->long_strings->nelts; ++i)
439 {
440 svn_string_t *string = &target->long_strings[i];
441 *string = APR_ARRAY_IDX(source->long_strings, i, svn_string_t);
442 string->data = apr_pstrmemdup(pool, string->data, string->len);
443 }
444
445 data->len += PADDING; /* add a few extra bytes at the end of the buffer
446 that we want to keep valid for chunky access */
447 assert(data->len < data->blocksize);
448 memset(data->data + data->len - PADDING, 0, PADDING);
449
450 target->data = apr_pmemdup(pool, data->data, data->len);
451 target->data_size = data->len;
452 }
453
454 string_table_t *
svn_fs_x__string_table_create(const string_table_builder_t * builder,apr_pool_t * pool)455 svn_fs_x__string_table_create(const string_table_builder_t *builder,
456 apr_pool_t *pool)
457 {
458 apr_size_t i;
459
460 string_table_t *result = apr_pcalloc(pool, sizeof(*result));
461 result->size = (apr_size_t)builder->tables->nelts;
462 result->sub_tables
463 = apr_pcalloc(pool, result->size * sizeof(*result->sub_tables));
464
465 for (i = 0; i < result->size; ++i)
466 create_table(&result->sub_tables[i],
467 APR_ARRAY_IDX(builder->tables, i, builder_table_t*),
468 pool,
469 builder->pool);
470
471 return result;
472 }
473
474 /* Masks used by table_copy_string. copy_mask[I] is used if the target
475 content to be preserved starts at byte I within the current chunk.
476 This is used to work around alignment issues.
477 */
478 #if SVN_UNALIGNED_ACCESS_IS_OK
479 static const char *copy_masks[8] = { "\xff\xff\xff\xff\xff\xff\xff\xff",
480 "\x00\xff\xff\xff\xff\xff\xff\xff",
481 "\x00\x00\xff\xff\xff\xff\xff\xff",
482 "\x00\x00\x00\xff\xff\xff\xff\xff",
483 "\x00\x00\x00\x00\xff\xff\xff\xff",
484 "\x00\x00\x00\x00\x00\xff\xff\xff",
485 "\x00\x00\x00\x00\x00\x00\xff\xff",
486 "\x00\x00\x00\x00\x00\x00\x00\xff" };
487 #endif
488
489 static void
table_copy_string(char * buffer,apr_size_t len,const string_sub_table_t * table,string_header_t * header)490 table_copy_string(char *buffer,
491 apr_size_t len,
492 const string_sub_table_t *table,
493 string_header_t *header)
494 {
495 buffer[len] = '\0';
496 do
497 {
498 assert(header->head_length <= len);
499 {
500 #if SVN_UNALIGNED_ACCESS_IS_OK
501 /* the sections that we copy tend to be short but we can copy
502 *all* of it chunky because we made sure that source and target
503 buffer have some extra padding to prevent segfaults. */
504 apr_uint64_t mask;
505 apr_size_t to_copy = len - header->head_length;
506 apr_size_t copied = 0;
507
508 const char *source = table->data + header->tail_start;
509 char *target = buffer + header->head_length;
510 len = header->head_length;
511
512 /* copy whole chunks */
513 while (to_copy >= copied + sizeof(apr_uint64_t))
514 {
515 *(apr_uint64_t *)(target + copied)
516 = *(const apr_uint64_t *)(source + copied);
517 copied += sizeof(apr_uint64_t);
518 }
519
520 /* copy the remainder assuming that we have up to 8 extra bytes
521 of addressable buffer on the source and target sides.
522 Now, we simply copy 8 bytes and use a mask to filter & merge
523 old with new data. */
524 mask = *(const apr_uint64_t *)copy_masks[to_copy - copied];
525 *(apr_uint64_t *)(target + copied)
526 = (*(apr_uint64_t *)(target + copied) & mask)
527 | (*(const apr_uint64_t *)(source + copied) & ~mask);
528 #else
529 memcpy(buffer + header->head_length,
530 table->data + header->tail_start,
531 len - header->head_length);
532 len = header->head_length;
533 #endif
534 }
535
536 header = &table->short_strings[header->head_string];
537 }
538 while (len);
539 }
540
541 const char*
svn_fs_x__string_table_get(const string_table_t * table,apr_size_t idx,apr_size_t * length,apr_pool_t * pool)542 svn_fs_x__string_table_get(const string_table_t *table,
543 apr_size_t idx,
544 apr_size_t *length,
545 apr_pool_t *pool)
546 {
547 apr_size_t table_number = idx >> TABLE_SHIFT;
548 apr_size_t sub_index = idx & STRING_INDEX_MASK;
549
550 if (table_number < table->size)
551 {
552 string_sub_table_t *sub_table = &table->sub_tables[table_number];
553 if (idx & LONG_STRING_MASK)
554 {
555 if (sub_index < sub_table->long_string_count)
556 {
557 if (length)
558 *length = sub_table->long_strings[sub_index].len;
559
560 return apr_pstrmemdup(pool,
561 sub_table->long_strings[sub_index].data,
562 sub_table->long_strings[sub_index].len);
563 }
564 }
565 else
566 {
567 if (sub_index < sub_table->short_string_count)
568 {
569 string_header_t *header = sub_table->short_strings + sub_index;
570 apr_size_t len = header->head_length + header->tail_length;
571 char *result = apr_palloc(pool, len + PADDING);
572
573 if (length)
574 *length = len;
575 table_copy_string(result, len, sub_table, header);
576
577 return result;
578 }
579 }
580 }
581
582 return apr_pstrmemdup(pool, "", 0);
583 }
584
585 svn_error_t *
svn_fs_x__write_string_table(svn_stream_t * stream,const string_table_t * table,apr_pool_t * scratch_pool)586 svn_fs_x__write_string_table(svn_stream_t *stream,
587 const string_table_t *table,
588 apr_pool_t *scratch_pool)
589 {
590 apr_size_t i, k;
591
592 svn_packed__data_root_t *root = svn_packed__data_create_root(scratch_pool);
593
594 svn_packed__int_stream_t *table_sizes
595 = svn_packed__create_int_stream(root, FALSE, FALSE);
596 svn_packed__int_stream_t *small_strings_headers
597 = svn_packed__create_int_stream(root, FALSE, FALSE);
598 svn_packed__byte_stream_t *large_strings
599 = svn_packed__create_bytes_stream(root);
600 svn_packed__byte_stream_t *small_strings_data
601 = svn_packed__create_bytes_stream(root);
602
603 svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE);
604 svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE);
605 svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE);
606 svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE);
607
608 /* number of sub-tables */
609
610 svn_packed__add_uint(table_sizes, table->size);
611
612 /* all short-string char data sizes */
613
614 for (i = 0; i < table->size; ++i)
615 svn_packed__add_uint(table_sizes,
616 table->sub_tables[i].short_string_count);
617
618 for (i = 0; i < table->size; ++i)
619 svn_packed__add_uint(table_sizes,
620 table->sub_tables[i].long_string_count);
621
622 /* all strings */
623
624 for (i = 0; i < table->size; ++i)
625 {
626 string_sub_table_t *sub_table = &table->sub_tables[i];
627 svn_packed__add_bytes(small_strings_data,
628 sub_table->data,
629 sub_table->data_size);
630
631 for (k = 0; k < sub_table->short_string_count; ++k)
632 {
633 string_header_t *string = &sub_table->short_strings[k];
634
635 svn_packed__add_uint(small_strings_headers, string->head_string);
636 svn_packed__add_uint(small_strings_headers, string->head_length);
637 svn_packed__add_uint(small_strings_headers, string->tail_start);
638 svn_packed__add_uint(small_strings_headers, string->tail_length);
639 }
640
641 for (k = 0; k < sub_table->long_string_count; ++k)
642 svn_packed__add_bytes(large_strings,
643 sub_table->long_strings[k].data,
644 sub_table->long_strings[k].len + 1);
645 }
646
647 /* write to target stream */
648
649 SVN_ERR(svn_packed__data_write(stream, root, scratch_pool));
650
651 return SVN_NO_ERROR;
652 }
653
654 svn_error_t *
svn_fs_x__read_string_table(string_table_t ** table_p,svn_stream_t * stream,apr_pool_t * result_pool,apr_pool_t * scratch_pool)655 svn_fs_x__read_string_table(string_table_t **table_p,
656 svn_stream_t *stream,
657 apr_pool_t *result_pool,
658 apr_pool_t *scratch_pool)
659 {
660 apr_size_t i, k;
661
662 string_table_t *table = apr_palloc(result_pool, sizeof(*table));
663
664 svn_packed__data_root_t *root;
665 svn_packed__int_stream_t *table_sizes;
666 svn_packed__byte_stream_t *large_strings;
667 svn_packed__byte_stream_t *small_strings_data;
668 svn_packed__int_stream_t *headers;
669
670 SVN_ERR(svn_packed__data_read(&root, stream, result_pool, scratch_pool));
671 table_sizes = svn_packed__first_int_stream(root);
672 headers = svn_packed__next_int_stream(table_sizes);
673 large_strings = svn_packed__first_byte_stream(root);
674 small_strings_data = svn_packed__next_byte_stream(large_strings);
675
676 /* create sub-tables */
677
678 table->size = (apr_size_t)svn_packed__get_uint(table_sizes);
679 table->sub_tables = apr_pcalloc(result_pool,
680 table->size * sizeof(*table->sub_tables));
681
682 /* read short strings */
683
684 for (i = 0; i < table->size; ++i)
685 {
686 string_sub_table_t *sub_table = &table->sub_tables[i];
687
688 sub_table->short_string_count
689 = (apr_size_t)svn_packed__get_uint(table_sizes);
690 if (sub_table->short_string_count)
691 {
692 sub_table->short_strings
693 = apr_pcalloc(result_pool, sub_table->short_string_count
694 * sizeof(*sub_table->short_strings));
695
696 /* read short string headers */
697
698 for (k = 0; k < sub_table->short_string_count; ++k)
699 {
700 string_header_t *string = &sub_table->short_strings[k];
701
702 string->head_string = (apr_uint16_t)svn_packed__get_uint(headers);
703 string->head_length = (apr_uint16_t)svn_packed__get_uint(headers);
704 string->tail_start = (apr_uint16_t)svn_packed__get_uint(headers);
705 string->tail_length = (apr_uint16_t)svn_packed__get_uint(headers);
706 }
707 }
708
709 sub_table->data = svn_packed__get_bytes(small_strings_data,
710 &sub_table->data_size);
711 }
712
713 /* read long strings */
714
715 for (i = 0; i < table->size; ++i)
716 {
717 /* initialize long string table */
718 string_sub_table_t *sub_table = &table->sub_tables[i];
719
720 sub_table->long_string_count = svn_packed__get_uint(table_sizes);
721 if (sub_table->long_string_count)
722 {
723 sub_table->long_strings
724 = apr_pcalloc(result_pool, sub_table->long_string_count
725 * sizeof(*sub_table->long_strings));
726
727 /* read long strings */
728
729 for (k = 0; k < sub_table->long_string_count; ++k)
730 {
731 svn_string_t *string = &sub_table->long_strings[k];
732 string->data = svn_packed__get_bytes(large_strings,
733 &string->len);
734 string->len--;
735 }
736 }
737 }
738
739 /* done */
740
741 *table_p = table;
742
743 return SVN_NO_ERROR;
744 }
745
746 void
svn_fs_x__serialize_string_table(svn_temp_serializer__context_t * context,string_table_t ** st)747 svn_fs_x__serialize_string_table(svn_temp_serializer__context_t *context,
748 string_table_t **st)
749 {
750 apr_size_t i, k;
751 string_table_t *string_table = *st;
752 if (string_table == NULL)
753 return;
754
755 /* string table struct */
756 svn_temp_serializer__push(context,
757 (const void * const *)st,
758 sizeof(*string_table));
759
760 /* sub-table array (all structs in a single memory block) */
761 svn_temp_serializer__push(context,
762 (const void * const *)&string_table->sub_tables,
763 sizeof(*string_table->sub_tables) *
764 string_table->size);
765
766 /* sub-elements of all sub-tables */
767 for (i = 0; i < string_table->size; ++i)
768 {
769 string_sub_table_t *sub_table = &string_table->sub_tables[i];
770 svn_temp_serializer__add_leaf(context,
771 (const void * const *)&sub_table->data,
772 sub_table->data_size);
773 svn_temp_serializer__add_leaf(context,
774 (const void * const *)&sub_table->short_strings,
775 sub_table->short_string_count * sizeof(string_header_t));
776
777 /* all "long string" instances form a single memory block */
778 svn_temp_serializer__push(context,
779 (const void * const *)&sub_table->long_strings,
780 sub_table->long_string_count * sizeof(svn_string_t));
781
782 /* serialize actual long string contents */
783 for (k = 0; k < sub_table->long_string_count; ++k)
784 {
785 svn_string_t *string = &sub_table->long_strings[k];
786 svn_temp_serializer__add_leaf(context,
787 (const void * const *)&string->data,
788 string->len + 1);
789 }
790
791 svn_temp_serializer__pop(context);
792 }
793
794 /* back to the caller's nesting level */
795 svn_temp_serializer__pop(context);
796 svn_temp_serializer__pop(context);
797 }
798
799 void
svn_fs_x__deserialize_string_table(void * buffer,string_table_t ** table)800 svn_fs_x__deserialize_string_table(void *buffer,
801 string_table_t **table)
802 {
803 apr_size_t i, k;
804 string_sub_table_t *sub_tables;
805
806 svn_temp_deserializer__resolve(buffer, (void **)table);
807 if (*table == NULL)
808 return;
809
810 svn_temp_deserializer__resolve(*table, (void **)&(*table)->sub_tables);
811 sub_tables = (*table)->sub_tables;
812 for (i = 0; i < (*table)->size; ++i)
813 {
814 string_sub_table_t *sub_table = sub_tables + i;
815
816 svn_temp_deserializer__resolve(sub_tables,
817 (void **)&sub_table->data);
818 svn_temp_deserializer__resolve(sub_tables,
819 (void **)&sub_table->short_strings);
820 svn_temp_deserializer__resolve(sub_tables,
821 (void **)&sub_table->long_strings);
822
823 for (k = 0; k < sub_table->long_string_count; ++k)
824 svn_temp_deserializer__resolve(sub_table->long_strings,
825 (void **)&sub_table->long_strings[k].data);
826 }
827 }
828
829 const char*
svn_fs_x__string_table_get_func(const string_table_t * table,apr_size_t idx,apr_size_t * length,apr_pool_t * pool)830 svn_fs_x__string_table_get_func(const string_table_t *table,
831 apr_size_t idx,
832 apr_size_t *length,
833 apr_pool_t *pool)
834 {
835 apr_size_t table_number = idx >> TABLE_SHIFT;
836 apr_size_t sub_index = idx & STRING_INDEX_MASK;
837
838 if (table_number < table->size)
839 {
840 /* resolve TABLE->SUB_TABLES pointer and select sub-table */
841 string_sub_table_t *sub_tables
842 = (string_sub_table_t *)svn_temp_deserializer__ptr(table,
843 (const void *const *)&table->sub_tables);
844 string_sub_table_t *sub_table = sub_tables + table_number;
845
846 /* pick the right kind of string */
847 if (idx & LONG_STRING_MASK)
848 {
849 if (sub_index < sub_table->long_string_count)
850 {
851 /* resolve SUB_TABLE->LONG_STRINGS, select the string we want
852 and resolve the pointer to its char data */
853 svn_string_t *long_strings
854 = (svn_string_t *)svn_temp_deserializer__ptr(sub_table,
855 (const void *const *)&sub_table->long_strings);
856 const char *str_data
857 = (const char*)svn_temp_deserializer__ptr(long_strings,
858 (const void *const *)&long_strings[sub_index].data);
859
860 /* return a copy of the char data */
861 if (length)
862 *length = long_strings[sub_index].len;
863
864 return apr_pstrmemdup(pool,
865 str_data,
866 long_strings[sub_index].len);
867 }
868 }
869 else
870 {
871 if (sub_index < sub_table->short_string_count)
872 {
873 string_header_t *header;
874 apr_size_t len;
875 char *result;
876
877 /* construct a copy of our sub-table struct with SHORT_STRINGS
878 and DATA pointers resolved. Leave all other pointers as
879 they are. This allows us to use the same code for string
880 reconstruction here as in the non-serialized case. */
881 string_sub_table_t table_copy = *sub_table;
882 table_copy.data
883 = (const char *)svn_temp_deserializer__ptr(sub_tables,
884 (const void *const *)&sub_table->data);
885 table_copy.short_strings
886 = (string_header_t *)svn_temp_deserializer__ptr(sub_tables,
887 (const void *const *)&sub_table->short_strings);
888
889 /* reconstruct the char data and return it */
890 header = table_copy.short_strings + sub_index;
891 len = header->head_length + header->tail_length;
892 result = apr_palloc(pool, len + PADDING);
893 if (length)
894 *length = len;
895
896 table_copy_string(result, len, &table_copy, header);
897
898 return result;
899 }
900 }
901 }
902
903 return "";
904 }
905