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

/*
 * Copyright (c) 2009 Sony Pictures Imageworks Inc
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the
 * distribution.  Neither the name of Sony Pictures Imageworks nor the
 * names of its contributors may be used to endorse or promote
 * products derived from this software without specific prior written
 * permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */

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

/*! \file SparseFile.h
  \brief Contains functions controlling the loading of sparse fields.
*/

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

#ifndef _INCLUDED_Field3D_SparseFile_H_
#define _INCLUDED_Field3D_SparseFile_H_

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

#include <boost/scoped_ptr.hpp>
#include <deque>
#include <list>
#include <vector>

#include <hdf5.h>

#include "Exception.h"
#include "Hdf5Util.h"
#include "OgawaFwd.h"
#include "SparseDataReader.h"
#include "Traits.h"

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

#define F3D_SHORT_MUTEX_ARRAY 1
#define F3D_MUTEX_ARRAY_SIZE  1000
#define F3D_NO_BLOCKS_ARRAY   1

#include "ns.h"

FIELD3D_NAMESPACE_OPEN

//----------------------------------------------------------------------------//
// Forward declarations
//----------------------------------------------------------------------------//

namespace Sparse {

  template <typename Data_T>
  struct SparseBlock;

}

template <typename Data_T>
class SparseField;

template <typename Data_T>
class OgSparseDataReader;

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

namespace SparseFile {

//----------------------------------------------------------------------------//
// Reference
//----------------------------------------------------------------------------//

/*! \class Reference
  Handles information about and block loading for a single SparseField 
  as referenced on disk
*/

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

template <class Data_T>
class Reference 
{
public:

  // Typedefs ------------------------------------------------------------------

#define USE_SHPTR 0
  
#if USE_SHPTR
  typedef boost::shared_ptr<Reference>              Ptr;
#else
  typedef Reference*                                Ptr;
#endif

#if F3D_NO_BLOCKS_ARRAY
  typedef Sparse::SparseBlock<Data_T>*              BlockPtrs;
#else
  typedef std::vector<Sparse::SparseBlock<Data_T>*> BlockPtrs;
#endif

  // Public data members -------------------------------------------------------

  std::string filename;
  std::string layerPath;
  int valuesPerBlock;
  int numVoxels;
  int numBlocks;
  int occupiedBlocks;
 
  //! Index in file for each block
  std::vector<int> fileBlockIndices;
  //! Whether each block is loaded. We don't use bools since vector<bool> 
  //! is weird
  std::vector<int> blockLoaded;
  //! Pointers to each block. This is so we can go in and manipulate them
  //! as we please
  BlockPtrs blocks;
  //! Flags of whether the blocks have been accessed since they were
  //! last considered for deallocation by the Second-chance/Clock
  //! caching system
  std::vector<bool> blockUsed;
  //! Per-block counts of the number of times each block has been
  //! loaded, for cache statistics
  std::vector<int> loadCounts;
  //! Per-block counts of the number of current references to the
  //! blocks.  If a block's ref count is non-zero, then the block
  //! shouldn't be unloaded.
  std::vector<int> refCounts;
  //! Allocated array of mutexes, one per block, to lock each block
  //! individually, for guaranteeing thread-safe updates of the ref
  //! counts
  boost::mutex *blockMutex;
#if F3D_SHORT_MUTEX_ARRAY
  //! Size of the mutex array. Used as modulus base.
  int blockMutexSize;
#endif

  // Ctors, dtor ---------------------------------------------------------------

  //! Destructor
  ~Reference();

  // Main methods --------------------------------------------------------------

  //! Returns a shared pointer to a reference. Preferred way of creating 
  //! References
  static Ptr create(const std::string a_filename, 
                    const std::string a_layerPath);
  //! Checks if the file used by this reference is open already
  bool fileIsOpen();
  //! Sets the number of blocks used by the SparseField we're supporting
  void setNumBlocks(int numBlocks);
  //! Opens the file. This is done just before the first request to loadBlock.
  //! This is delayed so that the original file open  has closed the file and
  //! doesn't cause any Hdf5 hiccups.
  void openFile();
  //! Closes the file. Will be re-opened as needed.
  void closeFile();
  //! Loads the block with the given index into memory. We don't pass in 
  //! a reference to where the data should go since this is already know in the
  //! blocks data member.
  void loadBlock(int blockIdx);
  //! Unloads the block with the given index from memory.
  void unloadBlock(int blockIdx);
  //! Increment reference count on a block, indicates the block is
  //! currently in use, so prevents it from being unloaded
  void incBlockRef(int blockIdx);
  //! Decrement reference count on a block
  void decBlockRef(int blockIdx);
  //! Returns the number of bytes used by the data in the block
  int blockSize(int blockIdx) const;
  //! Returns the total number of loads of the blocks of this file,
  //! for cache statistics
  int totalLoads() const;
  //! Returns the total number of blocks that are currently loaded,
  //! for statistics.
  int numLoadedBlocks() const;
  //! Returns the total number of blocks that were ever loaded (max 1
  //! per block, not the number of blocks), for statistics.
  int totalLoadedBlocks() const;
  //! Returns the average number of loads per accessed block in this file,
  //! for cache statistics
  float averageLoads() const;
  //! Resets counts of total block loads
  void resetCacheStatistics();
  //! Memory use for the Reference
  long long int memSize() const;

private:

