File Manager

003 File Manager

Current Path: /usr/src/contrib/subversion/subversion/libsvn_subr

usr / src / contrib / subversion / subversion / libsvn_subr /

📁 ..
📄 adler32.c(3.16 KB)
📄 atomic.c(7.23 KB)
📄 auth.c(32.4 KB)
📄 auth.h(6.1 KB)
📄 base64.c(19.18 KB)
📄 bit_array.c(6.26 KB)
📄 cache-inprocess.c(21.2 KB)
📄 cache-membuffer.c(116.43 KB)
📄 cache-memcache.c(17.35 KB)
📄 cache-null.c(4.35 KB)
📄 cache.c(10.22 KB)
📄 cache.h(4.03 KB)
📄 cache_config.c(6.01 KB)
📄 checksum.c(24.17 KB)
📄 checksum.h(2.32 KB)
📄 cmdline.c(58.99 KB)
📄 compat.c(5.28 KB)
📄 compress_lz4.c(4.51 KB)
📄 compress_zlib.c(6.85 KB)
📄 config.c(39.66 KB)
📄 config_auth.c(8.65 KB)
📄 config_file.c(70.25 KB)
📄 config_impl.h(6.15 KB)
📄 config_keys.inc(2.65 KB)
📄 config_win.c(9.61 KB)
📄 crypto.c(25.19 KB)
📄 crypto.h(5.43 KB)
📄 ctype.c(13.81 KB)
📄 date.c(12.86 KB)
📄 debug.c(3.77 KB)
📄 deprecated.c(64.3 KB)
📄 dirent_uri.c(80.17 KB)
📄 dirent_uri.h(1.43 KB)
📄 dso.c(3.74 KB)
📄 encode.c(2.69 KB)
📄 eol.c(2.79 KB)
📄 error.c(24.52 KB)
📄 errorcode.inc(4.27 KB)
📄 fnv1a.c(6.92 KB)
📄 fnv1a.h(3.04 KB)
📄 genctype.py(3.84 KB)
📄 gpg_agent.c(22.29 KB)
📄 hash.c(19.59 KB)
📄 internal_statements.h(1.87 KB)
📄 internal_statements.sql(1.58 KB)
📄 io.c(182.6 KB)
📄 iter.c(3.84 KB)
📄 libsvn_subr.pc.in(515 B)
📄 lock.c(1.69 KB)
📄 log.c(14 KB)
📁 lz4
📄 macos_keychain.c(9.7 KB)
📄 magic.c(5.25 KB)
📄 md5.c(1.8 KB)
📄 mergeinfo.c(89.24 KB)
📄 mutex.c(3.06 KB)
📄 nls.c(3.06 KB)
📄 object_pool.c(9.76 KB)
📄 opt.c(39.34 KB)
📄 opt.h(1.89 KB)
📄 packed_data.c(33.43 KB)
📄 path.c(35.99 KB)
📄 pool.c(4.35 KB)
📄 pools.h(1.45 KB)
📄 prefix_string.c(10.65 KB)
📄 prompt.c(28.82 KB)
📄 properties.c(13.59 KB)
📄 quoprint.c(8.96 KB)
📄 root_pools.c(3.15 KB)
📄 simple_providers.c(25.54 KB)
📄 skel.c(23.04 KB)
📄 sorts.c(15.9 KB)
📄 spillbuf.c(19.78 KB)
📄 sqlite.c(49.68 KB)
📄 sqlite3wrapper.c(3.16 KB)
📄 ssl_client_cert_providers.c(6.66 KB)
📄 ssl_client_cert_pw_providers.c(18.93 KB)
📄 ssl_server_trust_providers.c(7.77 KB)
📄 stream.c(65.69 KB)
📄 string.c(40.2 KB)
📄 subst.c(67.57 KB)
📄 sysinfo.c(43.67 KB)
📄 sysinfo.h(2.58 KB)
📄 target.c(11.58 KB)
📄 temp_serializer.c(14.02 KB)
📄 time.c(9.08 KB)
📄 token.c(2.58 KB)
📄 types.c(9.43 KB)
📄 user.c(2.66 KB)
📄 username_providers.c(9.2 KB)
📄 utf.c(40.38 KB)
📁 utf8proc
📄 utf8proc.c(20.71 KB)
📄 utf_validate.c(13.3 KB)
📄 utf_width.c(10.85 KB)
📄 validate.c(3.35 KB)
📄 version.c(9.89 KB)
📄 win32_crashrpt.c(25.06 KB)
📄 win32_crashrpt.h(1.35 KB)
📄 win32_crashrpt_dll.h(4 KB)
📄 win32_crypto.c(18.12 KB)
📄 win32_xlate.c(7.3 KB)
📄 win32_xlate.h(2.11 KB)
📄 x509.h(3.75 KB)
📄 x509info.c(9.53 KB)
📄 x509parse.c(35.77 KB)
📄 xml.c(20.01 KB)

Editing: prefix_string.c

/* prefix_string.c --- implement strings based on a prefix tree
 *
 * ====================================================================
 *    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.
 * ====================================================================
 */

