oset: Add an 'update' operation

[Bruno Haible]

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  <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.

0001-oset-Add-an-update-operation.patch
Description: Text Data