  typedef boost::mutex Mutex;

  // Private constructors ---

  //! Constructor. Requires the filename and layer path of the field to be known
  Reference(const std::string filename, const std::string layerPath);
  
  //! Copy constructor. Clears ref counts and rebuilds mutex array.
  Reference(const Reference &o);

  //! Assignment operator.  Clears ref counts and rebuilds mutex array.
  Reference & operator=(const Reference &o);

  // Data members ---

  //! Holds the Hdf5 handle to the file
  hid_t m_fileHandle;
  
  //! Hold the group containing the data open for the duration of the 
  //! Reference's existence.
  Hdf5Util::H5ScopedGopen m_layerGroup;

  //! Pointer to the reader object. NULL at construction time. Created in 
  //! openFile().
  SparseDataReader<Data_T> *m_reader;

  //! Shared pointer to the ogawa reader. 
  boost::shared_ptr<OgSparseDataReader<Data_T> > m_ogReaderPtr;
  //! Pointer to the ogawa reader. NULL at construction time. Created in 
  //! openFile().
  OgSparseDataReader<Data_T> *m_ogReader;
  //! Ogawa archive
  IArchivePtr m_ogArchive;
  //! Ogawa archive root
  OgIGroupPtr m_ogRoot;
  //! Ogawa layer group
  OgIGroupPtr m_ogLayerGroup;

  //! Mutex to prevent two threads from modifying conflicting data
  mutable Mutex m_mutex;

  //! Number of currently active blocks
  size_t m_numActiveBlocks;

};

//----------------------------------------------------------------------------//
// FileReferences
//----------------------------------------------------------------------------//

class FileReferences
{
public:

  /* A note on thread safety

     FileReferences uses a std::deque to store the References, which means
     that already-added references 'stay put' in memory, even as more elements
     are added. For threading purposes, we only need to lock during append()
     and numRefs(), but ref() is safe, since we never remove references.

   */

  // Ctors, dtor ---------------------------------------------------------------

  ~FileReferences();

  // Main methods --------------------------------------------------------------

  //! Returns a reference to the index. This is specialized so that the
  //! correct data member is accessed.
  template <class Data_T>
  Reference<Data_T>* ref(size_t idx);

  //! Appends a reference to the collection. This is specialized so that the
  //! correct data member is accessed.
  template <class Data_T>
  size_t append(typename Reference<Data_T>::Ptr ref);

  //! Returns the number of file references of the corresponding collection
  template <class Data_T>
  size_t numRefs() const;

  //! Returns the memory use for the refs
  long long int memSize() const;

private:

  // Data members --------------------------------------------------------------

  std::deque<Reference<half>::Ptr>   m_hRefs;
  std::deque<Reference<V3h>::Ptr>    m_vhRefs;
  std::deque<Reference<float>::Ptr>  m_fRefs;
  std::deque<Reference<V3f>::Ptr>    m_vfRefs;
  std::deque<Reference<double>::Ptr> m_dRefs;
  std::deque<Reference<V3d>::Ptr>    m_vdRefs;

  // Mutexes -------------------------------------------------------------------

  typedef boost::mutex Mutex;

  mutable Mutex m_mutex;

};

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

class CacheBlock {
public:
  DataTypeEnum blockType;
  int refIdx;
  int blockIdx;
  CacheBlock(DataTypeEnum blockTypeIn, int refIdxIn,  int blockIdxIn) :
    blockType(blockTypeIn), refIdx(refIdxIn), blockIdx(blockIdxIn) 
  { }
};

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

} // namespace SparseFile

//----------------------------------------------------------------------------//
// SparseFileManager
//----------------------------------------------------------------------------//

