gistfile1.hpp

#include <openssl/sha.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

struct CH {
	struct node {
		node() { }

		node(const std::string id) :
			id(id) { }

		std::string id;

		bool operator== (const node o) const
		{
			return id == o.id;
		}
	};

	struct vnode {
		vnode() { }

		vnode(const node real, uint64_t hash) :
			real(real), hash(hash) { }

		node real;
		uint64_t hash;

		bool operator< (const vnode& o) const
		{
			return hash < o.hash;
		}
	};

	typedef std::vector<node> nodes_t;
	typedef std::vector<vnode> vnodes_t;

	nodes_t nodes;
	vnodes_t space;

	static uint64_t hash(const std::string& id)
	{
		unsigned char buf[SHA_DIGEST_LENGTH];
		SHA1((unsigned const char*)id.data(), id.size(), buf);
		return *(uint64_t*)buf;
	}

	static uint64_t hash(uint64_t h)
	{
		unsigned char buf[SHA_DIGEST_LENGTH];
		SHA1((unsigned const char*)&h, 8, buf);
		return *(uint64_t*)buf;
	}


	void add_node(const std::string& id, unsigned int num_vnode)
	{
		node real(id);
		nodes.push_back(real);

		uint64_t h = hash(id);
		for(unsigned int i=0; i < num_vnode; ++i) {
			h = hash(h);
			space.push_back( vnode(real,h) );
		}
	}

	void build()
	{
		std::stable_sort(space.begin(), space.end());
	}
};


int main(int argc, char* argv[])
{
	if(argc != 4) {
		std::cout << "usage: "<<argv[0]<<" <#loop> <#virtual node per physical node>  <#physical node>" << std::endl;
		exit(1);
	}

	unsigned int LOOP = atoi(argv[1]);
	unsigned int V = atoi(argv[2]);
	unsigned int N = atoi(argv[3]);

	unsigned int num_try  = 0;
	unsigned int num_loss = 0;

	srand(clock());

for(unsigned int l=0; l < LOOP; ++l) {

	CH ch;

	for(unsigned int i=0; i < N; ++i) {
		char buf[12];
		size_t sz = sprintf(buf, "%d", rand());
		std::string id(buf, sz);
		//std::cout << id << std::endl;
		ch.add_node(id, V);
	}

	ch.build();

	//for(size_t s=0; s < ch.nodes.size(); ++s) {
	//	std::cout << ch.nodes[s].id << std::endl;
	//}

	//for(size_t s=0; s < ch.space.size(); ++s) {
	//	std::cout << ch.space[s].hash << "  " << ch.space[s].real.id << std::endl;
	//}

	//for(size_t a=0; a < ch.nodes.size() -2; ++a) {
	{ size_t a = 0;
		CH::nodes_t downs( ch.nodes.begin()+a, ch.nodes.begin()+a+3 );

		bool loss = false;

		size_t i, j, k;
		for(i=0; i < ch.space.size(); ++i) {
			CH::vnode v1 = ch.space[i];
			CH::vnode v2;
			CH::vnode v3;
			for(j=i+1; ; ++j) {
				v2 = ch.space[j % ch.space.size()];
				if(v1.real == v2.real) continue;

				for(k=j+1; ; ++k) {
					v3 = ch.space[k % ch.space.size()];
					if(v1.real == v3.real || v2.real == v3.real) continue;
					break;
				}
				break;
			}

			if(		std::find(downs.begin(), downs.end(), v1.real) != downs.end() &&
					std::find(downs.begin(), downs.end(), v2.real) != downs.end() &&
					std::find(downs.begin(), downs.end(), v3.real) != downs.end() ) {
				loss = true;
				break;
			}
		}

		++num_try;
		if(loss) ++num_loss;
	}

}

	std::cout << "try:  " << num_try  << std::endl;
	std::cout << "loss: " << num_loss << std::endl;
	std::cout << "prop: " << ((double)num_loss) / ((double)num_try) << std::endl;
}