Question

Concurrent Key-Value Database

Implement a non-persistent, concurrent key-value database using the Reader/Writers algorithm.

- Use a hashmap as the underlying data structure. Inspiration is ok, however the implementation must be yours. The hashmap must be able to grow to fit new elements, but it does not need to reduce its size.

-- Linked lists? Positional arrays? All are fine.

- Keys and values are strings (char *)

- Operations are: get, put

Provided files:

- Implement the contract set in the provided header file (ht_*)

- Run the provided main.c file. It must verify that there are no mismatches.

---------------------------------------------------------------------------------------------------------------------------------------------------

/**

* HashTable

*/

typedef struct {

// Add your implementation here.

} ht_hash_table;

ht_hash_table* ht_new();

void ht_del_hash_table(ht_hash_table* ht);

void ht_insert(ht_hash_table* ht, const char* key, const char* value);

char* ht_search(ht_hash_table* ht, const char* key);

void ht_delete(ht_hash_table* h, const char* key);

---------------------------------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <string.h>

#include <pthread.h>

#include <stdbool.h>

#include "hashtable.h"

#define MAX_INSERT_THREADS 100

#define MAX_COMPARE_THREADS 1

#define KEY_LENGTH 3

#define VALUE_LENGTH 6

typedef struct {

ht_hash_table *ht;

char *key;

char *value;

} insert_item_t;

typedef struct {

ht_hash_table *ht;

char *key;

} search_item_t;

void *insert_worker(void* in)

{

insert_item_t *insert_item = (insert_item_t*)in;

printf("Inserting key: %s, value: %s\n", insert_item->key, insert_item->value);

ht_insert(insert_item->ht, insert_item->key, insert_item->value);

free(insert_item);

return NULL;

}

void *search(void *in)

{

search_item_t *search_item = (search_item_t*)in;

printf("Searching for key: %s\n", search_item->key);

char *value = ht_search(search_item->ht, search_item->key);

return (void*)value;

}

char *random_string(const int size, char **blacklist, size_t blacklist_count)

{

int upper = 90;

int lower = 65;

char *buffer = calloc(size + 1, sizeof(char));

bool found = false;

do {

FILE *f = fopen("/dev/urandom", "r");

fread(buffer, size, sizeof(char), f);

for (int i=0; i < size; i++) {

buffer[i] = (abs(buffer[i]) % (upper - lower + 1)) + lower;

}

fclose(f);

} while (found == true);

return buffer;

}

int main() {

ht_hash_table *ht = ht_new();

pthread_t insert_threads[MAX_INSERT_THREADS];

pthread_t compare_threads[MAX_COMPARE_THREADS];

int mismatch_count = 0;

char *keys[MAX_INSERT_THREADS];

char *values[MAX_INSERT_THREADS];

for (int i=0; i < MAX_INSERT_THREADS; i++) {

keys[i] = random_string(KEY_LENGTH, keys, MAX_INSERT_THREADS);

values[i] = random_string(VALUE_LENGTH, values, MAX_INSERT_THREADS);

insert_item_t *insert_item = malloc(sizeof(insert_item_t));

insert_item->ht = ht;

insert_item->key = keys[i];

insert_item->value = values[i];

pthread_create(&insert_threads[i], NULL, insert_worker, (void*) insert_item);

}

for (int i=0; i < MAX_INSERT_THREADS; i++) {

pthread_join(insert_threads[i], NULL);

}

for (int i=0; i < MAX_INSERT_THREADS;) {

for(int j=0; j < MAX_COMPARE_THREADS && i < MAX_INSERT_THREADS; i++, j++) {

search_item_t search_item = {ht, keys[i]};

pthread_create(&compare_threads[i], NULL, search, &search_item);

char *result;

pthread_join(compare_threads[i], (void**)&result);

if (strcmp(result, values[i]) != 0) {

printf("Mismatch. Expected:%s - Obtained: %s\n", values[i], result);

mismatch_count++;

}

}

for (int i=0; i < MAX_COMPARE_THREADS; i++) {

pthread_join(compare_threads[i], NULL);

}

}

for (int i=0; i < MAX_INSERT_THREADS; i++) {

free(keys[i]);

free(values[i]);

}

printf("Process ended. Mismatches found: %d", mismatch_count);

return 0;

}

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node{
char *key;
char *val;
struct node *next;
};
struct table{
int size;
struct node **list;
};
struct table *createTable(int size);
int hashCode(struct table t,char key);
void put(struct table t,char key,char *val);
char get(struct table t,char *key);

int main(){
struct table *t = createTable(500);
put(t,"key1","firstValue");
put(t,"key2","secondValue");
printf("%s",get(t,"key2"));
return 0;
}
struct table *createTable(int size){
struct table *t = (struct table*)malloc(sizeof(struct table));
t->size = size;
t->list = (struct node**)malloc(sizeof(struct node*)*size);
int i;
for(i=0;i<size;i++)
t->list[i] = NULL;
return t;
}
int hashCode(struct table t,char key){
int code = 0;
for (int i = 0; i < strlen(key); ++i)
{
code = code + key[i];
}
if(code<0)
return -(code%t->size);
return code%t->size;
}
void put(struct table t,char key,char *val){
int pos = hashCode(t,key);
struct node *list = t->list[pos];
struct node *newNode = (struct node*)malloc(sizeof(struct node));
struct node *temp = list;
while(temp){
if(temp->key==key){
temp->val = val;
return;
}
temp = temp->next;
}
newNode->key = key;
newNode->val = val;
newNode->next = list;
t->list[pos] = newNode;
}
char get(struct table t,char *key){
int pos = hashCode(t,key);
struct node *list = t->list[pos];
struct node *temp = list;
while(temp){
if(temp->key==key){
return temp->val;
}
temp = temp->next;
}
return NULL;
}