A gl_oset_t keeps itself in sorted order when elements are inserted or removed.
In some applications, an element needs to be removed from the set, then it
gets modified in some way, then it gets added again - but at a different
position since its sorting key is different now.
The problem here - for code that does not use xmalloc() - is that adding the
modified element may cause an allocation failure. This is unwelcome. (In my
current use-case, the elements are "free-list" elements, and an allocation
failure means a leak.)
The 'update' operation is a removal and an addition of the same element at
a possibly different position. Since it reuses the tree node from the removal,
there is no possibility of an allocation failure.
Also, often the new position and the old position are the same or nearby;
in this case the 'update' operation is also faster than removal and subsequent
addition.
2020-07-20 Bruno Haible <br...@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.
>From 91af6d7383aad01cd43b45dd733b027065743d00 Mon Sep 17 00:00:00 2001
From: Bruno Haible <br...@clisp.org>
Date: Mon, 20 Jul 2020 20:06:29 +0200
Subject: [PATCH] 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.
---
ChangeLog | 49 ++++++++++++++++
lib/gl_anytree_oset.h | 124 +++++++++++++++++++++++++++++++++++----
lib/gl_array_oset.c | 111 +++++++++++++++++++++++++++++++++++
lib/gl_avltree_omap.c | 2 +-
lib/gl_avltree_ordered.h | 56 +++++++++++++-----
lib/gl_avltree_oset.c | 3 +-
lib/gl_oset.h | 25 ++++++++
lib/gl_oset.hh | 18 ++++++
lib/gl_rbtree_omap.c | 2 +-
lib/gl_rbtree_ordered.h | 54 ++++++++++++-----
lib/gl_rbtree_oset.c | 3 +-
modules/array-oset-tests | 1 +
modules/avltree-oset | 1 +
modules/avltree-oset-tests | 1 +
modules/rbtree-oset | 1 +
modules/rbtree-oset-tests | 1 +
tests/test-array_oset.c | 4 ++
tests/test-avltree_oset.c | 4 ++
tests/test-oset-c++.cc | 44 ++++++++++----
tests/test-oset-update.h | 141 +++++++++++++++++++++++++++++++++++++++++++++
tests/test-rbtree_oset.c | 4 ++
21 files changed, 591 insertions(+), 58 deletions(-)
create mode 100644 tests/test-oset-update.h
diff --git a/ChangeLog b/ChangeLog
index bc14818..239c83a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,52 @@
+2020-07-20 Bruno Haible <br...@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 <egg...@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 d737e31..8a64229 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 c4dd292..86fb747 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 e3d9e11..7d44709 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 014886c..d1cc48b 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 73b8188..34de5a2 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 672527c..2908297 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 b78ef52..5a72476 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 d91c95e..d16bd23 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 f7a5988..8625afe 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 29bded5..064c0c4 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 2ccc86f..aac2a3c 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 5bdb482..31ed0e6 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 2cb98e0..485c68a 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 7b7d3ca..410c0d7 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 366faf2..bac5094 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 21d2b04..6a7fd36 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 3502766..65e2d32 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 c737675..e7eb86e 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 0000000..070f56b
--- /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 <br...@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 44e0816..29f844a 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;
}
--
2.7.4
