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, 379289177Speter apr_pool_t *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; 390289177Speter target->short_strings = apr_palloc(pool, sizeof(*target->short_strings) * 391289177Speter target->short_string_count); 392289177Speter for (i = 0; i < source->short_strings->nelts; ++i) 393289177Speter { 394289177Speter const builder_string_t *string 395289177Speter = APR_ARRAY_IDX(source->short_strings, i, const builder_string_t *); 396289177Speter 397289177Speter string_header_t *entry = &target->short_strings[i]; 398289177Speter const char *tail = string->string.data + string->previous_match_len; 399289177Speter string_header_t *tail_match; 400289177Speter apr_size_t head_length = string->previous_match_len; 401289177Speter 402289177Speter /* Minimize the number of strings to visit when reconstructing the 403289177Speter string head. So, skip all predecessors that don't contribute to 404289177Speter first HEAD_LENGTH chars of our string. */ 405289177Speter if (head_length) 406289177Speter { 407289177Speter const builder_string_t *furthest_prev = string->previous; 408289177Speter while (furthest_prev->previous_match_len >= head_length) 409289177Speter furthest_prev = furthest_prev->previous; 410289177Speter entry->head_string = furthest_prev->position; 411289177Speter } 412289177Speter else 413289177Speter entry->head_string = 0; 414289177Speter 415289177Speter /* head & tail length are known */ 416289177Speter entry->head_length = (apr_uint16_t)head_length; 417289177Speter entry->tail_length 418289177Speter = (apr_uint16_t)(string->string.len - entry->head_length); 419289177Speter 420289177Speter /* try to reuse an existing tail segment */ 421289177Speter tail_match = apr_hash_get(tails, tail, entry->tail_length); 422289177Speter if (tail_match) 423289177Speter { 424289177Speter entry->tail_start = tail_match->tail_start; 425289177Speter } 426289177Speter else 427289177Speter { 428289177Speter entry->tail_start = (apr_uint16_t)data->len; 429289177Speter svn_stringbuf_appendbytes(data, tail, entry->tail_length); 430289177Speter apr_hash_set(tails, tail, entry->tail_length, entry); 431289177Speter } 432289177Speter } 433289177Speter 434289177Speter /* pack long strings */ 435289177Speter target->long_string_count = (apr_size_t)source->long_strings->nelts; 436289177Speter target->long_strings = apr_palloc(pool, sizeof(*target->long_strings) * 437289177Speter target->long_string_count); 438289177Speter for (i = 0; i < source->long_strings->nelts; ++i) 439289177Speter { 440289177Speter svn_string_t *string = &target->long_strings[i]; 441289177Speter *string = APR_ARRAY_IDX(source->long_strings, i, svn_string_t); 442289177Speter string->data = apr_pstrmemdup(pool, string->data, string->len); 443289177Speter } 444289177Speter 445289177Speter data->len += PADDING; /* add a few extra bytes at the end of the buffer 446289177Speter that we want to keep valid for chunky access */ 447289177Speter assert(data->len < data->blocksize); 448289177Speter memset(data->data + data->len - PADDING, 0, PADDING); 449289177Speter 450289177Speter target->data = apr_pmemdup(pool, data->data, data->len); 451289177Speter target->data_size = data->len; 452289177Speter} 453289177Speter 454289177Speterstring_table_t * 455289177Spetersvn_fs_x__string_table_create(const string_table_builder_t *builder, 456289177Speter apr_pool_t *pool) 457289177Speter{ 458289177Speter apr_size_t i; 459289177Speter 460289177Speter string_table_t *result = apr_pcalloc(pool, sizeof(*result)); 461289177Speter result->size = (apr_size_t)builder->tables->nelts; 462289177Speter result->sub_tables 463289177Speter = apr_pcalloc(pool, result->size * sizeof(*result->sub_tables)); 464289177Speter 465289177Speter for (i = 0; i < result->size; ++i) 466289177Speter create_table(&result->sub_tables[i], 467289177Speter APR_ARRAY_IDX(builder->tables, i, builder_table_t*), 468289177Speter pool, 469289177Speter builder->pool); 470289177Speter 471289177Speter return result; 472289177Speter} 473289177Speter 474289177Speter/* Masks used by table_copy_string. copy_mask[I] is used if the target 475289177Speter content to be preserved starts at byte I within the current chunk. 476289177Speter This is used to work around alignment issues. 477289177Speter */ 478289177Speter#if SVN_UNALIGNED_ACCESS_IS_OK 479289177Speterstatic const char *copy_masks[8] = { "\xff\xff\xff\xff\xff\xff\xff\xff", 480289177Speter "\x00\xff\xff\xff\xff\xff\xff\xff", 481289177Speter "\x00\x00\xff\xff\xff\xff\xff\xff", 482289177Speter "\x00\x00\x00\xff\xff\xff\xff\xff", 483289177Speter "\x00\x00\x00\x00\xff\xff\xff\xff", 484289177Speter "\x00\x00\x00\x00\x00\xff\xff\xff", 485289177Speter "\x00\x00\x00\x00\x00\x00\xff\xff", 486289177Speter "\x00\x00\x00\x00\x00\x00\x00\xff" }; 487289177Speter#endif 488289177Speter 489289177Speterstatic void 490289177Spetertable_copy_string(char *buffer, 491289177Speter apr_size_t len, 492289177Speter const string_sub_table_t *table, 493289177Speter string_header_t *header) 494289177Speter{ 495289177Speter buffer[len] = '\0'; 496289177Speter do 497289177Speter { 498289177Speter assert(header->head_length <= len); 499289177Speter { 500289177Speter#if SVN_UNALIGNED_ACCESS_IS_OK 501289177Speter /* the sections that we copy tend to be short but we can copy 502289177Speter *all* of it chunky because we made sure that source and target 503289177Speter buffer have some extra padding to prevent segfaults. */ 504289177Speter apr_uint64_t mask; 505289177Speter apr_size_t to_copy = len - header->head_length; 506289177Speter apr_size_t copied = 0; 507289177Speter 508289177Speter const char *source = table->data + header->tail_start; 509289177Speter char *target = buffer + header->head_length; 510289177Speter len = header->head_length; 511289177Speter 512289177Speter /* copy whole chunks */ 513289177Speter while (to_copy >= copied + sizeof(apr_uint64_t)) 514289177Speter { 515289177Speter *(apr_uint64_t *)(target + copied) 516289177Speter = *(const apr_uint64_t *)(source + copied); 517289177Speter copied += sizeof(apr_uint64_t); 518289177Speter } 519289177Speter 520289177Speter /* copy the remainder assuming that we have up to 8 extra bytes 521289177Speter of addressable buffer on the source and target sides. 522289177Speter Now, we simply copy 8 bytes and use a mask to filter & merge 523289177Speter old with new data. */ 524289177Speter mask = *(const apr_uint64_t *)copy_masks[to_copy - copied]; 525289177Speter *(apr_uint64_t *)(target + copied) 526289177Speter = (*(apr_uint64_t *)(target + copied) & mask) 527289177Speter | (*(const apr_uint64_t *)(source + copied) & ~mask); 528289177Speter#else 529289177Speter memcpy(buffer + header->head_length, 530289177Speter table->data + header->tail_start, 531289177Speter len - header->head_length); 532289177Speter len = header->head_length; 533289177Speter#endif 534289177Speter } 535289177Speter 536289177Speter header = &table->short_strings[header->head_string]; 537289177Speter } 538289177Speter while (len); 539289177Speter} 540289177Speter 541289177Speterconst char* 542289177Spetersvn_fs_x__string_table_get(const string_table_t *table, 543289177Speter apr_size_t idx, 544289177Speter apr_size_t *length, 545289177Speter apr_pool_t *pool) 546289177Speter{ 547289177Speter apr_size_t table_number = idx >> TABLE_SHIFT; 548289177Speter apr_size_t sub_index = idx & STRING_INDEX_MASK; 549289177Speter 550289177Speter if (table_number < table->size) 551289177Speter { 552289177Speter string_sub_table_t *sub_table = &table->sub_tables[table_number]; 553289177Speter if (idx & LONG_STRING_MASK) 554289177Speter { 555289177Speter if (sub_index < sub_table->long_string_count) 556289177Speter { 557289177Speter if (length) 558289177Speter *length = sub_table->long_strings[sub_index].len; 559289177Speter 560289177Speter return apr_pstrmemdup(pool, 561289177Speter sub_table->long_strings[sub_index].data, 562289177Speter sub_table->long_strings[sub_index].len); 563289177Speter } 564289177Speter } 565289177Speter else 566289177Speter { 567289177Speter if (sub_index < sub_table->short_string_count) 568289177Speter { 569289177Speter string_header_t *header = sub_table->short_strings + sub_index; 570289177Speter apr_size_t len = header->head_length + header->tail_length; 571289177Speter char *result = apr_palloc(pool, len + PADDING); 572289177Speter 573289177Speter if (length) 574289177Speter *length = len; 575289177Speter table_copy_string(result, len, sub_table, header); 576289177Speter 577289177Speter return result; 578289177Speter } 579289177Speter } 580289177Speter } 581289177Speter 582289177Speter return apr_pstrmemdup(pool, "", 0); 583289177Speter} 584289177Speter 585289177Spetersvn_error_t * 586289177Spetersvn_fs_x__write_string_table(svn_stream_t *stream, 587289177Speter const string_table_t *table, 588289177Speter apr_pool_t *scratch_pool) 589289177Speter{ 590289177Speter apr_size_t i, k; 591289177Speter 592289177Speter svn_packed__data_root_t *root = svn_packed__data_create_root(scratch_pool); 593289177Speter 594289177Speter svn_packed__int_stream_t *table_sizes 595289177Speter = svn_packed__create_int_stream(root, FALSE, FALSE); 596289177Speter svn_packed__int_stream_t *small_strings_headers 597289177Speter = svn_packed__create_int_stream(root, FALSE, FALSE); 598289177Speter svn_packed__byte_stream_t *large_strings 599289177Speter = svn_packed__create_bytes_stream(root); 600289177Speter svn_packed__byte_stream_t *small_strings_data 601289177Speter = svn_packed__create_bytes_stream(root); 602289177Speter 603289177Speter svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE); 604289177Speter svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE); 605289177Speter svn_packed__create_int_substream(small_strings_headers, TRUE, FALSE); 606289177Speter svn_packed__create_int_substream(small_strings_headers, FALSE, FALSE); 607289177Speter 608289177Speter /* number of sub-tables */ 609289177Speter 610289177Speter svn_packed__add_uint(table_sizes, table->size); 611289177Speter 612289177Speter /* all short-string char data sizes */ 613289177Speter 614289177Speter for (i = 0; i < table->size; ++i) 615289177Speter svn_packed__add_uint(table_sizes, 616289177Speter table->sub_tables[i].short_string_count); 617289177Speter 618289177Speter for (i = 0; i < table->size; ++i) 619289177Speter svn_packed__add_uint(table_sizes, 620289177Speter table->sub_tables[i].long_string_count); 621289177Speter 622289177Speter /* all strings */ 623289177Speter 624289177Speter for (i = 0; i < table->size; ++i) 625289177Speter { 626289177Speter string_sub_table_t *sub_table = &table->sub_tables[i]; 627289177Speter svn_packed__add_bytes(small_strings_data, 628289177Speter sub_table->data, 629289177Speter sub_table->data_size); 630289177Speter 631289177Speter for (k = 0; k < sub_table->short_string_count; ++k) 632289177Speter { 633289177Speter string_header_t *string = &sub_table->short_strings[k]; 634289177Speter 635289177Speter svn_packed__add_uint(small_strings_headers, string->head_string); 636289177Speter svn_packed__add_uint(small_strings_headers, string->head_length); 637289177Speter svn_packed__add_uint(small_strings_headers, string->tail_start); 638289177Speter svn_packed__add_uint(small_strings_headers, string->tail_length); 639289177Speter } 640289177Speter 641289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 642289177Speter svn_packed__add_bytes(large_strings, 643289177Speter sub_table->long_strings[k].data, 644289177Speter sub_table->long_strings[k].len + 1); 645289177Speter } 646289177Speter 647289177Speter /* write to target stream */ 648289177Speter 649289177Speter SVN_ERR(svn_packed__data_write(stream, root, scratch_pool)); 650289177Speter 651289177Speter return SVN_NO_ERROR; 652289177Speter} 653289177Speter 654289177Spetersvn_error_t * 655289177Spetersvn_fs_x__read_string_table(string_table_t **table_p, 656289177Speter svn_stream_t *stream, 657289177Speter apr_pool_t *result_pool, 658289177Speter apr_pool_t *scratch_pool) 659289177Speter{ 660289177Speter apr_size_t i, k; 661289177Speter 662289177Speter string_table_t *table = apr_palloc(result_pool, sizeof(*table)); 663289177Speter 664289177Speter svn_packed__data_root_t *root; 665289177Speter svn_packed__int_stream_t *table_sizes; 666289177Speter svn_packed__byte_stream_t *large_strings; 667289177Speter svn_packed__byte_stream_t *small_strings_data; 668289177Speter svn_packed__int_stream_t *headers; 669289177Speter 670289177Speter SVN_ERR(svn_packed__data_read(&root, stream, result_pool, scratch_pool)); 671289177Speter table_sizes = svn_packed__first_int_stream(root); 672289177Speter headers = svn_packed__next_int_stream(table_sizes); 673289177Speter large_strings = svn_packed__first_byte_stream(root); 674289177Speter small_strings_data = svn_packed__next_byte_stream(large_strings); 675289177Speter 676289177Speter /* create sub-tables */ 677289177Speter 678289177Speter table->size = (apr_size_t)svn_packed__get_uint(table_sizes); 679289177Speter table->sub_tables = apr_pcalloc(result_pool, 680289177Speter table->size * sizeof(*table->sub_tables)); 681289177Speter 682289177Speter /* read short strings */ 683289177Speter 684289177Speter for (i = 0; i < table->size; ++i) 685289177Speter { 686289177Speter string_sub_table_t *sub_table = &table->sub_tables[i]; 687289177Speter 688289177Speter sub_table->short_string_count 689289177Speter = (apr_size_t)svn_packed__get_uint(table_sizes); 690289177Speter if (sub_table->short_string_count) 691289177Speter { 692289177Speter sub_table->short_strings 693289177Speter = apr_pcalloc(result_pool, sub_table->short_string_count 694289177Speter * sizeof(*sub_table->short_strings)); 695289177Speter 696289177Speter /* read short string headers */ 697289177Speter 698289177Speter for (k = 0; k < sub_table->short_string_count; ++k) 699289177Speter { 700289177Speter string_header_t *string = &sub_table->short_strings[k]; 701289177Speter 702289177Speter string->head_string = (apr_uint16_t)svn_packed__get_uint(headers); 703289177Speter string->head_length = (apr_uint16_t)svn_packed__get_uint(headers); 704289177Speter string->tail_start = (apr_uint16_t)svn_packed__get_uint(headers); 705289177Speter string->tail_length = (apr_uint16_t)svn_packed__get_uint(headers); 706289177Speter } 707289177Speter } 708289177Speter 709289177Speter sub_table->data = svn_packed__get_bytes(small_strings_data, 710289177Speter &sub_table->data_size); 711289177Speter } 712289177Speter 713289177Speter /* read long strings */ 714289177Speter 715289177Speter for (i = 0; i < table->size; ++i) 716289177Speter { 717289177Speter /* initialize long string table */ 718289177Speter string_sub_table_t *sub_table = &table->sub_tables[i]; 719289177Speter 720289177Speter sub_table->long_string_count = svn_packed__get_uint(table_sizes); 721289177Speter if (sub_table->long_string_count) 722289177Speter { 723289177Speter sub_table->long_strings 724289177Speter = apr_pcalloc(result_pool, sub_table->long_string_count 725289177Speter * sizeof(*sub_table->long_strings)); 726289177Speter 727289177Speter /* read long strings */ 728289177Speter 729289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 730289177Speter { 731289177Speter svn_string_t *string = &sub_table->long_strings[k]; 732289177Speter string->data = svn_packed__get_bytes(large_strings, 733289177Speter &string->len); 734289177Speter string->len--; 735289177Speter } 736289177Speter } 737289177Speter } 738289177Speter 739289177Speter /* done */ 740289177Speter 741289177Speter *table_p = table; 742289177Speter 743289177Speter return SVN_NO_ERROR; 744289177Speter} 745289177Speter 746289177Spetervoid 747289177Spetersvn_fs_x__serialize_string_table(svn_temp_serializer__context_t *context, 748289177Speter string_table_t **st) 749289177Speter{ 750289177Speter apr_size_t i, k; 751289177Speter string_table_t *string_table = *st; 752289177Speter if (string_table == NULL) 753289177Speter return; 754289177Speter 755289177Speter /* string table struct */ 756289177Speter svn_temp_serializer__push(context, 757289177Speter (const void * const *)st, 758289177Speter sizeof(*string_table)); 759289177Speter 760289177Speter /* sub-table array (all structs in a single memory block) */ 761289177Speter svn_temp_serializer__push(context, 762289177Speter (const void * const *)&string_table->sub_tables, 763289177Speter sizeof(*string_table->sub_tables) * 764289177Speter string_table->size); 765289177Speter 766289177Speter /* sub-elements of all sub-tables */ 767289177Speter for (i = 0; i < string_table->size; ++i) 768289177Speter { 769289177Speter string_sub_table_t *sub_table = &string_table->sub_tables[i]; 770289177Speter svn_temp_serializer__add_leaf(context, 771289177Speter (const void * const *)&sub_table->data, 772289177Speter sub_table->data_size); 773289177Speter svn_temp_serializer__add_leaf(context, 774289177Speter (const void * const *)&sub_table->short_strings, 775289177Speter sub_table->short_string_count * sizeof(string_header_t)); 776289177Speter 777289177Speter /* all "long string" instances form a single memory block */ 778289177Speter svn_temp_serializer__push(context, 779289177Speter (const void * const *)&sub_table->long_strings, 780289177Speter sub_table->long_string_count * sizeof(svn_string_t)); 781289177Speter 782289177Speter /* serialize actual long string contents */ 783289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 784289177Speter { 785289177Speter svn_string_t *string = &sub_table->long_strings[k]; 786289177Speter svn_temp_serializer__add_leaf(context, 787289177Speter (const void * const *)&string->data, 788289177Speter string->len + 1); 789289177Speter } 790289177Speter 791289177Speter svn_temp_serializer__pop(context); 792289177Speter } 793289177Speter 794289177Speter /* back to the caller's nesting level */ 795289177Speter svn_temp_serializer__pop(context); 796289177Speter svn_temp_serializer__pop(context); 797289177Speter} 798289177Speter 799289177Spetervoid 800289177Spetersvn_fs_x__deserialize_string_table(void *buffer, 801289177Speter string_table_t **table) 802289177Speter{ 803289177Speter apr_size_t i, k; 804289177Speter string_sub_table_t *sub_tables; 805289177Speter 806289177Speter svn_temp_deserializer__resolve(buffer, (void **)table); 807289177Speter if (*table == NULL) 808289177Speter return; 809289177Speter 810289177Speter svn_temp_deserializer__resolve(*table, (void **)&(*table)->sub_tables); 811289177Speter sub_tables = (*table)->sub_tables; 812289177Speter for (i = 0; i < (*table)->size; ++i) 813289177Speter { 814289177Speter string_sub_table_t *sub_table = sub_tables + i; 815289177Speter 816289177Speter svn_temp_deserializer__resolve(sub_tables, 817289177Speter (void **)&sub_table->data); 818289177Speter svn_temp_deserializer__resolve(sub_tables, 819289177Speter (void **)&sub_table->short_strings); 820289177Speter svn_temp_deserializer__resolve(sub_tables, 821289177Speter (void **)&sub_table->long_strings); 822289177Speter 823289177Speter for (k = 0; k < sub_table->long_string_count; ++k) 824289177Speter svn_temp_deserializer__resolve(sub_table->long_strings, 825289177Speter (void **)&sub_table->long_strings[k].data); 826289177Speter } 827289177Speter} 828289177Speter 829289177Speterconst char* 830289177Spetersvn_fs_x__string_table_get_func(const string_table_t *table, 831289177Speter apr_size_t idx, 832289177Speter apr_size_t *length, 833289177Speter apr_pool_t *pool) 834289177Speter{ 835289177Speter apr_size_t table_number = idx >> TABLE_SHIFT; 836289177Speter apr_size_t sub_index = idx & STRING_INDEX_MASK; 837289177Speter 838289177Speter if (table_number < table->size) 839289177Speter { 840289177Speter /* resolve TABLE->SUB_TABLES pointer and select sub-table */ 841289177Speter string_sub_table_t *sub_tables 842289177Speter = (string_sub_table_t *)svn_temp_deserializer__ptr(table, 843289177Speter (const void *const *)&table->sub_tables); 844289177Speter string_sub_table_t *sub_table = sub_tables + table_number; 845289177Speter 846289177Speter /* pick the right kind of string */ 847289177Speter if (idx & LONG_STRING_MASK) 848289177Speter { 849289177Speter if (sub_index < sub_table->long_string_count) 850289177Speter { 851289177Speter /* resolve SUB_TABLE->LONG_STRINGS, select the string we want 852289177Speter and resolve the pointer to its char data */ 853289177Speter svn_string_t *long_strings 854289177Speter = (svn_string_t *)svn_temp_deserializer__ptr(sub_table, 855289177Speter (const void *const *)&sub_table->long_strings); 856289177Speter const char *str_data 857289177Speter = (const char*)svn_temp_deserializer__ptr(long_strings, 858289177Speter (const void *const *)&long_strings[sub_index].data); 859289177Speter 860289177Speter /* return a copy of the char data */ 861289177Speter if (length) 862289177Speter *length = long_strings[sub_index].len; 863289177Speter 864289177Speter return apr_pstrmemdup(pool, 865289177Speter str_data, 866289177Speter long_strings[sub_index].len); 867289177Speter } 868289177Speter } 869289177Speter else 870289177Speter { 871289177Speter if (sub_index < sub_table->short_string_count) 872289177Speter { 873289177Speter string_header_t *header; 874289177Speter apr_size_t len; 875289177Speter char *result; 876289177Speter 877289177Speter /* construct a copy of our sub-table struct with SHORT_STRINGS 878289177Speter and DATA pointers resolved. Leave all other pointers as 879289177Speter they are. This allows us to use the same code for string 880289177Speter reconstruction here as in the non-serialized case. */ 881289177Speter string_sub_table_t table_copy = *sub_table; 882289177Speter table_copy.data 883289177Speter = (const char *)svn_temp_deserializer__ptr(sub_tables, 884289177Speter (const void *const *)&sub_table->data); 885289177Speter table_copy.short_strings 886289177Speter = (string_header_t *)svn_temp_deserializer__ptr(sub_tables, 887289177Speter (const void *const *)&sub_table->short_strings); 888289177Speter 889289177Speter /* reconstruct the char data and return it */ 890289177Speter header = table_copy.short_strings + sub_index; 891289177Speter len = header->head_length + header->tail_length; 892289177Speter result = apr_palloc(pool, len + PADDING); 893289177Speter if (length) 894289177Speter *length = len; 895289177Speter 896289177Speter table_copy_string(result, len, &table_copy, header); 897289177Speter 898289177Speter return result; 899289177Speter } 900289177Speter } 901289177Speter } 902289177Speter 903289177Speter return ""; 904289177Speter} 905