Add another run on MacOS and properly guard the posix-dependent tests
(even the compilation).
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
We want to assert that our alignment-guarantees do not exceed the
guarantees of the system-linker or system-allocator on the target
platform. Hence, we check against max_align_t. This is a lower bound,
but not the exact check we actually want. And as it turns out, on m64k
it is too low. Add a static check against 4-byte alignment for m64k as
a workaround.
Reported-by: Michael Biebl
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Describe in a comment why c_rbtree_entry() uses the slightly odd style
of duplucate offsetof() expressions to avoid multiple-evaluation of its
argument-pointers.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Make sure to only conditionalize the execution of test-parallel on the
ptrace option, but always build the test for better coverage.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Declare the meson dependency in our build files, so older meson versions
will not erroneously try to build the projects.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Use the new c-util CI workflow and avoid the old combined github-action.
This will run jobs in parallel and reduce the amount of hacks required
for the CI to work significantly.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Define a new 'ptrace' option to replace the old TEST_RUN_PTRACE
environment variable. This is much cleaner and avoids relying on random
environment variables for communication.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Rather than relying on git-submodules, use the built-in dependency
handling of meson. Meson wrap-files allow to integrate versioned
dependencies.
Adjust the entire build system to use the new features.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Convert the private/shared builds to the new meson function
`both_libraries()`. This combines both builds into a single definition.
Furthermore, it allows us to drop the deprecated (and in some scenarios
broken) x.extract_all_objects().
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
We sometimes store pointers to `CRBTree` in `CRBNode*` variables, so we
must make sure CRBTree has matching alignment guarantees. We already
check for that with static-assertions.
This commit aligns CRBTree with CRBNode for 2-byte aligned machines.
While at it, add a short comment explaining what the unions are for.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
On m68k, 32bit integer are aligned to only 2 bytes. This breaks
assumptions and a static assertion of c-rbtree.
Explicitly require that the first field is aligned to at least 4 bytes.
This fixes the build and ensures that all valid pointers to a CRBTree have
the lowest two bits unset (so they can be used for storing 2 additional flags).
Use a union instead of aligning __parent_and_flags itself. That is
because alignas() cannot lower the natural alignment, so if we would
want to align __parent_and_flags, we could only do
alignas(sizeof(unsigned long) > 4 ? sizeof(unsigned long) : 4)
That would not be correct if "long" is 8 bytes long but had a natural
alignment of only 4. The union allows us to specify an alignment
of at least 4, but otherwise follow natural alignment.
There are some Debian-supported architectures where `max_align_t` is
only aligned to 4-bytes. This is unfortunate and breaks our assumptions.
While glibc-malloc still guarantees 8 / 16 bytes alignment, this is not
necessarily guaranteed by the C standard (and alternative allocators
will deviate (see jemalloc, for instance)).
Fortunately, we only need 2 flags, so a 4-byte alignment is more than
enough.
Reported-by: Thomas Haller
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
Enable an additional CI round which has ptrace-tests enabled. These
cannot be pulled in by dependent projects, nor can we run these through
unprivileged containers or valgrind.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
We want c-stdaux to replace our hand-crafting preprocessor macros. Pull
it in as submodule.
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
As it turns out, -DNDEBUG is used by several distributions as the
default meson options. Lets add a preliminary CI run to c-rbtree to see
whether we can test reliably for this and catch any compile-time
warnings.
Reported-by: Thomas Haller <thaller@redhat.com>
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
On armv7hl the PTRACE_SINGLESTEP call is no longer supported. Make sure
we skip the test in this case.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
Skip the full-matrix build on secondary CI systems, but use just the
default to keep build-times low.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
Now that the root-node contains a back-pointer to the tree-root, we
need an explicit helper to move trees. Provide c_rbtree_move().
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
There is no reason to use the _stale() version. Get rid of it and make
the code easier to follow.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
We previously incorrectly updated the symbol file. We broke ABI
intentionally (there is no stable release yet), so we must correctly
bump the versions.
We could theoretically keep some older ABI versions on some of the
functions, but there seems little reason to do so after breaking the
main entry points. Lets just bump all of the symbols.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
We reserve the lower three bits of __parent_and_color for flags, and
rely on the parent pointer being 64-bit aligned. This was already
enforced for CRBNode, but the parent can also be a CRBTree pointer
in case of the root node.
Signed-off-by: Tom Gundersen <teg@jklm.no>
Split this function into two, one that does recursive recoloring, and
one that performs tree-rotations to terminate the rebalance operation.
While at it, update the comment-style to be more consistent.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
Rather than hiding the recursing somewhere in c_rbtree_paint{,_one}(),
make it explicit. This allows us to more precicely argue about the
number of rotations we perform (and where we perform them).
While at it, document the procedure more thoroughly.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
Make c_rbnode_unlink() work like c_rbnode_unlink_init() used to, and rename the
old c_rbnode_unlink() to c_rbnode_unlink_stale(). This is meant to encourage the
use of the former, and for people to only use the stale version in the extremely
rare case that it affects performance.
Signed-off-by: Tom Gundersen <teg@jklm.no>
Keep the pop/push functions as they were intended. They surround a block
of rb-tree modifications, and make sure that the root-cache survives
those modifications. The code block can pretend the flag does not exist,
and only needs to tell the previous and next upper-most node.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
Not really clear what this is supposed to mean. Drop that fragment,
which rather looks like a stray paste.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
Many intrusive collections allow node removal without access to the
surrounding context. That is, adding a node to a context obviously
requires the context. However, removing it again should work without
access to the context.
Our c-list API does this nicely. Linking is done via c_list_link()
(allowing with or without context access), but unlinking is easy via
c_list_unlink(CList *node). No separate list pointer required, just the
node.
In case of c-rbtree we always wanted the same. A simple way to call
c_rbnode_unlink(CRBNode *node) to remove the node. However, the issue
always was that removing the root-node requires updating the tree-root.
But the nodes themselves do not embed the tree-root.
There are 2 obvious ways to fix that:
1) Embed a pointer to the tree-root in the root-node. Thus, modifying
the root-node grants access to the tree-root.
2) Make the tree-root part of the tree.
The second solution is the more elegant one, but with the downside that
tree-traversals need to be aware that the tree-root is not a valid
node. The c-list helpers do something similar to 2).
Furthermore, 2) also has the downside that the tree-root might no
longer actually be the root-node. This could be fixed by rotating with
a fixed tree-root. However, this easily becomes confusing.
Nevertheless, this solution would still provide O(log(n)) access.
The first solution is less elegant, but with the upside of keeping the
API clean. Hence, this is what is implemented here:
The root-node of any tree now uses the 'parent' pointer to store a
pointer to the tree-root. We introduce an additional flag which
marks a root-node as such. This way, whenever we modify it, we know
whether it is the root-node, and additionally get a pointer to the
tree-root.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
Rename the function to better represent what it does. Furthermore, the
RBTree parameter will be gone soon as well.
Signed-off-by: David Herrmann <dh.herrmann@gmail.com>