aboutsummaryrefslogtreecommitdiff
path: root/miniDB
diff options
context:
space:
mode:
Diffstat (limited to 'miniDB')
-rw-r--r--miniDB/HashMap.c247
-rw-r--r--miniDB/HashMap.h30
-rw-r--r--miniDB/db_commands.c97
-rw-r--r--miniDB/db_commands.h12
-rw-r--r--miniDB/main.c28
5 files changed, 414 insertions, 0 deletions
diff --git a/miniDB/HashMap.c b/miniDB/HashMap.c
new file mode 100644
index 0000000..af35308
--- /dev/null
+++ b/miniDB/HashMap.c
@@ -0,0 +1,247 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "HashMap.h"
+
+#define DELETED -1
+#define OCCUPIED 1
+#define EMPTY 0
+
+struct hashTable;
+struct Entry *__FIND(struct hashTable *self, const char *key);
+float __LOAD_FACTOR(struct hashTable *self);
+struct hashTable *createTable();
+void __RE_HASHER(struct hashTable *self);
+
+
+
+
+
+// private methods
+
+//
+
+unsigned int __GET_BUCKET(const char *key, int buckets) {
+
+ unsigned int hash = 0;
+
+ unsigned int bucket;
+
+ for(int i = 0; key[i] != '\0'; i++) {
+ hash = hash * 31 + key[i];
+ }
+
+ bucket = hash % buckets;
+
+ return bucket;
+}
+
+void __INSERT (struct hashTable *self, const char *key, int value) {
+
+ if(__LOAD_FACTOR(self) >= 0.75 || self->__tombs > self->__count) {
+ __RE_HASHER(self);
+ self->__tombs = 0;
+ }
+
+ struct Entry *found = __FIND(self, key);
+
+ if(found != NULL) {
+ found->__value = value;
+ return;
+ }
+
+ unsigned int bucket = __GET_BUCKET(key, self->__buckets);
+ int iterations = 0;
+ while(iterations < self->__buckets) {
+ if(self->__items[bucket].__state == EMPTY || self->__items[bucket].__state == DELETED) {
+ self->__items[bucket].__value = value;
+ self->__items[bucket].__key = malloc(strlen(key) + 1);
+ strcpy(self->__items[bucket].__key, key);
+ self->__items[bucket].__state = OCCUPIED;
+ self->__count++;
+ return;
+ }
+ else {
+ bucket++;
+ if(bucket >= self->__buckets) {
+ bucket = 0;
+ }
+ }
+ iterations++;
+ };
+
+ printf("INSERTION FAILED\n");
+ return;
+}
+
+struct Entry *__FIND(struct hashTable *self, const char *key) {
+
+ unsigned int bucket = __GET_BUCKET(key, self->__buckets);
+
+ int iterations = 0;
+ while(iterations < self->__buckets) {
+ if(self->__items[bucket].__state == EMPTY) break;
+ if(self->__items[bucket].__state != DELETED) {
+ if(strcmp(self->__items[bucket].__key, key) == 0) {
+ return &self->__items[bucket];
+ }
+ }
+
+ bucket = (bucket + 1) % self->__buckets;
+ iterations++;
+ }
+
+ return NULL;
+}
+
+void __DUMP (struct hashTable *self) {
+ for(int i = 0; i < self->__buckets; i++) {
+ printf("|Slot: (%d), State: (%d), Key: (%s), Value: (%d)|\n", i, self->__items[i].__state, self->__items[i].__key, self->__items[i].__value);
+ }
+}
+
+void __DESTRUCTOR(struct hashTable *self) {
+
+ int iterations = 0;
+ while(iterations < self->__buckets) {
+ if(self->__items[iterations].__key != NULL) {
+ free(self->__items[iterations].__key);
+ self->__items[iterations].__key = NULL;
+ }
+ iterations++;
+ }
+
+ free(self->__items);
+ self->__items = NULL;
+
+ free(self);
+}
+
+void __DELETE(struct hashTable *self, const char *key) {
+
+ struct Entry *found = __FIND(self, key);
+
+ if(!found) {
+ printf("DOESNT EXIST!\n");
+ return;
+ }
+
+ found->__state = DELETED;
+ found->__value = 0;
+ self->__count--;
+ self->__tombs++;
+ free(found->__key);
+ found->__key = NULL;
+}
+
+float __LOAD_FACTOR(struct hashTable *self) {
+
+ float retval = (float)self->__count / self->__buckets;
+
+ return retval;
+}
+
+
+void __RE_HASHER(struct hashTable *self) {
+
+ struct Entry *old_items = self->__items;
+ int old_buckets = self->__buckets;
+
+ if(self->__tombs > self->__count) {
+ self->__items = calloc(self->__buckets, sizeof(struct Entry));
+ self->__count = 0;
+ for (int i = 0; i < old_buckets; i++) {
+ if (old_items[i].__state == OCCUPIED) {
+ __INSERT(self,
+ old_items[i].__key,
+ old_items[i].__value);
+
+ free(old_items[i].__key);
+ }
+ }
+ free(old_items);
+ return;
+ }
+
+ self->__items = calloc(old_buckets * 2, sizeof(struct Entry));
+ self->__buckets = old_buckets * 2;
+ self->__count = 0;
+
+ for (int i = 0; i < old_buckets; i++) {
+ if (old_items[i].__state == OCCUPIED) {
+ __INSERT(self,
+ old_items[i].__key,
+ old_items[i].__value);
+
+ free(old_items[i].__key);
+ }
+ }
+
+ free(old_items);
+}
+
+
+
+
+// Public method(s)
+
+struct hashTable *createTable() {
+
+ struct hashTable *t = malloc(sizeof(*t));
+
+ t->__count = 0;
+ t->__buckets = 2;
+ t->__tombs = 0;
+ t->__items = calloc(t->__buckets, sizeof(struct Entry));
+ t->insert = &__INSERT;
+ t->dump = &__DUMP;
+ t->find = &__FIND;
+ t->destructor = &__DESTRUCTOR;
+ t->pop = &__DELETE;
+ t->factor = &__LOAD_FACTOR;
+
+ return t;
+}
+
+// input functions (Public)
+
+int intger_input() {
+
+ int tmp;
+
+ while (1) {
+
+ if ((scanf("%d", &tmp)) == 1) {
+ while (getchar() != '\n')
+ ;
+ break;
+ }
+
+ while (getchar() != '\n')
+ ;
+ printf("Invalid input, try again: ");
+ }
+
+ return tmp;
+}
+
+char *read_line() {
+
+ char buffer[1024];
+
+ if (fgets(buffer, sizeof(buffer), stdin) == NULL) {
+ return NULL;
+ }
+ if(buffer[0] == '\n') {
+ return NULL;;
+ }
+
+ char *result = NULL;
+ result = malloc(strlen(buffer) + 1);
+
+ strcpy(result, buffer);
+
+ result[strcspn(result, "\n")] = '\0';
+
+ return result;
+} \ No newline at end of file
diff --git a/miniDB/HashMap.h b/miniDB/HashMap.h
new file mode 100644
index 0000000..0698d3b
--- /dev/null
+++ b/miniDB/HashMap.h
@@ -0,0 +1,30 @@
+#ifndef HASHM_H
+#define HASHM_H
+
+struct hashTable {
+ int __count;
+ int __buckets;
+ struct Entry *__items;
+ int __tombs;
+
+ // public methods
+
+ void (*insert)(struct hashTable *self, const char *key, int value);
+ void (*dump)(struct hashTable *self);
+ struct Entry *(*find)(struct hashTable *self, const char *key);
+ void (*destructor)(struct hashTable *self);
+ void (*pop)(struct hashTable *self, const char *key);
+ float (*factor)(struct hashTable *self);
+};
+
+struct Entry {
+ int __value;
+ char *__key;
+ int __state;
+};
+
+char *read_line();
+int intger_input();
+struct hashTable *createTable();
+
+#endif \ No newline at end of file
diff --git a/miniDB/db_commands.c b/miniDB/db_commands.c
new file mode 100644
index 0000000..4e6edae
--- /dev/null
+++ b/miniDB/db_commands.c
@@ -0,0 +1,97 @@
+#include "HashMap.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define SUCCESS 1
+#define FAILED 0
+#define EXIT -1
+
+void parse(char *input, char *tokens[], int max_tokens) {
+
+ int i = 0;
+
+ char *token = strtok(input, " ");
+
+ while (token != NULL && i < max_tokens) {
+
+ tokens[i] = token;
+
+ i++;
+
+ token = strtok(NULL, " ");
+ }
+}
+
+int db_commands(struct hashTable *self, FILE *fh, char *fileName) {
+
+ printf("db> ");
+
+ char *input = read_line();
+ if (!input) {
+ return FAILED;
+ }
+
+ char *tokens[3];
+
+ parse(input, tokens, 3);
+
+ char *endptr;
+
+ int value = strtol(tokens[2], &endptr, 10);
+
+ if (strcmp(tokens[0], "INSERT") == 0) {
+
+ if (*endptr != '\0')
+ return FAILED;
+
+ self->insert(self, tokens[1], value);
+ return SUCCESS;
+ } else if (strcmp(tokens[0], "EXIT") == 0) {
+ printf("BYE\n");
+ return EXIT;
+ } else if (strcmp(tokens[0], "GET") == 0) {
+ struct Entry *cur = self->find(self, tokens[1]);
+ if (cur) {
+ printf("%d\n", cur->__value);
+ return SUCCESS;
+ }
+ return FAILED;
+ } else if (strcmp(tokens[0], "DELETE") == 0) {
+ self->pop(self, tokens[1]);
+ } else if (strcmp(tokens[0], "SAVE") == 0) {
+ fh = fopen(fileName, "w");
+
+ int iteratorCount = 0;
+
+ while (iteratorCount < self->__buckets) {
+ if (self->__items[iteratorCount].__key == NULL) {
+ iteratorCount++;
+ continue;
+ }
+ fprintf(fh, "%s %d\n", self->__items[iteratorCount].__key, self->__items[iteratorCount].__value);
+ iteratorCount++;
+ }
+
+ fclose(fh);
+ return SUCCESS;
+ } else if (strcmp(tokens[0], "LOAD") == 0) {
+ tokens[1] = fileName;
+ fh = fopen(tokens[1], "r");
+
+ char key[100];
+ int val;
+ while (fscanf(fh, "%s %d\n", key, &val) == 2) {
+ self->insert(self, key, val);
+ }
+ fclose(fh);
+ return SUCCESS;
+ } else if (strcmp(tokens[0], "HELP") == 0) {
+ printf("INSERT <key> <value>\nDELETE <key>\nGET <key>\nSAVE\nLOAD <filename>\nEXIT\nDUMPTBL\n");
+ return SUCCESS;
+ }
+ else if(strcmp(tokens[0], "DUMPTBL") == 0) {
+ self->dump(self);
+ }
+ return FAILED;
+} \ No newline at end of file
diff --git a/miniDB/db_commands.h b/miniDB/db_commands.h
new file mode 100644
index 0000000..3e9ec79
--- /dev/null
+++ b/miniDB/db_commands.h
@@ -0,0 +1,12 @@
+#ifndef DB_COMMANDS_H
+#define DB_COMMANDS_H
+
+#include "HashMap.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdlib.h>
+
+void parse(char *input, char *tokens[], int max_tokens);
+int db_commands(struct hashTable *self, FILE *fh, char *fileName);
+
+#endif \ No newline at end of file
diff --git a/miniDB/main.c b/miniDB/main.c
new file mode 100644
index 0000000..f6ce5d0
--- /dev/null
+++ b/miniDB/main.c
@@ -0,0 +1,28 @@
+#include "HashMap.h"
+#include "db_commands.h"
+#include <stdio.h>
+
+
+
+
+int main() {
+
+ struct hashTable *t1 = createTable();
+ FILE *fh = NULL;
+ printf("Enter a filename for the database, otherwise press ENTER: ");
+ char *fileName = read_line();
+ if(!fileName) {
+ fileName = "db.txt";
+ printf("Default name picked up: %s\n", fileName);
+ }
+
+
+ int exitState = -1;
+ while (db_commands(t1, fh, fileName) != exitState) {
+ printf("");
+ }
+
+ t1->destructor(t1);
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2026-07-07 19:52:17 +0000