Commit Graph

125 Commits (main)

Author SHA1 Message Date
alexis d2646776fe A bit more 2022-06-06 19:12:55 -06:00
alexis 3b86f4ae4c Cleanup 2022-06-06 19:02:10 -06:00
David Rheinsberg 7995758e85 ci: run on macos
Add another run on MacOS and properly guard the posix-dependent tests
(even the compilation).

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2022-05-30 11:30:43 +02:00
David Rheinsberg eb778d3969 c-rbtree: fix alignment assertion on m64k
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>
2022-05-18 11:35:05 +02:00
David Rheinsberg 9b9713aeb9 build: update docs
Update the copyright information and NEWS entries.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2022-05-03 10:06:20 +02:00
David Rheinsberg 7d38954dfd c-rbtree: document c_rbtree_entry() better
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>
2022-05-03 10:01:18 +02:00
David Rheinsberg 401241d4db build: always build test-parallel
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>
2022-05-03 09:49:49 +02:00
David Rheinsberg 337eb6c06d build: declare meson dependency
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>
2022-05-02 13:20:49 +02:00
David Rheinsberg 5741c13745 ci: switch to new c-util CI workflow
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>
2022-05-02 12:37:01 +02:00
David Rheinsberg 39f870caf0 build: drop redundant _GNU_SOURCE
Avoid defining _GNU_SOURCE as we now get this through the
c-stdaux-cflags.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2022-05-02 12:36:36 +02:00
David Rheinsberg cd315e186c build: define 'ptrace' option
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>
2022-05-02 12:36:26 +02:00
David Rheinsberg a1fb0a3296 build: drop old submodules
Drop all old submodules now that we use the new dependency handling.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2022-04-13 12:30:25 +02:00
David Rheinsberg 739c1e982d build: re-order build definitions alphabetically
Adjust the argument order to our standard alphabetical ordering.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2022-04-13 12:29:16 +02:00
David Rheinsberg e98d4ed5a8 build: rework dependency handling
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>
2022-04-13 12:26:37 +02:00
David Rheinsberg f9dd3852b8 build: use both_libraries()
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>
2022-03-30 13:09:46 +02:00
David Rheinsberg 8aa7bd1828 build: update submodules
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2021-03-17 11:59:22 +01:00
David Rheinsberg a3b1f80548 build: update submodules
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2020-10-26 08:52:10 +01:00
David Rheinsberg 3162c5c045 build: synchronize AUTHORS
Update all authors in `AUTHORS`, according to the git-shortlog history.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2020-10-21 10:12:05 +02:00
David Rheinsberg c795b7657f c-rbtree: align CRBTree with CRBNode
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>
2020-10-21 10:08:12 +02:00
Thomas Haller 10d973a9e6 c-rbtree: fix struct alignment of CRBTree on m68k architectures
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.
2020-10-21 10:03:45 +02:00
David Rheinsberg bd1c14dc0d c-rbtree: reduce alignment constraints
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>
2020-10-07 15:54:15 +02:00
David Rheinsberg 7624b79b26 ci: switch to c-util automation
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2020-04-16 12:28:50 +02:00
David Rheinsberg c8cf175278 ci: run additional CI with ptrace
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>
2020-02-25 11:58:10 +01:00
David Rheinsberg 7069619bc3 ci: switch to github-actions
Switch the travis-based CI to github-actions.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2020-02-25 11:43:52 +01:00
David Rheinsberg fa97402c3f ci: drop broken armv7hl
Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2019-06-05 16:03:37 +02:00
David Rheinsberg 4d48f58a3c build: update submodules
Pull in build-fixes from c-stdaux.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2019-05-19 11:37:36 +02:00
David Rheinsberg b46392d25d build: use c-stdaux
Make use of the symbols from c-stdaux, now that it is a dependency.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2019-04-10 10:32:27 +02:00
David Rheinsberg 61f21750be build: pull in c-stdaux
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>
2019-04-10 10:27:24 +02:00
David Rheinsberg 31fcf75afe build: sync with c-util
Synchronize the setup with c-util.

