1289177Speter/* string_table.c : operations on string tables 2289177Speter * 3289177Speter * ==================================================================== 4289177Speter * Licensed to the Apache Software Foundation (ASF) under one 5289177Speter * or more contributor license agreements. See the NOTICE file 6289177Speter * distributed with this work for additional information 7289177Speter * regarding copyright ownership. The ASF licenses this file 8289177Speter * to you under the Apache License, Version 2.0 (the 9289177Speter * "License"); you may not use this file except in compliance 10289177Speter * with the License. You may obtain a copy of the License at 11289177Speter * 12289177Speter * http://www.apache.org/licenses/LICENSE-2.0 13289177Speter * 14289177Speter * Unless required by applicable law or agreed to in writing, 15289177Speter * software distributed under the License is distributed on an 16289177Speter * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 17289177Speter * KIND, either express or implied. See the License for the 18289177Speter * specific language governing permissions and limitations 19289177Speter * under the License. 20289177Speter * ==================================================================== 21289177Speter */ 22289177Speter 23289177Speter#include <assert.h> 24289177Speter#include <string.h> 25289177Speter#include <apr_tables.h> 26289177Speter 27289177Speter#include "svn_string.h" 28289177Speter#include "svn_sorts.h" 29289177Speter#include "private/svn_dep_compat.h" 30289177Speter#include "private/svn_string_private.h" 31289177Speter#include "private/svn_subr_private.h" 32289177Speter#include "private/svn_packed_data.h" 33289177Speter#include "string_table.h" 34289177Speter 35289177Speter 36289177Speter 37289177Speter#define MAX_DATA_SIZE 0xffff 38289177Speter#define MAX_SHORT_STRING_LEN (MAX_DATA_SIZE / 4) 39289177Speter#define TABLE_SHIFT 13 40289177Speter#define MAX_STRINGS_PER_TABLE (1 << (TABLE_SHIFT - 1)) 41289177Speter#define LONG_STRING_MASK (1 << (TABLE_SHIFT - 1)) 42289177Speter#define STRING_INDEX_MASK ((1 << (TABLE_SHIFT - 1)) - 1) 43289177Speter#define PADDING (sizeof(apr_uint64_t)) 44289177Speter 45289177Speter 46289177Spetertypedef struct builder_string_t 47289177Speter{ 48289177Speter svn_string_t string; 49289177Speter int position; 50289177Speter apr_size_t depth; 51289177Speter struct builder_string_t *previous; 52289177Speter struct builder_string_t *next; 53289177Speter apr_size_t previous_match_len; 54289177Speter apr_size_t next_match_len; 55289177Speter struct builder_string_t *left; 56289177Speter struct builder_string_t *right; 57289177Speter} builder_string_t; 58289177Speter 59289177Spetertypedef struct builder_table_t 60289177Speter{ 61289177Speter apr_size_t max_data_size; 62289177Speter builder_string_t *top; 63289177Speter builder_string_t *first; 64289177Speter builder_string_t *last; 65289177Speter apr_array_header_t *short_strings; 66289177Speter apr_array_header_t *long_strings; 67289177Speter apr_hash_t *long_string_dict; 68289177Speter apr_size_t long_string_size; 69289177Speter} builder_table_t; 70289177Speter 71289177Speterstruct string_table_builder_t 72289177Speter{ 73289177Speter apr_pool_t *pool; 74289177Speter apr_array_header_t *tables; 75289177Speter}; 76289177Speter 77289177Spetertypedef struct string_header_t 78289177Speter{ 79289177Speter apr_uint16_t head_string; 80289177Speter apr_uint16_t head_length; 81289177Speter apr_uint16_t tail_start; 82289177Speter apr_uint16_t tail_length; 83289177Speter} string_header_t; 84289177Speter 85289177Spetertypedef struct string_sub_table_t 86289177Speter{ 87289177Speter const char *data; 88289177Speter apr_size_t data_size; 89289177Speter 90289177Speter string_header_t *short_strings; 91289177Speter apr_size_t short_string_count; 92289177Speter 93289177Speter svn_string_t *long_strings; 94289177Speter apr_size_t long_string_count; 95289177Speter} string_sub_table_t; 96289177Speter 97289177Speterstruct string_table_t 98289177Speter{ 99289177Speter apr_size_t size; 100289177Speter string_sub_table_t *sub_tables; 101289177Speter}; 102289177Speter 103289177Speter 104289177Speter/* Accessing ID Pieces. */ 105289177Speter 106289177Speterstatic builder_table_t * 107289177Speteradd_table(string_table_builder_t *builder) 108289177Speter{ 109289177Speter builder_table_t *table = apr_pcalloc(builder->pool, sizeof(*table)); 110289177Speter table->max_data_size = MAX_DATA_SIZE - PADDING; /* ensure there remain a few 111289177Speter unused bytes at the end */ 112289177Speter table->short_strings = apr_array_make(builder->pool, 64, 113289177Speter sizeof(builder_string_t *)); 114289177Speter table->long_strings = apr_array_make(builder->pool, 0, 115289177Speter sizeof(svn_string_t)); 116289177Speter table->long_string_dict = svn_hash__make(builder->pool); 117289177Speter 118289177Speter APR_ARRAY_PUSH(builder->tables, builder_table_t *) = table; 119289177Speter 120289177Speter return table; 121289177Speter} 122289177Speter 123289177Speterstring_table_builder_t * 124289177Spetersvn_fs_x__string_table_builder_create(apr_pool_t *result_pool) 125289177Speter{ 126289177Speter string_table_builder_t *result = apr_palloc(result_pool, sizeof(*result)); 127289177Speter result->pool = result_pool; 128289177Speter result->tables = apr_array_make(result_pool, 1, sizeof(builder_table_t *)); 129289177Speter 130289177Speter add_table(result); 131289177Speter 132289177Speter return result; 133289177Speter} 134289177Speter 135289177Speterstatic void 136289177Speterbalance(builder_table_t *table, 137289177Speter builder_string_t **parent, 138289177Speter builder_string_t *node) 139289177Speter{ 140289177Speter apr_size_t left_height = node->left ? node->left->depth + 1 : 0; 141289177Speter apr_size_t right_height = node->right ? node->right->depth + 1 : 0; 142289177Speter 143289177Speter if (left_height > right_height + 1) 144289177Speter { 145289177Speter builder_string_t *temp = node->left->right; 146289177Speter node->left->right = node; 147289177Speter *parent = node->left; 148289177Speter node->left = temp; 149289177Speter 150289177Speter --left_height; 151289177Speter } 152289177Speter else if (left_height + 1 < right_height) 153289177Speter { 154289177Speter builder_string_t *temp = node->right->left; 155289177Speter *parent = node->right; 156289177Speter node->right->left = node; 157289177Speter node->right = temp; 158289177Speter 159289177Speter --right_height; 160289177Speter } 161289177Speter 162289177Speter node->depth = MAX(left_height, right_height); 163289177Speter} 164289177Speter 165289177Speterstatic apr_uint16_t 166289177Spetermatch_length(const svn_string_t *lhs, 167289177Speter const svn_string_t *rhs) 168289177Speter{ 169289177Speter apr_size_t len = MIN(lhs->len, rhs->len); 170289177Speter return (apr_uint16_t)svn_cstring__match_length(lhs->data, rhs->data, len); 171289177Speter} 172289177Speter 173289177Speterstatic apr_uint16_t 174289177Speterinsert_string(builder_table_t *table, 175289177Speter builder_string_t **parent, 176289177Speter builder_string_t *to_insert) 177289177Speter{ 178289177Speter apr_uint16_t result; 179289177Speter builder_string_t *current = *parent; 180289177Speter int diff = strcmp(current->string.data, to_insert->string.data); 181289177Speter if (diff == 0) 182289177Speter { 183289177Speter apr_array_pop(table->short_strings); 184289177Speter return current->position; 185289177Speter } 186289177Speter 187289177Speter if (diff < 0) 188289177Speter { 189289177Speter if (current->left == NULL) 190289177Speter { 191289177Speter current->left = to_insert; 192289177Speter 193289177Speter to_insert->previous = current->previous; 194289177Speter to_insert->next = current; 195289177Speter 196289177Speter if (to_insert->previous == NULL) 197289177Speter { 198289177Speter table->first = to_insert; 199289177Speter } 200289177Speter else 201289177Speter { 202289177Speter builder_string_t *previous = to_insert->previous; 203289177Speter to_insert->previous_match_len 204289177Speter = match_length(&previous->string, &to_insert->string); 205289177Speter 206289177Speter previous->next = to_insert; 207289177Speter previous->next_match_len = to_insert->previous_match_len; 208289177Speter } 209289177Speter 210289177Speter current->previous = to_insert; 211289177Speter to_insert->next_match_len 212289177Speter = match_length(¤t->string, &to_insert->string); 213289177Speter current->previous_match_len = to_insert->next_match_len; 214289177Speter 215289177Speter table->max_data_size -= to_insert->string.len; 216289177Speter if (to_insert->previous == NULL) 217289177Speter table->max_data_size += to_insert->next_match_len; 218289177Speter else 219289177Speter table->max_data_size += MIN(to_insert->previous_match_len, 220289177Speter to_insert->next_match_len); 221289177Speter 222289177Speter return to_insert->position; 223289177Speter } 224289177Speter else 225289177Speter result = insert_string(table, ¤t->left, to_insert); 226289177Speter } 227289177Speter else 228289177Speter { 229289177Speter if (current->right == NULL) 230289177Speter { 231289177Speter current->right = to_insert; 232289177Speter 233289177Speter to_insert->next = current->next; 234289177Speter to_insert->previous = current; 235289177Speter 236289177Speter if (to_insert->next == NULL) 237289177Speter { 238289177Speter table->last = to_insert; 239289177Speter } 240289177Speter else 241289177Speter { 242289177Speter builder_string_t *next = to_insert->next; 243289177Speter to_insert->next_match_len 244289177Speter = match_length(&next->string, &to_insert->string); 245289177Speter 246289177Speter next->previous = to_insert; 247289177Speter next->previous_match_len = to_insert->next_match_len; 248289177Speter } 249289177Speter 250289177Speter current->next = current->right; 251289177Speter to_insert->previous_match_len 252289177Speter = match_length(¤t->string, &to_insert->string); 253289177Speter current->next_match_len = to_insert->previous_match_len; 254289177Speter 255289177Speter table->max_data_size -= to_insert->string.len; 256289177Speter if (to_insert->next == NULL) 257289177Speter table->max_data_size += to_insert->previous_match_len; 258289177Speter else 259289177Speter table->max_data_size += MIN(to_insert->previous_match_len, 260289177Speter to_insert->next_match_len); 261289177Speter 262289177Speter return to_insert->position; 263289177Speter } 264289177Speter else 265289177Speter result = insert_string(table, ¤t->right, to_insert); 266289177Speter } 267289177Speter 268289177Speter balance(table, parent, current); 269289177Speter return result; 270289177Speter} 271289177Speter 272289177Speterapr_size_t 273289177Spetersvn_fs_x__string_table_builder_add(string_table_builder_t *builder, 274289177Speter const char *string, 275289177Speter apr_size_t len) 276289177Speter{ 277289177Speter apr_size_t result; 278289177Speter builder_table_t *table = APR_ARRAY_IDX(builder->tables, 279289177Speter builder->tables->nelts - 1, 280289177Speter builder_table_t *); 281289177Speter if (len == 0) 282289177Speter len = strlen(string); 283289177Speter 284289177Speter string = apr_pstrmemdup(builder->pool, string, len); 285289177Speter if (len > MAX_SHORT_STRING_LEN) 286289177Speter { 287289177Speter void *idx_void; 288289177Speter svn_string_t item; 289289177Speter item.data = string; 290289177Speter item.len = len; 291289177Speter 292289177Speter idx_void = apr_hash_get(table->long_string_dict, string, len); 293289177Speter result = (apr_uintptr_t)idx_void; 294289177Speter if (result) 295289177Speter return result - 1 296289177Speter + LONG_STRING_MASK 297289177Speter + (((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT); 298289177Speter 299289177Speter if (table->long_strings->nelts == MAX_STRINGS_PER_TABLE) 300289177Speter table = add_table(builder); 301289177Speter 302289177Speter result = table->long_strings->nelts 303289177Speter + LONG_STRING_MASK 304289177Speter + (((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT); 305289177Speter APR_ARRAY_PUSH(table->long_strings, svn_string_t) = item; 306289177Speter apr_hash_set(table->long_string_dict, string, len, 307289177Speter (void*)(apr_uintptr_t)table->long_strings->nelts); 308289177Speter 309289177Speter table->long_string_size += len; 310289177Speter } 311289177Speter else 312289177Speter { 313289177Speter builder_string_t *item = apr_pcalloc(builder->pool, sizeof(*item)); 314289177Speter item->string.data = string; 315289177Speter item->string.len = len; 316289177Speter item->previous_match_len = 0; 317289177Speter item->next_match_len = 0; 318289177Speter 319289177Speter if ( table->short_strings->nelts == MAX_STRINGS_PER_TABLE 320289177Speter || table->max_data_size < len) 321289177Speter table = add_table(builder); 322289177Speter 323289177Speter item->position = table->short_strings->nelts; 324289177Speter APR_ARRAY_PUSH(table->short_strings, builder_string_t *) = item; 325289177Speter 326289177Speter if (table->top == NULL) 327289177Speter { 328289177Speter table->max_data_size -= len; 329289177Speter table->top = item; 330289177Speter table->first = item; 331289177Speter table->last = item; 332289177Speter 333289177Speter result = ((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT; 334289177Speter } 335289177Speter else 336289177Speter { 337289177Speter result = insert_string(table, &table->top, item) 338289177Speter + (((apr_size_t)builder->tables->nelts - 1) << TABLE_SHIFT); 339289177Speter } 340289177Speter } 341289177Speter 342289177Speter return result; 343289177Speter} 344289177Speter 345289177Speterapr_size_t 346289177Spetersvn_fs_x__string_table_builder_estimate_size(string_table_builder_t *builder) 347289177Speter{ 348289177Speter apr_size_t total = 0; 349289177Speter int i; 350289177Speter 351289177Speter for (i = 0; i < builder->tables->nelts; ++i) 352289177Speter { 353289177Speter builder_table_t *table 354289177Speter = APR_ARRAY_IDX(builder->tables, i, builder_table_t*); 355289177Speter 356289177Speter /* total number of chars to store, 357289177Speter * 8 bytes per short string table entry 358289177Speter * 4 bytes per long string table entry 359289177Speter * some static overhead */ 360289177Speter apr_size_t table_size 361289177Speter = MAX_DATA_SIZE - table->max_data_size 362289177Speter + table->long_string_size 363289177Speter + table->short_strings->nelts * 8 364289177Speter + table->long_strings->nelts * 4 365289177Speter + 10; 366289177Speter 367289177Speter total += table_size; 368289177Speter } 369289177Speter 370289177Speter /* ZIP compression should give us a 50% reduction. 371289177Speter * add some static overhead */ 372289177Speter return 200 + total / 2; 373289177Speter 374289177Speter} 375289177Speter 376289177Speterstatic void 377289177Spetercreate_table(string_sub_table_t *target, 378289177Speter builder_table_t *source, 379362181Sdim apr_pool_t *result_pool, 380289177Speter apr_pool_t *scratch_pool) 381289177Speter{ 382289177Speter int i = 0; 383289177Speter apr_hash_t *tails = svn_hash__make(scratch_pool); 384289177Speter svn_stringbuf_t *data 385289177Speter = svn_stringbuf_create_ensure(MAX_DATA_SIZE - source->max_data_size, 386289177Speter scratch_pool); 387289177Speter 388289177Speter /* pack sub-strings */ 389289177Speter target->short_string_count = (apr_size_t)source->short_strings->nelts; 390362181Sdim target->short_strings = apr_palloc(result_pool, 391362181Sdim sizeof(*target->short_strings) * 392289177Speter target->short_string_count); 393289177Speter for (i = 0; i < source->short_strings->nelts; ++i) 394289177Speter { 395289177Speter const builder_string_t *string 396289177Speter = APR_ARRAY_IDX(source->short_strings, i, const builder_string_t *); 397289177Speter 398289177Speter string_header_t *entry = &target->short_strings[i]; 399289177Speter const char *tail = string->string.data + string->previous_match_len; 400289177Speter string_header_t *tail_match; 401289177Speter apr_size_t head_length = string->previous_match_len; 402289177Speter 403289177Speter /* Minimize the number of strings to visit when reconstructing the 404289177Speter string head. So, skip all predecessors that don't contribute to 405289177Speter first HEAD_LENGTH chars of our string. */ 406289177Speter if (head_length) 407289177Speter { 408289177Speter const builder_string_t *furthest_prev = string->previous; 409289177Speter while (furthest_prev->previous_match_len >= head_length) 410289177Speter furthest_prev = furthest_prev->previous; 411289177Speter entry->head_string = furthest_prev->position; 412289177Speter } 413289177Speter else 414289177Speter entry->head_string = 0; 415289177Speter 416289177Speter /* head & tail length are known */ 417289177Speter entry->head_length = (apr_uint16_t)head_length; 418289177Speter entry->tail_length 419289177Speter = (apr_uint16_t)(string->string.len - entry->head_length); 420289177Speter 421289177Speter /* try to reuse an existing tail segment */ 422289177Speter tail_match = apr_hash_get(tails, tail, entry->tail_length); 423289177Speter if (tail_match) 424289177Speter { 425289177Speter entry->tail_start = tail_match->tail_start; 426289177Speter } 427289177Speter else 428289177Speter { 429289177Speter entry->tail_start = (apr_uint16_t)data->len; 430289177Speter svn_stringbuf_appendbytes(data, tail, entry->tail_length); 431289177Speter apr_hash_set(tails, tail, entry->tail_length, entry); 432289177Speter } 433289177Speter } 434289177Speter 435289177Speter /* pack long strings */ 436289177Speter target->long_string_count = (apr_size_t)source->long_strings->nelts; 437362181Sdim target->long_strings = apr_palloc(result_pool, 438362181Sdim sizeof(*target->long_strings) * 439289177Speter target->long_string_count); 440289177Speter for (i = 0; i < source->long_strings->nelts; ++i) 441289177Speter { 442289177Speter svn_string_t *string = &target->long_strings[i]; 443289177Speter *string = APR_ARRAY_IDX(source->long_strings, i, svn_string_t); 444362181Sdim string->data = apr_pstrmemdup(result_pool, string->data, string->len); 445289177Speter } 446289177Speter 447289177Speter data->len += PADDING; /* add a few extra bytes at the end of the buffer 448289177Speter that we want to keep valid for chunky access */ 449289177Speter assert(data->len < data->blocksize); 450289177Speter memset(data->data + data->len - PADDING, 0, PADDING); 451289177Speter 452362181Sdim target->data = apr_pmemdup(result_pool, data->data, data->len); 453289177Speter target->data_size = data->len; 454289177Speter} 455289177Speter 456289177Speterstring_table_t * 457289177Spetersvn_fs_x__string_table_create(const string_table_builder_t *builder, 458362181Sdim apr_pool_t *result_pool) 459289177Speter{ 460289177Speter apr_size_t i; 461289177Speter 462362181Sdim string_table_t *result = apr_pcalloc(result_pool, sizeof(*result)); 463289177Speter result->size = (apr_size_t)builder->tables->nelts; 464289177Speter result->sub_tables 465362181Sdim = apr_pcalloc(result_pool, result->size * sizeof(*result->sub_tables)); 466289177Speter 467289177Speter for (i = 0; i < result->size; ++i) 468289177Speter create_table(&result->sub_tables[i], 469289177Speter APR_ARRAY_IDX(builder->tables, i, builder_table_t*), 470362181Sdim result_pool, 471289177Speter builder->pool); 472289177Speter 473289177Speter return result; 474289177Speter} 475289177Speter 476289177Speter/* Masks used by table_copy_string. copy_mask[I] is used if the target 477289177Speter content to be preserved starts at byte I within the current chunk. 478289177Speter This is used to work around alignment issues. 479289177Speter */ 480289177Speter#if SVN_UNALIGNED_ACCESS_IS_OK 481289177Speterstatic const char *copy_masks[8] = { "\xff\xff\xff\xff\xff\xff\xff\xff", 482289177Speter "\x00\xff\xff\xff\xff\xff\xff\xff", 483289177Speter "\x00\x00\xff\xff\xff\xff\xff\xff", 484289177Speter "\x00\x00\x00\xff\xff\xff\xff\xff", 485289177Speter "\x00\x00\x00\x00\xff\xff\xff\xff", 486289177Speter "\x00\x00\x00\x00\x00\xff\xff\xff", 487289177Speter "\x00\x00\x00\x00\x00\x00\xff\xff", 488289177Speter "\x00\x00\x00\x00\x00\x00\x00\xff" }; 489289177Speter#endif 490289177Speter 491289177Speterstatic void 492289177Spetertable_copy_string(char *buffer, 493289177Speter apr_size_t len, 494289177Speter const string_sub_table_t *table, 495289177Speter string_header_t *header) 496289177Speter{ 497289177Speter buffer[len] = '\0'; 498289177Speter do 499289177Speter { 500289177Speter assert(header->head_length <= len); 501289177Speter { 502289177Speter#if SVN_UNALIGNED_ACCESS_IS_OK 503289177Speter /* the sections that we copy tend to be short but we can copy 504289177Speter *all* of it chunky because we made sure that source and target 505289177Speter buffer have some extra padding to prevent segfaults. */ 506289177Speter apr_uint64_t mask; 507289177Speter apr_size_t to_copy = len - header->head_length; 508289177Speter apr_size_t copied = 0; 509289177Speter 510289177Speter const char *source = table->data + header->tail_start; 511289177Speter char *target = buffer + header->head_length; 512289177Speter len = header->head_length; 513289177Speter 514289177Speter /* copy whole chunks */ 515289177Speter while (to_copy >= copied + sizeof(apr_uint64_t)) 516289177Speter { 517289177Speter *(apr_uint64_t *)(target + copied) 518289177Speter = *(const apr_uint64_t *)(source + copied); 519289177Speter copied += sizeof(apr_uint64_t); 520289177Speter } 521289177Speter 522289177Speter /* copy the remainder assuming that we have up to 8 extra bytes 523289177Speter of addressable buffer on the source and target sides. 524289177Speter Now, we simply copy 8 bytes and use a mask to filter & merge 525289177Speter old with new data. */ 526289177Speter mask = *(const apr_uint64_t *)copy_masks[to_copy - copied]; 527289177Speter *(apr_uint64_t *)(target + copied) 528289177Speter = (*(apr_uint64_t *)(target + copied) & mask) 529289177Speter | (*(const apr_uint64_t *)(source + copied) & ~mask); 530289177Speter#else 531289177Speter memcpy(buffer + header->head_length, 532289177Speter table->data + header->tail_start, 533289177Speter len - header->head_length); 534289177Speter len = header->head_length; 535289177Speter#endif 536289177Speter } 537289177Speter 538289177Speter header = &table->short_strings[header->head_string]; 539289177Speter } 540289177Speter while (len); 541289177Speter} 542289177Speter 543289177Speterconst char* 544289177Spetersvn_fs_x__string_table_get(const string_table_t *table, 545289177Speter apr_size_t idx, 546289177Speter apr_size_t *length, 547362181Sdim apr_pool_t *result_pool) 548289177Speter{ 549289177Speter apr_size_t table_number = idx >> TABLE_SHIFT; 550289177Speter apr_size_t sub_index = idx & STRING_INDEX_MASK; 551289177Speter 552289177Speter if (table_number < table->size) 553289177Speter { 554289177Speter string_sub_table_t *sub_table = &table->sub_tables[table_number]; 555289177Speter if (idx & LONG_STRING_MASK) 556289177Speter { 557289177Speter if (sub_index < sub_table->long_string_count) 558289177Speter { 559289177Speter if (length) 560289177Speter *length = sub_table->long_strings[sub_index].len; 561289177Speter 562362181Sdim return apr_pstrmemdup(result_pool, 563289177Speter sub_table->long_strings[sub_index].data, 564289177Speter sub_table->long_strings[sub_index].len); 565289177Speter } 566289177Speter } 567289177Speter else 568289177Speter { 569289177Speter if (sub_index < sub_table->short_string_count) 570289177Speter { 571289177Speter string_header_t *header = sub_table->short_strings + sub_index; 572289177Speter apr_size_t len = header->head_length + header->tail_length; 573362181Sdim char *result = apr_palloc(result_pool, len + PADDING); 574289177Speter 575289177Speter if (length) 576289177Speter *length = len; 577289177Speter table_copy_string(result, len, sub_table, header); 578289177Speter 579289177Speter return result; 580289177Speter } 581289177Speter } 582289177Speter } 583289177Speter 584362181Sdim return apr_pstrmemdup(result_pool, "", 0); 585289177Speter} 586289177Speter 587289177Spetersvn_error_t * 588289177Spetersvn_fs_x__write_string_table(svn_stream_t *stream, 589289177Speter const string_table_t *table, 590289177Speter apr_pool_t *scratch_pool) 591289177Speter{ 592289177Speter apr_size_t i, k; 593289177Speter 594289177Speter svn_packed__data_root_t *root = svn_packed__data_create_root(scratch_pool); 595289177Speter 596289177Speter svn_packed__int_stream_t *table_sizes 597289177Speter = svn_packed__create_int_stream(root, FALSE, FALSE); 598289177Speter svn_packed__int_stream_t *small_strings_headers 599289177Speter = svn_packed__create_int_stream(root, FALSE, FALSE); 600289177Speter svn_packed__byte_stream_t *large_strings 601289177Speter = svn_packed__create_bytes_stream(root); 602289177Speter svn_packed__byte_stream_t *small_strings_data 603289177Speter = svn_packed__create_bytes_stream(root); 604289177Speter 605289177Speter svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE); 606289177Speter svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE); 607289177Speter svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE); 608289177Speter svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE); 609289177Speter 610289177Speter /* number of sub-tables */ 611289177Speter 612289177Speter svn_packed__add_uint(table_sizes, table->size); 613289177Speter 614289177Speter /* all short-string char data sizes */ 615289177Speter 616289177Speter for (i = 0; i < table->size; ++i) 617289177Speter svn_packed__add_uint(table_sizes, 618289177Speter table->sub_tables[i].short_string_count); 619289177Speter 620289177Speter for (i = 0; i < table->size; ++i) 621289177Speter svn_packed__add_uint(table_sizes, 622289177Speter table->sub_tables[i].long_string_count); 623289177Speter 624289177Speter /* all strings */ 625289177Speter 626289177Speter for (i = 0; i < table->size; ++i) 627289177Speter { 628289177Speter string_sub_table_t *sub_table = &table->sub_tables[i]; 629289177Speter svn_packed__add_bytes(small_strings_data, 630289177Speter sub_table->data, 631289177Speter sub_table->data_size); 632289177Speter 633289177Speter for (k = 0; k < sub_table->short_string_count; ++k) 634289177Speter { 635289177Speter string_header_t *string = &sub_table->short_strings[k]; 636289177Speter 637289177Speter svn_packed__add_uint(small_strings_headers, string->head_string); 638289177Speter svn_packed__add_uint(small_strings_headers, string->head_length); 639289177Speter svn_packed__add_uint(small_strings_headers, string->tail_start); 640289177Speter svn_packed__add_uint(small_strings_headers, string->tail_length); 641289177Speter } 642289177Speter 643289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 644289177Speter svn_packed__add_bytes(large_strings, 645289177Speter sub_table->long_strings[k].data, 646289177Speter sub_table->long_strings[k].len + 1); 647289177Speter } 648289177Speter 649289177Speter /* write to target stream */ 650289177Speter 651289177Speter SVN_ERR(svn_packed__data_write(stream, root, scratch_pool)); 652289177Speter 653289177Speter return SVN_NO_ERROR; 654289177Speter} 655289177Speter 656289177Spetersvn_error_t * 657289177Spetersvn_fs_x__read_string_table(string_table_t **table_p, 658289177Speter svn_stream_t *stream, 659289177Speter apr_pool_t *result_pool, 660289177Speter apr_pool_t *scratch_pool) 661289177Speter{ 662289177Speter apr_size_t i, k; 663289177Speter 664289177Speter string_table_t *table = apr_palloc(result_pool, sizeof(*table)); 665289177Speter 666289177Speter svn_packed__data_root_t *root; 667289177Speter svn_packed__int_stream_t *table_sizes; 668289177Speter svn_packed__byte_stream_t *large_strings; 669289177Speter svn_packed__byte_stream_t *small_strings_data; 670289177Speter svn_packed__int_stream_t *headers; 671289177Speter 672289177Speter SVN_ERR(svn_packed__data_read(&root, stream, result_pool, scratch_pool)); 673289177Speter table_sizes = svn_packed__first_int_stream(root); 674289177Speter headers = svn_packed__next_int_stream(table_sizes); 675289177Speter large_strings = svn_packed__first_byte_stream(root); 676289177Speter small_strings_data = svn_packed__next_byte_stream(large_strings); 677289177Speter 678289177Speter /* create sub-tables */ 679289177Speter 680289177Speter table->size = (apr_size_t)svn_packed__get_uint(table_sizes); 681289177Speter table->sub_tables = apr_pcalloc(result_pool, 682289177Speter table->size * sizeof(*table->sub_tables)); 683289177Speter 684289177Speter /* read short strings */ 685289177Speter 686289177Speter for (i = 0; i < table->size; ++i) 687289177Speter { 688289177Speter string_sub_table_t *sub_table = &table->sub_tables[i]; 689289177Speter 690289177Speter sub_table->short_string_count 691289177Speter = (apr_size_t)svn_packed__get_uint(table_sizes); 692289177Speter if (sub_table->short_string_count) 693289177Speter { 694289177Speter sub_table->short_strings 695289177Speter = apr_pcalloc(result_pool, sub_table->short_string_count 696289177Speter * sizeof(*sub_table->short_strings)); 697289177Speter 698289177Speter /* read short string headers */ 699289177Speter 700289177Speter for (k = 0; k < sub_table->short_string_count; ++k) 701289177Speter { 702289177Speter string_header_t *string = &sub_table->short_strings[k]; 703289177Speter 704289177Speter string->head_string = (apr_uint16_t)svn_packed__get_uint(headers); 705289177Speter string->head_length = (apr_uint16_t)svn_packed__get_uint(headers); 706289177Speter string->tail_start = (apr_uint16_t)svn_packed__get_uint(headers); 707289177Speter string->tail_length = (apr_uint16_t)svn_packed__get_uint(headers); 708289177Speter } 709289177Speter } 710289177Speter 711289177Speter sub_table->data = svn_packed__get_bytes(small_strings_data, 712289177Speter &sub_table->data_size); 713289177Speter } 714289177Speter 715289177Speter /* read long strings */ 716289177Speter 717289177Speter for (i = 0; i < table->size; ++i) 718289177Speter { 719289177Speter /* initialize long string table */ 720289177Speter string_sub_table_t *sub_table = &table->sub_tables[i]; 721289177Speter 722289177Speter sub_table->long_string_count = svn_packed__get_uint(table_sizes); 723289177Speter if (sub_table->long_string_count) 724289177Speter { 725289177Speter sub_table->long_strings 726289177Speter = apr_pcalloc(result_pool, sub_table->long_string_count 727289177Speter * sizeof(*sub_table->long_strings)); 728289177Speter 729289177Speter /* read long strings */ 730289177Speter 731289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 732289177Speter { 733289177Speter svn_string_t *string = &sub_table->long_strings[k]; 734289177Speter string->data = svn_packed__get_bytes(large_strings, 735289177Speter &string->len); 736289177Speter string->len--; 737289177Speter } 738289177Speter } 739289177Speter } 740289177Speter 741289177Speter /* done */ 742289177Speter 743289177Speter *table_p = table; 744289177Speter 745289177Speter return SVN_NO_ERROR; 746289177Speter} 747289177Speter 748289177Spetervoid 749289177Spetersvn_fs_x__serialize_string_table(svn_temp_serializer__context_t *context, 750289177Speter string_table_t **st) 751289177Speter{ 752289177Speter apr_size_t i, k; 753289177Speter string_table_t *string_table = *st; 754289177Speter if (string_table == NULL) 755289177Speter return; 756289177Speter 757289177Speter /* string table struct */ 758289177Speter svn_temp_serializer__push(context, 759289177Speter (const void * const *)st, 760289177Speter sizeof(*string_table)); 761289177Speter 762289177Speter /* sub-table array (all structs in a single memory block) */ 763289177Speter svn_temp_serializer__push(context, 764289177Speter (const void * const *)&string_table->sub_tables, 765289177Speter sizeof(*string_table->sub_tables) * 766289177Speter string_table->size); 767289177Speter 768289177Speter /* sub-elements of all sub-tables */ 769289177Speter for (i = 0; i < string_table->size; ++i) 770289177Speter { 771289177Speter string_sub_table_t *sub_table = &string_table->sub_tables[i]; 772289177Speter svn_temp_serializer__add_leaf(context, 773289177Speter (const void * const *)&sub_table->data, 774289177Speter sub_table->data_size); 775289177Speter svn_temp_serializer__add_leaf(context, 776289177Speter (const void * const *)&sub_table->short_strings, 777289177Speter sub_table->short_string_count * sizeof(string_header_t)); 778289177Speter 779289177Speter /* all "long string" instances form a single memory block */ 780289177Speter svn_temp_serializer__push(context, 781289177Speter (const void * const *)&sub_table->long_strings, 782289177Speter sub_table->long_string_count * sizeof(svn_string_t)); 783289177Speter 784289177Speter /* serialize actual long string contents */ 785289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 786289177Speter { 787289177Speter svn_string_t *string = &sub_table->long_strings[k]; 788289177Speter svn_temp_serializer__add_leaf(context, 789289177Speter (const void * const *)&string->data, 790289177Speter string->len + 1); 791289177Speter } 792289177Speter 793289177Speter svn_temp_serializer__pop(context); 794289177Speter } 795289177Speter 796289177Speter /* back to the caller's nesting level */ 797289177Speter svn_temp_serializer__pop(context); 798289177Speter svn_temp_serializer__pop(context); 799289177Speter} 800289177Speter 801289177Spetervoid 802289177Spetersvn_fs_x__deserialize_string_table(void *buffer, 803289177Speter string_table_t **table) 804289177Speter{ 805289177Speter apr_size_t i, k; 806289177Speter string_sub_table_t *sub_tables; 807289177Speter 808289177Speter svn_temp_deserializer__resolve(buffer, (void **)table); 809289177Speter if (*table == NULL) 810289177Speter return; 811289177Speter 812289177Speter svn_temp_deserializer__resolve(*table, (void **)&(*table)->sub_tables); 813289177Speter sub_tables = (*table)->sub_tables; 814289177Speter for (i = 0; i < (*table)->size; ++i) 815289177Speter { 816289177Speter string_sub_table_t *sub_table = sub_tables + i; 817289177Speter 818289177Speter svn_temp_deserializer__resolve(sub_tables, 819289177Speter (void **)&sub_table->data); 820289177Speter svn_temp_deserializer__resolve(sub_tables, 821289177Speter (void **)&sub_table->short_strings); 822289177Speter svn_temp_deserializer__resolve(sub_tables, 823289177Speter (void **)&sub_table->long_strings); 824289177Speter 825289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 826289177Speter svn_temp_deserializer__resolve(sub_table->long_strings, 827289177Speter (void **)&sub_table->long_strings[k].data); 828289177Speter } 829289177Speter} 830289177Speter 831289177Speterconst char* 832289177Spetersvn_fs_x__string_table_get_func(const string_table_t *table, 833289177Speter apr_size_t idx, 834289177Speter apr_size_t *length, 835362181Sdim apr_pool_t *result_pool) 836289177Speter{ 837289177Speter apr_size_t table_number = idx >> TABLE_SHIFT; 838289177Speter apr_size_t sub_index = idx & STRING_INDEX_MASK; 839289177Speter 840289177Speter if (table_number < table->size) 841289177Speter { 842289177Speter /* resolve TABLE->SUB_TABLES pointer and select sub-table */ 843289177Speter string_sub_table_t *sub_tables 844289177Speter = (string_sub_table_t *)svn_temp_deserializer__ptr(table, 845289177Speter (const void *const *)&table->sub_tables); 846289177Speter string_sub_table_t *sub_table = sub_tables + table_number; 847289177Speter 848289177Speter /* pick the right kind of string */ 849289177Speter if (idx & LONG_STRING_MASK) 850289177Speter { 851289177Speter if (sub_index < sub_table->long_string_count) 852289177Speter { 853289177Speter /* resolve SUB_TABLE->LONG_STRINGS, select the string we want 854289177Speter and resolve the pointer to its char data */ 855289177Speter svn_string_t *long_strings 856289177Speter = (svn_string_t *)svn_temp_deserializer__ptr(sub_table, 857289177Speter (const void *const *)&sub_table->long_strings); 858289177Speter const char *str_data 859289177Speter = (const char*)svn_temp_deserializer__ptr(long_strings, 860289177Speter (const void *const *)&long_strings[sub_index].data); 861289177Speter 862289177Speter /* return a copy of the char data */ 863289177Speter if (length) 864289177Speter *length = long_strings[sub_index].len; 865289177Speter 866362181Sdim return apr_pstrmemdup(result_pool, 867289177Speter str_data, 868289177Speter long_strings[sub_index].len); 869289177Speter } 870289177Speter } 871289177Speter else 872289177Speter { 873289177Speter if (sub_index < sub_table->short_string_count) 874289177Speter { 875289177Speter string_header_t *header; 876289177Speter apr_size_t len; 877289177Speter char *result; 878289177Speter 879289177Speter /* construct a copy of our sub-table struct with SHORT_STRINGS 880289177Speter and DATA pointers resolved. Leave all other pointers as 881289177Speter they are. This allows us to use the same code for string 882289177Speter reconstruction here as in the non-serialized case. */ 883289177Speter string_sub_table_t table_copy = *sub_table; 884289177Speter table_copy.data 885289177Speter = (const char *)svn_temp_deserializer__ptr(sub_tables, 886289177Speter (const void *const *)&sub_table->data); 887289177Speter table_copy.short_strings 888289177Speter = (string_header_t *)svn_temp_deserializer__ptr(sub_tables, 889289177Speter (const void *const *)&sub_table->short_strings); 890289177Speter 891289177Speter /* reconstruct the char data and return it */ 892289177Speter header = table_copy.short_strings + sub_index; 893289177Speter len = header->head_length + header->tail_length; 894362181Sdim result = apr_palloc(result_pool, len + PADDING); 895289177Speter if (length) 896289177Speter *length = len; 897289177Speter 898289177Speter table_copy_string(result, len, &table_copy, header); 899289177Speter 900289177Speter return result; 901289177Speter } 902289177Speter } 903289177Speter } 904289177Speter 905289177Speter return ""; 906289177Speter} 907