/*! \class SparseFileManager
  \ingroup file

  Handles specifics about reading sparse fields from disk. Its primary use
  is to control sparse fields read using memory limiting (dynamic loading).

  To enable the dynamic cache for a file, call setLimitMemUse(true)
  before opening the file.  If you want other files to be fully loaded, call
  setLimitMemUse(false).

  Example of how to use the cache manager to automatically unload
  sparse blocks from a f3d file:

  <pre>
  SparseFileManager &sparseManager = SparseFileManager::singleton();
  sparseManager.setLimitMemUse(true);  // enables cache for files to be opened 
  sparseManager.setMaxMemUse(1000.0);  // sets cache to 1 GB
  Field3DInputFile cacheManagedFile;
  if (!cacheManagedFile.open(filename)) {
    Msg::print( "Couldn't open file: " + filename);
    return 1;
  }
  sparseManager.setLimitMemUse(false);  // disables cache for other files

  ... // You can use the file normally, loading layers and then accessing
  ... // with const_iterator, value(), or empty block functions like
  ... // getBlockEmptyValue().
  ... // Layers loaded from cacheManagedFile will be managed by the cache,
  ... // but other files you open will be fully loaded when opened because of
  ... // the setLimitMemUse(false) call.

  Msg::print("blocks in cache: " +
    boost::lexical_cast<std::string>(sparseManager.numLoadedBlocks()));
  Msg::print("cache blocks ever loaded: " +
    boost::lexical_cast<std::string>(sparseManager.totalLoadedBlocks()));
  Msg::print("cache loads: " +
    boost::lexical_cast<std::string>(sparseManager.totalLoads()));
  Msg::print("cache fraction loaded: " +
    boost::lexical_cast<std::string>(sparseManager.cacheFractionLoaded()));
  Msg::print("cache loads per block: " +
    boost::lexical_cast<std::string>(sparseManager.cacheLoadsPerBlock()));
  Msg::print("cache efficiency: " +
    boost::lexical_cast<std::string>(sparseManager.cacheEfficiency()));
  </pre>

  If you want to flush the cache manually instead of waiting for the
  process to end and clean up its memory:

  <pre>
  sparseManager.flushCache();
  sparseManager.resetCacheStatistics();
  </pre>

*/

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

class FIELD3D_API SparseFileManager
{

public:

  template <class Data_T>
  friend class SparseField;

  // typedefs ------------------------------------------------------------------

  typedef std::list<SparseFile::CacheBlock> CacheList;

  // Main methods --------------------------------------------------------------

  //! Returns a reference to the singleton instance
  static SparseFileManager &singleton();

  //! Sets whether to limit memory usage and do dynamic loading for sparse 
  //! fields.
  void setLimitMemUse(bool enabled);

  //! Returns whether to limit memory usage and do dynamic loading for sparse 
  //! fields.
  bool doLimitMemUse() const;

  //! Sets the maximum memory usage, in MB, by dynamically loaded sparse fields.
  void setMaxMemUse(float maxMemUse);

  //! Flushes the entire block cache for all files, should probably
  //! only be used for debugging
  void flushCache();

  //! Returns the total number of block loads in the cache
  long long totalLoads();

  //! Returns the total number of blocks currently loaded into cache
  long long numLoadedBlocks();

  //! Returns the total number of blocks loaded (max 1 per block) into cache
  long long totalLoadedBlocks();

  //! Computes the ratio of blocks in the cache to the total number of
  //! blocks that have been loaded (including unloaded blocks)
  float cacheFractionLoaded();

  //! Computes the overall loaded-blocks-to-load ratio for cached files
  float cacheLoadsPerBlock();

  //! Computes the efficiency, the ratio of the number of blocks ever
  //! loaded to the number of loads.  If this is <1, then there were reloads.
  float cacheEfficiency();

  //! Resets block load
  void resetCacheStatistics();

  //! Returns the number of bytes used by the SparseFileManager itself
  long long int memSize() const;

  //--------------------------------------------------------------------------//
  // Utility functions

  //! Increments the usage reference count on the specified block,
  //! to prevent it from getting unloaded while it's still in use.
  //! This should not be called by the user, and may be removed from the
  //! public interface later.
  template <class Data_T>
  void incBlockRef(int fileId, int blockIdx);

  //! Decrements the usage reference count on the specified block,
  //! after its value is no longer being used
  //! This should not be called by the user, and may be removed from the
  //! public interface later.
  template <class Data_T>
  void decBlockRef(int fileId, int blockIdx);

