diff options
Diffstat (limited to 'src/basic')
49 files changed, 1058 insertions, 68 deletions
diff --git a/src/basic/btrfs-util.c b/src/basic/btrfs-util.c index 1aff9d5329..acd48f6954 100644 --- a/src/basic/btrfs-util.c +++ b/src/basic/btrfs-util.c @@ -49,9 +49,9 @@ #include "selinux-util.h" #include "smack-util.h" #include "sparse-endian.h" -#include "time-util.h" #include "stat-util.h" #include "string-util.h" +#include "time-util.h" #include "util.h" /* WARNING: Be careful with file system ioctls! When we get an fd, we diff --git a/src/basic/c-rbtree.c b/src/basic/c-rbtree.c new file mode 100644 index 0000000000..914d7e5229 --- /dev/null +++ b/src/basic/c-rbtree.c @@ -0,0 +1,679 @@ +/*** + This file is part of systemd. See COPYING for details. + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see <http://www.gnu.org/licenses/>. +***/ + +/* + * RB-Tree Implementation + * This implements the insertion/removal of elements in RB-Trees. You're highly + * recommended to have an RB-Tree documentation at hand when reading this. Both + * insertion and removal can be split into a handful of situations that can + * occur. Those situations are enumerated as "Case 1" to "Case n" here, and + * follow closely the cases described in most RB-Tree documentations. This file + * does not explain why it is enough to handle just those cases, nor does it + * provide a proof of correctness. Dig out your algorithm 101 handbook if + * you're interested. + * + * This implementation is *not* straightforward. Usually, a handful of + * rotation, reparent, swap and link helpers can be used to implement the + * rebalance operations. However, those often perform unnecessary writes. + * Therefore, this implementation hard-codes all the operations. You're highly + * recommended to look at the two basic helpers before reading the code: + * c_rbtree_swap_child() + * c_rbtree_set_parent_and_color() + * Those are the only helpers used, hence, you should really know what they do + * before digging into the code. + * + * For a highlevel documentation of the API, see the header file and docbook + * comments. + */ + +#include <assert.h> +#include <stddef.h> +#include "c-rbtree.h" + +enum { + C_RBNODE_RED = 0, + C_RBNODE_BLACK = 1, +}; + +static inline unsigned long c_rbnode_color(CRBNode *n) { + return (unsigned long)n->__parent_and_color & 1UL; +} + +static inline _Bool c_rbnode_is_red(CRBNode *n) { + return c_rbnode_color(n) == C_RBNODE_RED; +} + +static inline _Bool c_rbnode_is_black(CRBNode *n) { + return c_rbnode_color(n) == C_RBNODE_BLACK; +} + +/** + * c_rbnode_leftmost() - return leftmost child + * @n: current node, or NULL + * + * This returns the leftmost child of @n. If @n is NULL, this will return NULL. + * In all other cases, this function returns a valid pointer. That is, if @n + * does not have any left children, this returns @n. + * + * Worst case runtime (n: number of elements in tree): O(log(n)) + * + * Return: Pointer to leftmost child, or NULL. + */ +CRBNode *c_rbnode_leftmost(CRBNode *n) { + if (n) + while (n->left) + n = n->left; + return n; +} + +/** + * c_rbnode_rightmost() - return rightmost child + * @n: current node, or NULL + * + * This returns the rightmost child of @n. If @n is NULL, this will return + * NULL. In all other cases, this function returns a valid pointer. That is, if + * @n does not have any right children, this returns @n. + * + * Worst case runtime (n: number of elements in tree): O(log(n)) + * + * Return: Pointer to rightmost child, or NULL. + */ +CRBNode *c_rbnode_rightmost(CRBNode *n) { + if (n) + while (n->right) + n = n->right; + return n; +} + +/** + * c_rbnode_next() - return next node + * @n: current node, or NULL + * + * An RB-Tree always defines a linear order of its elements. This function + * returns the logically next node to @n. If @n is NULL, the last node or + * unlinked, this returns NULL. + * + * Worst case runtime (n: number of elements in tree): O(log(n)) + * + * Return: Pointer to next node, or NULL. + */ +CRBNode *c_rbnode_next(CRBNode *n) { + CRBNode *p; + + if (!c_rbnode_is_linked(n)) + return NULL; + if (n->right) + return c_rbnode_leftmost(n->right); + + while ((p = c_rbnode_parent(n)) && n == p->right) + n = p; + + return p; +} + +/** + * c_rbnode_prev() - return previous node + * @n: current node, or NULL + * + * An RB-Tree always defines a linear order of its elements. This function + * returns the logically previous node to @n. If @n is NULL, the first node or + * unlinked, this returns NULL. + * + * Worst case runtime (n: number of elements in tree): O(log(n)) + * + * Return: Pointer to previous node, or NULL. + */ +CRBNode *c_rbnode_prev(CRBNode *n) { + CRBNode *p; + + if (!c_rbnode_is_linked(n)) + return NULL; + if (n->left) + return c_rbnode_rightmost(n->left); + + while ((p = c_rbnode_parent(n)) && n == p->left) + n = p; + + return p; +} + +/** + * c_rbtree_first() - return first node + * @t: tree to operate on + * + * An RB-Tree always defines a linear order of its elements. This function + * returns the logically first node in @t. If @t is empty, NULL is returned. + * + * Fixed runtime (n: number of elements in tree): O(log(n)) + * + * Return: Pointer to first node, or NULL. + */ +CRBNode *c_rbtree_first(CRBTree *t) { + assert(t); + return c_rbnode_leftmost(t->root); +} + +/** + * c_rbtree_last() - return last node + * @t: tree to operate on + * + * An RB-Tree always defines a linear order of its elements. This function + * returns the logically last node in @t. If @t is empty, NULL is returned. + * + * Fixed runtime (n: number of elements in tree): O(log(n)) + * + * Return: Pointer to last node, or NULL. + */ +CRBNode *c_rbtree_last(CRBTree *t) { + assert(t); + return c_rbnode_rightmost(t->root); +} + +/* + * Set the color and parent of a node. This should be treated as a simple + * assignment of the 'color' and 'parent' fields of the node. No other magic is + * applied. But since both fields share its backing memory, this helper + * function is provided. + */ +static inline void c_rbnode_set_parent_and_color(CRBNode *n, CRBNode *p, unsigned long c) { + assert(!((unsigned long)p & 1)); + assert(c < 2); + n->__parent_and_color = (CRBNode*)((unsigned long)p | c); +} + +/* same as c_rbnode_set_parent_and_color(), but keeps the current parent */ +static inline void c_rbnode_set_color(CRBNode *n, unsigned long c) { + c_rbnode_set_parent_and_color(n, c_rbnode_parent(n), c); +} + +/* same as c_rbnode_set_parent_and_color(), but keeps the current color */ +static inline void c_rbnode_set_parent(CRBNode *n, CRBNode *p) { + c_rbnode_set_parent_and_color(n, p, c_rbnode_color(n)); +} + +/* + * This function partially replaces an existing child pointer to a new one. The + * existing child must be given as @old, the new child as @new. @p must be the + * parent of @old (or NULL if it has no parent). + * This function ensures that the parent of @old now points to @new. However, + * it does *NOT* change the parent pointer of @new. The caller must ensure + * this. + * If @p is NULL, this function ensures that the root-pointer is adjusted + * instead (given as @t). + */ +static inline void c_rbtree_swap_child(CRBTree *t, CRBNode *p, CRBNode *old, CRBNode *new) { + if (p) { + if (p->left == old) + p->left = new; + else + p->right = new; + } else { + t->root = new; + } +} + +static inline CRBNode *c_rbtree_paint_one(CRBTree *t, CRBNode *n) { + CRBNode *p, *g, *gg, *u, *x; + + /* + * Paint a single node according to RB-Tree rules. The node must + * already be linked into the tree and painted red. + * We repaint the node or rotate the tree, if required. In case a + * recursive repaint is required, the next node to be re-painted + * is returned. + * p: parent + * g: grandparent + * gg: grandgrandparent + * u: uncle + * x: temporary + */ + + /* node is red, so we can access the parent directly */ + p = n->__parent_and_color; + + if (!p) { + /* Case 1: + * We reached the root. Mark it black and be done. As all + * leaf-paths share the root, the ratio of black nodes on each + * path stays the same. */ + c_rbnode_set_parent_and_color(n, p, C_RBNODE_BLACK); + n = NULL; + } else if (c_rbnode_is_black(p)) { + /* Case 2: + * The parent is already black. As our node is red, we did not + * change the number of black nodes on any path, nor do we have + * multiple consecutive red nodes. */ + n = NULL; + } else if (p == p->__parent_and_color->left) { /* parent is red, so grandparent exists */ + g = p->__parent_and_color; + gg = c_rbnode_parent(g); + u = g->right; + + if (u && c_rbnode_is_red(u)) { + /* Case 3: + * Parent and uncle are both red. We know the + * grandparent must be black then. Repaint parent and + * uncle black, the grandparent red and recurse into + * the grandparent. */ + c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED); + n = g; + } else { + /* parent is red, uncle is black */ + + if (n == p->right) { + /* Case 4: + * We're the right child. Rotate on parent to + * become left child, so we can handle it the + * same as case 5. */ + x = n->left; + p->right = n->left; + n->left = p; + if (x) + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED); + p = n; + } + + /* 'n' is invalid from here on! */ + n = NULL; + + /* Case 5: + * We're the red left child or a red parent, black + * grandparent and uncle. Rotate on grandparent and + * switch color with parent. Number of black nodes on + * each path stays the same, but we got rid of the + * double red path. As the grandparent is still black, + * we're done. */ + x = p->right; + g->left = x; + p->right = g; + if (x) + c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED); + c_rbtree_swap_child(t, gg, g, p); + } + } else /* if (p == p->__parent_and_color->left) */ { /* same as above, but mirrored */ + g = p->__parent_and_color; + gg = c_rbnode_parent(g); + u = g->left; + + if (u && c_rbnode_is_red(u)) { + c_rbnode_set_parent_and_color(p, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(u, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, gg, C_RBNODE_RED); + n = g; + } else { + if (n == p->left) { + x = n->right; + p->left = n->right; + n->right = p; + if (x) + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, n, C_RBNODE_RED); + p = n; + } + + n = NULL; + + x = p->left; + g->right = x; + p->left = g; + if (x) + c_rbnode_set_parent_and_color(x, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, gg, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(g, p, C_RBNODE_RED); + c_rbtree_swap_child(t, gg, g, p); + } + } + + return n; +} + +static inline void c_rbtree_paint(CRBTree *t, CRBNode *n) { + assert(t); + assert(n); + + while (n) + n = c_rbtree_paint_one(t, n); +} + +/** + * c_rbtree_add() - add node to tree + * @t: tree to operate one + * @p: parent node to link under, or NULL + * @l: left/right slot of @p (or root) to link at + * @n: node to add + * + * This links @n into the tree given as @t. The caller must provide the exact + * spot where to link the node. That is, the caller must traverse the tree + * based on their search order. Once they hit a leaf where to insert the node, + * call this function to link it and rebalance the tree. + * + * A typical insertion would look like this (@t is your tree, @n is your node): + * + * CRBNode **i, *p; + * + * i = &t->root; + * p = NULL; + * while (*i) { + * p = *i; + * if (compare(n, *i) < 0) + * i = &(*i)->left; + * else + * i = &(*i)->right; + * } + * + * c_rbtree_add(t, p, i, n); + * + * Once the node is linked into the tree, a simple lookup on the same tree can + * be coded like this: + * + * CRBNode *i; + * + * i = t->root; + * while (i) { + * int v = compare(n, i); + * if (v < 0) + * i = (*i)->left; + * else if (v > 0) + * i = (*i)->right; + * else + * break; + * } + * + * When you add nodes to a tree, the memory contents of the node do not matter. + * That is, there is no need to initialize the node via c_rbnode_init(). + * However, if you relink nodes multiple times during their lifetime, it is + * usually very convenient to use c_rbnode_init() and c_rbtree_remove_init(). + * In those cases, you should validate that a node is unlinked before you call + * c_rbtree_add(). + */ +void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n) { + assert(t); + assert(l); + assert(n); + assert(!p || l == &p->left || l == &p->right); + assert(p || l == &t->root); + + c_rbnode_set_parent_and_color(n, p, C_RBNODE_RED); + n->left = n->right = NULL; + *l = n; + + c_rbtree_paint(t, n); +} + +static inline CRBNode *c_rbtree_rebalance_one(CRBTree *t, CRBNode *p, CRBNode *n) { + CRBNode *s, *x, *y, *g; + + /* + * Rebalance tree after a node was removed. This happens only if you + * remove a black node and one path is now left with an unbalanced + * number or black nodes. + * This function assumes all paths through p and n have one black node + * less than all other paths. If recursive fixup is required, the + * current node is returned. + */ + + if (n == p->left) { + s = p->right; + if (c_rbnode_is_red(s)) { + /* Case 3: + * We have a red node as sibling. Rotate it onto our + * side so we can later on turn it black. This way, we + * gain the additional black node in our path. */ + g = c_rbnode_parent(p); + x = s->left; + p->right = x; + s->left = p; + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p)); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED); + c_rbtree_swap_child(t, g, p, s); + s = x; + } + + x = s->right; + if (!x || c_rbnode_is_black(x)) { + y = s->left; + if (!y || c_rbnode_is_black(y)) { + /* Case 4: + * Our sibling is black and has only black + * children. Flip it red and turn parent black. + * This way we gained a black node in our path, + * or we fix it recursively one layer up, which + * will rotate the red sibling as parent. */ + c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED); + if (c_rbnode_is_black(p)) + return p; + + c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK); + return NULL; + } + + /* Case 5: + * Left child of our sibling is red, right one is black. + * Rotate on parent so the right child of our sibling is + * now red, and we can fall through to case 6. */ + x = y->right; + s->left = y->right; + y->right = s; + p->right = y; + if (x) + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + x = s; + s = y; + } + + /* Case 6: + * The right child of our sibling is red. Rotate left and flip + * colors, which gains us an additional black node in our path, + * that was previously on our sibling. */ + g = c_rbnode_parent(p); + y = s->left; + p->right = y; + s->left = p; + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + if (y) + c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y)); + c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p)); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK); + c_rbtree_swap_child(t, g, p, s); + } else /* if (!n || n == p->right) */ { /* same as above, but mirrored */ + s = p->left; + if (c_rbnode_is_red(s)) { + g = c_rbnode_parent(p); + x = s->right; + p->left = x; + s->right = p; + c_rbnode_set_parent_and_color(x, p, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(s, g, C_RBNODE_BLACK); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_RED); + c_rbtree_swap_child(t, g, p, s); + s = x; + } + + x = s->left; + if (!x || c_rbnode_is_black(x)) { + y = s->right; + if (!y || c_rbnode_is_black(y)) { + c_rbnode_set_parent_and_color(s, p, C_RBNODE_RED); + if (c_rbnode_is_black(p)) + return p; + + c_rbnode_set_parent_and_color(p, c_rbnode_parent(p), C_RBNODE_BLACK); + return NULL; + } + + x = y->left; + s->right = y->left; + y->left = s; + p->left = y; + if (x) + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + x = s; + s = y; + } + + g = c_rbnode_parent(p); + y = s->right; + p->left = y; + s->right = p; + c_rbnode_set_parent_and_color(x, s, C_RBNODE_BLACK); + if (y) + c_rbnode_set_parent_and_color(y, p, c_rbnode_color(y)); + c_rbnode_set_parent_and_color(s, g, c_rbnode_color(p)); + c_rbnode_set_parent_and_color(p, s, C_RBNODE_BLACK); + c_rbtree_swap_child(t, g, p, s); + } + + return NULL; +} + +static inline void c_rbtree_rebalance(CRBTree *t, CRBNode *p) { + CRBNode *n = NULL; + + assert(t); + assert(p); + + do { + n = c_rbtree_rebalance_one(t, p, n); + p = n ? c_rbnode_parent(n) : NULL; + } while (p); +} + +/** + * c_rbtree_remove() - remove node from tree + * @t: tree to operate one + * @n: node to remove + * + * This removes the given node from its tree. Once unlinked, the tree is + * rebalanced. + * The caller *must* ensure that the given tree is actually the tree it is + * linked on. Otherwise, behavior is undefined. + * + * This does *NOT* reset @n to being unlinked (for performance reason, this + * function *never* modifies @n at all). If you need this, use + * c_rbtree_remove_init(). + */ +void c_rbtree_remove(CRBTree *t, CRBNode *n) { + CRBNode *p, *s, *gc, *x, *next = NULL; + unsigned long c; + + assert(t); + assert(n); + assert(c_rbnode_is_linked(n)); + + /* + * There are three distinct cases during node removal of a tree: + * * The node has no children, in which case it can simply be removed. + * * The node has exactly one child, in which case the child displaces + * its parent. + * * The node has two children, in which case there is guaranteed to + * be a successor to the node (successor being the node ordered + * directly after it). This successor cannot have two children by + * itself (two interior nodes can never be successive). Therefore, + * we can simply swap the node with its successor (including color) + * and have reduced this case to either of the first two. + * + * Whenever the node we removed was black, we have to rebalance the + * tree. Note that this affects the actual node we _remove_, not @n (in + * case we swap it). + * + * p: parent + * s: successor + * gc: grand-...-child + * x: temporary + * next: next node to rebalance on + */ + + if (!n->left) { + /* + * Case 1: + * The node has no left child. If it neither has a right child, + * it is a leaf-node and we can simply unlink it. If it also + * was black, we have to rebalance, as always if we remove a + * black node. + * But if the node has a right child, the child *must* be red + * (otherwise, the right path has more black nodes as the + * non-existing left path), and the node to be removed must + * hence be black. We simply replace the node with its child, + * turning the red child black, and thus no rebalancing is + * required. + */ + p = c_rbnode_parent(n); + c = c_rbnode_color(n); + c_rbtree_swap_child(t, p, n, n->right); + if (n->right) + c_rbnode_set_parent_and_color(n->right, p, c); + else + next = (c == C_RBNODE_BLACK) ? p : NULL; + } else if (!n->right) { + /* + * Case 1.1: + * The node has exactly one child, and it is on the left. Treat + * it as mirrored case of Case 1 (i.e., replace the node by its + * child). + */ + p = c_rbnode_parent(n); + c = c_rbnode_color(n); + c_rbtree_swap_child(t, p, n, n->left); + c_rbnode_set_parent_and_color(n->left, p, c); + } else { + /* + * Case 2: + * We are dealing with a full interior node with a child not on + * both sides. Find its successor and swap it. Then remove the + * node similar to Case 1. For performance reasons we don't + * perform the full swap, but skip links that are about to be + * removed, anyway. + */ + s = n->right; + if (!s->left) { + /* right child is next, no need to touch grandchild */ + p = s; + gc = s->right; + } else { + /* find successor and swap partially */ + s = c_rbnode_leftmost(s); + p = c_rbnode_parent(s); + + gc = s->right; + p->left = s->right; + s->right = n->right; + c_rbnode_set_parent(n->right, s); + } + + /* node is partially swapped, now remove as in Case 1 */ + s->left = n->left; + c_rbnode_set_parent(n->left, s); + + x = c_rbnode_parent(n); + c = c_rbnode_color(n); + c_rbtree_swap_child(t, x, n, s); + if (gc) + c_rbnode_set_parent_and_color(gc, p, C_RBNODE_BLACK); + else + next = c_rbnode_is_black(s) ? p : NULL; + c_rbnode_set_parent_and_color(s, x, c); + } + + if (next) + c_rbtree_rebalance(t, next); +} diff --git a/src/basic/c-rbtree.h b/src/basic/c-rbtree.h new file mode 100644 index 0000000000..20c5515ca1 --- /dev/null +++ b/src/basic/c-rbtree.h @@ -0,0 +1,297 @@ +#pragma once + +/*** + This file is part of systemd. See COPYING for details. + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see <http://www.gnu.org/licenses/>. +***/ + +/* + * Standalone Red-Black-Tree Implementation in Standard ISO-C11 + * + * This header provides an RB-Tree API, that is fully implemented in ISO-C11 + * and has no external dependencies. Furthermore, tree traversal, memory + * allocations, and key comparisons a fully in control of the API user. The + * implementation only provides the RB-Tree specific rebalancing and coloring. + * + * A tree is represented by the "CRBTree" structure. It contains a *singly* + * field, which is a pointer to the root node. If NULL, the tree is empty. If + * non-NULL, there is at least a single element in the tree. + * + * Each node of the tree is represented by the "CRBNode" structure. It has + * three fields. The @left and @right members can be accessed by the API user + * directly to traverse the tree. The third member is an implementation detail + * and encodes the parent pointer and color of the node. + * API users are required to embed the CRBNode object into their own objects + * and then use offsetof() (i.e., container_of() and friends) to turn CRBNode + * pointers into pointers to their own structure. + */ + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct CRBNode CRBNode; +typedef struct CRBTree CRBTree; + +/** + * struct CRBNode - Node of a Red-Black Tree + * @__parent_and_color: internal state + * @left: left child, or NULL + * @right: right child, or NULL + * + * Each node in an RB-Tree must embed an CRBNode object. This object contains + * pointers to its left and right child, which can be freely accessed by the + * API user at any time. They are NULL, if the node does not have a left/right + * child. + * + * The @__parent_and_color field must never be accessed directly. It encodes + * the pointer to the parent node, and the color of the node. Use the accessor + * functions instead. + * + * There is no reason to initialize a CRBNode object before linking it. + * However, if you need a boolean state that tells you whether the node is + * linked or not, you should initialize the node via c_rbnode_init() or + * C_RBNODE_INIT. + */ +struct CRBNode { + CRBNode *__parent_and_color; + CRBNode *left; + CRBNode *right; +}; + +#define C_RBNODE_INIT(_var) { .__parent_and_color = &(_var) } + +CRBNode *c_rbnode_leftmost(CRBNode *n); +CRBNode *c_rbnode_rightmost(CRBNode *n); +CRBNode *c_rbnode_next(CRBNode *n); +CRBNode *c_rbnode_prev(CRBNode *n); + +/** + * struct CRBTree - Red-Black Tree + * @root: pointer to the root node, or NULL + * + * Each Red-Black Tree is rooted in an CRBTree object. This object contains a + * pointer to the root node of the tree. The API user is free to access the + * @root member at any time, and use it to traverse the tree. + * + * To initialize an RB-Tree, set it to NULL / all zero. + */ +struct CRBTree { + CRBNode *root; +}; + +CRBNode *c_rbtree_first(CRBTree *t); +CRBNode *c_rbtree_last(CRBTree *t); + +void c_rbtree_add(CRBTree *t, CRBNode *p, CRBNode **l, CRBNode *n); +void c_rbtree_remove(CRBTree *t, CRBNode *n); + +/** + * c_rbnode_init() - mark a node as unlinked + * @n: node to operate on + * + * This marks the node @n as unlinked. The node will be set to a valid state + * that can never happen if the node is linked in a tree. Furthermore, this + * state is fully known to the implementation, and as such handled gracefully + * in all cases. + * + * You are *NOT* required to call this on your node. c_rbtree_add() can handle + * uninitialized nodes just fine. However, calling this allows to use + * c_rbnode_is_linked() to check for the state of a node. Furthermore, + * iterators and accessors can be called on initialized (yet unlinked) nodes. + * + * Use the C_RBNODE_INIT macro if you want to initialize static variables. + */ +static inline void c_rbnode_init(CRBNode *n) { + *n = (CRBNode)C_RBNODE_INIT(*n); +} + +/** + * c_rbnode_is_linked() - check whether a node is linked + * @n: node to check, or NULL + * + * This checks whether the passed node is linked. If you pass NULL, or if the + * node is not linked into a tree, this will return false. Otherwise, this + * returns true. + * + * Note that you must have either linked the node or initialized it, before + * calling this function. Never call this function on uninitialized nodes. + * Furthermore, removing a node via c_rbtree_remove() does *NOT* mark the node + * as unlinked. You have to call c_rbnode_init() yourself after removal, or use + * the c_rbtree_remove_init() helper. + * + * Return: true if the node is linked, false if not. + */ +static inline _Bool c_rbnode_is_linked(CRBNode *n) { + return n && n->__parent_and_color != n; +} + +/** + * c_rbnode_parent() - return parent pointer + * @n node to access + * + * This returns a pointer to the parent of the given node @n. If @n does not + * have a parent, NULL is returned. If @n is not linked, @n itself is returned. + * + * You should not call this on unlinked or uninitialized nodes! If you do, you + * better know how its semantics. + * + * Return: Pointer to parent. + */ +static inline CRBNode *c_rbnode_parent(CRBNode *n) { + return (CRBNode*)((unsigned long)n->__parent_and_color & ~1UL); +} + +/** + * c_rbtree_remove_init() - safely remove node from tree and reinitialize it + * @t: tree to operate on + * @n: node to remove, or NULL + * + * This is almost the same as c_rbtree_remove(), but extends it slightly, to be + * more convenient to use in many cases: + * - if @n is unlinked or NULL, this is a no-op + * - @n is reinitialized after being removed + */ +static inline void c_rbtree_remove_init(CRBTree *t, CRBNode *n) { + if (c_rbnode_is_linked(n)) { + c_rbtree_remove(t, n); + c_rbnode_init(n); + } +} + +/** + * CRBCompareFunc - compare a node to a key + * @t: tree where the node is linked to + * @k: key to compare + * @n: node to compare + * + * If you use the tree-traversal helpers (which are optional), you need to + * provide this callback so they can compare nodes in a tree to the key you + * look for. + * + * The tree @t is provided as optional context to this callback. The key you + * look for is provided as @k, the current node that should be compared to is + * provided as @n. This function should work like strcmp(), that is, return -1 + * if @key orders before @n, 0 if both compare equal, and 1 if it orders after + * @n. + */ +typedef int (*CRBCompareFunc) (CRBTree *t, void *k, CRBNode *n); + +/** + * c_rbtree_find_node() - find node + * @t: tree to search through + * @f: comparison function + * @k: key to search for + * + * This searches through @t for a node that compares equal to @k. The function + * @f must be provided by the caller, which is used to compare nodes to @k. See + * the documentation of CRBCompareFunc for details. + * + * If there are multiple entries that compare equal to @k, this will return a + * pseudo-randomly picked node. If you need stable lookup functions for trees + * where duplicate entries are allowed, you better code your own lookup. + * + * Return: Pointer to matching node, or NULL. + */ +static inline CRBNode *c_rbtree_find_node(CRBTree *t, CRBCompareFunc f, const void *k) { + CRBNode *i; + + assert(t); + assert(f); + + i = t->root; + while (i) { + int v = f(t, (void *)k, i); + if (v < 0) + i = i->left; + else if (v > 0) + i = i->right; + else + return i; + } + + return NULL; +} + +/** + * c_rbtree_find_entry() - find entry + * @_t: tree to search through + * @_f: comparison function + * @_k: key to search for + * @_t: type of the structure that embeds the nodes + * @_o: name of the node-member in type @_t + * + * This is very similar to c_rbtree_find_node(), but instead of returning a + * pointer to the CRBNode, it returns a pointer to the surrounding object. This + * object must embed the CRBNode object. The type of the surrounding object + * must be given as @_t, and the name of the embedded CRBNode member as @_o. + * + * See c_rbtree_find_node() for more details. + * + * Return: Pointer to found entry, NULL if not found. + */ +#define c_rbtree_find_entry(_m, _f, _k, _t, _o) \ + ((_t *)(((char *)c_rbtree_find_node((_m), (_f), (_k)) ?: \ + (char *)NULL + offsetof(_t, _o)) - offsetof(_t, _o))) + +/** + * c_rbtree_find_slot() - find slot to insert new node + * @t: tree to search through + * @f: comparison function + * @k: key to search for + * @p: output storage for parent pointer + * + * This searches through @t just like c_rbtree_find_node() does. However, + * instead of returning a pointer to a node that compares equal to @k, this + * searches for a slot to insert a node with key @k. A pointer to the slot is + * returned, and a pointer to the parent of the slot is stored in @p. Both + * can be passed directly to c_rbtree_add(), together with your node to insert. + * + * If there already is a node in the tree, that compares equal to @k, this will + * return NULL and store the conflicting node in @p. In all other cases, + * this will return a pointer (non-NULL) to the empty slot to insert the node + * at. @p will point to the parent node of that slot. + * + * If you want trees that allow duplicate nodes, you better code your own + * insertion function. + * + * Return: Pointer to slot to insert node, or NULL on conflicts. + */ +static inline CRBNode **c_rbtree_find_slot(CRBTree *t, CRBCompareFunc f, const void *k, CRBNode **p) { + CRBNode **i; + + assert(t); + assert(f); + assert(p); + + i = &t->root; + *p = NULL; + while (*i) { + int v = f(t, (void *)k, *i); + *p = *i; + if (v < 0) + i = &(*i)->left; + else if (v > 0) + i = &(*i)->right; + else + return NULL; + } + + return i; +} + +#ifdef __cplusplus +} +#endif diff --git a/src/basic/calendarspec.c b/src/basic/calendarspec.c index 2c670a1ac6..8f83d9c142 100644 --- a/src/basic/calendarspec.c +++ b/src/basic/calendarspec.c @@ -30,8 +30,8 @@ #include "alloc-util.h" #include "calendarspec.h" #include "fileio.h" -#include "parse-util.h" #include "macro.h" +#include "parse-util.h" #include "string-util.h" #define BITS_WEEKDAYS 127 diff --git a/src/basic/cap-list.c b/src/basic/cap-list.c index aac812dc52..0e5cc452b9 100644 --- a/src/basic/cap-list.c +++ b/src/basic/cap-list.c @@ -23,9 +23,9 @@ #include <string.h> #include "cap-list.h" +#include "macro.h" #include "missing.h" #include "parse-util.h" -#include "macro.h" #include "util.h" static const struct capability_name* lookup_capability(register const char *str, register unsigned int len); diff --git a/src/basic/cgroup-util.c b/src/basic/cgroup-util.c index 7c580caa43..639f9f3db1 100644 --- a/src/basic/cgroup-util.c +++ b/src/basic/cgroup-util.c @@ -34,14 +34,17 @@ #include "alloc-util.h" #include "cgroup-util.h" +#include "def.h" #include "dirent-util.h" #include "extract-word.h" #include "fd-util.h" #include "fileio.h" #include "formats-util.h" #include "fs-util.h" +#include "log.h" #include "login-util.h" #include "macro.h" +#include "missing.h" #include "mkdir.h" #include "parse-util.h" #include "path-util.h" @@ -49,9 +52,6 @@ #include "process-util.h" #include "set.h" #include "special.h" -#include "def.h" -#include "log.h" -#include "missing.h" #include "stat-util.h" #include "string-table.h" #include "string-util.h" @@ -2135,7 +2135,7 @@ int cg_unified(void) { else if (F_TYPE_EQUAL(fs.f_type, TMPFS_MAGIC)) unified_cache = false; else - return -ENOEXEC; + return -ENOMEDIUM; return unified_cache; } diff --git a/src/basic/cgroup-util.h b/src/basic/cgroup-util.h index b506995794..661785784a 100644 --- a/src/basic/cgroup-util.h +++ b/src/basic/cgroup-util.h @@ -28,9 +28,9 @@ #include <sys/types.h> #include "def.h" -#include "set.h" #include "hashmap.h" #include "macro.h" +#include "set.h" /* An enum of well known cgroup controllers */ typedef enum CGroupController { diff --git a/src/basic/copy.c b/src/basic/copy.c index c335959b74..024712d290 100644 --- a/src/basic/copy.c +++ b/src/basic/copy.c @@ -42,9 +42,9 @@ #include "fs-util.h" #include "io-util.h" #include "macro.h" -#include "time-util.h" #include "string-util.h" #include "strv.h" +#include "time-util.h" #include "umask-util.h" #include "xattr-util.h" diff --git a/src/basic/cpu-set-util.c b/src/basic/cpu-set-util.c index 51c0693954..85b7519953 100644 --- a/src/basic/cpu-set-util.c +++ b/src/basic/cpu-set-util.c @@ -27,9 +27,9 @@ #include "alloc-util.h" #include "cpu-set-util.h" #include "extract-word.h" -#include "parse-util.h" #include "log.h" #include "macro.h" +#include "parse-util.h" #include "string-util.h" cpu_set_t* cpu_set_malloc(unsigned *ncpus) { diff --git a/src/basic/dirent-util.h b/src/basic/dirent-util.h index 58273bb988..1ad5e4715a 100644 --- a/src/basic/dirent-util.h +++ b/src/basic/dirent-util.h @@ -25,8 +25,8 @@ #include <errno.h> #include <stdbool.h> -#include "path-util.h" #include "macro.h" +#include "path-util.h" int dirent_ensure_type(DIR *d, struct dirent *de); diff --git a/src/basic/env-util.c b/src/basic/env-util.c index fe8c825f36..dd56545f12 100644 --- a/src/basic/env-util.c +++ b/src/basic/env-util.c @@ -28,9 +28,9 @@ #include "alloc-util.h" #include "env-util.h" -#include "parse-util.h" #include "extract-word.h" #include "macro.h" +#include "parse-util.h" #include "string-util.h" #include "strv.h" #include "utf8.h" diff --git a/src/basic/exit-status.h b/src/basic/exit-status.h index 850f58fd98..664222c1d6 100644 --- a/src/basic/exit-status.h +++ b/src/basic/exit-status.h @@ -23,9 +23,9 @@ #include <stdbool.h> -#include "set.h" #include "hashmap.h" #include "macro.h" +#include "set.h" typedef enum ExitStatus { /* EXIT_SUCCESS defined by libc */ diff --git a/src/basic/fd-util.c b/src/basic/fd-util.c index 678ac3b195..9759cac23c 100644 --- a/src/basic/fd-util.c +++ b/src/basic/fd-util.c @@ -27,11 +27,11 @@ #include <unistd.h> #include "fd-util.h" -#include "parse-util.h" -#include "socket-util.h" #include "macro.h" #include "missing.h" +#include "parse-util.h" #include "path-util.h" +#include "socket-util.h" #include "util.h" int close_nointr(int fd) { diff --git a/src/basic/fdset.c b/src/basic/fdset.c index 654ec5a639..de9b723ab8 100644 --- a/src/basic/fdset.c +++ b/src/basic/fdset.c @@ -29,11 +29,11 @@ #include "fd-util.h" #include "fdset.h" +#include "log.h" #include "macro.h" #include "parse-util.h" -#include "set.h" -#include "log.h" #include "path-util.h" +#include "set.h" #define MAKE_SET(s) ((Set*) s) #define MAKE_FDSET(s) ((FDSet*) s) diff --git a/src/basic/fdset.h b/src/basic/fdset.h index 58a5b45f28..615ba05661 100644 --- a/src/basic/fdset.h +++ b/src/basic/fdset.h @@ -23,9 +23,9 @@ #include <stdbool.h> -#include "set.h" #include "hashmap.h" #include "macro.h" +#include "set.h" typedef struct FDSet FDSet; diff --git a/src/basic/fileio-label.c b/src/basic/fileio-label.c index 52a1515cd7..1cee87c9cd 100644 --- a/src/basic/fileio-label.c +++ b/src/basic/fileio-label.c @@ -23,8 +23,8 @@ #include <sys/stat.h> #include "fileio-label.h" -#include "selinux-util.h" #include "fileio.h" +#include "selinux-util.h" int write_string_file_atomic_label(const char *fn, const char *line) { int r; diff --git a/src/basic/fileio.c b/src/basic/fileio.c index 684ce3d58f..3a237252b5 100644 --- a/src/basic/fileio.c +++ b/src/basic/fileio.c @@ -37,15 +37,15 @@ #include "fileio.h" #include "fs-util.h" #include "hexdecoct.h" +#include "log.h" +#include "macro.h" #include "parse-util.h" #include "path-util.h" #include "random-util.h" -#include "log.h" -#include "macro.h" -#include "time-util.h" #include "stdio-util.h" #include "string-util.h" #include "strv.h" +#include "time-util.h" #include "umask-util.h" #include "utf8.h" diff --git a/src/basic/fs-util.c b/src/basic/fs-util.c index cd7abee989..fb760abe18 100644 --- a/src/basic/fs-util.c +++ b/src/basic/fs-util.c @@ -34,15 +34,15 @@ #include "fd-util.h" #include "fileio.h" #include "fs-util.h" -#include "mkdir.h" -#include "parse-util.h" -#include "path-util.h" #include "log.h" #include "macro.h" #include "missing.h" -#include "time-util.h" +#include "mkdir.h" +#include "parse-util.h" +#include "path-util.h" #include "string-util.h" #include "strv.h" +#include "time-util.h" #include "user-util.h" #include "util.h" diff --git a/src/basic/label.c b/src/basic/label.c index 70e6ee20bf..f72a985967 100644 --- a/src/basic/label.c +++ b/src/basic/label.c @@ -24,9 +24,9 @@ #include <unistd.h> #include "label.h" +#include "macro.h" #include "selinux-util.h" #include "smack-util.h" -#include "macro.h" int label_fix(const char *path, bool ignore_enoent, bool ignore_erofs) { int r, q; diff --git a/src/basic/locale-util.c b/src/basic/locale-util.c index 708da0d304..7784d02168 100644 --- a/src/basic/locale-util.c +++ b/src/basic/locale-util.c @@ -34,10 +34,10 @@ #include "dirent-util.h" #include "fd-util.h" +#include "hashmap.h" #include "locale-util.h" #include "path-util.h" #include "set.h" -#include "hashmap.h" #include "string-table.h" #include "string-util.h" #include "strv.h" diff --git a/src/basic/lockfile-util.c b/src/basic/lockfile-util.c index 704ae6cc52..6ecfc2ec46 100644 --- a/src/basic/lockfile-util.c +++ b/src/basic/lockfile-util.c @@ -30,8 +30,8 @@ #include "fd-util.h" #include "fs-util.h" #include "lockfile-util.h" -#include "path-util.h" #include "macro.h" +#include "path-util.h" int make_lock_file(const char *p, int operation, LockFile *ret) { _cleanup_close_ int fd = -1; diff --git a/src/basic/log.c b/src/basic/log.c index 829f85a5d8..1a9e6bdb91 100644 --- a/src/basic/log.c +++ b/src/basic/log.c @@ -49,12 +49,12 @@ #include "process-util.h" #include "signal-util.h" #include "socket-util.h" -#include "time-util.h" #include "stdio-util.h" #include "string-table.h" #include "string-util.h" #include "syslog-util.h" #include "terminal-util.h" +#include "time-util.h" #include "util.h" #define SNDBUF_SIZE (8*1024*1024) diff --git a/src/basic/memfd-util.c b/src/basic/memfd-util.c index a9b2151195..789638f013 100644 --- a/src/basic/memfd-util.c +++ b/src/basic/memfd-util.c @@ -32,9 +32,9 @@ #include "alloc-util.h" #include "fd-util.h" +#include "macro.h" #include "memfd-util.h" #include "missing.h" -#include "macro.h" #include "string-util.h" #include "utf8.h" diff --git a/src/basic/mkdir.c b/src/basic/mkdir.c index 4b809541b1..9f9d52b5df 100644 --- a/src/basic/mkdir.c +++ b/src/basic/mkdir.c @@ -25,9 +25,9 @@ #include <sys/stat.h> #include "fs-util.h" +#include "macro.h" #include "mkdir.h" #include "path-util.h" -#include "macro.h" #include "stat-util.h" #include "user-util.h" diff --git a/src/basic/mount-util.c b/src/basic/mount-util.c index aaac2d47bd..10a6536cfc 100644 --- a/src/basic/mount-util.c +++ b/src/basic/mount-util.c @@ -31,11 +31,11 @@ #include "escape.h" #include "fd-util.h" #include "fileio.h" +#include "hashmap.h" #include "mount-util.h" #include "parse-util.h" #include "path-util.h" #include "set.h" -#include "hashmap.h" #include "stdio-util.h" #include "string-util.h" diff --git a/src/basic/mount-util.h b/src/basic/mount-util.h index 3be75e6614..b37250f08e 100644 --- a/src/basic/mount-util.h +++ b/src/basic/mount-util.h @@ -28,8 +28,8 @@ #include <sys/stat.h> #include <sys/types.h> -#include "missing.h" #include "macro.h" +#include "missing.h" int fd_is_mount_point(int fd, const char *filename, int flags); int path_is_mount_point(const char *path, int flags); diff --git a/src/basic/parse-util.c b/src/basic/parse-util.c index 3d8123ca0d..618ef5d564 100644 --- a/src/basic/parse-util.c +++ b/src/basic/parse-util.c @@ -29,8 +29,8 @@ #include "alloc-util.h" #include "extract-word.h" -#include "parse-util.h" #include "macro.h" +#include "parse-util.h" #include "string-util.h" int parse_boolean(const char *v) { diff --git a/src/basic/path-util.c b/src/basic/path-util.c index 95b1052aeb..61fab0e087 100644 --- a/src/basic/path-util.c +++ b/src/basic/path-util.c @@ -34,16 +34,16 @@ #undef basename #include "alloc-util.h" +#include "extract-word.h" #include "fs-util.h" #include "log.h" #include "macro.h" #include "missing.h" #include "path-util.h" -#include "extract-word.h" -#include "time-util.h" #include "stat-util.h" #include "string-util.h" #include "strv.h" +#include "time-util.h" bool path_is_absolute(const char *p) { return p[0] == '/'; diff --git a/src/basic/prioq.c b/src/basic/prioq.c index 7d420d8a7b..86c5c0e9b4 100644 --- a/src/basic/prioq.c +++ b/src/basic/prioq.c @@ -33,8 +33,8 @@ #include <stdlib.h> #include "alloc-util.h" -#include "prioq.h" #include "hashmap.h" +#include "prioq.h" struct prioq_item { void *data; diff --git a/src/basic/process-util.c b/src/basic/process-util.c index 1d60811cbf..4cc54a51fb 100644 --- a/src/basic/process-util.c +++ b/src/basic/process-util.c @@ -41,10 +41,10 @@ #include "fs-util.h" #include "ioprio.h" #include "log.h" -#include "process-util.h" -#include "signal-util.h" #include "macro.h" #include "missing.h" +#include "process-util.h" +#include "signal-util.h" #include "string-table.h" #include "string-util.h" #include "user-util.h" diff --git a/src/basic/ratelimit.c b/src/basic/ratelimit.c index ee0f8176b9..b62f3da76b 100644 --- a/src/basic/ratelimit.c +++ b/src/basic/ratelimit.c @@ -22,8 +22,8 @@ #include <sys/time.h> -#include "ratelimit.h" #include "macro.h" +#include "ratelimit.h" /* Modelled after Linux' lib/ratelimit.c by Dave Young * <hidave.darkstar@gmail.com>, which is licensed GPLv2. */ diff --git a/src/basic/rlimit-util.c b/src/basic/rlimit-util.c index 2de965daa6..44f885db16 100644 --- a/src/basic/rlimit-util.c +++ b/src/basic/rlimit-util.c @@ -22,9 +22,9 @@ #include <errno.h> #include <sys/resource.h> +#include "macro.h" #include "missing.h" #include "rlimit-util.h" -#include "macro.h" #include "string-table.h" int setrlimit_closest(int resource, const struct rlimit *rlim) { diff --git a/src/basic/rm-rf.c b/src/basic/rm-rf.c index 0408e22777..14f8474da0 100644 --- a/src/basic/rm-rf.c +++ b/src/basic/rm-rf.c @@ -30,11 +30,11 @@ #include "btrfs-util.h" #include "fd-util.h" +#include "log.h" +#include "macro.h" #include "mount-util.h" #include "path-util.h" #include "rm-rf.h" -#include "log.h" -#include "macro.h" #include "stat-util.h" #include "string-util.h" diff --git a/src/basic/selinux-util.c b/src/basic/selinux-util.c index 9be8e2c76f..5956c4fe43 100644 --- a/src/basic/selinux-util.c +++ b/src/basic/selinux-util.c @@ -35,10 +35,10 @@ #endif #include "alloc-util.h" -#include "path-util.h" -#include "selinux-util.h" #include "log.h" #include "macro.h" +#include "path-util.h" +#include "selinux-util.h" #include "time-util.h" #include "util.h" diff --git a/src/basic/signal-util.c b/src/basic/signal-util.c index fd9258dfca..7637fccb2f 100644 --- a/src/basic/signal-util.c +++ b/src/basic/signal-util.c @@ -23,9 +23,9 @@ #include <stdarg.h> #include <stdio.h> +#include "macro.h" #include "parse-util.h" #include "signal-util.h" -#include "macro.h" #include "string-table.h" #include "string-util.h" diff --git a/src/basic/siphash24.c b/src/basic/siphash24.c index 65667b9859..060e8ba387 100644 --- a/src/basic/siphash24.c +++ b/src/basic/siphash24.c @@ -17,8 +17,8 @@ coding style) */ -#include "siphash24.h" #include "macro.h" +#include "siphash24.h" #include "unaligned.h" static inline uint64_t rotate_left(uint64_t x, uint8_t b) { diff --git a/src/basic/smack-util.c b/src/basic/smack-util.c index e8030c92f3..b9e4ff87d8 100644 --- a/src/basic/smack-util.c +++ b/src/basic/smack-util.c @@ -29,11 +29,11 @@ #include "alloc-util.h" #include "fileio.h" +#include "log.h" +#include "macro.h" #include "path-util.h" #include "process-util.h" #include "smack-util.h" -#include "log.h" -#include "macro.h" #include "string-table.h" #include "xattr-util.h" diff --git a/src/basic/socket-label.c b/src/basic/socket-label.c index 2dc6c76752..e169439e04 100644 --- a/src/basic/socket-label.c +++ b/src/basic/socket-label.c @@ -31,12 +31,12 @@ #include "alloc-util.h" #include "fd-util.h" +#include "log.h" #include "macro.h" #include "missing.h" #include "mkdir.h" #include "selinux-util.h" #include "socket-util.h" -#include "log.h" int socket_address_listen( const SocketAddress *a, diff --git a/src/basic/socket-util.c b/src/basic/socket-util.c index 240fb60212..79901a6a06 100644 --- a/src/basic/socket-util.c +++ b/src/basic/socket-util.c @@ -36,12 +36,12 @@ #include "fd-util.h" #include "fileio.h" #include "formats-util.h" +#include "log.h" #include "macro.h" #include "missing.h" #include "parse-util.h" #include "path-util.h" #include "socket-util.h" -#include "log.h" #include "string-table.h" #include "string-util.h" #include "user-util.h" @@ -870,16 +870,24 @@ int getpeersec(int fd, char **ret) { return 0; } -int send_one_fd(int transport_fd, int fd, int flags) { +int send_one_fd_sa( + int transport_fd, + int fd, + const struct sockaddr *sa, socklen_t len, + int flags) { + union { struct cmsghdr cmsghdr; uint8_t buf[CMSG_SPACE(sizeof(int))]; } control = {}; + struct cmsghdr *cmsg; + struct msghdr mh = { + .msg_name = (struct sockaddr*) sa, + .msg_namelen = len, .msg_control = &control, .msg_controllen = sizeof(control), }; - struct cmsghdr *cmsg; assert(transport_fd >= 0); assert(fd >= 0); diff --git a/src/basic/socket-util.h b/src/basic/socket-util.h index f9c90e0e73..6da1df68d8 100644 --- a/src/basic/socket-util.h +++ b/src/basic/socket-util.h @@ -128,7 +128,11 @@ int ip_tos_from_string(const char *s); int getpeercred(int fd, struct ucred *ucred); int getpeersec(int fd, char **ret); -int send_one_fd(int transport_fd, int fd, int flags); +int send_one_fd_sa(int transport_fd, + int fd, + const struct sockaddr *sa, socklen_t len, + int flags); +#define send_one_fd(transport_fd, fd, flags) send_one_fd_sa(transport_fd, fd, NULL, 0, flags) int receive_one_fd(int transport_fd, int flags); #define CMSG_FOREACH(cmsg, mh) \ diff --git a/src/basic/string-table.c b/src/basic/string-table.c index 07a6d785f8..4633a57f44 100644 --- a/src/basic/string-table.c +++ b/src/basic/string-table.c @@ -19,8 +19,8 @@ along with systemd; If not, see <http://www.gnu.org/licenses/>. ***/ -#include "string-util.h" #include "string-table.h" +#include "string-util.h" ssize_t string_table_lookup(const char * const *table, size_t len, const char *key) { size_t i; diff --git a/src/basic/strv.h b/src/basic/strv.h index d0dd08baf3..bb61db2638 100644 --- a/src/basic/strv.h +++ b/src/basic/strv.h @@ -26,8 +26,8 @@ #include <stdbool.h> #include <stddef.h> -#include "extract-word.h" #include "alloc-util.h" +#include "extract-word.h" #include "macro.h" #include "util.h" diff --git a/src/basic/terminal-util.c b/src/basic/terminal-util.c index 68664a152f..a39764472b 100644 --- a/src/basic/terminal-util.c +++ b/src/basic/terminal-util.c @@ -43,11 +43,11 @@ #include "fileio.h" #include "fs-util.h" #include "io-util.h" +#include "log.h" +#include "macro.h" #include "parse-util.h" #include "process-util.h" #include "socket-util.h" -#include "log.h" -#include "macro.h" #include "stat-util.h" #include "string-util.h" #include "terminal-util.h" diff --git a/src/basic/time-util.c b/src/basic/time-util.c index a9296d6ee6..bfc7cf870c 100644 --- a/src/basic/time-util.c +++ b/src/basic/time-util.c @@ -34,10 +34,10 @@ #include "fd-util.h" #include "fileio.h" #include "fs-util.h" -#include "parse-util.h" -#include "path-util.h" #include "log.h" #include "macro.h" +#include "parse-util.h" +#include "path-util.h" #include "string-util.h" #include "strv.h" #include "time-util.h" diff --git a/src/basic/unit-name.c b/src/basic/unit-name.c index bdec97e54b..5fc3b9d6fd 100644 --- a/src/basic/unit-name.c +++ b/src/basic/unit-name.c @@ -28,8 +28,8 @@ #include "alloc-util.h" #include "bus-label.h" #include "hexdecoct.h" -#include "path-util.h" #include "macro.h" +#include "path-util.h" #include "string-table.h" #include "string-util.h" #include "strv.h" diff --git a/src/basic/user-util.c b/src/basic/user-util.c index 55c64abdd9..56e1a3be48 100644 --- a/src/basic/user-util.c +++ b/src/basic/user-util.c @@ -34,10 +34,10 @@ #include "alloc-util.h" #include "fd-util.h" +#include "formats-util.h" #include "macro.h" #include "parse-util.h" #include "path-util.h" -#include "formats-util.h" #include "string-util.h" #include "user-util.h" diff --git a/src/basic/util.c b/src/basic/util.c index 6d264e0007..9e0b576283 100644 --- a/src/basic/util.c +++ b/src/basic/util.c @@ -51,12 +51,12 @@ #include "parse-util.h" #include "path-util.h" #include "process-util.h" -#include "signal-util.h" #include "set.h" -#include "time-util.h" +#include "signal-util.h" #include "stat-util.h" #include "string-util.h" #include "strv.h" +#include "time-util.h" #include "user-util.h" #include "util.h" diff --git a/src/basic/virt.c b/src/basic/virt.c index eb67949166..0ffc2769d2 100644 --- a/src/basic/virt.c +++ b/src/basic/virt.c @@ -26,9 +26,11 @@ #include <unistd.h> #include "alloc-util.h" +#include "dirent-util.h" +#include "fd-util.h" #include "fileio.h" -#include "process-util.h" #include "macro.h" +#include "process-util.h" #include "stat-util.h" #include "string-table.h" #include "string-util.h" diff --git a/src/basic/xattr-util.c b/src/basic/xattr-util.c index 166e2b23fa..960209282f 100644 --- a/src/basic/xattr-util.c +++ b/src/basic/xattr-util.c @@ -29,10 +29,10 @@ #include "alloc-util.h" #include "fd-util.h" -#include "sparse-endian.h" #include "macro.h" -#include "time-util.h" +#include "sparse-endian.h" #include "stdio-util.h" +#include "time-util.h" #include "xattr-util.h" int getxattr_malloc(const char *path, const char *name, char **value, bool allow_symlink) { |