I don't remember

1 files changed, 267 insertions, 0 deletions

diff --git a/src/routing.c.orig b/src/routing.c.orig
new file mode 100644
index 0000000..596548a
--- /dev/null
+++ b/src/routing.c.orig
@@ -0,0 +1,267 @@
+#include "routing.h"
+
+#include "log.h"
+
+#include <assert.h>
+#include <limits.h>
+#include <string.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+// The DHT routing table has a keyspace of 0 -- 2^160 split into buckets of 8.
+// When a bucket becomes full, we split it in half. As we further expand the
+// routing table we only continue to split the buckets on the side we fall on.
+//
+// Initially, this may sound like a binary tree (because we split it in two),
+// but looking at it as a flat array leads to some interesting intuitions.
+// Since we only expand one half of the "tree", the total size is bounded by
+// the depth of the tree log2(2^160) == 160.
+//
+// As a flat array we notice the intrinsic properties of the routing table.
+// With a bucket size of 8, the routing table contains 160 * 8 == 1280 nodes.
+// As the node ids get less similar to our own our grouping of them becomes
+// less detailed. While the bucket we are in contains node very close to us,
+// the nodes furthest away from us are grouped in buckets with nodes they
+// barely resemble.
+//
+// +----------------------------+
+// | n1 | n2 | n3 | ... | n1280 |
+// +----------------------------+
+//   More                  Less
+//  <--------Similarity-------->
+//  <----------Detail---------->
+//
+
+<<<<<<< HEAD
+struct table {
+	struct nodeid myID;
+	struct entry table[RT_SIZE];
+};
+
+struct table* pTable;
+=======
+#include<arpa/inet.h>
+
+#define IDBITS 160
+#define BUCKETSIZE 8
+// The 3 here is log2(BUCKETSIZE), since the final bucket will contain all those combinations
+#define BUCKETBITS 3
+#define ROUTINGSIZE (IDBITS * BUCKETSIZE)
+
+struct nodeid myID;
+struct entry table[ROUTINGSIZE];
+int table_size = ROUTINGSIZE;
+>>>>>>> 685b13e (I don't remember)
+
+void routing_init(struct nodeid* myid) {
+	pTable = malloc(sizeof(struct table));
+	pTable->myID = *myid;
+	routing_flush();
+}
+
+void routing_flush() {
+	memset(pTable->table, 0, sizeof(pTable->table));
+}
+
+// Calculate the common bit prefix between two node ids.
+static uint8_t prefix(struct nodeid* a, struct nodeid* b) {
+	uint8_t c = 0;
+	for(uint8_t i = 0; i < 5; i++) {
+          // Since the nodeids are stored in host byteorder in the words we have
+          // to make sure they're big endian before doing the prefix match,
+          // otherwise we end up with prefix matching that's different from the
+          // rest of the network
+          uint32_t word = htonl(a->inner[i]) ^ htonl(b->inner[i]);
+
+          // This word is different, find the location of the difference
+          if (word != 0)
+            return c + __builtin_clz(word);
+
+          // This word is completely the same
+          c += sizeof(word) * CHAR_BIT;
+	}
+
+	return c;
+}
+
+static int8_t scan(uint16_t baseIndex, struct nodeid* id) {
+	assert(baseIndex < RT_SIZE - RT_BSIZE);
+	int8_t index = -2;
+
+	for(size_t i = baseIndex; i < baseIndex + RT_BSIZE; i++) {
+		if(!pTable->table[i].set) {
+			index = index == -2 ? i - baseIndex : index;
+			continue;
+		}
+
+		if(memcmp(&pTable->table[i].id, id, sizeof(struct nodeid)) == 0) {
+			return -1;
+		}
+	}
+	
+	return index;
+}
+
+static uint16_t base_bucket(struct nodeid* id) {
+	uint16_t bucketIndex = prefix(&pTable->myID, id);
+	assert(bucketIndex != RT_IDBITS);
+
+	// If they are sufficiently similar they end up in the final bucket. Clamp the index to ensure.
+	bucketIndex = bucketIndex > (RT_IDBITS - RT_BBITS) ? (RT_IDBITS - RT_BBITS) : bucketIndex;
+	assert(bucketIndex <= RT_IDBITS - RT_BBITS);
+
+	return bucketIndex * RT_BSIZE;
+}
+
+struct entry* routing_get(struct nodeid* id) {
+	uint16_t baseIndex = base_bucket(id);
+	for(size_t i = baseIndex; i < baseIndex + RT_BSIZE; i++) {
+		if(!pTable->table[i].set) continue;
+
+		if(memcmp(&pTable->table[i].id, id, sizeof(struct nodeid)) == 0) {
+			return &pTable->table[i];
+		}
+	}
+
+	return NULL;
+}
+
+void routing_remove(struct nodeid* id) {
+	struct entry* entry = routing_get(id);
+
+	entry->set = false;
+}
+
+bool routing_interested(struct nodeid* id) {
+	uint16_t bucketIndex = prefix(&pTable->myID, id);
+	// The nodeid is the same as our own
+	if(bucketIndex == RT_IDBITS) {
+		return false;
+	}
+
+	uint16_t baseIndex = base_bucket(id);
+	int8_t inBucketIndex = scan(baseIndex, id);
+
+	if(inBucketIndex < 0) {
+		// The bucket either already contains the node, or it has no more space
+		return false;
+	}
+
+	return true;
+}
+
+// Offer the routing table a new node
+bool routing_offer(struct nodeid* id, struct entry **dest) {
+	uint16_t bucketIndex = prefix(&pTable->myID, id);
+	// The nodeid is the same as our own
+	if(bucketIndex == RT_IDBITS) {
+		return false;
+	}
+
+	uint16_t baseIndex = base_bucket(id);
+	int8_t inBucketIndex = scan(baseIndex, id);
+
+	if(inBucketIndex < 0) {
+		// The bucket either already contains the node, or it has no more space
+		return false;
+	}
+
+	struct entry* entry = &pTable->table[baseIndex + inBucketIndex];
+	entry->set = true;
+	entry->id = *id;
+
+	*dest = entry;
+	return true;
+}
+
+struct item {
+	struct nodeid distance;
+	bool set;
+	uint16_t index;
+};
+int compareItem(const void* a_v, const void* b_v) {
+	struct item* a = (struct item*)a_v;
+	struct item* b = (struct item*)b_v;
+
+	// If either of the two are not set, the one that is set comes before the
+	// one that isn't.
+	if(!a->set || !b->set) return b->set - a->set;
+
+	return memcmp(&a->distance, &b->distance, sizeof(struct nodeid));
+}
+
+size_t routing_closest(struct nodeid* needle, size_t n, struct entry** res) {
+	assert(n <= RT_SIZE);
+	static struct item items[RT_SIZE] = {0};
+	for(uint16_t i = 0; i < RT_SIZE; i++) {
+		items[i].index = i;
+	}
+
+	{
+		struct item* item;
+		struct entry* entry;
+		for(item = &items[0], entry = &pTable->table[0]; item < &items[RT_SIZE] && entry < &pTable->table[RT_SIZE]; item++, entry++){
+			item->set = entry->set;
+			for(uint8_t j = 0; j < 5; j++) {
+				item->distance.inner[j] = entry->id.inner[j] ^ needle->inner[j];
+			}
+		}
+	}
+
+	// @PERFORMANCE: There's an algorithm known as quickselect which can select
+	// the top k elements from a list while only doing a partial sort.
+	// I imagine that would be more efficient than this full sort.
+	qsort(items, RT_SIZE, sizeof(struct item), compareItem);
+
+	size_t read;
+	for(read = 0; read < n; read++) {
+		if(!items[read].set)
+			break;
+		res[read] = &pTable->table[items[read].index];
+	}
+
+	return read;
+}
+
+void routing_oldest(struct entry** dest) {
+	*dest = NULL;
+
+	for(struct entry* entry = pTable->table; entry < pTable->table+RT_SIZE; entry++){
+		if(!entry->set)
+			continue;
+
+		if(entry->expire == 0)
+			continue;
+
+		if(*dest == NULL) {
+			*dest = entry;
+			continue;
+		}
+
+		if(difftime((*dest)->expire, entry->expire) > 0.0) {
+			*dest = entry;
+		}
+	}
+}
+
+void routing_status(int* filled, int* size, double* load_factor, size_t load_factor_len) {
+	*size = RT_SIZE;
+
+	*filled = 0;
+	for(size_t i = 0; i < RT_SIZE; i++) {
+		if(pTable->table[i].set)
+			(*filled)++;
+	}
+
+	int per_bucket = RT_SIZE / load_factor_len;
+	int overflow = RT_SIZE % load_factor_len;
+	struct entry* table_cursor = pTable->table;
+	for(int i = 0; i < load_factor_len; i++) {
+		int is_overflow = i < overflow;
+		for(int j = 0; j < per_bucket + is_overflow; j++) {
+			load_factor[i] += table_cursor->set;
+			table_cursor++;
+		}
+		load_factor[i] /= per_bucket + is_overflow;
+	}
+}