New abstract list operation 'node_set_value'.

diff --git a/ChangeLog b/ChangeLog
index fca5c9f..a3f4900 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,27 @@
 2008-02-10  Bruno Haible  <bruno@clisp.org>
 
+       New abstract list operation 'node_set_value'.
+       * lib/gl_list.h (gl_list_node_set_value): New function.
+       (struct gl_list_implementation): New field node_set_value.
+       * lib/gl_list.c (gl_list_node_set_value): New function.
+       * lib/gl_array_list.c (gl_array_node_set_value): New function.
+       (gl_array_list_implementation): Update.
+       * lib/gl_carray_list.c (gl_carray_node_set_value): New function.
+       (gl_carray_list_implementation): Update.
+       * lib/gl_anylinked_list2.h (gl_linked_node_set_value): New function.
+       * lib/gl_linked_list.c (gl_linked_list_implementation): Update.
+       * lib/gl_linkedhash_list.c (gl_linkedhash_list_implementation): Update.
+       * lib/gl_anytree_list2.h (gl_tree_node_set_value): New function.
+       * lib/gl_avltree_list.c (gl_avltree_list_implementation): Update.
+       * lib/gl_rbtree_list.c (gl_rbtree_list_implementation): Update.
+       * lib/gl_avltreehash_list.c (gl_avltreehash_list_implementation):
+       Update.
+       * lib/gl_rbtreehash_list.c (gl_rbtreehash_list_implementation): Update.
+       * lib/gl_sublist.c (gl_sublist_node_set_value): New function.
+       (gl_sublist_list_implementation): Update.
+
+2008-02-10  Bruno Haible  <bruno@clisp.org>
+
        * lib/diffseq.h: Write "ELEMENT const" instead of "const ELEMENT".
        Needed when ELEMENT is #defined to 'some_type *'.
 

diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h
index 9d481a3..9fbe5a8 100644 (file)
--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a linked list.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -126,6 +126,32 @@ gl_linked_node_value (gl_list_t list, gl_list_node_t node)
   return node->value;
 }
 
+static void
+gl_linked_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+#if WITH_HASHTABLE
+  if (elt != node->value)
+    {
+      size_t new_hashcode =
+       (list->base.hashcode_fn != NULL
+        ? list->base.hashcode_fn (elt)
+        : (size_t)(uintptr_t) elt);
+
+      if (new_hashcode != node->h.hashcode)
+       {
+         remove_from_bucket (list, node);
+         node->value = elt;
+         node->h.hashcode = new_hashcode;
+         add_to_bucket (list, node);
+       }
+      else
+       node->value = elt;
+    }
+#else
+  node->value = elt;
+#endif
+}
+
 static gl_list_node_t
 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
 {

diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
index c5e5d83..143348e 100644 (file)
--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a binary tree.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -53,6 +53,32 @@ gl_tree_node_value (gl_list_t list, gl_list_node_t node)
   return node->value;
 }
 
+static void
+gl_tree_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+#if WITH_HASHTABLE
+  if (elt != node->value)
+    {
+      size_t new_hashcode =
+       (list->base.hashcode_fn != NULL
+        ? list->base.hashcode_fn (elt)
+        : (size_t)(uintptr_t) elt);
+
+      if (new_hashcode != node->h.hashcode)
+       {
+         remove_from_bucket (list, node);
+         node->value = elt;
+         node->h.hashcode = new_hashcode;
+         add_to_bucket (list, node);
+       }
+      else
+       node->value = elt;
+    }
+#else
+  node->value = elt;
+#endif
+}
+
 static gl_list_node_t
 gl_tree_next_node (gl_list_t list, gl_list_node_t node)
 {

diff --git a/lib/gl_array_list.c b/lib/gl_array_list.c
index deb83ae..f82d01b 100644 (file)
--- a/lib/gl_array_list.c
+++ b/lib/gl_array_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by an array.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -116,6 +116,16 @@ gl_array_node_value (gl_list_t list, gl_list_node_t node)
   return list->elements[index];
 }
 
