[bug-recutils] [PATCH 02/13] src,torture: imple ment initial index tree support without nodes.

[Michał Masłowski]

---
 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