# HG changeset patch # User Bruno Haible # Date 1202668554 -3600 # Node ID 25f7280c9cf0386c30fd93601f8860462220b995 # Parent 2858c91c7452c3ed2318f7676a0f1c9a616f8d3a New abstract list operation 'node_set_value'. diff --git a/ChangeLog b/ChangeLog --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,25 @@ +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". diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h --- 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 @@ 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 --- 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 @@ 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 --- 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 @@ 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, diff --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c --- 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 @@ 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 --- 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 @@ 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 --- 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 @@ 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, diff --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c --- 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 @@ 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 --- 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 @@ 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 --- 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 @@ ->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 --- 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 @@ 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) diff --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c --- 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 @@ 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 --- 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 @@ 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 --- 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 @@ 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,