Signed-off-by: David Rheinsberg <david.rheinsberg@gmail.com>
2019-04-10 10:25:50 +02:00
David Rheinsberg fec7b8f2da ci: add run with -DNDEBUG
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>
2019-04-09 09:18:31 +02:00
David Herrmann bf627e0c32 test: skip ptrace if SINGLESTEP is not supported
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>
2018-08-02 18:58:24 +02:00
David Herrmann dd309a51b0 build: only run full matrix on default CI
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>
2018-08-02 16:42:36 +02:00
David Herrmann aa40f46a82 build: update CI
Use our new CI infrastructure to get tests on 32bit platforms as well as
64bit.

Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
2018-08-02 16:34:27 +02:00
David Herrmann a5bbab0ee9 build: update build-system
Minor updates to the build-system all over the place.

Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
2018-08-02 16:33:57 +02:00
David Herrmann ba0527e915 c-rbtree: add c_rbtree_move()
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>
2017-12-15 11:22:26 +01:00
David Herrmann 15ecab895f tests: avoid c_rbnode_unlink_stale()
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>
2017-12-15 11:22:26 +01:00
David Herrmann 04f53d1af1 build: fix symbol file
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>
2017-12-15 11:22:26 +01:00
Tom Gundersen 825f626a16 c-rbtree: enforce CRBTree alignment
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>
2017-11-30 13:05:02 +01:00
David Herrmann 674baee687 c-rbtree: split c_rbtree_rebalance()
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>
2017-11-29 14:33:55 +01:00
David Herrmann 284a3d3cf4 c-rbtree: split c_rbtree_paint()
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>
2017-11-29 11:50:17 +01:00
Tom Gundersen bedf49468c c-rbtree: rename c_rbnode_unlink{,_init}
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>
2017-11-24 14:11:08 +01:00
Tom Gundersen d5ab891613 c-rbtree: remove deprecated c_rbtree_remove()
c_rbnode_unlink() should be used instead.

Signed-off-by: Tom Gundersen <teg@jklm.no>
2017-11-24 14:09:30 +01:00
David Herrmann 7cf2eeadcc c-rbtree: keep _{pop,push}_root() logic
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>
2017-11-20 11:21:34 +01:00
David Herrmann 423495fc13 c-rbtree: drop stray comment
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>
2017-11-20 11:21:07 +01:00
David Herrmann b6a6e0bb56 c-rbtree: keep comment style consistent
Keep the comment-block style consistent across a single function.

Signed-off-by: David Herrmann <dh.herrmann@gmail.com>
2017-11-20 11:20:38 +01:00
Tom Gundersen 3a49024572 c-rbtree: refactor c_rbtree_unlink and add more comments
Only minor refactoring for clarity.

Signed-off-by: Tom Gundersen <teg@jklm.no>
2017-11-19 13:59:19 +00:00
Tom Gundersen b30eb5186b r-rbtree/paint_one: drop redundant code
In case 4, all we do is rotate, we do not change the color (so
explicitly setting the color was redundant).

Signed-off-by: Tom Gundersen <teg@jklm.no>
2017-11-18 12:58:01 +00:00
Tom Gundersen c13daa2067 c-rbtree: refactor c_rbtree_paint_one() a bit
Just for readability, mostly add to the comments to make it clear why
this is correct.

Signed-off-by: Tom Gundersen <teg@jklm.no>
2017-11-18 12:56:16 +00:00
David Herrmann 0a985f9bc1 c-rbtree: embedd tree-root in root-node
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>
2017-11-17 13:39:09 +01:00
David Herrmann 57af2b4dfc c-rbtree: c_rbtree_swap_child() -> c_rbnode_swap_child()
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>
2017-11-17 10:40:44 +01:00