[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[bug-recutils] [PATCH 03/13] src,torture: imple ment index tree scans.
|
From: |
Michał Masłowski |
|
Subject: |
[bug-recutils] [PATCH 03/13] src,torture: imple ment index tree scans. |
|
Date: |
Mon, 20 Aug 2012 18:21:24 +0200 |
---
ChangeLog | 25 ++
src/rec-idx-tree.c | 491 ++++++++++++++++++++++++++++-
src/rec.h | 28 ++
torture/Makefile.am | 1 +
torture/rec-idx-tree/rec-idx-tree-scan.c | 196 ++++++++++++
torture/rec-idx-tree/tsuite-rec-idx-tree.c | 2 +
6 files changed, 740 insertions(+), 3 deletions(-)
create mode 100644 torture/rec-idx-tree/rec-idx-tree-scan.c
diff --git a/ChangeLog b/ChangeLog
index d401c5d..93012af 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,28 @@
+2012-08-12 Michał Masłowski <address@hidden>
+
+ src,torture: implement index tree scans.
+ * src/rec-idx-tree.c (struct rec_idx_tree_s): New fields parser,
+ rset and root.
+ (struct rec_idx_tree_iterator_s): New structure.
+ (REC_IDX_TREE_NONFIRST_MASK): New constant.
+ (rec_idx_tree_new): Initialize the new fields.
+ (rec_idx_tree_set_rset): New function.
+ (rec_idx_tree_scan): Likewise.
+ (rec_idx_tree_scan_interval): Likewise.
+ (rec_idx_tree_scan_common): Likewise.
+ (rec_idx_tree_get_depth): Likewise.
+ (rec_idx_tree_skip_and_compare_key): Likewise.
+ (rec_idx_tree_iter_next): Likewise.
+ (rec_idx_tree_iter_dispose): Likewise.
+ * src/rec.h: Add prototypes for rec_idx_tree_set_rset,
+ rec_idx_tree_scan and rec_idx_tree_scan_interval.
+
+ * torture/Makefile.am (REC_IDX_TREE_TSUITE): Add
+ rec-idx-tree-scan.c.
+ * torture/rec-idx-tree/rec-idx-tree-scan.c: New file.
+ * torture/rec-idx-tree/tsuite-rec-idx-tree.c: Add
+ test_rec_idx_tree_scan.
+
2012-08-08 Michał Masłowski <address@hidden>
src,torture: implement initial index tree support without nodes.
diff --git a/src/rec-idx-tree.c b/src/rec-idx-tree.c
index 3d92bf7..f106082 100644
--- a/src/rec-idx-tree.c
+++ b/src/rec-idx-tree.c
@@ -43,6 +43,26 @@ struct rec_idx_tree_s
const uint8_t *end; /* first byte after it */
const char **names; /* array of key field names */
rec_idx_tree_key_t *types; /* array of key field types */
+ rec_parser_t parser; /* parser for records */
+ rec_rset_t rset; /* rset for records */
+ const uint8_t *root; /* start of the root node */
+};
+
+/* Internal object storing record iterator state. */
+
+struct rec_idx_tree_iterator_s
+{
+ rec_idx_tree_t tree;
+ rec_record_t record; /* previous one, to be freed later */
+ const uint8_t *next; /* next key in the node */
+ const uint8_t *end; /* root must be less than this */
+ size_t line; /* next record position */
+ size_t character;
+ const void **right; /* maximum comparison key to iterate */
+ size_t right_ind; /* highest index to iterate */
+ int n_entries; /* number of entries in the node */
+ bool first_only;
+ bool is_end;
};
/* Type of the basic tree index. */
@@ -57,8 +77,51 @@ struct rec_idx_tree_header_s
};
/* Then a sequence of uint8_t type and null-terminated name follow.
- After them is padding to eight octets just before the first
- node. */
+ After them is padding to eight octets just before the root node.
+
+ A B+tree variant with variable number of keys in a node is used.
+
+ This is the nonleaf node format:
+ - uint64_t number of entries
+ - uint64_t offset in the index tree of the subtree for the first
+ key
+ - uint64_t number of first records (i.e. ones mapped from a key
+ based only on the first value for each field name, as used for
+ sorting and interval searches) in that subtree
+ - the lowest key for the second subtree (a sequence of values of
+ format depending on their type, i.e. null-terminated strings for
+ REC_IDX_KEY_STRING)
+ - padding to eight octets
+ - offsets, numbers of first records, keys and padding for following
+ entries (no key is stated after the numbers for the last
+ subtree).
+
+ Each subtree has higher lowest key than the highest key in the
+ preceding subtree.
+
+ This is the leaf node format:
+ - uint64_t number of entries
+ - uint64_t line number of the record to which the key is mapped,
+ with highest bit set if this is not a first record as defined
+ above
+ - uint64_t character offset of the record
+ - key for which the preceding numbers are stated
+ - padding to eight octets
+ - line, character numbers, keys and padding for following entries
+ - uint64_t offset of the next leaf or 0 if this is the last one.
+
+ Keys in a node are sorted in order depending on their types.
+*/
+
+#define REC_IDX_TREE_NONFIRST_MASK INT64_C(0x8000000000000000)
+
+/* Static functions defined in this file. */
+
+static rec_iter_t rec_idx_tree_scan_common (rec_idx_tree_t idx_tree, const
void **left, const void **right, size_t left_ind, size_t right_ind, bool
first_only);
+static size_t rec_idx_tree_get_depth (rec_idx_tree_t idx_tree);
+static int rec_idx_tree_skip_and_compare_key (rec_idx_tree_t tree, const
uint8_t **in_tree, const void **given);
+static bool rec_idx_tree_iter_next (void *data, rec_record_t *record);
+static void rec_idx_tree_iter_dispose (void *data);
/*
* Public functions.
@@ -95,6 +158,8 @@ rec_idx_tree_new (const uint8_t *bytes,
/* Set basic fields and allocate the per-field arrays. */
res->buffer = bytes;
res->end = bytes + size;
+ res->parser = NULL;
+ res->rset = NULL;
n_fields = rec_idx_tree_get_num_fields (res);
res->names = malloc (sizeof (res->names[0]) * n_fields);
@@ -119,7 +184,7 @@ rec_idx_tree_new (const uint8_t *bytes,
while ((next_byte != NULL)
&& (next_byte < res->end - 2) && (current_field < n_fields))
{
- next_byte++;
+ next_byte++; /* skip '\0' */
res->types[current_field] = *next_byte;
if (res->types[current_field] > REC_IDX_KEY_STRING)
@@ -141,10 +206,28 @@ rec_idx_tree_new (const uint8_t *bytes,
return NULL;
}
+ next_byte++; /* skip '\0' */
+
+ /* Save the start of the root node after padding. */
+ if ((next_byte - bytes) % 8)
+ {
+ next_byte += 8 - (next_byte - bytes) % 8;
+ }
+ res->root = next_byte;
+
return res;
}
void
+rec_idx_tree_set_rset (rec_idx_tree_t idx_tree,
+ rec_parser_t parser,
+ rec_rset_t rset)
+{
+ idx_tree->parser = parser;
+ idx_tree->rset = rset;
+}
+
+void
rec_idx_tree_destroy (rec_idx_tree_t idx_tree)
{
free (idx_tree->names);
@@ -180,4 +263,406 @@ rec_idx_tree_get_field_type (rec_idx_tree_t idx_tree,
size_t n)
return idx_tree->types[n];
}
+rec_iter_t
+rec_idx_tree_scan (rec_idx_tree_t idx_tree,
+ const void **left, const void **right)
+{
+ return rec_idx_tree_scan_common (idx_tree, left, right, 0, SIZE_MAX, false);
+}
+
+rec_iter_t
+rec_idx_tree_scan_interval (rec_idx_tree_t idx_tree, size_t left, size_t right)
+{
+ return rec_idx_tree_scan_common (idx_tree, NULL, NULL, left, right, true);
+}
+
+/*
+ * Private functions.
+ */
+
+static rec_iter_t
+rec_idx_tree_scan_common (rec_idx_tree_t idx_tree,
+ const void **left, const void **right,
+ size_t left_ind, size_t right_ind, bool first_only)
+{
+ size_t depth;
+ const uint8_t *root;
+ const uint64_t *node;
+ int n_entries, comparison;
+ size_t child, size, character, line;
+ bool empty;
+ struct rec_idx_tree_iterator_s *iter_state;
+ rec_iter_t iterator;
+
+ root = idx_tree->root;
+ depth = rec_idx_tree_get_depth (idx_tree);
+
+ /* Traverse the tree downward until finding the first possibly
+ useful leaf. */
+ while (depth > 0)
+ {
+ depth--;
+
+ if ((root >= idx_tree->end)
+ || (root < idx_tree->root))
+ {
+ return NULL; /* Invalid node position. */
+ }
+
+ node = (const uint64_t*) root;
+ n_entries = (int) node[0];
+ node++;
+ empty = true;
+
+ while (n_entries > 0)
+ {
+ n_entries--;
+
+ if (root + sizeof (node[0]) * 2 >= idx_tree->end)
+ {
+ return NULL; /* truncated index */
+ }
+
+ child = (size_t) node[0]; /* offset of subtree */
+ size = (size_t) node[1];
+ root = (const uint8_t*) &node[2]; /* skip to key */
+
+ /* Compare the key if there is one. */
+ if (n_entries > 0)
+ {
+ comparison = rec_idx_tree_skip_and_compare_key (idx_tree,
+ &root, left);
+ if (!root)
+ {
+ return NULL; /* truncated index */
+ }
+ }
+ else
+ {
+ comparison = 1; /* don't skip the last tree */
+ }
+
+ /* Check if we should skip the tree. */
+ if ((comparison <= 0) || (left_ind >= size))
+ {
+ if (left_ind >= size)
+ {
+ left_ind -= size;
+ }
+ else
+ {
+ left_ind = 0;
+ }
+ right_ind -= size;
+ continue;
+ }
+ else if (comparison > 0)
+ {
+ /* If a record is found, it's in this subtree. */
+ empty = false;
+ root = idx_tree->buffer + child;
+ }
+ break;
+ }
+
+ if (empty)
+ {
+ /* Skipped the whole tree. */
+ return rec_iter_new (NULL, NULL, NULL);
+ }
+ }
+
+ if (root + sizeof (node[0]) > idx_tree->end)
+ {
+ return NULL; /* truncated index */
+ }
+
+ /* Now root points to the beginning of a leaf node which must
+ contain the first record position we want to iterate, unless the
+ output is empty (assuming correct code and index). So find the
+ first element >= left and make an iterator starting the work
+ there. */
+ node = (const uint64_t *) root;
+ n_entries = node[0];
+ root = (const uint8_t*) &node[1];
+
+ while (n_entries > 0)
+ {
+ n_entries--;
+
+ if (root + sizeof(node[0]) * 2 > idx_tree->end)
+ {
+ return NULL; /* truncated index */
+ }
+
+ node = (const uint64_t *) root;
+ line = (size_t) node[0];
+ character = (size_t) node[1];
+ root = (const uint8_t *) &node[2];
+ comparison = rec_idx_tree_skip_and_compare_key (idx_tree, &root, left);
+ if (!root)
+ {
+ return NULL; /* truncated index */
+ }
+
+ if ((comparison < 0) || (left_ind > 0)
+ || ((line & REC_IDX_TREE_NONFIRST_MASK) && first_only))
+ {
+ /* Skip the record, it has too small key or index. */
+ left_ind--;
+ right_ind--;
+ continue;
+ }
+
+ /* We could have parsed the last entry of the node. In that
+ case go to the start of the next one so the iterator always
+ starts at a leaf node entry. */
+ if (n_entries == 0)
+ {
+ node = (const uint64_t*) root;
+
+ if (node[0] != 0)
+ {
+ root = idx_tree->buffer + node[0];
+ if (root + sizeof (node[0]) > idx_tree->end)
+ {
+ return NULL; /* truncated index */
+ }
+
+ n_entries = node[1];
+ root = (const uint8_t*) &node[2];
+ }
+ else
+ {
+ /* We found the last record of the tree, not looking
+ further. */
+ root = NULL;
+ }
+ }
+
+ /* Prepare the iterator. */
+ iter_state = malloc (sizeof (*iter_state));
+ if (!iter_state)
+ {
+ return NULL;
+ }
+
+ iterator = rec_iter_new (iter_state, rec_idx_tree_iter_next,
+ rec_idx_tree_iter_dispose);
+ if (!iterator)
+ {
+ free (iter_state);
+ return NULL;
+ }
+
+ iter_state->tree = idx_tree;
+ iter_state->record = NULL;
+ iter_state->next = root;
+ iter_state->end = idx_tree->end;
+ iter_state->line = line;
+ iter_state->character = character;
+ iter_state->right = right;
+ iter_state->right_ind = right_ind;
+ iter_state->n_entries = n_entries;
+ iter_state->first_only = first_only;
+ iter_state->is_end = (root == NULL);
+ return iterator;
+ }
+ return rec_iter_new (NULL, NULL, NULL); /* no records found */
+}
+
+static size_t
+rec_idx_tree_get_depth (rec_idx_tree_t idx_tree)
+{
+ struct rec_idx_tree_header_s *header =
+ (struct rec_idx_tree_header_s *) idx_tree->buffer;
+ return (size_t) header->depth;
+}
+
+/* Return a negative, zero or positive value if *in_tree is less,
+ equal or greater than specified in given. Advance *in_tree after
+ the whole key, or set it to NULL if the index is known to be
+ invalid. Pass NULL as given to just advance *in_tree. */
+
+static int
+rec_idx_tree_skip_and_compare_key (rec_idx_tree_t tree,
+ const uint8_t **in_tree, const void **given)
+{
+ size_t n_fields, n, limit;
+ int comparison = 0;
+
+ n_fields = rec_idx_tree_get_num_fields (tree);
+ for (n = 0; n < n_fields; n++)
+ {
+ limit = tree->end - *in_tree; /* maximal key size */
+ switch (tree->types[n])
+ {
+ case REC_IDX_KEY_NONE:
+ /* Does not occur. */
+ break;
+ case REC_IDX_KEY_STRING:
+ if ((comparison == 0) && (given[n] != NULL))
+ {
+ comparison = strncmp ((const char *) *in_tree,
+ (const char *) (given[n]), limit);
+ }
+
+ *in_tree = memchr (*in_tree, '\0', limit);
+ if (in_tree == NULL)
+ {
+ return comparison;
+ }
+
+ (*in_tree)++;
+ break;
+ }
+ }
+
+ /* Skip padding after the key. */
+ if ((*in_tree - tree->buffer) % 8)
+ {
+ *in_tree += 8 - (*in_tree - tree->buffer) % 8;
+ }
+ return comparison;
+}
+
+static bool
+rec_idx_tree_iter_next (void *data, rec_record_t *record)
+{
+ struct rec_idx_tree_iterator_s *iter =
+ (struct rec_idx_tree_iterator_s *) data;
+ uint64_t line_field;
+ const uint64_t *node;
+ int comparison;
+
+ /* Destroy the previous record. */
+ if (iter->record)
+ {
+ rec_record_destroy (iter->record);
+ iter->record = NULL;
+ }
+
+ if (iter->is_end)
+ {
+ return false;
+ }
+
+ /* Update the count of records iterated. */
+ if (iter->right_ind == 0)
+ {
+ iter->is_end = true;
+ }
+ else
+ {
+ iter->right_ind--;
+ }
+
+ /* Parse the current record. */
+ if (!rec_parser_seek (iter->tree->parser, iter->line, iter->character)
+ || !rec_parse_record (iter->tree->parser, &(iter->record)))
+ {
+ /* Error. */
+ *record = NULL;
+ return false;
+ }
+
+ rec_record_set_container (iter->record, iter->tree->rset);
+
+ if (iter->next == NULL)
+ {
+ iter->is_end = true;
+ }
+ else
+ {
+ /* Find the next record. */
+ while (iter->n_entries > 0)
+ {
+ iter->n_entries--;
+
+ if (iter->next + sizeof (node[0]) * 2 > iter->end)
+ {
+ /* Truncated index. */
+ *record = NULL;
+ return false;
+ }
+
+ node = (const uint64_t*) iter->next;
+ line_field = node[0];
+ iter->line = (size_t) (line_field & ~REC_IDX_TREE_NONFIRST_MASK);
+ iter->character = (size_t) node[1];
+ iter->next = (const uint8_t*) &node[2];
+ comparison = rec_idx_tree_skip_and_compare_key (iter->tree,
+ &(iter->next),
+ iter->right);
+
+ if (!iter->next)
+ {
+ *record = NULL;
+ return false;
+ }
+
+ if (comparison > 0)
+ {
+ iter->is_end = true;
+ }
+
+ if (iter->n_entries == 0)
+ {
+ /* Go to the next node. */
+ if (iter->next + sizeof (node[0]) > iter->end)
+ {
+ *record = NULL;
+ return false;
+ }
+
+ node = (const uint64_t *) iter->next;
+
+ if (node[0] == INT64_C(0))
+ {
+ /* This is a different condition than iter->is_end:
+ there is only one next record. */
+ iter->next = NULL;
+ }
+ else
+ {
+ iter->next = iter->tree->buffer + node[0];
+ if (iter->next + sizeof (node[0]) > iter->end)
+ {
+ *record = NULL;
+ return false;
+ }
+
+ node = (const uint64_t *) iter->next;
+ iter->n_entries = (size_t) node[0];
+ iter->next += sizeof (node[0]);
+ }
+
+ }
+
+ if (!((line_field & REC_IDX_TREE_NONFIRST_MASK) && iter->first_only))
+ {
+ /* We won't skip the record just found. */
+ break;
+ }
+ }
+ }
+
+ *record = iter->record;
+ return true;
+}
+
+static void
+rec_idx_tree_iter_dispose (void *data)
+{
+ struct rec_idx_tree_iterator_s *iter =
+ (struct rec_idx_tree_iterator_s *) data;
+
+ if (iter->record)
+ {
+ rec_record_destroy (iter->record);
+ }
+
+ free (iter);
+}
+
/* End of rec-idx-tree.c */
diff --git a/src/rec.h b/src/rec.h
index 980bf56..548e439 100644
--- a/src/rec.h
+++ b/src/rec.h
@@ -2480,6 +2480,12 @@ typedef enum rec_idx_tree_key_e rec_idx_tree_key_t;
rec_idx_tree_t rec_idx_tree_new (const uint8_t *bytes, int64_t type, size_t
size);
+/* Set rset and parser used by the index tree. Records found by
+ searches will be parsed by the given parser and considered elements
+ of the specified rset. */
+
+void rec_idx_tree_set_rset (rec_idx_tree_t idx_tree, rec_parser_t parser,
rec_rset_t rset);
+
/* Destroy an index tree object. */
void rec_idx_tree_destroy (rec_idx_tree_t idx_tree);
@@ -2504,6 +2510,28 @@ const char *rec_idx_tree_get_field_name (rec_idx_tree_t
idx_tree, size_t n);
rec_idx_tree_key_t rec_idx_tree_get_field_type (rec_idx_tree_t idx_tree,
size_t n);
+/**************** Searching index trees ******************************/
+
+/* Return an iterator over all records in the index mapped from keys
+ between (inclusive) left and right. Records mapped from multiple
+ keys in the specified range will be duplicated.
+
+ The left and right arguments are arrays of size equal to the key
+ type length containing values of key fields of representations
+ depending on their types. For REC_IDX_KEY_STRING fields the value
+ is a const char * pointing to the field value.
+
+ NULL is returned on error.
+*/
+
+rec_iter_t rec_idx_tree_scan (rec_idx_tree_t idx_tree, const void **left,
const void **right);
+
+/* Return an interator over records having indices in the tree in the
+ interval of [left, right]. Only the first occurrence of each
+ record in the tree might be used. NULL is returned on error. */
+
+rec_iter_t rec_idx_tree_scan_interval (rec_idx_tree_t idx_tree, size_t left,
size_t right);
+
#endif /* !GNU_REC_H */
/* End of rec.h */
diff --git a/torture/Makefile.am b/torture/Makefile.am
index 0ac2d86..38d9e6d 100644
--- a/torture/Makefile.am
+++ b/torture/Makefile.am
@@ -148,6 +148,7 @@ REC_ITER_TSUITE = rec-iter/rec-iter-mset.c \
rec-iter/tsuite-rec-iter.c
REC_IDX_TREE_TSUITE = rec-idx-tree/rec-idx-tree-new.c \
+ rec-idx-tree/rec-idx-tree-scan.c \
rec-idx-tree/tsuite-rec-idx-tree.c
runtests_SOURCES = runtests.c \
diff --git a/torture/rec-idx-tree/rec-idx-tree-scan.c
b/torture/rec-idx-tree/rec-idx-tree-scan.c
new file mode 100644
index 0000000..108b746
--- /dev/null
+++ b/torture/rec-idx-tree/rec-idx-tree-scan.c
@@ -0,0 +1,196 @@
+/* -*- mode: C -*-
+ *
+ * File: rec-idx-tree-scan.c
+ * Date: Thu Aug 9 20:24:08 2012
+ *
+ * GNU recutils - rec_idx_tree_scan unit tests.
+ *
+ */
+
+/* Copyright (C) 2012 Michał Masłowski */
+
+/* This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <check.h>
+
+#include <rec.h>
+
+/* Header and key description for a simple index tree. */
+static const uint8_t sample_header[] =
+ {
+ 1 /* second rset */, 0 /* only leaf node */,
+ 2 /* two fields in the key */,
+ 1 /* string */, 'f', 'o', 'o', '\0',
+ 1 /* string */, 'b', 'a', 'r', '\0',
+ 0, 0, 0 /* padding */
+ };
+
+/*-
+ * Test: rec_idx_tree_scan_one_node
+ * Unit: rec_idx_tree_scan
+ * Description:
+ * + Iterate records from a single-node tree.
+ */
+START_TEST(rec_idx_tree_scan_one_node)
+{
+ rec_idx_tree_t tree;
+ uint8_t buffer[1024];
+ uint64_t *node;
+ rec_rset_t rset;
+ rec_parser_t parser;
+ rec_iter_t iter;
+ rec_record_t record;
+ /* This isn't related to the keys in the index and is shorter. */
+ static const char recfile[] = "a: 1\n\na: 2\n\na: 3\n";
+ static const char* left[] = {"abc", "def"};
+ static const char* right[] = {"bcd", "efg"};
+
+ memcpy (buffer, sample_header, sizeof (sample_header));
+ rset = rec_rset_new ();
+ fail_if (!rset);
+ parser = rec_parser_new_str (recfile, "dummy");
+ fail_if (!parser);
+
+ /* Prepare the node. */
+ node = (uint64_t *) &buffer[sizeof (sample_header)];
+ node[0] = 3; /* number of entries */
+ node[1] = 1; /* line */
+ node[2] = 0; /* character */
+ memcpy (node + 3, "abc\0def\0", 8); /* key field values */
+ node[4] = 3;
+ node[5] = 6;
+ memcpy (node + 6, "bcd\0ef\0\0", 8);
+ node[7] = 5;
+ node[8] = 12;
+ memcpy (node + 9, "cde\0fgh\0", 8);
+ node[10] = 0; /* next node */
+
+ /* Open the tree. */
+ tree = rec_idx_tree_new (buffer, 1 /* the type */, sizeof(buffer));
+ fail_if (!tree);
+ rec_idx_tree_set_rset (tree, parser, rset);
+ iter = rec_idx_tree_scan (tree, (const void **) left, (const void **) right);
+ fail_if (!iter);
+
+ /* Read the records. */
+ fail_if (!rec_iter_next (iter, &record));
+ fail_if (!rec_record_contains_field (record, "a", "1"));
+ fail_if (!rec_iter_next (iter, &record));
+ fail_if (!rec_record_contains_field (record, "a", "2"));
+ fail_if (rec_iter_next (iter, &record));
+
+ /* Close. */
+ rec_iter_destroy (iter);
+ rec_idx_tree_destroy (tree);
+ rec_parser_destroy (parser);
+ rec_rset_destroy (rset);
+}
+END_TEST
+
+/*-
+ * Test: rec_idx_tree_scan_tree
+ * Unit: rec_idx_tree_scan
+ * Description:
+ * + Iterate a record from a tree having a nonleaf node.
+ */
+START_TEST(rec_idx_tree_scan_tree)
+{
+ rec_idx_tree_t tree;
+ uint8_t buffer[1024];
+ uint64_t *node;
+ rec_rset_t rset;
+ rec_parser_t parser;
+ rec_iter_t iter;
+ rec_record_t record;
+ /* This isn't related to the keys in the index and is shorter. */
+ static const char recfile[] = "a: 1\n\na: 2\n\na: 3\n";
+ static const char* left[] = {"abc", "def"};
+ static const char* right[] = {"bcd", "efg"};
+
+ memcpy (buffer, sample_header, sizeof (sample_header));
+ buffer[1] = 1; /* depth */
+ rset = rec_rset_new ();
+ fail_if (!rset);
+ parser = rec_parser_new_str (recfile, "dummy");
+ fail_if (!parser);
+
+ /* Prepare tree nodes, one root and two non-root. */
+ /* root */
+ node = (uint64_t *) &buffer[sizeof (sample_header)];
+ node[0] = 2; /* number of entries */
+ /* offset of the first child */
+ node[1] = sizeof (sample_header) + sizeof (uint64_t) * 6;
+ node[2] = 1; /* number of first records */
+ memcpy (node + 3, "bcd\0ef\0\0", 8); /* key field values */
+ /* offset of the second child */
+ node[4] = sizeof (sample_header) + sizeof (uint64_t) * 11;
+ node[5] = 2; /* number of first records */
+ /* first child */
+ node[6] = 1; /* number of entries */
+ node[7] = 1; /* line */
+ node[8] = 0; /* character */
+ memcpy (node + 9, "abc\0def\0", 8); /* key field values */
+ node[10] = sizeof (sample_header) + sizeof (uint64_t) * 11; /* next node */
+ /* second child */
+ node[11] = 2;
+ node[12] = 3;
+ node[13] = 6;
+ memcpy (node + 14, "bcd\0ef\0\0", 8);
+ node[15] = 5;
+ node[16] = 12;
+ memcpy (node + 17, "cde\0fgh\0", 8);
+ node[18] = 0; /* next node */
+
+ /* Open the tree. */
+ tree = rec_idx_tree_new (buffer, 1 /* the type */, sizeof(buffer));
+ fail_if (!tree);
+ rec_idx_tree_set_rset (tree, parser, rset);
+ iter = rec_idx_tree_scan (tree, (const void **) left, (const void **) right);
+ fail_if (!iter);
+
+ /* Read the records. */
+ fail_if (!rec_iter_next (iter, &record));
+ fail_if (!rec_record_contains_field (record, "a", "1"));
+ fail_if (!rec_iter_next (iter, &record));
+ fail_if (!rec_record_contains_field (record, "a", "2"));
+ fail_if (rec_iter_next (iter, &record));
+
+ /* Close. */
+ rec_iter_destroy (iter);
+ rec_idx_tree_destroy (tree);
+ rec_parser_destroy (parser);
+ rec_rset_destroy (rset);
+}
+END_TEST
+
+/*
+ * Test creation function
+ */
+TCase *
+test_rec_idx_tree_scan (void)
+{
+ TCase *tc = tcase_create ("rec_idx_tree_scan");
+ tcase_add_test (tc, rec_idx_tree_scan_one_node);
+ tcase_add_test (tc, rec_idx_tree_scan_tree);
+
+ return tc;
+}
+
+/* End of rec-idx-tree-scan.c */
diff --git a/torture/rec-idx-tree/tsuite-rec-idx-tree.c
b/torture/rec-idx-tree/tsuite-rec-idx-tree.c
index aae8873..0ea6d45 100644
--- a/torture/rec-idx-tree/tsuite-rec-idx-tree.c
+++ b/torture/rec-idx-tree/tsuite-rec-idx-tree.c
@@ -27,6 +27,7 @@
#include <check.h>
extern TCase *test_rec_idx_tree_new (void);
+extern TCase *test_rec_idx_tree_scan (void);
Suite *
tsuite_rec_idx_tree ()
@@ -35,6 +36,7 @@ tsuite_rec_idx_tree ()
s = suite_create ("rec-idx-tree");
suite_add_tcase (s, test_rec_idx_tree_new ());
+ suite_add_tcase (s, test_rec_idx_tree_scan ());
return s;
}
--
1.7.11.4
- [bug-recutils] [PATCH 06/13] utils,doc: make re cfix --build-index add index trees., (continued)
- [bug-recutils] [PATCH 06/13] utils,doc: make re cfix --build-index add index trees., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 05/13] src: fix index file builder., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 04/13] src,torture: imple ment index builder., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 12/13] src: implement a tri vial query planner., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 09/13] src,torture: suppo rt duplicating index tree objects., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 10/13] src: keep indexes in rsets., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 11/13] src: support index t rees that point to a leaf too left of the key searched f or., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 08/13] utils: add recfix -- add-index command., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 13/13] torture: use index t rees for performance tests., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 07/13] src: fix index range checks., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 03/13] src,torture: imple ment index tree scans.,
Michał Masłowski <=