libdht

dht.c (4615B)

---

 /*
  * Copy me if you can.
  * by 20h
  */
 
 #include <unistd.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
 #include <strings.h>
 #include <time.h>
 
 #include "dht.h"
 #include "ind.h"
 
 dhtnode_t *
 dhtnode_mkid(dhtnode_t *node)
 {
 	srand((unsigned int)time(NULL)*rand());
 
 	for (int i = 0; i < sizeof(node->id); i++)
 		node->id[i] = rand() & 0xFF;
 
 	return node;
 }
 
 dhtnode_t *
 dhtnode_setid(dhtnode_t *node, char id[IDLENGTH])
 {
 	memmove(node->id, id, sizeof(node->id));
 
 	return node;
 }
 
 dhtnode_t *
 dhtnode_setaddr(dhtnode_t *node, char *addr)
 {
 	node->addr = memdup(addr, strlen(addr)+1);
 
 	return node;
 }
 
 dhtnode_t *
 dhtnode_new(void)
 {
 	dhtnode_t *node;
 
 	node = mallocz(sizeof(dhtnode_t), 2);
 
 	return node;
 }
 
 void
 dhtnode_free(dhtnode_t *node)
 {
 	free(node);
 }
 
 void
 dhtnode_print(dhtnode_t *node)
 {
 	printf("dhtnode[id=");
 	for (int i = 0; i < sizeof(node->id); i++)
 		printf("%.2x", node->id[i] & 0xFF);
 	printf(", addr='");
 	if (node->addr != NULL)
 		printf("%s", node->addr);
 	printf("']\n");
 }
 
 int
 dhtnode_cmp(dhtnode_t *node1, dhtnode_t *node2)
 {
 	return memcmp(node1->id, node2->id, sizeof(node1->id));
 }
 
 dhtnode_t *
 dhtnode_xor(dhtnode_t *node1, dhtnode_t *node2)
 {
 	dhtnode_t *ret;
 
 	ret = dhtnode_new();
 	for (int i = 0; i < sizeof(ret->id); i++)
 		ret->id[i] = node1->id[i] ^ node2->id[i];
 
 	return ret;
 }
 
 int
 dhtnode_prefixlen(dhtnode_t *node)
 {
 	for (int i = 0; i < sizeof(node->id); i++)
 		for (int j = 0; j < 8; j++)
 			if ((node->id[i] >> (7-j)) & 0x1)
 				return i * 8 + j;
 	return sizeof(node->id) * 8 - 1;
 }
 
 dhtrouting_t *
 dhtrouting_new(dhtnode_t *node)
 {
 	dhtrouting_t *route;
 
 	route = mallocz(sizeof(dhtrouting_t), 2);
 	for (int i = 0; i < nelem(route->buckets); i++)
 		route->buckets[i] = dhtlist_new();
 	route->node = node;
 
 	return route;
 }
 
 void
 dhtrouting_free(dhtrouting_t *route)
 {
 
 	for (int i = 0; i < nelem(route->buckets); i++)
 		dhtlist_free(route->buckets[i]);
 	dhtnode_free(route->node);
 	free(route);
 }
 
 dhtrouting_t *
 dhtrouting_update(dhtrouting_t *route, dhtnode_t *node)
 {
 	dhtlist_t *bucket;
 	dhtlistelem_t *elem;
 	dhtnode_t *xornode;
 	int bucketnum;
 
 	xornode = dhtnode_xor(route->node, node);
 	bucketnum = dhtnode_prefixlen(xornode);
 	dhtnode_free(xornode);
 	bucket = route->buckets[bucketnum];
 
 	forodhtlist(bucket, elem)
 		if (!dhtnode_cmp(elem->node, node))
 			break;
 	if (elem == NULL) {
 		if (bucket->len < IDLENGTH)
 			dhtlist_push(bucket, node);
 		else
 			return NULL;
 	} else
 		dhtlist_move(bucket, elem, 0);
 
 	return route;
 }
 
 dhtlist_t *
 dhtrouting_sortnodes(dhtlist_t *dhtlist, dhtnode_t *target)
 {
 	dhtnode_t *xornode1, *xornode2, *swap;
 	int sorted;
 
 	sorted = 0;
 
 	while(!sorted) {
 		sorted = 1;
 		fordhtlist(dhtlist, elem) {
 			if (elem->next == NULL)
 				break;
 			xornode1 = dhtnode_xor(elem->node, target);
 			xornode2 = dhtnode_xor(elem->next->node, target);
 
 			if (dhtnode_cmp(xornode1, xornode2) > 0) {
 				swap = elem->next->node;
 				elem->next->node = elem->node;
 				elem->node = swap;
 				sorted = 0;
 			}
 			dhtnode_free(xornode1);
 			dhtnode_free(xornode2);
 		}
 	}
 
 	return dhtlist;
 }
 
 dhtlist_t *
 dhtrouting_addnodes(dhtlist_t *dhtlist, dhtlist_t *bucket, dhtnode_t *target,
 		int max)
 {
 	fordhtlist(bucket, elem) {
 		if (dhtlist->len >= max)
 			break;
 		dhtlist_add(dhtlist, elem->node);
 	}
 
 	return dhtrouting_sortnodes(dhtlist, target);
 }
 
 dhtlist_t *
 dhtrouting_findclosest(dhtrouting_t *route, dhtnode_t *target, int max)
 {
 	int bucketnum;
 	dhtnode_t *xornode;
 	dhtlist_t *retnodes;
 
 	retnodes = dhtlist_new();
 
 	xornode = dhtnode_xor(route->node, target);
 	bucketnum = dhtnode_prefixlen(xornode);
 	dhtnode_free(xornode);
 
 	dhtrouting_addnodes(retnodes, route->buckets[bucketnum], target, max);
 	for (int i = 1; ((bucketnum-i) >= 0
 				|| (bucketnum+i) < IDLENGTH * 8)
 			&& retnodes->len < max; i++) {
 		if (bucketnum-i >= 0) {
 			dhtrouting_addnodes(retnodes,
 					route->buckets[bucketnum-i],
 					target, max);
 		}
 		if (bucketnum+i < IDLENGTH * 8) {
 			dhtrouting_addnodes(retnodes,
 					route->buckets[bucketnum+i],
 					target, max);
 		}
 	}
 
 	return retnodes;
 }
 
 dht_t *
 dht_new(char *localhost)
 {
 	dht_t *dht;
 	dhtnode_t *node;
 
 	node = dhtnode_new();
 	dhtnode_mkid(node);
 	dhtnode_setaddr(node, localhost);
 
 	dht = mallocz(sizeof(dht_t), 2);
 	dht->routing = dhtrouting_new(node);
 
 	return dht;
 }
 
 void
 dht_free(dht_t *dht)
 {
 	dhtrouting_free(dht->routing);
 	free(dht);
 }
 
 dhtlist_t *
 dht_find(dht_t *dht, dhtnode_t *target, int max)
 {
 	return dhtrouting_findclosest(dht->routing, target, max);
 }
 
 dht_t *
 dht_update(dht_t *dht, dhtnode_t *node)
 {
 	dhtrouting_update(dht->routing, node);
 
 	return dht;
 }