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