+static void
+gl_array_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  uintptr_t index = NODE_TO_INDEX (node);
+  if (!(index < list->count))
+    /* Invalid argument.  */
+    abort ();
+  list->elements[index] = elt;
+}
+
 static gl_list_node_t
 gl_array_next_node (gl_list_t list, gl_list_node_t node)
 {
@@ -618,6 +628,7 @@ const struct gl_list_implementation gl_array_list_implementation =
     gl_array_create,
     gl_array_size,
     gl_array_node_value,
+    gl_array_node_set_value,
     gl_array_next_node,
     gl_array_previous_node,
     gl_array_get_at,

diff --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c
index ff74513..f50b6f3 100644 (file)
--- a/lib/gl_avltree_list.c
+++ b/lib/gl_avltree_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a binary tree.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -70,6 +70,7 @@ const struct gl_list_implementation gl_avltree_list_implementation =
     gl_tree_create,
     gl_tree_size,
     gl_tree_node_value,
+    gl_tree_node_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
     gl_tree_get_at,

diff --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c
index 195580e..ef739fc 100644 (file)
--- a/lib/gl_avltreehash_list.c
+++ b/lib/gl_avltreehash_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a hash table with a binary tree.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -99,6 +99,7 @@ const struct gl_list_implementation gl_avltreehash_list_implementation =
     gl_tree_create,
     gl_tree_size,
     gl_tree_node_value,
+    gl_tree_node_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
     gl_tree_get_at,

diff --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c
index 8e0c7d6..8b43901 100644 (file)
--- a/lib/gl_carray_list.c
+++ b/lib/gl_carray_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a circular array.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -126,6 +126,21 @@ gl_carray_node_value (gl_list_t list, gl_list_node_t node)
   return list->elements[i];
 }
 
+static void
+gl_carray_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  uintptr_t index = NODE_TO_INDEX (node);
+  size_t i;
+
+  if (!(index < list->count))
+    /* Invalid argument.  */
+    abort ();
+  i = list->offset + index;
+  if (i >= list->allocated)
+    i -= list->allocated;
+  list->elements[i] = elt;
+}
+
 static gl_list_node_t
 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
 {
@@ -808,6 +823,7 @@ const struct gl_list_implementation gl_carray_list_implementation =
     gl_carray_create,
     gl_carray_size,
     gl_carray_node_value,
+    gl_carray_node_set_value,
     gl_carray_next_node,
     gl_carray_previous_node,
     gl_carray_get_at,

diff --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c
index 8aac243..a1bd5ee 100644 (file)
--- a/lib/gl_linked_list.c
+++ b/lib/gl_linked_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a linked list.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -37,6 +37,7 @@ const struct gl_list_implementation gl_linked_list_implementation =
     gl_linked_create,
     gl_linked_size,
     gl_linked_node_value,
+    gl_linked_node_set_value,
     gl_linked_next_node,
     gl_linked_previous_node,
     gl_linked_get_at,

diff --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c
index 2114c43..7afecb5 100644 (file)
--- a/lib/gl_linkedhash_list.c
+++ b/lib/gl_linkedhash_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a hash table with a linked list.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -94,6 +94,7 @@ const struct gl_list_implementation gl_linkedhash_list_implementation =
     gl_linked_create,
     gl_linked_size,
     gl_linked_node_value,
+    gl_linked_node_set_value,
     gl_linked_next_node,
     gl_linked_previous_node,
     gl_linked_get_at,

diff --git a/lib/gl_list.c b/lib/gl_list.c
index 3f1512d..9eca9e4 100644 (file)
--- a/lib/gl_list.c
+++ b/lib/gl_list.c
@@ -1,5 +1,5 @@
 /* Abstract sequential list data type.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -63,6 +63,13 @@ gl_list_node_value (gl_list_t list, gl_list_node_t node)
         ->node_value (list, node);
 }
 
+void
+gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  ((const struct gl_list_impl_base *) list)->vtable
+  ->node_set_value (list, node, elt);
+}
+
 gl_list_node_t
 gl_list_next_node (gl_list_t list, gl_list_node_t node)
 {

diff --git a/lib/gl_list.h b/lib/gl_list.h
index 1a2f9fb..ca4f476 100644 (file)
--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -1,5 +1,5 @@
 /* Abstract sequential list data type.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -62,6 +62,7 @@ extern "C" {
 
    gl_list_size                O(1)     O(1)     O(1)      O(1)         O(1)
    gl_list_node_value          O(1)     O(1)     O(1)      O(1)         O(1)
+   gl_list_node_set_value      O(1)     O(1)     O(1)      O(1)    O((log n)²)/O(1)
    gl_list_next_node           O(1)     O(1)   O(log n)    O(1)       O(log n)
    gl_list_previous_node       O(1)     O(1)   O(log n)    O(1)       O(log n)
    gl_list_get_at              O(1)     O(n)   O(log n)    O(n)       O(log n)
@@ -158,6 +159,10 @@ extern size_t gl_list_size (gl_list_t list);
 /* Return the element value represented by a list node.  */
 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
 
+/* Replace the element value represented by a list node.  */
+extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
+                                   const void *elt);
+
 /* Return the node immediately after the given node in the list, or NULL
    if the given node is the last (rightmost) one in the list.  */
 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
