From 82ce342055ec8f7a0235d46f5332014eb3f69216 Mon Sep 17 00:00:00 2001 From: Felix Fietkau Date: Tue, 28 Dec 2010 23:59:06 +0100 Subject: [PATCH] merge an avl list implementation (imported from PacketBB) --- Makefile | 2 +- avl.c | 760 ++++++++++++++++++++++++++++++++++++++++++++++++++ avl.h | 525 ++++++++++++++++++++++++++++++++++ list.h | 11 + list_compat.h | 15 + 5 files changed, 1312 insertions(+), 1 deletion(-) create mode 100644 avl.c create mode 100644 avl.h create mode 100644 list_compat.h diff --git a/Makefile b/Makefile index ba25d1b..996d6a6 100644 --- a/Makefile +++ b/Makefile @@ -9,7 +9,7 @@ LIBDIR=$(PREFIX)/lib CPPFLAGS= OS=$(shell uname) -FILES=blob.c blobmsg.c hash.c uhtbl.c usock.c uloop.c +FILES=blob.c blobmsg.c hash.c uhtbl.c usock.c uloop.c avl.c ifeq ($(OS),Linux) FILES += unl.c LIBS += $(LIBNL) diff --git a/avl.c b/avl.c new file mode 100644 index 0000000..bde40b7 --- /dev/null +++ b/avl.c @@ -0,0 +1,760 @@ +/* + * PacketBB handler library (see RFC 5444) + * Copyright (c) 2010 Henning Rogge + * Original OLSRd implementation by Hannes Gredler + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of olsr.org, olsrd nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + * Visit http://www.olsr.org/git for more information. + * + * If you find this software useful feel free to make a donation + * to the project. For more information see the website or contact + * the copyright holders. + */ + +#include +#include +#include +#include +#include + +#include "avl.h" +#include "list.h" + +#define list_merge(_head, _list) list_merge(_list, _head) +#define list_is_last(_head, _list) list_is_last(_list, _head) +#define list_is_first(_head, _list) list_is_first(_list, _head) + +/** + * internal type save inline function to calculate the maximum of + * to integers without macro implementation. + * + * @param x first parameter of maximum function + * @param y second parameter of maximum function + * @return largest integer of both parameters + */ +static inline int avl_max(int x, int y) { + return x > y ? x : y; +} + +/** + * internal type save inline function to calculate the minimum of + * to integers without macro implementation. + * + * @param x first parameter of minimum function + * @param y second parameter of minimum function + * @return smallest integer of both parameters + */ +static inline int avl_min(int x, int y) { + return x < y ? x : y; +} + +static struct avl_node * +avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result); +static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node); +static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node); +static void post_insert(struct avl_tree *tree, struct avl_node *node); +static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node); +static void avl_remove(struct avl_tree *tree, struct avl_node *node); + +/** + * Initialize a new avl_tree struct + * @param tree pointer to avl-tree + * @param comp pointer to comparator for the tree + * @param allow_dups true if the tree allows multiple + * elements with the same + * @param ptr custom parameter for comparator + */ +void +avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr) +{ + list_init_head(&tree->list_head); + tree->root = NULL; + tree->count = 0; + tree->comp = comp; + tree->allow_dups = allow_dups; + tree->cmp_ptr = ptr; +} + +/** + * Internal function to support returning the element from a avl tree query + * @param tree pointer to avl tree + * @param key pointer to key + * @param offset offset of node inside the embedded struct + * @param mode mode of lookup operation (less equal, equal or greater equal) + * @param pointer to elemen, NULL if no fitting one was found + */ +void * +__avl_find_element(struct avl_tree *tree, const void *key, size_t offset, enum avl_find_mode mode) { + void *node = NULL; + + switch (mode) { + case AVL_FIND_EQUAL: + node = avl_find(tree, key); + break; + case AVL_FIND_LESSEQUAL: + node = avl_find_lessequal(tree, key); + break; + case AVL_FIND_GREATEREQUAL: + node = avl_find_greaterequal(tree, key); + break; + } + return node == NULL ? NULL : (((char *)node) - offset); +} + +/** + * Finds a node in an avl-tree with a certain key + * @param tree pointer to avl-tree + * @param key pointer to key + * @return pointer to avl-node with key, NULL if no node with + * this key exists. + */ +struct avl_node * +avl_find(struct avl_tree *tree, const void *key) +{ + struct avl_node *node; + int diff; + + if (tree->root == NULL) + return NULL; + + node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff); + + return diff == 0 ? node : NULL; +} + +/** + * Finds the last node in an avl-tree with a key less or equal + * than the specified key + * @param tree pointer to avl-tree + * @param key pointer to specified key + * @return pointer to avl-node, NULL if no node with + * key less or equal specified key exists. + */ +struct avl_node * +avl_find_lessequal(struct avl_tree *tree, const void *key) { + struct avl_node *node, *next; + int diff; + + if (tree->root == NULL) + return NULL; + + node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff); + + /* go left as long as keylist_head, &node->list)) { + return NULL; + } + + node = (struct avl_node *)node->list.prev; + diff = (*tree->comp) (key, node->key, tree->cmp_ptr); + } + + /* go right as long as key>=next_node.key */ + next = node; + while (diff >= 0) { + node = next; + if (list_is_last(&tree->list_head, &node->list)) { + break; + } + + next = (struct avl_node *)node->list.next; + diff = (*tree->comp) (key, next->key, tree->cmp_ptr); + } + return node; +} + +/** + * Finds the first node in an avl-tree with a key greater or equal + * than the specified key + * @param tree pointer to avl-tree + * @param key pointer to specified key + * @return pointer to avl-node, NULL if no node with + * key greater or equal specified key exists. + */ +struct avl_node * +avl_find_greaterequal(struct avl_tree *tree, const void *key) { + struct avl_node *node, *next; + int diff; + + if (tree->root == NULL) + return NULL; + + node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff); + + /* go right as long as key>node.key */ + while (diff > 0) { + if (list_is_last(&tree->list_head, &node->list)) { + return NULL; + } + + node = (struct avl_node *)node->list.next; + diff = (*tree->comp) (key, node->key, tree->cmp_ptr); + } + + /* go left as long as key<=next_node.key */ + next = node; + while (diff <= 0) { + node = next; + if (list_is_first(&tree->list_head, &node->list)) { + break; + } + + next = (struct avl_node *)node->list.prev; + diff = (*tree->comp) (key, next->key, tree->cmp_ptr); + } + return node; +} + +/** + * Inserts an avl_node into a tree + * @param tree pointer to tree + * @param new pointer to node + * @return 0 if node was inserted successfully, -1 if it was not inserted + * because of a key collision + */ +int +avl_insert(struct avl_tree *tree, struct avl_node *new) +{ + struct avl_node *node, *next, *last; + int diff; + + new->parent = NULL; + + new->left = NULL; + new->right = NULL; + + new->balance = 0; + new->leader = true; + + if (tree->root == NULL) { + list_add_head(&tree->list_head, &new->list); + tree->root = new; + tree->count = 1; + return 0; + } + + node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff); + + last = node; + + while (!list_is_last(&tree->list_head, &last->list)) { + next = list_next_element(last, list); + if (next->leader) { + break; + } + last = next; + } + + diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr); + + if (diff == 0) { + if (!tree->allow_dups) + return -1; + + new->leader = 0; + + avl_insert_after(tree, last, new); + return 0; + } + + if (node->balance == 1) { + avl_insert_before(tree, node, new); + + node->balance = 0; + new->parent = node; + node->left = new; + return 0; + } + + if (node->balance == -1) { + avl_insert_after(tree, last, new); + + node->balance = 0; + new->parent = node; + node->right = new; + return 0; + } + + if (diff < 0) { + avl_insert_before(tree, node, new); + + node->balance = -1; + new->parent = node; + node->left = new; + post_insert(tree, node); + return 0; + } + + avl_insert_after(tree, last, new); + + node->balance = 1; + new->parent = node; + node->right = new; + post_insert(tree, node); + return 0; +} + +/** + * Remove a node from an avl tree + * @param tree pointer to tree + * @param node pointer to node + */ +void +avl_delete(struct avl_tree *tree, struct avl_node *node) +{ + struct avl_node *next; + struct avl_node *parent; + struct avl_node *left; + struct avl_node *right; + if (node->leader) { + if (tree->allow_dups + && !list_is_last(&tree->list_head, &node->list) + && !(next = list_next_element(node, list))->leader) { + next->leader = true; + next->balance = node->balance; + + parent = node->parent; + left = node->left; + right = node->right; + + next->parent = parent; + next->left = left; + next->right = right; + + if (parent == NULL) + tree->root = next; + + else { + if (node == parent->left) + parent->left = next; + + else + parent->right = next; + } + + if (left != NULL) + left->parent = next; + + if (right != NULL) + right->parent = next; + } + + else + avl_delete_worker(tree, node); + } + + avl_remove(tree, node); +} + +static struct avl_node * +avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result) +{ + int diff; + + diff = (*comp) (key, node->key, cmp_ptr); + *cmp_result = diff; + + if (diff < 0) { + if (node->left != NULL) + return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result); + + return node; + } + + if (diff > 0) { + if (node->right != NULL) + return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result); + + return node; + } + + return node; +} + +static void +avl_rotate_right(struct avl_tree *tree, struct avl_node *node) +{ + struct avl_node *left, *parent; + + left = node->left; + parent = node->parent; + + left->parent = parent; + node->parent = left; + + if (parent == NULL) + tree->root = left; + + else { + if (parent->left == node) + parent->left = left; + + else + parent->right = left; + } + + node->left = left->right; + left->right = node; + + if (node->left != NULL) + node->left->parent = node; + + node->balance += 1 - avl_min(left->balance, 0); + left->balance += 1 + avl_max(node->balance, 0); +} + +static void +avl_rotate_left(struct avl_tree *tree, struct avl_node *node) +{ + struct avl_node *right, *parent; + + right = node->right; + parent = node->parent; + + right->parent = parent; + node->parent = right; + + if (parent == NULL) + tree->root = right; + + else { + if (parent->left == node) + parent->left = right; + + else + parent->right = right; + } + + node->right = right->left; + right->left = node; + + if (node->right != NULL) + node->right->parent = node; + + node->balance -= 1 + avl_max(right->balance, 0); + right->balance -= 1 - avl_min(node->balance, 0); +} + +static void +post_insert(struct avl_tree *tree, struct avl_node *node) +{ + struct avl_node *parent = node->parent; + + if (parent == NULL) + return; + + if (node == parent->left) { + parent->balance--; + + if (parent->balance == 0) + return; + + if (parent->balance == -1) { + post_insert(tree, parent); + return; + } + + if (node->balance == -1) { + avl_rotate_right(tree, parent); + return; + } + + avl_rotate_left(tree, node); + avl_rotate_right(tree, node->parent->parent); + return; + } + + parent->balance++; + + if (parent->balance == 0) + return; + + if (parent->balance == 1) { + post_insert(tree, parent); + return; + } + + if (node->balance == 1) { + avl_rotate_left(tree, parent); + return; + } + + avl_rotate_right(tree, node); + avl_rotate_left(tree, node->parent->parent); +} + +static void +avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node) +{ + list_add_before(&pos_node->list, &node->list); + tree->count++; +} + +static void +avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node) +{ + list_add_after(&pos_node->list, &node->list); + tree->count++; +} + +static void +avl_remove(struct avl_tree *tree, struct avl_node *node) +{ + list_remove(&node->list); + tree->count--; +} + +static void +avl_post_delete(struct avl_tree *tree, struct avl_node *node) +{ + struct avl_node *parent; + + if ((parent = node->parent) == NULL) + return; + + if (node == parent->left) { + parent->balance++; + + if (parent->balance == 0) { + avl_post_delete(tree, parent); + return; + } + + if (parent->balance == 1) + return; + + if (parent->right->balance == 0) { + avl_rotate_left(tree, parent); + return; + } + + if (parent->right->balance == 1) { + avl_rotate_left(tree, parent); + avl_post_delete(tree, parent->parent); + return; + } + + avl_rotate_right(tree, parent->right); + avl_rotate_left(tree, parent); + avl_post_delete(tree, parent->parent); + return; + } + + parent->balance--; + + if (parent->balance == 0) { + avl_post_delete(tree, parent); + return; + } + + if (parent->balance == -1) + return; + + if (parent->left->balance == 0) { + avl_rotate_right(tree, parent); + return; + } + + if (parent->left->balance == -1) { + avl_rotate_right(tree, parent); + avl_post_delete(tree, parent->parent); + return; + } + + avl_rotate_left(tree, parent->left); + avl_rotate_right(tree, parent); + avl_post_delete(tree, parent->parent); +} + +static struct avl_node * +avl_local_min(struct avl_node *node) +{ + while (node->left != NULL) + node = node->left; + + return node; +} + +#if 0 +static struct avl_node * +avl_local_max(struct avl_node *node) +{ + while (node->right != NULL) + node = node->right; + + return node; +} +#endif + +static void +avl_delete_worker(struct avl_tree *tree, struct avl_node *node) +{ + struct avl_node *parent, *min; + + parent = node->parent; + + if (node->left == NULL && node->right == NULL) { + if (parent == NULL) { + tree->root = NULL; + return; + } + + if (parent->left == node) { + parent->left = NULL; + parent->balance++; + + if (parent->balance == 1) + return; + + if (parent->balance == 0) { + avl_post_delete(tree, parent); + return; + } + + if (parent->right->balance == 0) { + avl_rotate_left(tree, parent); + return; + } + + if (parent->right->balance == 1) { + avl_rotate_left(tree, parent); + avl_post_delete(tree, parent->parent); + return; + } + + avl_rotate_right(tree, parent->right); + avl_rotate_left(tree, parent); + avl_post_delete(tree, parent->parent); + return; + } + + if (parent->right == node) { + parent->right = NULL; + parent->balance--; + + if (parent->balance == -1) + return; + + if (parent->balance == 0) { + avl_post_delete(tree, parent); + return; + } + + if (parent->left->balance == 0) { + avl_rotate_right(tree, parent); + return; + } + + if (parent->left->balance == -1) { + avl_rotate_right(tree, parent); + avl_post_delete(tree, parent->parent); + return; + } + + avl_rotate_left(tree, parent->left); + avl_rotate_right(tree, parent); + avl_post_delete(tree, parent->parent); + return; + } + } + + if (node->left == NULL) { + if (parent == NULL) { + tree->root = node->right; + node->right->parent = NULL; + return; + } + + node->right->parent = parent; + + if (parent->left == node) + parent->left = node->right; + + else + parent->right = node->right; + + avl_post_delete(tree, node->right); + return; + } + + if (node->right == NULL) { + if (parent == NULL) { + tree->root = node->left; + node->left->parent = NULL; + return; + } + + node->left->parent = parent; + + if (parent->left == node) + parent->left = node->left; + + else + parent->right = node->left; + + avl_post_delete(tree, node->left); + return; + } + + min = avl_local_min(node->right); + avl_delete_worker(tree, min); + parent = node->parent; + + min->balance = node->balance; + min->parent = parent; + min->left = node->left; + min->right = node->right; + + if (min->left != NULL) + min->left->parent = min; + + if (min->right != NULL) + min->right->parent = min; + + if (parent == NULL) { + tree->root = min; + return; + } + + if (parent->left == node) { + parent->left = min; + return; + } + + parent->right = min; +} + +/* + * Local Variables: + * c-basic-offset: 2 + * indent-tabs-mode: nil + * End: + */ diff --git a/avl.h b/avl.h new file mode 100644 index 0000000..1c57604 --- /dev/null +++ b/avl.h @@ -0,0 +1,525 @@ +/* + * PacketBB handler library (see RFC 5444) + * Copyright (c) 2010 Henning Rogge + * Original OLSRd implementation by Hannes Gredler + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of olsr.org, olsrd nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + * Visit http://www.olsr.org/git for more information. + * + * If you find this software useful feel free to make a donation + * to the project. For more information see the website or contact + * the copyright holders. + */ + +#ifndef _AVL_H +#define _AVL_H + +#include +#include + +#include "list.h" +#include "list_compat.h" + +/* Support for OLSR.org linker symbol export */ +#define EXPORT(sym) sym + +/** + * This element is a member of a avl-tree. It must be contained in all + * larger structs that should be put into a tree. + */ +struct avl_node { + /** + * Linked list node for supporting easy iteration and multiple + * elments with the same key. + * + * this must be the first element of an avl_node to + * make casting for lists easier + */ + struct list_entity list; + + /** + * Pointer to parent node in tree, NULL if root node + */ + struct avl_node *parent; + + /** + * Pointer to left child + */ + struct avl_node *left; + + /** + * Pointer to right child + */ + struct avl_node *right; + + /** + * pointer to key of node + */ + void *key; + + /** + * balance state of AVL tree (0,-1,+1) + */ + signed char balance; + + /** + * true if first of a series of nodes with same key + */ + bool leader; +}; + +/** + * Prototype for avl comparators + * @param k1 first key + * @param k2 second key + * @param ptr custom data for tree comparator + * @return +1 if k1>k2, -1 if k1list_head.next == &node->list; +} + +/** + * @param tree pointer to avl-tree + * @param node pointer to node of the tree + * @return true if node is the last one of the tree, false otherwise + */ +static inline bool +avl_is_last(struct avl_tree *tree, struct avl_node *node) { + return tree->list_head.prev == &node->list; +} + +/** + * @param tree pointer to avl-tree + * @return true if the tree is empty, false otherwise + */ +static inline bool +avl_is_empty(struct avl_tree *tree) { + return tree->count == 0; +} + +/** + * @param tree pointer to avl-tree + * @param key pointer to key + * @param element pointer to a node element + * (don't need to be initialized) + * @param node_element name of the avl_node element inside the + * larger struct + * @return pointer to tree element with the specified key, + * NULL if no element was found + */ +#define avl_find_element(tree, key, element, node_element) \ + ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL)) + +/** + * @param tree pointer to avl-tree + * @param key pointer to specified key + * @param element pointer to a node element + * (don't need to be initialized) + * @param node_element name of the avl_node element inside the + * larger struct + * return pointer to last tree element with less or equal key than specified key, + * NULL if no element was found + */ +#define avl_find_le_element(tree, key, element, node_element) \ + ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL)) + +/** + * @param tree pointer to avl-tree + * @param key pointer to specified key + * @param element pointer to a node element + * (don't need to be initialized) + * @param node_element name of the avl_node element inside the + * larger struct + * return pointer to first tree element with greater or equal key than specified key, + * NULL if no element was found + */ +#define avl_find_ge_element(tree, key, element, node_element) \ + ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL)) + +/** + * This function must not be called for an empty tree + * + * @param tree pointer to avl-tree + * @param element pointer to a node element + * (don't need to be initialized) + * @param node_member name of the avl_node element inside the + * larger struct + * @return pointer to the first element of the avl_tree + * (automatically converted to type 'element') + */ +#define avl_first_element(tree, element, node_member) \ + container_of((tree)->list_head.next, typeof(*(element)), node_member) + +/** + * @param tree pointer to tree + * @param element pointer to a node struct that contains the avl_node + * (don't need to be initialized) + * @param node_member name of the avl_node element inside the + * larger struct + * @return pointer to the last element of the avl_tree + * (automatically converted to type 'element') + */ +#define avl_last_element(tree, element, node_member) \ + container_of((tree)->list_head.prev, typeof(*(element)), node_member) + +/** + * This function must not be called for the last element of + * an avl tree + * + * @param element pointer to a node of the tree + * @param node_member name of the avl_node element inside the + * larger struct + * @return pointer to the node after 'element' + * (automatically converted to type 'element') + */ +#define avl_next_element(element, node_member) \ + container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member) + +/** + * This function must not be called for the first element of + * an avl tree + * + * @param element pointer to a node of the tree + * @param node_member name of the avl_node element inside the + * larger struct + * @return pointer to the node before 'element' + * (automatically converted to type 'element') + */ +#define avl_prev_element(element, node_member) \ + container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member) + +/** + * Loop over a block of elements of a tree, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * + * @param first pointer to first element of loop + * @param last pointer to last element of loop + * @param element pointer to a node of the tree, this element will + * contain the current node of the list during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_element_range(first, last, element, node_member) \ + for (element = (first); \ + element->node_member.list.prev != &(last)->node_member.list; \ + element = avl_next_element(element, node_member)) + +/** + * Loop over a block of elements of a tree backwards, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * + * @param first pointer to first element of loop + * @param last pointer to last element of loop + * @param element pointer to a node of the tree, this element will + * contain the current node of the list during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_element_range_reverse(first, last, element, node_member) \ + for (element = (last); \ + element->node_member.list.next != &(first)->node_member.list; \ + element = avl_prev_element(element, node_member)) + +/** + * Loop over all elements of an avl_tree, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * + * @param tree pointer to avl-tree + * @param element pointer to a node of the tree, this element will + * contain the current node of the tree during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_each_element(tree, element, node_member) \ + avl_for_element_range(avl_first_element(tree, element, node_member), \ + avl_last_element(tree, element, node_member), \ + element, node_member) + +/** + * Loop over all elements of an avl_tree backwards, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * + * @param tree pointer to avl-tree + * @param element pointer to a node of the tree, this element will + * contain the current node of the tree during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_each_element_reverse(tree, element, node_member) \ + avl_for_element_range_reverse(avl_first_element(tree, element, node_member), \ + avl_last_element(tree, element, node_member), \ + element, node_member) + +/** + * Loop over a block of elements of a tree, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * The loop runs from the element 'first' to the end of the tree. + * + * @param tree pointer to avl-tree + * @param first pointer to first element of loop + * @param element pointer to a node of the tree, this element will + * contain the current node of the list during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_element_to_last(tree, first, element, node_member) \ + avl_for_element_range(first, avl_last_element(tree, element, node_member), element, node_member) + + +/** + * Loop over a block of elements of a tree backwards, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * The loop runs from the element 'first' to the end of the tree. + * + * @param tree pointer to avl-tree + * @param first pointer to first element of loop + * @param element pointer to a node of the tree, this element will + * contain the current node of the list during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_element_to_last_reverse(tree, first, element, node_member) \ + avl_for_element_range_reverse(first, avl_last_element(tree, element, node_member), element, node_member) + +/** + * Loop over a block of elements of a tree, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * The loop runs from the start of the tree to the element 'last'. + * + * @param tree pointer to avl-tree + * @param last pointer to last element of loop + * @param element pointer to a node of the tree, this element will + * contain the current node of the list during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_first_to_element(tree, last, element, node_member) \ + avl_for_element_range(avl_first_element(tree, element, node_member), last, element, node_member) + + +/** + * Loop over a block of elements of a tree backwards, used similar to a for() command. + * This loop should not be used if elements are removed from the tree during + * the loop. + * The loop runs from the start of the tree to the element 'last'. + * + * @param tree pointer to avl-tree + * @param last pointer to last element of loop + * @param element pointer to a node of the tree, this element will + * contain the current node of the list during the loop + * @param node_member name of the avl_node element inside the + * larger struct + */ +#define avl_for_first_to_element_reverse(tree, last, element, node_member) \ + avl_for_element_range_reverse(avl_first_element(tree, element, node_member), last, element, node_member) + +/** + * Loop over a block of nodes of a tree, used similar to a for() command. + * This loop can be used if the current element might be removed from + * the tree during the loop. Other elements should not be removed during + * the loop. + * + * @param first_element first element of loop + * @param last_element last element of loop + * @param element iterator pointer to tree element struct + * @param node_member name of avl_node within tree element struct + * @param ptr pointer to tree element struct which is used to store + * the next node during the loop + */ +#define avl_for_element_range_safe(first_element, last_element, element, node_member, ptr) \ + for (element = (first_element), ptr = avl_next_element(first_element, node_member); \ + element->node_member.list.prev != &(last_element)->node_member.list; \ + element = ptr, ptr = avl_next_element(ptr, node_member)) + +/** + * Loop over a block of elements of a tree backwards, used similar to a for() command. + * This loop can be used if the current element might be removed from + * the tree during the loop. Other elements should not be removed during + * the loop. + * + * @param first_element first element of range (will be last returned by the loop) + * @param last_element last element of range (will be first returned by the loop) + * @param element iterator pointer to node element struct + * @param node_member name of avl_node within node element struct + * @param ptr pointer to node element struct which is used to store + * the previous node during the loop + */ +#define avl_for_element_range_reverse_safe(first_element, last_element, element, node_member, ptr) \ + for (element = (last_element), ptr = avl_prev_element(last_element, node_member); \ + element->node_member.list.next != &(first_element)->node_member.list; \ + element = ptr, ptr = avl_prev_element(ptr, node_member)) + +/** + * Loop over all elements of an avl_tree, used similar to a for() command. + * This loop can be used if the current element might be removed from + * the tree during the loop. Other elements should not be removed during + * the loop. + * + * @param tree pointer to avl-tree + * @param element pointer to a node of the tree, this element will + * contain the current node of the tree during the loop + * @param node_member name of the avl_node element inside the + * larger struct + * @param ptr pointer to a tree element which is used to store + * the next node during the loop + */ +#define avl_for_each_element_safe(tree, element, node_member, ptr) \ + avl_for_element_range_safe(avl_first_element(tree, element, node_member), \ + avl_last_element(tree, element, node_member), \ + element, node_member, ptr) + +/** + * Loop over all elements of an avl_tree backwards, used similar to a for() command. + * This loop can be used if the current element might be removed from + * the tree during the loop. Other elements should not be removed during + * the loop. + * + * @param tree pointer to avl-tree + * @param element pointer to a node of the tree, this element will + * contain the current node of the tree during the loop + * @param node_member name of the avl_node element inside the + * larger struct + * @param ptr pointer to a tree element which is used to store + * the next node during the loop + */ +#define avl_for_each_element_reverse_safe(tree, element, node_member, ptr) \ + avl_for_element_range_reverse_safe(avl_first_element(tree, element, node_member), \ + avl_last_element(tree, element, node_member), \ + element, node_member, ptr) + +/** + * A special loop that removes all elements of the tree and cleans up the tree + * root. The loop body is responsible to free the node elements of the tree. + * + * This loop is much faster than a normal one for clearing the tree because it + * does not rebalance the tree after each removal. Do NOT use a break command + * inside. + * You can free the memory of the elements within the loop. + * Do NOT call avl_delete() on the elements within the loop, + * + * @param tree pointer to avl-tree + * @param element pointer to a node of the tree, this element will + * contain the current node of the tree during the loop + * @param node_member name of the avl_node element inside the + * larger struct + * @param ptr pointer to a tree element which is used to store + * the next node during the loop + */ +#define avl_remove_all_elements(tree, element, node_member, ptr) \ + for (element = avl_first_element(tree, element, node_member), \ + ptr = avl_next_element(element, node_member), \ + list_init_head(&(tree)->list_head), \ + (tree)->root = NULL; \ + (tree)->count > 0; \ + element = ptr, ptr = avl_next_element(ptr, node_member), (tree)->count--) + +#endif /* _AVL_H */ + +/* + * Local Variables: + * c-basic-offset: 2 + * indent-tabs-mode: nil + * End: + */ diff --git a/list.h b/list.h index 2959a06..e8271d0 100644 --- a/list.h +++ b/list.h @@ -166,6 +166,17 @@ static inline void list_move_tail(struct list_head *list, list_add_tail(list, head); } +/** + * list_is_first - tests whether @list is the first entry in list @head + * @list: the entry to test + * @head: the head of the list + */ +static inline int list_is_first(const struct list_head *list, + const struct list_head *head) +{ + return list->prev == head; +} + /** * list_is_last - tests whether @list is the last entry in list @head * @list: the entry to test diff --git a/list_compat.h b/list_compat.h new file mode 100644 index 0000000..2b7b1f4 --- /dev/null +++ b/list_compat.h @@ -0,0 +1,15 @@ +#ifndef __LIST_COMPAT_H +#define __LIST_COMPAT_H + +#define list_entity list_head + +#define list_init_head(_list) INIT_LIST_HEAD(_list) +#define list_add_head(_head, _list) list_add(_list, _head) +#define list_add_after(_after, _list) list_add(_list, _after) +#define list_add_before(_before, _list) list_add_tail(_list, _before) +#define list_remove(_list) list_del(_list) +#define list_is_empty(_list) list_empty(_list) +#define list_next_element(_element, _member) list_entry((_element)->_member.next, typeof(*(_element)), _member) + + +#endif -- 2.25.1