#include <assert.h>
#include "private/svn_string_private.h"

/* A node in the tree represents a common prefix.  The root node is the
 * empty prefix.  Nodes may have up to 256 sub-nodes, each starting with
 * a different character (possibly '\0').
 *
 * The nodes in the tree store only up to 8 chars of the respective common
 * prefix, i.e. longer common prefixes must be drawn out over multiple
 * hierarchy levels.  This is a space <-> efficiency trade-off.
 *
 * Strings are the leaf nodes in the tree and use a specialized, smaller
 * data structure.  They may add 0 to 7 extra chars to the prefix.  Both
 * data types can be discerned by the last char in the data buffer.  This
 * must be 0 for strings (leaves) and non-0 otherwise.  Please note that
 * ordinary nodes have a length information so that no terminating 0 is
 * required for them.
 */

/* forward declaration */
typedef struct node_t node_t;

/* String type and tree leaf.
 */
struct svn_prefix_string__t
{
  /* mandatory prefix */
  node_t *prefix;

/* 0 ..7 chars to add the prefix.
   *
   * NUL-terminated, if this is indeed a tree leaf.  We use the same struct
   * within node_t for inner tree nodes, too.  There, DATA[7] is not NUL,
   * meaning DATA may or may not be NUL terminated.  The actual length is
   * provided by the node_t.length field (minus parent node length). */
  char data[8];
};

/* A node inside the tree, i.e. not a string and not a leaf (unless this is
 * the root node).
 *
 * Note: keep the ordering to minimize size / alignment overhead on 64 bit
 * machines.
 */
struct node_t
{
  /* pointer to the parent prefix plus the 1 .. 8 extra chars.
   * Only the root will provide 0 extra chars. */
  svn_prefix_string__t key;

/* Length of the prefix from the root down to and including this one.
   * 0 for the root node.  Only then will key.prefix be NULL. */
  apr_uint32_t length;

/* Number of entries used in SUB_NODES. */
  apr_uint32_t sub_node_count;

/* The sub-nodes, ordered by first char.  node_t and svn_prefix_string__t
   * may be mixed here.  May be NULL.
   * The number of allocated entries is always a power-of-two and only
   * given implicitly by SUB_NODE_COUNT. */
  struct node_t **sub_nodes;
};

/* The actual tree structure. */
struct svn_prefix_tree__t
{
  /* the common tree root (represents the empty prefix). */
  node_t *root;

/* all sub-nodes & strings will be allocated from this pool */
  apr_pool_t *pool;
};

/* Return TRUE, iff NODE is a leaf node.
 */
static svn_boolean_t
is_leaf(node_t *node)
{
  /* If this NOT a leaf node and this node has ...
   *    ... 8 chars, data[7] will not be NUL because we only support
   *        NUL-*terminated* strings.
   *    ... less than 8 chars, this will be set to 0xff
   *        (any other non-NUL would do as well but this is not valid UTF8
   *         making it easy to recognize during debugging etc.) */
  return node->key.data[7] == 0;
}

/* Ensure that the sub-nodes array of NODE within TREE has at least one
 * unused entry.  Re-allocate as necessary.
 */
static void
auto_realloc_sub_nodes(svn_prefix_tree__t *tree,
                       node_t *node)
{
  if (node->sub_node_count & (node->sub_node_count - 1))
    return;

if (node->sub_node_count == 0)
    {
      node->sub_nodes = apr_pcalloc(tree->pool, sizeof(*node->sub_nodes));
    }
  else
    {
      node_t **sub_nodes
        = apr_pcalloc(tree->pool,
                      2 * node->sub_node_count * sizeof(*sub_nodes));
      memcpy(sub_nodes, node->sub_nodes,
             node->sub_node_count * sizeof(*sub_nodes));
      node->sub_nodes = sub_nodes;
    }
}

/* Given the COUNT pointers in the SUB_NODES array, return the location at
 * which KEY is either located or would be inserted.
 */
static int
search_lower_bound(node_t **sub_nodes,
                   unsigned char key,
                   int count)
{
  int lower = 0;
  int upper = count - 1;

/* Binary search for the lowest position at which to insert KEY. */
  while (lower <= upper)
    {
      int current = lower + (upper - lower) / 2;

if ((unsigned char)sub_nodes[current]->key.data[0] < key)
        lower = current + 1;
      else
        upper = current - 1;
    }

return lower;
}

svn_prefix_tree__t *
svn_prefix_tree__create(apr_pool_t *pool)
{
  svn_prefix_tree__t *tree = apr_pcalloc(pool, sizeof(*tree));
  tree->pool = pool;

tree->root = apr_pcalloc(pool, sizeof(*tree->root));
  tree->root->key.data[7] = '\xff'; /* This is not a leaf. See is_leaf(). */

return tree;
}