  //! Called by SparseField when it's about to read from a block.
  //! This should not be called by the user, and may be removed from the
  //! public interface later.
  template <class Data_T>
  void activateBlock(int fileId, int blockIdx);

protected:

  //! Returns a reference to the Reference object with the given index
  template <class Data_T>
  SparseFile::Reference<Data_T>* reference(int index);

  //! Returns the id of the next cache item. This is stored in the SparseField
  //! in order to reference its fields at a later time
  template <class Data_T>
  int getNextId(const std::string filename, const std::string layerPath);

  template <class Data_T>
  void removeFieldFromCache(int refIdx);

private:

  //! Private to prevent instantiation
  SparseFileManager();

  //! Pointer to singleton
  static boost::scoped_ptr<SparseFileManager> ms_singleton;

  //! Adds the newly loaded block to the cache, managed by the paging algorithm
  void addBlockToCache(DataTypeEnum blockType, int fileId, int blockIdx);

  //! Utility function to reclaim the specified number of bytes by
  //! deallocating unneeded blocks
  void deallocateBlocks(int64_t bytesNeeded);

  //! Utility function to attempt to deallocate a single block and
  //! advance the "hand"
  template <class Data_T>
  int64_t deallocateBlock(const SparseFile::CacheBlock &cb);

  //! Utility function to deallocate a single block
  template <class Data_T>
  void deallocateBlock(CacheList::iterator &it);

  //! Max amount om memory to use in megabytes
  float m_maxMemUse;

  //! Max amount om memory to use in bytes
  int64_t m_maxMemUseInBytes;

  //! Current amount of memory in use in bytes
  int64_t m_memUse;

  //! Whether to limit memory use of sparse fields from disk. Enables the
  //! cache and dynamic loading when true.
  bool m_limitMemUse;

  //! Vector containing information for each of the managed fields.
  //! The order matches the index stored in each SparseField::m_fileId
  SparseFile::FileReferences m_fileData;

  //! List of dynamically loaded blocks to be considered for unloading
  //! when the cache is full.
  //! Currently using Second-chance/Clock paging algorithm.
  //! For a description of the algorithm, look at:
  //! http://en.wikipedia.org/wiki/Page_replacement_algorithm#Second-chance
  CacheList m_blockCacheList;

  //! Pointer to the next block to test for unloading in the cache,
  //! the "hand" of the clock
  CacheList::iterator m_nextBlock;

  //! Mutex to prevent multiple threads from deallocating blocks at
  //! the same time
  mutable boost::mutex m_mutex;

};

//----------------------------------------------------------------------------//
// Reference implementations
//----------------------------------------------------------------------------//

