diff options
| -rw-r--r-- | ChangeLog | 49 | ||||
| -rw-r--r-- | lib/gl_anytree_oset.h | 124 | ||||
| -rw-r--r-- | lib/gl_array_oset.c | 111 | ||||
| -rw-r--r-- | lib/gl_avltree_omap.c | 2 | ||||
| -rw-r--r-- | lib/gl_avltree_ordered.h | 56 | ||||
| -rw-r--r-- | lib/gl_avltree_oset.c | 3 | ||||
| -rw-r--r-- | lib/gl_oset.h | 25 | ||||
| -rw-r--r-- | lib/gl_oset.hh | 18 | ||||
| -rw-r--r-- | lib/gl_rbtree_omap.c | 2 | ||||
| -rw-r--r-- | lib/gl_rbtree_ordered.h | 54 | ||||
| -rw-r--r-- | lib/gl_rbtree_oset.c | 3 | ||||
| -rw-r--r-- | modules/array-oset-tests | 1 | ||||
| -rw-r--r-- | modules/avltree-oset | 1 | ||||
| -rw-r--r-- | modules/avltree-oset-tests | 1 | ||||
| -rw-r--r-- | modules/rbtree-oset | 1 | ||||
| -rw-r--r-- | modules/rbtree-oset-tests | 1 | ||||
| -rw-r--r-- | tests/test-array_oset.c | 4 | ||||
| -rw-r--r-- | tests/test-avltree_oset.c | 4 | ||||
| -rw-r--r-- | tests/test-oset-c++.cc | 44 | ||||
| -rw-r--r-- | tests/test-oset-update.h | 141 | ||||
| -rw-r--r-- | tests/test-rbtree_oset.c | 4 |
21 files changed, 591 insertions, 58 deletions
@@ -1,3 +1,52 @@ +2020-07-20 Bruno Haible <bruno@clisp.org> + + oset: Add an 'update' operation. + * lib/gl_array_oset.c (gl_array_update): New function. + (gl_array_oset_implementation): Use it. + * lib/gl_avltree_omap.c (NODE_PAYLOAD_DISPOSE): Add parameters. + * lib/gl_rbtree_omap.c (NODE_PAYLOAD_DISPOSE): Add parameters. + * lib/gl_avltree_ordered.h (gl_tree_add_node_before): New function, + extracted from gl_tree_nx_add_before. + (gl_tree_nx_add_before): Invoke it. + (gl_tree_add_node_after): New function, extracted from + gl_tree_nx_add_after. + (gl_tree_nx_add_after): Invoke it. + (gl_tree_remove_node_no_free): New function, extracted from + gl_tree_remove_node. + (gl_tree_remove_node): Invoke it. + * lib/gl_rbtree_ordered.h (gl_tree_add_node_before): New function, + extracted from gl_tree_nx_add_before. + (gl_tree_nx_add_before): Invoke it. + (gl_tree_add_node_after): New function, extracted from + gl_tree_nx_add_after. + (gl_tree_nx_add_after): Invoke it. + (gl_tree_remove_node_no_free): New function, extracted from + gl_tree_remove_node. + (gl_tree_remove_node): Invoke it. + * lib/gl_anytree_oset.h (gl_tree_next_node): New function, extracted + from gl_tree_iterator_next. + (gl_tree_iterator_next): Invoke it. + (gl_tree_prev_node, gl_tree_update): New functions. + * lib/gl_avltree_oset.c (NODE_PAYLOAD_DISPOSE): Add parameters. + (gl_avltree_oset_implementation): Use gl_tree_update. + * lib/gl_rbtree_oset.c (NODE_PAYLOAD_DISPOSE): Add parameters. + (gl_rbtree_oset_implementation): Use gl_tree_update. + * lib/gl_oset.h (struct gl_oset_implementation): Add 'update' member. + (gl_oset_update): New function. + * lib/gl_oset.hh (gl_OSet): Add 'update' member. + * modules/avltree-oset (configure.ac): Require AC_C_INLINE. + * modules/rbtree-oset (configure.ac): Likewise. + * tests/test-oset-update.h: New file. + * tests/test-array_oset.c: Include test-oset-update.h. + (main): Invoke test_update. + * tests/test-avltree_oset.c: Likewise. + * tests/test-rbtree_oset.c: Likewise. + * modules/array-oset-tests (Files): Add tests/test-oset-update.h. + * modules/avltree-oset-tests (Files): Likewise. + * modules/rbtree-oset-tests (Files): Likewise. + * tests/test-oset-c++.cc (action): New function. + (main): Test the 'update' member function. + 2020-07-15 Paul Eggert <eggert@cs.ucla.edu> md5, sha1, sha256, sha512: pacify Autoconf 2.70 diff --git a/lib/gl_anytree_oset.h b/lib/gl_anytree_oset.h index d737e313d7..8a64229b25 100644 --- a/lib/gl_anytree_oset.h +++ b/lib/gl_anytree_oset.h @@ -53,6 +53,44 @@ gl_tree_size (gl_oset_t set) return set->count; } +/* Returns the next node in the tree, or NULL if there is none. */ +static inline gl_oset_node_t +gl_tree_next_node (gl_oset_node_t node) +{ + if (node->right != NULL) + { + node = node->right; + while (node->left != NULL) + node = node->left; + } + else + { + while (node->parent != NULL && node->parent->right == node) + node = node->parent; + node = node->parent; + } + return node; +} + +/* Returns the previous node in the tree, or NULL if there is none. */ +static inline gl_oset_node_t +gl_tree_prev_node (gl_oset_node_t node) +{ + if (node->left != NULL) + { + node = node->left; + while (node->right != NULL) + node = node->right; + } + else + { + while (node->parent != NULL && node->parent->left == node) + node = node->parent; + node = node->parent; + } + return node; +} + static bool gl_tree_search (gl_oset_t set, const void *elt) { @@ -194,6 +232,79 @@ gl_tree_remove (gl_oset_t set, const void *elt) return false; } +static int +gl_tree_update (gl_oset_t set, const void *elt, + void (*action) (const void * /*elt*/, void * /*action_data*/), + void *action_data) +{ + /* Like gl_tree_remove, action (...), gl_tree_nx_add, except that we don't + actually remove ELT. */ + /* Remember the old node. Don't free it. */ + gl_oset_node_t old_node = gl_tree_search_node (set, elt); + /* Invoke ACTION. */ + action (elt, action_data); + /* Determine where to put the node now. */ + if (old_node != NULL) + { + if (set->count > 1) + { + gl_setelement_compar_fn compar = set->base.compar_fn; + + gl_oset_node_t prev_node = gl_tree_prev_node (old_node); + gl_oset_node_t next_node = gl_tree_next_node (old_node); + if (!(compar != NULL + ? (prev_node == NULL || compar (prev_node->value, elt) < 0) + && (next_node == NULL || compar (next_node->value, elt) > 0) + : (prev_node == NULL || prev_node->value < elt) + && (next_node == NULL || next_node->value > elt))) + { + /* old_node needs to move in the tree. */ + gl_oset_node_t node; + + /* Remove the node from the tree. Don't free it. */ + gl_tree_remove_node_no_free (set, old_node); + + node = set->root; + + for (;;) + { + int cmp = (compar != NULL + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); + + if (cmp < 0) + { + if (node->right == NULL) + { + gl_tree_add_node_after (set, node, old_node); + return true; + } + node = node->right; + } + else if (cmp > 0) + { + if (node->left == NULL) + { + gl_tree_add_node_before (set, node, old_node); + return true; + } + node = node->left; + } + else /* cmp == 0 */ + { + /* Two elements are the same. */ + NODE_PAYLOAD_DISPOSE (set, old_node) + free (old_node); + return -1; + } + } + } + } + } + return 0; +} + static void gl_tree_oset_free (gl_oset_t set) { @@ -272,18 +383,7 @@ gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) gl_oset_node_t node = (gl_oset_node_t) iterator->p; *eltp = node->value; /* Advance to the next node. */ - if (node->right != NULL) - { - node = node->right; - while (node->left != NULL) - node = node->left; - } - else - { - while (node->parent != NULL && node->parent->right == node) - node = node->parent; - node = node->parent; - } + node = gl_tree_next_node (node); iterator->p = node; return true; } diff --git a/lib/gl_array_oset.c b/lib/gl_array_oset.c index c4dd292bff..86fb747b68 100644 --- a/lib/gl_array_oset.c +++ b/lib/gl_array_oset.c @@ -267,6 +267,116 @@ gl_array_remove (gl_oset_t set, const void *elt) return false; } +static int +gl_array_update (gl_oset_t set, const void *elt, + void (*action) (const void * /*elt*/, void * /*action_data*/), + void *action_data) +{ + /* Like gl_array_remove, action (...), gl_array_nx_add, except that we don't + actually remove ELT. */ + /* Remember the old position. */ + size_t old_index = gl_array_indexof (set, elt); + /* Invoke ACTION. */ + action (elt, action_data); + /* Determine the new position. */ + if (old_index != (size_t)(-1)) + { + size_t count = set->count; + + if (count > 1) + { + gl_setelement_compar_fn compar = set->base.compar_fn; + size_t low; + size_t high; + + if (old_index > 0) + { + size_t mid = old_index - 1; + int cmp = (compar != NULL + ? compar (set->elements[mid], elt) + : (set->elements[mid] > elt ? 1 : + set->elements[mid] < elt ? -1 : 0)); + if (cmp < 0) + { + low = old_index + 1; + high = count; + } + else if (cmp > 0) + { + low = 0; + high = mid; + } + else /* cmp == 0 */ + { + /* Two adjacent elements are the same. */ + gl_array_remove_at (set, old_index); + return -1; + } + } + else + { + low = old_index + 1; + high = count; + } + + /* At each loop iteration, low <= high; for indices < low the values + are smaller than ELT; for indices >= high the values are greater + than ELT. So, if the element occurs in the list, it is at + low <= position < high. */ + while (low < high) + { + size_t mid = low + (high - low) / 2; /* low <= mid < high */ + int cmp = (compar != NULL + ? compar (set->elements[mid], elt) + : (set->elements[mid] > elt ? 1 : + set->elements[mid] < elt ? -1 : 0)); + + if (cmp < 0) + low = mid + 1; + else if (cmp > 0) + high = mid; + else /* cmp == 0 */ + { + /* Two elements are the same. */ + gl_array_remove_at (set, old_index); + return -1; + } + } + + if (low < old_index) + { + /* Move the element from old_index to low. */ + size_t new_index = low; + const void **elements = set->elements; + size_t i; + + for (i = old_index; i > new_index; i--) + elements[i] = elements[i - 1]; + elements[new_index] = elt; + return true; + } + else + { + /* low > old_index. */ + /* Move the element from old_index to low - 1. */ + size_t new_index = low - 1; + + if (new_index > old_index) + { + const void **elements = set->elements; + size_t i; + + for (i = old_index; i < new_index; i++) + elements[i] = elements[i + 1]; + elements[new_index] = elt; + return true; + } + } + } + } + return false; +} + static void gl_array_free (gl_oset_t set) { @@ -350,6 +460,7 @@ const struct gl_oset_implementation gl_array_oset_implementation = gl_array_search_atleast, gl_array_nx_add, gl_array_remove, + gl_array_update, gl_array_free, gl_array_iterator, gl_array_iterator_next, diff --git a/lib/gl_avltree_omap.c b/lib/gl_avltree_omap.c index e3d9e11a90..7d44709fae 100644 --- a/lib/gl_avltree_omap.c +++ b/lib/gl_avltree_omap.c @@ -38,7 +38,7 @@ #define NODE_PAYLOAD_ASSIGN(node) \ node->key = key; \ node->value = value; -#define NODE_PAYLOAD_DISPOSE \ +#define NODE_PAYLOAD_DISPOSE(container, node) \ if (container->base.kdispose_fn != NULL) \ container->base.kdispose_fn (node->key); diff --git a/lib/gl_avltree_ordered.h b/lib/gl_avltree_ordered.h index 014886c23b..d1cc48bfed 100644 --- a/lib/gl_avltree_ordered.h +++ b/lib/gl_avltree_ordered.h @@ -335,21 +335,15 @@ gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS) return new_node; } -static NODE_T -gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +/* Adds the already allocated NEW_NODE to the tree, right before NODE. */ +static void +gl_tree_add_node_before (CONTAINER_T container, NODE_T node, NODE_T new_node) { - /* Create new node. */ - NODE_T new_node = - (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); bool height_inc; - if (new_node == NULL) - return NULL; - new_node->left = NULL; new_node->right = NULL; new_node->balance = 0; - NODE_PAYLOAD_ASSIGN(new_node) /* Add it to the tree. */ if (node->left == NULL) @@ -373,24 +367,33 @@ gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) rebalance (container, node, 1, node->parent); container->count++; - return new_node; } static NODE_T -gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) { /* Create new node. */ NODE_T new_node = (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); - bool height_inc; if (new_node == NULL) return NULL; + NODE_PAYLOAD_ASSIGN(new_node) + + gl_tree_add_node_before (container, node, new_node); + return new_node; +} + +/* Adds the already allocated NEW_NODE to the tree, right after NODE. */ +static void +gl_tree_add_node_after (CONTAINER_T container, NODE_T node, NODE_T new_node) +{ + bool height_inc; + new_node->left = NULL; new_node->right = NULL; new_node->balance = 0; - NODE_PAYLOAD_ASSIGN(new_node) /* Add it to the tree. */ if (node->right == NULL) @@ -414,11 +417,26 @@ gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) rebalance (container, node, 1, node->parent); container->count++; +} + +static NODE_T +gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +{ + /* Create new node. */ + NODE_T new_node = + (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); + + if (new_node == NULL) + return NULL; + + NODE_PAYLOAD_ASSIGN(new_node) + + gl_tree_add_node_after (container, node, new_node); return new_node; } -static bool -gl_tree_remove_node (CONTAINER_T container, NODE_T node) +static void +gl_tree_remove_node_no_free (CONTAINER_T container, NODE_T node) { NODE_T parent = node->parent; @@ -519,7 +537,13 @@ gl_tree_remove_node (CONTAINER_T container, NODE_T node) } container->count--; - NODE_PAYLOAD_DISPOSE +} + +static bool +gl_tree_remove_node (CONTAINER_T container, NODE_T node) +{ + gl_tree_remove_node_no_free (container, node); + NODE_PAYLOAD_DISPOSE (container, node) free (node); return true; } diff --git a/lib/gl_avltree_oset.c b/lib/gl_avltree_oset.c index 73b8188c00..34de5a23bb 100644 --- a/lib/gl_avltree_oset.c +++ b/lib/gl_avltree_oset.c @@ -36,7 +36,7 @@ const void *elt #define NODE_PAYLOAD_ASSIGN(node) \ node->value = elt; -#define NODE_PAYLOAD_DISPOSE \ +#define NODE_PAYLOAD_DISPOSE(container, node) \ if (container->base.dispose_fn != NULL) \ container->base.dispose_fn (node->value); @@ -64,6 +64,7 @@ const struct gl_oset_implementation gl_avltree_oset_implementation = gl_tree_search_atleast, gl_tree_nx_add, gl_tree_remove, + gl_tree_update, gl_tree_oset_free, gl_tree_iterator, gl_tree_iterator_next, diff --git a/lib/gl_oset.h b/lib/gl_oset.h index 672527cd39..2908297f2c 100644 --- a/lib/gl_oset.h +++ b/lib/gl_oset.h @@ -65,6 +65,7 @@ extern "C" { gl_oset_size O(1) O(1) gl_oset_add O(n) O(log n) gl_oset_remove O(n) O(log n) + gl_oset_update O(n) O(log n) gl_oset_search O(log n) O(log n) gl_oset_search_atleast O(log n) O(log n) gl_oset_iterator O(1) O(log n) @@ -140,6 +141,18 @@ extern int gl_oset_nx_add (gl_oset_t set, const void *elt) Returns true if it was found and removed. */ extern bool gl_oset_remove (gl_oset_t set, const void *elt); +/* Invokes ACTION (ELT, ACTION_DATA) and updates the given ordered set if, + during this invocation, the attributes/properties of the element ELT change + in a way that influences the comparison function. + Warning: During the invocation of ACTION, the ordered set is inconsistent + and must not be accessed! + Returns 1 if the position of the element in the ordered set has changed as + a consequence, 0 if the element stayed at the same position, or -1 if it + collided with another element and was therefore removed. */ +extern int gl_oset_update (gl_oset_t set, const void *elt, + void (*action) (const void *elt, void *action_data), + void *action_data); + /* Frees an entire ordered set. (But this call does not free the elements of the set. It only invokes the DISPOSE_FN on each of the elements of the set.) */ @@ -198,6 +211,9 @@ struct gl_oset_implementation const void *threshold, const void **eltp); int (*nx_add) (gl_oset_t set, const void *elt); bool (*remove_elt) (gl_oset_t set, const void *elt); + int (*update) (gl_oset_t set, const void *elt, + void (*action) (const void * /*elt*/, void * /*action_data*/), + void *action_data); void (*oset_free) (gl_oset_t set); /* gl_oset_iterator_t functions. */ gl_oset_iterator_t (*iterator) (gl_oset_t set); @@ -258,6 +274,15 @@ gl_oset_remove (gl_oset_t set, const void *elt) ->remove_elt (set, elt); } +GL_OSET_INLINE int +gl_oset_update (gl_oset_t set, const void *elt, + void (*action) (const void * /*elt*/, void * /*action_data*/), + void *action_data) +{ + return ((const struct gl_oset_impl_base *) set)->vtable + ->update (set, elt, action, action_data); +} + GL_OSET_INLINE void gl_oset_free (gl_oset_t set) { diff --git a/lib/gl_oset.hh b/lib/gl_oset.hh index b78ef52802..5a72476229 100644 --- a/lib/gl_oset.hh +++ b/lib/gl_oset.hh @@ -97,6 +97,24 @@ public: bool remove (ELTYPE * elt) { return gl_oset_remove (_ptr, elt); } + /* Invokes ACTION (ELT, ACTION_DATA) and updates the ordered set if, + during this invocation, the attributes/properties of the element ELT change + in a way that influences the comparison function. + Warning: During the invocation of ACTION, the ordered set is inconsistent + and must not be accessed! + Returns 1 if the position of the element in the ordered set has changed as + a consequence, 0 if the element stayed at the same position, or -1 if it + collided with another element and was therefore removed. */ + template <typename DT> + int update (ELTYPE * elt, + void (*action) (ELTYPE * /*elt*/, DT * /*action_data*/), + DT *action_data) + { + return gl_oset_update (_ptr, elt, + reinterpret_cast<void (*) (const void *, void *)> (action), + action_data); + } + /* Frees the entire ordered set. (But this call does not free the elements of the set. It only invokes the DISPOSE_FN on each of the elements of the set.) */ diff --git a/lib/gl_rbtree_omap.c b/lib/gl_rbtree_omap.c index d91c95e5a2..d16bd23626 100644 --- a/lib/gl_rbtree_omap.c +++ b/lib/gl_rbtree_omap.c @@ -38,7 +38,7 @@ #define NODE_PAYLOAD_ASSIGN(node) \ node->key = key; \ node->value = value; -#define NODE_PAYLOAD_DISPOSE \ +#define NODE_PAYLOAD_DISPOSE(container, node) \ if (container->base.kdispose_fn != NULL) \ container->base.kdispose_fn (node->key); diff --git a/lib/gl_rbtree_ordered.h b/lib/gl_rbtree_ordered.h index f7a5988e57..8625afef46 100644 --- a/lib/gl_rbtree_ordered.h +++ b/lib/gl_rbtree_ordered.h @@ -565,19 +565,12 @@ gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS) return new_node; } -static NODE_T -gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +/* Adds the already allocated NEW_NODE to the tree, right before NODE. */ +static void +gl_tree_add_node_before (CONTAINER_T container, NODE_T node, NODE_T new_node) { - /* Create new node. */ - NODE_T new_node = - (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); - - if (new_node == NULL) - return NULL; - new_node->left = NULL; new_node->right = NULL; - NODE_PAYLOAD_ASSIGN(new_node) /* Add it to the tree. */ if (node->left == NULL) @@ -594,11 +587,10 @@ gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) rebalance_after_add (container, new_node, node); container->count++; - return new_node; } static NODE_T -gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) { /* Create new node. */ NODE_T new_node = @@ -607,9 +599,18 @@ gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) if (new_node == NULL) return NULL; + NODE_PAYLOAD_ASSIGN(new_node) + + gl_tree_add_node_before (container, node, new_node); + return new_node; +} + +/* Adds the already allocated NEW_NODE to the tree, right after NODE. */ +static void +gl_tree_add_node_after (CONTAINER_T container, NODE_T node, NODE_T new_node) +{ new_node->left = NULL; new_node->right = NULL; - NODE_PAYLOAD_ASSIGN(new_node) /* Add it to the tree. */ if (node->right == NULL) @@ -626,11 +627,26 @@ gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) rebalance_after_add (container, new_node, node); container->count++; +} + +static NODE_T +gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +{ + /* Create new node. */ + NODE_T new_node = + (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); + + if (new_node == NULL) + return NULL; + + NODE_PAYLOAD_ASSIGN(new_node) + + gl_tree_add_node_after (container, node, new_node); return new_node; } -static bool -gl_tree_remove_node (CONTAINER_T container, NODE_T node) +static void +gl_tree_remove_node_no_free (CONTAINER_T container, NODE_T node) { NODE_T parent = node->parent; @@ -749,7 +765,13 @@ gl_tree_remove_node (CONTAINER_T container, NODE_T node) } container->count--; - NODE_PAYLOAD_DISPOSE +} + +static bool +gl_tree_remove_node (CONTAINER_T container, NODE_T node) +{ + gl_tree_remove_node_no_free (container, node); + NODE_PAYLOAD_DISPOSE (container, node) free (node); return true; } diff --git a/lib/gl_rbtree_oset.c b/lib/gl_rbtree_oset.c index 29bded5110..064c0c4048 100644 --- a/lib/gl_rbtree_oset.c +++ b/lib/gl_rbtree_oset.c @@ -36,7 +36,7 @@ const void *elt #define NODE_PAYLOAD_ASSIGN(node) \ node->value = elt; -#define NODE_PAYLOAD_DISPOSE \ +#define NODE_PAYLOAD_DISPOSE(container, node) \ if (container->base.dispose_fn != NULL) \ container->base.dispose_fn (node->value); @@ -64,6 +64,7 @@ const struct gl_oset_implementation gl_rbtree_oset_implementation = gl_tree_search_atleast, gl_tree_nx_add, gl_tree_remove, + gl_tree_update, gl_tree_oset_free, gl_tree_iterator, gl_tree_iterator_next, diff --git a/modules/array-oset-tests b/modules/array-oset-tests index 2ccc86f73a..aac2a3c3d7 100644 --- a/modules/array-oset-tests +++ b/modules/array-oset-tests @@ -1,5 +1,6 @@ Files: tests/test-array_oset.c +tests/test-oset-update.h tests/macros.h Depends-on: diff --git a/modules/avltree-oset b/modules/avltree-oset index 5bdb482e8f..31ed0e6a02 100644 --- a/modules/avltree-oset +++ b/modules/avltree-oset @@ -11,6 +11,7 @@ Depends-on: oset configure.ac: +AC_REQUIRE([AC_C_INLINE]) Makefile.am: lib_SOURCES += gl_avltree_oset.h gl_avltree_oset.c gl_avltree_ordered.h gl_anytree_oset.h diff --git a/modules/avltree-oset-tests b/modules/avltree-oset-tests index 2cb98e0e4f..485c68a8c1 100644 --- a/modules/avltree-oset-tests +++ b/modules/avltree-oset-tests @@ -1,5 +1,6 @@ Files: tests/test-avltree_oset.c +tests/test-oset-update.h tests/macros.h Depends-on: diff --git a/modules/rbtree-oset b/modules/rbtree-oset index 7b7d3ca9d1..410c0d7662 100644 --- a/modules/rbtree-oset +++ b/modules/rbtree-oset @@ -11,6 +11,7 @@ Depends-on: oset configure.ac: +AC_REQUIRE([AC_C_INLINE]) Makefile.am: lib_SOURCES += gl_rbtree_oset.h gl_rbtree_oset.c gl_rbtree_ordered.h gl_anytree_oset.h diff --git a/modules/rbtree-oset-tests b/modules/rbtree-oset-tests index 366faf23cc..bac509446f 100644 --- a/modules/rbtree-oset-tests +++ b/modules/rbtree-oset-tests @@ -1,5 +1,6 @@ Files: tests/test-rbtree_oset.c +tests/test-oset-update.h tests/macros.h Depends-on: diff --git a/tests/test-array_oset.c b/tests/test-array_oset.c index 21d2b04018..6a7fd36f33 100644 --- a/tests/test-array_oset.c +++ b/tests/test-array_oset.c @@ -26,6 +26,8 @@ #include "gl_array_list.h" #include "macros.h" +#include "test-oset-update.h" + static const char *objects[30] = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", @@ -137,5 +139,7 @@ main (int argc, char *argv[]) gl_list_free (set2); } + test_update (GL_ARRAY_OSET); + return 0; } diff --git a/tests/test-avltree_oset.c b/tests/test-avltree_oset.c index 3502766d71..65e2d321f6 100644 --- a/tests/test-avltree_oset.c +++ b/tests/test-avltree_oset.c @@ -25,6 +25,8 @@ #include "gl_array_oset.h" #include "macros.h" +#include "test-oset-update.h" + extern void gl_avltree_oset_check_invariants (gl_oset_t set); static const char *objects[30] = @@ -129,5 +131,7 @@ main (int argc, char *argv[]) gl_oset_free (set2); } + test_update (GL_AVLTREE_OSET); + return 0; } diff --git a/tests/test-oset-c++.cc b/tests/test-oset-c++.cc index c737675046..e7eb86e67a 100644 --- a/tests/test-oset-c++.cc +++ b/tests/test-oset-c++.cc @@ -31,27 +31,51 @@ reverse_strcmp (const char *str1, const char *str2) return (cmp > 0 ? -1 : cmp < 0 ? 1 : 0); } +static void +action (const char *str, int *data) +{ + const_cast<char *> (str) [0] += *data; +} + int main (int argc, char *argv[]) { + char A[2] = "A"; gl_OSet<const char *> set1; set1 = gl_OSet<const char *> (GL_ARRAY_OSET, reverse_strcmp, NULL); - set1.add ("A"); + set1.add (A); set1.add ("C"); set1.add ("D"); set1.add ("C"); ASSERT (set1.size () == 3); - gl_OSet<const char *>::iterator iter1 = set1.begin (); - const char *elt; - ASSERT (iter1.next (elt)); - ASSERT (strcmp (elt, "D") == 0); - ASSERT (iter1.next (elt)); - ASSERT (strcmp (elt, "C") == 0); - ASSERT (iter1.next (elt)); - ASSERT (strcmp (elt, "A") == 0); - ASSERT (!iter1.next (elt)); + { + gl_OSet<const char *>::iterator iter1 = set1.begin (); + const char *elt; + ASSERT (iter1.next (elt)); + ASSERT (strcmp (elt, "D") == 0); + ASSERT (iter1.next (elt)); + ASSERT (strcmp (elt, "C") == 0); + ASSERT (iter1.next (elt)); + ASSERT (strcmp (elt, "A") == 0); + ASSERT (!iter1.next (elt)); + } + + int data = 'Z' - 'A'; + ASSERT (set1.update (A, action, &data) == 1); + + { + gl_OSet<const char *>::iterator iter2 = set1.begin (); + const char *elt; + ASSERT (iter2.next (elt)); + ASSERT (strcmp (elt, "Z") == 0); + ASSERT (iter2.next (elt)); + ASSERT (strcmp (elt, "D") == 0); + ASSERT (iter2.next (elt)); + ASSERT (strcmp (elt, "C") == 0); + ASSERT (!iter2.next (elt)); + } set1.free (); diff --git a/tests/test-oset-update.h b/tests/test-oset-update.h new file mode 100644 index 0000000000..070f56b4bb --- /dev/null +++ b/tests/test-oset-update.h @@ -0,0 +1,141 @@ +/* Test of ordered set data type implementation. + Copyright (C) 2020 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2020. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +static void +action (const void *str, void *data) +{ + ((char *) str)[0] += *(int *)data; +} + +static void +test_update (gl_oset_implementation_t implementation) +{ + char A[2] = "A"; + char B[2] = "B"; + char C[2] = "C"; + char D[2] = "D"; + + gl_oset_t set1 = + gl_oset_nx_create_empty (implementation, (gl_setelement_compar_fn) strcmp, NULL); + ASSERT (set1 != NULL); + + /* Fill the set. */ + ASSERT (gl_oset_nx_add (set1, C) == 1); + ASSERT (gl_oset_nx_add (set1, A) == 1); + ASSERT (gl_oset_nx_add (set1, B) == 1); + ASSERT (gl_oset_nx_add (set1, D) == 1); + + /* Verify that set1 = ["A", "B", "C", "D"]. */ + { + gl_oset_iterator_t iter = gl_oset_iterator (set1); + const void *elt; + + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == A); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == B); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == C); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == D); + ASSERT (!gl_oset_iterator_next (&iter, &elt)); + } + + /* Make a side effect on an element in the set, that moves the element. */ + { + int data = 'G' - 'B'; + ASSERT (gl_oset_update (set1, B, action, &data) == 1); + } + /* Verify that set1 = ["A", "C", "D", "G"]. */ + { + gl_oset_iterator_t iter = gl_oset_iterator (set1); + const void *elt; + + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == A); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == C); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == D); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == B); + ASSERT (!gl_oset_iterator_next (&iter, &elt)); + } + + /* Make a side effect on an element in the set, that does not move the + element. */ + { + int data = 'E' - 'D'; + ASSERT (gl_oset_update (set1, D, action, &data) == 0); + } + /* Verify that set1 = ["A", "C", "E", "G"]. */ + { + gl_oset_iterator_t iter = gl_oset_iterator (set1); + const void *elt; + + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == A); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == C); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == D); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == B); + ASSERT (!gl_oset_iterator_next (&iter, &elt)); + } + + /* Make a side effect on an element in the set, that provokes a + collision. */ + { + int data = 'G' - 'A'; + ASSERT (gl_oset_update (set1, A, action, &data) == -1); + } + /* Verify that set1 = ["C", "E", "G"]. */ + { + gl_oset_iterator_t iter = gl_oset_iterator (set1); + const void *elt; + + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == C); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == D); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == B); + ASSERT (!gl_oset_iterator_next (&iter, &elt)); + } + + /* Make a side effect on an element that is not in the set. */ + { + int data = 'R' - 'G'; + ASSERT (gl_oset_update (set1, A, action, &data) == 0); + } + /* Verify that set1 = ["C", "E", "G"]. */ + { + gl_oset_iterator_t iter = gl_oset_iterator (set1); + const void *elt; + + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == C); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == D); + ASSERT (gl_oset_iterator_next (&iter, &elt)); + ASSERT (elt == B); + ASSERT (!gl_oset_iterator_next (&iter, &elt)); + } + + gl_oset_free (set1); +} diff --git a/tests/test-rbtree_oset.c b/tests/test-rbtree_oset.c index 44e081604c..29f844a102 100644 --- a/tests/test-rbtree_oset.c +++ b/tests/test-rbtree_oset.c @@ -25,6 +25,8 @@ #include "gl_array_oset.h" #include "macros.h" +#include "test-oset-update.h" + extern void gl_rbtree_oset_check_invariants (gl_oset_t set); static const char *objects[30] = @@ -129,5 +131,7 @@ main (int argc, char *argv[]) gl_oset_free (set2); } + test_update (GL_RBTREE_OSET); + return 0; } |