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