contrib/subversion/subversion/libsvn_fs_x/string_table.c

   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 \f
  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 \f
  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 \f
 104 /* Accessing ID Pieces.  */
 105
 106 static builder_table_t *
 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 *
 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
 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
 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
 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(&current->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, &current->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(&current->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, &current->right, to_insert);
 266     }
 267
 268   balance(table, parent, current);
 269   return result;
 270 }
 271
 272 apr_size_t
 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
 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
 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 *
 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
 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*
 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 *
 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 *
 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
 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
 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*
 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 }