[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Lost] [PATCH 1/2] AVL-Baeume (v2)
+ libc: AVL-Baeume
Dieser Patch enthaelt gegenueber der ersten geposteten Version folgende
Aenderungen:
! libc: AVL-Baeume: rebalance akzeptiert auch Nullpointer als Parameter,
weil manchmal item->parent uebergeben wird, ohne zu pruefen, ob es
nicht die Wurzel ist (bei item == NULL passiert dann einfach nichts)
! libc: Beim Loeschen muss ein linker Teilbaum nur beruecksichtigt
werden, wenn es ihn auch gibt.
---
src/include/collections.h | 65 +++++++
src/lib/collections/tree.c | 441 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 506 insertions(+), 0 deletions(-)
create mode 100644 src/lib/collections/tree.c
diff --git a/src/include/collections.h b/src/include/collections.h
index 3702837..a215582 100644
--- a/src/include/collections.h
+++ b/src/include/collections.h
@@ -1,7 +1,46 @@
+/*
+ * Copyright (c) 2006-2008 The LOST Project. All rights reserved.
+ *
+ * This code is derived from software contributed to the LOST Project
+ * by Kevin Wolf.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the LOST Project
+ * and its contributors.
+ * 4. Neither the name of the LOST Project 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 HOLDERS 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.
+ */
+
#ifndef COLLECTIONS_H
#define COLLECTIONS_H
#include "types.h"
+#include <stdint.h>
+#include <stddef.h>
+
+/* Listen **************************************/
typedef struct {
struct list_node* anchor;
@@ -18,4 +57,30 @@ list_t* list_insert(list_t* list, int index, void* value);
void* list_remove(list_t* list, int index);
dword list_size(list_t* list);
+
+
+/* Baeume **************************************/
+
+struct tree_item {
+ struct tree_item* parent;
+ struct tree_item* left;
+ struct tree_item* right;
+ int balance;
+};
+
+typedef struct {
+ struct tree_item* root;
+ size_t tree_item_offset;
+ size_t sort_key_offset;
+} tree_t;
+
+tree_t* tree_create(size_t tree_item_offset, size_t sort_key_offset);
+void tree_destroy(tree_t* tree);
+
+void* tree_search(tree_t* tree, uint64_t key);
+tree_t* tree_insert(tree_t* tree, void* node);
+void* tree_remove(tree_t* tree, void* node);
+void* tree_prev(tree_t* tree, void* node);
+void* tree_next(tree_t* tree, void* node);
+
#endif
diff --git a/src/lib/collections/tree.c b/src/lib/collections/tree.c
new file mode 100644
index 0000000..4f53e62
--- /dev/null
+++ b/src/lib/collections/tree.c
@@ -0,0 +1,441 @@
+/*
+ * Copyright (c) 2008 The LOST Project. All rights reserved.
+ *
+ * This code is derived from software contributed to the LOST Project
+ * by Kevin Wolf.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the LOST Project
+ * and its contributors.
+ * 4. Neither the name of the LOST Project 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 HOLDERS 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.
+ */
+
+#include <collections.h>
+#include <stdlib.h>
+
+#ifdef DEBUG_TREE
+#include <stdio.h>
+
+void tree_dump(tree_t* tree);
+#endif
+
+static inline void* to_node(tree_t* tree, struct tree_item* item) {
+ return ((char*) item - tree->tree_item_offset);
+}
+
+static inline struct tree_item* to_tree_item(tree_t* tree, void* node) {
+ return (struct tree_item*) ((char*) node + tree->tree_item_offset);
+}
+
+static inline uint64_t get_key(tree_t* tree, struct tree_item* item) {
+ return *(uint64_t*)((char*) to_node(tree, item) + tree->sort_key_offset);
+}
+
+
+tree_t* tree_create(size_t tree_item_offset, size_t sort_key_offset)
+{
+ tree_t* tree = calloc(1, sizeof(*tree));
+
+ tree->tree_item_offset = tree_item_offset;
+ tree->sort_key_offset = sort_key_offset;
+
+ return tree;
+}
+
+void tree_destroy(tree_t* tree)
+{
+ free(tree);
+}
+
+static int do_search(tree_t* tree, uint64_t key, struct tree_item** node)
+{
+ struct tree_item* res = NULL;
+ struct tree_item* current = tree->root;
+ uint64_t current_key = key - 1;
+
+ while (current != NULL) {
+ res = current;
+ current_key = get_key(tree, current);
+ if (key == current_key) {
+ break;
+ } else if (key < current_key) {
+ current = current->left;
+ } else {
+ current = current->right;
+ }
+ }
+
+ *node = res;
+ return (key == current_key);
+}
+
+void* tree_search(tree_t* tree, uint64_t key)
+{
+ struct tree_item* ret;
+
+ if (do_search(tree, key, &ret)) {
+ return to_node(tree, ret);
+ } else {
+ return NULL;
+ }
+}
+
+static inline void adjust_balance(struct tree_item* item, int value)
+{
+ int stop = 0;
+
+ while (item->parent && !stop) {
+ if (item->parent->left == item) {
+ // Wenn an einem rechtslastigen Knoten links etwas geaendert wird,
+ // aendert sich zwar seine eigenen Balance, aber nicht mehr die des
+ // Vaterknotens.
+ if (item->parent->balance > 0) {
+ stop = 1;
+ }
+ item->parent->balance -= value;
+ if (item->parent->balance > 0) {
+ stop = 1;
+ }
+ } else {
+ // Dasselbe gilt fuer die rechte Seite eines linkslastigen Knotens.
+ if (item->parent->balance < 0) {
+ stop = 1;
+ }
+ item->parent->balance += value;
+ if (item->parent->balance < 0) {
+ stop = 1;
+ }
+ }
+ item = item->parent;
+ }
+}
+
+static void rotate_left(struct tree_item** root)
+{
+ struct tree_item* item = *root;
+ struct tree_item* tmp = item->right;
+
+ tmp->parent = item->parent;
+ item->parent = tmp;
+ if (tmp->left) {
+ tmp->left->parent = item;
+ }
+
+ item->right = tmp->left;
+ tmp->left = item;
+ *root = tmp;
+}
+
+static void rotate_right(struct tree_item** root)
+{
+ struct tree_item* item = *root;
+ struct tree_item* tmp = item->left;
+
+ tmp->parent = item->parent;
+ item->parent = tmp;
+ if (tmp->right) {
+ tmp->right->parent = item;
+ }
+
+ item->left = tmp->right;
+ tmp->right = item;
+ *root = tmp;
+}
+
+static struct tree_item** link_from_parent(tree_t* tree,
+ struct tree_item* item)
+{
+ if (item->parent == NULL) {
+ return &tree->root;
+ } else if (item->parent->left == item) {
+ return &item->parent->left;
+ } else {
+ return &item->parent->right;
+ }
+}
+
+static void rebalance(tree_t* tree, struct tree_item* item)
+{
+ struct tree_item** pitem;
+ struct tree_item* tmp;
+
+ while (item) {
+
+ pitem = link_from_parent(tree, item);
+
+ if (item->balance >= 2) {
+
+ // Rechtslastiger Baum
+ tmp = item->right;
+
+ if (item->right->balance >= 0) {
+ // Einfache Rotation
+ rotate_left(pitem);
+ item->balance = 0;
+ tmp->balance = 0;
+ } else {
+ // Doppelrotation
+ rotate_right(&item->right);
+ rotate_left(pitem);
+ item->balance = ((*pitem)->balance == 1 ? -1 : 0);
+ tmp->balance = ((*pitem)->balance == -1 ? 1 : 0);
+ (*pitem)->balance = 0;
+ }
+
+ adjust_balance(*pitem, -1);
+
+ } else if (item->balance <= -2) {
+
+ // Linkslastiger Baum
+ tmp = item->left;
+
+ if (item->left->balance <= 0) {
+ // Einfache Rotation
+ rotate_right(pitem);
+ item->balance = 0;
+ tmp->balance = 0;
+ } else {
+ // Doppelrotation
+ rotate_left(&item->left);
+ rotate_right(pitem);
+ item->balance = ((*pitem)->balance == -1 ? 1 : 0);
+ tmp->balance = ((*pitem)->balance == 1 ? -1 : 0);
+ (*pitem)->balance = 0;
+ }
+
+ adjust_balance(*pitem, -1);
+ }
+
+ // Weiter Richtung Wurzel gehen
+ item = item->parent;
+
+ }
+}
+
+tree_t* tree_insert(tree_t* tree, void* node)
+{
+ struct tree_item* new = to_tree_item(tree, node);
+ struct tree_item* parent;
+ uint64_t new_key = get_key(tree, new);
+
+ new->left = NULL;
+ new->right = NULL;
+ new->balance = 0;
+
+ // Wenn es noch keine Wurzel gibt, ist die Sache trivial
+ if (tree->root == NULL) {
+ new->parent = NULL;
+ tree->root = new;
+ return tree;
+ }
+
+ // Ansonsten erstmal einen nahegelegenen Knoten finden, an dem man den
+ // neuen Knoten einhaengen kann. Wenn ein Knoten mit derselben ID schon
+ // drin ist, machen wir gar nichts.
+ if (!do_search(tree, new_key, &parent)) {
+ new->parent = parent;
+
+ if (new_key < get_key(tree, parent)) {
+ parent->left = new;
+ } else {
+ parent->right = new;
+ }
+ adjust_balance(new, 1);
+ rebalance(tree, new);
+ }
+
+ return tree;
+}
+
+void* tree_remove(tree_t* tree, void* node)
+{
+ struct tree_item* item = to_tree_item(tree, node);
+ struct tree_item** pitem = link_from_parent(tree, item);
+
+ // Wenn es ein Blatt war, einfach rausnehmen
+
+ if (!item->left && !item->right) {
+ adjust_balance(item, -1);
+ *pitem = NULL;
+ rebalance(tree, item->parent);
+ return node;
+ }
+
+ // Ansonsten muessen wir die Kinder irgendwo anders aufhaengen. Wenn nur
+ // eine Seite besetzt ist, uebernimmt einfach das Kind dort den Platz.
+
+ if (item->left && !item->right) {
+ adjust_balance(item, -1);
+ *pitem = item->left;
+ item->left->parent = item->parent;
+ rebalance(tree, item->parent);
+ return node;
+ }
+
+ if (!item->left && item->right) {
+ adjust_balance(item, -1);
+ *pitem = item->right;
+ item->right->parent = item->parent;
+ rebalance(tree, item->parent);
+ return node;
+ }
+
+ // Bleibt schliesslich noch der komplizierteste Fall, naemlich, dass beide
+ // Seiten besetzt sind. Dann nehmen wir einen vom Index her nahegelegenen
+ // Knoten als Ersatz fuer den geloeschten. Ein guter Kandidat dafuer ist
+ // der am weitesten rechts gelegene Knoten des linken Teilbaums.
+
+ struct tree_item* subst = to_tree_item(tree, node);
+ struct tree_item** psubst;
+
+ subst = item->left;
+ while (subst->right) {
+ subst = subst->right;
+ }
+
+ psubst = link_from_parent(tree, item);
+
+ // Wir sind ganz nach rechts gegangen, aber moeglicherweise ist noch ein
+ // linker Teilbaum uebrig. Dieser wird dann vom bisherigen Elternknoten
+ // des Ersatzes geerbt.
+
+ struct tree_item* old_left = subst->left;
+ struct tree_item* old_parent = subst->parent;
+
+ subst->parent = item->parent;
+ subst->right = item->right;
+ subst->left = item->left;
+
+ if (subst->left == subst) {
+ subst->left = NULL;
+ }
+
+ if (subst->left) {
+ subst->left->parent = subst;
+ }
+ if (subst->right) {
+ subst->right->parent = subst;
+ }
+
+ *psubst = old_left;
+ *pitem = subst;
+
+ if (old_left) {
+ old_left->parent = old_parent;
+ adjust_balance(old_left->parent, -1);
+ rebalance(tree, old_left->parent);
+ }
+
+ return node;
+}
+
+void* tree_prev(tree_t* tree, void* node)
+{
+ struct tree_item* current = to_tree_item(tree, node);
+ struct tree_item* old = current;
+
+ if (node == NULL) {
+ current = tree->root;
+ } else {
+
+ // Irgendwo mitten im Baum ist es einfach, den Vorgaenger zu finden:
+ // Einmal nach links und dann so weit wie moeglich nach rechts.
+ //
+ // Wenn der Knoten keinen linken Kindknoten hat, muessen wir ein Stueck
+ // Richtung Wurzel zurueckgehen, und zwar so lange bis wir von der
+ // rechten Seite an einen Knoten kommen.
+
+ if (current->left == NULL) {
+ do {
+ old = current;
+ current = current->parent;
+ } while (current && (current->left == old));
+
+ return current ? to_node(tree, current) : NULL;
+ }
+
+ current = current->left;
+ }
+
+ while (current->right) {
+ current = current->right;
+ }
+
+ return to_node(tree, current);
+}
+
+void* tree_next(tree_t* tree, void* node)
+{
+ struct tree_item* current = to_tree_item(tree, node);
+ struct tree_item* old = current;
+
+ if (node == NULL) {
+ current = tree->root;
+ } else {
+ // Das ist im Prinzip ein tree_next mit links und rechts vertauscht
+
+ if (current->right == NULL) {
+ do {
+ old = current;
+ current = current->parent;
+ } while (current && (current->right == old));
+
+ return current ? to_node(tree, current) : NULL;
+ }
+
+ current = current->right;
+ }
+
+ while (current->left) {
+ current = current->left;
+ }
+
+ return to_node(tree, current);
+}
+
+
+#ifdef DEBUG_TREE
+static void do_dump(tree_t* tree, struct tree_item* current)
+{
+ if (!current) {
+ printf("-");
+ } else if (!current->left && !current->right) {
+ printf("%ld", get_key(tree, current));
+ } else {
+ printf("[%d] %ld (", current->balance, get_key(tree, current));
+ do_dump(tree, current->left),
+ printf(" ");
+ do_dump(tree, current->right);
+ printf(")");
+ }
+}
+
+void tree_dump(tree_t* tree)
+{
+ do_dump(tree, tree->root);
+ puts("");
+}
+#endif
--
1.5.4.5