subversion/libsvn_subr/prefix_string.c - subversion - Git at Google

 /* 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 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];
 }
	/* 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 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];
	}