#pragma region CPL License
/*
Nuclex Native Framework
Copyright (C) 2002-2013 Nuclex Development Labs

This library is free software; you can redistribute it and/or
modify it under the terms of the IBM Common Public License as
published by the IBM Corporation; either version 1.0 of the
License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
IBM Common Public License for more details.

You should have received a copy of the IBM Common Public
License along with this library
*/
#pragma endregion // CPL License

#ifndef NUCLEX_STORAGE_HELPERS_CACHE_H
#define NUCLEX_STORAGE_HELPERS_CACHE_H

#include "Nuclex/Storage/Config.h"

#include <memory>
#include <functional>
#include <cstdint>
#include <cstddef>
#include <cassert>
#include <stdexcept>
#include <mutex>

namespace Nuclex { namespace Storage { namespace Helpers {

  // ------------------------------------------------------------------------------------------- //

  /// <summary>Caches data read from disk or extracted from a compressed archive</summary>
  /// <typeparam name="TIdentifier">
  ///   Identifier through which the cache differentiates which context handles which file
  /// </typeparam>
  /// <remarks>
  ///   <para>
  ///     This cache implements a simple buffering technique where each access is routed
  ///     through a &quot;context&quot;. Each context can buffer a varying amount of data.
  ///     Recurring accesses pick the closest context before the data being accessed,
  ///     ensuring that the smallest possible read is performed each time. Should two
  ///     threads accesss the same location simultaneously, two contexts would be created
  ///     (each thread takes a context, reads through it and then returns it).
  ///   </para>
  ///   <para>
  ///     Caches are ideal to enable efficient random access on a sequential stream (usually
  ///     encountered on compressed archives where the decompressor can only advance through
  ///     the file in forward direction.
  ///   </para>
  ///   <para>
  ///     It is designed for low to moderate concurrency situations where just a few threads
  ///     contest the data being cached at a time (typically 2-8 threads). For heavily
  ///     contested resources, a custom cache should be implemented.
  ///   </para>
  /// </remarks>
  template <
    typename TIdentifier, typename TComparer = std::equal_to<TIdentifier>
  >
  class Cache {

    #pragma region struct Context

    /// <summary>Maintains the state of an individual decompressor or cache line</summary>
    /// <remarks>
    ///   A context performs the buffering of data in the cache. It is up to the context to
    ///   decide on the size of its buffer (usually, a cache and context will be implemented
    ///   together). Each context is guaranteed to be accessed by only 1 thread at a time,
    ///   but this thread may be a different one each time.
    /// </remarks>
    public: struct Context {

      /// <summary>Initializes a new cache context</summary>
      /// <param name="identifier">Identifier of the file the context is handling</param>
      public: NUCLEX_STORAGE_API Context(const TIdentifier &identifier) :
        Location(0),
        Identifier(identifier) {}

      /// <summary>Frees all resources owned by the context</summary>
      public: NUCLEX_STORAGE_API virtual ~Context() {}

      /// <summary>Reads data from the context</summary>
      /// <param name="location">Location in the file from which to read data</param>
      /// <param name="buffer">Buffer into which the data will be read</param>
      /// <param name="count">Number of bytes that need to be read</param>
      public: NUCLEX_STORAGE_API virtual void ReadAt(
        std::uint64_t location, void *buffer, std::size_t count
      ) = 0;

      /// <summary>Starting location of data this context has currently buffered</summary>
      public: std::uint64_t Location;
      /// <summary>Identifier that may be used for hashing or as unique id</summary>
      public: TIdentifier Identifier;

    };

    #pragma endregion // struct Context

    #pragma region struct Indices

    /// <summary>Stores the results of a context search</summary>
    private: struct Indices {

      /// <summary>Initializes a new index set</summary>
      public: NUCLEX_STORAGE_API Indices() :
        Closest(static_cast<std::size_t>(-1)),
        Oldest(static_cast<std::size_t>(-1)) {}

      /// <summary>Index of the context closest to the requested location</summary>
      public: std::size_t Closest;
      /// <summary>Index of the least recently used context</summary>
      public: std::size_t Oldest;

    };

    #pragma endregion // struct Indices

    #pragma region class ContextInsertionScope

