dht.c - libdht - A simple helper library for distributed hash tables.
(HTM) git clone git://r-36.net/libdht
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
dht.c (4615B)
---
1 /*
2 * Copy me if you can.
3 * by 20h
4 */
5
6 #include <unistd.h>
7 #include <stdlib.h>
8 #include <stdio.h>
9 #include <string.h>
10 #include <strings.h>
11 #include <time.h>
12
13 #include "dht.h"
14 #include "ind.h"
15
16 dhtnode_t *
17 dhtnode_mkid(dhtnode_t *node)
18 {
19 srand((unsigned int)time(NULL)*rand());
20
21 for (int i = 0; i < sizeof(node->id); i++)
22 node->id[i] = rand() & 0xFF;
23
24 return node;
25 }
26
27 dhtnode_t *
28 dhtnode_setid(dhtnode_t *node, char id[IDLENGTH])
29 {
30 memmove(node->id, id, sizeof(node->id));
31
32 return node;
33 }
34
35 dhtnode_t *
36 dhtnode_setaddr(dhtnode_t *node, char *addr)
37 {
38 node->addr = memdup(addr, strlen(addr)+1);
39
40 return node;
41 }
42
43 dhtnode_t *
44 dhtnode_new(void)
45 {
46 dhtnode_t *node;
47
48 node = mallocz(sizeof(dhtnode_t), 2);
49
50 return node;
51 }
52
53 void
54 dhtnode_free(dhtnode_t *node)
55 {
56 free(node);
57 }
58
59 void
60 dhtnode_print(dhtnode_t *node)
61 {
62 printf("dhtnode[id=");
63 for (int i = 0; i < sizeof(node->id); i++)
64 printf("%.2x", node->id[i] & 0xFF);
65 printf(", addr='");
66 if (node->addr != NULL)
67 printf("%s", node->addr);
68 printf("']\n");
69 }
70
71 int
72 dhtnode_cmp(dhtnode_t *node1, dhtnode_t *node2)
73 {
74 return memcmp(node1->id, node2->id, sizeof(node1->id));
75 }
76
77 dhtnode_t *
78 dhtnode_xor(dhtnode_t *node1, dhtnode_t *node2)
79 {
80 dhtnode_t *ret;
81
82 ret = dhtnode_new();
83 for (int i = 0; i < sizeof(ret->id); i++)
84 ret->id[i] = node1->id[i] ^ node2->id[i];
85
86 return ret;
87 }
88
89 int
90 dhtnode_prefixlen(dhtnode_t *node)
91 {
92 for (int i = 0; i < sizeof(node->id); i++)
93 for (int j = 0; j < 8; j++)
94 if ((node->id[i] >> (7-j)) & 0x1)
95 return i * 8 + j;
96 return sizeof(node->id) * 8 - 1;
97 }
98
99 dhtrouting_t *
100 dhtrouting_new(dhtnode_t *node)
101 {
102 dhtrouting_t *route;
103
104 route = mallocz(sizeof(dhtrouting_t), 2);
105 for (int i = 0; i < nelem(route->buckets); i++)
106 route->buckets[i] = dhtlist_new();
107 route->node = node;
108
109 return route;
110 }
111
112 void
113 dhtrouting_free(dhtrouting_t *route)
114 {
115
116 for (int i = 0; i < nelem(route->buckets); i++)
117 dhtlist_free(route->buckets[i]);
118 dhtnode_free(route->node);
119 free(route);
120 }
121
122 dhtrouting_t *
123 dhtrouting_update(dhtrouting_t *route, dhtnode_t *node)
124 {
125 dhtlist_t *bucket;
126 dhtlistelem_t *elem;
127 dhtnode_t *xornode;
128 int bucketnum;
129
130 xornode = dhtnode_xor(route->node, node);
131 bucketnum = dhtnode_prefixlen(xornode);
132 dhtnode_free(xornode);
133 bucket = route->buckets[bucketnum];
134
135 forodhtlist(bucket, elem)
136 if (!dhtnode_cmp(elem->node, node))
137 break;
138 if (elem == NULL) {
139 if (bucket->len < IDLENGTH)
140 dhtlist_push(bucket, node);
141 else
142 return NULL;
143 } else
144 dhtlist_move(bucket, elem, 0);
145
146 return route;
147 }
148
149 dhtlist_t *
150 dhtrouting_sortnodes(dhtlist_t *dhtlist, dhtnode_t *target)
151 {
152 dhtnode_t *xornode1, *xornode2, *swap;
153 int sorted;
154
155 sorted = 0;
156
157 while(!sorted) {
158 sorted = 1;
159 fordhtlist(dhtlist, elem) {
160 if (elem->next == NULL)
161 break;
162 xornode1 = dhtnode_xor(elem->node, target);
163 xornode2 = dhtnode_xor(elem->next->node, target);
164
165 if (dhtnode_cmp(xornode1, xornode2) > 0) {
166 swap = elem->next->node;
167 elem->next->node = elem->node;
168 elem->node = swap;
169 sorted = 0;
170 }
171 dhtnode_free(xornode1);
172 dhtnode_free(xornode2);
173 }
174 }
175
176 return dhtlist;
177 }
178
179 dhtlist_t *
180 dhtrouting_addnodes(dhtlist_t *dhtlist, dhtlist_t *bucket, dhtnode_t *target,
181 int max)
182 {
183 fordhtlist(bucket, elem) {
184 if (dhtlist->len >= max)
185 break;
186 dhtlist_add(dhtlist, elem->node);
187 }
188
189 return dhtrouting_sortnodes(dhtlist, target);
190 }
191
192 dhtlist_t *
193 dhtrouting_findclosest(dhtrouting_t *route, dhtnode_t *target, int max)
194 {
195 int bucketnum;
196 dhtnode_t *xornode;
197 dhtlist_t *retnodes;
198
199 retnodes = dhtlist_new();
200
201 xornode = dhtnode_xor(route->node, target);
202 bucketnum = dhtnode_prefixlen(xornode);
203 dhtnode_free(xornode);
204
205 dhtrouting_addnodes(retnodes, route->buckets[bucketnum], target, max);
206 for (int i = 1; ((bucketnum-i) >= 0
207 || (bucketnum+i) < IDLENGTH * 8)
208 && retnodes->len < max; i++) {
209 if (bucketnum-i >= 0) {
210 dhtrouting_addnodes(retnodes,
211 route->buckets[bucketnum-i],
212 target, max);
213 }
214 if (bucketnum+i < IDLENGTH * 8) {
215 dhtrouting_addnodes(retnodes,
216 route->buckets[bucketnum+i],
217 target, max);
218 }
219 }
220
221 return retnodes;
222 }
223
224 dht_t *
225 dht_new(char *localhost)
226 {
227 dht_t *dht;
228 dhtnode_t *node;
229
230 node = dhtnode_new();
231 dhtnode_mkid(node);
232 dhtnode_setaddr(node, localhost);
233
234 dht = mallocz(sizeof(dht_t), 2);
235 dht->routing = dhtrouting_new(node);
236
237 return dht;
238 }
239
240 void
241 dht_free(dht_t *dht)
242 {
243 dhtrouting_free(dht->routing);
244 free(dht);
245 }
246
247 dhtlist_t *
248 dht_find(dht_t *dht, dhtnode_t *target, int max)
249 {
250 return dhtrouting_findclosest(dht->routing, target, max);
251 }
252
253 dht_t *
254 dht_update(dht_t *dht, dhtnode_t *node)
255 {
256 dhtrouting_update(dht->routing, node);
257
258 return dht;
259 }
260