1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#include "routing.h"
#include <assert.h>
#include <limits.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.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];
void routing_init(struct nodeid* myid) {
myID = *myid;
}
void routing_flush() {
memset(table, 0, sizeof(table));
}
// Calculate the common bit prefix between two node ids.
uint8_t prefix(struct nodeid* a, struct nodeid* b) {
uint8_t c = 0;
for(uint8_t i = 0; i < 5; i++) {
uint32_t word = a->inner[i] ^ 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;
}
int8_t scan(uint16_t baseIndex, struct nodeid* id) {
assert(baseIndex < ROUTINGSIZE - BUCKETSIZE);
int8_t index = -1;
for(size_t i = baseIndex; i < baseIndex + BUCKETSIZE; i++) {
if(!table[i].set) {
index = index == -1 ? i - baseIndex : index;
continue;
}
if(memcmp(&table[i].id, id, sizeof(struct nodeid)) == 0) {
return -1;
}
}
return index;
}
// Offer the routing table a new node
bool routing_offer(struct nodeid* id, struct entry **dest) {
uint16_t bucketIndex = prefix(&myID, id);
// The nodeid is the same as our own
if(bucketIndex == IDBITS) {
return false;
}
// If they are sufficiently similar they end up in the final bucket. Clamp the index to ensure.
bucketIndex = bucketIndex > (IDBITS - BUCKETBITS) ? (IDBITS - BUCKETBITS) : bucketIndex;
assert(bucketIndex <= IDBITS - BUCKETBITS);
uint16_t baseIndex = bucketIndex * BUCKETSIZE;
int8_t inBucketIndex = scan(baseIndex, id);
if(inBucketIndex == -1) {
// The bucket either already contains the node, or it has no more space
return false;
}
struct entry* entry = &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 <= ROUTINGSIZE);
static struct item items[ROUTINGSIZE] = {0};
for(uint16_t i = 0; i < ROUTINGSIZE; i++) {
items[i].index = i;
}
{
struct item* item;
struct entry* entry;
for(item = &items[0], entry = &table[0]; item < &items[ROUTINGSIZE] && entry < &table[ROUTINGSIZE]; 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, ROUTINGSIZE, sizeof(struct item), compareItem);
size_t read;
for(read = 0; read < n; read++) {
if(!items[read].set)
break;
res[read] = &table[items[read].index];
}
return read;
}
|