namespace SparseFile {

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

template <class Data_T>
Reference<Data_T>::Reference(const std::string a_filename, 
                             const std::string a_layerPath)
  : filename(a_filename), layerPath(a_layerPath),
    valuesPerBlock(-1), numVoxels(-1), numBlocks(-1), occupiedBlocks(-1),
    blockMutex(NULL), m_fileHandle(-1), m_reader(NULL), m_ogReader(NULL), 
    m_numActiveBlocks(0)
{ 
  /* Empty */ 
}

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

template <class Data_T>
Reference<Data_T>::~Reference()
{
  closeFile();

  if (m_reader) {
    delete m_reader;
  }

  if (blockMutex)
    delete [] blockMutex;
}

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

template <class Data_T>
Reference<Data_T>::Reference(const Reference<Data_T> &o)
{
  m_ogReaderPtr.reset();
  m_ogReader = NULL;
  m_reader = NULL;
  blockMutex = NULL;
  *this = o;
}

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

template <class Data_T>
Reference<Data_T> &
Reference<Data_T>::operator=(const Reference<Data_T> &o)
{
  if (this == &o) {
    return *this;
  }
  
  // Copy public member variables (where appropriate)
  filename = o.filename;
  layerPath = o.layerPath;
  valuesPerBlock = o.valuesPerBlock;
  numVoxels = o.numVoxels;
  occupiedBlocks = o.occupiedBlocks;
  fileBlockIndices = o.fileBlockIndices;
  blockLoaded = o.blockLoaded;
  blocks = o.blocks;
  blockUsed = o.blockUsed;
  loadCounts = o.loadCounts;
  refCounts = o.refCounts;
  if (blockMutex)
    delete[] blockMutex;
#if F3D_SHORT_MUTEX_ARRAY
#  if F3D_NO_BLOCKS_ARRAY
  blockMutexSize = std::min(numBlocks, F3D_MUTEX_ARRAY_SIZE);
#  else
  blockMutexSize = std::min(static_cast<int>(blocks.size()), 
                            F3D_MUTEX_ARRAY_SIZE);
#  endif
  blockMutex = new boost::mutex[blockMutexSize];
#else
  blockMutex = new boost::mutex[blocks.size()];
#endif

#if 0
  // MW: Should this be copying the file handle? Never seems to happen,
  // but it also seems bad. Ifdef'ing out for now.
  // Copy private member variables (where appropriate)
  m_fileHandle = o.m_fileHandle;
  // Don't copy id, let hdf5 generate a new one.
  if (m_fileHandle >= 0) {
    m_layerGroup.open(m_fileHandle, layerPath.c_str());
  }
#else
  m_fileHandle = -1;
#endif

  // Re-allocate reader
  if (m_reader)
    delete m_reader;
  m_reader = NULL;

  m_ogReaderPtr.reset();
  m_ogReader = NULL;

  return *this;
}

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

template <class Data_T>
typename Reference<Data_T>::Ptr
Reference<Data_T>::create(const std::string a_filename, 
                          const std::string a_layerPath)
{
  return Ptr(new Reference(a_filename, a_layerPath));
}

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

template <class Data_T>
bool Reference<Data_T>::fileIsOpen()
{
  return m_fileHandle >= 0;
}

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

template <class Data_T>
void Reference<Data_T>::setNumBlocks(int a_numBlocks)
{
  boost::mutex::scoped_lock lock(m_mutex);

  // Store number of blocks in member variable
  numBlocks = a_numBlocks;

  fileBlockIndices.resize(numBlocks);
  blockLoaded.resize(numBlocks, 0);
#if !F3D_NO_BLOCKS_ARRAY
  blocks.resize(numBlocks, 0);
#endif
  blockUsed.resize(numBlocks, false);
  loadCounts.resize(numBlocks, 0);
  refCounts.resize(numBlocks, 0);
  if (blockMutex)
    delete[] blockMutex;
#if F3D_SHORT_MUTEX_ARRAY
#  if F3D_NO_BLOCKS_ARRAY
  blockMutexSize = std::min(numBlocks, F3D_MUTEX_ARRAY_SIZE);
#  else
  blockMutexSize = std::min(blocks.size(), 
                            static_cast<size_t>(F3D_MUTEX_ARRAY_SIZE));
#  endif
  blockMutex = new boost::mutex[blockMutexSize];
#else
  blockMutex = new boost::mutex[numBlocks];
#endif
}

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

template <class Data_T>
void Reference<Data_T>::closeFile()
{
  if (m_fileHandle >= 0) {
    if (H5Fclose(m_fileHandle) < 0) {
      Msg::print("In ~Reference(): Error closing file " + filename);
    }
  }
}

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

template <class Data_T>
void Reference<Data_T>::unloadBlock(int blockIdx)
{
  // Deallocate the block
#if F3D_NO_BLOCKS_ARRAY
  blocks[blockIdx].clear();
#else
  blocks[blockIdx]->clear();
#endif
  // Mark block as unloaded
  blockLoaded[blockIdx] = 0;
  // Track count
  m_numActiveBlocks--;
#if 0
  // If no active blocks, close the file. De-activate for now.
  if (m_numActiveBlocks == 0) {
    closeFile();
  }
#endif
}

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

template <class Data_T>
void Reference<Data_T>::incBlockRef(int blockIdx)
{
#if F3D_SHORT_MUTEX_ARRAY
  boost::mutex::scoped_lock lock(blockMutex[blockIdx % blockMutexSize]);
#else
  boost::mutex::scoped_lock lock(blockMutex[blockIdx]);
#endif
  ++refCounts[blockIdx];
}

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

template <class Data_T>
void Reference<Data_T>::decBlockRef(int blockIdx)
{
#if F3D_SHORT_MUTEX_ARRAY
  boost::mutex::scoped_lock lock(blockMutex[blockIdx % blockMutexSize]);
#else
  boost::mutex::scoped_lock lock(blockMutex[blockIdx]);
#endif
  --refCounts[blockIdx];
}

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

template <class Data_T>
int Reference<Data_T>::blockSize(int /* blockIdx */) const
{
  return numVoxels * sizeof(Data_T);
}

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

template <class Data_T>
int Reference<Data_T>::totalLoads() const
{
  std::vector<int>::const_iterator i = loadCounts.begin();
  std::vector<int>::const_iterator end = loadCounts.end();
  int numLoads = 0;
  for (; i != end; ++i)
    numLoads += *i;

  return numLoads;
}

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

template <class Data_T>
int Reference<Data_T>::numLoadedBlocks() const
{
  std::vector<int>::const_iterator i = blockLoaded.begin();
  std::vector<int>::const_iterator end = blockLoaded.end();
  int numBlockCounter = 0;
  for (; i != end; ++i)
    if (*i)
      numBlockCounter++;

  return numBlockCounter;
}

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

template <class Data_T>
int Reference<Data_T>::totalLoadedBlocks() const
{
  std::vector<int>::const_iterator i = loadCounts.begin();
  std::vector<int>::const_iterator li = blockLoaded.begin();
  std::vector<int>::const_iterator end = loadCounts.end();
  int numBlockCounter = 0;

  if (blockLoaded.size() == 0) {
    for (; i != end; ++i)
      if (*i)
        numBlockCounter++;
  } else {
    assert(loadCounts.size() == blockLoaded.size());

    for (; i != end; ++i, ++li)
      if (*i || *li)
        numBlockCounter++;
  }
  
  return numBlockCounter;
}

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

template <class Data_T>
float Reference<Data_T>::averageLoads() const
{
  std::vector<int>::const_iterator i = loadCounts.begin();
  std::vector<int>::const_iterator end = loadCounts.end();
  int numLoads = 0, numBlockCounter = 0;
  for (; i != end; ++i) {
    if (*i) {
      numLoads += *i;
      numBlockCounter++;
    }
  }

  return (float)numLoads / std::max(1, numBlockCounter);
}

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

template <class Data_T>
void Reference<Data_T>::resetCacheStatistics()
{
  std::vector<int>::iterator li = loadCounts.begin();
  std::vector<int>::iterator lend = loadCounts.end();
  for (; li != lend; ++li)
    *li = 0;
}

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

template <class Data_T>
long long int
Reference<Data_T>::memSize() const
{
  boost::mutex::scoped_lock lock(m_mutex);

  return sizeof(*this) + 
    fileBlockIndices.capacity() * sizeof(int) + 
    blockLoaded.capacity() * sizeof(int) + 
#if !F3D_NO_BLOCKS_ARRAY
    blocks.capacity() * sizeof(Sparse::SparseBlock<Data_T>*) + 
#endif
    blockUsed.capacity() * sizeof(bool) + 
    loadCounts.capacity() * sizeof(int) + 
    refCounts.capacity() * sizeof(int) + 
#if F3D_SHORT_MUTEX_ARRAY
    blockMutexSize * sizeof(boost::mutex) + 
#else
    numBlocks * sizeof(boost::mutex) + 
#endif
    sizeof(SparseDataReader<Data_T>);
}

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

} // namespace SparseFile

