[sheepdog] [PATCH RFC 3/5] dog/farm: use rb_tree for vdi management

[Liu Yuan]

On Thu, Sep 05, 2013 at 09:29:18AM +0900, MORITA Kazutaka wrote:
> From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
> 
> Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
> ---
>  dog/farm/farm.c |   27 +++++++++++++++------------
>  1 file changed, 15 insertions(+), 12 deletions(-)
> 
> diff --git a/dog/farm/farm.c b/dog/farm/farm.c
> index d034c7a..878d14d 100644
> --- a/dog/farm/farm.c
> +++ b/dog/farm/farm.c
> @@ -16,7 +16,7 @@
>  #include <pthread.h>
>  
>  #include "farm.h"
> -#include "list.h"
> +#include "rbtree.h"
>  
>  static char farm_object_dir[PATH_MAX];
>  static char farm_dir[PATH_MAX];
> @@ -28,9 +28,9 @@ struct vdi_entry {
>  	uint32_t vdi_id;
>  	uint32_t snap_id;
>  	uint8_t  nr_copies;
> -	struct list_node list;
> +	struct rb_node rb;
>  };
> -static LIST_HEAD(last_vdi_list);
> +static struct rb_root last_vdi_tree = RB_ROOT;
>  
>  struct snapshot_work {
>  	struct trunk_entry entry;
> @@ -40,15 +40,18 @@ struct snapshot_work {
>  static struct work_queue *wq;
>  static uatomic_bool work_error;
>  
> +static int vdi_cmp(const struct vdi_entry *e1, const struct vdi_entry *e2)
> +{
> +	return strcmp(e1->name, e2->name);
> +}
> +
>  static struct vdi_entry *find_vdi(const char *name)
>  {
> -	struct vdi_entry *vdi;
> +	struct vdi_entry key = {};
>  
> -	list_for_each_entry(vdi, &last_vdi_list, list) {
> -		if (!strcmp(vdi->name, name))
> -			return vdi;
> -	}
> -	return NULL;
> +	pstrcpy(key.name, sizeof(key.name), name);
> +
> +	return rb_search(&last_vdi_tree, &key, rb, vdi_cmp);
>  }
>  
>  static struct vdi_entry *new_vdi(const char *name, uint64_t vdi_size,
> @@ -75,7 +78,7 @@ static void insert_vdi(struct sd_inode *new)
>  			      new->vdi_id,
>  			      new->snap_id,
>  			      new->nr_copies);
> -		list_add(&vdi->list, &last_vdi_list);
> +		rb_insert(&last_vdi_tree, vdi, rb, vdi_cmp);
>  	} else if (vdi->snap_id < new->snap_id) {
>  		vdi->vdi_size = new->vdi_size;
>  		vdi->vdi_id = new->vdi_id;
> @@ -88,7 +91,7 @@ static int create_active_vdis(void)
>  {
>  	struct vdi_entry *vdi;
>  	uint32_t new_vid;
> -	list_for_each_entry(vdi, &last_vdi_list, list) {
> +	rb_for_each_entry(vdi, &last_vdi_tree, rb) {
>  		if (do_vdi_create(vdi->name,
>  				  vdi->vdi_size,
>  				  vdi->vdi_id, &new_vid,
> @@ -101,7 +104,7 @@ static int create_active_vdis(void)
>  static void free_vdi_list(void)
>  {
>  	struct vdi_entry *vdi;
> -	list_for_each_entry(vdi, &last_vdi_list, list)
> +	rb_for_each_entry(vdi, &last_vdi_tree, rb)
>  		free(vdi);

we need rb_erase() too here?

Thanks
Yuan