Lab 5: Caches - Filesystem Caching

CS1234: Small Scale Application Development
============================================

Shell Commands: Problem Statement:  (1 mark)
----------------------------------

Write the command(s) to list all files and folders in the "Downloads" directory
that are modified in February. The output should list the full month February
(instead of Feb). The same command should work irrespective of the present
working directory.

Notes/Submission:
-----------------

- You are NOT allowed to use awk scripting. Use the basic commands available
  in bash shell to achieve the desired outcome.
- Submit the command(s) as comments in the provided C source file CS25B0XX/Q1.c.

C Programming: Problem statement:   (4 marks)
---------------------------------

You are writing a very rudimentary database system. The user queries the
application for a particular file and a particular line from the file.
Since reading the file from the fileystem repeatedly is expensive, you are
supposed to cache them in a MOST RECENTLY USED format.

Your task is to develop this database application such that it has a fixed
size cache for the read files, and is able to open new files on receiving
queries. You are supposed to use a doubly linked list to maintain the cache.
The cache has a fixed size of 20 entries, starting from the most recently used
to the least recently used.

Upon receiving a query
- if a file was already present in the cache, promote it to the top of the
  cache, making it the most recently used element
- if a file was not present in the cache, retrieve it from the filesystem, add
  it as the most recently used element, and remove the least recently used
  element of the cache. An entry to the cache reads the entire contents of the
  file and stores them in the cache.


Input format:
-------------

The input is a list of queries, each query in one line of STDIN.
The format of each query is as follows:

<filename> <line_number>

- The filename will not contain spaces
- The line number is 0 indexed and guaranteed to exist in the file.

Output format:
--------------

The output will contain the following: for each query, print

<filename> <contents of file at line number> <whether file was present in cache>

If the file was present in the cache, print "YES" without the quotes. If not,
print "NO" without the quotes.

After processing all the queries, print a summary of the cached files:


0 most_recent_file.txt
1 second_most.txt
2 ...
...
19 ...

NOTE: Only print the number of files in the cache. If there are fewer than 20
files, stop early. Look at the sample inputs and outputs for further 
clarification.


Constraints:
------------

- The file name will be at most 255 characters long.
- The line numbers will lie between 0 and 10,000, both inclusive.
- the length of each line will be between 1 to 999 characters, both inclusive.


Sample input:
-------------


contents of file1.txt:

foo
bar
bat
baz


contents of file2.txt:

spam
eggs
food
fuss


sample input 1:

./file1.txt 0
./file1.txt 2
./file1.txt 1

sample output 1:

./file1.txt foo NO
./file1.txt bat YES
./file1.txt bar YES
0 ./file1.txt

Explanation of the output: The first query to file1 does not encounter the file
in the cache. After reading and adding it to the cache, we have the following
cache:

- file1.txt

The subsequent calls all go to the cached file.


sample input 2:

./file1.txt 0
./file2.txt 2
./file1.txt 1

sample output 2:

./file1.txt foo NO
./file2.txt food NO
./file1.txt bar YES
0 ./file1.txt
1 ./file2.txt

Explanation of the output: The first query to file1 does not encounter the file
in the cache. After reading and adding it to the cache, we have the following
cache:

- file1.txt

The second query (to file2) does not encounter the file in the cache. After
reading and adding it to the cache, the cache looks like follows:

- file2.txt
- file1.txt

file2 is the most recently used, so it is added on the top of the cache.

The subsequent query finds file1 in the cache, and promotes it to the top. The
cache structure now is:

- file1.txt
- file2.txt

Notice that file1 got promoted to the top of the cache.


sample input 3:

./file1.txt 0
./file2.txt 0
./file3.txt 0
./file4.txt 0
./file5.txt 0
./file6.txt 0
./file7.txt 0
./file8.txt 0
./file9.txt 0
./file10.txt 0
./file11.txt 0
./file12.txt 0
./file13.txt 0
./file14.txt 0
./file15.txt 0
./file16.txt 0
./file17.txt 0
./file18.txt 0
./file19.txt 0
./file20.txt 0
./file21.txt 0

sample output 3 (words have been skipped here):

./file1.txt ... NO
./file2.txt ... NO
./file3.txt ... NO
./file4.txt ... NO
./file5.txt ... NO
./file6.txt ... NO
./file7.txt ... NO
./file8.txt ... NO
./file9.txt ... NO
./file10.txt ... NO
./file11.txt ... NO
./file12.txt ... NO
./file13.txt ... NO
./file14.txt ... NO
./file15.txt ... NO
./file16.txt ... NO
./file17.txt ... NO
./file18.txt ... NO
./file19.txt ... NO
./file20.txt ... NO
./file21.txt ... NO
0 ./file21.txt
1 ./file20.txt
2 ./file19.txt
3 ./file18.txt
4 ./file17.txt
5 ./file16.txt
6 ./file15.txt
7 ./file14.txt
8 ./file13.txt
9 ./file12.txt
10 ./file11.txt
11 ./file10.txt
12 ./file9.txt
13 ./file8.txt
14 ./file7.txt
15 ./file6.txt
16 ./file5.txt
17 ./file4.txt
18 ./file3.txt
19 ./file2.txt


Explanation of the output: should be straightforward. Notice that file1 got
removed from the cache when file21 was added to the cache, since it was the
least recently used.


Notes and Submission Guidelines:
--------------------------------

- DOUBLY LINKED LIST: You are strictly required to use a doubly linked list to
  maintain the cache. The use of an array for the cache is forbidden.
- Nodes: You are free to design the node of the linked list as you please.
- Output formatting: ensure that everything is separated by just one space.
- Local testing: Run check.sh to check the testcases locally.
- Submision:
  - Rename CS25B0XX to your roll number ALL IN CAPS.
  - Replace your roll number in config.sh.
  - Run submit.sh to submit the lab.

Meta: Doubly linked lists:
--------------------------

Doubly linked lists are different from singly linked lists, in that they contain
a pointer to both the previous and the next element of the list.

A simple representation is given below:

Singly linked list:

[ field,     /--->[ field2,     /---->[ field3,    /----> ...
  next ] ---/       next  ] ---/         next ]---/

Doubly linked list:

[ prev, <---------[ prev, <---------[ prev, <--------- ...
  field,            field,            field,
  next ] ---------> next ] ---------> next ] ---------> ...

Often, to simplify things, a usual strategy is to have dummy/sentinel nodes
for both the head and the tail of the linked list, and store them in a
different struct altogether to make access simpler. This reduces the complexity
and need for null checks in most of the cases.

Extras (ungraded):
------------------

Extension 1: Dynamic cache threshold

Instead of having a fixed cache size of 20 elements, have a dynamic cache size
supplied by the CLI instead.

./a.out 40

If the argument isn't supplied, it should default to 20 elements.

Extension 2: Caching individual lines

Instead of reading the entire file and caching it all at once, you are required
to now cache individual lines. Assume that the length of the individual lines
is now fixed to 40 characters. The YES/NO criterion is updated to reflect
whether the file AND the line were in the cache or not.

Extension 3: Invalidation of stale entries

If a file in the cache hasn't been queried in the past 'n' queries, remove it
from the cache. 'n' is the specified size of the cache.
