[sheepdog] [PATCH v3 2/4] object list cache: put all the cache entry into a list

levin li levin108 at gmail.com
Thu Jul 19 04:19:09 CEST 2012


From: levin li <xingke.lwp at taobao.com>

Compared to rb-tree, putting the entry into a list makes
it easy to traverse and reclaim.

Signed-off-by: levin li <xingke.lwp at taobao.com>
---
 sheep/object_list_cache.c |    9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/sheep/object_list_cache.c b/sheep/object_list_cache.c
index e2fffc1..39e8d49 100644
--- a/sheep/object_list_cache.c
+++ b/sheep/object_list_cache.c
@@ -23,6 +23,7 @@
 
 struct objlist_cache_entry {
 	uint64_t oid;
+	struct list_head list;
 	struct rb_node node;
 };
 
@@ -31,6 +32,7 @@ struct objlist_cache {
 	int buf_version;
 	int cache_size;
 	uint64_t *buf;
+	struct list_head entry_list;
 	struct rb_root root;
 	pthread_rwlock_t lock;
 };
@@ -38,6 +40,7 @@ struct objlist_cache {
 struct objlist_cache obj_list_cache = {
 	.tree_version	= 1,
 	.root		= RB_ROOT,
+	.entry_list     = LIST_HEAD_INIT(obj_list_cache.entry_list),
 	.lock		= PTHREAD_RWLOCK_INITIALIZER,
 };
 
@@ -80,6 +83,7 @@ static int objlist_cache_rb_remove(struct rb_root *root, uint64_t oid)
 		else if (oid > entry->oid)
 			p = &(*p)->rb_right;
 		else {
+			list_del(&entry->list);
 			rb_erase(parent, root);
 			free(entry);
 			return 0;
@@ -118,6 +122,7 @@ int objlist_cache_insert(uint64_t oid)
 	if (p)
 		free(entry);
 	else {
+		list_add(&entry->list, &obj_list_cache.entry_list);
 		obj_list_cache.cache_size++;
 		obj_list_cache.tree_version++;
 	}
@@ -130,7 +135,6 @@ int get_obj_list(const struct sd_list_req *hdr, struct sd_list_rsp *rsp, void *d
 {
 	int nr = 0;
 	struct objlist_cache_entry *entry;
-	struct rb_node *p;
 
 	/* first try getting the cached buffer with only a read lock held */
 	pthread_rwlock_rdlock(&obj_list_cache.lock);
@@ -147,8 +151,7 @@ int get_obj_list(const struct sd_list_req *hdr, struct sd_list_rsp *rsp, void *d
 	obj_list_cache.buf = xrealloc(obj_list_cache.buf,
 				obj_list_cache.cache_size * sizeof(uint64_t));
 
-	for (p = rb_first(&obj_list_cache.root); p; p = rb_next(p)) {
-		entry = rb_entry(p, struct objlist_cache_entry, node);
+	list_for_each_entry(entry, &obj_list_cache.entry_list, list) {
 		obj_list_cache.buf[nr++] = entry->oid;
 	}
 
-- 
1.7.10




More information about the sheepdog mailing list