From f9a7d9cd8a7e603c89d4cc5d98d7f694cc217d85 Mon Sep 17 00:00:00 2001
From: Soikk
Date: Sat, 6 Aug 2022 21:46:45 +0200
Subject: Refactored database. Replaced htable with ctable (same thing
 different name). Introduced AVL tree for hashes.

---
 include/database.h |  6 +++--
 include/storage.h  | 65 ++++++++++++++++++++++++++++++++++++++++--------------
 2 files changed, 52 insertions(+), 19 deletions(-)

(limited to 'include')

diff --git a/include/database.h b/include/database.h
index bcade34..5f2d99d 100644
--- a/include/database.h
+++ b/include/database.h
@@ -7,8 +7,8 @@
 typedef struct database{
 	char name[32];
 	ltable *lfiles, *ltags;
-	htable *hfiles, *htags;
-	htable *fcount, *tcount;
+	ctable *cfiles, *ctags;
+	tree hfiles, htags;
 	mtable *map;
 } database;
 
@@ -33,6 +33,8 @@ int searchTag(database *db, char *tag, uint64_t n, uint64_t **r, uint64_t *rl);
 
 void printDatabase(database *db);
 
+void debugAVLtree(node *n);
+
 void debugDatabase(database *db);
 
 #endif
diff --git a/include/storage.h b/include/storage.h
index ebf2dc2..8bfc751 100644
--- a/include/storage.h
+++ b/include/storage.h
@@ -60,11 +60,11 @@ typedef struct lookupTable{
 	char **table; // They cant be longer than MAXPATH
 } ltable;
 
-// Stores the hashes of the filepaths/tags (for easier lookup)
-typedef struct hashTable{
+// Stores a number (used as the count for files and tags in the mapping table)
+typedef struct countTable{
 	uint64_t size;
 	uint64_t *table;
-} htable;
+} ctable;
 
 typedef struct relation{
 	uint64_t file;
@@ -77,42 +77,73 @@ typedef struct mappingTable{
 	relation *table;
 } mtable;
 
+// Stores a hash and an index (hash table implemented with an AVL tree) for easier lookup
+typedef struct AVLnode{
+	uint64_t h;
+	uint64_t i;
+	struct AVLnode *left;
+	struct AVLnode *right;
+} node;
 
-// LTABLE
-ltable *newLtable(uint64_t size);
+typedef node* tree;
 
-ltable *loadLtable(FILE *fp);
 
-int storeLtable(const ltable *lt, FILE *fp);
+// LTABLE
+
+ltable *newLtable(uint64_t size);
 
 int ltableAdd(ltable *lt, char *str);
 
 uint64_t ltableSearch(ltable *lt, char *str);
 
-// HTABLE
+int storeLtable(const ltable *lt, FILE *fp);
+
+ltable *loadLtable(FILE *fp);
+
+// CTABLE
 
-htable *newHtable(uint64_t size);
+ctable *newCtable(uint64_t size);
 
-htable *loadHtable(FILE *fp);
+int ctableAdd(ctable *ct, uint64_t n);
 
-int storeHtable(const htable *ht, FILE *fp);
+int ctableDelete(ctable *ct, uint64_t n);
 
-int htableAdd(htable *ht, uint64_t h);
+uint64_t ctableSearch(ctable *ct, uint64_t n);
 
-uint64_t htableSearch(htable *ht, uint64_t h);
+int storeCtable(const ctable *ht, FILE *fp);
 
-int htableDelete(htable *ht, uint64_t h);
+ctable *loadCtable(FILE *fp);
 
 // MTABLE
 
 mtable *newMtable(uint64_t size);
 
-mtable *loadMtable(FILE *fp);
+int mtableAdd(mtable *mt, relation r);
+
+uint64_t mtableSearch(mtable *mt, relation r);
+
+uint64_t mtableSearchFile(mtable *mt, uint64_t file);
+
+uint64_t mtableSearchTag(mtable *mt, uint64_t tag);
 
 int storeMtable(const mtable *mt, FILE *fp);
 
-int mtableAdd(mtable *mt, relation r);
+mtable *loadMtable(FILE *fp);
 
-uint64_t mtableSearch(mtable *mt, relation r);
+// AVL TREE
+
+uint64_t height(node *n);
+
+node *newNode(uint64_t h, uint64_t i);
+
+node *insertNode(node *r, uint64_t h, uint64_t i);
+
+node *deleteNode(node *r, uint64_t h);
+
+uint64_t nodeSearch(node *n, uint64_t h);
+
+int storeAVLTree(tree root, FILE *fp);
+
+tree loadAVLTree(FILE *fp);
 
 #endif
-- 
cgit v1.2.3