bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

new abstract list operation 'node_set_value'


From: Bruno Haible
Subject: new abstract list operation 'node_set_value'
Date: Sun, 10 Feb 2008 19:36:04 +0100
User-agent: KMail/1.5.4

The list abstraction in gnulib was missing an operation to modify the
value at a certain position, when the position is given as a node rather
than at as an index. For linked lists, operations that involve a position as
index are slow; it is essential to have a setter operation that is quick
for linked lists.

2008-02-10  Bruno Haible  <address@hidden>

        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.

*** lib/gl_anylinked_list2.h.orig       2008-02-10 19:24:20.000000000 +0100
--- lib/gl_anylinked_list2.h    2008-02-10 17:56:22.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a linked list.
!    Copyright (C) 2006-2007 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a linked list.
!    Copyright (C) 2006-2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 126,131 ****
--- 126,157 ----
    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)
  {
*** lib/gl_anytree_list2.h.orig 2008-02-10 19:24:20.000000000 +0100
--- lib/gl_anytree_list2.h      2008-02-10 18:00:43.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a binary tree.
!    Copyright (C) 2006-2007 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a binary tree.
!    Copyright (C) 2006-2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 53,58 ****
--- 53,84 ----
    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)
  {
*** lib/gl_array_list.c.orig    2008-02-10 19:24:20.000000000 +0100
--- lib/gl_array_list.c 2008-02-10 17:52:01.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by an array.
!    Copyright (C) 2006-2007 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by an array.
!    Copyright (C) 2006-2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 116,121 ****
--- 116,131 ----
    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,623 ****
--- 628,634 ----
      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,
*** lib/gl_avltree_list.c.orig  2008-02-10 19:24:20.000000000 +0100
--- lib/gl_avltree_list.c       2008-02-10 17:57:39.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a binary tree.
!    Copyright (C) 2006 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a binary tree.
!    Copyright (C) 2006, 2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 70,75 ****
--- 70,76 ----
      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,
*** lib/gl_avltreehash_list.c.orig      2008-02-10 19:24:20.000000000 +0100
--- lib/gl_avltreehash_list.c   2008-02-10 17:59:04.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a hash table with a binary tree.
!    Copyright (C) 2006 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a hash table with a binary tree.
!    Copyright (C) 2006, 2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 99,104 ****
--- 99,105 ----
      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,
*** lib/gl_carray_list.c.orig   2008-02-10 19:24:20.000000000 +0100
--- lib/gl_carray_list.c        2008-02-10 17:53:05.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a circular array.
!    Copyright (C) 2006-2007 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a circular array.
!    Copyright (C) 2006-2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 126,131 ****
--- 126,146 ----
    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,813 ****
--- 823,829 ----
      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,
*** lib/gl_linked_list.c.orig   2008-02-10 19:24:20.000000000 +0100
--- lib/gl_linked_list.c        2008-02-10 17:54:28.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a linked list.
!    Copyright (C) 2006 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a linked list.
!    Copyright (C) 2006, 2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 37,42 ****
--- 37,43 ----
      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,
*** lib/gl_linkedhash_list.c.orig       2008-02-10 19:24:21.000000000 +0100
--- lib/gl_linkedhash_list.c    2008-02-10 17:56:58.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a hash table with a linked list.
!    Copyright (C) 2006 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a hash table with a linked list.
!    Copyright (C) 2006, 2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 94,99 ****
--- 94,100 ----
      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,
*** lib/gl_list.c.orig  2008-02-10 19:24:21.000000000 +0100
--- lib/gl_list.c       2008-02-10 17:49:58.000000000 +0100
***************
*** 1,5 ****
  /* Abstract sequential list data type.
!    Copyright (C) 2006-2007 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Abstract sequential list data type.
!    Copyright (C) 2006-2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 63,68 ****
--- 63,75 ----
         ->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)
  {
*** lib/gl_list.h.orig  2008-02-10 19:24:21.000000000 +0100
--- lib/gl_list.h       2008-02-10 18:11:45.000000000 +0100
***************
*** 1,5 ****
  /* Abstract sequential list data type.
!    Copyright (C) 2006-2007 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Abstract sequential list data type.
!    Copyright (C) 2006-2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 62,67 ****
--- 62,68 ----
  
     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,163 ****
--- 159,168 ----
  /* 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,386 ****
--- 386,392 ----
                       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,494 ****
--- 495,508 ----
         ->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)
*** lib/gl_rbtree_list.c.orig   2008-02-10 19:24:21.000000000 +0100
--- lib/gl_rbtree_list.c        2008-02-10 17:58:10.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a binary tree.
!    Copyright (C) 2006 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a binary tree.
!    Copyright (C) 2006, 2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 71,76 ****
--- 71,77 ----
      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,
*** lib/gl_rbtreehash_list.c.orig       2008-02-10 19:24:21.000000000 +0100
--- lib/gl_rbtreehash_list.c    2008-02-10 17:58:45.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type implemented by a hash table with a binary tree.
!    Copyright (C) 2006 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type implemented by a hash table with a binary tree.
!    Copyright (C) 2006, 2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 100,105 ****
--- 100,106 ----
      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,
*** lib/gl_sublist.c.orig       2008-02-10 19:24:21.000000000 +0100
--- lib/gl_sublist.c    2008-02-10 18:03:06.000000000 +0100
***************
*** 1,5 ****
  /* Sequential list data type backed by another list.
!    Copyright (C) 2006-2007 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
--- 1,5 ----
  /* Sequential list data type backed by another list.
!    Copyright (C) 2006-2008 Free Software Foundation, Inc.
     Written by Bruno Haible <address@hidden>, 2006.
  
     This program is free software: you can redistribute it and/or modify
***************
*** 87,92 ****
--- 87,102 ----
    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,402 ****
--- 407,413 ----
      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,





reply via email to

[Prev in Thread] Current Thread [Next in Thread]