include/private/svn_string_private.h

/**
 * @copyright
 * ====================================================================
 *    Licensed to the Apache Software Foundation (ASF) under one
 *    or more contributor license agreements.  See the NOTICE file
 *    distributed with this work for additional information
 *    regarding copyright ownership.  The ASF licenses this file
 *    to you under the Apache License, Version 2.0 (the
 *    "License"); you may not use this file except in compliance
 *    with the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing,
 *    software distributed under the License is distributed on an
 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *    KIND, either express or implied.  See the License for the
 *    specific language governing permissions and limitations
 *    under the License.
 * ====================================================================
 * @endcopyright
 *
 * @file svn_string_private.h
 * @brief Non-public string utility functions.
 */


#ifndef SVN_STRING_PRIVATE_H
#define SVN_STRING_PRIVATE_H

#include "svn_string.h"    /* for svn_boolean_t, svn_error_t */

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

/**
 * @defgroup svn_string String handling
 * @{
 */


/** Private functions.
 *
 * @defgroup svn_string_private Private functions
 * @{
 */


/** A self-contained memory buffer of known size.
 *
 * Intended to be used where a single variable-sized buffer is needed
 * within an iteration, a scratch pool is available and we want to
 * avoid the cost of creating another pool just for the iteration.
 */
typedef struct svn_membuf_t
{
  /** The a pool from which this buffer was originally allocated, and is not
   * necessarily specific to this buffer.  This is used only for allocating
   * more memory from when the buffer needs to grow.
   */
  apr_pool_t *pool;

  /** pointer to the memory */
  void *data;

  /** total size of buffer allocated */
  apr_size_t size;
} svn_membuf_t;


/* Initialize a memory buffer of the given size */
void
svn_membuf__create(svn_membuf_t *membuf, apr_size_t size, apr_pool_t *pool);

/* Ensure that the given memory buffer has at least the given size */
void
svn_membuf__ensure(svn_membuf_t *membuf, apr_size_t size);

/* Resize the given memory buffer, preserving its contents. */
void
svn_membuf__resize(svn_membuf_t *membuf, apr_size_t size);

/* Zero-fill the given memory */
void
svn_membuf__zero(svn_membuf_t *membuf);

/* Zero-fill the given memory buffer up to the smaller of SIZE and the
   current buffer size. */
void
svn_membuf__nzero(svn_membuf_t *membuf, apr_size_t size);

/* Inline implementation of svn_membuf__zero.
 * Note that PMEMBUF is evaluated only once.
 */
#define SVN_MEMBUF__ZERO(pmembuf)                \
  do                                             \
    {                                            \
      svn_membuf_t *const _m_b_f_ = (pmembuf);   \
      memset(_m_b_f_->data, 0, _m_b_f_->size);   \
    }                                            \
  while(0)

/* Inline implementation of svn_membuf__nzero
 * Note that PMEMBUF and PSIZE are evaluated only once.
 */
#define SVN_MEMBUF__NZERO(pmembuf, psize)        \
  do                                             \
    {                                            \
      svn_membuf_t *const _m_b_f_ = (pmembuf);   \
      const apr_size_t _s_z_ = (psize);          \
      if (_s_z_ > _m_b_f_->size)                 \
        memset(_m_b_f_->data, 0, _m_b_f_->size); \
      else                                       \
        memset(_m_b_f_->data, 0, _s_z_);         \
    }                                            \
  while(0)

#ifndef SVN_DEBUG
/* In non-debug mode, just use these inlie replacements */
#define svn_membuf__zero(B) SVN_MEMBUF__ZERO((B))
#define svn_membuf__nzero(B, S) SVN_MEMBUF__NZERO((B), (S))
#endif


/** Returns the #svn_string_t information contained in the data and
 * len members of @a strbuf. This is effectively a typecast, converting
 * @a strbuf into an #svn_string_t. This first will become invalid and must
 * not be accessed after this function returned.
 */
svn_string_t *
svn_stringbuf__morph_into_string(svn_stringbuf_t *strbuf);

/** Utility macro to define static svn_string_t objects.  @a value must
 * be a static string; the "" in the macro declaration tries to ensure this.
 *
 * Usage:
 * static const svn_string_t my_string = SVN__STATIC_STRING("my text");
 */
#define SVN__STATIC_STRING(value) { value "", sizeof(value "") - 1 }

/** Like strtoul but with a fixed base of 10 and without overflow checks.
 * This allows the compiler to generate massively faster (4x on 64bit LINUX)
 * code.  Overflow checks may be added on the caller side where you might
 * want to test for a more specific value range anyway.
 */
unsigned long
svn__strtoul(const char *buffer, const char **end);

/** Number of chars needed to represent signed (19 places + sign + NUL) or
 * unsigned (20 places + NUL) integers as strings.
 */
#define SVN_INT64_BUFFER_SIZE 21

/** Writes the @a number as string into @a dest. The latter must provide
 * space for at least #SVN_INT64_BUFFER_SIZE characters. Returns the number
 * chars written excluding the terminating NUL.
 */
apr_size_t
svn__ui64toa(char * dest, apr_uint64_t number);

/** Writes the @a number as string into @a dest. The latter must provide
 * space for at least #SVN_INT64_BUFFER_SIZE characters. Returns the number
 * chars written excluding the terminating NUL.
 */
apr_size_t
svn__i64toa(char * dest, apr_int64_t number);

/** Returns a decimal string for @a number allocated in @a pool.  Put in
 * the @a separator at each third place.
 */
