[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[bug-recutils] [PATCH 02/13] src,torture: imple ment initial index tree
From: |
Michał Masłowski |
Subject: |
[bug-recutils] [PATCH 02/13] src,torture: imple ment initial index tree support without nodes. |
Date: |
Mon, 20 Aug 2012 18:21:23 +0200 |
---
ChangeLog | 13 ++
src/Makefile.am | 3 +-
src/rec-idx-tree.c | 183 +++++++++++++++++++++++++++++
src/rec.h | 62 ++++++++++
torture/Makefile.am | 6 +-
torture/rec-idx-tree/rec-idx-tree-new.c | 105 +++++++++++++++++
torture/rec-idx-tree/tsuite-rec-idx-tree.c | 42 +++++++
torture/runtests.c | 2 +
8 files changed, 414 insertions(+), 2 deletions(-)
create mode 100644 src/rec-idx-tree.c
create mode 100644 torture/rec-idx-tree/rec-idx-tree-new.c
create mode 100644 torture/rec-idx-tree/tsuite-rec-idx-tree.c
diff --git a/ChangeLog b/ChangeLog
index 8946498..d401c5d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2012-08-08 Michał Masłowski <address@hidden>
+
+ src,torture: implement initial index tree support without nodes.
+ * src/Makefile.am (librec_la_SOURCES): Add rec-idx-tree.c.
+ * src/rec-idx-tree.c: New file.
+ * src/rec.h: Add prototypes and documentation for index trees.
+
+ * torture/Makefile.am (REC_IDX_TREE_TSUITE): New variable.
+ (runtests_SOURCES): Add $(REC_IDX_TREE_TSUITE).
+ * torture/rec-idx-tree/rec-idx-tree-new.c: New file.
+ * torture/rec-idx-tree/tsuite-rec-idx-tree.c: Likewise.
+ * torture/runtests.c (main): Add the tsuite_rec_idx_tree test suite.
+
2012-07-18 Michał Masłowski <address@hidden>
src,torture: implement abstract record iterators.
diff --git a/src/Makefile.am b/src/Makefile.am
index 9a30fa1..2b3dab6 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -45,7 +45,8 @@ librec_la_SOURCES = rec.c \
rec-buf.c \
rec-aggregate.c \
rec-idx-file.c \
- rec-iter.c
+ rec-iter.c \
+ rec-idx-tree.c
if CRYPT
librec_la_SOURCES += rec-crypt.c
diff --git a/src/rec-idx-tree.c b/src/rec-idx-tree.c
new file mode 100644
index 0000000..3d92bf7
--- /dev/null
+++ b/src/rec-idx-tree.c
@@ -0,0 +1,183 @@
+/* -*- mode: C -*-
+ *
+ * File: rec-idx-tree.c
+ * Date: Tue Aug 7 19:02:17 2012
+ *
+ * GNU recutils - Index trees
+ *
+ */
+
+/* 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 <stdlib.h>
+#include <string.h>
+
+#include <rec.h>
+
+/*
+ * Data structures.
+ */
+
+/* Object representing a tree index for reading. */
+
+struct rec_idx_tree_s
+{
+ const uint8_t *buffer; /* start of the memory buffer with index data */
+ 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 */
+};
+
+/* Type of the basic tree index. */
+#define REC_IDX_TREE_TYPE 1
+
+/* Header of the index tree in the index file. */
+struct rec_idx_tree_header_s
+{
+ uint8_t n_rsets;
+ uint8_t depth; /* 0 if root is leaf. */
+ uint8_t n_fields;
+};
+
+/* Then a sequence of uint8_t type and null-terminated name follow.
+ After them is padding to eight octets just before the first
+ node. */
+
+/*
+ * Public functions.
+ */
+
+rec_idx_tree_t
+rec_idx_tree_new (const uint8_t *bytes,
+ int64_t type,
+ size_t size)
+{
+ rec_idx_tree_t res = NULL;
+ size_t n_fields;
+ const uint8_t *next_byte;
+ size_t current_field;
+
+ /* In future will store the type if multiple formats are
+ supported. */
+ if (type != REC_IDX_TREE_TYPE)
+ {
+ return NULL; /* Unsupported index type. */
+ }
+
+ if (size < sizeof (struct rec_idx_tree_header_s))
+ {
+ return NULL; /* Obviously too small buffer. */
+ }
+
+ res = malloc (sizeof (*res));
+ if (!res)
+ {
+ return res;
+ }
+
+ /* Set basic fields and allocate the per-field arrays. */
+ res->buffer = bytes;
+ res->end = bytes + size;
+ n_fields = rec_idx_tree_get_num_fields (res);
+
+ res->names = malloc (sizeof (res->names[0]) * n_fields);
+ if (!res->names)
+ {
+ free (res);
+ return NULL;
+ }
+
+ res->types = malloc (sizeof (res->types[0]) * n_fields);
+ if (!res->types)
+ {
+ free (res->names);
+ free (res);
+ return NULL;
+ }
+
+ /* Parse the key field data. */
+ current_field = 0;
+ next_byte = bytes + sizeof (struct rec_idx_tree_header_s) - 1;
+
+ while ((next_byte != NULL)
+ && (next_byte < res->end - 2) && (current_field < n_fields))
+ {
+ next_byte++;
+ res->types[current_field] = *next_byte;
+
+ if (res->types[current_field] > REC_IDX_KEY_STRING)
+ {
+ break; /* Unknown type. */
+ }
+
+ res->names[current_field] = (const char*) ++next_byte;
+ next_byte = memchr (next_byte, 0, res->end - next_byte);
+ current_field++;
+ }
+
+ if ((next_byte == NULL) || (current_field < n_fields))
+ {
+ /* Incomplete key. */
+ free (res->types);
+ free (res->names);
+ free (res);
+ return NULL;
+ }
+
+ return res;
+}
+
+void
+rec_idx_tree_destroy (rec_idx_tree_t idx_tree)
+{
+ free (idx_tree->names);
+ free (idx_tree->types);
+ free (idx_tree);
+}
+
+size_t
+rec_idx_tree_get_rset_number (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->n_rsets;
+}
+
+size_t
+rec_idx_tree_get_num_fields (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->n_fields;
+}
+
+const char *
+rec_idx_tree_get_field_name (rec_idx_tree_t idx_tree, size_t n)
+{
+ return idx_tree->names[n];
+}
+
+rec_idx_tree_key_t
+rec_idx_tree_get_field_type (rec_idx_tree_t idx_tree, size_t n)
+{
+ return idx_tree->types[n];
+}
+
+/* End of rec-idx-tree.c */
diff --git a/src/rec.h b/src/rec.h
index 3ee12e2..980bf56 100644
--- a/src/rec.h
+++ b/src/rec.h
@@ -28,6 +28,7 @@
#include <stdbool.h>
#include <stdio.h>
+#include <stdint.h>
#include <fcntl.h>
/*
@@ -2442,6 +2443,67 @@ bool rec_iter_next (rec_iter_t iterator, rec_record_t
*record);
void rec_iter_destroy (rec_iter_t iterator);
+/*
+ * TREE INDEXES
+ *
+ * The following datatypes and routines provide support for indexes
+ * mapping ordered tuples of fields to records.
+ */
+
+/* Opaque data type representing a tree index. */
+
+typedef struct rec_idx_tree_s *rec_idx_tree_t;
+
+/* Known key types. They affect index storage size and sorting. */
+
+enum rec_idx_tree_key_e
+{
+ REC_IDX_KEY_NONE = 0, /* Unknown key type, returned on error. */
+ REC_IDX_KEY_STRING = 1, /* A NULL-terminated string with ASCII
+ lexicographical sorting. */
+};
+
+typedef enum rec_idx_tree_key_e rec_idx_tree_key_t;
+
+/**************** Creating and destroying index tree objects *********/
+
+/* Create an index tree object for reading an index tree from the
+ memory area specified by bytes and size arguments.
+
+ The type argument must specify the index type obtained from
+ rec_idx_file_index with the index data. The index types supported
+ might change in future releases.
+
+ NULL is returned on error, including unsupported index types or
+ obviously incorrect indexes.
+*/
+
+rec_idx_tree_t rec_idx_tree_new (const uint8_t *bytes, int64_t type, size_t
size);
+
+/* Destroy an index tree object. */
+
+void rec_idx_tree_destroy (rec_idx_tree_t idx_tree);
+
+/**************** Reading index tree metadata ************************/
+
+/* Return the zero-based number of the rset referred to by this index
+ in the recfile of the index file. */
+
+size_t rec_idx_tree_get_rset_number (rec_idx_tree_t idx_tree);
+
+/* Return the number of fields in an index key. */
+
+size_t rec_idx_tree_get_num_fields (rec_idx_tree_t idx_tree);
+
+/* Return the name of the n-th (counting from zero) field in the index
+ key. */
+
+const char *rec_idx_tree_get_field_name (rec_idx_tree_t idx_tree, size_t n);
+
+/* Return the type of the n-th field in the index key. */
+
+rec_idx_tree_key_t rec_idx_tree_get_field_type (rec_idx_tree_t idx_tree,
size_t n);
+
#endif /* !GNU_REC_H */
/* End of rec.h */
diff --git a/torture/Makefile.am b/torture/Makefile.am
index 6b3fa3e..0ac2d86 100644
--- a/torture/Makefile.am
+++ b/torture/Makefile.am
@@ -147,6 +147,9 @@ REC_IDX_FILE_TSUITE = rec-idx-file/rec-idx-file-new-mem.c \
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/tsuite-rec-idx-tree.c
+
runtests_SOURCES = runtests.c \
$(REC_MSET_TSUITE) \
$(REC_COMMENT_TSUITE) \
@@ -160,7 +163,8 @@ runtests_SOURCES = runtests.c \
$(REC_WRITER_TSUITE) \
$(REC_SEX_TSUITE) \
$(REC_IDX_FILE_TSUITE) \
- $(REC_ITER_TSUITE)
+ $(REC_ITER_TSUITE) \
+ $(REC_IDX_TREE_TSUITE)
AM_CPPFLAGS = -I$(top_srcdir)/src \
-I$(top_srcdir)/torture
diff --git a/torture/rec-idx-tree/rec-idx-tree-new.c
b/torture/rec-idx-tree/rec-idx-tree-new.c
new file mode 100644
index 0000000..4214ba4
--- /dev/null
+++ b/torture/rec-idx-tree/rec-idx-tree-new.c
@@ -0,0 +1,105 @@
+/* -*- mode: C -*-
+ *
+ * File: rec-idx-tree-new.c
+ * Date: Wed Aug 8 16:28:49 2012
+ *
+ * GNU recutils - rec_idx_tree_new 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_new_nominal
+ * Unit: rec_idx_tree_new
+ * Description:
+ * + Open an index tree and verify its metadata.
+ */
+START_TEST(rec_idx_tree_new_nominal)
+{
+ rec_idx_tree_t tree;
+
+ /* Open the tree. */
+ tree = rec_idx_tree_new (sample_header, 1 /* the type */,
+ sizeof(sample_header));
+ fail_if (!tree);
+
+ /* Check the header. */
+ fail_if (rec_idx_tree_get_rset_number (tree) != 1);
+ fail_if (rec_idx_tree_get_num_fields (tree) != 2);
+
+ /* Check the key. */
+ fail_if (strcmp (rec_idx_tree_get_field_name (tree, 0), "foo"));
+ fail_if (rec_idx_tree_get_field_type (tree, 0) != REC_IDX_KEY_STRING);
+ fail_if (strcmp (rec_idx_tree_get_field_name (tree, 1), "bar"));
+ fail_if (rec_idx_tree_get_field_type (tree, 1) != REC_IDX_KEY_STRING);
+
+ /* Close. */
+ rec_idx_tree_destroy (tree);
+}
+END_TEST
+
+/*-
+ * Test: rec_idx_tree_new_too_short
+ * Unit: rec_idx_tree_new
+ * Description:
+ * + Check that an incomplete node cannot be open.
+ */
+START_TEST(rec_idx_tree_new_too_short)
+{
+ fail_if (rec_idx_tree_new (sample_header, 1, sizeof (sample_header) - 4));
+ fail_if (rec_idx_tree_new (sample_header, 1, sizeof (sample_header) - 5));
+ fail_if (rec_idx_tree_new (sample_header, 1, sizeof (sample_header) - 9));
+ fail_if (rec_idx_tree_new (sample_header, 1, 3));
+ fail_if (rec_idx_tree_new (sample_header, 1, 2));
+ fail_if (rec_idx_tree_new (sample_header, 1, 0));
+}
+END_TEST
+
+/*
+ * Test creation function
+ */
+TCase *
+test_rec_idx_tree_new (void)
+{
+ TCase *tc = tcase_create ("rec_idx_tree_new");
+ tcase_add_test (tc, rec_idx_tree_new_nominal);
+ tcase_add_test (tc, rec_idx_tree_new_too_short);
+
+ return tc;
+}
+
+/* End of rec-idx-tree-new.c */
diff --git a/torture/rec-idx-tree/tsuite-rec-idx-tree.c
b/torture/rec-idx-tree/tsuite-rec-idx-tree.c
new file mode 100644
index 0000000..aae8873
--- /dev/null
+++ b/torture/rec-idx-tree/tsuite-rec-idx-tree.c
@@ -0,0 +1,42 @@
+/* -*- mode: C -*-
+ *
+ * File: tsuite-rec-idx-tree.c
+ * Date: Wed Aug 8 16:25:28 2012
+ *
+ * GNU recutils - rec_idx_tree test suite
+ *
+ */
+
+/* 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 <check.h>
+
+extern TCase *test_rec_idx_tree_new (void);
+
+Suite *
+tsuite_rec_idx_tree ()
+{
+ Suite *s;
+
+ s = suite_create ("rec-idx-tree");
+ suite_add_tcase (s, test_rec_idx_tree_new ());
+
+ return s;
+}
+
+/* End of tsuite-rec-idx-tree.c */
diff --git a/torture/runtests.c b/torture/runtests.c
index 35c81b1..b13cc32 100644
--- a/torture/runtests.c
+++ b/torture/runtests.c
@@ -41,6 +41,7 @@ extern Suite *tsuite_rec_writer (void);
extern Suite *tsuite_rec_sex (void);
extern Suite *tsuite_rec_idx_file (void);
extern Suite *tsuite_rec_iter (void);
+extern Suite *tsuite_rec_idx_tree (void);
int
main (int argc, char **argv)
@@ -63,6 +64,7 @@ main (int argc, char **argv)
srunner_add_suite (sr, tsuite_rec_sex ());
srunner_add_suite (sr, tsuite_rec_idx_file ());
srunner_add_suite (sr, tsuite_rec_iter ());
+ srunner_add_suite (sr, tsuite_rec_idx_tree ());
srunner_set_log (sr, "tests.log");
--
1.7.11.4
- [bug-recutils] Index trees, Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 01/13] src,torture: imple ment abstract record iterators., Michał Masłowski, 2012/08/20
- [bug-recutils] [PATCH 02/13] src,torture: imple ment initial index tree support without nodes.,
Michał Masłowski <=
- [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