diff options
author | Richard Braun <rbraun@sceen.net> | 2018-01-04 21:50:05 +0100 |
---|---|---|
committer | Richard Braun <rbraun@sceen.net> | 2018-01-04 21:50:05 +0100 |
commit | b03224b9a82a4d46fd1e469821975f9a5295ed40 (patch) | |
tree | 7830e5dc6316f4d29abb3c27c8a7ef77684446df /src | |
parent | e7321910ca4d956b572a050d302a25df37ce06ab (diff) |
Move sources to new src/ directory
Diffstat (limited to 'src')
-rw-r--r-- | src/avltree.c | 601 | ||||
-rw-r--r-- | src/avltree.h | 329 | ||||
-rw-r--r-- | src/avltree_i.h | 203 | ||||
-rw-r--r-- | src/bitmap.c | 124 | ||||
-rw-r--r-- | src/bitmap.h | 214 | ||||
-rw-r--r-- | src/bitmap_i.h | 69 | ||||
-rw-r--r-- | src/cbuf.c | 202 | ||||
-rw-r--r-- | src/cbuf.h | 150 | ||||
-rw-r--r-- | src/check.h | 47 | ||||
-rw-r--r-- | src/cpu.h | 84 | ||||
-rw-r--r-- | src/fmt.c | 1462 | ||||
-rw-r--r-- | src/fmt.h | 69 | ||||
-rw-r--r-- | src/hash.h | 124 | ||||
-rw-r--r-- | src/hlist.h | 418 | ||||
-rw-r--r-- | src/list.c | 141 | ||||
-rw-r--r-- | src/list.h | 555 | ||||
-rw-r--r-- | src/macros.h | 90 | ||||
-rw-r--r-- | src/plist.c | 73 | ||||
-rw-r--r-- | src/plist.h | 296 | ||||
-rw-r--r-- | src/rbtree.c | 558 | ||||
-rw-r--r-- | src/rbtree.h | 328 | ||||
-rw-r--r-- | src/rbtree_i.h | 197 | ||||
-rw-r--r-- | src/rdxtree.c | 863 | ||||
-rw-r--r-- | src/rdxtree.h | 224 | ||||
-rw-r--r-- | src/rdxtree_i.h | 71 | ||||
-rw-r--r-- | src/shell.c | 1196 | ||||
-rw-r--r-- | src/shell.h | 106 | ||||
-rw-r--r-- | src/slist.h | 468 |
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 */ |