1251881Speter/* 2251881Speter * hash.c : dumping and reading hash tables to/from files. 3251881Speter * 4251881Speter * ==================================================================== 5251881Speter * Licensed to the Apache Software Foundation (ASF) under one 6251881Speter * or more contributor license agreements. See the NOTICE file 7251881Speter * distributed with this work for additional information 8251881Speter * regarding copyright ownership. The ASF licenses this file 9251881Speter * to you under the Apache License, Version 2.0 (the 10251881Speter * "License"); you may not use this file except in compliance 11251881Speter * with the License. You may obtain a copy of the License at 12251881Speter * 13251881Speter * http://www.apache.org/licenses/LICENSE-2.0 14251881Speter * 15251881Speter * Unless required by applicable law or agreed to in writing, 16251881Speter * software distributed under the License is distributed on an 17251881Speter * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 18251881Speter * KIND, either express or implied. See the License for the 19251881Speter * specific language governing permissions and limitations 20251881Speter * under the License. 21251881Speter * ==================================================================== 22251881Speter */ 23251881Speter 24251881Speter 25251881Speter 26251881Speter#include <stdlib.h> 27251881Speter#include <limits.h> 28251881Speter 29251881Speter#include <apr_version.h> 30251881Speter#include <apr_pools.h> 31251881Speter#include <apr_hash.h> 32251881Speter#include <apr_file_io.h> 33251881Speter 34362181Sdim#ifndef SVN_HASH__GETS_SETS 35362181Sdim#define SVN_HASH__GETS_SETS 36362181Sdim#endif 37362181Sdim#include "svn_hash.h" 38362181Sdim 39251881Speter#include "svn_types.h" 40251881Speter#include "svn_string.h" 41251881Speter#include "svn_error.h" 42251881Speter#include "svn_sorts.h" 43251881Speter#include "svn_io.h" 44251881Speter#include "svn_pools.h" 45251881Speter 46251881Speter#include "private/svn_dep_compat.h" 47289180Speter#include "private/svn_sorts_private.h" 48251881Speter#include "private/svn_subr_private.h" 49251881Speter 50251881Speter#include "svn_private_config.h" 51251881Speter 52251881Speter 53251881Speter 54251881Speter/* 55251881Speter * The format of a dumped hash table is: 56251881Speter * 57251881Speter * K <nlength> 58251881Speter * name (a string of <nlength> bytes, followed by a newline) 59251881Speter * V <vlength> 60251881Speter * val (a string of <vlength> bytes, followed by a newline) 61251881Speter * [... etc, etc ...] 62251881Speter * END 63251881Speter * 64251881Speter * 65251881Speter * (Yes, there is a newline after END.) 66251881Speter * 67251881Speter * For example: 68251881Speter * 69251881Speter * K 5 70251881Speter * color 71251881Speter * V 3 72251881Speter * red 73251881Speter * K 11 74251881Speter * wine review 75251881Speter * V 376 76251881Speter * A forthright entrance, yet coquettish on the tongue, its deceptively 77251881Speter * fruity exterior hides the warm mahagony undercurrent that is the 78251881Speter * hallmark of Chateau Fraisant-Pitre. Connoisseurs of the region will 79251881Speter * be pleased to note the familiar, subtle hints of mulberries and 80251881Speter * carburator fluid. Its confident finish is marred only by a barely 81251881Speter * detectable suggestion of rancid squid ink. 82251881Speter * K 5 83251881Speter * price 84251881Speter * V 8 85251881Speter * US $6.50 86251881Speter * END 87251881Speter * 88251881Speter */ 89251881Speter 90251881Speter 91251881Speter 92251881Speter 93251881Speter/*** Dumping and loading hash files. */ 94251881Speter 95251881Speter/* Implements svn_hash_read2 and svn_hash_read_incremental. */ 96289180Spetersvn_error_t * 97289180Spetersvn_hash__read_entry(svn_hash__entry_t *entry, 98289180Speter svn_stream_t *stream, 99289180Speter const char *terminator, 100289180Speter svn_boolean_t incremental, 101289180Speter apr_pool_t *pool) 102251881Speter{ 103251881Speter svn_stringbuf_t *buf; 104251881Speter svn_boolean_t eof; 105289180Speter apr_size_t len; 106289180Speter char c; 107251881Speter 108289180Speter svn_error_t *err; 109289180Speter apr_uint64_t ui64; 110251881Speter 111289180Speter /* Read a key length line. Might be END, though. */ 112289180Speter SVN_ERR(svn_stream_readline(stream, &buf, "\n", &eof, pool)); 113251881Speter 114289180Speter /* Check for the end of the hash. */ 115289180Speter if ((!terminator && eof && buf->len == 0) 116289180Speter || (terminator && (strcmp(buf->data, terminator) == 0))) 117289180Speter { 118289180Speter entry->key = NULL; 119289180Speter entry->keylen = 0; 120289180Speter entry->val = NULL; 121289180Speter entry->vallen = 0; 122251881Speter 123289180Speter return SVN_NO_ERROR; 124289180Speter } 125251881Speter 126289180Speter /* Check for unexpected end of stream */ 127289180Speter if (eof) 128289180Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, 129289180Speter _("Serialized hash missing terminator")); 130289180Speter 131289180Speter if ((buf->len >= 3) && (buf->data[0] == 'K') && (buf->data[1] == ' ')) 132289180Speter { 133289180Speter /* Get the length of the key */ 134289180Speter err = svn_cstring_strtoui64(&ui64, buf->data + 2, 135289180Speter 0, APR_SIZE_MAX, 10); 136289180Speter if (err) 137289180Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, err, 138289180Speter _("Serialized hash malformed key length")); 139289180Speter entry->keylen = (apr_size_t)ui64; 140289180Speter 141289180Speter /* Now read that much into a buffer. */ 142289180Speter entry->key = apr_palloc(pool, entry->keylen + 1); 143289180Speter SVN_ERR(svn_stream_read_full(stream, entry->key, &entry->keylen)); 144289180Speter entry->key[entry->keylen] = '\0'; 145289180Speter 146289180Speter /* Suck up extra newline after key data */ 147289180Speter len = 1; 148289180Speter SVN_ERR(svn_stream_read_full(stream, &c, &len)); 149289180Speter if (c != '\n') 150251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, 151289180Speter _("Serialized hash malformed key data")); 152251881Speter 153289180Speter /* Read a val length line */ 154289180Speter SVN_ERR(svn_stream_readline(stream, &buf, "\n", &eof, pool)); 155289180Speter 156289180Speter if ((buf->data[0] == 'V') && (buf->data[1] == ' ')) 157251881Speter { 158289180Speter /* Get the length of the val */ 159251881Speter err = svn_cstring_strtoui64(&ui64, buf->data + 2, 160251881Speter 0, APR_SIZE_MAX, 10); 161251881Speter if (err) 162251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, err, 163289180Speter _("Serialized hash malformed value length")); 164289180Speter entry->vallen = (apr_size_t)ui64; 165251881Speter 166289180Speter entry->val = apr_palloc(pool, entry->vallen + 1); 167289180Speter SVN_ERR(svn_stream_read_full(stream, entry->val, &entry->vallen)); 168289180Speter entry->val[entry->vallen] = '\0'; 169251881Speter 170289180Speter /* Suck up extra newline after val data */ 171251881Speter len = 1; 172289180Speter SVN_ERR(svn_stream_read_full(stream, &c, &len)); 173251881Speter if (c != '\n') 174251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, 175289180Speter _("Serialized hash malformed value data")); 176289180Speter } 177289180Speter else 178289180Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, 179289180Speter _("Serialized hash malformed")); 180289180Speter } 181289180Speter else if (incremental && (buf->len >= 3) 182289180Speter && (buf->data[0] == 'D') && (buf->data[1] == ' ')) 183289180Speter { 184289180Speter /* Get the length of the key */ 185289180Speter err = svn_cstring_strtoui64(&ui64, buf->data + 2, 186289180Speter 0, APR_SIZE_MAX, 10); 187289180Speter if (err) 188289180Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, err, 189289180Speter _("Serialized hash malformed key length")); 190289180Speter entry->keylen = (apr_size_t)ui64; 191251881Speter 192289180Speter /* Now read that much into a buffer. */ 193289180Speter entry->key = apr_palloc(pool, entry->keylen + 1); 194289180Speter SVN_ERR(svn_stream_read_full(stream, entry->key, &entry->keylen)); 195289180Speter entry->key[entry->keylen] = '\0'; 196251881Speter 197289180Speter /* Suck up extra newline after key data */ 198289180Speter len = 1; 199289180Speter SVN_ERR(svn_stream_read_full(stream, &c, &len)); 200289180Speter if (c != '\n') 201289180Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, 202289180Speter _("Serialized hash malformed key data")); 203251881Speter 204289180Speter /* Remove this hash entry. */ 205289180Speter entry->vallen = 0; 206289180Speter entry->val = NULL; 207289180Speter } 208289180Speter else 209289180Speter { 210289180Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, 211289180Speter _("Serialized hash malformed")); 212289180Speter } 213251881Speter 214289180Speter return SVN_NO_ERROR; 215289180Speter} 216251881Speter 217289180Speterstatic svn_error_t * 218289180Speterhash_read(apr_hash_t *hash, svn_stream_t *stream, const char *terminator, 219289180Speter svn_boolean_t incremental, apr_pool_t *pool) 220289180Speter{ 221289180Speter apr_pool_t *iterpool = svn_pool_create(pool); 222251881Speter 223289180Speter while (1) 224289180Speter { 225289180Speter svn_hash__entry_t entry; 226251881Speter 227289180Speter svn_pool_clear(iterpool); 228289180Speter SVN_ERR(svn_hash__read_entry(&entry, stream, terminator, 229289180Speter incremental, iterpool)); 230251881Speter 231289180Speter /* end of hash? */ 232289180Speter if (entry.key == NULL) 233289180Speter break; 234289180Speter 235289180Speter if (entry.val) 236289180Speter { 237289180Speter /* Add a new hash entry. */ 238289180Speter apr_hash_set(hash, apr_pstrmemdup(pool, entry.key, entry.keylen), 239289180Speter entry.keylen, 240289180Speter svn_string_ncreate(entry.val, entry.vallen, pool)); 241251881Speter } 242251881Speter else 243251881Speter { 244289180Speter /* Remove this hash entry. */ 245289180Speter apr_hash_set(hash, entry.key, entry.keylen, NULL); 246251881Speter } 247251881Speter } 248251881Speter 249251881Speter svn_pool_destroy(iterpool); 250251881Speter return SVN_NO_ERROR; 251251881Speter} 252251881Speter 253251881Speter 254251881Speter/* Implements svn_hash_write2 and svn_hash_write_incremental. */ 255251881Speterstatic svn_error_t * 256251881Speterhash_write(apr_hash_t *hash, apr_hash_t *oldhash, svn_stream_t *stream, 257251881Speter const char *terminator, apr_pool_t *pool) 258251881Speter{ 259251881Speter apr_pool_t *subpool; 260251881Speter apr_size_t len; 261251881Speter apr_array_header_t *list; 262251881Speter int i; 263251881Speter 264251881Speter subpool = svn_pool_create(pool); 265251881Speter 266251881Speter list = svn_sort__hash(hash, svn_sort_compare_items_lexically, pool); 267251881Speter for (i = 0; i < list->nelts; i++) 268251881Speter { 269251881Speter svn_sort__item_t *item = &APR_ARRAY_IDX(list, i, svn_sort__item_t); 270251881Speter svn_string_t *valstr = item->value; 271251881Speter 272251881Speter svn_pool_clear(subpool); 273251881Speter 274251881Speter /* Don't output entries equal to the ones in oldhash, if present. */ 275251881Speter if (oldhash) 276251881Speter { 277251881Speter svn_string_t *oldstr = apr_hash_get(oldhash, item->key, item->klen); 278251881Speter 279251881Speter if (oldstr && svn_string_compare(valstr, oldstr)) 280251881Speter continue; 281251881Speter } 282251881Speter 283251881Speter if (item->klen < 0) 284251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, 285251881Speter _("Cannot serialize negative length")); 286251881Speter 287251881Speter /* Write it out. */ 288251881Speter SVN_ERR(svn_stream_printf(stream, subpool, 289251881Speter "K %" APR_SIZE_T_FMT "\n%s\n" 290251881Speter "V %" APR_SIZE_T_FMT "\n", 291251881Speter (apr_size_t) item->klen, 292251881Speter (const char *) item->key, 293251881Speter valstr->len)); 294251881Speter len = valstr->len; 295251881Speter SVN_ERR(svn_stream_write(stream, valstr->data, &len)); 296251881Speter SVN_ERR(svn_stream_puts(stream, "\n")); 297251881Speter } 298251881Speter 299251881Speter if (oldhash) 300251881Speter { 301251881Speter /* Output a deletion entry for each property in oldhash but not hash. */ 302251881Speter list = svn_sort__hash(oldhash, svn_sort_compare_items_lexically, 303251881Speter pool); 304251881Speter for (i = 0; i < list->nelts; i++) 305251881Speter { 306251881Speter svn_sort__item_t *item = &APR_ARRAY_IDX(list, i, svn_sort__item_t); 307251881Speter 308251881Speter svn_pool_clear(subpool); 309251881Speter 310251881Speter /* If it's not present in the new hash, write out a D entry. */ 311251881Speter if (! apr_hash_get(hash, item->key, item->klen)) 312251881Speter SVN_ERR(svn_stream_printf(stream, subpool, 313251881Speter "D %" APR_SSIZE_T_FMT "\n%s\n", 314251881Speter item->klen, (const char *) item->key)); 315251881Speter } 316251881Speter } 317251881Speter 318251881Speter if (terminator) 319251881Speter SVN_ERR(svn_stream_printf(stream, subpool, "%s\n", terminator)); 320251881Speter 321251881Speter svn_pool_destroy(subpool); 322251881Speter return SVN_NO_ERROR; 323251881Speter} 324251881Speter 325251881Speter 326251881Spetersvn_error_t *svn_hash_read2(apr_hash_t *hash, svn_stream_t *stream, 327251881Speter const char *terminator, apr_pool_t *pool) 328251881Speter{ 329251881Speter return hash_read(hash, stream, terminator, FALSE, pool); 330251881Speter} 331251881Speter 332251881Speter 333251881Spetersvn_error_t *svn_hash_read_incremental(apr_hash_t *hash, 334251881Speter svn_stream_t *stream, 335251881Speter const char *terminator, 336251881Speter apr_pool_t *pool) 337251881Speter{ 338251881Speter return hash_read(hash, stream, terminator, TRUE, pool); 339251881Speter} 340251881Speter 341251881Speter 342251881Spetersvn_error_t * 343251881Spetersvn_hash_write2(apr_hash_t *hash, svn_stream_t *stream, 344251881Speter const char *terminator, apr_pool_t *pool) 345251881Speter{ 346251881Speter return hash_write(hash, NULL, stream, terminator, pool); 347251881Speter} 348251881Speter 349251881Speter 350251881Spetersvn_error_t * 351251881Spetersvn_hash_write_incremental(apr_hash_t *hash, apr_hash_t *oldhash, 352251881Speter svn_stream_t *stream, const char *terminator, 353251881Speter apr_pool_t *pool) 354251881Speter{ 355251881Speter SVN_ERR_ASSERT(oldhash != NULL); 356251881Speter return hash_write(hash, oldhash, stream, terminator, pool); 357251881Speter} 358251881Speter 359251881Speter 360251881Spetersvn_error_t * 361251881Spetersvn_hash_write(apr_hash_t *hash, apr_file_t *destfile, apr_pool_t *pool) 362251881Speter{ 363251881Speter return hash_write(hash, NULL, svn_stream_from_aprfile2(destfile, TRUE, pool), 364251881Speter SVN_HASH_TERMINATOR, pool); 365251881Speter} 366251881Speter 367251881Speter 368251881Speter/* There are enough quirks in the deprecated svn_hash_read that we 369251881Speter should just preserve its implementation. */ 370251881Spetersvn_error_t * 371251881Spetersvn_hash_read(apr_hash_t *hash, 372251881Speter apr_file_t *srcfile, 373251881Speter apr_pool_t *pool) 374251881Speter{ 375251881Speter svn_error_t *err; 376251881Speter char buf[SVN_KEYLINE_MAXLEN]; 377251881Speter apr_size_t num_read; 378251881Speter char c; 379251881Speter int first_time = 1; 380251881Speter 381251881Speter 382251881Speter while (1) 383251881Speter { 384251881Speter /* Read a key length line. Might be END, though. */ 385251881Speter apr_size_t len = sizeof(buf); 386251881Speter 387251881Speter err = svn_io_read_length_line(srcfile, buf, &len, pool); 388251881Speter if (err && APR_STATUS_IS_EOF(err->apr_err) && first_time) 389251881Speter { 390251881Speter /* We got an EOF on our very first attempt to read, which 391251881Speter means it's a zero-byte file. No problem, just go home. */ 392251881Speter svn_error_clear(err); 393251881Speter return SVN_NO_ERROR; 394251881Speter } 395251881Speter else if (err) 396251881Speter /* Any other circumstance is a genuine error. */ 397251881Speter return err; 398251881Speter 399251881Speter first_time = 0; 400251881Speter 401251881Speter if (((len == 3) && (buf[0] == 'E') && (buf[1] == 'N') && (buf[2] == 'D')) 402251881Speter || ((len == 9) 403251881Speter && (buf[0] == 'P') 404251881Speter && (buf[1] == 'R') /* We formerly used just "END" to */ 405251881Speter && (buf[2] == 'O') /* end a property hash, but later */ 406251881Speter && (buf[3] == 'P') /* we added "PROPS-END", so that */ 407251881Speter && (buf[4] == 'S') /* the fs dump format would be */ 408251881Speter && (buf[5] == '-') /* more human-readable. That's */ 409251881Speter && (buf[6] == 'E') /* why we accept either way here. */ 410251881Speter && (buf[7] == 'N') 411251881Speter && (buf[8] == 'D'))) 412251881Speter { 413251881Speter /* We've reached the end of the dumped hash table, so leave. */ 414251881Speter return SVN_NO_ERROR; 415251881Speter } 416251881Speter else if ((buf[0] == 'K') && (buf[1] == ' ')) 417251881Speter { 418251881Speter size_t keylen; 419251881Speter int parsed_len; 420251881Speter void *keybuf; 421251881Speter 422251881Speter /* Get the length of the key */ 423251881Speter SVN_ERR(svn_cstring_atoi(&parsed_len, buf + 2)); 424251881Speter keylen = parsed_len; 425251881Speter 426251881Speter /* Now read that much into a buffer, + 1 byte for null terminator */ 427251881Speter keybuf = apr_palloc(pool, keylen + 1); 428251881Speter SVN_ERR(svn_io_file_read_full2(srcfile, 429251881Speter keybuf, keylen, 430251881Speter &num_read, NULL, pool)); 431251881Speter ((char *) keybuf)[keylen] = '\0'; 432251881Speter 433251881Speter /* Suck up extra newline after key data */ 434251881Speter SVN_ERR(svn_io_file_getc(&c, srcfile, pool)); 435251881Speter if (c != '\n') 436251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL); 437251881Speter 438251881Speter /* Read a val length line */ 439251881Speter len = sizeof(buf); 440251881Speter SVN_ERR(svn_io_read_length_line(srcfile, buf, &len, pool)); 441251881Speter 442251881Speter if ((buf[0] == 'V') && (buf[1] == ' ')) 443251881Speter { 444251881Speter svn_string_t *value = apr_palloc(pool, sizeof(*value)); 445251881Speter apr_size_t vallen; 446251881Speter void *valbuf; 447251881Speter 448251881Speter /* Get the length of the value */ 449251881Speter SVN_ERR(svn_cstring_atoi(&parsed_len, buf + 2)); 450251881Speter vallen = parsed_len; 451251881Speter 452251881Speter /* Again, 1 extra byte for the null termination. */ 453251881Speter valbuf = apr_palloc(pool, vallen + 1); 454251881Speter SVN_ERR(svn_io_file_read_full2(srcfile, 455251881Speter valbuf, vallen, 456251881Speter &num_read, NULL, pool)); 457251881Speter ((char *) valbuf)[vallen] = '\0'; 458251881Speter 459251881Speter /* Suck up extra newline after val data */ 460251881Speter SVN_ERR(svn_io_file_getc(&c, srcfile, pool)); 461251881Speter if (c != '\n') 462251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL); 463251881Speter 464251881Speter value->data = valbuf; 465251881Speter value->len = vallen; 466251881Speter 467251881Speter /* The Grand Moment: add a new hash entry! */ 468251881Speter apr_hash_set(hash, keybuf, keylen, value); 469251881Speter } 470251881Speter else 471251881Speter { 472251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL); 473251881Speter } 474251881Speter } 475251881Speter else 476251881Speter { 477251881Speter return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL); 478251881Speter } 479251881Speter } /* while (1) */ 480251881Speter} 481251881Speter 482251881Speter 483251881Speter 484251881Speter/*** Diffing hashes ***/ 485251881Speter 486251881Spetersvn_error_t * 487251881Spetersvn_hash_diff(apr_hash_t *hash_a, 488251881Speter apr_hash_t *hash_b, 489251881Speter svn_hash_diff_func_t diff_func, 490251881Speter void *diff_func_baton, 491251881Speter apr_pool_t *pool) 492251881Speter{ 493251881Speter apr_hash_index_t *hi; 494251881Speter 495251881Speter if (hash_a) 496251881Speter for (hi = apr_hash_first(pool, hash_a); hi; hi = apr_hash_next(hi)) 497251881Speter { 498251881Speter const void *key; 499251881Speter apr_ssize_t klen; 500251881Speter 501251881Speter apr_hash_this(hi, &key, &klen, NULL); 502251881Speter 503251881Speter if (hash_b && (apr_hash_get(hash_b, key, klen))) 504251881Speter SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_both, 505251881Speter diff_func_baton)); 506251881Speter else 507251881Speter SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_a, 508251881Speter diff_func_baton)); 509251881Speter } 510251881Speter 511251881Speter if (hash_b) 512251881Speter for (hi = apr_hash_first(pool, hash_b); hi; hi = apr_hash_next(hi)) 513251881Speter { 514251881Speter const void *key; 515251881Speter apr_ssize_t klen; 516251881Speter 517251881Speter apr_hash_this(hi, &key, &klen, NULL); 518251881Speter 519251881Speter if (! (hash_a && apr_hash_get(hash_a, key, klen))) 520251881Speter SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_b, 521251881Speter diff_func_baton)); 522251881Speter } 523251881Speter 524251881Speter return SVN_NO_ERROR; 525251881Speter} 526251881Speter 527251881Speter 528251881Speter/*** Misc. hash APIs ***/ 529251881Speter 530251881Spetersvn_error_t * 531251881Spetersvn_hash_keys(apr_array_header_t **array, 532251881Speter apr_hash_t *hash, 533251881Speter apr_pool_t *pool) 534251881Speter{ 535251881Speter apr_hash_index_t *hi; 536251881Speter 537251881Speter *array = apr_array_make(pool, apr_hash_count(hash), sizeof(const char *)); 538251881Speter 539251881Speter for (hi = apr_hash_first(pool, hash); hi; hi = apr_hash_next(hi)) 540251881Speter { 541289180Speter APR_ARRAY_PUSH(*array, const char *) = apr_hash_this_key(hi); 542251881Speter } 543251881Speter 544251881Speter return SVN_NO_ERROR; 545251881Speter} 546251881Speter 547251881Speter 548251881Spetersvn_error_t * 549251881Spetersvn_hash_from_cstring_keys(apr_hash_t **hash_p, 550251881Speter const apr_array_header_t *keys, 551251881Speter apr_pool_t *pool) 552251881Speter{ 553251881Speter int i; 554251881Speter apr_hash_t *hash = svn_hash__make(pool); 555251881Speter for (i = 0; i < keys->nelts; i++) 556251881Speter { 557251881Speter const char *key = 558251881Speter apr_pstrdup(pool, APR_ARRAY_IDX(keys, i, const char *)); 559251881Speter svn_hash_sets(hash, key, key); 560251881Speter } 561251881Speter *hash_p = hash; 562251881Speter return SVN_NO_ERROR; 563251881Speter} 564251881Speter 565251881Speter 566362181Sdimvoid * 567362181Sdimsvn_hash__gets_debug(apr_hash_t *ht, const char *key) 568362181Sdim{ 569362181Sdim return apr_hash_get(ht, key, APR_HASH_KEY_STRING); 570362181Sdim} 571362181Sdim 572362181Sdim 573362181Sdimvoid 574362181Sdimsvn_hash__sets_debug(apr_hash_t *ht, const char *key, const void *val) 575362181Sdim{ 576362181Sdim apr_hash_set(ht, key, APR_HASH_KEY_STRING, val); 577362181Sdim} 578362181Sdim 579362181Sdim 580251881Speter 581251881Speter/*** Specialized getter APIs ***/ 582251881Speter 583251881Speterconst char * 584251881Spetersvn_hash__get_cstring(apr_hash_t *hash, 585251881Speter const char *key, 586251881Speter const char *default_value) 587251881Speter{ 588251881Speter if (hash) 589251881Speter { 590251881Speter const char *value = svn_hash_gets(hash, key); 591251881Speter return value ? value : default_value; 592251881Speter } 593251881Speter 594251881Speter return default_value; 595251881Speter} 596251881Speter 597251881Speter 598251881Spetersvn_boolean_t 599251881Spetersvn_hash__get_bool(apr_hash_t *hash, const char *key, 600251881Speter svn_boolean_t default_value) 601251881Speter{ 602251881Speter const char *tmp_value = svn_hash__get_cstring(hash, key, NULL); 603251881Speter svn_tristate_t value = svn_tristate__from_word(tmp_value); 604251881Speter 605251881Speter if (value == svn_tristate_true) 606251881Speter return TRUE; 607251881Speter else if (value == svn_tristate_false) 608251881Speter return FALSE; 609251881Speter 610251881Speter return default_value; 611251881Speter} 612251881Speter 613251881Speter 614251881Speter 615251881Speter/*** Optimized hash function ***/ 616251881Speter 617289180Speter/* apr_hashfunc_t optimized for the key that we use in SVN: paths and 618289180Speter * property names. Its primary goal is speed for keys of known length. 619251881Speter * 620289180Speter * Since strings tend to spawn large value spaces (usually differ in many 621289180Speter * bits with differences spanning a larger section of the key), we can be 622289180Speter * quite sloppy extracting a hash value. The more keys there are in a 623289180Speter * hash container, the more bits of the value returned by this function 624289180Speter * will be used. For a small number of string keys, choosing bits from any 625289180Speter * any fix location close to the tail of those keys would usually be good 626289180Speter * enough to prevent high collision rates. 627251881Speter */ 628251881Speterstatic unsigned int 629251881Speterhashfunc_compatible(const char *char_key, apr_ssize_t *klen) 630251881Speter{ 631251881Speter unsigned int hash = 0; 632251881Speter const unsigned char *key = (const unsigned char *)char_key; 633251881Speter const unsigned char *p; 634251881Speter apr_ssize_t i; 635251881Speter 636251881Speter if (*klen == APR_HASH_KEY_STRING) 637289180Speter *klen = strlen(char_key); 638289180Speter 639289180Speter#if SVN_UNALIGNED_ACCESS_IS_OK 640289180Speter for (p = key, i = *klen; i >= 4; i-=4, p+=4) 641251881Speter { 642289180Speter apr_uint32_t chunk = *(const apr_uint32_t *)p; 643251881Speter 644289180Speter /* the ">> 17" part gives upper bits in the chunk a chance to make 645289180Speter some impact as well */ 646289180Speter hash = hash * 33 * 33 * 33 * 33 + chunk + (chunk >> 17); 647251881Speter } 648289180Speter#else 649289180Speter for (p = key, i = *klen; i >= 4; i-=4, p+=4) 650251881Speter { 651289180Speter hash = hash * 33 * 33 * 33 * 33 652289180Speter + p[0] * 33 * 33 * 33 653289180Speter + p[1] * 33 * 33 654289180Speter + p[2] * 33 655289180Speter + p[3]; 656251881Speter } 657289180Speter#endif 658289180Speter for (; i; i--, p++) 659289180Speter hash = hash * 33 + *p; 660251881Speter 661251881Speter return hash; 662251881Speter} 663251881Speter 664251881Speterapr_hash_t * 665251881Spetersvn_hash__make(apr_pool_t *pool) 666251881Speter{ 667251881Speter return apr_hash_make_custom(pool, hashfunc_compatible); 668251881Speter} 669