[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Lost] [PATCH 1/2] AVL-Baeume (v2)



On Sat, Oct 25 23:05, Kevin Wolf wrote:
> + 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
> ...
> +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

BUG im Kommentar ;-)

> +
> +        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);
> +}
> +

Ich würde zwar grundsätzlich gerne noch ein bisschen Dokumentation
sehen, aber schieb das halt mal rein so. Im Moment sehe ich nichts mehr,
das kaputt sein könnte.

-- 
Antoine Kaufmann
<toni@xxxxxxxxxxxxxxxx>

Attachment: pgpKS9LbJNX2D.pgp
Description: PGP signature