1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
#ifndef STORAGE_H
#define STORAGE_H
#include "db.h"
/* (From tags.h)
tags are stored in a big table (or their hashes are) ordered
by alphabetical order
tags can have namespaces which are a special tag that starts
with a ':'
all tags in a namespace are located between two occurrences
of the namespace within the list,
e.g [":people", "sam hyde", "hitler", ":people"]
maybe namespaces use another hashing function to prevent
collisions because of the lack of space because of the ':'
*/
/*
tags are stored in a big table (or their hashes are) ordered
by alphabetical order
tags can have namespaces which are a special tag that starts
with a ':'
all tags in a namespace are located between two occurrences
of the namespace within the list,
e.g [":people", "sam hyde", "hitler", ":people"]
maybe namespaces use another hashing function to prevent
collisions because of the lack of space because of the ':'
files (their paths) are stored in a big table (or their hashes
are) by alphabetical/numerical order
tags and files' indexes on their respective tables correspond
to the index of the actual tag or file on alookup table.
e.g
iT[23] = 816820769819429900 = hash(lT[23]) = hash("cacadevaca")
there is another table that ties the two together by their
indexes
if an file has more than one tag, it is stored as multiple
relations inside the table, e.g ["1:2", "1:3", "1:4"]
searching for an file that has a tag is as simple as
- finding the tag on its list
- if the tag is on the list, getting its index number
if not, return 'tag not found'
- search for all the relations that have the index as
the second argument
- if no files are found, return 'files not found'
- store the indexes of all the files (the first argument)
- return the list of all the files
- (OPTIONAL) show all the other tags the files shown have
*/
#define MAXPATH 4096
// Stores the actual filepaths/tags
typedef struct lookupTable{
uint64_t size;
char **table; // They cant be longer than MAXPATH
} ltable;
// Stores a number (used as the count for files and tags in the mapping table)
typedef struct countTable{
uint64_t size;
uint64_t *table;
} ctable;
typedef struct relation{
uint64_t file;
uint64_t tag;
} relation;
// Maps the relations between the filepaths and the tags
typedef struct mappingTable{
uint64_t size;
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;
typedef node* tree;
// LTABLE
ltable *newLtable(uint64_t size);
int ltableAdd(ltable *lt, char *str);
uint64_t ltableSearch(ltable *lt, char *str);
int storeLtable(const ltable *lt, FILE *fp);
ltable *loadLtable(FILE *fp);
// CTABLE
ctable *newCtable(uint64_t size);
int ctableAdd(ctable *ct, uint64_t n);
int ctableDelete(ctable *ct, uint64_t n);
uint64_t ctableSearch(ctable *ct, uint64_t n);
int storeCtable(const ctable *ht, FILE *fp);
ctable *loadCtable(FILE *fp);
// MTABLE
mtable *newMtable(uint64_t size);
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);
mtable *loadMtable(FILE *fp);
// 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
|