svn_prefix_string__t *
svn_prefix_string__create(svn_prefix_tree__t *tree,
                          const char *s)
{
  svn_prefix_string__t *new_string;
  apr_size_t len = strlen(s);
  node_t *node = tree->root;
  node_t *new_node;
  int idx;

/* walk the existing tree until we either find S or the node at which S
   * has to be inserted */
  while (TRUE)
    {
      node_t *sub_node;
      int match = 1;

/* index of the matching sub-node */
      idx = node->sub_node_count
          ? search_lower_bound(node->sub_nodes,
                               (unsigned char)s[node->length],
                               node->sub_node_count)
          : 0;

/* any (partially) matching sub-nodes? */
      if (idx == (int)node->sub_node_count
          || node->sub_nodes[idx]->key.data[0] != s[node->length])
        break;

/* Yes, it matches - at least the first character does. */
      sub_node = node->sub_nodes[idx];

/* fully matching sub-node? */
      if (is_leaf(sub_node))
        {
          if (strcmp(sub_node->key.data, s + node->length) == 0)
            return &sub_node->key;
        }
      else
        {
          /* The string formed by the path from the root down to
           * SUB_NODE differs from S.
           *
           * Is it a prefix?  In that case, the chars added by SUB_NODE
           * must fully match the respective chars in S. */
          apr_size_t sub_node_len = sub_node->length - node->length;
          if (strncmp(sub_node->key.data, s + node->length,
                      sub_node_len) == 0)
            {
              node = sub_node;
              continue;
            }
        }

/* partial match -> split
       *
       * At this point, S may either be a prefix to the string represented
       * by SUB_NODE, or they may diverge at some offset with
       * SUB_NODE->KEY.DATA .
       *
       * MATCH starts with 1 here b/c we already know that at least one
       * char matches.  Also, the loop will terminate because the strings
       * differ before SUB_NODE->KEY.DATA - either at the NUL terminator
       * of S or some char before that.
       */
      while (sub_node->key.data[match] == s[node->length + match])
        ++match;

new_node = apr_pcalloc(tree->pool, sizeof(*new_node));
      new_node->key = sub_node->key;
      new_node->length = node->length + match;
      new_node->key.data[7] = '\xff';  /* This is not a leaf. See is_leaf(). */
      new_node->sub_node_count = 1;
      new_node->sub_nodes = apr_palloc(tree->pool, sizeof(node_t *));
      new_node->sub_nodes[0] = sub_node;

memmove(sub_node->key.data, sub_node->key.data + match, 8 - match);

/* replace old sub-node with new one and continue lookup */
      sub_node->key.prefix = new_node;
      node->sub_nodes[idx] = new_node;
      node = new_node;
    }

/* add sub-node(s) and final string */
  while (len - node->length > 7)
    {
      new_node = apr_pcalloc(tree->pool, sizeof(*new_node));
      new_node->key.prefix = node;
      new_node->length = node->length + 8;
      memcpy(new_node->key.data, s + node->length, 8);

auto_realloc_sub_nodes(tree, node);
      memmove(node->sub_nodes + idx + 1, node->sub_nodes + idx,
              (node->sub_node_count - idx) * sizeof(node_t *));

/* replace old sub-node with new one and continue lookup */
      node->sub_nodes[idx] = new_node;
      node->sub_node_count++;
      node = new_node;
      idx = 0;
    }

new_string = apr_pcalloc(tree->pool, sizeof(*new_string));
  new_string->prefix = node;
  memcpy(new_string->data, s + node->length, len - node->length);

auto_realloc_sub_nodes(tree, node);
  memmove(node->sub_nodes + idx + 1, node->sub_nodes + idx,
          (node->sub_node_count - idx) * sizeof(node_t *));

node->sub_nodes[idx] = (node_t *)new_string;
  node->sub_node_count++;
  return new_string;
}

svn_string_t *
svn_prefix_string__expand(const svn_prefix_string__t *s,
                          apr_pool_t *pool)
{
  apr_size_t s_len = strlen(s->data);
  apr_size_t len = s->prefix->length + s_len;
  char *buffer = apr_palloc(pool, len + 1);

svn_string_t *result = apr_pcalloc(pool, sizeof(*result));
  result->data = buffer;
  result->len = len;
  buffer[len] = '\0';

while (s->prefix)
    {
      memcpy(buffer + s->prefix->length, s->data, len - s->prefix->length);
      len = s->prefix->length;
      s = &s->prefix->key;
    }

return result;
}

int
svn_prefix_string__compare(const svn_prefix_string__t *lhs,
                           const svn_prefix_string__t *rhs)
{
  const node_t *lhs_parent = lhs->prefix;
  const node_t *rhs_parent = rhs->prefix;

if (lhs == rhs)
    return 0;

/* find the common root */
  while (lhs_parent != rhs_parent)
    {
      if (lhs_parent->length <= rhs_parent->length)
        {
          rhs = &rhs_parent->key;
          rhs_parent = rhs_parent->key.prefix;
        }
      else if (rhs_parent->length <= lhs_parent->length)
        {
          lhs = &lhs_parent->key;
          lhs_parent = lhs_parent->key.prefix;
        }

/* same tree? */
      assert(lhs_parent && rhs_parent);
    }

/* at the common root, strings will differ in the first follow-up char */
  return (int)(unsigned char)lhs->data[0] - (int)(unsigned char)rhs->data[0];
}

003 File Manager

Editing: prefix_string.c

Upload File

Create Folder