123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737 |
- /*
- * PacketBB handler library (see RFC 5444)
- * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
- * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
- * 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 <stdbool.h>
- #include <stddef.h>
- #include <stdint.h>
- #include <time.h>
- #include <string.h>
- #include "avl.h"
- #include "assert.h"
- #include "list.h"
- /**
- * 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)
- {
- INIT_LIST_HEAD(&tree->list_head);
- tree->root = NULL;
- tree->count = 0;
- tree->comp = comp;
- tree->allow_dups = allow_dups;
- tree->cmp_ptr = ptr;
- }
- static inline struct avl_node *avl_next(struct avl_node *node)
- {
- return list_entry(node->list.next, struct avl_node, list);
- }
- /**
- * 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(const 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(const 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 key<node.key */
- while (diff < 0) {
- if (list_is_first(&node->list, &tree->list_head)) {
- 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(&node->list, &tree->list_head)) {
- 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(const 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(&node->list, &tree->list_head)) {
- 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(&node->list, &tree->list_head)) {
- 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(&new->list, &tree->list_head);
- 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(&last->list, &tree->list_head)) {
- next = avl_next(last);
- 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(&node->list, &tree->list_head)
- && !(next = avl_next(node))->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_tail(&node->list, &pos_node->list);
- tree->count++;
- }
- static void
- avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
- {
- list_add(&node->list, &pos_node->list);
- tree->count++;
- }
- static void
- avl_remove(struct avl_tree *tree, struct avl_node *node)
- {
- list_del(&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;
- }
- assert(node->right);
- 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:
- */
|