From 92877a2d8aef6f0296ff0567f9828151d4d82d64 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sun, 10 Feb 2008 19:35:54 +0100 Subject: [PATCH] New abstract list operation 'node_set_value'. --- ChangeLog | 22 ++++++++++++++++++++++ lib/gl_anylinked_list2.h | 28 +++++++++++++++++++++++++++- lib/gl_anytree_list2.h | 28 +++++++++++++++++++++++++++- lib/gl_array_list.c | 13 ++++++++++++- lib/gl_avltree_list.c | 3 ++- lib/gl_avltreehash_list.c | 3 ++- lib/gl_carray_list.c | 18 +++++++++++++++++- lib/gl_linked_list.c | 3 ++- lib/gl_linkedhash_list.c | 3 ++- lib/gl_list.c | 9 ++++++++- lib/gl_list.h | 16 +++++++++++++++- lib/gl_rbtree_list.c | 3 ++- lib/gl_rbtreehash_list.c | 3 ++- lib/gl_sublist.c | 13 ++++++++++++- 14 files changed, 152 insertions(+), 13 deletions(-) diff --git a/ChangeLog b/ChangeLog index fca5c9f53..a3f490025 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,27 @@ 2008-02-10 Bruno Haible + 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 + * 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 9d481a31a..9fbe5a879 100644 --- 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 , 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 c5e5d830e..143348eda 100644 --- 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 , 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 deb83aea6..f82d01b0b 100644 --- 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 , 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 ff74513d6..f50b6f3dc 100644 --- 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 , 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 195580ed6..ef739fca2 100644 --- 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 , 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 8e0c7d6ed..8b43901e2 100644 --- 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 , 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 8aac2434d..a1bd5eee4 100644 --- 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 , 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 2114c437e..7afecb59a 100644 --- 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 , 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 3f1512d51..9eca9e4e3 100644 --- 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 , 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 1a2f9fb76..ca4f476b3 100644 --- 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 , 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 ee6f96ce6..b4f37e661 100644 --- 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 , 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 faa95cff2..73ba2f653 100644 --- 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 , 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 0760cbd52..19158d02d 100644 --- 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 , 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, -- 2.11.0