basic: remove rbtree code, it's unused

it's unused, and should we need it one day we can always resurrect it from git
history.

1 files changed, 0 insertions, 297 deletions

diff --git a/src/basic/c-rbtree.h b/src/basic/c-rbtree.h
deleted file mode 100644
index 20c5515ca1..0000000000
--- a/src/basic/c-rbtree.h
+++ /dev/null
@@ -1,297 +0,0 @@
-#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