@@ -381,6 +386,7 @@ struct gl_list_implementation
                       size_t count, const void **contents);
   size_t (*size) (gl_list_t list);
   const void * (*node_value) (gl_list_t list, gl_list_node_t node);
+  void (*node_set_value) (gl_list_t list, gl_list_node_t node, const void *elt);
   gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
   gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
   const void * (*get_at) (gl_list_t list, size_t position);
@@ -489,6 +495,14 @@ gl_list_node_value (gl_list_t list, gl_list_node_t node)
         ->node_value (list, node);
 }
 
+# define gl_list_node_set_value gl_list_node_set_value_inline
+static inline void
+gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  ((const struct gl_list_impl_base *) list)->vtable
+  ->node_set_value (list, node, elt);
+}
+
 # define gl_list_next_node gl_list_next_node_inline
 static inline gl_list_node_t
 gl_list_next_node (gl_list_t list, gl_list_node_t node)

diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c
index ee6f96c..b4f37e6 100644 (file)
--- a/lib/gl_rbtree_list.c
+++ b/lib/gl_rbtree_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a binary tree.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -71,6 +71,7 @@ const struct gl_list_implementation gl_rbtree_list_implementation =
     gl_tree_create,
     gl_tree_size,
     gl_tree_node_value,
+    gl_tree_node_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
     gl_tree_get_at,

diff --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c
index faa95cf..73ba2f6 100644 (file)
--- a/lib/gl_rbtreehash_list.c
+++ b/lib/gl_rbtreehash_list.c
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a hash table with a binary tree.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -100,6 +100,7 @@ const struct gl_list_implementation gl_rbtreehash_list_implementation =
     gl_tree_create,
     gl_tree_size,
     gl_tree_node_value,
+    gl_tree_node_set_value,
     gl_tree_next_node,
     gl_tree_previous_node,
     gl_tree_get_at,

diff --git a/lib/gl_sublist.c b/lib/gl_sublist.c
index 0760cbd..19158d0 100644 (file)
--- a/lib/gl_sublist.c
+++ b/lib/gl_sublist.c
@@ -1,5 +1,5 @@
 /* Sequential list data type backed by another list.
-   Copyright (C) 2006-2007 Free Software Foundation, Inc.
+   Copyright (C) 2006-2008 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software: you can redistribute it and/or modify
@@ -87,6 +87,16 @@ gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
   return gl_list_get_at (list->whole, list->start + index);
 }
 
+static void
+gl_sublist_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  uintptr_t index = NODE_TO_INDEX (node);
+  if (!(index < list->end - list->start))
+    /* Invalid argument.  */
+    abort ();
+  gl_list_set_at (list->whole, list->start + index, elt);
+}
+
 static gl_list_node_t
 gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
 {
@@ -397,6 +407,7 @@ static const struct gl_list_implementation gl_sublist_list_implementation =
     gl_sublist_create_fill,
     gl_sublist_size,
     gl_sublist_node_value,
+    gl_sublist_node_set_value,
     gl_sublist_next_node,
     gl_sublist_previous_node,
     gl_sublist_get_at,