summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorRichard Braun <rbraun@sceen.net>2018-01-04 21:50:05 +0100
committerRichard Braun <rbraun@sceen.net>2018-01-04 21:50:05 +0100
commitb03224b9a82a4d46fd1e469821975f9a5295ed40 (patch)
tree7830e5dc6316f4d29abb3c27c8a7ef77684446df /src
parente7321910ca4d956b572a050d302a25df37ce06ab (diff)
Move sources to new src/ directory
Diffstat (limited to 'src')
-rw-r--r--src/avltree.c601
-rw-r--r--src/avltree.h329
-rw-r--r--src/avltree_i.h203
-rw-r--r--src/bitmap.c124
-rw-r--r--src/bitmap.h214
-rw-r--r--src/bitmap_i.h69
-rw-r--r--src/cbuf.c202
-rw-r--r--src/cbuf.h150
-rw-r--r--src/check.h47
-rw-r--r--src/cpu.h84
-rw-r--r--src/fmt.c1462
-rw-r--r--src/fmt.h69
-rw-r--r--src/hash.h124
-rw-r--r--src/hlist.h418
-rw-r--r--src/list.c141
-rw-r--r--src/list.h555
-rw-r--r--src/macros.h90
-rw-r--r--src/plist.c73
-rw-r--r--src/plist.h296
-rw-r--r--src/rbtree.c558
-rw-r--r--src/rbtree.h328
-rw-r--r--src/rbtree_i.h197
-rw-r--r--src/rdxtree.c863
-rw-r--r--src/rdxtree.h224
-rw-r--r--src/rdxtree_i.h71
-rw-r--r--src/shell.c1196
-rw-r--r--src/shell.h106
-rw-r--r--src/slist.h468
28 files changed, 9262 insertions, 0 deletions
diff --git a/src/avltree.c b/src/avltree.c
new file mode 100644
index 0000000..91839a5
--- /dev/null
+++ b/src/avltree.c
@@ -0,0 +1,601 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "macros.h"
+#include "avltree.h"
+#include "avltree_i.h"
+
+/*
+ * Convert an index of the children array (0 or 1) into a balance value
+ * (-1 or 1).
+ */
+static inline int
+avltree_i2b(int index)
+{
+ assert(avltree_check_index(index));
+ return (index - 1) | 1;
+}
+
+/*
+ * Return the index of a node in the children array of its parent.
+ *
+ * The parent parameter must not be NULL, and must be the parent of the
+ * given node.
+ */
+static inline int
+avltree_node_index(const struct avltree_node *node,
+ const struct avltree_node *parent)
+{
+ assert(parent != NULL);
+ assert((node == NULL) || (avltree_node_parent(node) == parent));
+
+ if (parent->children[AVLTREE_LEFT] == node) {
+ return AVLTREE_LEFT;
+ }
+
+ assert(parent->children[AVLTREE_RIGHT] == node);
+
+ return AVLTREE_RIGHT;
+}
+
+/*
+ * Return the balance of a node.
+ */
+static inline int
+avltree_node_balance(const struct avltree_node *node)
+{
+ int balance;
+
+ balance = (node->parent & AVLTREE_BALANCE_MASK);
+ assert(balance != AVLTREE_BALANCE_INVALID);
+
+ return balance - 1;
+}
+
+/*
+ * Set the parent of a node, retaining its current balance.
+ */
+static inline void
+avltree_node_set_parent(struct avltree_node *node, struct avltree_node *parent)
+{
+ assert(avltree_node_check_alignment(node));
+ assert(avltree_node_check_alignment(parent));
+ node->parent = (uintptr_t)parent | (node->parent & AVLTREE_BALANCE_MASK);
+}
+
+/*
+ * Set the balance of a node, retaining its current parent.
+ */
+static inline void
+avltree_node_set_balance(struct avltree_node *node, int balance)
+{
+ assert((-1 <= balance) && (balance <= 1));
+ node->parent = (node->parent & AVLTREE_PARENT_MASK) | (balance + 1);
+}
+
+/*
+ * Return the left-most deepest child node of the given node.
+ */
+static struct avltree_node *
+avltree_node_find_deepest(struct avltree_node *node)
+{
+ struct avltree_node *parent;
+
+ assert(node != NULL);
+
+ for (;;) {
+ parent = node;
+ node = node->children[AVLTREE_LEFT];
+
+ if (node == NULL) {
+ node = parent->children[AVLTREE_RIGHT];
+
+ if (node == NULL) {
+ return parent;
+ }
+ }
+ }
+}
+
+/*
+ * Rotate an unbalanced tree.
+ *
+ * This function is called after the insertion or the removal of a node made
+ * a tree unbalanced. The node and balance parameters define the rotation root
+ * (the balance being either -2 or 2).
+ *
+ * Return true if the overall height of the subtree rooted at node has
+ * decreased, false otherwise.
+ */
+static int
+avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance)
+{
+ struct avltree_node *parent, *lnode, *lrnode, *lrlnode, *lrrnode;
+ int left, right, lweight, rweight, lbalance;
+ int index = 0; /* GCC */
+
+ assert((balance == -2) || (balance == 2));
+
+ left = avltree_d2i(balance);
+ right = 1 - left;
+ lweight = balance >> 1;
+ rweight = -lweight;
+
+ parent = avltree_node_parent(node);
+
+ if (likely(parent != NULL)) {
+ index = avltree_node_index(node, parent);
+ }
+
+ lnode = node->children[left];
+ assert(lnode != NULL);
+ lbalance = avltree_node_balance(lnode);
+ lrnode = lnode->children[right];
+
+ /*
+ * Left-left case. Note that only a removal can set the left node balance
+ * to 0 when rotating.
+ */
+ if (lbalance != rweight) {
+ node->children[left] = lrnode;
+
+ if (lrnode != NULL) {
+ avltree_node_set_parent(lrnode, node);
+ }
+
+ lbalance += rweight;
+
+ lnode->children[right] = node;
+
+ avltree_node_set_parent(node, lnode);
+ avltree_node_set_balance(node, -lbalance);
+
+ avltree_node_set_parent(lnode, parent);
+ avltree_node_set_balance(lnode, lbalance);
+
+ if (unlikely(parent == NULL)) {
+ tree->root = lnode;
+ } else {
+ parent->children[index] = lnode;
+ }
+
+ /*
+ * If the adjusted balance is now 0, it means that the height of the
+ * left subtree has decreased.
+ */
+ return (lbalance == 0);
+ }
+
+ /*
+ * Left-right case.
+ */
+
+ assert(lrnode != NULL);
+ lrlnode = lrnode->children[left];
+ lrrnode = lrnode->children[right];
+
+ node->children[left] = lrrnode;
+
+ if (lrrnode != NULL) {
+ avltree_node_set_parent(lrrnode, node);
+ }
+
+ lnode->children[right] = lrlnode;
+
+ if (lrlnode != NULL) {
+ avltree_node_set_parent(lrlnode, lnode);
+ }
+
+ balance = avltree_node_balance(lrnode);
+
+ lrnode->children[left] = lnode;
+ avltree_node_set_parent(lnode, lrnode);
+ avltree_node_set_balance(lnode, ((balance == rweight) ? lweight : 0));
+
+ lrnode->children[right] = node;
+ avltree_node_set_parent(node, lrnode);
+ avltree_node_set_balance(node, ((balance == lweight) ? rweight : 0));
+
+ avltree_node_set_parent(lrnode, parent);
+ avltree_node_set_balance(lrnode, 0);
+
+ if (unlikely(parent == NULL)) {
+ tree->root = lrnode;
+ } else {
+ parent->children[index] = lrnode;
+ }
+
+ /*
+ * The balance of the new subtree root is always 0 in this case, which
+ * implies the overall subtree height has decreased.
+ */
+ return 1;
+}
+
+void
+avltree_insert_rebalance(struct avltree *tree, struct avltree_node *parent,
+ int index, struct avltree_node *node)
+{
+ int old_balance, new_balance;
+
+ assert(avltree_node_check_alignment(parent));
+ assert(avltree_node_check_alignment(node));
+
+ node->parent = (uintptr_t)parent | AVLTREE_BALANCE_ZERO;
+ node->children[AVLTREE_LEFT] = NULL;
+ node->children[AVLTREE_RIGHT] = NULL;
+
+ /*
+ * The node is the tree root, and is the single tree entry.
+ */
+ if (parent == NULL) {
+ assert(tree->root == NULL);
+ tree->root = node;
+ return;
+ }
+
+ assert(avltree_check_index(index));
+ assert(parent->children[index] == NULL);
+ parent->children[index] = node;
+
+ for (;;) {
+ node = parent;
+
+ old_balance = avltree_node_balance(node);
+ new_balance = old_balance + avltree_i2b(index);
+
+ /*
+ * Perfect balance, stop now.
+ */
+ if (new_balance == 0) {
+ avltree_node_set_balance(node, 0);
+ return;
+ }
+
+ /*
+ * Both previous and new balances are different from 0, which means the
+ * new one has reached -2 or 2. Rebalance now.
+ */
+ if (old_balance != 0) {
+ break;
+ }
+
+ /*
+ * The new balance is either -1 or 1. Update the current node and
+ * iterate again to propagate the height change.
+ */
+ avltree_node_set_balance(node, new_balance);
+ parent = avltree_node_parent(node);
+
+ /*
+ * The tree root was reached.
+ */
+ if (parent == NULL) {
+ return;
+ }
+
+ index = avltree_node_index(node, parent);
+ }
+
+ avltree_rotate(tree, node, new_balance);
+}
+
+void *
+avltree_replace_slot(struct avltree *tree, avltree_slot_t slot,
+ struct avltree_node *node)
+{
+ struct avltree_node *parent, *prev;
+ int index;
+
+ parent = avltree_slot_parent(slot);
+
+ if (!parent) {
+ prev = tree->root;
+ tree->root = node;
+ } else {
+ index = avltree_slot_index(slot);
+ assert(avltree_check_index(index));
+ prev = parent->children[index];
+ parent->children[index] = node;
+ }
+
+ assert(prev);
+ *node = *prev;
+
+ for (size_t i = 0; i < ARRAY_SIZE(node->children); i++) {
+ if (!node->children[i]) {
+ continue;
+ }
+
+
+ avltree_node_set_parent(node->children[i], node);
+ }
+
+ return prev;
+}
+
+void
+avltree_remove(struct avltree *tree, struct avltree_node *node)
+{
+ struct avltree_node *child, *parent;
+ int left, right, index, old_balance, new_balance;
+
+ if (node->children[AVLTREE_LEFT] == NULL) {
+ child = node->children[AVLTREE_RIGHT];
+ } else if (node->children[AVLTREE_RIGHT] == NULL) {
+ child = node->children[AVLTREE_LEFT];
+ } else {
+ struct avltree_node *successor;
+
+ /*
+ * Two-children case: replace the node with one of its successors. The
+ * choice of the successor depends on the balance of the node to remove,
+ * as swapping with a node in a heavier subtree can reduce the number of
+ * rotations needed to rebalance the tree.
+ */
+
+ old_balance = avltree_node_balance(node);
+ right = avltree_d2i(old_balance);
+ left = 1 - right;
+
+ successor = node->children[right];
+
+ while (successor->children[left] != NULL) {
+ successor = successor->children[left];
+ }
+
+ child = successor->children[right];
+ parent = avltree_node_parent(node);
+
+ if (unlikely(parent == NULL)) {
+ tree->root = successor;
+ } else {
+ parent->children[avltree_node_index(node, parent)] = successor;
+ }
+
+ parent = avltree_node_parent(successor);
+ index = avltree_node_index(successor, parent);
+
+ /*
+ * Set parent directly to keep the original balance.
+ */
+ successor->parent = node->parent;
+ successor->children[left] = node->children[left];
+ avltree_node_set_parent(successor->children[left], successor);
+
+ if (node == parent) {
+ parent = successor;
+ } else {
+ successor->children[right] = node->children[right];
+ avltree_node_set_parent(successor->children[right], successor);
+ parent->children[left] = child;
+
+ if (child != NULL) {
+ avltree_node_set_parent(child, parent);
+ }
+ }
+
+ goto update_balance;
+ }
+
+ /*
+ * Node has at most one child.
+ */
+
+ parent = avltree_node_parent(node);
+
+ if (child != NULL) {
+ avltree_node_set_parent(child, parent);
+ }
+
+ if (parent == NULL) {
+ tree->root = child;
+ return;
+ } else {
+ index = avltree_node_index(node, parent);
+ parent->children[index] = child;
+ }
+
+ /*
+ * The node has been removed, update the balance factors. At this point,
+ * the node parent and the index of the node in its parent children array
+ * must be valid.
+ */
+update_balance:
+ for (;;) {
+ node = parent;
+
+ old_balance = avltree_node_balance(node);
+ new_balance = old_balance - avltree_i2b(index);
+
+ /*
+ * The overall subtree height hasn't decreased, stop now.
+ */
+ if (old_balance == 0) {
+ avltree_node_set_balance(node, new_balance);
+ break;
+ }
+
+ parent = avltree_node_parent(node);
+
+ if (parent != NULL) {
+ index = avltree_node_index(node, parent);
+ }
+
+ /*
+ * The overall subtree height has decreased. Update the current node and
+ * iterate again to propagate the change.
+ */
+ if (new_balance == 0) {
+ avltree_node_set_balance(node, new_balance);
+ } else {
+ int decreased;
+
+ /*
+ * The new balance is either -2 or 2. Rebalance the tree and exit
+ * the loop if the rotation hasn't decreased the overall tree
+ * height.
+ */
+
+ decreased = avltree_rotate(tree, node, new_balance);
+
+ if (!decreased) {
+ break;
+ }
+ }
+
+ /*
+ * The tree root was reached.
+ */
+ if (parent == NULL) {
+ break;
+ }
+ }
+}
+
+struct avltree_node *
+avltree_nearest(struct avltree_node *parent, int index, int direction)
+{
+ assert(avltree_check_index(direction));
+
+ if (parent == NULL) {
+ return NULL;
+ }
+
+ assert(avltree_check_index(index));
+
+ if (index != direction) {
+ return parent;
+ }
+
+ return avltree_walk(parent, direction);
+}
+
+struct avltree_node *
+avltree_firstlast(const struct avltree *tree, int direction)
+{
+ struct avltree_node *prev, *cur;
+
+ assert(avltree_check_index(direction));
+
+ prev = NULL;
+
+ for (cur = tree->root; cur != NULL; cur = cur->children[direction]) {
+ prev = cur;
+ }
+
+ return prev;
+}
+
+struct avltree_node *
+avltree_walk(struct avltree_node *node, int direction)
+{
+ int left, right;
+
+ assert(avltree_check_index(direction));
+
+ left = direction;
+ right = 1 - left;
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ if (node->children[left] != NULL) {
+ node = node->children[left];
+
+ while (node->children[right] != NULL) {
+ node = node->children[right];
+ }
+ } else {
+ struct avltree_node *parent;
+ int index;
+
+ for (;;) {
+ parent = avltree_node_parent(node);
+
+ if (parent == NULL) {
+ return NULL;
+ }
+
+ index = avltree_node_index(node, parent);
+ node = parent;
+
+ if (index == right) {
+ break;
+ }
+ }
+ }
+
+ return node;
+}
+
+struct avltree_node *
+avltree_postwalk_deepest(const struct avltree *tree)
+{
+ struct avltree_node *node;
+
+ node = tree->root;
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ return avltree_node_find_deepest(node);
+}
+
+struct avltree_node *
+avltree_postwalk_unlink(struct avltree_node *node)
+{
+ struct avltree_node *parent;
+ int index;
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ assert(node->children[AVLTREE_LEFT] == NULL);
+ assert(node->children[AVLTREE_RIGHT] == NULL);
+
+ parent = avltree_node_parent(node);
+
+ if (parent == NULL) {
+ return NULL;
+ }
+
+ index = avltree_node_index(node, parent);
+ parent->children[index] = NULL;
+ node = parent->children[AVLTREE_RIGHT];
+
+ if (node == NULL) {
+ return parent;
+ }
+
+ return avltree_node_find_deepest(node);
+}
diff --git a/src/avltree.h b/src/avltree.h
new file mode 100644
index 0000000..ce6c49f
--- /dev/null
+++ b/src/avltree.h
@@ -0,0 +1,329 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * AVL tree.
+ *
+ * This type of tree is well suited for lookup intensive applications. In
+ * the more common case where there can be as many insertions/removals as
+ * lookups, or the amount of changes can't be determined, red-black trees
+ * provide better average performance.
+ */
+
+#ifndef _AVLTREE_H
+#define _AVLTREE_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "macros.h"
+
+/*
+ * Indexes of the left and right nodes in the children array of a node.
+ */
+#define AVLTREE_LEFT 0
+#define AVLTREE_RIGHT 1
+
+/*
+ * AVL node.
+ */
+struct avltree_node;
+
+/*
+ * AVL tree.
+ */
+struct avltree;
+
+/*
+ * Insertion point identifier.
+ */
+typedef uintptr_t avltree_slot_t;
+
+/*
+ * Static tree initializer.
+ */
+#define AVLTREE_INITIALIZER { NULL }
+
+#include "avltree_i.h"
+
+/*
+ * Initialize a tree.
+ */
+static inline void
+avltree_init(struct avltree *tree)
+{
+ tree->root = NULL;
+}
+
+/*
+ * Initialize a node.
+ *
+ * A node is in no tree when its parent points to itself.
+ */
+static inline void
+avltree_node_init(struct avltree_node *node)
+{
+ assert(avltree_node_check_alignment(node));
+
+ node->parent = (uintptr_t)node | AVLTREE_BALANCE_ZERO;
+ node->children[AVLTREE_LEFT] = NULL;
+ node->children[AVLTREE_RIGHT] = NULL;
+}
+
+/*
+ * Return true if node is in no tree.
+ */
+static inline int
+avltree_node_unlinked(const struct avltree_node *node)
+{
+ return avltree_node_parent(node) == node;
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define avltree_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Return true if tree is empty.
+ */
+static inline int
+avltree_empty(const struct avltree *tree)
+{
+ return tree->root == NULL;
+}
+
+/*
+ * Look up a node in a tree.
+ *
+ * Note that implementing the lookup algorithm as a macro gives two benefits:
+ * First, it avoids the overhead of a callback function. Next, the type of the
+ * cmp_fn parameter isn't rigid. The only guarantee offered by this
+ * implementation is that the key parameter is the first parameter given to
+ * cmp_fn. This way, users can pass only the value they need for comparison
+ * instead of e.g. allocating a full structure on the stack.
+ */
+#define avltree_lookup(tree, key, cmp_fn) \
+MACRO_BEGIN \
+ struct avltree_node *___cur; \
+ int ___diff; \
+ \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(key, ___cur); \
+ \
+ if (___diff == 0) { \
+ break; \
+ } \
+ \
+ ___cur = ___cur->children[avltree_d2i(___diff)]; \
+ } \
+ \
+ ___cur; \
+MACRO_END
+
+/*
+ * Look up a node or one of its nearest nodes in a tree.
+ *
+ * This macro essentially acts as avltree_lookup() but if no entry matched
+ * the key, an additional step is performed to obtain the next or previous
+ * node, depending on the direction (left or right).
+ *
+ * The constraints that apply to the key parameter are the same as for
+ * avltree_lookup().
+ */
+#define avltree_lookup_nearest(tree, key, cmp_fn, dir) \
+MACRO_BEGIN \
+ struct avltree_node *___cur, *___prev; \
+ int ___diff, ___index; \
+ \
+ ___prev = NULL; \
+ ___index = 0; \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(key, ___cur); \
+ \
+ if (___diff == 0) { \
+ break; \
+ } \
+ \
+ ___prev = ___cur; \
+ ___index = avltree_d2i(___diff); \
+ ___cur = ___cur->children[___index]; \
+ } \
+ \
+ if (___cur == NULL) { \
+ ___cur = avltree_nearest(___prev, ___index, dir); \
+ } \
+ \
+ ___cur; \
+MACRO_END
+
+/*
+ * Insert a node in a tree.
+ *
+ * This macro performs a standard lookup to obtain the insertion point of
+ * the given node in the tree (it is assumed that the inserted node never
+ * compares equal to any other entry in the tree) and links the node. It
+ * then updates and checks balances of the parent nodes, and rebalances the
+ * tree if necessary.
+ *
+ * Unlike avltree_lookup(), the cmp_fn parameter must compare two complete
+ * entries, so it is suggested to use two different comparison inline
+ * functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no
+ * guarantee about the order of the nodes given to the comparison function.
+ */
+#define avltree_insert(tree, node, cmp_fn) \
+MACRO_BEGIN \
+ struct avltree_node *___cur, *___prev; \
+ int ___diff, ___index; \
+ \
+ ___prev = NULL; \
+ ___index = 0; \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(node, ___cur); \
+ assert(___diff != 0); \
+ ___prev = ___cur; \
+ ___index = avltree_d2i(___diff); \
+ ___cur = ___cur->children[___index]; \
+ } \
+ \
+ avltree_insert_rebalance(tree, ___prev, ___index, node); \
+MACRO_END
+
+/*
+ * Look up a node/slot pair in a tree.
+ *
+ * This macro essentially acts as avltree_lookup() but in addition to a node,
+ * it also returns a slot, which identifies an insertion point in the tree.
+ * If the returned node is NULL, the slot can be used by avltree_insert_slot()
+ * to insert without the overhead of an additional lookup.
+ *
+ * The constraints that apply to the key parameter are the same as for
+ * avltree_lookup().
+ */
+#define avltree_lookup_slot(tree, key, cmp_fn, slot) \
+MACRO_BEGIN \
+ struct avltree_node *___cur, *___prev; \
+ int ___diff, ___index; \
+ \
+ ___prev = NULL; \
+ ___index = 0; \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(key, ___cur); \
+ \
+ if (___diff == 0) { \
+ break; \
+ } \
+ \
+ ___prev = ___cur; \
+ ___index = avltree_d2i(___diff); \
+ ___cur = ___cur->children[___index]; \
+ } \
+ \
+ (slot) = avltree_slot(___prev, ___index); \
+ ___cur; \
+MACRO_END
+
+/*
+ * Insert a node at an insertion point in a tree.
+ *
+ * This macro essentially acts as avltree_insert() except that it doesn't
+ * obtain the insertion point with a standard lookup. The insertion point
+ * is obtained by calling avltree_lookup_slot(). In addition, the new node
+ * must not compare equal to an existing node in the tree (i.e. the slot
+ * must denote a NULL node).
+ */
+static inline void
+avltree_insert_slot(struct avltree *tree, avltree_slot_t slot,
+ struct avltree_node *node)
+{
+ struct avltree_node *parent;
+ int index;
+
+ parent = avltree_slot_parent(slot);
+ index = avltree_slot_index(slot);
+ avltree_insert_rebalance(tree, parent, index, node);
+}
+
+/*
+ * Replace a node at an insertion point in a tree.
+ *
+ * The given node must compare strictly equal to the previous node,
+ * which is returned on completion.
+ */
+void * avltree_replace_slot(struct avltree *tree, avltree_slot_t slot,
+ struct avltree_node *node);
+
+/*
+ * Remove a node from a tree.
+ *
+ * After completion, the node is stale.
+ */
+void avltree_remove(struct avltree *tree, struct avltree_node *node);
+
+/*
+ * Return the first node of a tree.
+ */
+#define avltree_first(tree) avltree_firstlast(tree, AVLTREE_LEFT)
+
+/*
+ * Return the last node of a tree.
+ */
+#define avltree_last(tree) avltree_firstlast(tree, AVLTREE_RIGHT)
+
+/*
+ * Return the node previous to the given node.
+ */
+#define avltree_prev(node) avltree_walk(node, AVLTREE_LEFT)
+
+/*
+ * Return the node next to the given node.
+ */
+#define avltree_next(node) avltree_walk(node, AVLTREE_RIGHT)
+
+/*
+ * Forge a loop to process all nodes of a tree, removing them when visited.
+ *
+ * This macro can only be used to destroy a tree, so that the resources used
+ * by the entries can be released by the user. It basically removes all nodes
+ * without doing any balance checking.
+ *
+ * After completion, all nodes and the tree root member are stale.
+ */
+#define avltree_for_each_remove(tree, node, tmp) \
+for (node = avltree_postwalk_deepest(tree), \
+ tmp = avltree_postwalk_unlink(node); \
+ node != NULL; \
+ node = tmp, tmp = avltree_postwalk_unlink(node))
+
+#endif /* _AVLTREE_H */
diff --git a/src/avltree_i.h b/src/avltree_i.h
new file mode 100644
index 0000000..37baa61
--- /dev/null
+++ b/src/avltree_i.h
@@ -0,0 +1,203 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#ifndef _AVLTREE_I_H
+#define _AVLTREE_I_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "macros.h"
+
+/*
+ * AVL node structure.
+ *
+ * To reduce the number of branches and the instruction cache footprint,
+ * the left and right child pointers are stored in an array, and the symmetry
+ * of most tree operations is exploited by using left/right variables when
+ * referring to children.
+ *
+ * In addition, this implementation assumes that all nodes are at least 4-byte
+ * aligned, so that the two least significant bits of the parent member can
+ * be used to store the balance of the node. This is true for all modern 32
+ * and 64 bits architectures, as long as the nodes aren't embedded in
+ * structures with special alignment constraints such as member packing.
+ *
+ * To avoid issues with signed operations when handling a negative balance,
+ * the raw values stored in the parent member are always positive, and are
+ * actually one more than the value they represent. It is then easy to obtain
+ * a balance of -1 from a raw value of 0.
+ */
+struct avltree_node {
+ uintptr_t parent;
+ struct avltree_node *children[2];
+};
+
+/*
+ * AVL tree structure.
+ */
+struct avltree {
+ struct avltree_node *root;
+};
+
+/*
+ * Masks applied on the parent member of a node to obtain either the
+ * balance or the parent address.
+ */
+#define AVLTREE_BALANCE_MASK ((uintptr_t)0x3)
+#define AVLTREE_PARENT_MASK (~AVLTREE_BALANCE_MASK)
+
+/*
+ * Special raw balance values.
+ */
+#define AVLTREE_BALANCE_ZERO ((uintptr_t)1)
+#define AVLTREE_BALANCE_INVALID AVLTREE_BALANCE_MASK
+
+/*
+ * Masks applied on slots to obtain either the child index or the parent
+ * address.
+ */
+#define AVLTREE_SLOT_INDEX_MASK ((uintptr_t)0x1)
+#define AVLTREE_SLOT_PARENT_MASK (~AVLTREE_SLOT_INDEX_MASK)
+
+/*
+ * Return true if the given index is a valid child index.
+ */
+static inline int
+avltree_check_index(int index)
+{
+ return index == (index & 1);
+}
+
+/*
+ * Convert the result of a comparison (or a balance) into an index in the
+ * children array (0 or 1).
+ *
+ * This function is mostly used when looking up a node.
+ */
+static inline int
+avltree_d2i(int diff)
+{
+ return !(diff <= 0);
+}
+
+/*
+ * Return true if the given pointer is suitably aligned.
+ */
+static inline int
+avltree_node_check_alignment(const struct avltree_node *node)
+{
+ return ((uintptr_t)node & AVLTREE_BALANCE_MASK) == 0;
+}
+
+/*
+ * Return the parent of a node.
+ */
+static inline struct avltree_node *
+avltree_node_parent(const struct avltree_node *node)
+{
+ return (struct avltree_node *)(node->parent & AVLTREE_PARENT_MASK);
+}
+
+/*
+ * Translate an insertion point into a slot.
+ */
+static inline avltree_slot_t
+avltree_slot(struct avltree_node *parent, int index)
+{
+ assert(avltree_node_check_alignment(parent));
+ assert(avltree_check_index(index));
+ return (avltree_slot_t)parent | index;
+}
+
+/*
+ * Extract the parent address from a slot.
+ */
+static inline struct avltree_node *
+avltree_slot_parent(avltree_slot_t slot)
+{
+ return (struct avltree_node *)(slot & AVLTREE_SLOT_PARENT_MASK);
+}
+
+/*
+ * Extract the index from a slot.
+ */
+static inline int
+avltree_slot_index(avltree_slot_t slot)
+{
+ return slot & AVLTREE_SLOT_INDEX_MASK;
+}
+
+/*
+ * Insert a node in a tree, rebalancing it if necessary.
+ *
+ * The index parameter is the index in the children array of the parent where
+ * the new node is to be inserted. It is ignored if the parent is NULL.
+ *
+ * This function is intended to be used by the avltree_insert() macro only.
+ */
+void avltree_insert_rebalance(struct avltree *tree, struct avltree_node *parent,
+ int index, struct avltree_node *node);
+
+/*
+ * Return the previous or next node relative to a location in a tree.
+ *
+ * The parent and index parameters define the location, which can be empty.
+ * The direction parameter is either AVLTREE_LEFT (to obtain the previous
+ * node) or AVLTREE_RIGHT (to obtain the next one).
+ */
+struct avltree_node * avltree_nearest(struct avltree_node *parent, int index,
+ int direction);
+
+/*
+ * Return the first or last node of a tree.
+ *
+ * The direction parameter is either AVLTREE_LEFT (to obtain the first node)
+ * or AVLTREE_RIGHT (to obtain the last one).
+ */
+struct avltree_node * avltree_firstlast(const struct avltree *tree,
+ int direction);
+
+/*
+ * Return the node next to, or previous to the given node.
+ *
+ * The direction parameter is either AVLTREE_LEFT (to obtain the previous node)
+ * or AVLTREE_RIGHT (to obtain the next one).
+ */
+struct avltree_node * avltree_walk(struct avltree_node *node, int direction);
+
+/*
+ * Return the left-most deepest node of a tree, which is the starting point of
+ * the postorder traversal performed by avltree_for_each_remove().
+ */
+struct avltree_node * avltree_postwalk_deepest(const struct avltree *tree);
+
+/*
+ * Unlink a node from its tree and return the next (right) node in postorder.
+ */
+struct avltree_node * avltree_postwalk_unlink(struct avltree_node *node);
+
+#endif /* _AVLTREE_I_H */
diff --git a/src/bitmap.c b/src/bitmap.c
new file mode 100644
index 0000000..d449c3d
--- /dev/null
+++ b/src/bitmap.c
@@ -0,0 +1,124 @@
+/*
+ * Copyright (c) 2013-2015 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include <limits.h>
+#include <stddef.h>
+#include <string.h>
+
+#include "bitmap.h"
+#include "bitmap_i.h"
+
+int
+bitmap_cmp(const unsigned long *a, const unsigned long *b, int nr_bits)
+{
+ unsigned long last_a, last_b, mask;
+ int n, rv;
+
+ n = BITMAP_LONGS(nr_bits) - 1;
+
+ if (n != 0) {
+ rv = memcmp(a, b, n * sizeof(unsigned long));
+
+ if (rv != 0) {
+ return rv;
+ }
+
+ nr_bits -= n * LONG_BIT;
+ }
+
+ last_a = a[n];
+ last_b = b[n];
+
+ if (nr_bits != LONG_BIT) {
+ mask = (1UL << nr_bits) - 1;
+ last_a &= mask;
+ last_b &= mask;
+ }
+
+ if (last_a == last_b) {
+ return 0;
+ } else if (last_a < last_b) {
+ return -1;
+ } else {
+ return 1;
+ }
+}
+
+static inline unsigned long
+bitmap_find_next_compute_complement(unsigned long word, int nr_bits)
+{
+ if (nr_bits < LONG_BIT) {
+ word |= (((unsigned long)-1) << nr_bits);
+ }
+
+ return ~word;
+}
+
+int
+bitmap_find_next_bit(const unsigned long *bm, int nr_bits, int bit,
+ int complement)
+{
+ const unsigned long *start, *end;
+ unsigned long word;
+
+ start = bm;
+ end = bm + BITMAP_LONGS(nr_bits);
+
+ if (bit >= LONG_BIT) {
+ bitmap_lookup(&bm, &bit);
+ nr_bits -= ((bm - start) * LONG_BIT);
+ }
+
+ word = *bm;
+
+ if (complement) {
+ word = bitmap_find_next_compute_complement(word, nr_bits);
+ }
+
+ if (bit < LONG_BIT) {
+ word &= ~(bitmap_mask(bit) - 1);
+ }
+
+ for (;;) {
+ bit = __builtin_ffsl(word);
+
+ if (bit != 0) {
+ return ((bm - start) * LONG_BIT) + bit - 1;
+ }
+
+ bm++;
+
+ if (bm >= end) {
+ return -1;
+ }
+
+ nr_bits -= LONG_BIT;
+ word = *bm;
+
+ if (complement) {
+ word = bitmap_find_next_compute_complement(word, nr_bits);
+ }
+ }
+}
diff --git a/src/bitmap.h b/src/bitmap.h
new file mode 100644
index 0000000..7d5db63
--- /dev/null
+++ b/src/bitmap.h
@@ -0,0 +1,214 @@
+/*
+ * Copyright (c) 2013-2015 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Arbitrary-length bit arrays.
+ *
+ * Most functions do not check whether the given parameters are valid. This
+ * is the responsibility of the caller.
+ */
+
+#ifndef _BITMAP_H
+#define _BITMAP_H
+
+#include <limits.h>
+#include <stdatomic.h>
+#include <string.h>
+
+#include "bitmap_i.h"
+
+#define BITMAP_DECLARE(name, nr_bits) unsigned long name[BITMAP_LONGS(nr_bits)]
+
+int bitmap_cmp(const unsigned long *a, const unsigned long *b, int nr_bits);
+
+static inline void
+bitmap_zero(unsigned long *bm, int nr_bits)
+{
+ int n;
+
+ n = BITMAP_LONGS(nr_bits);
+ memset(bm, 0, n * sizeof(unsigned long));
+}
+
+static inline void
+bitmap_fill(unsigned long *bm, int nr_bits)
+{
+ int n;
+
+ n = BITMAP_LONGS(nr_bits);
+ memset(bm, 0xff, n * sizeof(unsigned long));
+}
+
+static inline void
+bitmap_copy(unsigned long *dest, const unsigned long *src, int nr_bits)
+{
+ int n;
+
+ n = BITMAP_LONGS(nr_bits);
+ memcpy(dest, src, n * sizeof(unsigned long));
+}
+
+static inline void
+bitmap_set(unsigned long *bm, int bit)
+{
+ if (bit >= LONG_BIT) {
+ bitmap_lookup(&bm, &bit);
+ }
+
+ *bm |= bitmap_mask(bit);
+}
+
+static inline void
+bitmap_set_atomic(unsigned long *bm, int bit)
+{
+ atomic_ulong *ptr;
+
+ if (bit >= LONG_BIT) {
+ bitmap_lookup(&bm, &bit);
+ }
+
+ ptr = (atomic_ulong *)bm;
+ atomic_fetch_or_explicit(ptr, bitmap_mask(bit), memory_order_release);
+}
+
+static inline void
+bitmap_clear(unsigned long *bm, int bit)
+{
+ if (bit >= LONG_BIT) {
+ bitmap_lookup(&bm, &bit);
+ }
+
+ *bm &= ~bitmap_mask(bit);
+}
+
+static inline void
+bitmap_clear_atomic(unsigned long *bm, int bit)
+{
+ atomic_ulong *ptr;
+
+ if (bit >= LONG_BIT) {
+ bitmap_lookup(&bm, &bit);
+ }
+
+ ptr = (atomic_ulong *)bm;
+ atomic_fetch_and_explicit(ptr, ~bitmap_mask(bit), memory_order_acquire);
+}
+
+static inline int
+bitmap_test(const unsigned long *bm, int bit)
+{
+ if (bit >= LONG_BIT) {
+ bitmap_lookup(&bm, &bit);
+ }
+
+ return ((*bm & bitmap_mask(bit)) != 0);
+}
+
+static inline int
+bitmap_test_atomic(const unsigned long *bm, int bit)
+{
+ atomic_ulong *ptr;
+
+ if (bit >= LONG_BIT) {
+ bitmap_lookup(&bm, &bit);
+ }
+
+ ptr = (atomic_ulong *)bm;
+ return ((atomic_load_explicit(ptr, memory_order_acquire)
+ & bitmap_mask(bit)) != 0);
+}
+
+static inline void
+bitmap_and(unsigned long *a, const unsigned long *b, int nr_bits)
+{
+ int i, n;
+
+ n = BITMAP_LONGS(nr_bits);
+
+ for (i = 0; i < n; i++) {
+ a[i] &= b[i];
+ }
+}
+
+static inline void
+bitmap_or(unsigned long *a, const unsigned long *b, int nr_bits)
+{
+ int i, n;
+
+ n = BITMAP_LONGS(nr_bits);
+
+ for (i = 0; i < n; i++) {
+ a[i] |= b[i];
+ }
+}
+
+static inline void
+bitmap_xor(unsigned long *a, const unsigned long *b, int nr_bits)
+{
+ int i, n;
+
+ n = BITMAP_LONGS(nr_bits);
+
+ for (i = 0; i < n; i++) {
+ a[i] ^= b[i];
+ }
+}
+
+static inline int
+bitmap_find_next(const unsigned long *bm, int nr_bits, int bit)
+{
+ return bitmap_find_next_bit(bm, nr_bits, bit, 0);
+}
+
+static inline int
+bitmap_find_first(const unsigned long *bm, int nr_bits)
+{
+ return bitmap_find_next(bm, nr_bits, 0);
+}
+
+static inline int
+bitmap_find_next_zero(const unsigned long *bm, int nr_bits, int bit)
+{
+ return bitmap_find_next_bit(bm, nr_bits, bit, 1);
+}
+
+static inline int
+bitmap_find_first_zero(const unsigned long *bm, int nr_bits)
+{
+ return bitmap_find_next_zero(bm, nr_bits, 0);
+}
+
+#define bitmap_for_each(bm, nr_bits, bit) \
+for ((bit) = 0; \
+ ((bit) < nr_bits) \
+ && (((bit) = bitmap_find_next(bm, nr_bits, bit)) != -1); \
+ (bit)++)
+
+#define bitmap_for_each_zero(bm, nr_bits, bit) \
+for ((bit) = 0; \
+ ((bit) < nr_bits) \
+ && (((bit) = bitmap_find_next_zero(bm, nr_bits, bit)) != -1); \
+ (bit)++)
+
+#endif /* _BITMAP_H */
diff --git a/src/bitmap_i.h b/src/bitmap_i.h
new file mode 100644
index 0000000..2607141
--- /dev/null
+++ b/src/bitmap_i.h
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2013-2015 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#ifndef _BITMAP_I_H
+#define _BITMAP_I_H
+
+#include <limits.h>
+
+#include "macros.h"
+
+#ifndef LONG_BIT
+#define LONG_BIT ((int)(CHAR_BIT * sizeof(long)))
+#endif /* LONG_BIT */
+
+#define BITMAP_LONGS(nr_bits) DIV_CEIL(nr_bits, LONG_BIT)
+
+/*
+ * Adjust the bitmap pointer and the bit index so that the latter refers
+ * to a bit inside the word pointed by the former.
+ *
+ * Implemented as a macro for const-correctness.
+ */
+#define bitmap_lookup(bmp, bitp) \
+MACRO_BEGIN \
+ int i; \
+ \
+ i = BITMAP_LONGS(*(bitp) + 1) - 1; \
+ *(bmp) += i; \
+ *(bitp) -= i * LONG_BIT; \
+MACRO_END
+
+static inline unsigned long
+bitmap_mask(int bit)
+{
+ return (1UL << bit);
+}
+
+/*
+ * Return the index of the next set bit in the bitmap, starting (and
+ * including) the given bit index, or -1 if the bitmap is empty. If
+ * complement is true, bits are toggled before searching so that the
+ * result is the index of the next zero bit.
+ */
+int bitmap_find_next_bit(const unsigned long *bm, int nr_bits, int bit,
+ int complement);
+
+#endif /* _BITMAP_I_H */
diff --git a/src/cbuf.c b/src/cbuf.c
new file mode 100644
index 0000000..1570ac8
--- /dev/null
+++ b/src/cbuf.c
@@ -0,0 +1,202 @@
+/*
+ * Copyright (c) 2015-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include <assert.h>
+#include <errno.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "cbuf.h"
+#include "macros.h"
+
+/* Negative close to 0 so that an overflow occurs early */
+#define CBUF_INIT_INDEX ((size_t)-500)
+
+void
+cbuf_init(struct cbuf *cbuf, void *buf, size_t capacity)
+{
+ assert(ISP2(capacity));
+
+ cbuf->buf = buf;
+ cbuf->capacity = capacity;
+ cbuf->start = CBUF_INIT_INDEX;
+ cbuf->end = cbuf->start;
+}
+
+static size_t
+cbuf_index(const struct cbuf *cbuf, size_t abs_index)
+{
+ return abs_index & (cbuf->capacity - 1);
+}
+
+static void
+cbuf_update_start(struct cbuf *cbuf)
+{
+ /* Mind integer overflows */
+ if (cbuf_size(cbuf) > cbuf->capacity) {
+ cbuf->start = cbuf->end - cbuf->capacity;
+ }
+}
+
+int
+cbuf_push(struct cbuf *cbuf, const void *buf, size_t size, bool erase)
+{
+ size_t free_size;
+
+ if (!erase) {
+ free_size = cbuf_capacity(cbuf) - cbuf_size(cbuf);
+
+ if (size > free_size) {
+ return EAGAIN;
+ }
+ }
+
+ return cbuf_write(cbuf, cbuf_end(cbuf), buf, size);
+}
+
+int
+cbuf_pop(struct cbuf *cbuf, void *buf, size_t *sizep)
+{
+ __unused int error;
+
+ if (cbuf_size(cbuf) == 0) {
+ return EAGAIN;
+ }
+
+ error = cbuf_read(cbuf, cbuf_start(cbuf), buf, sizep);
+ assert(!error);
+ cbuf->start += *sizep;
+ return 0;
+}
+
+int
+cbuf_pushb(struct cbuf *cbuf, uint8_t byte, bool erase)
+{
+ size_t free_size;
+
+ if (!erase) {
+ free_size = cbuf_capacity(cbuf) - cbuf_size(cbuf);
+
+ if (free_size == 0) {
+ return EAGAIN;
+ }
+ }
+
+ cbuf->buf[cbuf_index(cbuf, cbuf->end)] = byte;
+ cbuf->end++;
+ cbuf_update_start(cbuf);
+ return 0;
+}
+
+int
+cbuf_popb(struct cbuf *cbuf, void *bytep)
+{
+ uint8_t *ptr;
+
+ if (cbuf_size(cbuf) == 0) {
+ return EAGAIN;
+ }
+
+ ptr = bytep;
+ *ptr = cbuf->buf[cbuf_index(cbuf, cbuf->start)];
+ cbuf->start++;
+ return 0;
+}
+
+int
+cbuf_write(struct cbuf *cbuf, size_t index, const void *buf, size_t size)
+{
+ uint8_t *start, *end, *buf_end;
+ size_t new_end, skip;
+
+ if (!cbuf_range_valid(cbuf, index, cbuf->end)) {
+ return EINVAL;
+ }
+
+ new_end = index + size;
+
+ if (!cbuf_range_valid(cbuf, cbuf->start, new_end)) {
+ cbuf->end = new_end;
+
+ if (size > cbuf_capacity(cbuf)) {
+ skip = size - cbuf_capacity(cbuf);
+ buf += skip;
+ index += skip;
+ size = cbuf_capacity(cbuf);
+ }
+ }
+
+ start = &cbuf->buf[cbuf_index(cbuf, index)];
+ end = start + size;
+ buf_end = cbuf->buf + cbuf->capacity;
+
+ if ((end <= cbuf->buf) || (end > buf_end)) {
+ skip = buf_end - start;
+ memcpy(start, buf, skip);
+ buf += skip;
+ start = cbuf->buf;
+ size -= skip;
+ }
+
+ memcpy(start, buf, size);
+ cbuf_update_start(cbuf);
+ return 0;
+}
+
+int
+cbuf_read(const struct cbuf *cbuf, size_t index, void *buf, size_t *sizep)
+{
+ const uint8_t *start, *end, *buf_end;
+ size_t size;
+
+ /* At least one byte must be available */
+ if (!cbuf_range_valid(cbuf, index, index + 1)) {
+ return EINVAL;
+ }
+
+ size = cbuf->end - index;
+
+ if (*sizep > size) {
+ *sizep = size;
+ }
+
+ start = &cbuf->buf[cbuf_index(cbuf, index)];
+ end = start + *sizep;
+ buf_end = cbuf->buf + cbuf->capacity;
+
+ if ((end > cbuf->buf) && (end <= buf_end)) {
+ size = *sizep;
+ } else {
+ size = buf_end - start;
+ memcpy(buf, start, size);
+ buf += size;
+ start = cbuf->buf;
+ size = *sizep - size;
+ }
+
+ memcpy(buf, start, size);
+ return 0;
+}
diff --git a/src/cbuf.h b/src/cbuf.h
new file mode 100644
index 0000000..8b46cd4
--- /dev/null
+++ b/src/cbuf.h
@@ -0,0 +1,150 @@
+/*
+ * Copyright (c) 2015-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Circular byte buffer.
+ */
+
+#ifndef _CBUF_H
+#define _CBUF_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+/*
+ * Circular buffer descriptor.
+ *
+ * The buffer capacity must be a power-of-two. Indexes are absolute values
+ * which can overflow. Their difference cannot exceed the capacity.
+ */
+struct cbuf {
+ uint8_t *buf;
+ size_t capacity;
+ size_t start;
+ size_t end;
+};
+
+static inline size_t
+cbuf_capacity(const struct cbuf *cbuf)
+{
+ return cbuf->capacity;
+}
+
+static inline size_t
+cbuf_start(const struct cbuf *cbuf)
+{
+ return cbuf->start;
+}
+
+static inline size_t
+cbuf_end(const struct cbuf *cbuf)
+{
+ return cbuf->end;
+}
+
+static inline size_t
+cbuf_size(const struct cbuf *cbuf)
+{
+ return cbuf->end - cbuf->start;
+}
+
+static inline void
+cbuf_clear(struct cbuf *cbuf)
+{
+ cbuf->start = cbuf->end;
+}
+
+static inline bool
+cbuf_range_valid(const struct cbuf *cbuf, size_t start, size_t end)
+{
+ return (((end - start) <= cbuf_size(cbuf))
+ && ((start - cbuf->start) <= cbuf_size(cbuf))
+ && ((cbuf->end - end) <= cbuf_size(cbuf)));
+}
+
+/*
+ * Initialize a circular buffer.
+ *
+ * The descriptor is set to use the given buffer for storage. Capacity
+ * must be a power-of-two.
+ */
+void cbuf_init(struct cbuf *cbuf, void *buf, size_t capacity);
+
+/*
+ * Push data to a circular buffer.
+ *
+ * If the function isn't allowed to erase old data and the circular buffer
+ * doesn't have enough unused bytes for the new data, EAGAIN is returned.
+ */
+int cbuf_push(struct cbuf *cbuf, const void *buf, size_t size, bool erase);
+
+/*
+ * Pop data from a circular buffer.
+ *
+ * On entry, the sizep argument points to the size of the output buffer.
+ * On exit, it is updated to the number of bytes actually transferred.
+ *
+ * If the buffer is empty, EAGAIN is returned, and the size of the
+ * output buffer is undefined.
+ */
+int cbuf_pop(struct cbuf *cbuf, void *buf, size_t *sizep);
+
+/*
+ * Push a byte to a circular buffer.
+ *
+ * If the function isn't allowed to erase old data and the circular buffer
+ * is full, EAGAIN is returned.
+ */
+int cbuf_pushb(struct cbuf *cbuf, uint8_t byte, bool erase);
+
+/*
+ * Pop a byte from a circular buffer.
+ *
+ * If the buffer is empty, EAGAIN is returned.
+ */
+int cbuf_popb(struct cbuf *cbuf, void *bytep);
+
+/*
+ * Write into a circular buffer at a specific location.
+ *
+ * If the given index is outside buffer boundaries, EINVAL is returned.
+ * The given [index, size) range may extend beyond the end of the circular
+ * buffer.
+ */
+int cbuf_write(struct cbuf *cbuf, size_t index, const void *buf, size_t size);
+
+/*
+ * Read from a circular buffer at a specific location.
+ *
+ * On entry, the sizep argument points to the size of the output buffer.
+ * On exit, it is updated to the number of bytes actually transferred.
+ *
+ * If the given index is outside buffer boundaries, EINVAL is returned.
+ *
+ * The circular buffer isn't changed by this operation.
+ */
+int cbuf_read(const struct cbuf *cbuf, size_t index, void *buf, size_t *sizep);
+
+#endif /* _CBUF_H */
diff --git a/src/check.h b/src/check.h
new file mode 100644
index 0000000..e22a879
--- /dev/null
+++ b/src/check.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright (c) 2016 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#ifndef _CHECK_H
+#define _CHECK_H
+
+#include <stdlib.h>
+
+#include "macros.h"
+
+/*
+ * Non conditional assert-like macro.
+ */
+#define check(expr) \
+MACRO_BEGIN \
+ if (unlikely(!(expr))) { \
+ fprintf(stderr, \
+ __FILE__ ":%u: check failed: " \
+ "'" QUOTE(expr) "'\n", \
+ __LINE__); \
+ abort(); \
+ } \
+MACRO_END
+
+#endif /* _CHECK_H */
diff --git a/src/cpu.h b/src/cpu.h
new file mode 100644
index 0000000..0445a00
--- /dev/null
+++ b/src/cpu.h
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2011-2015 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#ifndef _CPU_H
+#define _CPU_H
+
+#include <sched.h>
+
+#include "macros.h"
+
+/*
+ * Maximum number of supported processors.
+ */
+#define NR_CPUS CONFIG_NR_CPUS
+
+/*
+ * Filter invalid values.
+ *
+ * The maximum number of processors must be a power-of-two in order to avoid
+ * divisions.
+ */
+#if (NR_CPUS < 1) || !ISP2(NR_CPUS)
+#error "invalid number of configured processors"
+#endif
+
+/*
+ * L1 cache line shift and size.
+ */
+#define CPU_L1_SHIFT CONFIG_CPU_L1_SHIFT
+#define CPU_L1_SIZE (1 << CPU_L1_SHIFT)
+
+/*
+ * Return the ID of the currently running CPU.
+ *
+ * This implementation uses a glibc-specific function that relies on a
+ * Linux-specific system call to obtain the CPU ID. If this function fails
+ * (e.g. when run in valgrind), 0 is returned.
+ *
+ * The returned CPU ID cannot be greater than the maximum number of supported
+ * processors.
+ */
+static inline int
+cpu_id(void)
+{
+#if NR_CPUS == 1
+ return 0;
+#else
+ int id;
+
+ id = sched_getcpu();
+
+ if (id == -1) {
+ return 0;
+ } else if (id >= NR_CPUS) {
+ id &= (NR_CPUS - 1);
+ }
+
+ return id;
+#endif
+}
+
+#endif /* _CPU_H */
diff --git a/src/fmt.c b/src/fmt.c
new file mode 100644
index 0000000..5b5db78
--- /dev/null
+++ b/src/fmt.c
@@ -0,0 +1,1462 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include <assert.h>
+#include <errno.h>
+#include <limits.h>
+#include <stdbool.h>
+#include <stdarg.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "fmt.h"
+#include "macros.h"
+
+/*
+ * Size for the temporary number buffer. The minimum base is 8 so 3 bits
+ * are consumed per digit. Add one to round up. The conversion algorithm
+ * doesn't use the null byte.
+ */
+#define FMT_MAX_NUM_SIZE (((sizeof(unsigned long long) * CHAR_BIT) / 3) + 1)
+
+/*
+ * Special size for fmt_vsnprintf(), used when the buffer size is unknown.
+ */
+#define FMT_NOLIMIT ((size_t)-1)
+
+/*
+ * Formatting flags.
+ *
+ * FMT_FORMAT_LOWER must be 0x20 as it is OR'd with fmt_digits, eg.
+ * '0': 0x30 | 0x20 => 0x30 ('0')
+ * 'A': 0x41 | 0x20 => 0x61 ('a')
+ */
+#define FMT_FORMAT_ALT_FORM 0x0001 /* "Alternate form" */
+#define FMT_FORMAT_ZERO_PAD 0x0002 /* Zero padding on the left */
+#define FMT_FORMAT_LEFT_JUSTIFY 0x0004 /* Align text on the left */
+#define FMT_FORMAT_BLANK 0x0008 /* Blank space before positive number */
+#define FMT_FORMAT_SIGN 0x0010 /* Always place a sign (either + or -) */
+#define FMT_FORMAT_LOWER 0x0020 /* To lowercase (for %x) */
+#define FMT_FORMAT_CONV_SIGNED 0x0040 /* Format specifies signed conversion */
+#define FMT_FORMAT_DISCARD 0x0080 /* Discard output (scanf) */
+#define FMT_FORMAT_CHECK_WIDTH 0x0100 /* Check field width (scanf) */
+
+enum {
+ FMT_MODIFIER_NONE,
+ FMT_MODIFIER_CHAR,
+ FMT_MODIFIER_SHORT,
+ FMT_MODIFIER_LONG,
+ FMT_MODIFIER_LONGLONG,
+ FMT_MODIFIER_PTR, /* Used only for %p */
+ FMT_MODIFIER_SIZE,
+ FMT_MODIFIER_PTRDIFF,
+};
+
+enum {
+ FMT_SPECIFIER_INVALID,
+ FMT_SPECIFIER_INT,
+ FMT_SPECIFIER_CHAR,
+ FMT_SPECIFIER_STR,
+ FMT_SPECIFIER_NRCHARS,
+ FMT_SPECIFIER_PERCENT,
+};
+
+/*
+ * Note that copies of the original va_list object are made, because va_arg()
+ * may not reliably be used by different callee functions, and despite the
+ * standard explicitely allowing pointers to va_list objects, it's apparently
+ * very difficult for implementations to provide and is best avoided.
+ */
+
+struct fmt_sprintf_state {
+ const char *format;
+ va_list ap;
+ unsigned int flags;
+ int width;
+ int precision;
+ unsigned int modifier;
+ unsigned int specifier;
+ unsigned int base;
+ char *str;
+ char *start;
+ char *end;
+};
+
+struct fmt_sscanf_state {
+ const char *str;
+ const char *start;
+ const char *format;
+ va_list ap;
+ unsigned int flags;
+ int width;
+ int precision;
+ unsigned int modifier;
+ unsigned int specifier;
+ unsigned int base;
+ int nr_convs;
+};
+
+static const char fmt_digits[] = "0123456789ABCDEF";
+
+static char
+fmt_consume(const char **strp)
+{
+ char c;
+
+ c = **strp;
+ (*strp)++;
+ return c;
+}
+
+static void
+fmt_restore(const char **strp)
+{
+ (*strp)--;
+}
+
+static void
+fmt_vsnprintf_produce(char **strp, char *end, char c)
+{
+ if (*strp < end) {
+ **strp = c;
+ }
+
+ (*strp)++;
+}
+
+static bool
+fmt_isdigit(char c)
+{
+ return (c >= '0') && (c <= '9');
+}
+
+static bool
+fmt_isxdigit(char c)
+{
+ return fmt_isdigit(c)
+ || ((c >= 'a') && (c <= 'f'))
+ || ((c >= 'A') && (c <= 'F'));
+}
+
+static void
+fmt_sprintf_state_init(struct fmt_sprintf_state *state,
+ char *str, size_t size,
+ const char *format, va_list ap)
+{
+ state->format = format;
+ va_copy(state->ap, ap);
+ state->str = str;
+ state->start = str;
+
+ if (size == 0) {
+ state->end = NULL;
+ } else if (size == FMT_NOLIMIT) {
+ state->end = (char *)-1;
+ } else {
+ state->end = state->start + size - 1;
+ }
+}
+
+static int
+fmt_sprintf_state_finalize(struct fmt_sprintf_state *state)
+{
+ va_end(state->ap);
+
+ if (state->str < state->end) {
+ *state->str = '\0';
+ } else if (state->end != NULL) {
+ *state->end = '\0';
+ }
+
+ return state->str - state->start;
+}
+
+static char
+fmt_sprintf_state_consume_format(struct fmt_sprintf_state *state)
+{
+ return fmt_consume(&state->format);
+}
+
+static void
+fmt_sprintf_state_restore_format(struct fmt_sprintf_state *state)
+{
+ fmt_restore(&state->format);
+}
+
+static void
+fmt_sprintf_state_consume_flags(struct fmt_sprintf_state *state)
+{
+ bool found;
+ char c;
+
+ found = true;
+ state->flags = 0;
+
+ do {
+ c = fmt_sprintf_state_consume_format(state);
+
+ switch (c) {
+ case '#':
+ state->flags |= FMT_FORMAT_ALT_FORM;
+ break;
+ case '0':
+ state->flags |= FMT_FORMAT_ZERO_PAD;
+ break;
+ case '-':
+ state->flags |= FMT_FORMAT_LEFT_JUSTIFY;
+ break;
+ case ' ':
+ state->flags |= FMT_FORMAT_BLANK;
+ break;
+ case '+':
+ state->flags |= FMT_FORMAT_SIGN;
+ break;
+ default:
+ found = false;
+ break;
+ }
+ } while (found);
+
+ fmt_sprintf_state_restore_format(state);
+}
+
+static void
+fmt_sprintf_state_consume_width(struct fmt_sprintf_state *state)
+{
+ char c;
+
+ c = fmt_sprintf_state_consume_format(state);
+
+ if (fmt_isdigit(c)) {
+ state->width = 0;
+
+ do {
+ state->width = state->width * 10 + (c - '0');
+ c = fmt_sprintf_state_consume_format(state);
+ } while (fmt_isdigit(c));
+
+ fmt_sprintf_state_restore_format(state);
+ } else if (c == '*') {
+ state->width = va_arg(state->ap, int);
+
+ if (state->width < 0) {
+ state->flags |= FMT_FORMAT_LEFT_JUSTIFY;
+ state->width = -state->width;
+ }
+ } else {
+ state->width = 0;
+ fmt_sprintf_state_restore_format(state);
+ }
+}
+
+static void
+fmt_sprintf_state_consume_precision(struct fmt_sprintf_state *state)
+{
+ char c;
+
+ c = fmt_sprintf_state_consume_format(state);
+
+ if (c == '.') {
+ c = fmt_sprintf_state_consume_format(state);
+
+ if (fmt_isdigit(c)) {
+ state->precision = 0;
+
+ do {
+ state->precision = state->precision * 10 + (c - '0');
+ c = fmt_sprintf_state_consume_format(state);
+ } while (fmt_isdigit(c));
+
+ fmt_sprintf_state_restore_format(state);
+ } else if (c == '*') {
+ state->precision = va_arg(state->ap, int);
+
+ if (state->precision < 0) {
+ state->precision = 0;
+ }
+ } else {
+ state->precision = 0;
+ fmt_sprintf_state_restore_format(state);
+ }
+ } else {
+ /* precision is >= 0 only if explicit */
+ state->precision = -1;
+ fmt_sprintf_state_restore_format(state);
+ }
+}
+
+static void
+fmt_sprintf_state_consume_modifier(struct fmt_sprintf_state *state)
+{
+ char c, c2;
+
+ c = fmt_sprintf_state_consume_format(state);
+
+ switch (c) {
+ case 'h':
+ case 'l':
+ c2 = fmt_sprintf_state_consume_format(state);
+
+ if (c == c2) {
+ state->modifier = (c == 'h') ? FMT_MODIFIER_CHAR
+ : FMT_MODIFIER_LONGLONG;
+ } else {
+ state->modifier = (c == 'h') ? FMT_MODIFIER_SHORT
+ : FMT_MODIFIER_LONG;
+ fmt_sprintf_state_restore_format(state);
+ }
+
+ break;
+ case 'z':
+ state->modifier = FMT_MODIFIER_SIZE;
+ case 't':
+ state->modifier = FMT_MODIFIER_PTRDIFF;
+ break;
+ default:
+ state->modifier = FMT_MODIFIER_NONE;
+ fmt_sprintf_state_restore_format(state);
+ break;
+ }
+}
+
+static void
+fmt_sprintf_state_consume_specifier(struct fmt_sprintf_state *state)
+{
+ char c;
+
+ c = fmt_sprintf_state_consume_format(state);
+
+ switch (c) {
+ case 'd':
+ case 'i':
+ state->flags |= FMT_FORMAT_CONV_SIGNED;
+ case 'u':
+ state->base = 10;
+ state->specifier = FMT_SPECIFIER_INT;
+ break;
+ case 'o':
+ state->base = 8;
+ state->specifier = FMT_SPECIFIER_INT;
+ break;
+ case 'p':
+ state->flags |= FMT_FORMAT_ALT_FORM;
+ state->modifier = FMT_MODIFIER_PTR;
+ case 'x':
+ state->flags |= FMT_FORMAT_LOWER;
+ case 'X':
+ state->base = 16;
+ state->specifier = FMT_SPECIFIER_INT;
+ break;
+ case 'c':
+ state->specifier = FMT_SPECIFIER_CHAR;
+ break;
+ case 's':
+ state->specifier = FMT_SPECIFIER_STR;
+ break;
+ case 'n':
+ state->specifier = FMT_SPECIFIER_NRCHARS;
+ break;
+ case '%':
+ state->specifier = FMT_SPECIFIER_PERCENT;
+ break;
+ default:
+ state->specifier = FMT_SPECIFIER_INVALID;
+ fmt_sprintf_state_restore_format(state);
+ break;
+ }
+}
+
+static void
+fmt_sprintf_state_produce_raw_char(struct fmt_sprintf_state *state, char c)
+{
+ fmt_vsnprintf_produce(&state->str, state->end, c);
+}
+
+static int
+fmt_sprintf_state_consume(struct fmt_sprintf_state *state)
+{
+ char c;
+
+ c = fmt_consume(&state->format);
+
+ if (c == '\0') {
+ return ENOENT;
+ }
+
+ if (c != '%') {
+ fmt_sprintf_state_produce_raw_char(state, c);
+ return EAGAIN;
+ }
+
+ fmt_sprintf_state_consume_flags(state);
+ fmt_sprintf_state_consume_width(state);
+ fmt_sprintf_state_consume_precision(state);
+ fmt_sprintf_state_consume_modifier(state);
+ fmt_sprintf_state_consume_specifier(state);
+ return 0;
+}
+
+static void
+fmt_sprintf_state_produce_int(struct fmt_sprintf_state *state)
+{
+ char c, sign, tmp[FMT_MAX_NUM_SIZE];
+ unsigned int r, mask, shift;
+ unsigned long long n;
+ int i;
+
+ switch (state->modifier) {
+ case FMT_MODIFIER_CHAR:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ n = (signed char)va_arg(state->ap, int);
+ } else {
+ n = (unsigned char)va_arg(state->ap, int);
+ }
+
+ break;
+ case FMT_MODIFIER_SHORT:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ n = (short)va_arg(state->ap, int);
+ } else {
+ n = (unsigned short)va_arg(state->ap, int);
+ }
+
+ break;
+ case FMT_MODIFIER_LONG:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ n = va_arg(state->ap, long);
+ } else {
+ n = va_arg(state->ap, unsigned long);
+ }
+
+ break;
+ case FMT_MODIFIER_LONGLONG:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ n = va_arg(state->ap, long long);
+ } else {
+ n = va_arg(state->ap, unsigned long long);
+ }
+
+ break;
+ case FMT_MODIFIER_PTR:
+ n = (uintptr_t)va_arg(state->ap, void *);
+ break;
+ case FMT_MODIFIER_SIZE:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ n = va_arg(state->ap, ssize_t);
+ } else {
+ n = va_arg(state->ap, size_t);
+ }
+
+ break;
+ case FMT_MODIFIER_PTRDIFF:
+ n = va_arg(state->ap, ptrdiff_t);
+ break;
+ default:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ n = va_arg(state->ap, int);
+ } else {
+ n = va_arg(state->ap, unsigned int);
+ }
+
+ break;
+ }
+
+ if ((state->flags & FMT_FORMAT_LEFT_JUSTIFY) || (state->precision >= 0)) {
+ state->flags &= ~FMT_FORMAT_ZERO_PAD;
+ }
+
+ sign = '\0';
+
+ if (state->flags & FMT_FORMAT_ALT_FORM) {
+ /* '0' for octal */
+ state->width--;
+
+ /* '0x' or '0X' for hexadecimal */
+ if (state->base == 16) {
+ state->width--;
+ }
+ } else if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ if ((long long)n < 0) {
+ sign = '-';
+ state->width--;
+ n = -(long long)n;
+ } else if (state->flags & FMT_FORMAT_SIGN) {
+ /* FMT_FORMAT_SIGN must precede FMT_FORMAT_BLANK. */
+ sign = '+';
+ state->width--;
+ } else if (state->flags & FMT_FORMAT_BLANK) {
+ sign = ' ';
+ state->width--;
+ }
+ }
+
+ /* Conversion, in reverse order */
+
+ i = 0;
+
+ if (n == 0) {
+ if (state->precision != 0) {
+ tmp[i] = '0';
+ i++;
+ }
+ } else if (state->base == 10) {
+ /*
+ * Try to avoid 64 bits operations if the processor doesn't
+ * support them. Note that even when using modulus and
+ * division operators close to each other, the compiler may
+ * forge two functions calls to compute the quotient and the
+ * remainder, whereas processor instructions are generally
+ * correctly used once, giving both results at once, through
+ * plain or reciprocal division.
+ */
+#ifndef __LP64__
+ if (state->modifier == FMT_MODIFIER_LONGLONG) {
+#endif /* __LP64__ */
+ do {
+ r = n % 10;
+ n /= 10;
+ tmp[i] = fmt_digits[r];
+ i++;
+ } while (n != 0);
+#ifndef __LP64__
+ } else {
+ unsigned long m;
+
+ m = (unsigned long)n;
+
+ do {
+ r = m % 10;
+ m /= 10;
+ tmp[i] = fmt_digits[r];
+ i++;
+ } while (m != 0);
+ }
+#endif /* __LP64__ */
+ } else {
+ mask = state->base - 1;
+ shift = (state->base == 8) ? 3 : 4;
+
+ do {
+ r = n & mask;
+ n >>= shift;
+ tmp[i] = fmt_digits[r] | (state->flags & FMT_FORMAT_LOWER);
+ i++;
+ } while (n != 0);
+ }
+
+ if (i > state->precision) {
+ state->precision = i;
+ }
+
+ state->width -= state->precision;
+
+ if (!(state->flags & (FMT_FORMAT_LEFT_JUSTIFY | FMT_FORMAT_ZERO_PAD))) {
+ while (state->width > 0) {
+ state->width--;
+ fmt_sprintf_state_produce_raw_char(state, ' ');
+ }
+
+ state->width--;
+ }
+
+ if (state->flags & FMT_FORMAT_ALT_FORM) {
+ fmt_sprintf_state_produce_raw_char(state, '0');
+
+ if (state->base == 16) {
+ c = 'X' | (state->flags & FMT_FORMAT_LOWER);
+ fmt_sprintf_state_produce_raw_char(state, c);
+ }
+ } else if (sign != '\0') {
+ fmt_sprintf_state_produce_raw_char(state, sign);
+ }
+
+ if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) {
+ c = (state->flags & FMT_FORMAT_ZERO_PAD) ? '0' : ' ';
+
+ while (state->width > 0) {
+ state->width--;
+ fmt_sprintf_state_produce_raw_char(state, c);
+ }
+
+ state->width--;
+ }
+
+ while (i < state->precision) {
+ state->precision--;
+ fmt_sprintf_state_produce_raw_char(state, '0');
+ }
+
+ state->precision--;
+
+ while (i > 0) {
+ i--;
+ fmt_sprintf_state_produce_raw_char(state, tmp[i]);
+ }
+
+ while (state->width > 0) {
+ state->width--;
+ fmt_sprintf_state_produce_raw_char(state, ' ');
+ }
+
+ state->width--;
+}
+
+static void
+fmt_sprintf_state_produce_char(struct fmt_sprintf_state *state)
+{
+ char c;
+
+ c = va_arg(state->ap, int);
+
+ if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) {
+ for (;;) {
+ state->width--;
+
+ if (state->width <= 0) {
+ break;
+ }
+
+ fmt_sprintf_state_produce_raw_char(state, ' ');
+ }
+ }
+
+ fmt_sprintf_state_produce_raw_char(state, c);
+
+ for (;;) {
+ state->width--;
+
+ if (state->width <= 0) {
+ break;
+ }
+
+ fmt_sprintf_state_produce_raw_char(state, ' ');
+ }
+}
+
+static void
+fmt_sprintf_state_produce_str(struct fmt_sprintf_state *state)
+{
+ int i, len;
+ char *s;
+
+ s = va_arg(state->ap, char *);
+
+ if (s == NULL) {
+ s = "(null)";
+ }
+
+ len = 0;
+
+ for (len = 0; s[len] != '\0'; len++) {
+ if (len == state->precision) {
+ break;
+ }
+ }
+
+ if (!(state->flags & FMT_FORMAT_LEFT_JUSTIFY)) {
+ while (len < state->width) {
+ state->width--;
+ fmt_sprintf_state_produce_raw_char(state, ' ');
+ }
+ }
+
+ for (i = 0; i < len; i++) {
+ fmt_sprintf_state_produce_raw_char(state, *s);
+ s++;
+ }
+
+ while (len < state->width) {
+ state->width--;
+ fmt_sprintf_state_produce_raw_char(state, ' ');
+ }
+}
+
+static void
+fmt_sprintf_state_produce_nrchars(struct fmt_sprintf_state *state)
+{
+ if (state->modifier == FMT_MODIFIER_CHAR) {
+ signed char *ptr = va_arg(state->ap, signed char *);
+ *ptr = state->str - state->start;
+ } else if (state->modifier == FMT_MODIFIER_SHORT) {
+ short *ptr = va_arg(state->ap, short *);
+ *ptr = state->str - state->start;
+ } else if (state->modifier == FMT_MODIFIER_LONG) {
+ long *ptr = va_arg(state->ap, long *);
+ *ptr = state->str - state->start;
+ } else if (state->modifier == FMT_MODIFIER_LONGLONG) {
+ long long *ptr = va_arg(state->ap, long long *);
+ *ptr = state->str - state->start;
+ } else if (state->modifier == FMT_MODIFIER_SIZE) {
+ ssize_t *ptr = va_arg(state->ap, ssize_t *);
+ *ptr = state->str - state->start;
+ } else if (state->modifier == FMT_MODIFIER_PTRDIFF) {
+ ptrdiff_t *ptr = va_arg(state->ap, ptrdiff_t *);
+ *ptr = state->str - state->start;
+ } else {
+ int *ptr = va_arg(state->ap, int *);
+ *ptr = state->str - state->start;
+ }
+}
+
+static void
+fmt_sprintf_state_produce(struct fmt_sprintf_state *state)
+{
+ switch (state->specifier) {
+ case FMT_SPECIFIER_INT:
+ fmt_sprintf_state_produce_int(state);
+ break;
+ case FMT_SPECIFIER_CHAR:
+ fmt_sprintf_state_produce_char(state);
+ break;
+ case FMT_SPECIFIER_STR:
+ fmt_sprintf_state_produce_str(state);
+ break;
+ case FMT_SPECIFIER_NRCHARS:
+ fmt_sprintf_state_produce_nrchars(state);
+ break;
+ case FMT_SPECIFIER_PERCENT:
+ case FMT_SPECIFIER_INVALID:
+ fmt_sprintf_state_produce_raw_char(state, '%');
+ break;
+ }
+}
+
+int
+fmt_sprintf(char *str, const char *format, ...)
+{
+ va_list ap;
+ int length;
+
+ va_start(ap, format);
+ length = fmt_vsprintf(str, format, ap);
+ va_end(ap);
+
+ return length;
+}
+
+int
+fmt_vsprintf(char *str, const char *format, va_list ap)
+{
+ return fmt_vsnprintf(str, FMT_NOLIMIT, format, ap);
+}
+
+int
+fmt_snprintf(char *str, size_t size, const char *format, ...)
+{
+ va_list ap;
+ int length;
+
+ va_start(ap, format);
+ length = fmt_vsnprintf(str, size, format, ap);
+ va_end(ap);
+
+ return length;
+}
+
+int
+fmt_vsnprintf(char *str, size_t size, const char *format, va_list ap)
+{
+ struct fmt_sprintf_state state;
+ int error;
+
+ fmt_sprintf_state_init(&state, str, size, format, ap);
+
+ for (;;) {
+ error = fmt_sprintf_state_consume(&state);
+
+ if (error == EAGAIN) {
+ continue;
+ } else if (error) {
+ break;
+ }
+
+ fmt_sprintf_state_produce(&state);
+ }
+
+ return fmt_sprintf_state_finalize(&state);
+}
+
+static char
+fmt_atoi(char c)
+{
+ assert(fmt_isxdigit(c));
+
+ if (fmt_isdigit(c)) {
+ return c - '0';
+ } else if (c >= 'a' && c <= 'f') {
+ return 10 + (c - 'a');
+ } else {
+ return 10 + (c - 'A');
+ }
+}
+
+static bool
+fmt_isspace(char c)
+{
+ if (c == ' ') {
+ return true;
+ }
+
+ if ((c >= '\t') && (c <= '\f')) {
+ return true;
+ }
+
+ return false;
+}
+
+static void
+fmt_skip(const char **strp)
+{
+ while (fmt_isspace(**strp)) {
+ (*strp)++;
+ }
+}
+
+static void
+fmt_sscanf_state_init(struct fmt_sscanf_state *state, const char *str,
+ const char *format, va_list ap)
+{
+ state->str = str;
+ state->start = str;
+ state->format = format;
+ state->flags = 0;
+ state->width = 0;
+ va_copy(state->ap, ap);
+ state->nr_convs = 0;
+}
+
+static int
+fmt_sscanf_state_finalize(struct fmt_sscanf_state *state)
+{
+ va_end(state->ap);
+ return state->nr_convs;
+}
+
+static void
+fmt_sscanf_state_report_conv(struct fmt_sscanf_state *state)
+{
+ if (state->nr_convs == EOF) {
+ state->nr_convs = 1;
+ return;
+ }
+
+ state->nr_convs++;
+}
+
+static void
+fmt_sscanf_state_report_error(struct fmt_sscanf_state *state)
+{
+ if (state->nr_convs != 0) {
+ return;
+ }
+
+ state->nr_convs = EOF;
+}
+
+static void
+fmt_sscanf_state_skip_space(struct fmt_sscanf_state *state)
+{
+ fmt_skip(&state->str);
+}
+
+static char
+fmt_sscanf_state_consume_string(struct fmt_sscanf_state *state)
+{
+ char c;
+
+ c = fmt_consume(&state->str);
+
+ if (state->flags & FMT_FORMAT_CHECK_WIDTH) {
+ if (state->width == 0) {
+ c = EOF;
+ } else {
+ state->width--;
+ }
+ }
+
+ return c;
+}
+
+static void
+fmt_sscanf_state_restore_string(struct fmt_sscanf_state *state)
+{
+ fmt_restore(&state->str);
+}
+
+static char
+fmt_sscanf_state_consume_format(struct fmt_sscanf_state *state)
+{
+ return fmt_consume(&state->format);
+}
+
+static void
+fmt_sscanf_state_restore_format(struct fmt_sscanf_state *state)
+{
+ fmt_restore(&state->format);
+}
+
+static void
+fmt_sscanf_state_consume_flags(struct fmt_sscanf_state *state)
+{
+ bool found;
+ char c;
+
+ found = true;
+ state->flags = 0;
+
+ do {
+ c = fmt_sscanf_state_consume_format(state);
+
+ switch (c) {
+ case '*':
+ state->flags |= FMT_FORMAT_DISCARD;
+ break;
+ default:
+ found = false;
+ break;
+ }
+ } while (found);
+
+ fmt_sscanf_state_restore_format(state);
+}
+
+static void
+fmt_sscanf_state_consume_width(struct fmt_sscanf_state *state)
+{
+ char c;
+
+ state->width = 0;
+
+ for (;;) {
+ c = fmt_sscanf_state_consume_format(state);
+
+ if (!fmt_isdigit(c)) {
+ break;
+ }
+
+ state->width = state->width * 10 + (c - '0');
+ }
+
+ if (state->width != 0) {
+ state->flags |= FMT_FORMAT_CHECK_WIDTH;
+ }
+
+ fmt_sscanf_state_restore_format(state);
+}
+
+static void
+fmt_sscanf_state_consume_modifier(struct fmt_sscanf_state *state)
+{
+ char c, c2;
+
+ c = fmt_sscanf_state_consume_format(state);
+
+ switch (c) {
+ case 'h':
+ case 'l':
+ c2 = fmt_sscanf_state_consume_format(state);
+
+ if (c == c2) {
+ state->modifier = (c == 'h') ? FMT_MODIFIER_CHAR
+ : FMT_MODIFIER_LONGLONG;
+ } else {
+ state->modifier = (c == 'h') ? FMT_MODIFIER_SHORT
+ : FMT_MODIFIER_LONG;
+ fmt_sscanf_state_restore_format(state);
+ }
+
+ break;
+ case 'z':
+ state->modifier = FMT_MODIFIER_SIZE;
+ break;
+ case 't':
+ state->modifier = FMT_MODIFIER_PTRDIFF;
+ break;
+ default:
+ state->modifier = FMT_MODIFIER_NONE;
+ fmt_sscanf_state_restore_format(state);
+ break;
+ }
+}
+
+static void
+fmt_sscanf_state_consume_specifier(struct fmt_sscanf_state *state)
+{
+ char c;
+
+ c = fmt_sscanf_state_consume_format(state);
+
+ switch (c) {
+ case 'i':
+ state->base = 0;
+ state->flags |= FMT_FORMAT_CONV_SIGNED;
+ state->specifier = FMT_SPECIFIER_INT;
+ break;
+ case 'd':
+ state->flags |= FMT_FORMAT_CONV_SIGNED;
+ case 'u':
+ state->base = 10;
+ state->specifier = FMT_SPECIFIER_INT;
+ break;
+ case 'o':
+ state->base = 8;
+ state->specifier = FMT_SPECIFIER_INT;
+ break;
+ case 'p':
+ state->modifier = FMT_MODIFIER_PTR;
+ case 'x':
+ case 'X':
+ state->base = 16;
+ state->specifier = FMT_SPECIFIER_INT;
+ break;
+ case 'c':
+ state->specifier = FMT_SPECIFIER_CHAR;
+ break;
+ case 's':
+ state->specifier = FMT_SPECIFIER_STR;
+ break;
+ case 'n':
+ state->specifier = FMT_SPECIFIER_NRCHARS;
+ break;
+ case '%':
+ state->specifier = FMT_SPECIFIER_PERCENT;
+ break;
+ default:
+ state->specifier = FMT_SPECIFIER_INVALID;
+ fmt_sscanf_state_restore_format(state);
+ break;
+ }
+}
+
+static int
+fmt_sscanf_state_discard_char(struct fmt_sscanf_state *state, char c)
+{
+ char c2;
+
+ if (fmt_isspace(c)) {
+ fmt_sscanf_state_skip_space(state);
+ return 0;
+ }
+
+ c2 = fmt_sscanf_state_consume_string(state);
+
+ if (c != c2) {
+ if ((c2 == '\0') && (state->nr_convs == 0)) {
+ state->nr_convs = EOF;
+ }
+
+ return EINVAL;
+ }
+
+ return 0;
+}
+
+static int
+fmt_sscanf_state_consume(struct fmt_sscanf_state *state)
+{
+ int error;
+ char c;
+
+ state->flags = 0;
+
+ c = fmt_consume(&state->format);
+
+ if (c == '\0') {
+ return ENOENT;
+ }
+
+ if (c != '%') {
+ error = fmt_sscanf_state_discard_char(state, c);
+
+ if (error) {
+ return error;
+ }
+
+ return EAGAIN;
+ }
+
+ fmt_sscanf_state_consume_flags(state);
+ fmt_sscanf_state_consume_width(state);
+ fmt_sscanf_state_consume_modifier(state);
+ fmt_sscanf_state_consume_specifier(state);
+ return 0;
+}
+
+static int
+fmt_sscanf_state_produce_int(struct fmt_sscanf_state *state)
+{
+ unsigned long long n, m, tmp;
+ char c, buf[FMT_MAX_NUM_SIZE];
+ bool negative;
+ size_t i;
+
+ negative = 0;
+
+ fmt_sscanf_state_skip_space(state);
+ c = fmt_sscanf_state_consume_string(state);
+
+ if (c == '-') {
+ negative = true;
+ c = fmt_sscanf_state_consume_string(state);
+ }
+
+ if (c == '0') {
+ c = fmt_sscanf_state_consume_string(state);
+
+ if ((c == 'x') || (c == 'X')) {
+ if (state->base == 0) {
+ state->base = 16;
+ }
+
+ if (state->base == 16) {
+ c = fmt_sscanf_state_consume_string(state);
+ } else {
+ fmt_sscanf_state_restore_string(state);
+ c = '0';
+ }
+ } else {
+ if (state->base == 0) {
+ state->base = 8;
+ }
+
+ if (state->base != 8) {
+ fmt_sscanf_state_restore_string(state);
+ c = '0';
+ }
+ }
+ }
+
+ i = 0;
+
+ while (c != '\0') {
+ if (state->base == 8) {
+ if (!((c >= '0') && (c <= '7'))) {
+ break;
+ }
+ } else if (state->base == 16) {
+ if (!fmt_isxdigit(c)) {
+ break;
+ }
+ } else {
+ if (!fmt_isdigit(c)) {
+ break;
+ }
+ }
+
+ /* XXX Standard sscanf provides no way to cleanly handle overflows */
+ if (i < (ARRAY_SIZE(buf) - 1)) {
+ buf[i] = c;
+ } else if (i == (ARRAY_SIZE(buf) - 1)) {
+ strcpy(buf, "1");
+ negative = true;
+ }
+
+ i++;
+ c = fmt_sscanf_state_consume_string(state);
+ }
+
+ fmt_sscanf_state_restore_string(state);
+
+ if (state->flags & FMT_FORMAT_DISCARD) {
+ return 0;
+ }
+
+ if (i == 0) {
+ if (c == '\0') {
+ fmt_sscanf_state_report_error(state);
+ return EINVAL;
+ }
+
+ buf[0] = '0';
+ i = 1;
+ }
+
+ if (i < ARRAY_SIZE(buf)) {
+ buf[i] = '\0';
+ i--;
+ } else {
+ i = strlen(buf) - 1;
+ }
+
+ n = 0;
+
+#ifndef __LP64__
+ if (state->modifier == FMT_MODIFIER_LONGLONG) {
+#endif /* __LP64__ */
+ m = 1;
+ tmp = 0;
+
+ while (&buf[i] >= buf) {
+ tmp += fmt_atoi(buf[i]) * m;
+
+ if (tmp < n) {
+ n = 1;
+ negative = true;
+ break;
+ }
+
+ n = tmp;
+ m *= state->base;
+ i--;
+ }
+#ifndef __LP64__
+ } else {
+ unsigned long _n, _m, _tmp;
+
+ _n = 0;
+ _m = 1;
+ _tmp = 0;
+
+ while (&buf[i] >= buf) {
+ _tmp += fmt_atoi(buf[i]) * _m;
+
+ if (_tmp < _n) {
+ _n = 1;
+ negative = true;
+ break;
+ }
+
+ _n = _tmp;
+ _m *= state->base;
+ i--;
+ }
+
+ n = _n;
+ }
+#endif /* __LP64__ */
+
+ if (negative) {
+ n = -n;
+ }
+
+ switch (state->modifier) {
+ case FMT_MODIFIER_CHAR:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ *va_arg(state->ap, char *) = n;
+ } else {
+ *va_arg(state->ap, unsigned char *) = n;
+ }
+
+ break;
+ case FMT_MODIFIER_SHORT:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ *va_arg(state->ap, short *) = n;
+ } else {
+ *va_arg(state->ap, unsigned short *) = n;
+ }
+
+ break;
+ case FMT_MODIFIER_LONG:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ *va_arg(state->ap, long *) = n;
+ } else {
+ *va_arg(state->ap, unsigned long *) = n;
+ }
+
+ break;
+ case FMT_MODIFIER_LONGLONG:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ *va_arg(state->ap, long long *) = n;
+ } else {
+ *va_arg(state->ap, unsigned long long *) = n;
+ }
+
+ break;
+ case FMT_MODIFIER_PTR:
+ *va_arg(state->ap, uintptr_t *) = n;
+ break;
+ case FMT_MODIFIER_SIZE:
+ *va_arg(state->ap, size_t *) = n;
+ break;
+ case FMT_MODIFIER_PTRDIFF:
+ *va_arg(state->ap, ptrdiff_t *) = n;
+ break;
+ default:
+ if (state->flags & FMT_FORMAT_CONV_SIGNED) {
+ *va_arg(state->ap, int *) = n;
+ } else {
+ *va_arg(state->ap, unsigned int *) = n;
+ }
+ }
+
+ fmt_sscanf_state_report_conv(state);
+ return 0;
+}
+
+static int
+fmt_sscanf_state_produce_char(struct fmt_sscanf_state *state)
+{
+ char c, *dest;
+ int i, width;
+
+ if (state->flags & FMT_FORMAT_DISCARD) {
+ dest = NULL;
+ } else {
+ dest = va_arg(state->ap, char *);
+ }
+
+ if (state->flags & FMT_FORMAT_CHECK_WIDTH) {
+ width = state->width;
+ } else {
+ width = 1;
+ }
+
+ for (i = 0; i < width; i++) {
+ c = fmt_sscanf_state_consume_string(state);
+
+ if ((c == '\0') || (c == EOF)) {
+ break;
+ }
+
+ if (dest != NULL) {
+ *dest = c;
+ dest++;
+ }
+ }
+
+ if (i < width) {
+ fmt_sscanf_state_restore_string(state);
+ }
+
+ if ((dest != NULL) && (i != 0)) {
+ fmt_sscanf_state_report_conv(state);
+ }
+
+ return 0;
+}
+
+static int
+fmt_sscanf_state_produce_str(struct fmt_sscanf_state *state)
+{
+ const char *orig;
+ char c, *dest;
+
+ orig = state->str;
+
+ fmt_sscanf_state_skip_space(state);
+
+ if (state->flags & FMT_FORMAT_DISCARD) {
+ dest = NULL;
+ } else {
+ dest = va_arg(state->ap, char *);
+ }
+
+ for (;;) {
+ c = fmt_sscanf_state_consume_string(state);
+
+ if ((c == '\0') || (c == ' ') || (c == EOF)) {
+ break;
+ }
+
+ if (dest != NULL) {
+ *dest = c;
+ dest++;
+ }
+ }
+
+ fmt_sscanf_state_restore_string(state);
+
+ if (state->str == orig) {
+ fmt_sscanf_state_report_error(state);
+ return EINVAL;
+ }
+
+ if (dest != NULL) {
+ *dest = '\0';
+ fmt_sscanf_state_report_conv(state);
+ }
+
+ return 0;
+}
+
+static int
+fmt_sscanf_state_produce_nrchars(struct fmt_sscanf_state *state)
+{
+ *va_arg(state->ap, int *) = state->str - state->start;
+ return 0;
+}
+
+static int
+fmt_sscanf_state_produce(struct fmt_sscanf_state *state)
+{
+ switch (state->specifier) {
+ case FMT_SPECIFIER_INT:
+ return fmt_sscanf_state_produce_int(state);
+ case FMT_SPECIFIER_CHAR:
+ return fmt_sscanf_state_produce_char(state);
+ case FMT_SPECIFIER_STR:
+ return fmt_sscanf_state_produce_str(state);
+ case FMT_SPECIFIER_NRCHARS:
+ return fmt_sscanf_state_produce_nrchars(state);
+ case FMT_SPECIFIER_PERCENT:
+ fmt_sscanf_state_skip_space(state);
+ return fmt_sscanf_state_discard_char(state, '%');
+ default:
+ fmt_sscanf_state_report_error(state);
+ return EINVAL;
+ }
+}
+
+int
+fmt_sscanf(const char *str, const char *format, ...)
+{
+ va_list ap;
+ int ret;
+
+ va_start(ap, format);
+ ret = fmt_vsscanf(str, format, ap);
+ va_end(ap);
+
+ return ret;
+}
+
+int
+fmt_vsscanf(const char *str, const char *format, va_list ap)
+{
+ struct fmt_sscanf_state state;
+ int error;
+
+ fmt_sscanf_state_init(&state, str, format, ap);
+
+ for (;;) {
+ error = fmt_sscanf_state_consume(&state);
+
+ if (error == EAGAIN) {
+ continue;
+ } else if (error) {
+ break;
+ }
+
+ error = fmt_sscanf_state_produce(&state);
+
+ if (error) {
+ break;
+ }
+ }
+
+ return fmt_sscanf_state_finalize(&state);
+}
diff --git a/src/fmt.h b/src/fmt.h
new file mode 100644
index 0000000..babaa52
--- /dev/null
+++ b/src/fmt.h
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Formatted string functions.
+ *
+ * The functions provided by this module implement a subset of the standard
+ * sprintf- and sscanf-like functions.
+ *
+ * sprintf:
+ * - flags: # 0 - ' ' (space) +
+ * - field width is supported
+ * - precision is supported
+ *
+ * sscanf:
+ * - flags: *
+ * - field width is supported
+ *
+ * common:
+ * - modifiers: hh h l ll z t
+ * - specifiers: d i o u x X c s p n %
+ */
+
+#ifndef _FMT_H
+#define _FMT_H
+
+#include <stdarg.h>
+#include <stddef.h>
+
+int fmt_sprintf(char *str, const char *format, ...)
+ __attribute__((format(printf, 2, 3)));
+
+int fmt_vsprintf(char *str, const char *format, va_list ap)
+ __attribute__((format(printf, 2, 0)));
+
+int fmt_snprintf(char *str, size_t size, const char *format, ...)
+ __attribute__((format(printf, 3, 4)));
+
+int fmt_vsnprintf(char *str, size_t size, const char *format, va_list ap)
+ __attribute__((format(printf, 3, 0)));
+
+int fmt_sscanf(const char *str, const char *format, ...)
+ __attribute__((format(scanf, 2, 3)));
+
+int fmt_vsscanf(const char *str, const char *format, va_list ap)
+ __attribute__((format(scanf, 2, 0)));
+
+#endif /* _FMT_H */
diff --git a/src/hash.h b/src/hash.h
new file mode 100644
index 0000000..9909ee4
--- /dev/null
+++ b/src/hash.h
@@ -0,0 +1,124 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Hash functions for integers and strings.
+ *
+ * Integer hashing follows Thomas Wang's paper about his 32/64-bits mix
+ * functions :
+ * - https://gist.github.com/badboy/6267743
+ *
+ * String hashing uses a variant of the djb2 algorithm with k=31, as in
+ * the implementation of the hashCode() method of the Java String class :
+ * - http://www.javamex.com/tutorials/collections/hash_function_technical.shtml
+ *
+ * Note that this algorithm isn't suitable to obtain usable 64-bits hashes
+ * and is expected to only serve as an array index producer.
+ *
+ * These functions all have a bits parameter that indicates the number of
+ * relevant bits the caller is interested in. When returning a hash, its
+ * value must be truncated so that it can fit in the requested bit size.
+ * It can be used by the implementation to select high or low bits, depending
+ * on their relative randomness. To get complete, unmasked hashes, use the
+ * HASH_ALLBITS macro.
+ */
+
+#ifndef _HASH_H
+#define _HASH_H
+
+#include <assert.h>
+#include <stdint.h>
+
+#ifdef __LP64__
+#define HASH_ALLBITS 64
+#define hash_long(n, bits) hash_int64(n, bits)
+#else /* __LP64__ */
+static_assert(sizeof(long) == 4, "unsupported data model");
+#define HASH_ALLBITS 32
+#define hash_long(n, bits) hash_int32(n, bits)
+#endif
+
+static inline uint32_t
+hash_int32(uint32_t n, unsigned int bits)
+{
+ uint32_t hash;
+
+ hash = n;
+ hash = ~hash + (hash << 15);
+ hash ^= (hash >> 12);
+ hash += (hash << 2);
+ hash ^= (hash >> 4);
+ hash += (hash << 3) + (hash << 11);
+ hash ^= (hash >> 16);
+
+ return hash >> (32 - bits);
+}
+
+static inline uint64_t
+hash_int64(uint64_t n, unsigned int bits)
+{
+ uint64_t hash;
+
+ hash = n;
+ hash = ~hash + (hash << 21);
+ hash ^= (hash >> 24);
+ hash += (hash << 3) + (hash << 8);
+ hash ^= (hash >> 14);
+ hash += (hash << 2) + (hash << 4);
+ hash ^= (hash >> 28);
+ hash += (hash << 31);
+
+ return hash >> (64 - bits);
+}
+
+static inline uintptr_t
+hash_ptr(const void *ptr, unsigned int bits)
+{
+ if (sizeof(uintptr_t) == 8) {
+ return hash_int64((uintptr_t)ptr, bits);
+ } else {
+ return hash_int32((uintptr_t)ptr, bits);
+ }
+}
+
+static inline unsigned long
+hash_str(const char *str, unsigned int bits)
+{
+ unsigned long hash;
+ char c;
+
+ for (hash = 0; /* no condition */; str++) {
+ c = *str;
+
+ if (c == '\0') {
+ break;
+ }
+
+ hash = ((hash << 5) - hash) + c;
+ }
+
+ return hash & ((1 << bits) - 1);
+}
+
+#endif /* _HASH_H */
diff --git a/src/hlist.h b/src/hlist.h
new file mode 100644
index 0000000..dd32112
--- /dev/null
+++ b/src/hlist.h
@@ -0,0 +1,418 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Doubly-linked list specialized for forward traversals and O(1) removals.
+ */
+
+#ifndef _HLIST_H
+#define _HLIST_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "macros.h"
+
+/*
+ * List node.
+ *
+ * The pprev member points to another node member instead of another node,
+ * so that it may safely refer to the first member of the list head. Its
+ * main purpose is to allow O(1) removal.
+ */
+struct hlist_node {
+ struct hlist_node *next;
+ struct hlist_node **pprev;
+};
+
+/*
+ * List head.
+ */
+struct hlist {
+ struct hlist_node *first;
+};
+
+/*
+ * Static list initializer.
+ */
+#define HLIST_INITIALIZER(list) { NULL }
+
+/*
+ * Initialize a list.
+ */
+static inline void
+hlist_init(struct hlist *list)
+{
+ list->first = NULL;
+}
+
+/*
+ * Initialize a list node.
+ *
+ * A node is in no list when its pprev member points to NULL.
+ */
+static inline void
+hlist_node_init(struct hlist_node *node)
+{
+ node->pprev = NULL;
+}
+
+/*
+ * Return true if node is in no list.
+ */
+static inline bool
+hlist_node_unlinked(const struct hlist_node *node)
+{
+ return node->pprev == NULL;
+}
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct hlist_node *
+hlist_first(const struct hlist *list)
+{
+ return list->first;
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct hlist_node *
+hlist_next(const struct hlist_node *node)
+{
+ return node->next;
+}
+
+/*
+ * Return true if node is invalid and denotes the end of the list.
+ */
+static inline bool
+hlist_end(const struct hlist_node *node)
+{
+ return node == NULL;
+}
+
+/*
+ * Return true if list is empty.
+ */
+static inline bool
+hlist_empty(const struct hlist *list)
+{
+ return list->first == NULL;
+}
+
+/*
+ * Return true if list contains exactly one node.
+ */
+static inline bool
+hlist_singular(const struct hlist *list)
+{
+ return !hlist_empty(list) && hlist_end(list->first->next);
+}
+
+/*
+ * Set the new head of a list.
+ *
+ * After completion, old_head is stale.
+ */
+static inline void
+hlist_set_head(struct hlist *new_head, const struct hlist *old_head)
+{
+ *new_head = *old_head;
+
+ if (!hlist_empty(new_head)) {
+ new_head->first->pprev = &new_head->first;
+ }
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+hlist_insert_head(struct hlist *list, struct hlist_node *node)
+{
+ struct hlist_node *first;
+
+ first = list->first;
+ node->next = first;
+ node->pprev = &list->first;
+
+ if (first != NULL) {
+ first->pprev = &node->next;
+ }
+
+ list->first = node;
+}
+
+/*
+ * Insert a node before another node.
+ */
+static inline void
+hlist_insert_before(struct hlist_node *next, struct hlist_node *node)
+{
+ node->next = next;
+ node->pprev = next->pprev;
+ next->pprev = &node->next;
+ *node->pprev = node;
+}
+
+/*
+ * Insert a node after another node.
+ */
+static inline void
+hlist_insert_after(struct hlist_node *prev, struct hlist_node *node)
+{
+ node->next = prev->next;
+ node->pprev = &prev->next;
+
+ if (node->next != NULL) {
+ node->next->pprev = &node->next;
+ }
+
+ prev->next = node;
+}
+
+/*
+ * Remove a node from a list.
+ */
+static inline void
+hlist_remove(struct hlist_node *node)
+{
+ if (node->next != NULL) {
+ node->next->pprev = node->pprev;
+ }
+
+ *node->pprev = node->next;
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define hlist_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Get the first entry of a list.
+ */
+#define hlist_first_entry(list, type, member) \
+MACRO_BEGIN \
+ struct hlist_node *___first; \
+ \
+ ___first = (list)->first; \
+ hlist_end(___first) ? NULL : hlist_entry(___first, type, member); \
+MACRO_END
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define hlist_next_entry(entry, member) \
+MACRO_BEGIN \
+ struct hlist_node *___next; \
+ \
+ ___next = (entry)->member.next; \
+ hlist_end(___next) \
+ ? NULL \
+ : hlist_entry(___next, typeof(*entry), member); \
+MACRO_END
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define hlist_for_each(list, node) \
+for (node = hlist_first(list); \
+ !hlist_end(node); \
+ node = hlist_next(node))
+
+/*
+ * Forge a loop to process all nodes of a list.
+ */
+#define hlist_for_each_safe(list, node, tmp) \
+for (node = hlist_first(list), \
+ tmp = hlist_end(node) ? NULL : hlist_next(node); \
+ !hlist_end(node); \
+ node = tmp, \
+ tmp = hlist_end(node) ? NULL : hlist_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define hlist_for_each_entry(list, entry, member) \
+for (entry = hlist_first_entry(list, typeof(*entry), member); \
+ entry != NULL; \
+ entry = hlist_next_entry(entry, member))
+
+/*
+ * Forge a loop to process all entries of a list.
+ */
+#define hlist_for_each_entry_safe(list, entry, tmp, member) \
+for (entry = hlist_first_entry(list, typeof(*entry), member), \
+ tmp = (entry == NULL) ? NULL : hlist_next_entry(entry, member); \
+ entry != NULL; \
+ entry = tmp, \
+ tmp = (entry == NULL) ? NULL : hlist_next_entry(entry, member)) \
+
+/*
+ * Lockless variants
+ *
+ * The hlist_end() function may be used from read-side critical sections.
+ */
+
+/*
+ * These macros can be replaced by actual functions in an environment
+ * that provides lockless synchronization such as RCU.
+ */
+#define llsync_store_ptr(ptr, value) ((ptr) = (value))
+#define llsync_load_ptr(ptr) (ptr)
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct hlist_node *
+hlist_llsync_first(const struct hlist *list)
+{
+ return llsync_load_ptr(list->first);
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct hlist_node *
+hlist_llsync_next(const struct hlist_node *node)
+{
+ return llsync_load_ptr(node->next);
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+hlist_llsync_insert_head(struct hlist *list, struct hlist_node *node)
+{
+ struct hlist_node *first;
+
+ first = list->first;
+ node->next = first;
+ node->pprev = &list->first;
+
+ if (first != NULL) {
+ first->pprev = &node->next;
+ }
+
+ llsync_store_ptr(list->first, node);
+}
+
+/*
+ * Insert a node before another node.
+ */
+static inline void
+hlist_llsync_insert_before(struct hlist_node *next, struct hlist_node *node)
+{
+ node->next = next;
+ node->pprev = next->pprev;
+ next->pprev = &node->next;
+ llsync_store_ptr(*node->pprev, node);
+}
+
+/*
+ * Insert a node after another node.
+ */
+static inline void
+hlist_llsync_insert_after(struct hlist_node *prev, struct hlist_node *node)
+{
+ node->next = prev->next;
+ node->pprev = &prev->next;
+
+ if (node->next != NULL) {
+ node->next->pprev = &node->next;
+ }
+
+ llsync_store_ptr(prev->next, node);
+}
+
+/*
+ * Remove a node from a list.
+ */
+static inline void
+hlist_llsync_remove(struct hlist_node *node)
+{
+ if (node->next != NULL) {
+ node->next->pprev = node->pprev;
+ }
+
+ llsync_store_ptr(*node->pprev, node->next);
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define hlist_llsync_entry(node, type, member) \
+ structof(llsync_load_ptr(node), type, member)
+
+/*
+ * Get the first entry of a list.
+ */
+#define hlist_llsync_first_entry(list, type, member) \
+MACRO_BEGIN \
+ struct hlist_node *___first; \
+ \
+ ___first = hlist_llsync_first(list); \
+ hlist_end(___first) ? NULL : hlist_entry(___first, type, member); \
+MACRO_END
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define hlist_llsync_next_entry(entry, member) \
+MACRO_BEGIN \
+ struct hlist_node *___next; \
+ \
+ ___next = hlist_llsync_next(&entry->member); \
+ hlist_end(___next) \
+ ? NULL \
+ : hlist_entry(___next, typeof(*entry), member); \
+MACRO_END
+
+/*
+ * Forge a loop to process all nodes of a list.
+ */
+#define hlist_llsync_for_each(list, node) \
+for (node = hlist_llsync_first(list); \
+ !hlist_end(node); \
+ node = hlist_llsync_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ */
+#define hlist_llsync_for_each_entry(list, entry, member) \
+for (entry = hlist_llsync_first_entry(list, typeof(*entry), member); \
+ entry != NULL; \
+ entry = hlist_llsync_next_entry(entry, member))
+
+#endif /* _HLIST_H */
diff --git a/src/list.c b/src/list.c
new file mode 100644
index 0000000..b33226a
--- /dev/null
+++ b/src/list.c
@@ -0,0 +1,141 @@
+/*
+ * Copyright (c) 2009-2015 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * List sorting implementation.
+ *
+ * In addition to most common list operations, this implementation includes
+ * a sort operation. The algorithm used is a variant of the bottom-up
+ * mergesort algorithm. It has the following properties :
+ * - It is iterative (no recursion overhead).
+ * - It is stable (the relative order of equal entries is preserved).
+ * - It only requires constant additional space (as it works on linked lists).
+ * - It performs at O(n log n) for average and worst cases.
+ * - It is adaptive, performing faster on already sorted lists.
+ */
+
+#include "list.h"
+
+/*
+ * Split input_list into two lists.
+ *
+ * The list_size first entries of input_list are moved into left_list while
+ * the "right" list is actually the list_size first entries of input_list
+ * after completion.
+ */
+static void
+_list_divide(struct list *input_list, struct list *left_list,
+ unsigned int list_size)
+{
+ struct list *node;
+ unsigned int i;
+
+ node = input_list->next;
+
+ for (i = 0; (i < list_size) && !list_end(input_list, node); i++) {
+ node = node->next;
+ }
+
+ list_split(left_list, input_list, node);
+}
+
+/*
+ * Merge left_list and right_list at the tail of output_list.
+ */
+static void
+_list_merge(struct list *left_list, struct list *right_list,
+ struct list *output_list, unsigned int right_list_size,
+ list_sort_cmp_fn_t cmp_fn)
+{
+ struct list *left, *right;
+
+ left = left_list->prev;
+ right = right_list->next;
+
+ /*
+ * Try to concatenate lists instead of merging first. This reduces
+ * complexity for already sorted lists.
+ */
+ if (!list_end(left_list, left)
+ && ((right_list_size > 0) && !list_end(right_list, right))
+ && (cmp_fn(left, right) <= 0)) {
+ struct list tmp_list;
+
+ list_concat(output_list, left_list);
+ list_init(left_list);
+
+ while ((right_list_size > 0) && !list_end(right_list, right)) {
+ right = right->next;
+ right_list_size--;
+ }
+
+ list_split(&tmp_list, right_list, right);
+ list_concat(output_list, &tmp_list);
+ return;
+ }
+
+ left = left_list->next;
+
+ while (!list_end(left_list, left)
+ || ((right_list_size > 0) && !list_end(right_list, right)))
+ if (((right_list_size == 0) || list_end(right_list, right))
+ || (!list_end(left_list, left) && (cmp_fn(left, right) <= 0))) {
+ list_remove(left);
+ list_insert_tail(output_list, left);
+ left = left_list->next;
+ } else {
+ list_remove(right);
+ list_insert_tail(output_list, right);
+ right = right_list->next;
+ right_list_size--;
+ }
+}
+
+void
+list_sort(struct list *list, list_sort_cmp_fn_t cmp_fn)
+{
+ struct list left_list, output_list;
+ unsigned int list_size, nr_merges;
+
+ list_init(&left_list);
+ list_init(&output_list);
+
+ for (list_size = 1; /* no condition */; list_size <<= 1) {
+ for (nr_merges = 0; /* no condition */; nr_merges++) {
+ if (list_empty(list)) {
+ break;
+ }
+
+ _list_divide(list, &left_list, list_size);
+ _list_merge(&left_list, list, &output_list, list_size, cmp_fn);
+ }
+
+ list_concat(list, &output_list);
+ list_init(&output_list);
+
+ if (nr_merges <= 1) {
+ return;
+ }
+ }
+}
diff --git a/src/list.h b/src/list.h
new file mode 100644
index 0000000..85d3dc2
--- /dev/null
+++ b/src/list.h
@@ -0,0 +1,555 @@
+/*
+ * Copyright (c) 2009-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Doubly-linked list.
+ */
+
+#ifndef _LIST_H
+#define _LIST_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "macros.h"
+
+/*
+ * Structure used as both head and node.
+ *
+ * This implementation relies on using the same type for both heads and nodes.
+ *
+ * It is recommended to encode the use of struct list variables in their names,
+ * e.g. struct list free_list or struct list free_objects is a good hint for a
+ * list of free objects. A declaration like struct list free_node clearly
+ * indicates it is used as part of a node in the free list.
+ */
+struct list {
+ struct list *prev;
+ struct list *next;
+};
+
+/*
+ * Function type for list sorting.
+ *
+ * Return a value less than, equal to, or greater than 0 if node A
+ * is repsectively less than, equal to, or greater than node B.
+ *
+ * Use list_entry() to obtain the entries from the given nodes.
+ *
+ * See list_sort().
+ */
+typedef int (*list_sort_cmp_fn_t)(struct list *node_a, struct list *node_b);
+
+/*
+ * Static list initializer.
+ */
+#define LIST_INITIALIZER(list) { &(list), &(list) }
+
+/*
+ * Initialize a list.
+ */
+static inline void
+list_init(struct list *list)
+{
+ list->prev = list;
+ list->next = list;
+}
+
+/*
+ * Initialize a list node.
+ *
+ * A node is in no list when its node members point to NULL.
+ */
+static inline void
+list_node_init(struct list *node)
+{
+ node->prev = NULL;
+ node->next = NULL;
+}
+
+/*
+ * Return true if node is in no list.
+ */
+static inline bool
+list_node_unlinked(const struct list *node)
+{
+ return node->prev == NULL;
+}
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct list *
+list_first(const struct list *list)
+{
+ return list->next;
+}
+
+/*
+ * Return the last node of a list.
+ */
+static inline struct list *
+list_last(const struct list *list)
+{
+ return list->prev;
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct list *
+list_next(const struct list *node)
+{
+ return node->next;
+}
+
+/*
+ * Return the node previous to the given node.
+ */
+static inline struct list *
+list_prev(const struct list *node)
+{
+ return node->prev;
+}
+
+/*
+ * Return true if node is invalid and denotes one of the ends of the list.
+ */
+static inline bool
+list_end(const struct list *list, const struct list *node)
+{
+ return list == node;
+}
+
+/*
+ * Return true if list is empty.
+ */
+static inline bool
+list_empty(const struct list *list)
+{
+ return list == list->next;
+}
+
+/*
+ * Return true if list contains exactly one node.
+ */
+static inline bool
+list_singular(const struct list *list)
+{
+ return !list_empty(list) && (list->next == list->prev);
+}
+
+/*
+ * Split list2 by moving its nodes up to, but not including, the given
+ * node into list1, which can be in a stale state.
+ *
+ * If list2 is empty, or node is list2 or list2->next, list1 is merely
+ * initialized.
+ */
+static inline void
+list_split(struct list *list1, struct list *list2, struct list *node)
+{
+ if (list_empty(list2) || (list2->next == node) || list_end(list2, node)) {
+ list_init(list1);
+ return;
+ }
+
+ list1->next = list2->next;
+ list1->next->prev = list1;
+
+ list1->prev = node->prev;
+ node->prev->next = list1;
+
+ list2->next = node;
+ node->prev = list2;
+}
+
+/*
+ * Append the nodes of list2 at the end of list1.
+ *
+ * After completion, list2 is stale.
+ */
+static inline void
+list_concat(struct list *list1, const struct list *list2)
+{
+ struct list *last1, *first2, *last2;
+
+ if (list_empty(list2)) {
+ return;
+ }
+
+ last1 = list1->prev;
+ first2 = list2->next;
+ last2 = list2->prev;
+
+ last1->next = first2;
+ first2->prev = last1;
+
+ last2->next = list1;
+ list1->prev = last2;
+}
+
+/*
+ * Set the new head of a list.
+ *
+ * This function is an optimized version of :
+ * list_init(&new_list);
+ * list_concat(&new_list, &old_list);
+ *
+ * After completion, old_head is stale.
+ */
+static inline void
+list_set_head(struct list *new_head, const struct list *old_head)
+{
+ if (list_empty(old_head)) {
+ list_init(new_head);
+ return;
+ }
+
+ *new_head = *old_head;
+ new_head->next->prev = new_head;
+ new_head->prev->next = new_head;
+}
+
+/*
+ * Add a node between two nodes.
+ *
+ * This function is private.
+ */
+static inline void
+list_add(struct list *prev, struct list *next, struct list *node)
+{
+ next->prev = node;
+ node->next = next;
+
+ prev->next = node;
+ node->prev = prev;
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+list_insert_head(struct list *list, struct list *node)
+{
+ list_add(list, list->next, node);
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+list_insert_tail(struct list *list, struct list *node)
+{
+ list_add(list->prev, list, node);
+}
+
+/*
+ * Insert a node before another node.
+ */
+static inline void
+list_insert_before(struct list *next, struct list *node)
+{
+ list_add(next->prev, next, node);
+}
+
+/*
+ * Insert a node after another node.
+ */
+static inline void
+list_insert_after(struct list *prev, struct list *node)
+{
+ list_add(prev, prev->next, node);
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * After completion, the node is stale.
+ */
+static inline void
+list_remove(struct list *node)
+{
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define list_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Get the first entry of a list.
+ */
+#define list_first_entry(list, type, member) \
+ list_entry(list_first(list), type, member)
+
+/*
+ * Get the last entry of a list.
+ */
+#define list_last_entry(list, type, member) \
+ list_entry(list_last(list), type, member)
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define list_next_entry(entry, member) \
+ list_entry(list_next(&(entry)->member), typeof(*(entry)), member)
+
+/*
+ * Get the entry previous to the given entry.
+ */
+#define list_prev_entry(entry, member) \
+ list_entry(list_prev(&(entry)->member), typeof(*(entry)), member)
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define list_for_each(list, node) \
+for (node = list_first(list); \
+ !list_end(list, node); \
+ node = list_next(node))
+
+/*
+ * Forge a loop to process all nodes of a list.
+ */
+#define list_for_each_safe(list, node, tmp) \
+for (node = list_first(list), tmp = list_next(node); \
+ !list_end(list, node); \
+ node = tmp, tmp = list_next(node))
+
+/*
+ * Version of list_for_each() that processes nodes backward.
+ */
+#define list_for_each_reverse(list, node) \
+for (node = list_last(list); \
+ !list_end(list, node); \
+ node = list_prev(node))
+
+/*
+ * Version of list_for_each_safe() that processes nodes backward.
+ */
+#define list_for_each_reverse_safe(list, node, tmp) \
+for (node = list_last(list), tmp = list_prev(node); \
+ !list_end(list, node); \
+ node = tmp, tmp = list_prev(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define list_for_each_entry(list, entry, member) \
+for (entry = list_first_entry(list, typeof(*entry), member); \
+ !list_end(list, &entry->member); \
+ entry = list_next_entry(entry, member))
+
+/*
+ * Forge a loop to process all entries of a list.
+ */
+#define list_for_each_entry_safe(list, entry, tmp, member) \
+for (entry = list_first_entry(list, typeof(*entry), member), \
+ tmp = list_next_entry(entry, member); \
+ !list_end(list, &entry->member); \
+ entry = tmp, tmp = list_next_entry(entry, member))
+
+/*
+ * Version of list_for_each_entry() that processes entries backward.
+ */
+#define list_for_each_entry_reverse(list, entry, member) \
+for (entry = list_last_entry(list, typeof(*entry), member); \
+ !list_end(list, &entry->member); \
+ entry = list_prev_entry(entry, member))
+
+/*
+ * Version of list_for_each_entry_safe() that processes entries backward.
+ */
+#define list_for_each_entry_reverse_safe(list, entry, tmp, member) \
+for (entry = list_last_entry(list, typeof(*entry), member), \
+ tmp = list_prev_entry(entry, member); \
+ !list_end(list, &entry->member); \
+ entry = tmp, tmp = list_prev_entry(entry, member))
+
+/*
+ * Lockless variants
+ *
+ * This is a subset of the main interface that only supports forward traversal.
+ * In addition, list_end() is also allowed in read-side critical sections.
+ */
+
+/*
+ * These macros can be replaced by actual functions in an environment
+ * that provides lockless synchronization such as RCU.
+ */
+#define llsync_store_ptr(ptr, value) ((ptr) = (value))
+#define llsync_load_ptr(ptr) (ptr)
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct list *
+list_llsync_first(const struct list *list)
+{
+ return llsync_load_ptr(list->next);
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct list *
+list_llsync_next(const struct list *node)
+{
+ return llsync_load_ptr(node->next);
+}
+
+/*
+ * Add a node between two nodes.
+ *
+ * This function is private.
+ */
+static inline void
+list_llsync_add(struct list *prev, struct list *next, struct list *node)
+{
+ node->next = next;
+ node->prev = prev;
+ llsync_store_ptr(prev->next, node);
+ next->prev = node;
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+list_llsync_insert_head(struct list *list, struct list *node)
+{
+ list_llsync_add(list, list->next, node);
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+list_llsync_insert_tail(struct list *list, struct list *node)
+{
+ list_llsync_add(list->prev, list, node);
+}
+
+/*
+ * Insert a node before another node.
+ */
+static inline void
+list_llsync_insert_before(struct list *next, struct list *node)
+{
+ list_llsync_add(next->prev, next, node);
+}
+
+/*
+ * Insert a node after another node.
+ */
+static inline void
+list_llsync_insert_after(struct list *prev, struct list *node)
+{
+ list_llsync_add(prev, prev->next, node);
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * After completion, the node is stale.
+ */
+static inline void
+list_llsync_remove(struct list *node)
+{
+ node->next->prev = node->prev;
+ llsync_store_ptr(node->prev->next, node->next);
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define list_llsync_entry(node, type, member) \
+ structof(llsync_load_ptr(node), type, member)
+
+/*
+ * Get the first entry of a list.
+ *
+ * Unlike list_first_entry(), this macro may evaluate to NULL, because
+ * the node pointer can only be read once, preventing the combination
+ * of lockless list_empty()/list_first_entry() variants.
+ */
+#define list_llsync_first_entry(list, type, member) \
+MACRO_BEGIN \
+ struct list *___list; \
+ struct list *___first; \
+ \
+ ___list = (list); \
+ ___first = list_llsync_first(___list); \
+ list_end(___list, ___first) \
+ ? NULL \
+ : list_entry(___first, type, member); \
+MACRO_END
+
+/*
+ * Get the entry next to the given entry.
+ *
+ * Unlike list_next_entry(), this macro may evaluate to NULL, because
+ * the node pointer can only be read once, preventing the combination
+ * of lockless list_empty()/list_next_entry() variants.
+ */
+#define list_llsync_next_entry(entry, member) \
+ list_llsync_first_entry(&entry->member, typeof(*entry), member)
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define list_llsync_for_each(list, node) \
+for (node = list_llsync_first(list); \
+ !list_end(list, node); \
+ node = list_llsync_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define list_llsync_for_each_entry(list, entry, member) \
+for (entry = list_llsync_entry(list_first(list), \
+ typeof(*entry), member); \
+ !list_end(list, &entry->member); \
+ entry = list_llsync_entry(list_next(&entry->member), \
+ typeof(*entry), member))
+
+/*
+ * Sort a list.
+ */
+void list_sort(struct list *list, list_sort_cmp_fn_t cmp_fn);
+
+#endif /* _LIST_H */
diff --git a/src/macros.h b/src/macros.h
new file mode 100644
index 0000000..67b3c46
--- /dev/null
+++ b/src/macros.h
@@ -0,0 +1,90 @@
+/*
+ * Copyright (c) 2009-2015 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Helper macros.
+ */
+
+#ifndef _MACROS_H
+#define _MACROS_H
+
+#if !defined(__GNUC__) || (__GNUC__ < 4)
+#error "GCC 4+ required"
+#endif
+
+#include <stddef.h>
+
+#define MACRO_BEGIN ({
+#define MACRO_END })
+
+#define __QUOTE(x) #x
+#define QUOTE(x) __QUOTE(x)
+
+#define STRLEN(x) (sizeof(x) - 1)
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+
+#define MIN(a, b) ((a) < (b) ? (a) : (b))
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
+#define DIV_CEIL(n, d) (((n) + (d) - 1) / (d))
+
+#define P2ALIGNED(x, a) (((x) & ((a) - 1)) == 0)
+#define ISP2(x) P2ALIGNED(x, x)
+#define P2ALIGN(x, a) ((x) & -(a)) /* decreases if not aligned */
+#define P2ROUND(x, a) (-(-(x) & -(a))) /* increases if not aligned */
+#define P2END(x, a) (-(~(x) & -(a))) /* always increases */
+
+#define structof(ptr, type, member) \
+ ((type *)((char *)(ptr) - offsetof(type, member)))
+
+#define likely(expr) __builtin_expect(!!(expr), 1)
+#define unlikely(expr) __builtin_expect(!!(expr), 0)
+
+#define barrier() asm volatile("" : : : "memory")
+
+/*
+ * The following macros may be provided by the C environment.
+ */
+
+#ifndef __noinline
+#define __noinline __attribute__((noinline))
+#endif
+
+#ifndef __always_inline
+#define __always_inline inline __attribute__((always_inline))
+#endif
+
+#ifndef __section
+#define __section(x) __attribute__((section(x)))
+#endif
+
+#ifndef __packed
+#define __packed __attribute__((packed))
+#endif
+
+#ifndef __unused
+#define __unused __attribute__((unused))
+#endif
+
+#endif /* _MACROS_H */
diff --git a/src/plist.c b/src/plist.c
new file mode 100644
index 0000000..80c0b27
--- /dev/null
+++ b/src/plist.c
@@ -0,0 +1,73 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include "list.h"
+#include "plist.h"
+
+void
+plist_add(struct plist *plist, struct plist_node *pnode)
+{
+ struct plist_node *next;
+
+ if (plist_empty(plist)) {
+ list_insert_head(&plist->list, &pnode->node);
+ list_insert_head(&plist->prio_list, &pnode->prio_node);
+ return;
+ }
+
+ list_for_each_entry(&plist->prio_list, next, prio_node) {
+ if (pnode->priority < next->priority) {
+ break;
+ }
+ }
+
+ if (list_end(&plist->prio_list, &next->prio_node)
+ || (pnode->priority != next->priority)) {
+ list_insert_before(&next->prio_node, &pnode->prio_node);
+ } else {
+ list_init(&pnode->prio_node);
+ }
+
+ list_insert_before(&next->node, &pnode->node);
+}
+
+void
+plist_remove(struct plist *plist, struct plist_node *pnode)
+{
+ struct plist_node *next;
+
+ if (!list_node_unlinked(&pnode->prio_node)) {
+ next = list_next_entry(pnode, node);
+
+ if (!list_end(&plist->list, &next->node)
+ && list_node_unlinked(&next->prio_node)) {
+ list_insert_after(&pnode->prio_node, &next->prio_node);
+ }
+
+ list_remove(&pnode->prio_node);
+ }
+
+ list_remove(&pnode->node);
+}
diff --git a/src/plist.h b/src/plist.h
new file mode 100644
index 0000000..9328d27
--- /dev/null
+++ b/src/plist.h
@@ -0,0 +1,296 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Priority list.
+ *
+ * This container acts as a doubly-linked list sorted by priority in
+ * ascending order. All operations behave as with a regular linked list
+ * except insertion, which is O(k), k being the number of priorities
+ * among the entries.
+ */
+
+#ifndef _PLIST_H
+#define _PLIST_H
+
+#include <stdbool.h>
+
+#include "list.h"
+#include "macros.h"
+
+/*
+ * Priority list.
+ *
+ * The list member is used as the underlying regular linked list and
+ * contains all entries, sorted by priority in ascending order. The
+ * prio_list member contains exactly one entry for each priority
+ * present, also sorted by priority in ascending order. An entry
+ * on prio_list is the first entry in list for that priority.
+ * Here is a representation of a possible priority list :
+ *
+ * list--|1|--|3|--|3|--|3|--|4|--|6|--|6|--|8|
+ * | | | | | | | | |
+ * prio_list--+ +--+ +------------+ +--+ +-------+
+ *
+ */
+struct plist {
+ struct list list;
+ struct list prio_list;
+};
+
+/*
+ * Priority list node.
+ */
+struct plist_node {
+ unsigned int priority;
+ struct list node;
+ struct list prio_node;
+};
+
+/*
+ * Static priority list initializer.
+ */
+#define PLIST_INITIALIZER(plist) \
+ { LIST_INITIALIZER((plist).list), LIST_INITIALIZER((plist).prio_list) }
+
+/*
+ * Initialize a priority list.
+ */
+static inline void
+plist_init(struct plist *plist)
+{
+ list_init(&plist->list);
+ list_init(&plist->prio_list);
+}
+
+/*
+ * Initialize a priority list node.
+ */
+static inline void
+plist_node_init(struct plist_node *pnode, unsigned int priority)
+{
+ pnode->priority = priority;
+ list_node_init(&pnode->node);
+ list_node_init(&pnode->prio_node);
+}
+
+/*
+ * Return the priority associated with a node.
+ */
+static inline unsigned int
+plist_node_priority(const struct plist_node *pnode)
+{
+ return pnode->priority;
+}
+
+/*
+ * Update the priority of an already initialized node.
+ */
+static inline void
+plist_node_set_priority(struct plist_node *pnode, unsigned int priority)
+{
+ pnode->priority = priority;
+}
+
+/*
+ * Return true if pnode is in no priority lists.
+ */
+static inline bool
+plist_node_unlinked(const struct plist_node *pnode)
+{
+ return list_node_unlinked(&pnode->node);
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define plist_entry(pnode, type, member) structof(pnode, type, member)
+
+/*
+ * Return the first node of a priority list.
+ */
+static inline struct plist_node *
+plist_first(const struct plist *plist)
+{
+ return list_first_entry(&plist->list, struct plist_node, node);
+}
+
+/*
+ * Return the last node of a priority list.
+ */
+static inline struct plist_node *
+plist_last(const struct plist *plist)
+{
+ return list_last_entry(&plist->list, struct plist_node, node);
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct plist_node *
+plist_next(const struct plist_node *pnode)
+{
+ return (struct plist_node *)list_next_entry(pnode, node);
+}
+
+/*
+ * Return the node previous to the given node.
+ */
+static inline struct plist_node *
+plist_prev(const struct plist_node *pnode)
+{
+ return (struct plist_node *)list_prev_entry(pnode, node);
+}
+
+/*
+ * Get the first entry of a priority list.
+ */
+#define plist_first_entry(plist, type, member) \
+ plist_entry(plist_first(plist), type, member)
+
+/*
+ * Get the last entry of a priority list.
+ */
+#define plist_last_entry(plist, type, member) \
+ plist_entry(plist_last(plist), type, member)
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define plist_next_entry(entry, member) \
+ plist_entry(plist_next(&(entry)->member), typeof(*(entry)), member)
+
+/*
+ * Get the entry previous to the given entry.
+ */
+#define plist_prev_entry(entry, member) \
+ plist_entry(plist_prev(&(entry)->member), typeof(*(entry)), member)
+
+/*
+ * Return true if node is after the last or before the first node of
+ * a priority list.
+ */
+static inline bool
+plist_end(const struct plist *plist, const struct plist_node *pnode)
+{
+ return list_end(&plist->list, &pnode->node);
+}
+
+/*
+ * Return true if plist is empty.
+ */
+static inline bool
+plist_empty(const struct plist *plist)
+{
+ return list_empty(&plist->list);
+}
+
+/*
+ * Return true if plist contains exactly one node.
+ */
+static inline bool
+plist_singular(const struct plist *plist)
+{
+ return list_singular(&plist->list);
+}
+
+/*
+ * Add a node to a priority list.
+ *
+ * If the priority list already contains nodes with the same priority
+ * as the given node, it is inserted before them.
+ *
+ * The node must be initialized before calling this function.
+ */
+void plist_add(struct plist *plist, struct plist_node *pnode);
+
+/*
+ * Remove a node from a priority list.
+ *
+ * After completion, the node is stale.
+ */
+void plist_remove(struct plist *plist, struct plist_node *pnode);
+
+/*
+ * Forge a loop to process all nodes of a priority list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define plist_for_each(plist, pnode) \
+for (pnode = plist_first(plist); \
+ !plist_end(plist, pnode); \
+ pnode = plist_next(pnode))
+
+/*
+ * Forge a loop to process all nodes of a priority list.
+ */
+#define plist_for_each_safe(plist, pnode, tmp) \
+for (pnode = plist_first(plist), tmp = plist_next(pnode); \
+ !plist_end(plist, pnode); \
+ pnode = tmp, tmp = plist_next(pnode))
+
+/*
+ * Version of plist_for_each() that processes nodes backward.
+ */
+#define plist_for_each_reverse(plist, pnode) \
+for (pnode = plist_last(plist); \
+ !plist_end(plist, pnode); \
+ pnode = plist_prev(pnode))
+
+/*
+ * Version of plist_for_each_safe() that processes nodes backward.
+ */
+#define plist_for_each_reverse_safe(plist, pnode, tmp) \
+for (pnode = plist_last(plist), tmp = plist_prev(pnode); \
+ !plist_end(plist, pnode); \
+ pnode = tmp, tmp = plist_prev(pnode))
+
+/*
+ * Forge a loop to process all entries of a priority list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define plist_for_each_entry(plist, entry, member) \
+ list_for_each_entry(&(plist)->list, entry, member.node)
+
+/*
+ * Forge a loop to process all entries of a priority list.
+ */
+#define plist_for_each_entry_safe(plist, entry, tmp, member) \
+ list_for_each_entry_safe(&(plist)->list, entry, tmp, member.node)
+
+/*
+ * Version of plist_for_each_entry() that processes entries backward.
+ */
+#define plist_for_each_entry_reverse(plist, entry, member) \
+ list_for_each_entry_reverse(&(plist)->list, entry, member.node)
+
+/*
+ * Version of plist_for_each_entry_safe() that processes entries backward.
+ */
+#define plist_for_each_entry_reverse_safe(plist, entry, tmp, member) \
+ list_for_each_entry_reverse_safe(&(plist)->list, entry, tmp, member.node)
+
+#endif /* _PLIST_H */
diff --git a/src/rbtree.c b/src/rbtree.c
new file mode 100644
index 0000000..360c879
--- /dev/null
+++ b/src/rbtree.c
@@ -0,0 +1,558 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "macros.h"
+#include "rbtree.h"
+#include "rbtree_i.h"
+
+/*
+ * Return the index of a node in the children array of its parent.
+ *
+ * The parent parameter must not be NULL, and must be the parent of the
+ * given node.
+ */
+static inline int
+rbtree_node_index(const struct rbtree_node *node,
+ const struct rbtree_node *parent)
+{
+ assert(parent != NULL);
+ assert((node == NULL) || (rbtree_node_parent(node) == parent));
+
+ if (parent->children[RBTREE_LEFT] == node) {
+ return RBTREE_LEFT;
+ }
+
+ assert(parent->children[RBTREE_RIGHT] == node);
+
+ return RBTREE_RIGHT;
+}
+
+/*
+ * Return the color of a node.
+ */
+static inline int
+rbtree_node_color(const struct rbtree_node *node)
+{
+ return node->parent & RBTREE_COLOR_MASK;
+}
+
+/*
+ * Return true if the node is red.
+ */
+static inline int
+rbtree_node_is_red(const struct rbtree_node *node)
+{
+ return rbtree_node_color(node) == RBTREE_COLOR_RED;
+}
+
+/*
+ * Return true if the node is black.
+ */
+static inline int
+rbtree_node_is_black(const struct rbtree_node *node)
+{
+ return rbtree_node_color(node) == RBTREE_COLOR_BLACK;
+}
+
+/*
+ * Set the parent of a node, retaining its current color.
+ */
+static inline void
+rbtree_node_set_parent(struct rbtree_node *node, struct rbtree_node *parent)
+{
+ assert(rbtree_node_check_alignment(node));
+ assert(rbtree_node_check_alignment(parent));
+
+ node->parent = (uintptr_t)parent | (node->parent & RBTREE_COLOR_MASK);
+}
+
+/*
+ * Set the color of a node, retaining its current parent.
+ */
+static inline void
+rbtree_node_set_color(struct rbtree_node *node, int color)
+{
+ assert((color & ~RBTREE_COLOR_MASK) == 0);
+ node->parent = (node->parent & RBTREE_PARENT_MASK) | color;
+}
+
+/*
+ * Set the color of a node to red, retaining its current parent.
+ */
+static inline void
+rbtree_node_set_red(struct rbtree_node *node)
+{
+ rbtree_node_set_color(node, RBTREE_COLOR_RED);
+}
+
+/*
+ * Set the color of a node to black, retaining its current parent.
+ */
+static inline void
+rbtree_node_set_black(struct rbtree_node *node)
+{
+ rbtree_node_set_color(node, RBTREE_COLOR_BLACK);
+}
+
+/*
+ * Return the left-most deepest child node of the given node.
+ */
+static struct rbtree_node *
+rbtree_node_find_deepest(struct rbtree_node *node)
+{
+ struct rbtree_node *parent;
+
+ assert(node != NULL);
+
+ for (;;) {
+ parent = node;
+ node = node->children[RBTREE_LEFT];
+
+ if (node == NULL) {
+ node = parent->children[RBTREE_RIGHT];
+
+ if (node == NULL) {
+ return parent;
+ }
+ }
+ }
+}
+
+/*
+ * Perform a tree rotation, rooted at the given node.
+ *
+ * The direction parameter defines the rotation direction and is either
+ * RBTREE_LEFT or RBTREE_RIGHT.
+ */
+static void
+rbtree_rotate(struct rbtree *tree, struct rbtree_node *node, int direction)
+{
+ struct rbtree_node *parent, *rnode;
+ int left, right;
+
+ left = direction;
+ right = 1 - left;
+ parent = rbtree_node_parent(node);
+ rnode = node->children[right];
+
+ node->children[right] = rnode->children[left];
+
+ if (rnode->children[left] != NULL) {
+ rbtree_node_set_parent(rnode->children[left], node);
+ }
+
+ rnode->children[left] = node;
+ rbtree_node_set_parent(rnode, parent);
+
+ if (unlikely(parent == NULL)) {
+ tree->root = rnode;
+ } else {
+ parent->children[rbtree_node_index(node, parent)] = rnode;
+ }
+
+ rbtree_node_set_parent(node, rnode);
+}
+
+void
+rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
+ int index, struct rbtree_node *node)
+{
+ struct rbtree_node *grand_parent, *uncle;
+ int left, right;
+
+ assert(rbtree_node_check_alignment(parent));
+ assert(rbtree_node_check_alignment(node));
+
+ node->parent = (uintptr_t)parent | RBTREE_COLOR_RED;
+ node->children[RBTREE_LEFT] = NULL;
+ node->children[RBTREE_RIGHT] = NULL;
+
+ if (unlikely(parent == NULL)) {
+ tree->root = node;
+ } else {
+ parent->children[index] = node;
+ }
+
+ for (;;) {
+ if (parent == NULL) {
+ rbtree_node_set_black(node);
+ break;
+ }
+
+ if (rbtree_node_is_black(parent)) {
+ break;
+ }
+
+ grand_parent = rbtree_node_parent(parent);
+ assert(grand_parent != NULL);
+
+ left = rbtree_node_index(parent, grand_parent);
+ right = 1 - left;
+
+ uncle = grand_parent->children[right];
+
+ /*
+ * Uncle is red. Flip colors and repeat at grand parent.
+ */
+ if ((uncle != NULL) && rbtree_node_is_red(uncle)) {
+ rbtree_node_set_black(uncle);
+ rbtree_node_set_black(parent);
+ rbtree_node_set_red(grand_parent);
+ node = grand_parent;
+ parent = rbtree_node_parent(node);
+ continue;
+ }
+
+ /*
+ * Node is the right child of its parent. Rotate left at parent.
+ */
+ if (parent->children[right] == node) {
+ rbtree_rotate(tree, parent, left);
+ parent = node;
+ }
+
+ /*
+ * Node is the left child of its parent. Handle colors, rotate right
+ * at grand parent, and leave.
+ */
+ rbtree_node_set_black(parent);
+ rbtree_node_set_red(grand_parent);
+ rbtree_rotate(tree, grand_parent, right);
+ break;
+ }
+
+ assert(rbtree_node_is_black(tree->root));
+}
+
+void *
+rbtree_replace_slot(struct rbtree *tree, rbtree_slot_t slot,
+ struct rbtree_node *node)
+{
+ struct rbtree_node *parent, *prev;
+ int index;
+
+ parent = rbtree_slot_parent(slot);
+
+ if (!parent) {
+ prev = tree->root;
+ tree->root = node;
+ } else {
+ index = rbtree_slot_index(slot);
+ assert(rbtree_check_index(index));
+ prev = parent->children[index];
+ parent->children[index] = node;
+ }
+
+ assert(prev);
+ *node = *prev;
+
+ for (size_t i = 0; i < ARRAY_SIZE(node->children); i++) {
+ if (!node->children[i]) {
+ continue;
+ }
+
+
+ rbtree_node_set_parent(node->children[i], node);
+ }
+
+ return prev;
+}
+
+void
+rbtree_remove(struct rbtree *tree, struct rbtree_node *node)
+{
+ struct rbtree_node *child, *parent, *brother;
+ int color, left, right;
+
+ if (node->children[RBTREE_LEFT] == NULL) {
+ child = node->children[RBTREE_RIGHT];
+ } else if (node->children[RBTREE_RIGHT] == NULL) {
+ child = node->children[RBTREE_LEFT];
+ } else {
+ struct rbtree_node *successor;
+
+ /*
+ * Two-children case: replace the node with its successor.
+ */
+
+ successor = node->children[RBTREE_RIGHT];
+
+ while (successor->children[RBTREE_LEFT] != NULL) {
+ successor = successor->children[RBTREE_LEFT];
+ }
+
+ color = rbtree_node_color(successor);
+ child = successor->children[RBTREE_RIGHT];
+ parent = rbtree_node_parent(node);
+
+ if (unlikely(parent == NULL)) {
+ tree->root = successor;
+ } else {
+ parent->children[rbtree_node_index(node, parent)] = successor;
+ }
+
+ parent = rbtree_node_parent(successor);
+
+ /*
+ * Set parent directly to keep the original color.
+ */
+ successor->parent = node->parent;
+ successor->children[RBTREE_LEFT] = node->children[RBTREE_LEFT];
+ rbtree_node_set_parent(successor->children[RBTREE_LEFT], successor);
+
+ if (node == parent) {
+ parent = successor;
+ } else {
+ successor->children[RBTREE_RIGHT] = node->children[RBTREE_RIGHT];
+ rbtree_node_set_parent(successor->children[RBTREE_RIGHT],
+ successor);
+ parent->children[RBTREE_LEFT] = child;
+
+ if (child != NULL) {
+ rbtree_node_set_parent(child, parent);
+ }
+ }
+
+ goto update_color;
+ }
+
+ /*
+ * Node has at most one child.
+ */
+
+ color = rbtree_node_color(node);
+ parent = rbtree_node_parent(node);
+
+ if (child != NULL) {
+ rbtree_node_set_parent(child, parent);
+ }
+
+ if (unlikely(parent == NULL)) {
+ tree->root = child;
+ } else {
+ parent->children[rbtree_node_index(node, parent)] = child;
+ }
+
+ /*
+ * The node has been removed, update the colors. The child pointer can
+ * be NULL, in which case it is considered a black leaf.
+ */
+update_color:
+ if (color == RBTREE_COLOR_RED) {
+ return;
+ }
+
+ for (;;) {
+ if ((child != NULL) && rbtree_node_is_red(child)) {
+ rbtree_node_set_black(child);
+ break;
+ }
+
+ if (parent == NULL) {
+ break;
+ }
+
+ left = rbtree_node_index(child, parent);
+ right = 1 - left;
+
+ brother = parent->children[right];
+
+ /*
+ * Brother is red. Recolor and rotate left at parent so that brother
+ * becomes black.
+ */
+ if (rbtree_node_is_red(brother)) {
+ rbtree_node_set_black(brother);
+ rbtree_node_set_red(parent);
+ rbtree_rotate(tree, parent, left);
+ brother = parent->children[right];
+ }
+
+ assert(brother != NULL);
+
+ /*
+ * Brother has no red child. Recolor and repeat at parent.
+ */
+ if (((brother->children[RBTREE_LEFT] == NULL)
+ || rbtree_node_is_black(brother->children[RBTREE_LEFT]))
+ && ((brother->children[RBTREE_RIGHT] == NULL)
+ || rbtree_node_is_black(brother->children[RBTREE_RIGHT]))) {
+ rbtree_node_set_red(brother);
+ child = parent;
+ parent = rbtree_node_parent(child);
+ continue;
+ }
+
+ /*
+ * Brother's right child is black. Recolor and rotate right at brother.
+ */
+ if ((brother->children[right] == NULL)
+ || rbtree_node_is_black(brother->children[right])) {
+ rbtree_node_set_black(brother->children[left]);
+ rbtree_node_set_red(brother);
+ rbtree_rotate(tree, brother, right);
+ brother = parent->children[right];
+ }
+
+ /*
+ * Brother's left child is black. Exchange parent and brother colors
+ * (we already know brother is black), set brother's right child black,
+ * rotate left at parent and leave.
+ */
+ assert(brother->children[right] != NULL);
+ rbtree_node_set_color(brother, rbtree_node_color(parent));
+ rbtree_node_set_black(parent);
+ rbtree_node_set_black(brother->children[right]);
+ rbtree_rotate(tree, parent, left);
+ break;
+ }
+
+ assert((tree->root == NULL) || rbtree_node_is_black(tree->root));
+}
+
+struct rbtree_node *
+rbtree_nearest(struct rbtree_node *parent, int index, int direction)
+{
+ assert(rbtree_check_index(direction));
+
+ if (parent == NULL) {
+ return NULL;
+ }
+
+ assert(rbtree_check_index(index));
+
+ if (index != direction) {
+ return parent;
+ }
+
+ return rbtree_walk(parent, direction);
+}
+
+struct rbtree_node *
+rbtree_firstlast(const struct rbtree *tree, int direction)
+{
+ struct rbtree_node *prev, *cur;
+
+ assert(rbtree_check_index(direction));
+
+ prev = NULL;
+
+ for (cur = tree->root; cur != NULL; cur = cur->children[direction]) {
+ prev = cur;
+ }
+
+ return prev;
+}
+
+struct rbtree_node *
+rbtree_walk(struct rbtree_node *node, int direction)
+{
+ int left, right;
+
+ assert(rbtree_check_index(direction));
+
+ left = direction;
+ right = 1 - left;
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ if (node->children[left] != NULL) {
+ node = node->children[left];
+
+ while (node->children[right] != NULL) {
+ node = node->children[right];
+ }
+ } else {
+ struct rbtree_node *parent;
+ int index;
+
+ for (;;) {
+ parent = rbtree_node_parent(node);
+
+ if (parent == NULL) {
+ return NULL;
+ }
+
+ index = rbtree_node_index(node, parent);
+ node = parent;
+
+ if (index == right) {
+ break;
+ }
+ }
+ }
+
+ return node;
+}
+
+struct rbtree_node *
+rbtree_postwalk_deepest(const struct rbtree *tree)
+{
+ struct rbtree_node *node;
+
+ node = tree->root;
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ return rbtree_node_find_deepest(node);
+}
+
+struct rbtree_node *
+rbtree_postwalk_unlink(struct rbtree_node *node)
+{
+ struct rbtree_node *parent;
+ int index;
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ assert(node->children[RBTREE_LEFT] == NULL);
+ assert(node->children[RBTREE_RIGHT] == NULL);
+
+ parent = rbtree_node_parent(node);
+
+ if (parent == NULL) {
+ return NULL;
+ }
+
+ index = rbtree_node_index(node, parent);
+ parent->children[index] = NULL;
+ node = parent->children[RBTREE_RIGHT];
+
+ if (node == NULL) {
+ return parent;
+ }
+
+ return rbtree_node_find_deepest(node);
+}
diff --git a/src/rbtree.h b/src/rbtree.h
new file mode 100644
index 0000000..1838c27
--- /dev/null
+++ b/src/rbtree.h
@@ -0,0 +1,328 @@
+/*
+ * Copyright (c) 2010-2015 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Red-black tree.
+ */
+
+#ifndef _RBTREE_H
+#define _RBTREE_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "macros.h"
+
+/*
+ * Indexes of the left and right nodes in the children array of a node.
+ */
+#define RBTREE_LEFT 0
+#define RBTREE_RIGHT 1
+
+/*
+ * Red-black node.
+ */
+struct rbtree_node;
+
+/*
+ * Red-black tree.
+ */
+struct rbtree;
+
+/*
+ * Insertion point identifier.
+ */
+typedef uintptr_t rbtree_slot_t;
+
+/*
+ * Static tree initializer.
+ */
+#define RBTREE_INITIALIZER { NULL }
+
+#include "rbtree_i.h"
+
+/*
+ * Initialize a tree.
+ */
+static inline void
+rbtree_init(struct rbtree *tree)
+{
+ tree->root = NULL;
+}
+
+/*
+ * Initialize a node.
+ *
+ * A node is in no tree when its parent points to itself.
+ */
+static inline void
+rbtree_node_init(struct rbtree_node *node)
+{
+ assert(rbtree_node_check_alignment(node));
+
+ node->parent = (uintptr_t)node | RBTREE_COLOR_RED;
+ node->children[RBTREE_LEFT] = NULL;
+ node->children[RBTREE_RIGHT] = NULL;
+}
+
+/*
+ * Return true if node is in no tree.
+ */
+static inline int
+rbtree_node_unlinked(const struct rbtree_node *node)
+{
+ return rbtree_node_parent(node) == node;
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define rbtree_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Return true if tree is empty.
+ */
+static inline int
+rbtree_empty(const struct rbtree *tree)
+{
+ return tree->root == NULL;
+}
+
+/*
+ * Look up a node in a tree.
+ *
+ * Note that implementing the lookup algorithm as a macro gives two benefits:
+ * First, it avoids the overhead of a callback function. Next, the type of the
+ * cmp_fn parameter isn't rigid. The only guarantee offered by this
+ * implementation is that the key parameter is the first parameter given to
+ * cmp_fn. This way, users can pass only the value they need for comparison
+ * instead of e.g. allocating a full structure on the stack.
+ *
+ * See rbtree_insert().
+ */
+#define rbtree_lookup(tree, key, cmp_fn) \
+MACRO_BEGIN \
+ struct rbtree_node *___cur; \
+ int ___diff; \
+ \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(key, ___cur); \
+ \
+ if (___diff == 0) { \
+ break; \
+ } \
+ \
+ ___cur = ___cur->children[rbtree_d2i(___diff)]; \
+ } \
+ \
+ ___cur; \
+MACRO_END
+
+/*
+ * Look up a node or one of its nearest nodes in a tree.
+ *
+ * This macro essentially acts as rbtree_lookup() but if no entry matched
+ * the key, an additional step is performed to obtain the next or previous
+ * node, depending on the direction (left or right).
+ *
+ * The constraints that apply to the key parameter are the same as for
+ * rbtree_lookup().
+ */
+#define rbtree_lookup_nearest(tree, key, cmp_fn, dir) \
+MACRO_BEGIN \
+ struct rbtree_node *___cur, *___prev; \
+ int ___diff, ___index; \
+ \
+ ___prev = NULL; \
+ ___index = -1; \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(key, ___cur); \
+ \
+ if (___diff == 0) { \
+ break; \
+ } \
+ \
+ ___prev = ___cur; \
+ ___index = rbtree_d2i(___diff); \
+ ___cur = ___cur->children[___index]; \
+ } \
+ \
+ if (___cur == NULL) { \
+ ___cur = rbtree_nearest(___prev, ___index, dir); \
+ } \
+ \
+ ___cur; \
+MACRO_END
+
+/*
+ * Insert a node in a tree.
+ *
+ * This macro performs a standard lookup to obtain the insertion point of
+ * the given node in the tree (it is assumed that the inserted node never
+ * compares equal to any other entry in the tree) and links the node. It
+ * then checks red-black rules violations, and rebalances the tree if
+ * necessary.
+ *
+ * Unlike rbtree_lookup(), the cmp_fn parameter must compare two complete
+ * entries, so it is suggested to use two different comparison inline
+ * functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no
+ * guarantee about the order of the nodes given to the comparison function.
+ *
+ * See rbtree_lookup().
+ */
+#define rbtree_insert(tree, node, cmp_fn) \
+MACRO_BEGIN \
+ struct rbtree_node *___cur, *___prev; \
+ int ___diff, ___index; \
+ \
+ ___prev = NULL; \
+ ___index = -1; \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(node, ___cur); \
+ assert(___diff != 0); \
+ ___prev = ___cur; \
+ ___index = rbtree_d2i(___diff); \
+ ___cur = ___cur->children[___index]; \
+ } \
+ \
+ rbtree_insert_rebalance(tree, ___prev, ___index, node); \
+MACRO_END
+
+/*
+ * Look up a node/slot pair in a tree.
+ *
+ * This macro essentially acts as rbtree_lookup() but in addition to a node,
+ * it also returns a slot, which identifies an insertion point in the tree.
+ * If the returned node is NULL, the slot can be used by rbtree_insert_slot()
+ * to insert without the overhead of an additional lookup.
+ *
+ * The constraints that apply to the key parameter are the same as for
+ * rbtree_lookup().
+ */
+#define rbtree_lookup_slot(tree, key, cmp_fn, slot) \
+MACRO_BEGIN \
+ struct rbtree_node *___cur, *___prev; \
+ int ___diff, ___index; \
+ \
+ ___prev = NULL; \
+ ___index = 0; \
+ ___cur = (tree)->root; \
+ \
+ while (___cur != NULL) { \
+ ___diff = cmp_fn(key, ___cur); \
+ \
+ if (___diff == 0) { \
+ break; \
+ } \
+ \
+ ___prev = ___cur; \
+ ___index = rbtree_d2i(___diff); \
+ ___cur = ___cur->children[___index]; \
+ } \
+ \
+ (slot) = rbtree_slot(___prev, ___index); \
+ ___cur; \
+MACRO_END
+
+/*
+ * Insert a node at an insertion point in a tree.
+ *
+ * This macro essentially acts as rbtree_insert() except that it doesn't
+ * obtain the insertion point with a standard lookup. The insertion point
+ * is obtained by calling rbtree_lookup_slot(). In addition, the new node
+ * must not compare equal to an existing node in the tree (i.e. the slot
+ * must denote a NULL node).
+ */
+static inline void
+rbtree_insert_slot(struct rbtree *tree, rbtree_slot_t slot,
+ struct rbtree_node *node)
+{
+ struct rbtree_node *parent;
+ int index;
+
+ parent = rbtree_slot_parent(slot);
+ index = rbtree_slot_index(slot);
+ rbtree_insert_rebalance(tree, parent, index, node);
+}
+
+/*
+ * Replace a node at an insertion point in a tree.
+ *
+ * The given node must compare strictly equal to the previous node,
+ * which is returned on completion.
+ */
+void * rbtree_replace_slot(struct rbtree *tree, rbtree_slot_t slot,
+ struct rbtree_node *node);
+
+/*
+ * Remove a node from a tree.
+ *
+ * After completion, the node is stale.
+ */
+void rbtree_remove(struct rbtree *tree, struct rbtree_node *node);
+
+/*
+ * Return the first node of a tree.
+ */
+#define rbtree_first(tree) rbtree_firstlast(tree, RBTREE_LEFT)
+
+/*
+ * Return the last node of a tree.
+ */
+#define rbtree_last(tree) rbtree_firstlast(tree, RBTREE_RIGHT)
+
+/*
+ * Return the node previous to the given node.
+ */
+#define rbtree_prev(node) rbtree_walk(node, RBTREE_LEFT)
+
+/*
+ * Return the node next to the given node.
+ */
+#define rbtree_next(node) rbtree_walk(node, RBTREE_RIGHT)
+
+/*
+ * Forge a loop to process all nodes of a tree, removing them when visited.
+ *
+ * This macro can only be used to destroy a tree, so that the resources used
+ * by the entries can be released by the user. It basically removes all nodes
+ * without doing any color checking.
+ *
+ * After completion, all nodes and the tree root member are stale.
+ */
+#define rbtree_for_each_remove(tree, node, tmp) \
+for (node = rbtree_postwalk_deepest(tree), \
+ tmp = rbtree_postwalk_unlink(node); \
+ node != NULL; \
+ node = tmp, tmp = rbtree_postwalk_unlink(node))
+
+#endif /* _RBTREE_H */
diff --git a/src/rbtree_i.h b/src/rbtree_i.h
new file mode 100644
index 0000000..f794373
--- /dev/null
+++ b/src/rbtree_i.h
@@ -0,0 +1,197 @@
+/*
+ * Copyright (c) 2010-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#ifndef _RBTREE_I_H
+#define _RBTREE_I_H
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "macros.h"
+
+/*
+ * Red-black node structure.
+ *
+ * To reduce the number of branches and the instruction cache footprint,
+ * the left and right child pointers are stored in an array, and the symmetry
+ * of most tree operations is exploited by using left/right variables when
+ * referring to children.
+ *
+ * In addition, this implementation assumes that all nodes are 4-byte aligned,
+ * so that the least significant bit of the parent member can be used to store
+ * the color of the node. This is true for all modern 32 and 64 bits
+ * architectures, as long as the nodes aren't embedded in structures with
+ * special alignment constraints such as member packing.
+ */
+struct rbtree_node {
+ uintptr_t parent;
+ struct rbtree_node *children[2];
+};
+
+/*
+ * Red-black tree structure.
+ */
+struct rbtree {
+ struct rbtree_node *root;
+};
+
+/*
+ * Masks applied on the parent member of a node to obtain either the
+ * color or the parent address.
+ */
+#define RBTREE_COLOR_MASK ((uintptr_t)0x1)
+#define RBTREE_PARENT_MASK (~(uintptr_t)0x3)
+
+/*
+ * Node colors.
+ */
+#define RBTREE_COLOR_RED 0
+#define RBTREE_COLOR_BLACK 1
+
+/*
+ * Masks applied on slots to obtain either the child index or the parent
+ * address.
+ */
+#define RBTREE_SLOT_INDEX_MASK 0x1UL
+#define RBTREE_SLOT_PARENT_MASK (~RBTREE_SLOT_INDEX_MASK)
+
+/*
+ * Return true if the given index is a valid child index.
+ */
+static inline int
+rbtree_check_index(int index)
+{
+ return index == (index & 1);
+}
+
+/*
+ * Convert the result of a comparison into an index in the children array
+ * (0 or 1).
+ *
+ * This function is mostly used when looking up a node.
+ */
+static inline int
+rbtree_d2i(int diff)
+{
+ return !(diff <= 0);
+}
+
+/*
+ * Return true if the given pointer is suitably aligned.
+ */
+static inline int
+rbtree_node_check_alignment(const struct rbtree_node *node)
+{
+ return ((uintptr_t)node & (~RBTREE_PARENT_MASK)) == 0;
+}
+
+/*
+ * Return the parent of a node.
+ */
+static inline struct rbtree_node *
+rbtree_node_parent(const struct rbtree_node *node)
+{
+ return (struct rbtree_node *)(node->parent & RBTREE_PARENT_MASK);
+}
+
+/*
+ * Translate an insertion point into a slot.
+ */
+static inline rbtree_slot_t
+rbtree_slot(struct rbtree_node *parent, int index)
+{
+ assert(rbtree_node_check_alignment(parent));
+ assert(rbtree_check_index(index));
+ return (rbtree_slot_t)parent | index;
+}
+
+/*
+ * Extract the parent address from a slot.
+ */
+static inline struct rbtree_node *
+rbtree_slot_parent(rbtree_slot_t slot)
+{
+ return (struct rbtree_node *)(slot & RBTREE_SLOT_PARENT_MASK);
+}
+
+/*
+ * Extract the index from a slot.
+ */
+static inline int
+rbtree_slot_index(rbtree_slot_t slot)
+{
+ return slot & RBTREE_SLOT_INDEX_MASK;
+}
+
+/*
+ * Insert a node in a tree, rebalancing it if necessary.
+ *
+ * The index parameter is the index in the children array of the parent where
+ * the new node is to be inserted. It is ignored if the parent is NULL.
+ *
+ * This function is intended to be used by the rbtree_insert() macro only.
+ */
+void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
+ int index, struct rbtree_node *node);
+
+/*
+ * Return the previous or next node relative to a location in a tree.
+ *
+ * The parent and index parameters define the location, which can be empty.
+ * The direction parameter is either RBTREE_LEFT (to obtain the previous
+ * node) or RBTREE_RIGHT (to obtain the next one).
+ */
+struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index,
+ int direction);
+
+/*
+ * Return the first or last node of a tree.
+ *
+ * The direction parameter is either RBTREE_LEFT (to obtain the first node)
+ * or RBTREE_RIGHT (to obtain the last one).
+ */
+struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction);
+
+/*
+ * Return the node next to, or previous to the given node.
+ *
+ * The direction parameter is either RBTREE_LEFT (to obtain the previous node)
+ * or RBTREE_RIGHT (to obtain the next one).
+ */
+struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction);
+
+/*
+ * Return the left-most deepest node of a tree, which is the starting point of
+ * the postorder traversal performed by rbtree_for_each_remove().
+ */
+struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree);
+
+/*
+ * Unlink a node from its tree and return the next (right) node in postorder.
+ */
+struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node);
+
+#endif /* _RBTREE_I_H */
diff --git a/src/rdxtree.c b/src/rdxtree.c
new file mode 100644
index 0000000..3df6ccb
--- /dev/null
+++ b/src/rdxtree.c
@@ -0,0 +1,863 @@
+/*
+ * Copyright (c) 2011-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include <stdbool.h>
+
+#include <assert.h>
+#include <errno.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "macros.h"
+#include "rdxtree.h"
+#include "rdxtree_i.h"
+
+/*
+ * Mask applied on an entry to obtain its address.
+ */
+#define RDXTREE_ENTRY_ADDR_MASK (~0x3UL)
+
+/*
+ * Global properties used to shape radix trees.
+ */
+#define RDXTREE_RADIX 6
+#define RDXTREE_RADIX_SIZE (1UL << RDXTREE_RADIX)
+#define RDXTREE_RADIX_MASK (RDXTREE_RADIX_SIZE - 1)
+
+#if RDXTREE_RADIX < 6
+typedef unsigned long rdxtree_bm_t;
+#define rdxtree_ffs(x) __builtin_ffsl(x)
+#elif RDXTREE_RADIX == 6 /* RDXTREE_RADIX < 6 */
+typedef unsigned long long rdxtree_bm_t;
+#define rdxtree_ffs(x) __builtin_ffsll(x)
+#else /* RDXTREE_RADIX < 6 */
+#error "radix too high"
+#endif /* RDXTREE_RADIX < 6 */
+
+/*
+ * Allocation bitmap size in bits.
+ */
+#define RDXTREE_BM_SIZE (sizeof(rdxtree_bm_t) * CHAR_BIT)
+
+/*
+ * Empty/full allocation bitmap words.
+ */
+#define RDXTREE_BM_EMPTY ((rdxtree_bm_t)0)
+#define RDXTREE_BM_FULL \
+ ((~(rdxtree_bm_t)0) >> (RDXTREE_BM_SIZE - RDXTREE_RADIX_SIZE))
+
+/*
+ * Radix tree node.
+ *
+ * The height of a tree is the number of nodes to traverse until stored
+ * pointers are reached. A height of 0 means the entries of a node (or the
+ * tree root) directly point to stored pointers.
+ *
+ * The index is valid if and only if the parent isn't NULL.
+ *
+ * Concerning the allocation bitmap, a bit is set when the node it denotes,
+ * or one of its children, can be used to allocate an entry. Conversely, a bit
+ * is clear when the matching node and all of its children have no free entry.
+ *
+ * In order to support safe lockless lookups, in particular during a resize,
+ * each node includes the height of its subtree, which is invariant during
+ * the entire node lifetime. Since the tree height does vary, it can't be
+ * used to determine whether the tree root is a node or a stored pointer.
+ * This implementation assumes that all nodes and stored pointers are at least
+ * 4-byte aligned, and uses the least significant bit of entries to indicate
+ * the pointer type. This bit is set for internal nodes, and clear for stored
+ * pointers so that they can be accessed from slots without conversion.
+ */
+struct rdxtree_node {
+ struct rdxtree_node *parent;
+ unsigned short index;
+ unsigned short height;
+ unsigned short nr_entries;
+ rdxtree_bm_t alloc_bm;
+ void *entries[RDXTREE_RADIX_SIZE];
+};
+
+#ifdef RDXTREE_ENABLE_NODE_CREATION_FAILURES
+unsigned int rdxtree_fail_node_creation_threshold;
+unsigned int rdxtree_nr_node_creations;
+#endif /* RDXTREE_ENABLE_NODE_CREATION_FAILURES */
+
+static inline void
+rdxtree_assert_alignment(const void *ptr)
+{
+ assert(((uintptr_t)ptr & ~RDXTREE_ENTRY_ADDR_MASK) == 0);
+ (void)ptr;
+}
+
+static inline void *
+rdxtree_entry_addr(void *entry)
+{
+ return (void *)((uintptr_t)entry & RDXTREE_ENTRY_ADDR_MASK);
+}
+
+static inline int
+rdxtree_entry_is_node(const void *entry)
+{
+ return ((uintptr_t)entry & 1) != 0;
+}
+
+static inline void *
+rdxtree_node_to_entry(struct rdxtree_node *node)
+{
+ return (void *)((uintptr_t)node | 1);
+}
+
+static int
+rdxtree_node_create(struct rdxtree_node **nodep, unsigned short height)
+{
+ struct rdxtree_node *node;
+
+#ifdef RDXTREE_ENABLE_NODE_CREATION_FAILURES
+ if (rdxtree_fail_node_creation_threshold != 0) {
+ rdxtree_nr_node_creations++;
+
+ if (rdxtree_nr_node_creations == rdxtree_fail_node_creation_threshold) {
+ return ENOMEM;
+ }
+ }
+#endif /* RDXTREE_ENABLE_NODE_CREATION_FAILURES */
+
+ node = malloc(sizeof(*node));
+
+ if (node == NULL) {
+ return ENOMEM;
+ }
+
+ rdxtree_assert_alignment(node);
+ node->parent = NULL;
+ node->height = height;
+ node->nr_entries = 0;
+ node->alloc_bm = RDXTREE_BM_FULL;
+ memset(node->entries, 0, sizeof(node->entries));
+ *nodep = node;
+ return 0;
+}
+
+static void
+rdxtree_node_schedule_destruction(struct rdxtree_node *node)
+{
+ /*
+ * This function is intended to use the appropriate interface to defer
+ * destruction until all read-side references are dropped in an
+ * environment that provides lockless synchronization.
+ *
+ * Otherwise, it simply "schedules" destruction immediately.
+ */
+ free(node);
+}
+
+static inline void
+rdxtree_node_link(struct rdxtree_node *node, struct rdxtree_node *parent,
+ unsigned short index)
+{
+ node->parent = parent;
+ node->index = index;
+}
+
+static inline void
+rdxtree_node_unlink(struct rdxtree_node *node)
+{
+ assert(node->parent != NULL);
+ node->parent = NULL;
+}
+
+static inline int
+rdxtree_node_full(struct rdxtree_node *node)
+{
+ return (node->nr_entries == ARRAY_SIZE(node->entries));
+}
+
+static inline int
+rdxtree_node_empty(struct rdxtree_node *node)
+{
+ return (node->nr_entries == 0);
+}
+
+static inline void
+rdxtree_node_insert(struct rdxtree_node *node, unsigned short index,
+ void *entry)
+{
+ assert(index < ARRAY_SIZE(node->entries));
+ assert(node->entries[index] == NULL);
+
+ node->nr_entries++;
+ llsync_store_ptr(node->entries[index], entry);
+}
+
+static inline void
+rdxtree_node_insert_node(struct rdxtree_node *node, unsigned short index,
+ struct rdxtree_node *child)
+{
+ rdxtree_node_insert(node, index, rdxtree_node_to_entry(child));
+}
+
+static inline void
+rdxtree_node_remove(struct rdxtree_node *node, unsigned short index)
+{
+ assert(index < ARRAY_SIZE(node->entries));
+ assert(node->entries[index] != NULL);
+
+ node->nr_entries--;
+ llsync_store_ptr(node->entries[index], NULL);
+}
+
+static inline void *
+rdxtree_node_find(struct rdxtree_node *node, unsigned short *indexp)
+{
+ unsigned short index;
+ void *ptr;
+
+ index = *indexp;
+
+ while (index < ARRAY_SIZE(node->entries)) {
+ ptr = rdxtree_entry_addr(llsync_load_ptr(node->entries[index]));
+
+ if (ptr != NULL) {
+ *indexp = index;
+ return ptr;
+ }
+
+ index++;
+ }
+
+ return NULL;
+}
+
+static inline void
+rdxtree_node_bm_set(struct rdxtree_node *node, unsigned short index)
+{
+ node->alloc_bm |= (rdxtree_bm_t)1 << index;
+}
+
+static inline void
+rdxtree_node_bm_clear(struct rdxtree_node *node, unsigned short index)
+{
+ node->alloc_bm &= ~((rdxtree_bm_t)1 << index);
+}
+
+static inline int
+rdxtree_node_bm_is_set(struct rdxtree_node *node, unsigned short index)
+{
+ return (node->alloc_bm & ((rdxtree_bm_t)1 << index));
+}
+
+static inline int
+rdxtree_node_bm_empty(struct rdxtree_node *node)
+{
+ return (node->alloc_bm == RDXTREE_BM_EMPTY);
+}
+
+static inline unsigned short
+rdxtree_node_bm_first(struct rdxtree_node *node)
+{
+ return rdxtree_ffs(node->alloc_bm) - 1;
+}
+
+static inline rdxtree_key_t
+rdxtree_max_key(unsigned short height)
+{
+ size_t shift;
+
+ shift = RDXTREE_RADIX * height;
+
+ if (likely(shift < (sizeof(rdxtree_key_t) * CHAR_BIT))) {
+ return ((rdxtree_key_t)1 << shift) - 1;
+ } else {
+ return ~((rdxtree_key_t)0);
+ }
+}
+
+static inline bool
+rdxtree_key_alloc_enabled(const struct rdxtree *tree)
+{
+ return (tree->flags & RDXTREE_KEY_ALLOC);
+}
+
+static void
+rdxtree_shrink(struct rdxtree *tree)
+{
+ struct rdxtree_node *node;
+ void *entry;
+
+ while (tree->height > 0) {
+ node = rdxtree_entry_addr(tree->root);
+
+ if (node->nr_entries != 1) {
+ break;
+ }
+
+ entry = node->entries[0];
+
+ if (entry == NULL) {
+ break;
+ }
+
+ tree->height--;
+
+ if (tree->height > 0) {
+ rdxtree_node_unlink(rdxtree_entry_addr(entry));
+ }
+
+ llsync_store_ptr(tree->root, entry);
+ rdxtree_node_schedule_destruction(node);
+ }
+}
+
+static int
+rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key)
+{
+ struct rdxtree_node *root, *node;
+ unsigned short new_height;
+ int error;
+
+ new_height = tree->height + 1;
+
+ while (key > rdxtree_max_key(new_height)) {
+ new_height++;
+ }
+
+ if (tree->root == NULL) {
+ tree->height = new_height;
+ return 0;
+ }
+
+ root = rdxtree_entry_addr(tree->root);
+
+ do {
+ error = rdxtree_node_create(&node, tree->height);
+
+ if (error) {
+ rdxtree_shrink(tree);
+ return error;
+ }
+
+ if (tree->height == 0) {
+ if (rdxtree_key_alloc_enabled(tree)) {
+ rdxtree_node_bm_clear(node, 0);
+ }
+ } else {
+ rdxtree_node_link(root, node, 0);
+
+ if (rdxtree_key_alloc_enabled(tree)
+ && rdxtree_node_bm_empty(root)) {
+ rdxtree_node_bm_clear(node, 0);
+ }
+ }
+
+ rdxtree_node_insert(node, 0, tree->root);
+ tree->height++;
+ llsync_store_ptr(tree->root, rdxtree_node_to_entry(node));
+ root = node;
+ } while (new_height > tree->height);
+
+ return 0;
+}
+
+static void
+rdxtree_cleanup(struct rdxtree *tree, struct rdxtree_node *node)
+{
+ struct rdxtree_node *prev;
+
+ for (;;) {
+ if (likely(!rdxtree_node_empty(node))) {
+ if (unlikely(node->parent == NULL)) {
+ rdxtree_shrink(tree);
+ }
+
+ break;
+ }
+
+ if (node->parent == NULL) {
+ tree->height = 0;
+ llsync_store_ptr(tree->root, NULL);
+ rdxtree_node_schedule_destruction(node);
+ break;
+ }
+
+ prev = node;
+ node = node->parent;
+ rdxtree_node_unlink(prev);
+ rdxtree_node_remove(node, prev->index);
+ rdxtree_node_schedule_destruction(prev);
+ }
+}
+
+static void
+rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned short index)
+{
+ for (;;) {
+ rdxtree_node_bm_clear(node, index);
+
+ if (!rdxtree_node_full(node) || (node->parent == NULL)) {
+ break;
+ }
+
+ index = node->index;
+ node = node->parent;
+ }
+}
+
+int
+rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key,
+ void *ptr, void ***slotp)
+{
+ struct rdxtree_node *node, *prev;
+ unsigned short height, shift;
+ unsigned short index = 0; /* GCC */
+ int error;
+
+ assert(ptr != NULL);
+ rdxtree_assert_alignment(ptr);
+
+ if (unlikely(key > rdxtree_max_key(tree->height))) {
+ error = rdxtree_grow(tree, key);
+
+ if (error) {
+ return error;
+ }
+ }
+
+ height = tree->height;
+
+ if (unlikely(height == 0)) {
+ if (tree->root != NULL) {
+ return EBUSY;
+ }
+
+ llsync_store_ptr(tree->root, ptr);
+
+ if (slotp != NULL) {
+ *slotp = &tree->root;
+ }
+
+ return 0;
+ }
+
+ node = rdxtree_entry_addr(tree->root);
+ shift = (height - 1) * RDXTREE_RADIX;
+ prev = NULL;
+
+ do {
+ if (node == NULL) {
+ error = rdxtree_node_create(&node, height - 1);
+
+ if (error) {
+ if (prev == NULL) {
+ tree->height = 0;
+ } else {
+ rdxtree_cleanup(tree, prev);
+ }
+
+ return error;
+ }
+
+ if (prev == NULL) {
+ llsync_store_ptr(tree->root, rdxtree_node_to_entry(node));
+ } else {
+ rdxtree_node_link(node, prev, index);
+ rdxtree_node_insert_node(prev, index, node);
+ }
+ }
+
+ prev = node;
+ index = (unsigned short)(key >> shift) & RDXTREE_RADIX_MASK;
+ node = rdxtree_entry_addr(prev->entries[index]);
+ shift -= RDXTREE_RADIX;
+ height--;
+ } while (height > 0);
+
+ if (unlikely(node != NULL)) {
+ return EBUSY;
+ }
+
+ rdxtree_node_insert(prev, index, ptr);
+
+ if (rdxtree_key_alloc_enabled(tree)) {
+ rdxtree_insert_bm_clear(prev, index);
+ }
+
+ if (slotp != NULL) {
+ *slotp = &prev->entries[index];
+ }
+
+ return 0;
+}
+
+int
+rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
+ rdxtree_key_t *keyp, void ***slotp)
+{
+ struct rdxtree_node *node, *prev;
+ unsigned short height, shift;
+ unsigned short index = 0; /* GCC */
+ rdxtree_key_t key;
+ int error;
+
+ assert(rdxtree_key_alloc_enabled(tree));
+ assert(ptr != NULL);
+ rdxtree_assert_alignment(ptr);
+
+ height = tree->height;
+
+ if (unlikely(height == 0)) {
+ if (tree->root == NULL) {
+ llsync_store_ptr(tree->root, ptr);
+ *keyp = 0;
+
+ if (slotp != NULL) {
+ *slotp = &tree->root;
+ }
+
+ return 0;
+ }
+
+ goto grow;
+ }
+
+ node = rdxtree_entry_addr(tree->root);
+ key = 0;
+ shift = (height - 1) * RDXTREE_RADIX;
+ prev = NULL;
+
+ do {
+ if (node == NULL) {
+ error = rdxtree_node_create(&node, height - 1);
+
+ if (error) {
+ rdxtree_cleanup(tree, prev);
+ return error;
+ }
+
+ rdxtree_node_link(node, prev, index);
+ rdxtree_node_insert_node(prev, index, node);
+ }
+
+ prev = node;
+ index = rdxtree_node_bm_first(node);
+
+ if (index == (unsigned short)-1) {
+ goto grow;
+ }
+
+ key |= (rdxtree_key_t)index << shift;
+ node = rdxtree_entry_addr(node->entries[index]);
+ shift -= RDXTREE_RADIX;
+ height--;
+ } while (height > 0);
+
+ rdxtree_node_insert(prev, index, ptr);
+ rdxtree_insert_bm_clear(prev, index);
+
+ if (slotp != NULL) {
+ *slotp = &prev->entries[index];
+ }
+
+ goto out;
+
+grow:
+ key = rdxtree_max_key(height) + 1;
+ error = rdxtree_insert_common(tree, key, ptr, slotp);
+
+ if (error) {
+ return error;
+ }
+
+out:
+ *keyp = key;
+ return 0;
+}
+
+static void
+rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned short index)
+{
+ do {
+ rdxtree_node_bm_set(node, index);
+
+ if (node->parent == NULL) {
+ break;
+ }
+
+ index = node->index;
+ node = node->parent;
+ } while (!rdxtree_node_bm_is_set(node, index));
+}
+
+void *
+rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key)
+{
+ struct rdxtree_node *node, *prev;
+ unsigned short height, shift, index;
+
+ height = tree->height;
+
+ if (unlikely(key > rdxtree_max_key(height))) {
+ return NULL;
+ }
+
+ node = rdxtree_entry_addr(tree->root);
+
+ if (unlikely(height == 0)) {
+ llsync_store_ptr(tree->root, NULL);
+ return node;
+ }
+
+ shift = (height - 1) * RDXTREE_RADIX;
+
+ do {
+ if (node == NULL) {
+ return NULL;
+ }
+
+ prev = node;
+ index = (unsigned short)(key >> shift) & RDXTREE_RADIX_MASK;
+ node = rdxtree_entry_addr(node->entries[index]);
+ shift -= RDXTREE_RADIX;
+ height--;
+ } while (height > 0);
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ if (rdxtree_key_alloc_enabled(tree)) {
+ rdxtree_remove_bm_set(prev, index);
+ }
+
+ rdxtree_node_remove(prev, index);
+ rdxtree_cleanup(tree, prev);
+ return node;
+}
+
+void *
+rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key,
+ int get_slot)
+{
+ struct rdxtree_node *node, *prev;
+ unsigned short height, shift, index;
+ void *entry;
+
+ entry = llsync_load_ptr(tree->root);
+
+ if (entry == NULL) {
+ node = NULL;
+ height = 0;
+ } else {
+ node = rdxtree_entry_addr(entry);
+ height = rdxtree_entry_is_node(entry) ? node->height + 1 : 0;
+ }
+
+ if (key > rdxtree_max_key(height)) {
+ return NULL;
+ }
+
+ if (height == 0) {
+ if (node == NULL) {
+ return NULL;
+ }
+
+ return get_slot ? (void *)&tree->root : node;
+ }
+
+ shift = (height - 1) * RDXTREE_RADIX;
+
+ do {
+ if (node == NULL) {
+ return NULL;
+ }
+
+ prev = node;
+ index = (unsigned short)(key >> shift) & RDXTREE_RADIX_MASK;
+ entry = llsync_load_ptr(node->entries[index]);
+ node = rdxtree_entry_addr(entry);
+ shift -= RDXTREE_RADIX;
+ height--;
+ } while (height > 0);
+
+ if (node == NULL) {
+ return NULL;
+ }
+
+ return get_slot ? (void *)&prev->entries[index] : node;
+}
+
+void *
+rdxtree_replace_slot(void **slot, void *ptr)
+{
+ void *old;
+
+ assert(ptr != NULL);
+ rdxtree_assert_alignment(ptr);
+
+ old = *slot;
+ assert(old != NULL);
+ rdxtree_assert_alignment(old);
+ llsync_store_ptr(*slot, ptr);
+ return old;
+}
+
+static void *
+rdxtree_walk_next(struct rdxtree *tree, struct rdxtree_iter *iter)
+{
+ struct rdxtree_node *root, *node, *prev;
+ unsigned short height, shift, index, orig_index;
+ rdxtree_key_t key;
+ void *entry;
+
+ entry = llsync_load_ptr(tree->root);
+
+ if (entry == NULL) {
+ return NULL;
+ }
+
+ if (!rdxtree_entry_is_node(entry)) {
+ if (iter->key != (rdxtree_key_t)-1) {
+ return NULL;
+ } else {
+ iter->key = 0;
+ return rdxtree_entry_addr(entry);
+ }
+ }
+
+ key = iter->key + 1;
+
+ if ((key == 0) && (iter->node != NULL)) {
+ return NULL;
+ }
+
+ root = rdxtree_entry_addr(entry);
+
+restart:
+ node = root;
+ height = root->height + 1;
+
+ if (key > rdxtree_max_key(height)) {
+ return NULL;
+ }
+
+ shift = (height - 1) * RDXTREE_RADIX;
+
+ do {
+ prev = node;
+ index = (key >> shift) & RDXTREE_RADIX_MASK;
+ orig_index = index;
+ node = rdxtree_node_find(node, &index);
+
+ if (node == NULL) {
+ shift += RDXTREE_RADIX;
+ key = ((key >> shift) + 1) << shift;
+
+ if (key == 0) {
+ return NULL;
+ }
+
+ goto restart;
+ }
+
+ if (orig_index != index) {
+ key = ((key >> shift) + (index - orig_index)) << shift;
+ }
+
+ shift -= RDXTREE_RADIX;
+ height--;
+ } while (height > 0);
+
+ iter->node = prev;
+ iter->key = key;
+ return node;
+}
+
+void *
+rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter)
+{
+ unsigned short index, orig_index;
+ void *ptr;
+
+ if (iter->node == NULL) {
+ return rdxtree_walk_next(tree, iter);
+ }
+
+ index = (iter->key + 1) & RDXTREE_RADIX_MASK;
+
+ if (index != 0) {
+ orig_index = index;
+ ptr = rdxtree_node_find(iter->node, &index);
+
+ if (ptr != NULL) {
+ iter->key += (index - orig_index) + 1;
+ return ptr;
+ }
+ }
+
+ return rdxtree_walk_next(tree, iter);
+}
+
+void
+rdxtree_remove_all(struct rdxtree *tree)
+{
+ struct rdxtree_node *node, *parent;
+ struct rdxtree_iter iter;
+
+ if (tree->height == 0) {
+ if (tree->root != NULL) {
+ llsync_store_ptr(tree->root, NULL);
+ }
+
+ return;
+ }
+
+ for (;;) {
+ rdxtree_iter_init(&iter);
+ rdxtree_walk_next(tree, &iter);
+
+ if (iter.node == NULL) {
+ break;
+ }
+
+ node = iter.node;
+ parent = node->parent;
+
+ if (parent == NULL) {
+ rdxtree_init(tree, tree->flags);
+ } else {
+ if (rdxtree_key_alloc_enabled(tree)) {
+ rdxtree_remove_bm_set(parent, node->index);
+ }
+
+ rdxtree_node_remove(parent, node->index);
+ rdxtree_cleanup(tree, parent);
+ node->parent = NULL;
+ }
+
+ rdxtree_node_schedule_destruction(node);
+ }
+}
diff --git a/src/rdxtree.h b/src/rdxtree.h
new file mode 100644
index 0000000..24e8c0a
--- /dev/null
+++ b/src/rdxtree.h
@@ -0,0 +1,224 @@
+/*
+ * Copyright (c) 2011-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Radix tree.
+ *
+ * In addition to the standard insertion operation, this implementation
+ * can allocate keys for the caller at insertion time.
+ */
+
+#ifndef _RDXTREE_H
+#define _RDXTREE_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+/*
+ * These macros can be replaced by actual functions in an environment
+ * that provides lockless synchronization such as RCU.
+ */
+#define llsync_store_ptr(ptr, value) ((ptr) = (value))
+#define llsync_load_ptr(ptr) (ptr)
+
+/*
+ * This macro selects between 32 or 64-bits (the default) keys.
+ */
+#if 0
+#define RDXTREE_KEY_32
+#endif
+
+#ifdef RDXTREE_KEY_32
+typedef uint32_t rdxtree_key_t;
+#else /* RDXTREE_KEY_32 */
+typedef uint64_t rdxtree_key_t;
+#endif /* RDXTREE_KEY_32 */
+
+/*
+ * Radix tree initialization flags.
+ */
+#define RDXTREE_KEY_ALLOC 0x1 /* Enable key allocation */
+
+/*
+ * Radix tree.
+ */
+struct rdxtree;
+
+/*
+ * Radix tree iterator.
+ */
+struct rdxtree_iter;
+
+/*
+ * Static tree initializer.
+ */
+#define RDXTREE_INITIALIZER { 0, NULL }
+
+#include "rdxtree_i.h"
+
+/*
+ * Initialize a tree.
+ */
+static inline void
+rdxtree_init(struct rdxtree *tree, unsigned short flags)
+{
+ assert((flags & ~RDXTREE_KEY_ALLOC) == 0);
+
+ tree->height = 0;
+ tree->flags = flags;
+ tree->root = NULL;
+}
+
+/*
+ * Insert a pointer in a tree.
+ *
+ * The ptr parameter must not be NULL.
+ */
+static inline int
+rdxtree_insert(struct rdxtree *tree, rdxtree_key_t key, void *ptr)
+{
+ return rdxtree_insert_common(tree, key, ptr, NULL);
+}
+
+/*
+ * Insert a pointer in a tree and obtain its slot.
+ *
+ * The ptr and slotp parameters must not be NULL. If successful, the slot of
+ * the newly inserted pointer is stored at the address pointed to by the slotp
+ * parameter.
+ */
+static inline int
+rdxtree_insert_slot(struct rdxtree *tree, rdxtree_key_t key,
+ void *ptr, void ***slotp)
+{
+ return rdxtree_insert_common(tree, key, ptr, slotp);
+}
+
+/*
+ * Insert a pointer in a tree, for which a new key is allocated.
+ *
+ * The ptr and keyp parameters must not be NULL. The newly allocated key is
+ * stored at the address pointed to by the keyp parameter.
+ */
+static inline int
+rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, rdxtree_key_t *keyp)
+{
+ return rdxtree_insert_alloc_common(tree, ptr, keyp, NULL);
+}
+
+/*
+ * Insert a pointer in a tree, for which a new key is allocated, and obtain
+ * its slot.
+ *
+ * The ptr, keyp and slotp parameters must not be NULL. The newly allocated
+ * key is stored at the address pointed to by the keyp parameter while the
+ * slot of the inserted pointer is stored at the address pointed to by the
+ * slotp parameter.
+ */
+static inline int
+rdxtree_insert_alloc_slot(struct rdxtree *tree, void *ptr,
+ rdxtree_key_t *keyp, void ***slotp)
+{
+ return rdxtree_insert_alloc_common(tree, ptr, keyp, slotp);
+}
+
+/*
+ * Remove a pointer from a tree.
+ *
+ * The matching pointer is returned if successful, NULL otherwise.
+ */
+void * rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key);
+
+/*
+ * Look up a pointer in a tree.
+ *
+ * The matching pointer is returned if successful, NULL otherwise.
+ */
+static inline void *
+rdxtree_lookup(const struct rdxtree *tree, rdxtree_key_t key)
+{
+ return rdxtree_lookup_common(tree, key, 0);
+}
+
+/*
+ * Look up a slot in a tree.
+ *
+ * A slot is a pointer to a stored pointer in a tree. It can be used as
+ * a placeholder for fast replacements to avoid multiple lookups on the same
+ * key.
+ *
+ * A slot for the matching pointer is returned if successful, NULL otherwise.
+ *
+ * See rdxtree_replace_slot().
+ */
+static inline void **
+rdxtree_lookup_slot(const struct rdxtree *tree, rdxtree_key_t key)
+{
+ return rdxtree_lookup_common(tree, key, 1);
+}
+
+static inline void *
+rdxtree_load_slot(void **slot)
+{
+ return llsync_load_ptr(*slot);
+}
+
+/*
+ * Replace a pointer in a tree.
+ *
+ * The ptr parameter must not be NULL. The previous pointer is returned.
+ *
+ * See rdxtree_lookup_slot().
+ */
+void * rdxtree_replace_slot(void **slot, void *ptr);
+
+/*
+ * Forge a loop to process all pointers of a tree.
+ *
+ * It is not safe to modify a tree from such a loop.
+ */
+#define rdxtree_for_each(tree, iter, ptr) \
+for (rdxtree_iter_init(iter), ptr = rdxtree_walk(tree, iter); \
+ ptr != NULL; \
+ ptr = rdxtree_walk(tree, iter))
+
+/*
+ * Return the key of the current pointer from an iterator.
+ */
+static inline rdxtree_key_t
+rdxtree_iter_key(const struct rdxtree_iter *iter)
+{
+ return iter->key;
+}
+
+/*
+ * Remove all pointers from a tree.
+ *
+ * The common way to destroy a tree and its pointers is to loop over all
+ * the pointers using rdxtree_for_each(), freeing them, then call this
+ * function.
+ */
+void rdxtree_remove_all(struct rdxtree *tree);
+
+#endif /* _RDXTREE_H */
diff --git a/src/rdxtree_i.h b/src/rdxtree_i.h
new file mode 100644
index 0000000..99b9f9c
--- /dev/null
+++ b/src/rdxtree_i.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright (c) 2011-2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#ifndef _RDXTREE_I_H
+#define _RDXTREE_I_H
+
+/*
+ * Radix tree.
+ */
+struct rdxtree {
+ unsigned short height;
+ unsigned short flags;
+ void *root;
+};
+
+/*
+ * Radix tree iterator.
+ *
+ * The node member refers to the node containing the current pointer, if any.
+ * The key member refers to the current pointer, and is valid if and only if
+ * rdxtree_walk() has been called at least once on the iterator.
+ */
+struct rdxtree_iter {
+ void *node;
+ rdxtree_key_t key;
+};
+
+/*
+ * Initialize an iterator.
+ */
+static inline void
+rdxtree_iter_init(struct rdxtree_iter *iter)
+{
+ iter->node = NULL;
+ iter->key = (rdxtree_key_t)-1;
+}
+
+int rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key,
+ void *ptr, void ***slotp);
+
+int rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr,
+ rdxtree_key_t *keyp, void ***slotp);
+
+void * rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key,
+ int get_slot);
+
+void * rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter);
+
+#endif /* _RDXTREE_I_H */
diff --git a/src/shell.c b/src/shell.c
new file mode 100644
index 0000000..f98baab
--- /dev/null
+++ b/src/shell.c
@@ -0,0 +1,1196 @@
+/*
+ * Copyright (c) 2015-2018 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ */
+
+#include <errno.h>
+#include <pthread.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "macros.h"
+#include "hash.h"
+#include "shell.h"
+
+/*
+ * Binary exponent and size of the hash table used to store commands.
+ */
+#define SHELL_HTABLE_BITS 6
+#define SHELL_HTABLE_SIZE (1 << SHELL_HTABLE_BITS)
+
+struct shell_bucket {
+ struct shell_cmd *cmd;
+};
+
+/*
+ * Hash table for quick command lookup.
+ */
+static struct shell_bucket shell_htable[SHELL_HTABLE_SIZE];
+
+#define SHELL_COMPLETION_MATCH_FMT "-16s"
+#define SHELL_COMPLETION_NR_MATCHES_PER_LINE 4
+
+/*
+ * Sorted command list.
+ */
+static struct shell_cmd *shell_list;
+
+/*
+ * Lock protecting access to the hash table and list of commands.
+ *
+ * Note that this lock only protects access to the commands containers,
+ * not the commands themselves. In particular, it is not necessary to
+ * hold this lock when a command is used, i.e. when accessing a command
+ * name, function pointer, or description.
+ */
+static pthread_mutex_t shell_lock;
+
+/*
+ * Escape sequence states.
+ *
+ * Here is an incomplete description of escape sequences :
+ * http://en.wikipedia.org/wiki/ANSI_escape_code
+ *
+ * These values must be different from 0.
+ */
+#define SHELL_ESC_STATE_START 1
+#define SHELL_ESC_STATE_CSI 2
+
+/*
+ * This value changes depending on the standard used and was chosen arbitrarily.
+ */
+#define SHELL_ESC_SEQ_MAX_SIZE 8
+
+typedef void (*shell_esc_seq_fn)(void);
+
+struct shell_esc_seq {
+ const char *str;
+ shell_esc_seq_fn fn;
+};
+
+#define SHELL_LINE_MAX_SIZE 64
+
+/*
+ * Line containing a shell entry.
+ *
+ * The string must be nul-terminated. The size doesn't include this
+ * additional nul character, the same way strlen() doesn't account for it.
+ */
+struct shell_line {
+ char str[SHELL_LINE_MAX_SIZE];
+ unsigned long size;
+};
+
+/*
+ * Number of entries in the history.
+ *
+ * One of these entryes is used as the current line.
+ */
+#define SHELL_HISTORY_SIZE 21
+
+#if SHELL_HISTORY_SIZE == 0
+#error "shell history size must be non-zero"
+#endif /* SHELL_HISTORY_SIZE == 0 */
+
+/*
+ * Shell history.
+ *
+ * The history is never empty. There is always at least one entry, the
+ * current line, referenced by the newest (most recent) index. The array
+ * is used like a circular buffer, i.e. old entries are implicitely
+ * erased by new ones. The index references the entry used as a template
+ * for the current line.
+ */
+static struct shell_line shell_history[SHELL_HISTORY_SIZE];
+static unsigned long shell_history_newest;
+static unsigned long shell_history_oldest;
+static unsigned long shell_history_index;
+
+/*
+ * Cursor within the current line.
+ */
+static unsigned long shell_cursor;
+
+#define SHELL_SEPARATOR ' '
+
+/*
+ * Commonly used backspace control characters.
+ *
+ * XXX Adjust for your needs.
+ */
+#define SHELL_ERASE_BS '\b'
+#define SHELL_ERASE_DEL '\x7f'
+
+/*
+ * Buffer used to store the current line during argument processing.
+ *
+ * The pointers in the argv array point inside this buffer. The
+ * separators immediately following the arguments are replaced with
+ * nul characters.
+ */
+static char shell_tmp_line[SHELL_LINE_MAX_SIZE];
+
+#define SHELL_MAX_ARGS 16
+
+static int shell_argc;
+static char *shell_argv[SHELL_MAX_ARGS];
+
+static const char *
+shell_find_word(const char *str)
+{
+ for (;;) {
+ if ((*str == '\0') || (*str != SHELL_SEPARATOR)) {
+ break;
+ }
+
+ str++;
+ }
+
+ return str;
+}
+
+void
+shell_cmd_init(struct shell_cmd *cmd, const char *name,
+ shell_fn_t fn, const char *usage,
+ const char *short_desc, const char *long_desc)
+{
+ cmd->ht_next = NULL;
+ cmd->ls_next = NULL;
+ cmd->name = name;
+ cmd->fn = fn;
+ cmd->usage = usage;
+ cmd->short_desc = short_desc;
+ cmd->long_desc = long_desc;
+}
+
+static const char *
+shell_cmd_name(const struct shell_cmd *cmd)
+{
+ return cmd->name;
+}
+
+static inline struct shell_bucket *
+shell_bucket_get(const char *name)
+{
+ return &shell_htable[hash_str(name, SHELL_HTABLE_BITS)];
+}
+
+static void
+shell_cmd_acquire(void)
+{
+ pthread_mutex_lock(&shell_lock);
+}
+
+static void
+shell_cmd_release(void)
+{
+ pthread_mutex_unlock(&shell_lock);
+}
+
+static const struct shell_cmd *
+shell_cmd_lookup(const char *name)
+{
+ const struct shell_bucket *bucket;
+ const struct shell_cmd *cmd;
+
+ shell_cmd_acquire();
+
+ bucket = shell_bucket_get(name);
+
+ for (cmd = bucket->cmd; cmd != NULL; cmd = cmd->ht_next) {
+ if (strcmp(cmd->name, name) == 0) {
+ break;
+ }
+ }
+
+ shell_cmd_release();
+
+ return cmd;
+}
+
+/*
+ * Look up the first command that matches a given string.
+ *
+ * The input string is defined by the given string pointer and size.
+ *
+ * The global lock must be acquired before calling this function.
+ */
+static const struct shell_cmd *
+shell_cmd_match(const struct shell_cmd *cmd, const char *str,
+ unsigned long size)
+{
+ while (cmd != NULL) {
+ if (strncmp(cmd->name, str, size) == 0) {
+ return cmd;
+ }
+
+ cmd = cmd->ls_next;
+ }
+
+ return NULL;
+}
+
+/*
+ * Attempt command auto-completion.
+ *
+ * The given string is the beginning of a command, or the empty string.
+ * The sizep parameter initially points to the size of the given string.
+ * If the string matches any registered command, the cmdp pointer is
+ * updated to point to the first matching command in the sorted list of
+ * commands, and sizep is updated to the number of characters in the
+ * command name that are common in subsequent commands. The command
+ * pointer and the returned size can be used to print a list of commands
+ * eligible for completion.
+ *
+ * If there is a single match for the given string, return 0. If there
+ * are more than one match, return EAGAIN. If there is no match,
+ * return EINVAL.
+ *
+ * The global lock must be acquired before calling this function.
+ */
+static int
+shell_cmd_complete(const char *str, unsigned long *sizep,
+ const struct shell_cmd **cmdp)
+{
+ const struct shell_cmd *cmd, *next;
+ unsigned long size;
+
+ size = *sizep;
+
+ /*
+ * Start with looking up a command that matches the given argument.
+ * If there is no match, return an error.
+ */
+ cmd = shell_cmd_match(shell_list, str, size);
+
+ if (cmd == NULL) {
+ return EINVAL;
+ }
+
+ *cmdp = cmd;
+
+ /*
+ * If at least one command matches, try to complete it.
+ * There can be two cases :
+ * 1/ There is one and only one match, which is directly returned.
+ * 2/ There are several matches, in which case the common length is
+ * computed.
+ */
+ next = cmd->ls_next;
+
+ if ((next == NULL)
+ || (strncmp(cmd->name, next->name, size) != 0)) {
+ *sizep = strlen(cmd->name);
+ return 0;
+ }
+
+ /*
+ * When computing the common length, all the commands that can match
+ * must be evaluated. Considering the current command is the first
+ * that can match, the only other variable missing is the last
+ * command that can match.
+ */
+ while (next->ls_next != NULL) {
+ if (strncmp(cmd->name, next->ls_next->name, size) != 0) {
+ break;
+ }
+
+ next = next->ls_next;
+ }
+
+ if (size == 0) {
+ size = 1;
+ }
+
+ while ((cmd->name[size - 1] != '\0')
+ && (cmd->name[size - 1] == next->name[size - 1])) {
+ size++;
+ }
+
+ size--;
+ *sizep = size;
+ return EAGAIN;
+}
+
+/*
+ * Print a list of commands eligible for completion, starting at the
+ * given command. Other eligible commands share the same prefix, as
+ * defined by the size argument.
+ *
+ * The global lock must be acquired before calling this function.
+ */
+static void
+shell_cmd_print_matches(const struct shell_cmd *cmd, unsigned long size)
+{
+ const struct shell_cmd *tmp;
+ unsigned int i;
+
+ printf("\n");
+
+ for (tmp = cmd, i = 1; tmp != NULL; tmp = tmp->ls_next, i++) {
+ if (strncmp(cmd->name, tmp->name, size) != 0) {
+ break;
+ }
+
+ printf("%" SHELL_COMPLETION_MATCH_FMT, tmp->name);
+
+ if ((i % SHELL_COMPLETION_NR_MATCHES_PER_LINE) == 0) {
+ printf("\n");
+ }
+ }
+
+ if ((i % SHELL_COMPLETION_NR_MATCHES_PER_LINE) != 1) {
+ printf("\n");
+ }
+}
+
+static int
+shell_cmd_check_char(char c)
+{
+ if (((c >= 'a') && (c <= 'z'))
+ || ((c >= 'A') && (c <= 'Z'))
+ || ((c >= '0') && (c <= '9'))
+ || (c == '-')
+ || (c == '_')) {
+ return 0;
+ }
+
+ return EINVAL;
+}
+
+static int
+shell_cmd_check(const struct shell_cmd *cmd)
+{
+ unsigned long i;
+ int error;
+
+ for (i = 0; cmd->name[i] != '\0'; i++) {
+ error = shell_cmd_check_char(cmd->name[i]);
+
+ if (error) {
+ return error;
+ }
+ }
+
+ if (i == 0) {
+ return EINVAL;
+ }
+
+ return 0;
+}
+
+/*
+ * The global lock must be acquired before calling this function.
+ */
+static void
+shell_cmd_add_list(struct shell_cmd *cmd)
+{
+ struct shell_cmd *prev, *next;
+
+ prev = shell_list;
+
+ if ((prev == NULL)
+ || (strcmp(cmd->name, prev->name) < 0)) {
+ shell_list = cmd;
+ cmd->ls_next = prev;
+ return;
+ }
+
+ for (;;) {
+ next = prev->ls_next;
+
+ if ((next == NULL)
+ || (strcmp(cmd->name, next->name) < 0)) {
+ break;
+ }
+
+ prev = next;
+ }
+
+ prev->ls_next = cmd;
+ cmd->ls_next = next;
+}
+
+/*
+ * The global lock must be acquired before calling this function.
+ */
+static int
+shell_cmd_add(struct shell_cmd *cmd)
+{
+ struct shell_bucket *bucket;
+ struct shell_cmd *tmp;
+
+ bucket = shell_bucket_get(cmd->name);
+ tmp = bucket->cmd;
+
+ if (tmp == NULL) {
+ bucket->cmd = cmd;
+ goto out;
+ }
+
+ for (;;) {
+ if (strcmp(cmd->name, tmp->name) == 0) {
+ fprintf(stderr, "shell: %s: shell command name collision",
+ cmd->name);
+ return EEXIST;
+ }
+
+ if (tmp->ht_next == NULL) {
+ break;
+ }
+
+ tmp = tmp->ht_next;
+ }
+
+ tmp->ht_next = cmd;
+
+out:
+ shell_cmd_add_list(cmd);
+ return 0;
+}
+
+int
+shell_cmd_register(struct shell_cmd *cmd)
+{
+ int error;
+
+ error = shell_cmd_check(cmd);
+
+ if (error) {
+ return error;
+ }
+
+ shell_cmd_acquire();
+ error = shell_cmd_add(cmd);
+ shell_cmd_release();
+
+ return error;
+}
+
+static inline const char *
+shell_line_str(const struct shell_line *line)
+{
+ return line->str;
+}
+
+static inline unsigned long
+shell_line_size(const struct shell_line *line)
+{
+ return line->size;
+}
+
+static inline void
+shell_line_reset(struct shell_line *line)
+{
+ line->str[0] = '\0';
+ line->size = 0;
+}
+
+static inline void
+shell_line_copy(struct shell_line *dest, const struct shell_line *src)
+{
+ strcpy(dest->str, src->str);
+ dest->size = src->size;
+}
+
+static inline int
+shell_line_cmp(const struct shell_line *a, const struct shell_line *b)
+{
+ return strcmp(a->str, b->str);
+}
+
+static int
+shell_line_insert(struct shell_line *line, unsigned long index, char c)
+{
+ unsigned long remaining_chars;
+
+ if (index > line->size) {
+ return EINVAL;
+ }
+
+ if ((line->size + 1) == sizeof(line->str)) {
+ return ENOMEM;
+ }
+
+ remaining_chars = line->size - index;
+
+ if (remaining_chars != 0) {
+ memmove(&line->str[index + 1], &line->str[index], remaining_chars);
+ }
+
+ line->str[index] = c;
+ line->size++;
+ line->str[line->size] = '\0';
+ return 0;
+}
+
+static int
+shell_line_erase(struct shell_line *line, unsigned long index)
+{
+ unsigned long remaining_chars;
+
+ if (index >= line->size) {
+ return EINVAL;
+ }
+
+ remaining_chars = line->size - index - 1;
+
+ if (remaining_chars != 0) {
+ memmove(&line->str[index], &line->str[index + 1], remaining_chars);
+ }
+
+ line->size--;
+ line->str[line->size] = '\0';
+ return 0;
+}
+
+static struct shell_line *
+shell_history_get(unsigned long index)
+{
+ return &shell_history[index % ARRAY_SIZE(shell_history)];
+}
+
+static struct shell_line *
+shell_history_get_newest(void)
+{
+ return shell_history_get(shell_history_newest);
+}
+
+static struct shell_line *
+shell_history_get_index(void)
+{
+ return shell_history_get(shell_history_index);
+}
+
+static void
+shell_history_reset_index(void)
+{
+ shell_history_index = shell_history_newest;
+}
+
+static inline int
+shell_history_same_newest(void)
+{
+ return (shell_history_newest != shell_history_oldest)
+ && shell_line_cmp(shell_history_get_newest(),
+ shell_history_get(shell_history_newest - 1)) == 0;
+}
+
+static void
+shell_history_push(void)
+{
+ if ((shell_line_size(shell_history_get_newest()) == 0)
+ || shell_history_same_newest()) {
+ shell_history_reset_index();
+ return;
+ }
+
+ shell_history_newest++;
+ shell_history_reset_index();
+
+ /* Mind integer overflows */
+ if ((shell_history_newest - shell_history_oldest)
+ >= ARRAY_SIZE(shell_history)) {
+ shell_history_oldest = shell_history_newest
+ - ARRAY_SIZE(shell_history) + 1;
+ }
+}
+
+static void
+shell_history_back(void)
+{
+ if (shell_history_index == shell_history_oldest) {
+ return;
+ }
+
+ shell_history_index--;
+ shell_line_copy(shell_history_get_newest(), shell_history_get_index());
+}
+
+static void
+shell_history_forward(void)
+{
+ if (shell_history_index == shell_history_newest) {
+ return;
+ }
+
+ shell_history_index++;
+
+ if (shell_history_index == shell_history_newest) {
+ shell_line_reset(shell_history_get_newest());
+ } else {
+ shell_line_copy(shell_history_get_newest(), shell_history_get_index());
+ }
+}
+
+static void
+shell_cmd_help(int argc, char *argv[])
+{
+ const struct shell_cmd *cmd;
+
+ if (argc > 2) {
+ argc = 2;
+ argv[1] = "help";
+ }
+
+ if (argc == 2) {
+ cmd = shell_cmd_lookup(argv[1]);
+
+ if (cmd == NULL) {
+ printf("shell: help: %s: command not found\n", argv[1]);
+ return;
+ }
+
+ printf("usage: %s\n%s\n", cmd->usage, cmd->short_desc);
+
+ if (cmd->long_desc != NULL) {
+ printf("\n%s\n", cmd->long_desc);
+ }
+
+ return;
+ }
+
+ shell_cmd_acquire();
+
+ for (cmd = shell_list; cmd != NULL; cmd = cmd->ls_next) {
+ printf("%13s %s\n", cmd->name, cmd->short_desc);
+ }
+
+ shell_cmd_release();
+}
+
+static void
+shell_cmd_history(int argc, char *argv[])
+{
+ unsigned long i;
+
+ (void)argc;
+ (void)argv;
+
+ /* Mind integer overflows */
+ for (i = shell_history_oldest; i != shell_history_newest; i++) {
+ printf("%6lu %s\n", i - shell_history_oldest,
+ shell_line_str(shell_history_get(i)));
+ }
+}
+
+static struct shell_cmd shell_default_cmds[] = {
+ SHELL_CMD_INITIALIZER("help", shell_cmd_help,
+ "help [command]",
+ "obtain help about shell commands"),
+ SHELL_CMD_INITIALIZER("history", shell_cmd_history,
+ "history",
+ "display history list"),
+};
+
+static void
+shell_prompt(void)
+{
+ printf("shell> ");
+}
+
+static void
+shell_reset(void)
+{
+ shell_line_reset(shell_history_get_newest());
+ shell_cursor = 0;
+ shell_prompt();
+}
+
+static void
+shell_erase(void)
+{
+ struct shell_line *current_line;
+ unsigned long remaining_chars;
+
+ current_line = shell_history_get_newest();
+ remaining_chars = shell_line_size(current_line);
+
+ while (shell_cursor != remaining_chars) {
+ putchar(' ');
+ shell_cursor++;
+ }
+
+ while (remaining_chars != 0) {
+ printf("\b \b");
+ remaining_chars--;
+ }
+
+ shell_cursor = 0;
+}
+
+static void
+shell_restore(void)
+{
+ struct shell_line *current_line;
+
+ current_line = shell_history_get_newest();
+ printf("%s", shell_line_str(current_line));
+ shell_cursor = shell_line_size(current_line);
+}
+
+static int
+shell_is_ctrl_char(char c)
+{
+ return ((c < ' ') || (c >= 0x7f));
+}
+
+static void
+shell_process_left(void)
+{
+ if (shell_cursor == 0) {
+ return;
+ }
+
+ shell_cursor--;
+ printf("\e[1D");
+}
+
+static int
+shell_process_right(void)
+{
+ if (shell_cursor >= shell_line_size(shell_history_get_newest())) {
+ return EAGAIN;
+ }
+
+ shell_cursor++;
+ printf("\e[1C");
+ return 0;
+}
+
+static void
+shell_process_up(void)
+{
+ shell_erase();
+ shell_history_back();
+ shell_restore();
+}
+
+static void
+shell_process_down(void)
+{
+ shell_erase();
+ shell_history_forward();
+ shell_restore();
+}
+
+static void
+shell_process_backspace(void)
+{
+ struct shell_line *current_line;
+ unsigned long remaining_chars;
+ int error;
+
+ current_line = shell_history_get_newest();
+ error = shell_line_erase(current_line, shell_cursor - 1);
+
+ if (error) {
+ return;
+ }
+
+ shell_cursor--;
+ printf("\b%s ", shell_line_str(current_line) + shell_cursor);
+ remaining_chars = shell_line_size(current_line) - shell_cursor + 1;
+
+ while (remaining_chars != 0) {
+ putchar('\b');
+ remaining_chars--;
+ }
+}
+
+static int
+shell_process_raw_char(char c)
+{
+ struct shell_line *current_line;
+ unsigned long remaining_chars;
+ int error;
+
+ current_line = shell_history_get_newest();
+ error = shell_line_insert(current_line, shell_cursor, c);
+
+ if (error) {
+ printf("\nshell: line too long\n");
+ return error;
+ }
+
+ shell_cursor++;
+
+ if (shell_cursor == shell_line_size(current_line)) {
+ putchar(c);
+ goto out;
+ }
+
+ /*
+ * This assumes that the backspace character only moves the cursor
+ * without erasing characters.
+ */
+ printf("%s", shell_line_str(current_line) + shell_cursor - 1);
+ remaining_chars = shell_line_size(current_line) - shell_cursor;
+
+ while (remaining_chars != 0) {
+ putchar('\b');
+ remaining_chars--;
+ }
+
+out:
+ return 0;
+}
+
+static int
+shell_process_tabulation(void)
+{
+ const struct shell_cmd *cmd = NULL; /* GCC */
+ const char *name, *str, *word;
+ unsigned long i, size, cmd_cursor;
+ int error;
+
+ shell_cmd_acquire();
+
+ str = shell_line_str(shell_history_get_newest());
+ word = shell_find_word(str);
+ size = shell_cursor - (word - str);
+ cmd_cursor = shell_cursor - size;
+
+ error = shell_cmd_complete(word, &size, &cmd);
+
+ if (error && (error != EAGAIN)) {
+ error = 0;
+ goto out;
+ }
+
+ if (error == EAGAIN) {
+ unsigned long cursor;
+
+ cursor = shell_cursor;
+ shell_cmd_print_matches(cmd, size);
+ shell_prompt();
+ shell_restore();
+
+ /* Keep existing arguments as they are */
+ while (shell_cursor != cursor) {
+ shell_process_left();
+ }
+ }
+
+ name = shell_cmd_name(cmd);
+
+ while (shell_cursor != cmd_cursor) {
+ shell_process_backspace();
+ }
+
+ for (i = 0; i < size; i++) {
+ error = shell_process_raw_char(name[i]);
+
+ if (error) {
+ goto out;
+ }
+ }
+
+ error = 0;
+
+out:
+ shell_cmd_release();
+ return error;
+}
+
+static void
+shell_esc_seq_up(void)
+{
+ shell_process_up();
+}
+
+static void
+shell_esc_seq_down(void)
+{
+ shell_process_down();
+}
+
+static void
+shell_esc_seq_next(void)
+{
+ shell_process_right();
+}
+
+static void
+shell_esc_seq_prev(void)
+{
+ shell_process_left();
+}
+
+static void
+shell_esc_seq_home(void)
+{
+ while (shell_cursor != 0) {
+ shell_process_left();
+ }
+}
+
+static void
+shell_esc_seq_del(void)
+{
+ int error;
+
+ error = shell_process_right();
+
+ if (error) {
+ return;
+ }
+
+ shell_process_backspace();
+}
+
+static void
+shell_esc_seq_end(void)
+{
+ unsigned long size;
+
+ size = shell_line_size(shell_history_get_newest());
+
+ while (shell_cursor < size) {
+ shell_process_right();
+ }
+}
+
+static const struct shell_esc_seq shell_esc_seqs[] = {
+ { "A", shell_esc_seq_up },
+ { "B", shell_esc_seq_down },
+ { "C", shell_esc_seq_next },
+ { "D", shell_esc_seq_prev },
+ { "H", shell_esc_seq_home },
+ { "1~", shell_esc_seq_home },
+ { "3~", shell_esc_seq_del },
+ { "F", shell_esc_seq_end },
+ { "4~", shell_esc_seq_end },
+};
+
+static const struct shell_esc_seq *
+shell_esc_seq_lookup(const char *str)
+{
+ unsigned long i;
+
+ for (i = 0; i < ARRAY_SIZE(shell_esc_seqs); i++) {
+ if (strcmp(shell_esc_seqs[i].str, str) == 0) {
+ return &shell_esc_seqs[i];
+ }
+ }
+
+ return NULL;
+}
+
+/*
+ * Process a single escape sequence character.
+ *
+ * Return the next escape state or 0 if the sequence is complete.
+ */
+static int
+shell_process_esc_sequence(char c)
+{
+ static char str[SHELL_ESC_SEQ_MAX_SIZE], *ptr = str;
+
+ const struct shell_esc_seq *seq;
+ uintptr_t index;
+
+ index = ptr - str;
+
+ if (index >= (ARRAY_SIZE(str) - 1)) {
+ printf("shell: escape sequence too long\n");
+ goto reset;
+ }
+
+ *ptr = c;
+ ptr++;
+ *ptr = '\0';
+
+ if ((c >= '@') && (c <= '~')) {
+ seq = shell_esc_seq_lookup(str);
+
+ if (seq != NULL) {
+ seq->fn();
+ }
+
+ goto reset;
+ }
+
+ return SHELL_ESC_STATE_CSI;
+
+reset:
+ ptr = str;
+ return 0;
+}
+
+static int
+shell_process_args(void)
+{
+ unsigned long i;
+ char c, prev;
+ int j;
+
+ snprintf(shell_tmp_line, sizeof(shell_tmp_line), "%s",
+ shell_line_str(shell_history_get_newest()));
+
+ for (i = 0, j = 0, prev = SHELL_SEPARATOR;
+ (c = shell_tmp_line[i]) != '\0';
+ i++, prev = c) {
+ if (c == SHELL_SEPARATOR) {
+ if (prev != SHELL_SEPARATOR) {
+ shell_tmp_line[i] = '\0';
+ }
+ } else {
+ if (prev == SHELL_SEPARATOR) {
+ shell_argv[j] = &shell_tmp_line[i];
+ j++;
+
+ if (j == ARRAY_SIZE(shell_argv)) {
+ printf("shell: too many arguments\n");
+ return EINVAL;
+ }
+
+ shell_argv[j] = NULL;
+ }
+ }
+ }
+
+ shell_argc = j;
+ return 0;
+}
+
+static void
+shell_process_line(void)
+{
+ const struct shell_cmd *cmd;
+ int error;
+
+ cmd = NULL;
+ error = shell_process_args();
+
+ if (error) {
+ goto out;
+ }
+
+ if (shell_argc == 0) {
+ goto out;
+ }
+
+ cmd = shell_cmd_lookup(shell_argv[0]);
+
+ if (cmd == NULL) {
+ printf("shell: %s: command not found\n", shell_argv[0]);
+ goto out;
+ }
+
+out:
+ shell_history_push();
+
+ if (cmd != NULL) {
+ cmd->fn(shell_argc, shell_argv);
+ }
+}
+
+/*
+ * Process a single control character.
+ *
+ * Return an error if the caller should reset the current line state.
+ */
+static int
+shell_process_ctrl_char(char c)
+{
+ switch (c) {
+ case SHELL_ERASE_BS:
+ case SHELL_ERASE_DEL:
+ shell_process_backspace();
+ break;
+ case '\t':
+ return shell_process_tabulation();
+ case '\n':
+ case '\r':
+ putchar('\n');
+ shell_process_line();
+ return EAGAIN;
+ default:
+ return 0;
+ }
+
+ return 0;
+}
+
+void
+shell_run(void)
+{
+ int c, error, escape;
+
+ for (;;) {
+ shell_reset();
+ escape = 0;
+
+ for (;;) {
+ c = getchar();
+
+ if (escape) {
+ switch (escape) {
+ case SHELL_ESC_STATE_START:
+ /* XXX CSI and SS3 sequence processing is the same */
+ if ((c == '[') || (c == 'O')) {
+ escape = SHELL_ESC_STATE_CSI;
+ } else {
+ escape = 0;
+ }
+
+ break;
+ case SHELL_ESC_STATE_CSI:
+ escape = shell_process_esc_sequence(c);
+ break;
+ default:
+ escape = 0;
+ }
+
+ error = 0;
+ } else if (shell_is_ctrl_char(c)) {
+ if (c == '\e') {
+ escape = SHELL_ESC_STATE_START;
+ error = 0;
+ } else {
+ error = shell_process_ctrl_char(c);
+
+ if (error) {
+ break;
+ }
+ }
+ } else {
+ error = shell_process_raw_char(c);
+ }
+
+ if (error) {
+ break;
+ }
+ }
+ }
+}
+
+void
+shell_setup(void)
+{
+ pthread_mutex_init(&shell_lock, NULL);
+ SHELL_REGISTER_CMDS(shell_default_cmds);
+}
diff --git a/src/shell.h b/src/shell.h
new file mode 100644
index 0000000..54a3b7a
--- /dev/null
+++ b/src/shell.h
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2015-2018 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Minimalist shell for embedded systems.
+ */
+
+#ifndef _SHELL_H
+#define _SHELL_H
+
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <macros.h>
+
+#define SHELL_REGISTER_CMDS(cmds) \
+MACRO_BEGIN \
+ size_t ___i; \
+ int ___error; \
+ \
+ for (___i = 0; ___i < ARRAY_SIZE(cmds); ___i++) { \
+ ___error = shell_cmd_register(&(cmds)[___i]); \
+ \
+ if (___error) { \
+ fprintf(stderr, "%s: %s\n", __func__, strerror(___error)); \
+ abort(); \
+ } \
+ } \
+MACRO_END
+
+typedef void (*shell_fn_t)(int argc, char *argv[]);
+
+struct shell_cmd {
+ struct shell_cmd *ht_next;
+ struct shell_cmd *ls_next;
+ const char *name;
+ shell_fn_t fn;
+ const char *usage;
+ const char *short_desc;
+ const char *long_desc;
+};
+
+/*
+ * Static shell command initializers.
+ */
+#define SHELL_CMD_INITIALIZER(name, fn, usage, short_desc) \
+ { NULL, NULL, name, fn, usage, short_desc, NULL }
+#define SHELL_CMD_INITIALIZER2(name, fn, usage, short_desc, long_desc) \
+ { NULL, NULL, name, fn, usage, short_desc, long_desc }
+
+/*
+ * Initialize a shell command structure.
+ */
+void shell_cmd_init(struct shell_cmd *cmd, const char *name,
+ shell_fn_t fn, const char *usage,
+ const char *short_desc, const char *long_desc);
+
+/*
+ * Initialize the shell module.
+ *
+ * On return, shell commands can be registered.
+ */
+void shell_setup(void);
+
+/*
+ * Register a shell command.
+ *
+ * The command name must be unique. It must not include characters outside
+ * the [a-zA-Z0-9-_] class.
+ *
+ * The structure passed when calling this function is directly reused by
+ * the shell module and must persist in memory.
+ */
+int shell_cmd_register(struct shell_cmd *cmd);
+
+/*
+ * Run the shell.
+ *
+ * This function doesn't return.
+ */
+void shell_run(void);
+
+#endif /* _SHELL_H */
diff --git a/src/slist.h b/src/slist.h
new file mode 100644
index 0000000..42fc54b
--- /dev/null
+++ b/src/slist.h
@@ -0,0 +1,468 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Upstream site with license notes :
+ * http://git.sceen.net/rbraun/librbraun.git/
+ *
+ *
+ * Singly-linked list.
+ */
+
+#ifndef _SLIST_H
+#define _SLIST_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "macros.h"
+
+/*
+ * List node.
+ */
+struct slist_node {
+ struct slist_node *next;
+};
+
+/*
+ * List head.
+ */
+struct slist {
+ struct slist_node *first;
+ struct slist_node *last;
+};
+
+/*
+ * Static list initializer.
+ */
+#define SLIST_INITIALIZER(list) { NULL, NULL }
+
+/*
+ * Initialize a list.
+ */
+static inline void
+slist_init(struct slist *list)
+{
+ list->first = NULL;
+ list->last = NULL;
+}
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct slist_node *
+slist_first(const struct slist *list)
+{
+ return list->first;
+}
+
+/*
+ * Return the last node of a list.
+ */
+static inline struct slist_node *
+slist_last(const struct slist *list)
+{
+ return list->last;
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct slist_node *
+slist_next(const struct slist_node *node)
+{
+ return node->next;
+}
+
+/*
+ * Return true if node is invalid and denotes one of the ends of the list.
+ */
+static inline bool
+slist_end(const struct slist_node *node)
+{
+ return node == NULL;
+}
+
+/*
+ * Return true if list is empty.
+ */
+static inline bool
+slist_empty(const struct slist *list)
+{
+ return list->first == NULL;
+}
+
+/*
+ * Return true if list contains exactly one node.
+ */
+static inline bool
+slist_singular(const struct slist *list)
+{
+ return !slist_empty(list) && (list->first == list->last);
+}
+
+/*
+ * Append the nodes of list2 at the end of list1.
+ *
+ * After completion, list2 is stale.
+ */
+static inline void
+slist_concat(struct slist *list1, const struct slist *list2)
+{
+ if (slist_empty(list2)) {
+ return;
+ }
+
+ if (slist_empty(list1)) {
+ list1->first = list2->first;
+ } else {
+ list1->last->next = list2->first;
+ }
+
+ list1->last = list2->last;
+}
+
+/*
+ * Set the new head of a list.
+ *
+ * This function is an optimized version of :
+ * list_init(&new_list);
+ * list_concat(&new_list, &old_list);
+ */
+static inline void
+slist_set_head(struct slist *new_head, const struct slist *old_head)
+{
+ *new_head = *old_head;
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+slist_insert_head(struct slist *list, struct slist_node *node)
+{
+ if (slist_empty(list)) {
+ list->last = node;
+ }
+
+ node->next = list->first;
+ list->first = node;
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+slist_insert_tail(struct slist *list, struct slist_node *node)
+{
+ node->next = NULL;
+
+ if (slist_empty(list)) {
+ list->first = node;
+ } else {
+ list->last->next = node;
+ }
+
+ list->last = node;
+}
+
+/*
+ * Insert a node after another node.
+ *
+ * The prev node must be valid.
+ */
+static inline void
+slist_insert_after(struct slist *list, struct slist_node *prev,
+ struct slist_node *node)
+{
+ node->next = prev->next;
+ prev->next = node;
+
+ if (list->last == prev) {
+ list->last = node;
+ }
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * The prev argument must point to the node immediately preceding the target
+ * node. It may safely denote the end of the given list, in which case the
+ * first node is removed.
+ */
+static inline void
+slist_remove(struct slist *list, struct slist_node *prev)
+{
+ struct slist_node *node;
+
+ if (slist_end(prev)) {
+ node = list->first;
+ list->first = node->next;
+
+ if (list->last == node) {
+ list->last = NULL;
+ }
+ } else {
+ node = prev->next;
+ prev->next = node->next;
+
+ if (list->last == node) {
+ list->last = prev;
+ }
+ }
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define slist_entry(node, type, member) structof(node, type, member)
+
+/*
+ * Get the first entry of a list.
+ */
+#define slist_first_entry(list, type, member) \
+MACRO_BEGIN \
+ struct slist_node *___first; \
+ \
+ ___first = (list)->first; \
+ slist_end(___first) ? NULL : slist_entry(___first, type, member); \
+MACRO_END
+
+/*
+ * Get the last entry of a list.
+ */
+#define slist_last_entry(list, type, member) \
+MACRO_BEGIN \
+ struct slist_node *___last; \
+ \
+ ___last = (list)->last; \
+ slist_end(___last) ? NULL : slist_entry(___last, type, member); \
+MACRO_END
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define slist_next_entry(entry, member) \
+MACRO_BEGIN \
+ struct slist_node *___next; \
+ \
+ ___next = (entry)->member.next; \
+ slist_end(___next) \
+ ? NULL \
+ : slist_entry(___next, typeof(*entry), member); \
+MACRO_END
+
+/*
+ * Forge a loop to process all nodes of a list.
+ *
+ * The node must not be altered during the loop.
+ */
+#define slist_for_each(list, node) \
+for (node = slist_first(list); \
+ !slist_end(node); \
+ node = slist_next(node))
+
+/*
+ * Forge a loop to process all nodes of a list.
+ */
+#define slist_for_each_safe(list, node, tmp) \
+for (node = slist_first(list), \
+ tmp = slist_end(node) ? NULL : slist_next(node); \
+ !slist_end(node); \
+ node = tmp, \
+ tmp = slist_end(node) ? NULL : slist_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ *
+ * The entry node must not be altered during the loop.
+ */
+#define slist_for_each_entry(list, entry, member) \
+for (entry = slist_first_entry(list, typeof(*entry), member); \
+ entry != NULL; \
+ entry = slist_next_entry(entry, member))
+
+/*
+ * Forge a loop to process all entries of a list.
+ */
+#define slist_for_each_entry_safe(list, entry, tmp, member) \
+for (entry = slist_first_entry(list, typeof(*entry), member), \
+ tmp = (entry == NULL) ? NULL : slist_next_entry(entry, member); \
+ entry != NULL; \
+ entry = tmp, \
+ tmp = (entry == NULL) ? NULL : slist_next_entry(entry, member)) \
+
+/*
+ * Lockless variants
+ *
+ * The slist_end() function may be used from read-side critical sections.
+ */
+
+/*
+ * These macros can be replaced by actual functions in an environment
+ * that provides lockless synchronization such as RCU.
+ */
+#define llsync_store_ptr(ptr, value) ((ptr) = (value))
+#define llsync_load_ptr(ptr) (ptr)
+
+/*
+ * Return the first node of a list.
+ */
+static inline struct slist_node *
+slist_llsync_first(const struct slist *list)
+{
+ return llsync_load_ptr(list->first);
+}
+
+/*
+ * Return the node next to the given node.
+ */
+static inline struct slist_node *
+slist_llsync_next(const struct slist_node *node)
+{
+ return llsync_load_ptr(node->next);
+}
+
+/*
+ * Insert a node at the head of a list.
+ */
+static inline void
+slist_llsync_insert_head(struct slist *list, struct slist_node *node)
+{
+ if (slist_empty(list)) {
+ list->last = node;
+ }
+
+ node->next = list->first;
+ llsync_store_ptr(list->first, node);
+}
+
+/*
+ * Insert a node at the tail of a list.
+ */
+static inline void
+slist_llsync_insert_tail(struct slist *list, struct slist_node *node)
+{
+ node->next = NULL;
+
+ if (slist_empty(list)) {
+ llsync_store_ptr(list->first, node);
+ } else {
+ llsync_store_ptr(list->last->next, node);
+ }
+
+ list->last = node;
+}
+
+/*
+ * Insert a node after another node.
+ *
+ * The prev node must be valid.
+ */
+static inline void
+slist_llsync_insert_after(struct slist *list, struct slist_node *prev,
+ struct slist_node *node)
+{
+ node->next = prev->next;
+ llsync_store_ptr(prev->next, node);
+
+ if (list->last == prev) {
+ list->last = node;
+ }
+}
+
+/*
+ * Remove a node from a list.
+ *
+ * The prev argument must point to the node immediately preceding the target
+ * node. It may safely denote the end of the given list, in which case the
+ * first node is removed.
+ */
+static inline void
+slist_llsync_remove(struct slist *list, struct slist_node *prev)
+{
+ struct slist_node *node;
+
+ if (slist_end(prev)) {
+ node = list->first;
+ llsync_store_ptr(list->first, node->next);
+
+ if (list->last == node) {
+ list->last = NULL;
+ }
+ } else {
+ node = prev->next;
+ llsync_store_ptr(prev->next, node->next);
+
+ if (list->last == node) {
+ list->last = prev;
+ }
+ }
+}
+
+/*
+ * Macro that evaluates to the address of the structure containing the
+ * given node based on the given type and member.
+ */
+#define slist_llsync_entry(node, type, member) \
+ structof(llsync_load_ptr(node), type, member)
+
+/*
+ * Get the first entry of a list.
+ */
+#define slist_llsync_first_entry(list, type, member) \
+MACRO_BEGIN \
+ struct slist_node *___first; \
+ \
+ ___first = slist_llsync_first(list); \
+ slist_end(___first) ? NULL : slist_entry(___first, type, member); \
+MACRO_END
+
+/*
+ * Get the entry next to the given entry.
+ */
+#define slist_llsync_next_entry(entry, member) \
+MACRO_BEGIN \
+ struct slist_node *___next; \
+ \
+ ___next = slist_llsync_next(&entry->member); \
+ slist_end(___next) \
+ ? NULL \
+ : slist_entry(___next, typeof(*entry), member); \
+MACRO_END
+
+/*
+ * Forge a loop to process all nodes of a list.
+ */
+#define slist_llsync_for_each(list, node) \
+for (node = slist_llsync_first(list); \
+ !slist_end(node); \
+ node = slist_llsync_next(node))
+
+/*
+ * Forge a loop to process all entries of a list.
+ */
+#define slist_llsync_for_each_entry(list, entry, member) \
+for (entry = slist_llsync_first_entry(list, typeof(*entry), member); \
+ entry != NULL; \
+ entry = slist_llsync_next_entry(entry, member))
+
+#endif /* _SLIST_H */