Architecture Phase1 Week5:HomeWork

refernced by:https://github.com/chrismoos/hash-ring

static int item_sort(const void a, const void b);

hashringt *hashringcreate(uint32t numReplicas, HASHFUNCTION hash_fn) {

hashringt *ring = NULL;

// numReplicas must be greater than or equal to 1

if (numReplicas <= 0) return NULL;

// Make sure that the HASH_FUNCTION is supported

if (hashfn != HASHFUNCTIONMD5 && hashfn != HASHFUNCTIONSHA1) return NULL;

ring = (hashringt*)malloc(sizeof(hashringt));

ring->numReplicas = numReplicas;

ring->nodes = NULL;

ring->items = NULL;

ring->numNodes = 0;

ring->numItems = 0;

ring->hashfn = hashfn;

ring->mode = HASHRINGMODE_NORMAL;

return ring;

}

void hashringfree(hashringt *ring) {

if (ring == NULL) return;

// Clean up the nodes

ll_t tmp, cur = ring->nodes;

while (cur != NULL) {

free(((hashringnode_t*)cur->data)->name);

free(cur->data);

tmp = cur;

cur = tmp->next;

free(tmp);

}

ring->nodes = NULL;

// Clean up the items

int x;

for (x = 0; x < ring->numItems; x++) {

free(ring->items[x]);

}

if (ring->items != NULL) free(ring->items);

free(ring);

}

static int hashringhash(hashringt ring, uint8_t data, uint8t dataLen, uint64t *hash) {

if (ring->hashfn == HASHFUNCTION_MD5) {

uint8_t digest[16];

md5statet state;

md5_init(&state);

md5append(&state, (md5byte_t*)data, dataLen);

md5finish(&state, (md5byte_t*)&digest);

if (ring->mode == HASHRINGMODE_LIBMEMCACHED_COMPAT) {

uint32_t low = (digest[3] << 24 | digest[2] << 16 | digest[1] << 8 | digest[0]);

uint64_t keyInt;

keyInt = low;

*hash = keyInt;

return 0;

}

else {

uint32_t low = (digest[11] << 24 | digest[10] << 16 | digest[9] << 8 | digest[8]);

uint32_t high = (digest[15] << 24 | digest[14] << 16 | digest[13] << 8 | digest[12]);

uint64_t keyInt;

keyInt = high;

keyInt <<= 32;

keyInt &= 0xffffffff00000000LLU;

keyInt |= low;

*hash = keyInt;

return 0;

}

}

else if (ring->hashfn == HASHFUNCTION_SHA1) {

SHA1Context sha1_ctx;

SHA1Reset(&sha1_ctx);

SHA1Input(&sha1_ctx, data, dataLen);

if (SHA1Result(&sha1_ctx) != 1) {

return -1;

}

uint64t keyInt = sha1ctx.Message_Digest[3];

keyInt <<= 32;

keyInt |= sha1ctx.MessageDigest[4];

*hash = keyInt;

return 0;

}

else {

return -1;

}

}

void hashringprint(hashringt *ring) {

if (ring == NULL) return;

int x, y;

printf("----------------------------------------\n");

printf("hash_ring\n\n");

printf("numReplicas:%8d\n", ring->numReplicas);

printf("Nodes: \n\n");

ll_t *cur = ring->nodes;

x = 0;

while (cur != NULL) {

printf("%d: ", x);

hashringnode_t node = (hash_ring_node_t)cur->data;

for (y = 0; y < node->nameLen; y++) {

printf("%c", node->name[y]);

}

printf("\n");

cur = cur->next;

x++;

}

printf("\n");

printf("Items (%d): \n\n", ring->numItems);

for (x = 0; x < ring->numItems; x++) {

hashringitem_t *item = ring->items[x];

printf("%" PRIu64 " : ", item->number);

for (y = 0; y < item->node->nameLen; y++) {

printf("%c", item->node->name[y]);

}

printf("\n");

}

printf("\n");

printf("----------------------------------------\n");

}

int hashringadd_items(hash_ring_t ring, hash_ring_node_t node) {

int x;

char concat_buf[8];

int concat_len;

uint64_t keyInt;

// Resize the items array

void resized = realloc(ring->items, (sizeof(hash_ring_item_t) * ring->numNodes * ring->numReplicas));

if (resized == NULL) {

return HASHRINGERR;

}

ring->items = (hashringitem_t**)resized;

for (x = 0; x < ring->numReplicas; x++) {

if (ring->mode == HASHRINGMODE_LIBMEMCACHED_COMPAT) {

concatlen = snprintf(concatbuf, sizeof(concat_buf), "-%d", x);

}

else {

concatlen = snprintf(concatbuf, sizeof(concat_buf), "%d", x);

}

uint8_t data = (uint8_t)malloc(concat_len + node->nameLen);

memcpy(data, node->name, node->nameLen);

memcpy(data + node->nameLen, &concatbuf, concatlen);

if (hashringhash(ring, data, concat_len + node->nameLen, &keyInt) == -1) {

free(data);

return HASHRINGERR;

}

free(data);

hashringitem_t item = (hash_ring_item_t)malloc(sizeof(hashringitem_t));

item->node = node;

item->number = keyInt;

ring->items[(ring->numNodes - 1) * ring->numReplicas + x] = item;

}

ring->numItems += ring->numReplicas;

return HASHRINGOK;

}

static int item_sort(const void a, const void b) {

hashringitem_t itemA = (hashringitem_t*)a, itemB = (hash_ring_item_t*)b;

if (itemA == NULL) return 1;

if (itemB == NULL) return -1;

if (itemA->number < itemB->number) {

return -1;

}

else if (itemA->number > itemB->number) {

return 1;

}

else {

return 0;

}

}