char *
svn__ui64toa_sep(apr_uint64_t number, char separator, apr_pool_t *pool);

/** Returns a decimal string for @a number allocated in @a pool.  Put in
 * the @a separator at each third place.
 */
char *
svn__i64toa_sep(apr_int64_t number, char separator, apr_pool_t *pool);


/** Writes the @a number as base36-encoded string into @a dest. The latter
 * must provide space for at least #SVN_INT64_BUFFER_SIZE characters.
 * Returns the number chars written excluding the terminating NUL.
 *
 * @note The actual maximum buffer requirement is much shorter than
 * #SVN_INT64_BUFFER_SIZE but introducing yet another constant is only
 * marginally useful and may open the door to security issues when e.g.
 * switching between base10 and base36 encoding.
 */
apr_size_t
svn__ui64tobase36(char *dest, apr_uint64_t number);

/** Returns the value of the base36 encoded unsigned integer starting at
 * @a source.  If @a next is not NULL, @a *next will be set to the first
 * position after the integer.
 *
 * The data in @a source will be considered part of the number to parse
 * as long as the characters are within the base36 range.  If there are
 * no such characters to begin with, 0 is returned.  Inputs with more than
 * #SVN_INT64_BUFFER_SIZE digits will not be fully parsed, i.e. the value
 * of @a *next as well as the return value are undefined.
 */
apr_uint64_t
svn__base36toui64(const char **next, const char *source);

/**
 * The upper limit of the similarity range returned by
 * svn_cstring__similarity() and svn_string__similarity().
 */
#define SVN_STRING__SIM_RANGE_MAX 1000000

/**
 * Computes the similarity score of STRA and STRB. Returns the ratio
 * of the length of their longest common subsequence and the average
 * length of the strings, normalized to the range
 * [0..SVN_STRING__SIM_RANGE_MAX]. The result is equivalent to
 * Python's
 *
 *   difflib.SequenceMatcher.ratio
 *
 * Optionally sets *RLCS to the length of the longest common
 * subsequence of STRA and STRB. Using BUFFER for temporary storage,
 * requires memory proportional to the length of the shorter string.
 *
 * The LCS algorithm used is described in, e.g.,
 *
 *   http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
 *
 * Q: Why another LCS when we already have one in libsvn_diff?
 * A: svn_diff__lcs is too heavyweight and too generic for the
 *    purposes of similarity testing. Whilst it would be possible
 *    to use a character-based tokenizer with it, we really only need
 *    the *length* of the LCS for the similarity score, not all the
 *    other information that svn_diff__lcs produces in order to
 *    make printing diffs possible.
 *
 * Q: Is there a limit on the length of the string parameters?
 * A: Only available memory. But note that the LCS algorithm used
 *    has O(strlen(STRA) * strlen(STRB)) worst-case performance,
 *    so do keep a rein on your enthusiasm.
 */
apr_size_t
svn_cstring__similarity(const char *stra, const char *strb,
                        svn_membuf_t *buffer, apr_size_t *rlcs);

/**
 * Like svn_cstring__similarity, but accepts svn_string_t's instead
 * of NUL-terminated character strings.
 */
apr_size_t
svn_string__similarity(const svn_string_t *stringa,
                       const svn_string_t *stringb,
                       svn_membuf_t *buffer, apr_size_t *rlcs);


/* Return the lowest position at which A and B differ. If no difference
 * can be found in the first MAX_LEN characters, MAX_LEN will be returned.
 */
apr_size_t
svn_cstring__match_length(const char *a,
                          const char *b,
                          apr_size_t max_len);

/* Return the number of bytes before A and B that don't differ.  If no
 * difference can be found in the first MAX_LEN characters,  MAX_LEN will
 * be returned.  Please note that A-MAX_LEN and B-MAX_LEN must both be
 * valid addresses.
 */
apr_size_t
svn_cstring__reverse_match_length(const char *a,
                                  const char *b,
                                  apr_size_t max_len);

/** @} */

/** Prefix trees.
 *
 * Prefix trees allow for a space-efficient representation of a set of path-
 * like strings, i.e. those that share common prefixes.  Any given string
 * value will be stored only once, i.e. two strings stored in the same tree
 * are equal if and only if the point to the same #svn_prefix_string__t.
 *
 * @defgroup svn_prefix_string Strings in prefix trees.
* @{
 */

/**
 * Opaque data type for prefix-tree-based strings.
 */
typedef struct svn_prefix_string__t svn_prefix_string__t;

/**
 * Opaque data type representing a prefix tree
 */
typedef struct svn_prefix_tree__t svn_prefix_tree__t;

/**
 * Return a new prefix tree allocated in @a pool.
 */
svn_prefix_tree__t *
svn_prefix_tree__create(apr_pool_t *pool);

/**
 * Return a string with the value @a s stored in @a tree.  If no such string
 * exists yet, add it automatically.
 */
svn_prefix_string__t *
svn_prefix_string__create(svn_prefix_tree__t *tree,
                          const char *s);

/**
 * Return the contents of @a s as a new string object allocated in @a pool.
 */
svn_string_t *
svn_prefix_string__expand(const svn_prefix_string__t *s,
                          apr_pool_t *pool);

/**
 * Compare the two strings @a lhs and @a rhs that must be part of the same
 * tree.
 */
int
svn_prefix_string__compare(const svn_prefix_string__t *lhs,
                           const svn_prefix_string__t *rhs);

/** @} */

/** @} */


#ifdef __cplusplus
}
#endif /* __cplusplus */

#endif  /* SVN_STRING_PRIVATE_H */