File-Indexer

Multi-threaded text file indexing command line application.

System Info:

Linux 4.16.0-rc4 #3 SMP Sat Mar 10 02:42:36 EST 2018 x86_64 x86_64 x86_64 GNU/Linux
gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-16)

Configuration:

git clone https://github.com/prafful1/File-Indexer.git
cd File-Indexer
Run "make"
Generates "bin" and "obj" directory.
Generates "file_indexer" binary in "bin" folder.
Run following command in "bin" folder: "./file_indexer <Directory_Path>".
Run "make clean" to delete files from "obj/" and "bin/" folder.

Output:

Input Command: ./file_indexer /root/text_files-dir
Sample Output:
######################################################
Scanner Thread started
######################################################
Worker Thread 1 started
######################################################
Worker Thread 2 started
######################################################
Worker Thread 3 started
File Path extracted from message queue /root/text_files-dir/file2.txt
######################################################
Worker Thread 4 started
File Path extracted from message queue /root/text_files-dir/pqrs/pqrs2/zmap.txt
######################################################
File Path extracted from message queue /root/text_files-dir/pqrs/text.txt
File Path extracted from message queue /root/text_files-dir/pqrs/file3.txt
File Path extracted from message queue /root/text_files-dir/pqrs/file.txt
File Path extracted from message queue /root/text_files-dir/b.txt
File Path extracted from message queue /root/text_files-dir/file.txt
File Path extracted from message queue /root/text_files-dir/abcd/e.txt
File Path extracted from message queue /root/text_files-dir/abcd/c.txt
File Path extracted from message queue /root/text_files-dir/abcd/file3.txt
Word: the, Frequency: 95
Word: and, Frequency: 70
Word: to, Frequency: 67
Word: of, Frequency: 50
Word: that, Frequency: 49
Word: a, Frequency: 48
Word: in, Frequency: 38
Word: is, Frequency: 33
Word: about, Frequency: 30
Word: authors, Frequency: 25

Design:

1 scanner thread that recursively iterates through <Directory_Path> and searches for all ".txt" files.
Scanner thread adds all paths to message queue.
Message Queue is implemented with a singly linked list.
A Scanner thread acquires write lock on linked-list and adds a new node to the tail of list with ".txt" file path in it.
Linked-list is used as message queue because it can dynamically grow in size.
4 worker threads, read file paths from Message Queue in parallel.
Each worker thread acquires write lock on message queue and reads file path from top. Worker thread removes top element and reads file path.
After node is removed from front, lock on message queue is released.
Each worker thread reads a file provided to them, tokenizes words in each line on the basis of following delimeter " .,-".
Each word is added to hash_map. If word is not available in hash_map, then word is added to map with counter set to 1. If word is already available, counter is incremented.
I provided my own implementaion of thread safe Hash Map.
Every time, a word is added to map, a write lock is aquired and then added.
In case of collison, next available is being looked and word is added to that bucket.
Current implementation of hash map only supports a maximum of 1000000 words.
After all worker threads are done writing into hash map, they exit.
main thread runs through hash_map and searches for Top 10 words with maximum frequency and prints that on console.

Current Implementation:

1 Scanner Thread. Can be increased.
4 Worker Threads. Can be changed.
Hash_Map can store a maximum of 1000000 unique words. Can be changed.