/* products derived from this software without specific prior written */
/* permission. */
/* */
-/* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND */
-/* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE */
-/* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */
-/* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS */
-/* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR */
-/* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF */
-/* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS */
-/* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN */
-/* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) */
-/* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF */
-/* THE POSSIBILITY OF SUCH DAMAGE. */
+/* THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS ``AS IS'' AND ANY EXPRESS */
+/* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */
+/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */
+/* DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY */
+/* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL */
+/* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS */
+/* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) */
+/* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, */
+/* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN */
+/* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE */
+/* POSSIBILITY OF SUCH DAMAGE. */
+/* */
+/* Copyright (c) 2006-2008 the Authors */
+/* see AUTHORS and source files for details */
/******************************************************************************/
/*
#define TRIE_ENTRY_INIT { 0, 0, 0, 0 }
ARRAY(trie_entry_t)
+#define str(trie, entry) array_ptr((trie)->c, (entry)->c_offset)
+#define key(trie, id) array_ptr((trie)->keys, array_elt((trie)->keys_offset, (id)))
+
struct trie_t {
A(trie_entry_t) entries;
A(char) c;
const trie_entry_t *entry,
const char *key)
{
- const char *c = array_ptr(trie->c, entry->c_offset);
+ const char *c = str(trie, entry);
int i = 0;
for (i = 0 ; i < entry->c_len ; ++i) {
if (key[i] != c[i]) {
static inline bool trie_entry_match(const trie_t *trie,
const trie_entry_t *entry, const char *key)
{
- return !!(strcmp(array_ptr(trie->c, entry->c_offset), key) == 0);
+ return !!(strcmp(str(trie, entry), key) == 0);
}
static inline bool trie_entry_prefix(const trie_t *trie,
const trie_entry_t *entry, const char *key)
{
int len = entry->c_len;
- if (len > 0 && array_elt(trie->c, entry->c_offset + len - 1) == '\0') {
+ if (len > 0 && str(trie, entry)[len -1] == '\0') {
--len;
}
- return !!(strncmp(array_ptr(trie->c, entry->c_offset), key, len) == 0);
+ return !!(strncmp(str(trie, entry), key, len) == 0);
}
static inline bool trie_entry_is_leaf(const trie_entry_t *entry)
while (start < end) {
uint32_t mid = (start + end) >> 1;
const trie_entry_t* child = array_ptr(trie->entries, mid);
- const char c2 = array_elt(trie->c, child->c_offset);
+ const char c2 = str(trie, child)[0];
if (c2 == c) {
- return child;
+ return child;
}
if (c < c2) {
- end = mid;
+ end = mid;
} else {
- start = mid + 1;
+ start = mid + 1;
}
}
return NULL;
static inline void trie_compile_aux(trie_t *trie, uint32_t id,
uint32_t first_key, uint32_t last_key,
- int offset)
+ int offset, int initial_diff)
{
uint32_t forks[256];
uint32_t fork_pos = 0;
char current = '\0';
#ifdef CHECK_INTEGRITY
- assert(strcmp(array_ptr(trie->keys, array_elt(trie->keys_offset, first_key) + offset),
- array_ptr(trie->c, array_elt(trie->entries, id).c_offset)) == 0);
+ assert(strcmp(key(trie, first_key) + offset, str(trie, entry)) == 0);
#endif
- for (int off_diff = 0 ; fork_pos == 0 ; ++off_diff, ++offset) {
- current = array_elt(trie->keys, array_elt(trie->keys_offset, first_key) + offset);
+ for (int off_diff = initial_diff ; fork_pos == 0 ; ++off_diff, ++offset) {
+ current = key(trie, first_key)[offset];
for (uint32_t i = first_key + 1 ; i < last_key ; ++i) {
- const char *str = array_ptr(trie->keys, array_elt(trie->keys_offset, i));
- const char c = str[offset];
+ const char *ckey = key(trie, i) + offset;
+ const char c = *ckey;
if (c != current) {
array_ensure_capacity_delta(trie->entries, 2);
if (fork_pos == 0) {
trie_entry_split(trie, id, off_diff);
}
- trie_entry_insert_child(trie, id, trie_add_leaf(trie, str + offset));
+ trie_entry_insert_child(trie, id, trie_add_leaf(trie, ckey));
forks[fork_pos++] = i;
current = c;
}
for (uint16_t i = 0 ; i < children_len ; ++i) {
int child = array_elt(trie->entries, id).children_offset + i;
if (forks[i] - 1 > first_key) {
- trie_compile_aux(trie, child, first_key, forks[i], offset - 1);
+ trie_compile_aux(trie, child, first_key, forks[i], offset, 1);
}
first_key = forks[i];
}
}
array_ensure_capacity(trie->entries, trie->keys_offset.len);
- trie_compile_aux(trie, trie_add_leaf(trie, array_ptr(trie->keys, array_elt(trie->keys_offset, 0))),
- 0, trie->keys_offset.len, 0);
+ trie_compile_aux(trie, trie_add_leaf(trie, key(trie, 0)),
+ 0, trie->keys_offset.len, 0, 0);
trie_cleanup_build_data(trie);
array_adjust(trie->entries);
array_adjust(trie->c);
if (entry->c_len == 0) {
fputs("(0)", stdout);
} else {
- const char *c = array_ptr(trie->c, entry->c_offset);
+ const char *c = str(trie, entry);
printf("(%d) ", entry->c_len);
for (int i = 0 ; i < entry->c_len ; ++i) {
if (c[i]) {
}
fputs("\n", stdout);
}
- for (uint32_t i = entry->children_offset ;
- i < entry->children_offset + entry->children_len ; ++i) {
- trie_entry_inspect(trie, show_content, array_ptr(trie->entries, i), level + 1);
+ for (uint32_t i = 0 ; i < entry->children_len ; ++i) {
+ trie_entry_inspect(trie, show_content,
+ array_ptr(trie->entries, entry->children_offset + i),
+ level + 1);
}
if (level == 0) {
printf("Average char per node: %d\n", trie->c.len / trie->entries.len);
projects / apps / pfixtools.git / blobdiff