libdht

A simple helper library for distributed hash tables.
git clone git://r-36.net/libdht
Log | Files | Refs | README | 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