//----------------------------------------------------------------------------//
// Specializations for FileReferences
//----------------------------------------------------------------------------//

namespace SparseFile {

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

inline FileReferences::~FileReferences()
{
#if !USE_SHPTR
  for (size_t i = 0, end = m_hRefs.size(); i < end; ++i) {
    delete m_hRefs[i];
  }
  for (size_t i = 0, end = m_fRefs.size(); i < end; ++i) {
    delete m_fRefs[i];
  }
  for (size_t i = 0, end = m_dRefs.size(); i < end; ++i) {
    delete m_dRefs[i];
  }
  for (size_t i = 0, end = m_vhRefs.size(); i < end; ++i) {
    delete m_vhRefs[i];
  }
  for (size_t i = 0, end = m_vfRefs.size(); i < end; ++i) {
    delete m_vfRefs[i];
  }
  for (size_t i = 0, end = m_vdRefs.size(); i < end; ++i) {
    delete m_vdRefs[i];
  }
#endif  
}

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

template <>
inline Reference<half>* 
FileReferences::ref(size_t idx)
{
#if USE_SHPTR
  return m_hRefs[idx].get();
#else
  return m_hRefs[idx];
#endif
}

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

template <>
inline Reference<V3h>* 
FileReferences::ref(size_t idx)
{
#if USE_SHPTR
  return m_vhRefs[idx].get();
#else
  return m_vhRefs[idx];
#endif
}

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

template <>
inline Reference<float>* 
FileReferences::ref(size_t idx)
{
#if USE_SHPTR
  return m_fRefs[idx].get();
#else
  return m_fRefs[idx];
#endif
}

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

template <>
inline Reference<V3f>* 
FileReferences::ref(size_t idx)
{
#if USE_SHPTR
  return m_vfRefs[idx].get();
#else
  return m_vfRefs[idx];
#endif
}

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

template <>
inline Reference<double>* 
FileReferences::ref(size_t idx)
{
#if USE_SHPTR
  return m_dRefs[idx].get();
#else
  return m_dRefs[idx];
#endif
}

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

template <>
inline Reference<V3d>* 
FileReferences::ref(size_t idx)
{
#if USE_SHPTR
  return m_vdRefs[idx].get();
#else
  return m_vdRefs[idx];
#endif
}

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

template <>
inline size_t FileReferences::append<half>(Reference<half>::Ptr ref)
{
  Mutex::scoped_lock lock(m_mutex);

  m_hRefs.push_back(ref);
  return m_hRefs.size() - 1;
}

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

template <>
inline size_t FileReferences::append<V3h>(Reference<V3h>::Ptr ref)
{
  Mutex::scoped_lock lock(m_mutex);

  m_vhRefs.push_back(ref);
  return m_vhRefs.size() - 1;
}

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

template <>
inline size_t FileReferences::append<float>(Reference<float>::Ptr ref)
{
  Mutex::scoped_lock lock(m_mutex);

  m_fRefs.push_back(ref);
  return m_fRefs.size() - 1;
}

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

template <>
inline size_t FileReferences::append<V3f>(Reference<V3f>::Ptr ref)
{
  Mutex::scoped_lock lock(m_mutex);

  m_vfRefs.push_back(ref);
  return m_vfRefs.size() - 1;
}

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

template <>
inline size_t FileReferences::append<double>(Reference<double>::Ptr ref)
{
  Mutex::scoped_lock lock(m_mutex);

  m_dRefs.push_back(ref);
  return m_dRefs.size() - 1;
}

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

template <>
inline size_t FileReferences::append<V3d>(Reference<V3d>::Ptr ref)
{
  Mutex::scoped_lock lock(m_mutex);

  m_vdRefs.push_back(ref);
  return m_vdRefs.size() - 1;
}

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

template <>
inline size_t FileReferences::numRefs<half>() const
{
  Mutex::scoped_lock lock(m_mutex);

  return m_hRefs.size();
}

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

template <>
inline size_t FileReferences::numRefs<V3h>() const
{
  Mutex::scoped_lock lock(m_mutex);

  return m_vhRefs.size();
}

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

template <>
inline size_t FileReferences::numRefs<float>() const
{
  Mutex::scoped_lock lock(m_mutex);

  return m_fRefs.size();
}

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

template <>
inline size_t FileReferences::numRefs<V3f>() const
{
  Mutex::scoped_lock lock(m_mutex);

  return m_vfRefs.size();
}

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

template <>
inline size_t FileReferences::numRefs<double>() const
{
  Mutex::scoped_lock lock(m_mutex);

  return m_dRefs.size();
}

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

template <>
inline size_t FileReferences::numRefs<V3d>() const
{
  Mutex::scoped_lock lock(m_mutex);

  return m_vdRefs.size();
}

//----------------------------------------------------------------------------//
// Implementations for FileReferences
//----------------------------------------------------------------------------//

#if 0

template <class Data_T>
Reference<Data_T>& FileReferences::ref(size_t)
{
  assert(false && "Do not use memory limiting on sparse fields that aren't "
         "simple scalars or vectors!");
  Msg::print(Msg::SevWarning, 
             "FileReferences::ref(): Do not use memory limiting on sparse "
             "fields that aren't simple scalars or vectors!");
  static Reference<Data_T> dummy("", "");
  return dummy;
}

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

template <class Data_T>
size_t FileReferences::append(const Reference<Data_T>&)
{
  assert(false && "Do not use memory limiting on sparse fields that aren't "
         "simple scalars or vectors!");
  Msg::print(Msg::SevWarning,
             "FileReferences::append(): Do not use memory limiting on sparse "
             "fields that aren't simple scalars or vectors!");
  return -1;    
}

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

template <class Data_T>
size_t FileReferences::numRefs() const
{
  assert(false && "Do not use memory limiting on sparse fields that aren't "
         "simple scalars or vectors!");
  Msg::print(Msg::SevWarning,
             "FileReferences::numRefs(): "
             "Do not use memory limiting on sparse "
             "fields that aren't "
             "simple scalars or vectors!");
  return -1;
}

#endif

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

} // namespace SparseFile

