From e0c0c474fc3b2c68f7d814256aebf204f4ce7218 Mon Sep 17 00:00:00 2001
From: sage <sage@29311d96-e01e-0410-9327-a35deaab8ce9>
Date: Fri, 20 Jan 2006 20:13:35 +0000
Subject: [PATCH] *** empty log message ***

git-svn-id: https://ceph.svn.sf.net/svnroot/ceph@576 29311d96-e01e-0410-9327-a35deaab8ce9
---
 ceph/crush/Bucket.h                | 33 +++++++++++-----
 ceph/crush/crush.h                 |  4 +-
 ceph/crush/test/bucket_movement.cc |  4 +-
 ceph/crush/test/overload.cc        |  2 +-
 ceph/crush/test/speed_depth.cc     | 62 ++++++++++++++++++++++--------
 5 files changed, 76 insertions(+), 29 deletions(-)

diff --git a/ceph/crush/Bucket.h b/ceph/crush/Bucket.h
index dcbf4569981ca..b621b16449302 100644
--- a/ceph/crush/Bucket.h
+++ b/ceph/crush/Bucket.h
@@ -65,7 +65,7 @@ namespace crush {
 
 	virtual void get_items(vector<int>& i) const = 0;
 	virtual float get_item_weight(int item) const = 0;
-	virtual void add_item(int item, float w) = 0;
+	virtual void add_item(int item, float w, bool back=false) = 0;
 	virtual void adjust_item_weight(int item, float w) = 0;
 	virtual void set_item_weight(int item, float w) {
 	  adjust_item_weight(item, w - get_item_weight(item));
@@ -165,7 +165,7 @@ namespace crush {
 	int get_item_type() const { return item_type; }
 	float get_item_weight(int item) const { return item_weight; }
 
-	void add_item(int item, float w) {
+	void add_item(int item, float w, bool back=false) {
 	  if (items.empty())
 		item_weight = w;
 	  items.push_back(item);
@@ -244,11 +244,26 @@ namespace crush {
 	  return 0;
 	}
 
-	void add_item(int item, float w) {
-	  items.push_front(item);
-	  item_weight.push_front(w);
-	  weight += w;
-	  sum_weight.push_front(weight);
+	void add_item(int item, float w, bool back=false) {
+	  if (back) {
+		items.push_back(item);
+		item_weight.push_back(w);
+		sum_weight.clear();
+		float s = 0.0;
+		for (list<float>::reverse_iterator i = item_weight.rbegin();
+			 i != item_weight.rend();
+			 i++) {
+		  s += *i;
+		  sum_weight.push_front(s);
+		}
+		weight += w;
+		assert(weight == s);
+	  } else {
+		items.push_front(item);
+		item_weight.push_front(w);
+		weight += w;
+		sum_weight.push_front(weight);
+	  }
 	}
 
 	void adjust_item_weight(int item, float dw) {
@@ -356,7 +371,7 @@ namespace crush {
 	}
 
 
-	void add_item(int item, float w) {
+	void add_item(int item, float w, bool back=false) {
 	  item_weight[item] = w;
 	  weight += w;
 
@@ -451,7 +466,7 @@ namespace crush {
 	  return ((map<int,float>)item_weight)[item];
 	}
 
-	void add_item(int item, float w) {
+	void add_item(int item, float w, bool back=false) {
 	  item_weight[item] = w;
 	  weight += w;
 	  calc_straws();
diff --git a/ceph/crush/crush.h b/ceph/crush/crush.h
index 5975e5c16a28d..3f8a4659a90db 100644
--- a/ceph/crush/crush.h
+++ b/ceph/crush/crush.h
@@ -210,12 +210,12 @@ namespace crush {
 	  return n;
 	}
 
-	int add_item(int parent, int item, float w) {
+	int add_item(int parent, int item, float w, bool back=false) {
 	  // add item
 	  assert(!buckets[parent]->is_uniform());
 	  Bucket *p = buckets[parent];
 	  
-	  p->add_item(item, w);
+	  p->add_item(item, w, back);
 
 	  // set item's parent
 	  Bucket *n = buckets[item];
diff --git a/ceph/crush/test/bucket_movement.cc b/ceph/crush/test/bucket_movement.cc
index fdc890b4bf3fb..6fa2b2718a5d8 100644
--- a/ceph/crush/test/bucket_movement.cc
+++ b/ceph/crush/test/bucket_movement.cc
@@ -31,8 +31,8 @@ void place(Crush& c, Rule& rule, int numpg, int numrep, map<int, vector<int> >&
 		  bad = true;
 	  }
 	}
-	if (bad)
-	  cout << "bad set " << x << ": " << v << endl;
+	//if (bad)
+	// cout << "bad set " << x << ": " << v << endl;
 	
 	placement[x] = v;
 
diff --git a/ceph/crush/test/overload.cc b/ceph/crush/test/overload.cc
index 7a403ffd5974f..32c667201bca3 100644
--- a/ceph/crush/test/overload.cc
+++ b/ceph/crush/test/overload.cc
@@ -25,7 +25,7 @@ Bucket *make_bucket(Crush& c, vector<int>& wid, int h, int& ndisks)
 	  disks.push_back(ndisks++);
 	float w = ((ndisks-1)/100+1)*10;
 	UniformBucket *b = new UniformBucket(1, 0, w, disks);
-	b->make_primes(hash);  
+	//b->make_primes(hash);  
 	c.add_bucket(b);
 	//cout << h << " uniformbucket with " << wid[h] << " disks weight " << w << endl;
 	return b;
diff --git a/ceph/crush/test/speed_depth.cc b/ceph/crush/test/speed_depth.cc
index c4e6693377293..00a0102f9fffd 100644
--- a/ceph/crush/test/speed_depth.cc
+++ b/ceph/crush/test/speed_depth.cc
@@ -13,8 +13,9 @@ Clock g_clock;
 using namespace std;
 
 
+int uniform = 10;
 int branching = 10;
-bool linear = false;
+int buckettype = 0;
 int numrep = 1;
 
 Bucket *make_bucket(Crush& c, vector<int>& wid, int h, int& ndisks)
@@ -33,10 +34,12 @@ Bucket *make_bucket(Crush& c, vector<int>& wid, int h, int& ndisks)
   } else {
 	// mixed
 	Bucket *b;
-	if (linear)
-	  b = new ListBucket(h+1);
-	else
+	if (buckettype == 0)
 	  b = new TreeBucket(h+1);
+	else if (buckettype == 1 || buckettype == 2)
+	  b = new ListBucket(h+1);
+	else if (buckettype == 3)
+	  b = new StrawBucket(h+1);
 	for (int i=0; i<wid[h]; i++) {
 	  Bucket *n = make_bucket(c, wid, h-1, ndisks);
 	  b->add_item(n->get_id(), n->get_weight());
@@ -54,7 +57,7 @@ int make_hierarchy(Crush& c, vector<int>& wid, int& ndisks)
 }
 
 
-double go(int dep) 
+double go(int dep, int per) 
 {
   Hash h(73232313);
 
@@ -68,8 +71,9 @@ double go(int dep)
 
   vector<int> wid;
   if (1) {
-	for (int d=0; d<dep; d++)
-	  wid.push_back(branching);
+	wid.push_back(uniform);
+	for (int d=1; d<dep; d++)
+	  wid.push_back(per);
   }
   if (0) {
 	if (dep == 0) 
@@ -114,7 +118,7 @@ double go(int dep)
   end -= start;
   double el = (double)end;
 
-  cout << "\t" << ndisks;
+  //cout << "\t" << ndisks;
 
   return el;
 }
@@ -122,18 +126,46 @@ double go(int dep)
 
 int main() 
 {
-  branching = 8;
+  uniform = branching = 8;
+
+  cout << "// dep\tuniform\tbranch\tndisks" << endl;
 
   for (int d=2; d<=5; d++) {
-	cout << d << "\t" << branching;
-	for (numrep = 1; numrep <= 3; numrep++) {
-	  cout << "\t" << numrep;
+	cout << d;// << "\t" << branching;
+	cout << "\t" << uniform;
+	cout << "\t" << branching;
+
+	int n = 1;
+	for (int i=0; i<d; i++)
+	  n *= branching;
+	cout << "\t" << n;
+
+	numrep = 2;
+
+	// crush
+	for (buckettype = 0; buckettype <= 3; buckettype++) {
+	  switch (buckettype) {
+	  case 0: cout << "\ttree"; break;
+	  case 1: cout << "\tlist"; break;
+	  case 2: continue;
+	  case 3: cout << "\tstraw"; break;
+	  }
+
+	  //for (numrep = 1; numrep <= 3; numrep++) {
+	  //cout << "\t" << numrep;
 	  
-	  //for (linear = false; 1; linear = true) {
-	  double el = go(d);
+	  double el = go(d, branching);
 	  cout << "\t" << el;
-	  //if (linear) break;
 	}
+
+	// rush
+
+	buckettype = 0;
+	cout << "\trush_T\t" << go(2, n/uniform);
+
+	buckettype = 1;
+	cout << "\trush_P\t" << go(2, n/uniform);
+
 	cout << endl;
   }
 }
-- 
2.39.5