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

[MORITA Kazutaka]

At Thu, 5 Sep 2013 10:58:43 +0800,
Liu Yuan wrote:
> 
> 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?

Looks necessary.  I wonder why the current code doesn't call
list_del() here.

Thanks,

Kazutaka