int hashringadd_node(hash_ring_t ring, uint8_t name, uint32_t nameLen) {

if (ring == NULL) return HASHRINGERR;

if (hashringget_node(ring, name, nameLen) != NULL) return HASH_RING_ERR;

if (name == NULL || nameLen <= 0) return HASHRINGERR;

hashringnode_t node = (hash_ring_node_t)malloc(sizeof(hashringnode_t));

if (node == NULL) {

return HASHRINGERR;

}

node->name = (uint8_t*)malloc(nameLen);

if (node->name == NULL) {

free(node);

return HASHRINGERR;

}

memcpy(node->name, name, nameLen);

node->nameLen = nameLen;

ll_t cur = (ll_t)malloc(sizeof(ll_t));

if (cur == NULL) {

free(node->name);

free(node);

return HASHRINGERR;

}

cur->data = node;

// Add the node

ll_t *tmp = ring->nodes;

ring->nodes = cur;

ring->nodes->next = tmp;

ring->numNodes++;

// Add the items for this node

if (hashringadd_items(ring, node) != HASH_RING_OK) {

hashringremove_node(ring, node->name, node->nameLen);

return HASHRINGERR;

}

// Sort the items

qsort((void*)ring->items, ring->numItems, sizeof(struct hash_ring_item_t), item_sort);

return HASHRINGOK;

}

int hashringremovenode(hashring_t ring, uint8_t name, uint32_t nameLen) {

if (ring == NULL || name == NULL || nameLen <= 0) return HASHRINGERR;

hashringnode_t *node;

ll_t next, prev = NULL, *cur = ring->nodes;

while (cur != NULL) {

node = (hashringnode_t*)cur->data;

if (node->nameLen == nameLen &&

memcmp(node->name, name, nameLen) == 0) {

// Node found, remove it

next = cur->next;

free(node->name);

if (prev == NULL) {

ring->nodes = next;

}

else {

prev->next = next;

}

int x;

// Remove all items for this node and mark them as NULL

for (x = 0; x < ring->numItems; x++) {

if (ring->items[x]->node == node) {

free(ring->items[x]);

ring->items[x] = NULL;

}

}

// By re-sorting, all the NULLs will be at the end of the array

// Then the numItems is reset and that memory is no longer used

qsort((void*)ring->items, ring->numItems, sizeof(struct hash_ring_item_t), item_sort);

ring->numItems -= ring->numReplicas;

free(node);

free(cur);

ring->numNodes--;

return HASHRINGOK;

}

prev = cur;

cur = prev->next;

}

return HASHRINGERR;

}

hashringnode_t hash_ring_get_node(hash_ring_t ring, uint8t *name, uint32t nameLen) {

if (ring == NULL || name == NULL || nameLen <= 0) return NULL;

ll_t *cur = ring->nodes;

while (cur != NULL) {

hashringnode_t node = (hash_ring_node_t)cur->data;

// Check if the nameLen is the same as well as the name

if (node->nameLen == nameLen &&

memcmp(node->name, name, nameLen) == 0) {

return node;

}

cur = cur->next;

}

return NULL;

}

hashringitem_t hash_ring_find_next_highest_item(hash_ring_t ring, uint64_t num) {

if (ring->numItems == 0) return NULL;

int min = 0;

int max = ring->numItems - 1;

hashringitem_t *item = NULL;

while (1) {

if (min > max) {

if (min == ring->numItems) {

// Past the end of the ring, return the first item

return ring->items[0];

}

else {

// Return the next highest item

return ring->items[min];

}

}

int midpointIndex = (min + max) / 2;

item = ring->items[midpointIndex];

if (item->number > num) {

// Key is in the lower half

max = midpointIndex - 1;

}

else if (item->number <= num) {

// Key is in the upper half

min = midpointIndex + 1;

}

}

return NULL;

}

hashringnode_t hash_ring_find_node(hash_ring_t ring, uint8t *key, uint32t keyLen) {

if (ring == NULL || key == NULL || keyLen <= 0) return NULL;

uint64_t keyInt;

if (hashringhash(ring, key, keyLen, &keyInt) == -1) return NULL;

hashringitem_t *item = hash_ringfindnext_highest_item(ring, keyInt);

if (item == NULL) {

return NULL;

}

else {

return item->node;

}

}

/*

* Consistently hash the key to num nodes;

* returns the number of nodes found, or -1 if there is an error

*/

int hashringfind_nodes(

hashringt *ring,

uint8_t *key,

uint32_t keyLen,

hashringnode_t *nodes[],

uint32_t num) {

// the number of nodes we're going to return is either the number of nodes

// requested, or the number of nodes available

int ret = ring->numNodes < num ? ring->numNodes : num;

uint64_t keyInt;

if (hashringhash(ring, key, keyLen, &keyInt) == -1) return -1;

hashringitem_t *item;

int x = 0;

int seen;

int i;

while (1) {

item = hashringfind_next_highest_item(ring, keyInt);

if (item == NULL) return -1;

keyInt = item->number;

// if we've already included this node, skip it

seen = 0;

for (i = 0; i < x; i++) {

if (item->node == nodes[i]) {

seen = 1;

break;

}

}

if (seen) continue;

nodes[x] = item->node;

x++;

if (x == ret) break;

}

return ret;

}

int hashringset_mode(hash_ringt *ring, HASHMODE mode) {

if (ring == NULL) return HASHRINGERR;

if (mode == HASHRINGMODE_LIBMEMCACHED_COMPAT) {

if (ring->hashfn != HASHFUNCTIONMD5) return HASHRING_ERR;

ring->mode = mode;

return HASHRINGOK;

}

else if (mode == HASHRINGMODE_NORMAL) {

ring->mode = mode;

return HASHRINGOK;

}

else {

/ Invalid mode /

return HASHRINGERR;

}

}