    /// <summary>Inserts a context into the front of the cache</summary>
    private: class ContextInsertionScope {

      /// <summary>Initializes a new context inserter</summary>
      /// <param name="cache">Cache into which the context will be inserted</param>
      /// <param name="insertAtFront">Method that will be called to insert the context</param>
      /// <param name="context">Context that will be inserted into the cache</param>
      public: NUCLEX_STORAGE_API ContextInsertionScope(
        Cache *cache,
        void (Cache::*insertAtFront)(Context *context),
        Context *context
      ) :
        cache(cache),
        insertAtFront(insertAtFront),
        context(context) {}

      /// <summary>Inserts the context into the cache</summary>
      public: NUCLEX_STORAGE_API ~ContextInsertionScope() {
        (this->cache->*this->insertAtFront)(this->context);
      }

      /// <summary>Cache into which the context will be inserted</summary>
      private: Cache *cache;
      /// <summary>Method that will be called to insert the context</summary>
      private: void (Cache::*insertAtFront)(Context *context);
      /// <summary>Context that will be inserted</summary>
      private: Context *context;

    };

    #pragma endregion // class ContextInsertionScope

    /// <summary>Initializes the cache</summary>
    /// <param name="contextCapacity">Number of contexts to keep alive at all times</param>
    /// <remarks>
    ///   <para>
    ///     The cache is designed to handle a limited number of simultaneous reads. A new
    ///     context will be created when no context exists that starts before the required
    ///     position or when such contexts are being occupied by another thread at the time
    ///     of the call. After reaching the specified, the least recently used one will be
    ///     evicted each time a new context has to be created.
    ///   </para>
    ///   <para>
    ///     There is one situation where more than the specified number of contexts may
    ///     exist: if all of the contexts are occupied by other threads at the time of
    ///     the call, a temporary context will be created for the calling thread. This means
    ///     that for the affected thread, extraction will start from scratch, so it is wise
    ///     to pick a context capacity high enough to prevent this situation.
    ///   </para>
    ///   <para>
    ///     A typical value for the context capacity is 8, which should cover all normal
    ///     use cases. Excessive capacities will waste memory and slow down context search.
    ///   </para>
    /// </remarks>
    public: NUCLEX_STORAGE_API Cache(std::size_t contextCapacity) :
      contexts(nullptr),
      contextCount(0),
      contextCapacity(contextCapacity) {
      
      this->contexts = new Context *[contextCapacity];
      std::fill(this->contexts, this->contexts + contextCapacity, nullptr);
    }

    /// <summary>Frees all resources owned by the instance</summary>
    public: NUCLEX_STORAGE_API virtual ~Cache() {
      for(std::size_t index = 0; index < this->contextCapacity; ++index) {
        delete this->contexts[index];
      }

      delete []this->contexts;
    }

    /// <summary>Reads the specified number of bytes from the specified position</summary>
    /// <param name="identifier">Identifier of the file that will be accessed</param>
    /// <param name="position">Absolute file position the data will be read from</param>
    /// <param name="buffer">Buffer into which the data will be read</param>
    /// <param name="count">Number of bytes that will be read</param>
    public: NUCLEX_STORAGE_API void ReadAt(
      const TIdentifier &identifier, std::uint64_t position, void *buffer, std::size_t count
    ) {
      bool usePrivateContext;
      Context *context;

      { std::lock_guard<std::mutex> scope(this->mutex);
        Indices indices = locate(identifier, position);

        // Was there a context we can reuse?
        if(indices.Closest != static_cast<std::size_t>(-1)) {
          context = pick(indices.Closest);
          usePrivateContext = false;
        } else { // No, we need to add or replace a context
          context = nullptr;

          // Is there space left to create a new context?
          if(this->contextCount < this->contextCapacity) {
            ++this->contextCount;
            usePrivateContext = false;
          } else { // No, we are completely full
          
            // Is there a slot we can throw out for the new context we create?
            if(indices.Oldest != static_cast<std::size_t>(-1)) {
              delete this->contexts[indices.Oldest];
              remove(indices.Oldest);
              usePrivateContext = false;
            } else { // No, we have to resort to a temporary context
              usePrivateContext = true;
            }

          }
        }
      } // mutex scope

      // In case all slots were filled, a temporary context needs to be used.
      if(usePrivateContext) {
        std::unique_ptr<Context> temporaryContext(CreateContext(identifier));
        temporaryContext->ReadAt(position, buffer, count);
      } else { // There were slots left, so take/create a context and return it afterwards
        if(context == nullptr) {
          context = CreateContext(identifier);
        }
        ContextInsertionScope insertionScope(this, &Cache::insertAtFront, context); {
          context->ReadAt(position, buffer, count);
        }
      }
    }

    /// <summary>Creates a new context storing the state of a cache line</summary>
    /// <param name="identifier">Identifies the file a context is required for</param>
    /// <returns>The new context</returns>
    protected: virtual Context *CreateContext(const TIdentifier &identifier) = 0;

