Mercurial > hg > octave-lojdl > gnulib-hg

changeset 9686:25f7280c9cf0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
New abstract list operation 'node_set_value'.
author Bruno Haible <bruno@clisp.org>
date Sun, 10 Feb 2008 19:35:54 +0100
parents 2858c91c7452
children 5556ce2a3460
files ChangeLog lib/gl_anylinked_list2.h lib/gl_anytree_list2.h lib/gl_array_list.c lib/gl_avltree_list.c lib/gl_avltreehash_list.c lib/gl_carray_list.c lib/gl_linked_list.c lib/gl_linkedhash_list.c lib/gl_list.c lib/gl_list.h lib/gl_rbtree_list.c lib/gl_rbtreehash_list.c lib/gl_sublist.c
diffstat 14 files changed, 152 insertions(+), 13 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,25 @@
+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".
--- 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 @@
   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)
 {
--- 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 @@
   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)
 {
--- 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 @@
   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 @@
     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,
--- 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 @@
     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,
--- 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 @@
     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,
--- 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 @@
   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 @@
     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,
--- 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 @@
     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,
--- 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 @@
     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,
--- 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 @@
 	 ->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)
 {
--- 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 @@
 
    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 @@
 /* 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 @@
 		       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 @@
 	 ->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)
--- 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 @@
     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,
--- 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 @@
     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,
--- 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 @@
   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 @@
     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,