//----------------------------------------------------------------------------//
// SparseFileManager implementations
//----------------------------------------------------------------------------//

template <class Data_T>
int 
SparseFileManager::getNextId(const std::string filename, 
                             const std::string layerPath)
{
  using namespace SparseFile;

  // Must hold a mutex while appending to m_fileData
  boost::mutex::scoped_lock lock(m_mutex);

  int id = m_fileData.append<Data_T>(Reference<Data_T>::create(filename, 
                                                               layerPath));
  return id;
}

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

template <class Data_T>
void
SparseFileManager::removeFieldFromCache(int refIdx)
{
  boost::mutex::scoped_lock lock(m_mutex);

  DataTypeEnum blockType = DataTypeTraits<Data_T>::typeEnum();
  SparseFile::Reference<Data_T> *reference = m_fileData.ref<Data_T>(refIdx);

  CacheList::iterator it = m_blockCacheList.begin();
  CacheList::iterator end = m_blockCacheList.end();
  CacheList::iterator next;

  int64_t bytesFreed = 0;

  while (it != end) {
    if (it->blockType == blockType && it->refIdx == refIdx) {
      if (it == m_nextBlock) {
        ++m_nextBlock;
      }
      next = it;
      ++next;
      bytesFreed += reference->blockSize(it->blockIdx);
      m_blockCacheList.erase(it);
      it = next;
    } else {
      ++it;
    }
  }
  m_memUse -= bytesFreed;

  std::vector<int>().swap(reference->fileBlockIndices);
#if F3D_NO_BLOCKS_ARRAY
  reference->fileBlockIndices.resize(reference->numBlocks, -1);
#else
  reference->fileBlockIndices.resize(reference->blocks.size(), -1);
  typedef typename SparseFile::Reference<Data_T>::BlockPtrs BlockPtrs;
  BlockPtrs().swap(reference->blocks);
#endif
  std::vector<int>().swap(reference->blockLoaded);
  std::vector<bool>().swap(reference->blockUsed);
  std::vector<int>().swap(reference->loadCounts);
  std::vector<int>().swap(reference->refCounts);
  delete[] reference->blockMutex;
  reference->blockMutex = NULL;
}

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