    /// <summary>Searches for the context closest to the specified position</summary>
    /// <param name="identifier">
    ///   Identifier of the file for which a context will be located
    /// </param>
    /// <param name="position">Position for which a context will be searched</param>
    /// <returns>Indices of the closest, oldest and first free context</returns>
    private: Indices locate(const TIdentifier &identifier, std::uint64_t position) {
      Indices indices;

      std::uint64_t closestDistance = static_cast<std::uint64_t>(-1);
      std::size_t closestIndex = static_cast<std::size_t>(-1);

      for(std::size_t index = 0; index < this->contextCapacity; ++index) {
        Context *current = this->contexts[index];
        if(current == nullptr) {
          break;
        }

        if(current->Location <= position) {
          if(this->identifierComparer(current->Identifier, identifier)) {
            if(closestIndex == static_cast<std::size_t>(-1)) {
              closestDistance = position - current->Location;
              indices.Closest = index;
            } else {
              std::uint64_t currentDistance = position - current->Location;
              if(currentDistance < closestDistance) {
                closestDistance = currentDistance;
                indices.Closest = index;
              }
            }
          }
        }

        indices.Oldest = index;
      }

      return indices;
    }

    /// <summary>Picks a context to be used for reading by the current thread</summary>
    /// <param name="index">Index of the context that will be picked</param>
    /// <returns>The context the thread should use to read</returns>
    /// <remarks>
    ///   This removes the context from the context list. It is up to the caller to ensure
    ///   that it is returned whatever happens (otherwise the cache would be loosing contexts,
    ///   resulting in memory leaks and eventually a maxed out contextCount without
    ///   available contexts, causing performance to suffer dramatically).
    /// </remarks>
    private: Context *pick(std::size_t index) {
      using namespace std;

      // If this triggers, there's an out-of-range index being calculated somewhere
      assert(
        (index < this->contextCapacity) &&
        "Index must stay inside the context array"
      );

      Context *picked = this->contexts[index];
      remove(index);
      return picked;
    }

    /// <summary>Removes a context from the context array</summary>
    /// <param name="index">Index of the context that will be removed</param>
    /// <remarks>
    ///   Shifts all contexts following after the index to the left by one.
    /// </remarks>
    private: void remove(std::size_t index) {
      using namespace std;

      // If this triggers, there's an out-of-range index being calculated somewhere
      assert(
        (index < this->contextCapacity) &&
        "Index must stay inside the context array"
      );

      std::size_t lastIndex = this->contextCount - 1;
      for(; index < lastIndex; ++index) {
        if(this->contexts[index + 1] == nullptr) {
          break;
        }

        this->contexts[index] = this->contexts[index + 1];
      }
      this->contexts[lastIndex] = nullptr;
    }

    /// <summary>Moves the specified context to the front of the context list</summary>
    /// <param name="context">Index of the context that will be moved to the front</param>
    private: void insertAtFront(Context *context) {
      using namespace std;

      // If this should happen threads have attempted to return more contexts to the array
      // than have been picked up, which means that there's an error managing contexts somewhere.
      assert(
        (this->contexts[this->contextCapacity - 1] == nullptr) &&
        "There must be open slots in the context array"
      );

      // Normally, synchronization is up to the public methods and privates assume that
      // they're being called in an appropriate context. This method is being called from
      // a RAII scope and thus needs to perform its own synchronization.
      std::lock_guard<std::mutex> scope(this->mutex); {

        // Skip until we encounter the first used slot
        std::size_t index = this->contextCount - 1;
        while(index > 0) {
          if(this->contexts[index] != nullptr) {
            break;
          }

          --index;
        }

        // Shift all slots to the right to make space at the beginning
        while(index > 0) {
          this->contexts[index + 1] = this->contexts[index];
          --index;
        }

        this->contexts[0] = context;

      } // mutex scope
    }

    /// <summary>Synchronizes multi-threaded accesses to the cache</summary>
    private: std::mutex mutex;
    /// <summary>Currently active decompressor states</summary>
    private: Context **contexts;
    /// <summary>Maximum number of simultaneous decompression contexts</summary>
    private: std::size_t contextCapacity;
    /// <summary>Number of currently active contexts</summary>
    /// <remarks>
    ///   This must not be used to reason about the number of used slots in the context
    ///   array. When a thread picks a context, it removes it from the context array, without
    ///   decrementing this value. The context count is used to guarantee that there are
    ///   no more than the specified number of contexts active at the same time.
    /// </remarks>
    private: std::size_t contextCount;
    /// <summary>Compares identifiers to see if contexts can be reused</summary>
    private: TComparer identifierComparer;

  };

  // ------------------------------------------------------------------------------------------- //

}}} // namespace Nuclex::Storage::Helpers

#endif // NUCLEX_STORAGE_HELPERS_CACHE_H