[Top][All Lists]
[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,
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- new abstract list operation 'node_set_value',
Bruno Haible <=