1251881Speter/* 2251881Speter * string.c: routines to manipulate counted-length strings 3251881Speter * (svn_stringbuf_t and svn_string_t) and C strings. 4251881Speter * 5251881Speter * 6251881Speter * ==================================================================== 7251881Speter * Licensed to the Apache Software Foundation (ASF) under one 8251881Speter * or more contributor license agreements. See the NOTICE file 9251881Speter * distributed with this work for additional information 10251881Speter * regarding copyright ownership. The ASF licenses this file 11251881Speter * to you under the Apache License, Version 2.0 (the 12251881Speter * "License"); you may not use this file except in compliance 13251881Speter * with the License. You may obtain a copy of the License at 14251881Speter * 15251881Speter * http://www.apache.org/licenses/LICENSE-2.0 16251881Speter * 17251881Speter * Unless required by applicable law or agreed to in writing, 18251881Speter * software distributed under the License is distributed on an 19251881Speter * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 20251881Speter * KIND, either express or implied. See the License for the 21251881Speter * specific language governing permissions and limitations 22251881Speter * under the License. 23251881Speter * ==================================================================== 24251881Speter */ 25251881Speter 26251881Speter 27251881Speter 28251881Speter#include <apr.h> 29289180Speter#include <assert.h> 30251881Speter 31251881Speter#include <string.h> /* for memcpy(), memcmp(), strlen() */ 32251881Speter#include <apr_fnmatch.h> 33251881Speter#include "svn_string.h" /* loads "svn_types.h" and <apr_pools.h> */ 34251881Speter#include "svn_ctype.h" 35251881Speter#include "private/svn_dep_compat.h" 36251881Speter#include "private/svn_string_private.h" 37251881Speter 38251881Speter#include "svn_private_config.h" 39251881Speter 40251881Speter 41251881Speter 42251881Speter/* Allocate the space for a memory buffer from POOL. 43251881Speter * Return a pointer to the new buffer in *DATA and its size in *SIZE. 44251881Speter * The buffer size will be at least MINIMUM_SIZE. 45251881Speter * 46251881Speter * N.B.: The stringbuf creation functions use this, but since stringbufs 47251881Speter * always consume at least 1 byte for the NUL terminator, the 48251881Speter * resulting data pointers will never be NULL. 49251881Speter */ 50251881Speterstatic APR_INLINE void 51251881Spetermembuf_create(void **data, apr_size_t *size, 52251881Speter apr_size_t minimum_size, apr_pool_t *pool) 53251881Speter{ 54251881Speter /* apr_palloc will allocate multiples of 8. 55251881Speter * Thus, we would waste some of that memory if we stuck to the 56251881Speter * smaller size. Note that this is safe even if apr_palloc would 57289180Speter * use some other alignment or none at all. */ 58251881Speter minimum_size = APR_ALIGN_DEFAULT(minimum_size); 59289180Speter *data = apr_palloc(pool, minimum_size); 60251881Speter *size = minimum_size; 61251881Speter} 62251881Speter 63251881Speter/* Ensure that the size of a given memory buffer is at least MINIMUM_SIZE 64251881Speter * bytes. If *SIZE is already greater than or equal to MINIMUM_SIZE, 65251881Speter * this function does nothing. 66251881Speter * 67251881Speter * If *SIZE is 0, the allocated buffer size will be MINIMUM_SIZE 68251881Speter * rounded up to the nearest APR alignment boundary. Otherwse, *SIZE 69251881Speter * will be multiplied by a power of two such that the result is 70251881Speter * greater or equal to MINIMUM_SIZE. The pointer to the new buffer 71251881Speter * will be returned in *DATA, and its size in *SIZE. 72251881Speter */ 73251881Speterstatic APR_INLINE void 74251881Spetermembuf_ensure(void **data, apr_size_t *size, 75251881Speter apr_size_t minimum_size, apr_pool_t *pool) 76251881Speter{ 77251881Speter if (minimum_size > *size) 78251881Speter { 79251881Speter apr_size_t new_size = *size; 80251881Speter 81251881Speter if (new_size == 0) 82251881Speter new_size = minimum_size; 83251881Speter else 84251881Speter while (new_size < minimum_size) 85251881Speter { 86251881Speter const apr_size_t prev_size = new_size; 87251881Speter new_size *= 2; 88251881Speter 89251881Speter /* check for apr_size_t overflow */ 90251881Speter if (prev_size > new_size) 91251881Speter { 92251881Speter new_size = minimum_size; 93251881Speter break; 94251881Speter } 95251881Speter } 96251881Speter 97251881Speter membuf_create(data, size, new_size, pool); 98251881Speter } 99251881Speter} 100251881Speter 101251881Spetervoid 102251881Spetersvn_membuf__create(svn_membuf_t *membuf, apr_size_t size, apr_pool_t *pool) 103251881Speter{ 104251881Speter membuf_create(&membuf->data, &membuf->size, size, pool); 105251881Speter membuf->pool = pool; 106251881Speter} 107251881Speter 108251881Spetervoid 109251881Spetersvn_membuf__ensure(svn_membuf_t *membuf, apr_size_t size) 110251881Speter{ 111251881Speter membuf_ensure(&membuf->data, &membuf->size, size, membuf->pool); 112251881Speter} 113251881Speter 114251881Spetervoid 115251881Spetersvn_membuf__resize(svn_membuf_t *membuf, apr_size_t size) 116251881Speter{ 117251881Speter const void *const old_data = membuf->data; 118251881Speter const apr_size_t old_size = membuf->size; 119251881Speter 120251881Speter membuf_ensure(&membuf->data, &membuf->size, size, membuf->pool); 121289180Speter 122289180Speter /* If we re-allocated MEMBUF->DATA, it cannot be NULL. 123289180Speter * Statically initialized membuffers (OLD_DATA) may be NULL, though. */ 124289180Speter if (old_data && old_data != membuf->data) 125251881Speter memcpy(membuf->data, old_data, old_size); 126251881Speter} 127251881Speter 128251881Speter/* Always provide an out-of-line implementation of svn_membuf__zero */ 129251881Speter#undef svn_membuf__zero 130251881Spetervoid 131251881Spetersvn_membuf__zero(svn_membuf_t *membuf) 132251881Speter{ 133251881Speter SVN_MEMBUF__ZERO(membuf); 134251881Speter} 135251881Speter 136251881Speter/* Always provide an out-of-line implementation of svn_membuf__nzero */ 137251881Speter#undef svn_membuf__nzero 138251881Spetervoid 139251881Spetersvn_membuf__nzero(svn_membuf_t *membuf, apr_size_t size) 140251881Speter{ 141251881Speter SVN_MEMBUF__NZERO(membuf, size); 142251881Speter} 143251881Speter 144251881Speterstatic APR_INLINE svn_boolean_t 145251881Speterstring_compare(const char *str1, 146251881Speter const char *str2, 147251881Speter apr_size_t len1, 148251881Speter apr_size_t len2) 149251881Speter{ 150251881Speter /* easy way out :) */ 151251881Speter if (len1 != len2) 152251881Speter return FALSE; 153251881Speter 154289180Speter /* now the strings must have identical lengths */ 155251881Speter 156251881Speter if ((memcmp(str1, str2, len1)) == 0) 157251881Speter return TRUE; 158251881Speter else 159251881Speter return FALSE; 160251881Speter} 161251881Speter 162251881Speterstatic APR_INLINE apr_size_t 163251881Speterstring_first_non_whitespace(const char *str, apr_size_t len) 164251881Speter{ 165251881Speter apr_size_t i; 166251881Speter 167251881Speter for (i = 0; i < len; i++) 168251881Speter { 169251881Speter if (! svn_ctype_isspace(str[i])) 170251881Speter return i; 171251881Speter } 172251881Speter 173251881Speter /* if we get here, then the string must be entirely whitespace */ 174251881Speter return len; 175251881Speter} 176251881Speter 177251881Speterstatic APR_INLINE apr_size_t 178251881Speterfind_char_backward(const char *str, apr_size_t len, char ch) 179251881Speter{ 180251881Speter apr_size_t i = len; 181251881Speter 182251881Speter while (i != 0) 183251881Speter { 184251881Speter if (str[--i] == ch) 185251881Speter return i; 186251881Speter } 187251881Speter 188251881Speter /* char was not found, return len */ 189251881Speter return len; 190251881Speter} 191251881Speter 192251881Speter 193251881Speter/* svn_string functions */ 194251881Speter 195251881Speter/* Return a new svn_string_t object, allocated in POOL, initialized with 196251881Speter * DATA and SIZE. Do not copy the contents of DATA, just store the pointer. 197251881Speter * SIZE is the length in bytes of DATA, excluding the required NUL 198251881Speter * terminator. */ 199251881Speterstatic svn_string_t * 200251881Spetercreate_string(const char *data, apr_size_t size, 201251881Speter apr_pool_t *pool) 202251881Speter{ 203251881Speter svn_string_t *new_string; 204251881Speter 205251881Speter new_string = apr_palloc(pool, sizeof(*new_string)); 206251881Speter 207251881Speter new_string->data = data; 208251881Speter new_string->len = size; 209251881Speter 210251881Speter return new_string; 211251881Speter} 212251881Speter 213251881Speter/* A data buffer for a zero-length string (just a null terminator). Many 214251881Speter * svn_string_t instances may share this same buffer. */ 215251881Speterstatic const char empty_buffer[1] = {0}; 216251881Speter 217251881Spetersvn_string_t * 218251881Spetersvn_string_create_empty(apr_pool_t *pool) 219251881Speter{ 220251881Speter svn_string_t *new_string = apr_palloc(pool, sizeof(*new_string)); 221251881Speter new_string->data = empty_buffer; 222251881Speter new_string->len = 0; 223251881Speter 224251881Speter return new_string; 225251881Speter} 226251881Speter 227251881Speter 228251881Spetersvn_string_t * 229251881Spetersvn_string_ncreate(const char *bytes, apr_size_t size, apr_pool_t *pool) 230251881Speter{ 231251881Speter void *mem; 232251881Speter char *data; 233251881Speter svn_string_t *new_string; 234251881Speter 235251881Speter /* Allocate memory for svn_string_t and data in one chunk. */ 236251881Speter mem = apr_palloc(pool, sizeof(*new_string) + size + 1); 237251881Speter data = (char*)mem + sizeof(*new_string); 238251881Speter 239251881Speter new_string = mem; 240251881Speter new_string->data = data; 241251881Speter new_string->len = size; 242251881Speter 243289180Speter /* If SIZE is 0, NULL is valid for BYTES. */ 244289180Speter if (size) 245289180Speter memcpy(data, bytes, size); 246251881Speter 247251881Speter /* Null termination is the convention -- even if we suspect the data 248251881Speter to be binary, it's not up to us to decide, it's the caller's 249251881Speter call. Heck, that's why they call it the caller! */ 250251881Speter data[size] = '\0'; 251251881Speter 252251881Speter return new_string; 253251881Speter} 254251881Speter 255251881Speter 256251881Spetersvn_string_t * 257251881Spetersvn_string_create(const char *cstring, apr_pool_t *pool) 258251881Speter{ 259251881Speter return svn_string_ncreate(cstring, strlen(cstring), pool); 260251881Speter} 261251881Speter 262251881Speter 263251881Spetersvn_string_t * 264251881Spetersvn_string_create_from_buf(const svn_stringbuf_t *strbuf, apr_pool_t *pool) 265251881Speter{ 266251881Speter return svn_string_ncreate(strbuf->data, strbuf->len, pool); 267251881Speter} 268251881Speter 269251881Speter 270251881Spetersvn_string_t * 271251881Spetersvn_string_createv(apr_pool_t *pool, const char *fmt, va_list ap) 272251881Speter{ 273251881Speter char *data = apr_pvsprintf(pool, fmt, ap); 274251881Speter 275251881Speter /* wrap an svn_string_t around the new data */ 276251881Speter return create_string(data, strlen(data), pool); 277251881Speter} 278251881Speter 279251881Speter 280251881Spetersvn_string_t * 281251881Spetersvn_string_createf(apr_pool_t *pool, const char *fmt, ...) 282251881Speter{ 283251881Speter svn_string_t *str; 284251881Speter 285251881Speter va_list ap; 286251881Speter va_start(ap, fmt); 287251881Speter str = svn_string_createv(pool, fmt, ap); 288251881Speter va_end(ap); 289251881Speter 290251881Speter return str; 291251881Speter} 292251881Speter 293251881Speter 294251881Spetersvn_boolean_t 295251881Spetersvn_string_isempty(const svn_string_t *str) 296251881Speter{ 297251881Speter return (str->len == 0); 298251881Speter} 299251881Speter 300251881Speter 301251881Spetersvn_string_t * 302251881Spetersvn_string_dup(const svn_string_t *original_string, apr_pool_t *pool) 303251881Speter{ 304289180Speter return (original_string ? svn_string_ncreate(original_string->data, 305289180Speter original_string->len, pool) 306289180Speter : NULL); 307251881Speter} 308251881Speter 309251881Speter 310251881Speter 311251881Spetersvn_boolean_t 312251881Spetersvn_string_compare(const svn_string_t *str1, const svn_string_t *str2) 313251881Speter{ 314251881Speter return 315251881Speter string_compare(str1->data, str2->data, str1->len, str2->len); 316251881Speter} 317251881Speter 318251881Speter 319251881Speter 320251881Speterapr_size_t 321251881Spetersvn_string_first_non_whitespace(const svn_string_t *str) 322251881Speter{ 323251881Speter return 324251881Speter string_first_non_whitespace(str->data, str->len); 325251881Speter} 326251881Speter 327251881Speter 328251881Speterapr_size_t 329251881Spetersvn_string_find_char_backward(const svn_string_t *str, char ch) 330251881Speter{ 331251881Speter return find_char_backward(str->data, str->len, ch); 332251881Speter} 333251881Speter 334251881Spetersvn_string_t * 335251881Spetersvn_stringbuf__morph_into_string(svn_stringbuf_t *strbuf) 336251881Speter{ 337251881Speter /* In debug mode, detect attempts to modify the original STRBUF object. 338251881Speter */ 339251881Speter#ifdef SVN_DEBUG 340251881Speter strbuf->pool = NULL; 341251881Speter strbuf->blocksize = strbuf->len + 1; 342251881Speter#endif 343251881Speter 344251881Speter /* Both, svn_string_t and svn_stringbuf_t are public API structures 345251881Speter * since the svn epoch. Thus, we can rely on their precise layout not 346251881Speter * to change. 347251881Speter * 348251881Speter * It just so happens that svn_string_t is structurally equivalent 349251881Speter * to the (data, len) sub-set of svn_stringbuf_t. There is also no 350251881Speter * difference in alignment and padding. So, we can just re-interpret 351251881Speter * that part of STRBUF as a svn_string_t. 352251881Speter * 353251881Speter * However, since svn_string_t does not know about the blocksize 354251881Speter * member in svn_stringbuf_t, any attempt to re-size the returned 355251881Speter * svn_string_t might invalidate the STRBUF struct. Hence, we consider 356251881Speter * the source STRBUF "consumed". 357251881Speter * 358251881Speter * Modifying the string character content is fine, though. 359251881Speter */ 360251881Speter return (svn_string_t *)&strbuf->data; 361251881Speter} 362251881Speter 363251881Speter 364251881Speter 365251881Speter/* svn_stringbuf functions */ 366251881Speter 367251881Spetersvn_stringbuf_t * 368251881Spetersvn_stringbuf_create_empty(apr_pool_t *pool) 369251881Speter{ 370251881Speter return svn_stringbuf_create_ensure(0, pool); 371251881Speter} 372251881Speter 373251881Spetersvn_stringbuf_t * 374251881Spetersvn_stringbuf_create_ensure(apr_size_t blocksize, apr_pool_t *pool) 375251881Speter{ 376251881Speter void *mem; 377251881Speter svn_stringbuf_t *new_string; 378251881Speter 379251881Speter ++blocksize; /* + space for '\0' */ 380251881Speter 381251881Speter /* Allocate memory for svn_string_t and data in one chunk. */ 382251881Speter membuf_create(&mem, &blocksize, blocksize + sizeof(*new_string), pool); 383251881Speter 384251881Speter /* Initialize header and string */ 385251881Speter new_string = mem; 386251881Speter new_string->data = (char*)mem + sizeof(*new_string); 387251881Speter new_string->data[0] = '\0'; 388251881Speter new_string->len = 0; 389251881Speter new_string->blocksize = blocksize - sizeof(*new_string); 390251881Speter new_string->pool = pool; 391251881Speter 392251881Speter return new_string; 393251881Speter} 394251881Speter 395251881Spetersvn_stringbuf_t * 396251881Spetersvn_stringbuf_ncreate(const char *bytes, apr_size_t size, apr_pool_t *pool) 397251881Speter{ 398251881Speter svn_stringbuf_t *strbuf = svn_stringbuf_create_ensure(size, pool); 399251881Speter 400289180Speter /* If SIZE is 0, NULL is valid for BYTES. */ 401289180Speter if (size) 402289180Speter memcpy(strbuf->data, bytes, size); 403289180Speter 404251881Speter /* Null termination is the convention -- even if we suspect the data 405251881Speter to be binary, it's not up to us to decide, it's the caller's 406251881Speter call. Heck, that's why they call it the caller! */ 407251881Speter strbuf->data[size] = '\0'; 408251881Speter strbuf->len = size; 409251881Speter 410251881Speter return strbuf; 411251881Speter} 412251881Speter 413251881Speter 414251881Spetersvn_stringbuf_t * 415251881Spetersvn_stringbuf_create(const char *cstring, apr_pool_t *pool) 416251881Speter{ 417251881Speter return svn_stringbuf_ncreate(cstring, strlen(cstring), pool); 418251881Speter} 419251881Speter 420251881Speter 421251881Spetersvn_stringbuf_t * 422251881Spetersvn_stringbuf_create_from_string(const svn_string_t *str, apr_pool_t *pool) 423251881Speter{ 424251881Speter return svn_stringbuf_ncreate(str->data, str->len, pool); 425251881Speter} 426251881Speter 427289180Spetersvn_stringbuf_t * 428289180Spetersvn_stringbuf_create_wrap(char *str, apr_pool_t *pool) 429289180Speter{ 430289180Speter svn_stringbuf_t *result = apr_palloc(pool, sizeof(*result)); 431289180Speter result->pool = pool; 432289180Speter result->data = str; 433289180Speter result->len = strlen(str); 434289180Speter result->blocksize = result->len + 1; 435251881Speter 436289180Speter return result; 437289180Speter} 438289180Speter 439251881Spetersvn_stringbuf_t * 440251881Spetersvn_stringbuf_createv(apr_pool_t *pool, const char *fmt, va_list ap) 441251881Speter{ 442251881Speter char *data = apr_pvsprintf(pool, fmt, ap); 443251881Speter apr_size_t size = strlen(data); 444251881Speter svn_stringbuf_t *new_string; 445251881Speter 446251881Speter new_string = apr_palloc(pool, sizeof(*new_string)); 447251881Speter new_string->data = data; 448251881Speter new_string->len = size; 449251881Speter new_string->blocksize = size + 1; 450251881Speter new_string->pool = pool; 451251881Speter 452251881Speter return new_string; 453251881Speter} 454251881Speter 455251881Speter 456251881Spetersvn_stringbuf_t * 457251881Spetersvn_stringbuf_createf(apr_pool_t *pool, const char *fmt, ...) 458251881Speter{ 459251881Speter svn_stringbuf_t *str; 460251881Speter 461251881Speter va_list ap; 462251881Speter va_start(ap, fmt); 463251881Speter str = svn_stringbuf_createv(pool, fmt, ap); 464251881Speter va_end(ap); 465251881Speter 466251881Speter return str; 467251881Speter} 468251881Speter 469251881Speter 470251881Spetervoid 471251881Spetersvn_stringbuf_fillchar(svn_stringbuf_t *str, unsigned char c) 472251881Speter{ 473251881Speter memset(str->data, c, str->len); 474251881Speter} 475251881Speter 476251881Speter 477251881Spetervoid 478251881Spetersvn_stringbuf_set(svn_stringbuf_t *str, const char *value) 479251881Speter{ 480251881Speter apr_size_t amt = strlen(value); 481251881Speter 482362181Sdim membuf_ensure((void**) &str->data, &str->blocksize, amt + 1, str->pool); 483251881Speter memcpy(str->data, value, amt + 1); 484251881Speter str->len = amt; 485251881Speter} 486251881Speter 487251881Spetervoid 488251881Spetersvn_stringbuf_setempty(svn_stringbuf_t *str) 489251881Speter{ 490362181Sdim str->data[0] = '\0'; 491251881Speter str->len = 0; 492251881Speter} 493251881Speter 494251881Speter 495251881Spetervoid 496251881Spetersvn_stringbuf_chop(svn_stringbuf_t *str, apr_size_t nbytes) 497251881Speter{ 498251881Speter if (nbytes > str->len) 499251881Speter str->len = 0; 500251881Speter else 501251881Speter str->len -= nbytes; 502251881Speter 503251881Speter str->data[str->len] = '\0'; 504251881Speter} 505251881Speter 506362181Sdimvoid 507362181Sdimsvn_stringbuf_leftchop(svn_stringbuf_t *str, apr_size_t nbytes) 508362181Sdim{ 509362181Sdim if (str->len == 0) 510362181Sdim return; 511251881Speter 512362181Sdim if (nbytes >= str->len) 513362181Sdim { 514362181Sdim str->len = 0; 515362181Sdim *str->data = '\0'; 516362181Sdim } 517362181Sdim else 518362181Sdim { 519362181Sdim /* Note: This will irretrievably waste nbytes of space in the 520362181Sdim stringbuf's pool, but unlike the alternative of memmoving the 521362181Sdim data, it's a constant-time operation. */ 522362181Sdim str->data += nbytes; 523362181Sdim str->len -= nbytes; 524362181Sdim str->blocksize -= nbytes; 525362181Sdim } 526362181Sdim} 527362181Sdim 528251881Spetersvn_boolean_t 529251881Spetersvn_stringbuf_isempty(const svn_stringbuf_t *str) 530251881Speter{ 531251881Speter return (str->len == 0); 532251881Speter} 533251881Speter 534251881Speter 535251881Spetervoid 536251881Spetersvn_stringbuf_ensure(svn_stringbuf_t *str, apr_size_t minimum_size) 537251881Speter{ 538251881Speter void *mem = NULL; 539251881Speter ++minimum_size; /* + space for '\0' */ 540251881Speter 541251881Speter membuf_ensure(&mem, &str->blocksize, minimum_size, str->pool); 542251881Speter if (mem && mem != str->data) 543251881Speter { 544251881Speter if (str->data) 545251881Speter memcpy(mem, str->data, str->len + 1); 546251881Speter str->data = mem; 547251881Speter } 548251881Speter} 549251881Speter 550251881Speter 551251881Speter/* WARNING - Optimized code ahead! 552251881Speter * This function has been hand-tuned for performance. Please read 553251881Speter * the comments below before modifying the code. 554251881Speter */ 555251881Spetervoid 556251881Spetersvn_stringbuf_appendbyte(svn_stringbuf_t *str, char byte) 557251881Speter{ 558251881Speter char *dest; 559251881Speter apr_size_t old_len = str->len; 560251881Speter 561251881Speter /* In most cases, there will be pre-allocated memory left 562251881Speter * to just write the new byte at the end of the used section 563251881Speter * and terminate the string properly. 564251881Speter */ 565251881Speter if (str->blocksize > old_len + 1) 566251881Speter { 567251881Speter /* The following read does not depend this write, so we 568251881Speter * can issue the write first to minimize register pressure: 569251881Speter * The value of old_len+1 is no longer needed; on most processors, 570251881Speter * dest[old_len+1] will be calculated implicitly as part of 571251881Speter * the addressing scheme. 572251881Speter */ 573251881Speter str->len = old_len+1; 574251881Speter 575251881Speter /* Since the compiler cannot be sure that *src->data and *src 576251881Speter * don't overlap, we read src->data *once* before writing 577251881Speter * to *src->data. Replacing dest with str->data would force 578251881Speter * the compiler to read it again after the first byte. 579251881Speter */ 580251881Speter dest = str->data; 581251881Speter 582251881Speter /* If not already available in a register as per ABI, load 583251881Speter * "byte" into the register (e.g. the one freed from old_len+1), 584251881Speter * then write it to the string buffer and terminate it properly. 585251881Speter * 586251881Speter * Including the "byte" fetch, all operations so far could be 587251881Speter * issued at once and be scheduled at the CPU's descression. 588251881Speter * Most likely, no-one will soon depend on the data that will be 589251881Speter * written in this function. So, no stalls there, either. 590251881Speter */ 591251881Speter dest[old_len] = byte; 592251881Speter dest[old_len+1] = '\0'; 593251881Speter } 594251881Speter else 595251881Speter { 596251881Speter /* we need to re-allocate the string buffer 597251881Speter * -> let the more generic implementation take care of that part 598251881Speter */ 599251881Speter 600251881Speter /* Depending on the ABI, "byte" is a register value. If we were 601251881Speter * to take its address directly, the compiler might decide to 602251881Speter * put in on the stack *unconditionally*, even if that would 603251881Speter * only be necessary for this block. 604251881Speter */ 605251881Speter char b = byte; 606251881Speter svn_stringbuf_appendbytes(str, &b, 1); 607251881Speter } 608251881Speter} 609251881Speter 610251881Speter 611251881Spetervoid 612251881Spetersvn_stringbuf_appendbytes(svn_stringbuf_t *str, const char *bytes, 613251881Speter apr_size_t count) 614251881Speter{ 615251881Speter apr_size_t total_len; 616251881Speter void *start_address; 617251881Speter 618289180Speter if (!count) 619289180Speter /* Allow BYTES to be NULL by avoiding passing it to memcpy. */ 620289180Speter return; 621289180Speter 622251881Speter total_len = str->len + count; /* total size needed */ 623251881Speter 624251881Speter /* svn_stringbuf_ensure adds 1 for null terminator. */ 625251881Speter svn_stringbuf_ensure(str, total_len); 626251881Speter 627251881Speter /* get address 1 byte beyond end of original bytestring */ 628251881Speter start_address = (str->data + str->len); 629251881Speter 630251881Speter memcpy(start_address, bytes, count); 631251881Speter str->len = total_len; 632251881Speter 633251881Speter str->data[str->len] = '\0'; /* We don't know if this is binary 634251881Speter data or not, but convention is 635251881Speter to null-terminate. */ 636251881Speter} 637251881Speter 638289180Spetervoid 639289180Spetersvn_stringbuf_appendfill(svn_stringbuf_t *str, 640289180Speter char byte, 641289180Speter apr_size_t count) 642289180Speter{ 643289180Speter apr_size_t new_len = str->len + count; 644289180Speter svn_stringbuf_ensure(str, new_len); 645251881Speter 646289180Speter memset(str->data + str->len, byte, count); 647289180Speter 648289180Speter /* update buffer length and always NUL-terminate it */ 649289180Speter str->len = new_len; 650289180Speter str->data[new_len] = '\0'; 651289180Speter} 652289180Speter 653289180Speter 654251881Spetervoid 655251881Spetersvn_stringbuf_appendstr(svn_stringbuf_t *targetstr, 656251881Speter const svn_stringbuf_t *appendstr) 657251881Speter{ 658251881Speter svn_stringbuf_appendbytes(targetstr, appendstr->data, appendstr->len); 659251881Speter} 660251881Speter 661251881Speter 662251881Spetervoid 663251881Spetersvn_stringbuf_appendcstr(svn_stringbuf_t *targetstr, const char *cstr) 664251881Speter{ 665251881Speter svn_stringbuf_appendbytes(targetstr, cstr, strlen(cstr)); 666251881Speter} 667251881Speter 668251881Spetervoid 669251881Spetersvn_stringbuf_insert(svn_stringbuf_t *str, 670251881Speter apr_size_t pos, 671251881Speter const char *bytes, 672251881Speter apr_size_t count) 673251881Speter{ 674289180Speter /* For COUNT==0, we allow BYTES to be NULL. It's a no-op in that case. */ 675289180Speter if (count == 0) 676289180Speter return; 677289180Speter 678289180Speter /* special case: BYTES overlaps with this string -> copy the source */ 679251881Speter if (bytes + count > str->data && bytes < str->data + str->blocksize) 680289180Speter bytes = apr_pmemdup(str->pool, bytes, count); 681251881Speter 682289180Speter if (pos > str->len) 683289180Speter pos = str->len; 684251881Speter 685289180Speter svn_stringbuf_ensure(str, str->len + count); 686289180Speter memmove(str->data + pos + count, str->data + pos, str->len - pos + 1); 687289180Speter memcpy(str->data + pos, bytes, count); 688289180Speter 689289180Speter str->len += count; 690251881Speter} 691251881Speter 692251881Spetervoid 693251881Spetersvn_stringbuf_remove(svn_stringbuf_t *str, 694251881Speter apr_size_t pos, 695251881Speter apr_size_t count) 696251881Speter{ 697251881Speter if (pos > str->len) 698251881Speter pos = str->len; 699298845Sdim if (count > str->len - pos) 700251881Speter count = str->len - pos; 701251881Speter 702251881Speter memmove(str->data + pos, str->data + pos + count, str->len - pos - count + 1); 703251881Speter str->len -= count; 704251881Speter} 705251881Speter 706251881Spetervoid 707251881Spetersvn_stringbuf_replace(svn_stringbuf_t *str, 708251881Speter apr_size_t pos, 709251881Speter apr_size_t old_count, 710251881Speter const char *bytes, 711251881Speter apr_size_t new_count) 712251881Speter{ 713289180Speter /* For COUNT==0, we allow BYTES to be NULL. 714289180Speter * In that case, this is just a substring removal. */ 715289180Speter if (new_count == 0) 716251881Speter { 717289180Speter svn_stringbuf_remove(str, pos, old_count); 718289180Speter return; 719251881Speter } 720251881Speter 721289180Speter /* special case: BYTES overlaps with this string -> copy the source */ 722289180Speter if (bytes + new_count > str->data && bytes < str->data + str->blocksize) 723289180Speter bytes = apr_pmemdup(str->pool, bytes, new_count); 724251881Speter 725289180Speter if (pos > str->len) 726289180Speter pos = str->len; 727298845Sdim if (old_count > str->len - pos) 728289180Speter old_count = str->len - pos; 729251881Speter 730289180Speter if (old_count < new_count) 731289180Speter { 732289180Speter apr_size_t delta = new_count - old_count; 733289180Speter svn_stringbuf_ensure(str, str->len + delta); 734251881Speter } 735289180Speter 736289180Speter if (old_count != new_count) 737289180Speter memmove(str->data + pos + new_count, str->data + pos + old_count, 738289180Speter str->len - pos - old_count + 1); 739289180Speter 740289180Speter memcpy(str->data + pos, bytes, new_count); 741289180Speter str->len += new_count - old_count; 742251881Speter} 743251881Speter 744251881Speter 745362181Sdimapr_size_t 746362181Sdimsvn_stringbuf_replace_all(svn_stringbuf_t *str, 747362181Sdim const char *to_find, 748362181Sdim const char *replacement) 749362181Sdim{ 750362181Sdim apr_size_t replacements = 0; 751362181Sdim 752362181Sdim apr_size_t current = 0; 753362181Sdim apr_size_t original_length = str->len; 754362181Sdim 755362181Sdim apr_size_t to_copy; 756362181Sdim apr_size_t to_find_len; 757362181Sdim apr_size_t replacement_len; 758362181Sdim apr_size_t new_length; 759362181Sdim 760362181Sdim /* Early exit. */ 761362181Sdim const char *pos = strstr(str->data, to_find); 762362181Sdim if (pos == NULL) 763362181Sdim return 0; 764362181Sdim 765362181Sdim to_find_len = strlen(to_find); 766362181Sdim replacement_len = strlen(replacement); 767362181Sdim 768362181Sdim /* We will store the new contents behind the NUL terminator of the current 769362181Sdim * data and track the total length in STR->LEN to make the reallocation 770362181Sdim * code preserve both bits. However, we need to keep the NUL between them 771362181Sdim * to make strstr stop at that boundary. */ 772362181Sdim ++str->len; 773362181Sdim 774362181Sdim /* Find all occurrences of TO_FIND, copy the bits in between to the target, 775362181Sdim * separated by REPLACEMENT. */ 776362181Sdim for ( ; pos; pos = strstr(str->data + current, to_find), ++replacements) 777362181Sdim { 778362181Sdim to_copy = pos - str->data - current; 779362181Sdim svn_stringbuf_ensure(str, str->len + to_copy + replacement_len); 780362181Sdim 781362181Sdim if (to_copy) 782362181Sdim memcpy(str->data + str->len, str->data + current, to_copy); 783362181Sdim current += to_copy + to_find_len; 784362181Sdim 785362181Sdim str->len += to_copy; 786362181Sdim memcpy(str->data + str->len, replacement, replacement_len); 787362181Sdim str->len += replacement_len; 788362181Sdim } 789362181Sdim 790362181Sdim /* Copy remainder. */ 791362181Sdim to_copy = original_length - current; 792362181Sdim if (to_copy) 793362181Sdim { 794362181Sdim svn_stringbuf_ensure(str, str->len + to_copy); 795362181Sdim memcpy(str->data + str->len, str->data + current, to_copy); 796362181Sdim str->len += to_copy; 797362181Sdim } 798362181Sdim 799362181Sdim /* Move new contents to the start of the buffer and terminate it. */ 800362181Sdim new_length = str->len - original_length - 1; 801362181Sdim memmove(str->data, str->data + original_length + 1, new_length); 802362181Sdim str->len = new_length; 803362181Sdim str->data[new_length] = 0; 804362181Sdim 805362181Sdim /* Done. */ 806362181Sdim return replacements; 807362181Sdim} 808362181Sdim 809362181Sdim 810251881Spetersvn_stringbuf_t * 811251881Spetersvn_stringbuf_dup(const svn_stringbuf_t *original_string, apr_pool_t *pool) 812251881Speter{ 813251881Speter return (svn_stringbuf_ncreate(original_string->data, 814251881Speter original_string->len, pool)); 815251881Speter} 816251881Speter 817251881Speter 818251881Speter 819251881Spetersvn_boolean_t 820251881Spetersvn_stringbuf_compare(const svn_stringbuf_t *str1, 821251881Speter const svn_stringbuf_t *str2) 822251881Speter{ 823251881Speter return string_compare(str1->data, str2->data, str1->len, str2->len); 824251881Speter} 825251881Speter 826251881Speter 827251881Speter 828251881Speterapr_size_t 829251881Spetersvn_stringbuf_first_non_whitespace(const svn_stringbuf_t *str) 830251881Speter{ 831251881Speter return string_first_non_whitespace(str->data, str->len); 832251881Speter} 833251881Speter 834251881Speter 835251881Spetervoid 836251881Spetersvn_stringbuf_strip_whitespace(svn_stringbuf_t *str) 837251881Speter{ 838362181Sdim /* Skip (hide) whitespace at the beginning of the string. */ 839362181Sdim if (svn_ctype_isspace(str->data[0])) 840362181Sdim { 841362181Sdim /* Find first non-whitespace character */ 842362181Sdim apr_size_t offset = string_first_non_whitespace(str->data + 1, 843362181Sdim str->len - 1) + 1; 844251881Speter 845362181Sdim /* Go ahead! Waste some RAM, we've got pools! :) */ 846362181Sdim str->data += offset; 847362181Sdim str->len -= offset; 848362181Sdim str->blocksize -= offset; 849362181Sdim } 850251881Speter 851251881Speter /* Now that we've trimmed the front, trim the end, wasting more RAM. */ 852251881Speter while ((str->len > 0) && svn_ctype_isspace(str->data[str->len - 1])) 853251881Speter str->len--; 854251881Speter str->data[str->len] = '\0'; 855251881Speter} 856251881Speter 857251881Speter 858251881Speterapr_size_t 859251881Spetersvn_stringbuf_find_char_backward(const svn_stringbuf_t *str, char ch) 860251881Speter{ 861251881Speter return find_char_backward(str->data, str->len, ch); 862251881Speter} 863251881Speter 864251881Speter 865251881Spetersvn_boolean_t 866251881Spetersvn_string_compare_stringbuf(const svn_string_t *str1, 867251881Speter const svn_stringbuf_t *str2) 868251881Speter{ 869251881Speter return string_compare(str1->data, str2->data, str1->len, str2->len); 870251881Speter} 871251881Speter 872251881Speter 873251881Speter 874251881Speter/*** C string stuff. ***/ 875251881Speter 876251881Spetervoid 877251881Spetersvn_cstring_split_append(apr_array_header_t *array, 878251881Speter const char *input, 879251881Speter const char *sep_chars, 880251881Speter svn_boolean_t chop_whitespace, 881251881Speter apr_pool_t *pool) 882251881Speter{ 883251881Speter char *pats; 884251881Speter char *p; 885251881Speter 886251881Speter pats = apr_pstrdup(pool, input); /* strtok wants non-const data */ 887251881Speter p = svn_cstring_tokenize(sep_chars, &pats); 888251881Speter 889251881Speter while (p) 890251881Speter { 891251881Speter if (chop_whitespace) 892251881Speter { 893251881Speter while (svn_ctype_isspace(*p)) 894251881Speter p++; 895251881Speter 896251881Speter { 897251881Speter char *e = p + (strlen(p) - 1); 898251881Speter while ((e >= p) && (svn_ctype_isspace(*e))) 899251881Speter e--; 900251881Speter *(++e) = '\0'; 901251881Speter } 902251881Speter } 903251881Speter 904251881Speter if (p[0] != '\0') 905251881Speter APR_ARRAY_PUSH(array, const char *) = p; 906251881Speter 907251881Speter p = svn_cstring_tokenize(sep_chars, &pats); 908251881Speter } 909251881Speter 910251881Speter return; 911251881Speter} 912251881Speter 913251881Speter 914251881Speterapr_array_header_t * 915251881Spetersvn_cstring_split(const char *input, 916251881Speter const char *sep_chars, 917251881Speter svn_boolean_t chop_whitespace, 918251881Speter apr_pool_t *pool) 919251881Speter{ 920251881Speter apr_array_header_t *a = apr_array_make(pool, 5, sizeof(input)); 921251881Speter svn_cstring_split_append(a, input, sep_chars, chop_whitespace, pool); 922251881Speter return a; 923251881Speter} 924251881Speter 925251881Speter 926251881Spetersvn_boolean_t svn_cstring_match_glob_list(const char *str, 927251881Speter const apr_array_header_t *list) 928251881Speter{ 929251881Speter int i; 930251881Speter 931251881Speter for (i = 0; i < list->nelts; i++) 932251881Speter { 933251881Speter const char *this_pattern = APR_ARRAY_IDX(list, i, char *); 934251881Speter 935251881Speter if (apr_fnmatch(this_pattern, str, 0) == APR_SUCCESS) 936251881Speter return TRUE; 937251881Speter } 938251881Speter 939251881Speter return FALSE; 940251881Speter} 941251881Speter 942251881Spetersvn_boolean_t 943251881Spetersvn_cstring_match_list(const char *str, const apr_array_header_t *list) 944251881Speter{ 945251881Speter int i; 946251881Speter 947251881Speter for (i = 0; i < list->nelts; i++) 948251881Speter { 949251881Speter const char *this_str = APR_ARRAY_IDX(list, i, char *); 950251881Speter 951251881Speter if (strcmp(this_str, str) == 0) 952251881Speter return TRUE; 953251881Speter } 954251881Speter 955251881Speter return FALSE; 956251881Speter} 957251881Speter 958251881Speterchar * 959251881Spetersvn_cstring_tokenize(const char *sep, char **str) 960251881Speter{ 961251881Speter char *token; 962289180Speter char *next; 963251881Speter char csep; 964251881Speter 965251881Speter /* check parameters */ 966251881Speter if ((sep == NULL) || (str == NULL) || (*str == NULL)) 967251881Speter return NULL; 968251881Speter 969251881Speter /* let APR handle edge cases and multiple separators */ 970251881Speter csep = *sep; 971251881Speter if (csep == '\0' || sep[1] != '\0') 972251881Speter return apr_strtok(NULL, sep, str); 973251881Speter 974251881Speter /* skip characters in sep (will terminate at '\0') */ 975251881Speter token = *str; 976251881Speter while (*token == csep) 977251881Speter ++token; 978251881Speter 979251881Speter if (!*token) /* no more tokens */ 980251881Speter return NULL; 981251881Speter 982251881Speter /* skip valid token characters to terminate token and 983251881Speter * prepare for the next call (will terminate at '\0) 984251881Speter */ 985251881Speter next = strchr(token, csep); 986251881Speter if (next == NULL) 987251881Speter { 988251881Speter *str = token + strlen(token); 989251881Speter } 990251881Speter else 991251881Speter { 992289180Speter *next = '\0'; 993289180Speter *str = next + 1; 994251881Speter } 995251881Speter 996251881Speter return token; 997251881Speter} 998251881Speter 999251881Speterint svn_cstring_count_newlines(const char *msg) 1000251881Speter{ 1001251881Speter int count = 0; 1002251881Speter const char *p; 1003251881Speter 1004251881Speter for (p = msg; *p; p++) 1005251881Speter { 1006251881Speter if (*p == '\n') 1007251881Speter { 1008251881Speter count++; 1009251881Speter if (*(p + 1) == '\r') 1010251881Speter p++; 1011251881Speter } 1012251881Speter else if (*p == '\r') 1013251881Speter { 1014251881Speter count++; 1015251881Speter if (*(p + 1) == '\n') 1016251881Speter p++; 1017251881Speter } 1018251881Speter } 1019251881Speter 1020251881Speter return count; 1021251881Speter} 1022251881Speter 1023251881Speterchar * 1024362181Sdimsvn_cstring_join2(const apr_array_header_t *strings, 1025362181Sdim const char *separator, 1026362181Sdim svn_boolean_t trailing_separator, 1027362181Sdim apr_pool_t *pool) 1028251881Speter{ 1029251881Speter svn_stringbuf_t *new_str = svn_stringbuf_create_empty(pool); 1030251881Speter size_t sep_len = strlen(separator); 1031251881Speter int i; 1032251881Speter 1033251881Speter for (i = 0; i < strings->nelts; i++) 1034251881Speter { 1035251881Speter const char *string = APR_ARRAY_IDX(strings, i, const char *); 1036362181Sdim if (i > 0) 1037362181Sdim svn_stringbuf_appendbytes(new_str, separator, sep_len); 1038251881Speter svn_stringbuf_appendbytes(new_str, string, strlen(string)); 1039251881Speter } 1040362181Sdim 1041362181Sdim if (strings->nelts > 0 && trailing_separator) 1042362181Sdim svn_stringbuf_appendbytes(new_str, separator, sep_len); 1043362181Sdim 1044251881Speter return new_str->data; 1045251881Speter} 1046251881Speter 1047251881Speterint 1048251881Spetersvn_cstring_casecmp(const char *str1, const char *str2) 1049251881Speter{ 1050251881Speter for (;;) 1051251881Speter { 1052251881Speter const int a = *str1++; 1053251881Speter const int b = *str2++; 1054251881Speter const int cmp = svn_ctype_casecmp(a, b); 1055251881Speter if (cmp || !a || !b) 1056251881Speter return cmp; 1057251881Speter } 1058251881Speter} 1059251881Speter 1060251881Spetersvn_error_t * 1061251881Spetersvn_cstring_strtoui64(apr_uint64_t *n, const char *str, 1062251881Speter apr_uint64_t minval, apr_uint64_t maxval, 1063251881Speter int base) 1064251881Speter{ 1065251881Speter apr_int64_t val; 1066251881Speter char *endptr; 1067251881Speter 1068251881Speter /* We assume errno is thread-safe. */ 1069251881Speter errno = 0; /* APR-0.9 doesn't always set errno */ 1070251881Speter 1071251881Speter /* ### We're throwing away half the number range here. 1072251881Speter * ### APR needs a apr_strtoui64() function. */ 1073251881Speter val = apr_strtoi64(str, &endptr, base); 1074251881Speter if (errno == EINVAL || endptr == str || str[0] == '\0' || *endptr != '\0') 1075251881Speter return svn_error_createf(SVN_ERR_INCORRECT_PARAMS, NULL, 1076251881Speter _("Could not convert '%s' into a number"), 1077251881Speter str); 1078251881Speter if ((errno == ERANGE && (val == APR_INT64_MIN || val == APR_INT64_MAX)) || 1079251881Speter val < 0 || (apr_uint64_t)val < minval || (apr_uint64_t)val > maxval) 1080251881Speter /* ### Mark this for translation when gettext doesn't choke on macros. */ 1081251881Speter return svn_error_createf(SVN_ERR_INCORRECT_PARAMS, NULL, 1082251881Speter "Number '%s' is out of range " 1083251881Speter "'[%" APR_UINT64_T_FMT ", %" APR_UINT64_T_FMT "]'", 1084251881Speter str, minval, maxval); 1085251881Speter *n = val; 1086251881Speter return SVN_NO_ERROR; 1087251881Speter} 1088251881Speter 1089251881Spetersvn_error_t * 1090251881Spetersvn_cstring_atoui64(apr_uint64_t *n, const char *str) 1091251881Speter{ 1092251881Speter return svn_error_trace(svn_cstring_strtoui64(n, str, 0, 1093251881Speter APR_UINT64_MAX, 10)); 1094251881Speter} 1095251881Speter 1096251881Spetersvn_error_t * 1097251881Spetersvn_cstring_atoui(unsigned int *n, const char *str) 1098251881Speter{ 1099251881Speter apr_uint64_t val; 1100251881Speter 1101251881Speter SVN_ERR(svn_cstring_strtoui64(&val, str, 0, APR_UINT32_MAX, 10)); 1102251881Speter *n = (unsigned int)val; 1103251881Speter return SVN_NO_ERROR; 1104251881Speter} 1105251881Speter 1106251881Spetersvn_error_t * 1107251881Spetersvn_cstring_strtoi64(apr_int64_t *n, const char *str, 1108251881Speter apr_int64_t minval, apr_int64_t maxval, 1109251881Speter int base) 1110251881Speter{ 1111251881Speter apr_int64_t val; 1112251881Speter char *endptr; 1113251881Speter 1114251881Speter /* We assume errno is thread-safe. */ 1115251881Speter errno = 0; /* APR-0.9 doesn't always set errno */ 1116251881Speter 1117251881Speter val = apr_strtoi64(str, &endptr, base); 1118251881Speter if (errno == EINVAL || endptr == str || str[0] == '\0' || *endptr != '\0') 1119251881Speter return svn_error_createf(SVN_ERR_INCORRECT_PARAMS, NULL, 1120251881Speter _("Could not convert '%s' into a number"), 1121251881Speter str); 1122251881Speter if ((errno == ERANGE && (val == APR_INT64_MIN || val == APR_INT64_MAX)) || 1123251881Speter val < minval || val > maxval) 1124251881Speter /* ### Mark this for translation when gettext doesn't choke on macros. */ 1125251881Speter return svn_error_createf(SVN_ERR_INCORRECT_PARAMS, NULL, 1126251881Speter "Number '%s' is out of range " 1127251881Speter "'[%" APR_INT64_T_FMT ", %" APR_INT64_T_FMT "]'", 1128251881Speter str, minval, maxval); 1129251881Speter *n = val; 1130251881Speter return SVN_NO_ERROR; 1131251881Speter} 1132251881Speter 1133251881Spetersvn_error_t * 1134251881Spetersvn_cstring_atoi64(apr_int64_t *n, const char *str) 1135251881Speter{ 1136251881Speter return svn_error_trace(svn_cstring_strtoi64(n, str, APR_INT64_MIN, 1137251881Speter APR_INT64_MAX, 10)); 1138251881Speter} 1139251881Speter 1140251881Spetersvn_error_t * 1141251881Spetersvn_cstring_atoi(int *n, const char *str) 1142251881Speter{ 1143251881Speter apr_int64_t val; 1144251881Speter 1145251881Speter SVN_ERR(svn_cstring_strtoi64(&val, str, APR_INT32_MIN, APR_INT32_MAX, 10)); 1146251881Speter *n = (int)val; 1147251881Speter return SVN_NO_ERROR; 1148251881Speter} 1149251881Speter 1150289180Speterunsigned long 1151289180Spetersvn__strtoul(const char* buffer, const char** end) 1152289180Speter{ 1153289180Speter unsigned long result = 0; 1154251881Speter 1155289180Speter /* this loop will execute in just 2 CPU cycles, confirmed by measurement: 1156289180Speter 7 macro-ops (max 4 / cycle => 2 cycles) 1157289180Speter 1 load (max 1 / cycle) 1158289180Speter 1 jumps (compare + conditional jump == 1 macro op; max 1 / cycle) 1159289180Speter 2 arithmetic ops (subtract, increment; max 3 / cycle) 1160289180Speter 2 scale-and-add AGU ops (max 3 / cycle) 1161289180Speter 1 compiler-generated move operation 1162289180Speter dependency chain: temp = result * 4 + result; result = temp * 2 + c 1163289180Speter (2 ops with latency 1 => 2 cycles) 1164289180Speter */ 1165289180Speter while (1) 1166289180Speter { 1167289180Speter unsigned long c = (unsigned char)*buffer - (unsigned char)'0'; 1168289180Speter if (c > 9) 1169289180Speter break; 1170289180Speter 1171289180Speter result = result * 10 + c; 1172289180Speter ++buffer; 1173289180Speter } 1174289180Speter 1175289180Speter *end = buffer; 1176289180Speter return result; 1177251881Speter} 1178251881Speter 1179251881Speter/* "Precalculated" itoa values for 2 places (including leading zeros). 1180251881Speter * For maximum performance, make sure all table entries are word-aligned. 1181251881Speter */ 1182251881Speterstatic const char decimal_table[100][4] 1183251881Speter = { "00", "01", "02", "03", "04", "05", "06", "07", "08", "09" 1184251881Speter , "10", "11", "12", "13", "14", "15", "16", "17", "18", "19" 1185251881Speter , "20", "21", "22", "23", "24", "25", "26", "27", "28", "29" 1186251881Speter , "30", "31", "32", "33", "34", "35", "36", "37", "38", "39" 1187251881Speter , "40", "41", "42", "43", "44", "45", "46", "47", "48", "49" 1188251881Speter , "50", "51", "52", "53", "54", "55", "56", "57", "58", "59" 1189251881Speter , "60", "61", "62", "63", "64", "65", "66", "67", "68", "69" 1190251881Speter , "70", "71", "72", "73", "74", "75", "76", "77", "78", "79" 1191251881Speter , "80", "81", "82", "83", "84", "85", "86", "87", "88", "89" 1192251881Speter , "90", "91", "92", "93", "94", "95", "96", "97", "98", "99"}; 1193251881Speter 1194251881Speter/* Copy the two bytes at SOURCE[0] and SOURCE[1] to DEST[0] and DEST[1] */ 1195251881Speter#define COPY_TWO_BYTES(dest,source)\ 1196251881Speter memcpy((dest), (source), 2) 1197251881Speter 1198251881Speterapr_size_t 1199251881Spetersvn__ui64toa(char * dest, apr_uint64_t number) 1200251881Speter{ 1201251881Speter char buffer[SVN_INT64_BUFFER_SIZE]; 1202251881Speter apr_uint32_t reduced; /* used for 32 bit DIV */ 1203251881Speter char* target; 1204251881Speter 1205251881Speter /* Small numbers are by far the most common case. 1206251881Speter * Therefore, we use special code. 1207251881Speter */ 1208251881Speter if (number < 100) 1209251881Speter { 1210251881Speter if (number < 10) 1211251881Speter { 1212251881Speter dest[0] = (char)('0' + number); 1213251881Speter dest[1] = 0; 1214251881Speter return 1; 1215251881Speter } 1216251881Speter else 1217251881Speter { 1218251881Speter COPY_TWO_BYTES(dest, decimal_table[(apr_size_t)number]); 1219251881Speter dest[2] = 0; 1220251881Speter return 2; 1221251881Speter } 1222251881Speter } 1223251881Speter 1224251881Speter /* Standard code. Write string in pairs of chars back-to-front */ 1225251881Speter buffer[SVN_INT64_BUFFER_SIZE - 1] = 0; 1226251881Speter target = &buffer[SVN_INT64_BUFFER_SIZE - 3]; 1227251881Speter 1228251881Speter /* Loop may be executed 0 .. 2 times. */ 1229251881Speter while (number >= 100000000) 1230251881Speter { 1231251881Speter /* Number is larger than 100^4, i.e. we can write 4x2 chars. 1232251881Speter * Also, use 32 bit DIVs as these are about twice as fast. 1233251881Speter */ 1234251881Speter reduced = (apr_uint32_t)(number % 100000000); 1235251881Speter number /= 100000000; 1236251881Speter 1237251881Speter COPY_TWO_BYTES(target - 0, decimal_table[reduced % 100]); 1238251881Speter reduced /= 100; 1239251881Speter COPY_TWO_BYTES(target - 2, decimal_table[reduced % 100]); 1240251881Speter reduced /= 100; 1241251881Speter COPY_TWO_BYTES(target - 4, decimal_table[reduced % 100]); 1242251881Speter reduced /= 100; 1243251881Speter COPY_TWO_BYTES(target - 6, decimal_table[reduced % 100]); 1244251881Speter target -= 8; 1245251881Speter } 1246251881Speter 1247251881Speter /* Now, the number fits into 32 bits, but may still be larger than 99 */ 1248251881Speter reduced = (apr_uint32_t)(number); 1249251881Speter while (reduced >= 100) 1250251881Speter { 1251251881Speter COPY_TWO_BYTES(target, decimal_table[reduced % 100]); 1252251881Speter reduced /= 100; 1253251881Speter target -= 2; 1254251881Speter } 1255251881Speter 1256251881Speter /* The number is now smaller than 100 but larger than 1 */ 1257251881Speter COPY_TWO_BYTES(target, decimal_table[reduced]); 1258251881Speter 1259251881Speter /* Correction for uneven count of places. */ 1260251881Speter if (reduced < 10) 1261251881Speter ++target; 1262251881Speter 1263251881Speter /* Copy to target */ 1264251881Speter memcpy(dest, target, &buffer[SVN_INT64_BUFFER_SIZE] - target); 1265251881Speter return &buffer[SVN_INT64_BUFFER_SIZE] - target - 1; 1266251881Speter} 1267251881Speter 1268251881Speterapr_size_t 1269251881Spetersvn__i64toa(char * dest, apr_int64_t number) 1270251881Speter{ 1271251881Speter if (number >= 0) 1272251881Speter return svn__ui64toa(dest, (apr_uint64_t)number); 1273251881Speter 1274251881Speter *dest = '-'; 1275289180Speter return svn__ui64toa(dest + 1, 0 - (apr_uint64_t)number) + 1; 1276251881Speter} 1277251881Speter 1278251881Speterstatic void 1279289180Speterui64toa_sep(apr_uint64_t number, char separator, char *buffer) 1280251881Speter{ 1281251881Speter apr_size_t length = svn__ui64toa(buffer, number); 1282251881Speter apr_size_t i; 1283251881Speter 1284251881Speter for (i = length; i > 3; i -= 3) 1285251881Speter { 1286251881Speter memmove(&buffer[i - 2], &buffer[i - 3], length - i + 3); 1287289180Speter buffer[i-3] = separator; 1288251881Speter length++; 1289251881Speter } 1290251881Speter 1291251881Speter buffer[length] = 0; 1292251881Speter} 1293251881Speter 1294251881Speterchar * 1295289180Spetersvn__ui64toa_sep(apr_uint64_t number, char separator, apr_pool_t *pool) 1296251881Speter{ 1297251881Speter char buffer[2 * SVN_INT64_BUFFER_SIZE]; 1298289180Speter ui64toa_sep(number, separator, buffer); 1299251881Speter 1300251881Speter return apr_pstrdup(pool, buffer); 1301251881Speter} 1302251881Speter 1303251881Speterchar * 1304289180Spetersvn__i64toa_sep(apr_int64_t number, char separator, apr_pool_t *pool) 1305251881Speter{ 1306251881Speter char buffer[2 * SVN_INT64_BUFFER_SIZE]; 1307251881Speter if (number < 0) 1308251881Speter { 1309251881Speter buffer[0] = '-'; 1310289180Speter ui64toa_sep((apr_uint64_t)(-number), separator, &buffer[1]); 1311251881Speter } 1312251881Speter else 1313289180Speter ui64toa_sep((apr_uint64_t)(number), separator, buffer); 1314251881Speter 1315251881Speter return apr_pstrdup(pool, buffer); 1316251881Speter} 1317251881Speter 1318289180Speterapr_size_t 1319289180Spetersvn__ui64tobase36(char *dest, apr_uint64_t value) 1320289180Speter{ 1321289180Speter char *dest_start = dest; 1322289180Speter if (value < 10) 1323289180Speter { 1324289180Speter /* pretty frequent and trivial case. Make it fast. */ 1325289180Speter *(dest++) = (char)(value) + '0'; 1326289180Speter } 1327289180Speter else 1328289180Speter { 1329289180Speter char buffer[SVN_INT64_BUFFER_SIZE]; 1330289180Speter char *p = buffer; 1331289180Speter 1332289180Speter /* write result as little-endian to buffer */ 1333289180Speter while (value > 0) 1334289180Speter { 1335289180Speter char c = (char)(value % 36); 1336289180Speter value /= 36; 1337289180Speter 1338289180Speter *p = (c <= 9) ? (c + '0') : (c - 10 + 'a'); 1339289180Speter ++p; 1340289180Speter } 1341289180Speter 1342289180Speter /* copy as big-endian to DEST */ 1343289180Speter while (p > buffer) 1344289180Speter *(dest++) = *(--p); 1345289180Speter } 1346289180Speter 1347289180Speter *dest = '\0'; 1348289180Speter return dest - dest_start; 1349289180Speter} 1350289180Speter 1351289180Speterapr_uint64_t 1352289180Spetersvn__base36toui64(const char **next, const char *source) 1353289180Speter{ 1354289180Speter apr_uint64_t result = 0; 1355289180Speter apr_uint64_t factor = 1; 1356289180Speter int i = 0; 1357289180Speter char digits[SVN_INT64_BUFFER_SIZE]; 1358289180Speter 1359289180Speter /* convert digits to numerical values and count the number of places. 1360289180Speter * Also, prevent buffer overflow. */ 1361289180Speter while (i < sizeof(digits)) 1362289180Speter { 1363289180Speter char c = *source; 1364289180Speter if (c < 'a') 1365289180Speter { 1366289180Speter /* includes detection of NUL terminator */ 1367289180Speter if (c < '0' || c > '9') 1368289180Speter break; 1369289180Speter 1370289180Speter c -= '0'; 1371289180Speter } 1372289180Speter else 1373289180Speter { 1374289180Speter if (c < 'a' || c > 'z') 1375289180Speter break; 1376289180Speter 1377289180Speter c -= 'a' - 10; 1378289180Speter } 1379289180Speter 1380289180Speter digits[i++] = c; 1381289180Speter source++; 1382289180Speter } 1383289180Speter 1384289180Speter /* fold digits into the result */ 1385289180Speter while (i > 0) 1386289180Speter { 1387289180Speter result += factor * (apr_uint64_t)digits[--i]; 1388289180Speter factor *= 36; 1389289180Speter } 1390289180Speter 1391289180Speter if (next) 1392289180Speter *next = source; 1393289180Speter 1394289180Speter return result; 1395289180Speter} 1396289180Speter 1397289180Speter 1398289180Speterapr_size_t 1399251881Spetersvn_cstring__similarity(const char *stra, const char *strb, 1400251881Speter svn_membuf_t *buffer, apr_size_t *rlcs) 1401251881Speter{ 1402251881Speter svn_string_t stringa, stringb; 1403251881Speter stringa.data = stra; 1404251881Speter stringa.len = strlen(stra); 1405251881Speter stringb.data = strb; 1406251881Speter stringb.len = strlen(strb); 1407251881Speter return svn_string__similarity(&stringa, &stringb, buffer, rlcs); 1408251881Speter} 1409251881Speter 1410289180Speterapr_size_t 1411251881Spetersvn_string__similarity(const svn_string_t *stringa, 1412251881Speter const svn_string_t *stringb, 1413251881Speter svn_membuf_t *buffer, apr_size_t *rlcs) 1414251881Speter{ 1415251881Speter const char *stra = stringa->data; 1416251881Speter const char *strb = stringb->data; 1417251881Speter const apr_size_t lena = stringa->len; 1418251881Speter const apr_size_t lenb = stringb->len; 1419251881Speter const apr_size_t total = lena + lenb; 1420251881Speter const char *enda = stra + lena; 1421251881Speter const char *endb = strb + lenb; 1422251881Speter apr_size_t lcs = 0; 1423251881Speter 1424251881Speter /* Skip the common prefix ... */ 1425251881Speter while (stra < enda && strb < endb && *stra == *strb) 1426251881Speter { 1427251881Speter ++stra; ++strb; 1428251881Speter ++lcs; 1429251881Speter } 1430251881Speter 1431251881Speter /* ... and the common suffix */ 1432251881Speter while (stra < enda && strb < endb) 1433251881Speter { 1434251881Speter --enda; --endb; 1435251881Speter if (*enda != *endb) 1436251881Speter { 1437251881Speter ++enda; ++endb; 1438251881Speter break; 1439251881Speter } 1440251881Speter 1441251881Speter ++lcs; 1442251881Speter } 1443251881Speter 1444251881Speter if (stra < enda && strb < endb) 1445251881Speter { 1446251881Speter const apr_size_t resta = enda - stra; 1447251881Speter const apr_size_t restb = endb - strb; 1448251881Speter const apr_size_t slots = (resta > restb ? restb : resta); 1449251881Speter apr_size_t *curr, *prev; 1450251881Speter const char *pstr; 1451251881Speter 1452251881Speter /* The outer loop must iterate on the longer string. */ 1453251881Speter if (resta < restb) 1454251881Speter { 1455251881Speter pstr = stra; 1456251881Speter stra = strb; 1457251881Speter strb = pstr; 1458251881Speter 1459251881Speter pstr = enda; 1460251881Speter enda = endb; 1461251881Speter endb = pstr; 1462251881Speter } 1463251881Speter 1464251881Speter /* Allocate two columns in the LCS matrix 1465251881Speter ### Optimize this to (slots + 2) instesd of 2 * (slots + 1) */ 1466251881Speter svn_membuf__ensure(buffer, 2 * (slots + 1) * sizeof(apr_size_t)); 1467251881Speter svn_membuf__nzero(buffer, (slots + 2) * sizeof(apr_size_t)); 1468251881Speter prev = buffer->data; 1469251881Speter curr = prev + slots + 1; 1470251881Speter 1471251881Speter /* Calculate LCS length of the remainder */ 1472251881Speter for (pstr = stra; pstr < enda; ++pstr) 1473251881Speter { 1474289180Speter apr_size_t i; 1475251881Speter for (i = 1; i <= slots; ++i) 1476251881Speter { 1477251881Speter if (*pstr == strb[i-1]) 1478251881Speter curr[i] = prev[i-1] + 1; 1479251881Speter else 1480251881Speter curr[i] = (curr[i-1] > prev[i] ? curr[i-1] : prev[i]); 1481251881Speter } 1482251881Speter 1483251881Speter /* Swap the buffers, making the previous one current */ 1484251881Speter { 1485251881Speter apr_size_t *const temp = prev; 1486251881Speter prev = curr; 1487251881Speter curr = temp; 1488251881Speter } 1489251881Speter } 1490251881Speter 1491251881Speter lcs += prev[slots]; 1492251881Speter } 1493251881Speter 1494251881Speter if (rlcs) 1495251881Speter *rlcs = lcs; 1496251881Speter 1497251881Speter /* Return similarity ratio rounded to 4 significant digits */ 1498251881Speter if (total) 1499289180Speter return ((2 * SVN_STRING__SIM_RANGE_MAX * lcs + total/2) / total); 1500251881Speter else 1501289180Speter return SVN_STRING__SIM_RANGE_MAX; 1502251881Speter} 1503289180Speter 1504289180Speterapr_size_t 1505289180Spetersvn_cstring__match_length(const char *a, 1506289180Speter const char *b, 1507289180Speter apr_size_t max_len) 1508289180Speter{ 1509289180Speter apr_size_t pos = 0; 1510289180Speter 1511289180Speter#if SVN_UNALIGNED_ACCESS_IS_OK 1512289180Speter 1513289180Speter /* Chunky processing is so much faster ... 1514289180Speter * 1515289180Speter * We can't make this work on architectures that require aligned access 1516289180Speter * because A and B will probably have different alignment. So, skipping 1517289180Speter * the first few chars until alignment is reached is not an option. 1518289180Speter */ 1519362181Sdim for (; max_len - pos >= sizeof(apr_size_t); pos += sizeof(apr_size_t)) 1520289180Speter if (*(const apr_size_t*)(a + pos) != *(const apr_size_t*)(b + pos)) 1521289180Speter break; 1522289180Speter 1523289180Speter#endif 1524289180Speter 1525289180Speter for (; pos < max_len; ++pos) 1526289180Speter if (a[pos] != b[pos]) 1527289180Speter break; 1528289180Speter 1529289180Speter return pos; 1530289180Speter} 1531289180Speter 1532289180Speterapr_size_t 1533289180Spetersvn_cstring__reverse_match_length(const char *a, 1534289180Speter const char *b, 1535289180Speter apr_size_t max_len) 1536289180Speter{ 1537289180Speter apr_size_t pos = 0; 1538289180Speter 1539289180Speter#if SVN_UNALIGNED_ACCESS_IS_OK 1540289180Speter 1541289180Speter /* Chunky processing is so much faster ... 1542289180Speter * 1543289180Speter * We can't make this work on architectures that require aligned access 1544289180Speter * because A and B will probably have different alignment. So, skipping 1545289180Speter * the first few chars until alignment is reached is not an option. 1546289180Speter */ 1547289180Speter for (pos = sizeof(apr_size_t); pos <= max_len; pos += sizeof(apr_size_t)) 1548289180Speter if (*(const apr_size_t*)(a - pos) != *(const apr_size_t*)(b - pos)) 1549289180Speter break; 1550289180Speter 1551289180Speter pos -= sizeof(apr_size_t); 1552289180Speter 1553289180Speter#endif 1554289180Speter 1555289180Speter /* If we find a mismatch at -pos, pos-1 characters matched. 1556289180Speter */ 1557289180Speter while (++pos <= max_len) 1558289180Speter if (a[0-pos] != b[0-pos]) 1559289180Speter return pos - 1; 1560289180Speter 1561289180Speter /* No mismatch found -> at least MAX_LEN matching chars. 1562289180Speter */ 1563289180Speter return max_len; 1564289180Speter} 1565289180Speter 1566289180Speterconst char * 1567289180Spetersvn_cstring_skip_prefix(const char *str, const char *prefix) 1568289180Speter{ 1569289180Speter apr_size_t len = strlen(prefix); 1570289180Speter 1571289180Speter if (strncmp(str, prefix, len) == 0) 1572289180Speter { 1573289180Speter return str + len; 1574289180Speter } 1575289180Speter else 1576289180Speter { 1577289180Speter return NULL; 1578289180Speter } 1579289180Speter} 1580