LRUcache - Least Recently Used cache implementation for reading file data
=========================================================================

=> COMPILE:
-----------

$ make clean
$ make debug

=> TEST DATA:
-------------

$ bash +x ./testdata.sh

=> EXECUTE:
-----------

$ ./LRUcache

=> Performance Analysis:
========================

--> Read over network (1KB, 10KB, 100KB, 1MB, 10MB, 1GB):
-------------------------------------------------------

----> File Size (vs) Wall clock time


      +--+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--+*
      +          +           +          +           +    Cache Miss *******+
  400 ++                                                  Cache Hit #####*++
      |                                                                 *  |
      |                                                                 *  |
  300 ++                                                               *  ++
      |                                                               *    |
      |                                                              *     |
  200 ++                                                            *     ++
      |                                                            *       |
      |                                                            *       |
      |                                                           *        |
  100 ++                                                         *        ++
      |                                                      ****          |
      |                                                ******              |
    0 *************************************************#####################
      |                                                                    |
      +          +           +          +           +          +           +
 -100 ++-+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--++
     1000      10000       100000     1e+06       1e+07      1e+08       1e+09
                              File Size (in Bytes)


----> File Size (vs) CPU


    3 ++-+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--+*
      +          +           +          +           +    Cache Miss *******+
  2.5 ++                                                  Cache Hit #####*++
      |                                                                 *  |
    2 ++                                                               *  ++
      |                                                               *    |
      |                                                               *    |
  1.5 ++                                                             *    ++
      |                                                             *      |
    1 ++                                                           *      ++
      |                                                           *        |
  0.5 ++                                                         *        ++
      |                                                   *******          |
    0 ****************************************************##################
      |                                                                    |
      |                                                                    |
 -0.5 ++                                                                  ++
      +          +           +          +           +          +           +
   -1 ++-+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--++
     1000      10000       100000     1e+06       1e+07      1e+08       1e+09
                              File Size (in Bytes)



--> Read from disk (1KB, 10KB, 100KB, 1MB, 10MB, 1GB):
-------------------------------------------------------

----> File Size (vs) Wall clock time

    2 ++-+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--++
      +          +           +          +           +    Cache Miss ****** +
      |                                                   Cache Hit ###### |
  1.5 ++                                                                  ++
      |                                                                    |
      |                                                                    |
    1 ++                                                                  +*
      |                                                                  **|
      |                                                                **  |
  0.5 ++                                                             **   ++
      |                                                            **      |
      |                                                          **        |
    0 ***********************************************************###########
      |                                                                    |
      |                                                                    |
 -0.5 ++                                                                  ++
      |                                                                    |
      +          +           +          +           +          +           +
   -1 ++-+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--++
     1000      10000       100000     1e+06       1e+07      1e+08       1e+09
                              File Size (in Bytes)


----> File Size (vs) CPU

    3 ++-+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--++
      +          +           +          +           +    Cache Miss ****** +
  2.5 ++                                                  Cache Hit ######++
      |                                                                    |
    2 ++                                                                  ++
      |                                                                    |
      |                                                                    |
  1.5 ++                                                                  ++
      |                                                                   **
    1 ++                                                                **++
      |                                                               **   |
  0.5 ++                                                            **    ++
      |                                                           **       |
    0 ************************************************************##########
      |                                                                    |
      |                                                                    |
 -0.5 ++                                                                  ++
      +          +           +          +           +          +           +
   -1 ++-+----+-++---+----+-++--+----+-++---+---+--++--+----+-++---+---+--++
     1000      10000       100000     1e+06       1e+07      1e+08       1e+09
                              File Size (in Bytes)



=> Implementation:
==================

- A double linked list (dlqueue.h) is used to maintain cache. 
- The data in the double linked list points to (filename, filedata)
- A hash table is used for fast access to to the nodes in double linked list
- Hash table is indexed based on the filename
- Hash table nodes contain Key(filename) and Value (pointer to the corresponding node in double linked list)