New module 'sublist'.

5 files changed, 536 insertions, 0 deletions

diff --git a/ChangeLog b/ChangeLog
index a8c8f8d00c..7555b06002 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
+2006-10-03  Bruno Haible  <bruno@clisp.org>
+
+	* modules/sublist: New file.
+
 2006-09-29  Bruno Haible  <bruno@clisp.org>
 
 	* modules/closeout (Description): Mention stderr too.
diff --git a/lib/ChangeLog b/lib/ChangeLog
index 6f4bd8d0f0..31837f3a77 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,8 @@
+2006-10-03  Bruno Haible  <bruno@clisp.org>
+
+	* gl_sublist.h: New file.
+	* gl_sublist.c: New file.
+
 2006-10-06  Paul Eggert  <eggert@cs.ucla.edu>
 
 	* mkancesdirs.c (mkancesdirs): Pass to MAKE_DIR both the full file
diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c
new file mode 100644
index 0000000000..e851c882fc
--- /dev/null
+++ b/lib/gl_sublist.c
@@ -0,0 +1,457 @@
+/* Sequential list data type backed by another list.
+   Copyright (C) 2006 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+   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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+#include <config.h>
+
+/* Specification.  */
+#include "gl_sublist.h"
+
+#include <stdlib.h>
+
+#include "xalloc.h"
+
+#ifndef uintptr_t
+# define uintptr_t unsigned long
+#endif
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Concrete gl_list_impl type, valid for this file only.  */
+struct gl_list_impl
+{
+  struct gl_list_impl_base base;
+  /* Reference to the whole list.  */
+  gl_list_t whole;
+  /* Limits of the index range.  */
+  size_t start;
+  size_t end;
+};
+
+/* struct gl_list_node_impl doesn't exist here.  The pointers are actually
+   indices + 1.  (We don't use the whole list's gl_list_node_t implementation,
+   because gl_sublist_next_node and gl_sublist_previous_node would not be easy
+   to implement with this choice.)  */
+#define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
+#define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
+
+static gl_list_t
+gl_sublist_create_empty (gl_list_implementation_t implementation,
+			 gl_listelement_equals_fn equals_fn,
+			 gl_listelement_hashcode_fn hashcode_fn,
+			 bool allow_duplicates)
+{
+  /* Shouldn't be called.  */
+  abort ();
+}
+
+static gl_list_t
+gl_sublist_create_fill (gl_list_implementation_t implementation,
+			gl_listelement_equals_fn equals_fn,
+			gl_listelement_hashcode_fn hashcode_fn,
+			bool allow_duplicates,
+			size_t count, const void **contents)
+{
+  /* Shouldn't be called.  */
+  abort ();
+}
+
+static size_t
+gl_sublist_size (gl_list_t list)
+{
+  return list->end - list->start;
+}
+
+static const void *
+gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
+{
+  uintptr_t index = NODE_TO_INDEX (node);
+  if (!(index < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  return gl_list_get_at (list->whole, list->start + index);
+}
+
+static gl_list_node_t
+gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
+{
+  uintptr_t index = NODE_TO_INDEX (node);
+  size_t count = list->end - list->start;
+  if (!(index < count))
+    /* Invalid argument.  */
+    abort ();
+  index++;
+  if (index < count)
+    return INDEX_TO_NODE (index);
+  else
+    return NULL;
+}
+
+static gl_list_node_t
+gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
+{
+  uintptr_t index = NODE_TO_INDEX (node);
+  if (!(index < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  if (index > 0)
+    return INDEX_TO_NODE (index - 1);
+  else
+    return NULL;
+}
+
+static const void *
+gl_sublist_get_at (gl_list_t list, size_t position)
+{
+  if (!(position < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  return gl_list_get_at (list->whole, list->start + position);
+}
+
+static gl_list_node_t
+gl_sublist_set_at (gl_list_t list, size_t position, const void *elt)
+{
+  if (!(position < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  gl_list_set_at (list->whole, list->start + position, elt);
+  return INDEX_TO_NODE (position);
+}
+
+static gl_list_node_t
+gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			   const void *elt)
+{
+  if (!(start_index <= end_index && end_index <= list->end - list->start))
+    /* Invalid arguments.  */
+    abort ();
+  {
+    size_t index =
+      gl_list_indexof_from_to (list->whole,
+			       list->start + start_index,
+			       list->start + end_index,
+			       elt);
+    if (index != (size_t)(-1))
+      return INDEX_TO_NODE (index - list->start);
+    else
+      return NULL;
+  }
+}
+
+static size_t
+gl_sublist_indexof_from_to (gl_list_t list,
+			    size_t start_index, size_t end_index,
+			    const void *elt)
+{
+  if (!(start_index <= end_index && end_index <= list->end - list->start))
+    /* Invalid arguments.  */
+    abort ();
+  {
+    size_t index =
+      gl_list_indexof_from_to (list->whole,
+			       list->start + start_index,
+			       list->start + end_index,
+			       elt);
+    if (index != (size_t)(-1))
+      index -= list->start;
+    return index;
+  }
+}
+
+static gl_list_node_t
+gl_sublist_add_first (gl_list_t list, const void *elt)
+{
+  gl_list_add_at (list->whole, list->start, elt);
+  list->end++;
+  return INDEX_TO_NODE (0);
+}
+
+static gl_list_node_t
+gl_sublist_add_last (gl_list_t list, const void *elt)
+{
+  gl_list_add_at (list->whole, list->end, elt);
+  list->end++;
+  return INDEX_TO_NODE (list->end - list->start - 1);
+}
+
+static gl_list_node_t
+gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  size_t position = NODE_TO_INDEX (node);
+  if (!(position < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  gl_list_add_at (list->whole, list->start + position, elt);
+  list->end++;
+  return INDEX_TO_NODE (position);
+}
+
+static gl_list_node_t
+gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  size_t position = NODE_TO_INDEX (node);
+  if (!(position < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  position++;
+  gl_list_add_at (list->whole, list->start + position, elt);
+  list->end++;
+  return INDEX_TO_NODE (position);
+}
+
+static gl_list_node_t
+gl_sublist_add_at (gl_list_t list, size_t position, const void *elt)
+{
+  if (!(position <= list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  gl_list_add_at (list->whole, list->start + position, elt);
+  list->end++;
+  return INDEX_TO_NODE (position);
+}
+
+static bool
+gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
+{
+  uintptr_t index = NODE_TO_INDEX (node);
+  if (!(index < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  return gl_list_remove_at (list->whole, list->start + index);
+}
+
+static bool
+gl_sublist_remove_at (gl_list_t list, size_t position)
+{
+  if (!(position < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  return gl_list_remove_at (list->whole, list->start + position);
+}
+
+static bool
+gl_sublist_remove (gl_list_t list, const void *elt)
+{
+  size_t position =
+    gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
+  if (position == (size_t)(-1))
+    return false;
+  else
+    return gl_list_remove_at (list->whole, position);
+}
+
+static void
+gl_sublist_list_free (gl_list_t list)
+{
+  free (list);
+}
+
+/* --------------------- gl_list_iterator_t Data Type --------------------- */
+
+static gl_list_iterator_t
+gl_sublist_iterator (gl_list_t list)
+{
+  return gl_list_iterator_from_to (list->whole, list->start, list->end);
+}
+
+static gl_list_iterator_t
+gl_sublist_iterator_from_to (gl_list_t list,
+			     size_t start_index, size_t end_index)
+{
+  if (!(start_index <= end_index && end_index <= list->end - list->start))
+    /* Invalid arguments.  */
+    abort ();
+  return gl_list_iterator_from_to (list->whole,
+				   list->start + start_index,
+				   list->start + end_index);
+}
+
+static bool
+gl_sublist_iterator_next (gl_list_iterator_t *iterator,
+			  const void **eltp, gl_list_node_t *nodep)
+{
+  /* Shouldn't be called.  */
+  abort ();
+}
+
+static void
+gl_sublist_iterator_free (gl_list_iterator_t *iterator)
+{
+  /* Shouldn't be called.  */
+  abort ();
+}
+
+/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
+
+static gl_list_node_t
+gl_sublist_sortedlist_search (gl_list_t list,
+			      gl_listelement_compar_fn compar,
+			      const void *elt)
+{
+  size_t index =
+    gl_sortedlist_indexof_from_to (list->whole, compar,
+				   list->start, list->end, elt);
+  if (index != (size_t)(-1))
+    return INDEX_TO_NODE (index - list->start);
+  else
+    return NULL;
+}
+
+static gl_list_node_t
+gl_sublist_sortedlist_search_from_to (gl_list_t list,
+				      gl_listelement_compar_fn compar,
+				      size_t low, size_t high,
+				      const void *elt)
+{
+  size_t index;
+
+  if (!(low <= high && high <= list->end - list->start))
+    /* Invalid arguments.  */
+    abort ();
+
+  index =
+    gl_sortedlist_indexof_from_to (list->whole, compar,
+				   list->start + low, list->start + high, elt);
+  if (index != (size_t)(-1))
+    return INDEX_TO_NODE (index - list->start);
+  else
+    return NULL;
+}
+
+static size_t
+gl_sublist_sortedlist_indexof (gl_list_t list,
+			       gl_listelement_compar_fn compar,
+			       const void *elt)
+{
+  size_t index =
+    gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
+				   elt);
+  if (index != (size_t)(-1))
+    index -= list->start;
+  return index;
+}
+
+static size_t
+gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
+				       gl_listelement_compar_fn compar,
+				       size_t low, size_t high,
+				       const void *elt)
+{
+  size_t index;
+
+  if (!(low <= high && high <= list->end - list->start))
+    /* Invalid arguments.  */
+    abort ();
+
+  index = gl_sortedlist_indexof_from_to (list->whole, compar,
+					 list->start + low, list->start + high,
+					 elt);
+  if (index != (size_t)(-1))
+    index -= list->start;
+  return index;
+}
+
+static gl_list_node_t
+gl_sublist_sortedlist_add (gl_list_t list,
+			   gl_listelement_compar_fn compar,
+			   const void *elt)
+{
+  /* It's impossible to implement this method without risking to put the
+     whole list into unsorted order (namely, when the given ELT is smaller
+     or larger than all elements of the sublist).  */
+  abort ();
+}
+
+static bool
+gl_sublist_sortedlist_remove (gl_list_t list,
+			      gl_listelement_compar_fn compar,
+			      const void *elt)
+{
+  size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
+  if (index == (size_t)(-1))
+    return false;
+  else
+    return gl_sublist_remove_at (list, index);
+}
+
+
+static const struct gl_list_implementation gl_sublist_list_implementation =
+  {
+    gl_sublist_create_empty,
+    gl_sublist_create_fill,
+    gl_sublist_size,
+    gl_sublist_node_value,
+    gl_sublist_next_node,
+    gl_sublist_previous_node,
+    gl_sublist_get_at,
+    gl_sublist_set_at,
+    gl_sublist_search_from_to,
+    gl_sublist_indexof_from_to,
+    gl_sublist_add_first,
+    gl_sublist_add_last,
+    gl_sublist_add_before,
+    gl_sublist_add_after,
+    gl_sublist_add_at,
+    gl_sublist_remove_node,
+    gl_sublist_remove_at,
+    gl_sublist_remove,
+    gl_sublist_list_free,
+    gl_sublist_iterator,
+    gl_sublist_iterator_from_to,
+    gl_sublist_iterator_next,
+    gl_sublist_iterator_free,
+    gl_sublist_sortedlist_search,
+    gl_sublist_sortedlist_search_from_to,
+    gl_sublist_sortedlist_indexof,
+    gl_sublist_sortedlist_indexof_from_to,
+    gl_sublist_sortedlist_add,
+    gl_sublist_sortedlist_remove
+  };
+
+gl_list_t
+gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index)
+{
+  if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
+    /* Invalid arguments.  */
+    abort ();
+  {
+    struct gl_list_impl *list =
+      (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+
+    list->base.vtable = &gl_sublist_list_implementation;
+    list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */
+    list->base.hashcode_fn = whole_list->base.hashcode_fn; /* actually unused */
+    list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */
+    if (whole_list->base.vtable == &gl_sublist_list_implementation)
+      {
+	/* Optimization of a sublist of a sublist: Collapse the two
+	   indirections into a single indirection.  */
+	list->whole = whole_list->whole;
+	list->start = whole_list->start + start_index;
+	list->end = whole_list->start + end_index;
+      }
+    else
+      {
+	list->whole = whole_list;
+	list->start = start_index;
+	list->end = end_index;
+      }
+
+    return list;
+  }
+}
diff --git a/lib/gl_sublist.h b/lib/gl_sublist.h
new file mode 100644
index 0000000000..dd5fe01c60
--- /dev/null
+++ b/lib/gl_sublist.h
@@ -0,0 +1,45 @@
+/* Sequential list data type backed by another list.
+   Copyright (C) 2006 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+   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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+#ifndef _GL_SUBLIST_H
+#define _GL_SUBLIST_H
+
+#include "gl_list.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+/* Create a sublist of a given list.
+   This is the list of elements with indices i, start_index <= i < end_index.
+   The sublist is backed by the given list, which means:
+     - Modifications to the sublist affect the whole list.
+     - Modifications to the whole list are immediately visible in the sublist.
+     - The sublist is only valid as long as the whole list is valid.
+     - The sublist must not be passed to the gl_list_sortedlist_add() function.
+ */
+extern gl_list_t gl_sublist_create (gl_list_t whole_list,
+				    size_t start_index, size_t end_index);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_SUBLIST_H */
diff --git a/modules/sublist b/modules/sublist
new file mode 100644
index 0000000000..e8e3d9873a
--- /dev/null
+++ b/modules/sublist
@@ -0,0 +1,25 @@
+Description:
+Sequential list data type backed by another list.
+
+Files:
+lib/gl_sublist.h
+lib/gl_sublist.c
+
+Depends-on:
+list
+xalloc
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_sublist.h gl_sublist.c
+
+Include:
+"gl_sublist.h"
+
+License:
+GPL
+
+Maintainer:
+Bruno Haible
+