[sheepdog] [PATCH] sheep: refactor get_nth_node() and get_vnode_pos()

[Yunkai Zhang]

From: Yunkai Zhang <qiushu.zyk at taobao.com>

oid_to_sheeps() calls get_nth_node() in a for-loop, but get_nth_node()
will do duplicated works because it should find [0..(n-2)] vnodes indexs
before it try to calculate n'th vnode index.

The return value of get_vnode_pos() seems werid for user, it need to plus one
before we can use it.

This patch try to refactor these two functions:
1) split a new function named get_vnode_next_idx() from get_nth_node().
2) rename get_vnode_pos() to get_vnode_first_idx(), and make the return
   value can be used directly.
3) rename get_nth_node() to get_vnode_nth_idx() which will be more descriptive.

Signed-off-by: Yunkai Zhang <qiushu.zyk at taobao.com>
---
 include/sheep.h | 101 ++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 62 insertions(+), 39 deletions(-)

diff --git a/include/sheep.h b/include/sheep.h
index 5795111..1d07b23 100644
--- a/include/sheep.h
+++ b/include/sheep.h
@@ -60,32 +60,9 @@ static inline int same_zone(struct sd_vnode *e, int n1, int n2)
 	return e[n1].zone != 0 && e[n1].zone == e[n2].zone;
 }
 
-/* traverse the virtual node list and return the n'th one */
-static inline int get_nth_node(struct sd_vnode *entries,
-			       int nr_entries, int base, int n)
-{
-	int nodes[SD_MAX_REDUNDANCY];
-	int nr = 0, idx = base, i;
-
-	while (n--) {
-		nodes[nr++] = idx;
-next:
-		idx = (idx + 1) % nr_entries;
-		if (idx == base) {
-			panic("bug"); /* not found */
-		}
-		for (i = 0; i < nr; i++) {
-			if (same_zone(entries, idx, nodes[i]))
-				/* this node is in the same zone, so skip here */
-				goto next;
-		}
-	}
-
-	return idx;
-}
-
-static inline int get_vnode_pos(struct sd_vnode *entries,
-			int nr_entries, uint64_t oid)
+/* Get the first vnode's index which is matching the OID */
+static inline int get_vnode_first_idx(struct sd_vnode *entries, int nr_entries,
+				      uint64_t oid)
 {
 	uint64_t id = fnv_64a_buf(&oid, sizeof(oid), FNV1A_64_INIT);
 	int start, end, pos;
@@ -94,36 +71,82 @@ static inline int get_vnode_pos(struct sd_vnode *entries,
 	end = nr_entries - 1;
 
 	if (id > entries[end].id || id < entries[start].id)
-		return end;
+		return (end + 1) % nr_entries;
 
 	for (;;) {
 		pos = (end - start) / 2 + start;
 		if (entries[pos].id < id) {
 			if (entries[pos + 1].id >= id)
-				return pos;
+				return (pos + 1) % nr_entries;
 			start = pos;
 		} else
 			end = pos;
 	}
 }
 
-static inline int obj_to_sheep(struct sd_vnode *entries,
-			       int nr_entries, uint64_t oid, int idx)
+/* Get next vnode's index according to the PREV_IDXS */
+static inline int get_vnode_next_idx(struct sd_vnode *entries, int nr_entries,
+				     int *prev_idxs, int nr_prev_idxs)
 {
-	int pos = get_vnode_pos(entries, nr_entries, oid);
+	int i, found, idx, first_idx;
+
+	first_idx = prev_idxs[0];
+	idx = prev_idxs[nr_prev_idxs - 1];
+	for (;;) {
+		idx = (idx + 1) % nr_entries;
+		if (idx == first_idx)
+			panic("can't find next new idx\n");
+
+		for (found = 0, i = 0; i < nr_prev_idxs; i++) {
+			if (same_zone(entries, idx, prev_idxs[i])) {
+				found = 1;
+				break;
+			}
+		}
 
-	return get_nth_node(entries, nr_entries, (pos + 1) % nr_entries, idx);
+		if (!found)
+			return idx;
+	}
+}
+
+/* Get the n'th vnode's index which is matching the OID */
+static inline int get_vnode_nth_idx(struct sd_vnode *entries,
+			int nr_entries, uint64_t oid, int nth)
+{
+	int nr_idxs = 0, idxs[SD_MAX_REDUNDANCY];
+
+	idxs[nr_idxs++] = get_vnode_first_idx(entries, nr_entries, oid);
+
+	if (!nth)
+		return idxs[nth];
+
+	while (nr_idxs <= nth) {
+		idxs[nr_idxs] = get_vnode_next_idx(entries, nr_entries,
+						     idxs, nr_idxs);
+		nr_idxs++;
+	}
+
+	return idxs[nth];
 }
 
-static inline void obj_to_sheeps(struct sd_vnode *entries,
-		  int nr_entries, uint64_t oid, int nr_copies, int *idxs)
+static inline int obj_to_sheep(struct sd_vnode *entries, int nr_entries,
+			       uint64_t oid, int nth_idx)
 {
-	int pos = get_vnode_pos(entries, nr_entries, oid);
-	int idx;
+	return get_vnode_nth_idx(entries, nr_entries, oid, nth_idx);
+}
 
-	for (idx = 0; idx < nr_copies; idx++)
-		idxs[idx] = get_nth_node(entries, nr_entries,
-				(pos + 1) % nr_entries, idx);
+static inline void obj_to_sheeps(struct sd_vnode *entries, int nr_entries,
+				 uint64_t oid, int nr_copies, int *idxs)
+{
+	int nr_idxs = 0;
+
+	idxs[nr_idxs++] = get_vnode_first_idx(entries, nr_entries, oid);
+
+	while (nr_idxs < nr_copies) {
+		idxs[nr_idxs] = get_vnode_next_idx(entries, nr_entries,
+						     idxs, nr_idxs);
+		nr_idxs++;
+	}
 }
 
 static inline const char *sd_strerror(int err)
-- 
1.7.11.2