template <class Data_T>
SparseFile::Reference<Data_T>*
SparseFileManager::reference(int index)
{ 
  return m_fileData.ref<Data_T>(index); 
}

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

template <class Data_T>
void 
SparseFileManager::activateBlock(int fileId, int blockIdx)
{
  SparseFile::Reference<Data_T> *reference = m_fileData.ref<Data_T>(fileId);

  if (reference->fileBlockIndices[blockIdx] >= 0) {
    if (!reference->blockLoaded[blockIdx]) {
      int blockSize = reference->blockSize(blockIdx);
      if (m_limitMemUse) {
        // if we already have enough free memory, deallocateBlocks()
        // will just return
        deallocateBlocks(blockSize);
      }

      if (!reference->fileIsOpen()) {
        reference->openFile();
      }

      boost::mutex::scoped_lock lock_A(m_mutex);
#if F3D_SHORT_MUTEX_ARRAY
      boost::mutex::scoped_lock 
        lock_B(reference->blockMutex[blockIdx % reference->blockMutexSize]);
#else
      boost::mutex::scoped_lock lock_B(reference->blockMutex[blockIdx]);
#endif
      // check to see if it was loaded between when the function
      // started and we got the lock on the block
      if (!reference->blockLoaded[blockIdx]) {
        reference->loadBlock(blockIdx);
        reference->loadCounts[blockIdx]++;
        addBlockToCache(DataTypeTraits<Data_T>::typeEnum(), fileId, blockIdx);
        m_memUse += blockSize;
      }
    }
  }
  reference->blockUsed[blockIdx] = true;
}

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

template <class Data_T>
void 
SparseFileManager::incBlockRef(int fileId, int blockIdx)
{
  SparseFile::Reference<Data_T> *reference = m_fileData.ref<Data_T>(fileId);

  if (reference->fileBlockIndices[blockIdx] >= 0) {
    reference->incBlockRef(blockIdx);
  }
}

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

template <class Data_T>
void 
SparseFileManager::decBlockRef(int fileId, int blockIdx)
{
  SparseFile::Reference<Data_T> *reference = m_fileData.ref<Data_T>(fileId);

  if (reference->fileBlockIndices[blockIdx] >= 0) {
    reference->decBlockRef(blockIdx);
  }
}

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

FIELD3D_NAMESPACE_HEADER_CLOSE

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

#endif