Re: [RFC PATCH 1/3] Weight-balanced tree

[Andrew Morton <akpm@linux-foundation.org>]

On Tue, 22 Feb 2011 11:55:05 -0700
Alex Williamson <alex.williamson@redhat.com> wrote:

> Signed-off-by: Alex Williamson <alex.williamson@redhat.com>
> ---
> 
>  include/linux/wbtree.h |   55 ++++++++++++++++
>  lib/Makefile           |    3 +
>  lib/wbtree.c           |  170 ++++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 227 insertions(+), 1 deletions(-)
>  create mode 100644 include/linux/wbtree.h
>  create mode 100644 lib/wbtree.c
> 
> diff --git a/include/linux/wbtree.h b/include/linux/wbtree.h
> new file mode 100644
> index 0000000..ef70f6f
> --- /dev/null
> +++ b/include/linux/wbtree.h
> @@ -0,0 +1,55 @@
> +/*
> + * Weight-balanced binary tree
> + *
> + * The balance of this tree is based on search probability.  The
> + * heaviest weighted nodes (the ones we're most likely to hit), are
> + * at the top of each subtree.
> + *
> + * Copywrite (C) 2011 Red Hat, Inc.
> + *
> + * Authors:
> + *   Alex Williamson <alex.williamson@redhat.com>
> + *
> + * This work is licensed under the terms of the GNU GPL, version 2.  See
> + * the COPYING file in the top-level directory.
> + */
> +#ifndef _LINUX_WBTREE_H
> +#define _LINUX_WBTREE_H
> +
> +#include <linux/kernel.h>
> +#include <linux/stddef.h>
> +
> +struct wb_node {
> +	struct wb_node *wb_parent;
> +	struct wb_node *wb_left;
> +	struct wb_node *wb_right;
> +	unsigned long wb_weight;
> +};
> +
> +struct wb_root {
> +	struct wb_node *wb_node;
> +};
> +
> +#define WB_ROOT (struct wb_root) { NULL, }
> +#define wb_entry(ptr, type, member) container_of(ptr, type, member)

Please implement this as a C function.  That way we get typechecking
which container_of() is unable to provide.

Otherwise the code looks OK to me, apart from the total lack of
documentation.  Please document at least all the exported interfaces. 
The documentation should be designed to tell people how to maintain
this code, and how to use this code reliably and well from other subsystems.
Don't fall into the trap of just dumbly filling out templates.

The documentation should also carefully explain the locking
requirements which these functions place upon callers.  (rwlocks used
how?  rcu?)

Once that is all squared away, please merge the code via the KVM tree.