[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