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 *result_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(result_pool,
 391                                      sizeof(*target->short_strings) *
 392                                            target->short_string_count);
 393   for (i = 0; i < source->short_strings->nelts; ++i)
 394     {
 395       const builder_string_t *string
 396         = APR_ARRAY_IDX(source->short_strings, i, const builder_string_t *);
 397
 398       string_header_t *entry = &target->short_strings[i];
 399       const char *tail = string->string.data + string->previous_match_len;
 400       string_header_t *tail_match;
 401       apr_size_t head_length = string->previous_match_len;
 402
 403       /* Minimize the number of strings to visit when reconstructing the
 404          string head.  So, skip all predecessors that don't contribute to
 405          first HEAD_LENGTH chars of our string. */
 406       if (head_length)
 407         {
 408           const builder_string_t *furthest_prev = string->previous;
 409           while (furthest_prev->previous_match_len >= head_length)
 410             furthest_prev = furthest_prev->previous;
 411           entry->head_string = furthest_prev->position;
 412         }
 413       else
 414         entry->head_string = 0;
 415
 416       /* head & tail length are known */
 417       entry->head_length = (apr_uint16_t)head_length;
 418       entry->tail_length
 419         = (apr_uint16_t)(string->string.len - entry->head_length);
 420
 421       /* try to reuse an existing tail segment */
 422       tail_match = apr_hash_get(tails, tail, entry->tail_length);
 423       if (tail_match)
 424         {
 425           entry->tail_start = tail_match->tail_start;
 426         }
 427       else
 428         {
 429           entry->tail_start = (apr_uint16_t)data->len;
 430           svn_stringbuf_appendbytes(data, tail, entry->tail_length);
 431           apr_hash_set(tails, tail, entry->tail_length, entry);
 432         }
 433     }
 434
 435   /* pack long strings */
 436   target->long_string_count = (apr_size_t)source->long_strings->nelts;
 437   target->long_strings = apr_palloc(result_pool,
 438                                     sizeof(*target->long_strings) *
 439                                           target->long_string_count);
 440   for (i = 0; i < source->long_strings->nelts; ++i)
 441     {
 442       svn_string_t *string = &target->long_strings[i];
 443       *string = APR_ARRAY_IDX(source->long_strings, i, svn_string_t);
 444       string->data = apr_pstrmemdup(result_pool, string->data, string->len);
 445     }
 446
 447   data->len += PADDING; /* add a few extra bytes at the end of the buffer
 448                            that we want to keep valid for chunky access */
 449   assert(data->len < data->blocksize);
 450   memset(data->data + data->len - PADDING, 0, PADDING);
 451
 452   target->data = apr_pmemdup(result_pool, data->data, data->len);
 453   target->data_size = data->len;
 454 }
 455
 456 string_table_t *
 457 svn_fs_x__string_table_create(const string_table_builder_t *builder,
 458                               apr_pool_t *result_pool)
 459 {
 460   apr_size_t i;
 461
 462   string_table_t *result = apr_pcalloc(result_pool, sizeof(*result));
 463   result->size = (apr_size_t)builder->tables->nelts;
 464   result->sub_tables
 465     = apr_pcalloc(result_pool, result->size * sizeof(*result->sub_tables));
 466
 467   for (i = 0; i < result->size; ++i)
 468     create_table(&result->sub_tables[i],
 469                  APR_ARRAY_IDX(builder->tables, i, builder_table_t*),
 470                  result_pool,
 471                  builder->pool);
 472
 473   return result;
 474 }
 475
 476 /* Masks used by table_copy_string.  copy_mask[I] is used if the target
 477    content to be preserved starts at byte I within the current chunk.
 478    This is used to work around alignment issues.
 479  */
 480 #if SVN_UNALIGNED_ACCESS_IS_OK
 481 static const char *copy_masks[8] = { "\xff\xff\xff\xff\xff\xff\xff\xff",
 482                                      "\x00\xff\xff\xff\xff\xff\xff\xff",
 483                                      "\x00\x00\xff\xff\xff\xff\xff\xff",
 484                                      "\x00\x00\x00\xff\xff\xff\xff\xff",
 485                                      "\x00\x00\x00\x00\xff\xff\xff\xff",
 486                                      "\x00\x00\x00\x00\x00\xff\xff\xff",
 487                                      "\x00\x00\x00\x00\x00\x00\xff\xff",
 488                                      "\x00\x00\x00\x00\x00\x00\x00\xff" };
 489 #endif
 490
 491 static void
 492 table_copy_string(char *buffer,
 493                   apr_size_t len,
 494                   const string_sub_table_t *table,
 495                   string_header_t *header)
 496 {
 497   buffer[len] = '\0';
 498   do
 499     {
 500       assert(header->head_length <= len);
 501         {
 502 #if SVN_UNALIGNED_ACCESS_IS_OK
 503           /* the sections that we copy tend to be short but we can copy
 504              *all* of it chunky because we made sure that source and target
 505              buffer have some extra padding to prevent segfaults. */
 506           apr_uint64_t mask;
 507           apr_size_t to_copy = len - header->head_length;
 508           apr_size_t copied = 0;
 509
 510           const char *source = table->data + header->tail_start;
 511           char *target = buffer + header->head_length;
 512           len = header->head_length;
 513
 514           /* copy whole chunks */
 515           while (to_copy >= copied + sizeof(apr_uint64_t))
 516             {
 517               *(apr_uint64_t *)(target + copied)
 518                 = *(const apr_uint64_t *)(source + copied);
 519               copied += sizeof(apr_uint64_t);
 520             }
 521
 522           /* copy the remainder assuming that we have up to 8 extra bytes
 523              of addressable buffer on the source and target sides.
 524              Now, we simply copy 8 bytes and use a mask to filter & merge
 525              old with new data. */
 526           mask = *(const apr_uint64_t *)copy_masks[to_copy - copied];
 527           *(apr_uint64_t *)(target + copied)
 528             = (*(apr_uint64_t *)(target + copied) & mask)
 529             | (*(const apr_uint64_t *)(source + copied) & ~mask);
 530 #else
 531           memcpy(buffer + header->head_length,
 532                  table->data + header->tail_start,
 533                  len - header->head_length);
 534           len = header->head_length;
 535 #endif
 536         }
 537
 538       header = &table->short_strings[header->head_string];
 539     }
 540   while (len);
 541 }
 542
 543 const char*
 544 svn_fs_x__string_table_get(const string_table_t *table,
 545                            apr_size_t idx,
 546                            apr_size_t *length,
 547                            apr_pool_t *result_pool)
 548 {
 549   apr_size_t table_number = idx >> TABLE_SHIFT;
 550   apr_size_t sub_index = idx & STRING_INDEX_MASK;
 551
 552   if (table_number < table->size)
 553     {
 554       string_sub_table_t *sub_table = &table->sub_tables[table_number];
 555       if (idx & LONG_STRING_MASK)
 556         {
 557           if (sub_index < sub_table->long_string_count)
 558             {
 559               if (length)
 560                 *length = sub_table->long_strings[sub_index].len;
 561
 562               return apr_pstrmemdup(result_pool,
 563                                     sub_table->long_strings[sub_index].data,
 564                                     sub_table->long_strings[sub_index].len);
 565             }
 566         }
 567       else
 568         {
 569           if (sub_index < sub_table->short_string_count)
 570             {
 571               string_header_t *header = sub_table->short_strings + sub_index;
 572               apr_size_t len = header->head_length + header->tail_length;
 573               char *result = apr_palloc(result_pool, len + PADDING);
 574
 575               if (length)
 576                 *length = len;
 577               table_copy_string(result, len, sub_table, header);
 578
 579               return result;
 580             }
 581         }
 582     }
 583
 584   return apr_pstrmemdup(result_pool, "", 0);
 585 }
 586
 587 svn_error_t *
 588 svn_fs_x__write_string_table(svn_stream_t *stream,
 589                              const string_table_t *table,
 590                              apr_pool_t *scratch_pool)
 591 {
 592   apr_size_t i, k;
 593
 594   svn_packed__data_root_t *root = svn_packed__data_create_root(scratch_pool);
 595
 596   svn_packed__int_stream_t *table_sizes
 597     = svn_packed__create_int_stream(root, FALSE, FALSE);
 598   svn_packed__int_stream_t *small_strings_headers
 599     = svn_packed__create_int_stream(root, FALSE, FALSE);
 600   svn_packed__byte_stream_t *large_strings
 601     = svn_packed__create_bytes_stream(root);
 602   svn_packed__byte_stream_t *small_strings_data
 603     = svn_packed__create_bytes_stream(root);
 604
 605   svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE);
 606   svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE);
 607   svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE);
 608   svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE);
 609
 610   /* number of sub-tables */
 611
 612   svn_packed__add_uint(table_sizes, table->size);
 613
 614   /* all short-string char data sizes */
 615
 616   for (i = 0; i < table->size; ++i)
 617     svn_packed__add_uint(table_sizes,
 618                          table->sub_tables[i].short_string_count);
 619
 620   for (i = 0; i < table->size; ++i)
 621     svn_packed__add_uint(table_sizes,
 622                          table->sub_tables[i].long_string_count);
 623
 624   /* all strings */
 625
 626   for (i = 0; i < table->size; ++i)
 627     {
 628       string_sub_table_t *sub_table = &table->sub_tables[i];
 629       svn_packed__add_bytes(small_strings_data,
 630                             sub_table->data,
 631                             sub_table->data_size);
 632
 633       for (k = 0; k < sub_table->short_string_count; ++k)
 634         {
 635           string_header_t *string = &sub_table->short_strings[k];
 636
 637           svn_packed__add_uint(small_strings_headers, string->head_string);
 638           svn_packed__add_uint(small_strings_headers, string->head_length);
 639           svn_packed__add_uint(small_strings_headers, string->tail_start);
 640           svn_packed__add_uint(small_strings_headers, string->tail_length);
 641         }
 642
 643       for (k = 0; k < sub_table->long_string_count; ++k)
 644         svn_packed__add_bytes(large_strings,
 645                               sub_table->long_strings[k].data,
 646                               sub_table->long_strings[k].len + 1);
 647     }
 648
 649   /* write to target stream */
 650
 651   SVN_ERR(svn_packed__data_write(stream, root, scratch_pool));
 652
 653   return SVN_NO_ERROR;
 654 }
 655
 656 svn_error_t *
 657 svn_fs_x__read_string_table(string_table_t **table_p,
 658                             svn_stream_t *stream,
 659                             apr_pool_t *result_pool,
 660                             apr_pool_t *scratch_pool)
 661 {
 662   apr_size_t i, k;
 663
 664   string_table_t *table = apr_palloc(result_pool, sizeof(*table));
 665
 666   svn_packed__data_root_t *root;
 667   svn_packed__int_stream_t *table_sizes;
 668   svn_packed__byte_stream_t *large_strings;
 669   svn_packed__byte_stream_t *small_strings_data;
 670   svn_packed__int_stream_t *headers;
 671
 672   SVN_ERR(svn_packed__data_read(&root, stream, result_pool, scratch_pool));
 673   table_sizes = svn_packed__first_int_stream(root);
 674   headers = svn_packed__next_int_stream(table_sizes);
 675   large_strings = svn_packed__first_byte_stream(root);
 676   small_strings_data = svn_packed__next_byte_stream(large_strings);
 677
 678   /* create sub-tables */
 679
 680   table->size = (apr_size_t)svn_packed__get_uint(table_sizes);
 681   table->sub_tables = apr_pcalloc(result_pool,
 682                                   table->size * sizeof(*table->sub_tables));
 683
 684   /* read short strings */
 685
 686   for (i = 0; i < table->size; ++i)
 687     {
 688       string_sub_table_t *sub_table = &table->sub_tables[i];
 689
 690       sub_table->short_string_count
 691         = (apr_size_t)svn_packed__get_uint(table_sizes);
 692       if (sub_table->short_string_count)
 693         {
 694           sub_table->short_strings
 695             = apr_pcalloc(result_pool, sub_table->short_string_count
 696                                     * sizeof(*sub_table->short_strings));
 697
 698           /* read short string headers */
 699
 700           for (k = 0; k < sub_table->short_string_count; ++k)
 701             {
 702               string_header_t *string = &sub_table->short_strings[k];
 703
 704               string->head_string = (apr_uint16_t)svn_packed__get_uint(headers);
 705               string->head_length = (apr_uint16_t)svn_packed__get_uint(headers);
 706               string->tail_start = (apr_uint16_t)svn_packed__get_uint(headers);
 707               string->tail_length = (apr_uint16_t)svn_packed__get_uint(headers);
 708             }
 709         }
 710
 711       sub_table->data = svn_packed__get_bytes(small_strings_data,
 712                                               &sub_table->data_size);
 713     }
 714
 715   /* read long strings */
 716
 717   for (i = 0; i < table->size; ++i)
 718     {
 719       /* initialize long string table */
 720       string_sub_table_t *sub_table = &table->sub_tables[i];
 721
 722       sub_table->long_string_count = svn_packed__get_uint(table_sizes);
 723       if (sub_table->long_string_count)
 724         {
 725           sub_table->long_strings
 726             = apr_pcalloc(result_pool, sub_table->long_string_count
 727                                     * sizeof(*sub_table->long_strings));
 728
 729           /* read long strings */
 730
 731           for (k = 0; k < sub_table->long_string_count; ++k)
 732             {
 733               svn_string_t *string = &sub_table->long_strings[k];
 734               string->data = svn_packed__get_bytes(large_strings,
 735                                                    &string->len);
 736               string->len--;
 737             }
 738         }
 739     }
 740
 741   /* done */
 742
 743   *table_p = table;
 744
 745   return SVN_NO_ERROR;
 746 }
 747
 748 void
 749 svn_fs_x__serialize_string_table(svn_temp_serializer__context_t *context,
 750                                  string_table_t **st)
 751 {
 752   apr_size_t i, k;
 753   string_table_t *string_table = *st;
 754   if (string_table == NULL)
 755     return;
 756
 757   /* string table struct */
 758   svn_temp_serializer__push(context,
 759                             (const void * const *)st,
 760                             sizeof(*string_table));
 761
 762   /* sub-table array (all structs in a single memory block) */
 763   svn_temp_serializer__push(context,
 764                             (const void * const *)&string_table->sub_tables,
 765                             sizeof(*string_table->sub_tables) *
 766                             string_table->size);
 767
 768   /* sub-elements of all sub-tables */
 769   for (i = 0; i < string_table->size; ++i)
 770     {
 771       string_sub_table_t *sub_table = &string_table->sub_tables[i];
 772       svn_temp_serializer__add_leaf(context,
 773                                     (const void * const *)&sub_table->data,
 774                                     sub_table->data_size);
 775       svn_temp_serializer__add_leaf(context,
 776                     (const void * const *)&sub_table->short_strings,
 777                     sub_table->short_string_count * sizeof(string_header_t));
 778
 779       /* all "long string" instances form a single memory block */
 780       svn_temp_serializer__push(context,
 781                     (const void * const *)&sub_table->long_strings,
 782                     sub_table->long_string_count * sizeof(svn_string_t));
 783
 784       /* serialize actual long string contents */
 785       for (k = 0; k < sub_table->long_string_count; ++k)
 786         {
 787           svn_string_t *string = &sub_table->long_strings[k];
 788           svn_temp_serializer__add_leaf(context,
 789                                         (const void * const *)&string->data,
 790                                         string->len + 1);
 791         }
 792
 793       svn_temp_serializer__pop(context);
 794     }
 795
 796   /* back to the caller's nesting level */
 797   svn_temp_serializer__pop(context);
 798   svn_temp_serializer__pop(context);
 799 }
 800
 801 void
 802 svn_fs_x__deserialize_string_table(void *buffer,
 803                                    string_table_t **table)
 804 {
 805   apr_size_t i, k;
 806   string_sub_table_t *sub_tables;
 807
 808   svn_temp_deserializer__resolve(buffer, (void **)table);
 809   if (*table == NULL)
 810     return;
 811
 812   svn_temp_deserializer__resolve(*table, (void **)&(*table)->sub_tables);
 813   sub_tables = (*table)->sub_tables;
 814   for (i = 0; i < (*table)->size; ++i)
 815     {
 816       string_sub_table_t *sub_table = sub_tables + i;
 817
 818       svn_temp_deserializer__resolve(sub_tables,
 819                                      (void **)&sub_table->data);
 820       svn_temp_deserializer__resolve(sub_tables,
 821                                      (void **)&sub_table->short_strings);
 822       svn_temp_deserializer__resolve(sub_tables,
 823                                      (void **)&sub_table->long_strings);
 824
 825       for (k = 0; k < sub_table->long_string_count; ++k)
 826         svn_temp_deserializer__resolve(sub_table->long_strings,
 827                                (void **)&sub_table->long_strings[k].data);
 828     }
 829 }
 830
 831 const char*
 832 svn_fs_x__string_table_get_func(const string_table_t *table,
 833                                 apr_size_t idx,
 834                                 apr_size_t *length,
 835                                 apr_pool_t *result_pool)
 836 {
 837   apr_size_t table_number = idx >> TABLE_SHIFT;
 838   apr_size_t sub_index = idx & STRING_INDEX_MASK;
 839
 840   if (table_number < table->size)
 841     {
 842       /* resolve TABLE->SUB_TABLES pointer and select sub-table */
 843       string_sub_table_t *sub_tables
 844         = (string_sub_table_t *)svn_temp_deserializer__ptr(table,
 845                                    (const void *const *)&table->sub_tables);
 846       string_sub_table_t *sub_table = sub_tables + table_number;
 847
 848       /* pick the right kind of string */
 849       if (idx & LONG_STRING_MASK)
 850         {
 851           if (sub_index < sub_table->long_string_count)
 852             {
 853               /* resolve SUB_TABLE->LONG_STRINGS, select the string we want
 854                  and resolve the pointer to its char data */
 855               svn_string_t *long_strings
 856                 = (svn_string_t *)svn_temp_deserializer__ptr(sub_table,
 857                              (const void *const *)&sub_table->long_strings);
 858               const char *str_data
 859                 = (const char*)svn_temp_deserializer__ptr(long_strings,
 860                         (const void *const *)&long_strings[sub_index].data);
 861
 862               /* return a copy of the char data */
 863               if (length)
 864                 *length = long_strings[sub_index].len;
 865
 866               return apr_pstrmemdup(result_pool,
 867                                     str_data,
 868                                     long_strings[sub_index].len);
 869             }
 870         }
 871       else
 872         {
 873           if (sub_index < sub_table->short_string_count)
 874             {
 875               string_header_t *header;
 876               apr_size_t len;
 877               char *result;
 878
 879               /* construct a copy of our sub-table struct with SHORT_STRINGS
 880                  and DATA pointers resolved.  Leave all other pointers as
 881                  they are.  This allows us to use the same code for string
 882                  reconstruction here as in the non-serialized case. */
 883               string_sub_table_t table_copy = *sub_table;
 884               table_copy.data
 885                 = (const char *)svn_temp_deserializer__ptr(sub_tables,
 886                                      (const void *const *)&sub_table->data);
 887               table_copy.short_strings
 888                 = (string_header_t *)svn_temp_deserializer__ptr(sub_tables,
 889                             (const void *const *)&sub_table->short_strings);
 890
 891               /* reconstruct the char data and return it */
 892               header = table_copy.short_strings + sub_index;
 893               len = header->head_length + header->tail_length;
 894               result = apr_palloc(result_pool, len + PADDING);
 895               if (length)
 896                 *length = len;
 897
 898               table_copy_string(result, len, &table_copy, header);
 899
 900               return result;
 901             }
 902         }
 903     }
 904
 905   return "";
 906 }