/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkSMPThreadLocalImpl.h

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/

// Thread Specific Storage is implemented as a Hash Table, with the Thread Id
// as the key and a Pointer to the data as the value. The Hash Table implements
// Open Addressing with Linear Probing. A fixed-size array (HashTableArray) is
// used as the hash table. The size of this array is allocated to be large
// enough to store thread specific data for all the threads with a Load Factor
// of 0.5. In case the number of threads changes dynamically and the current
// array is not able to accommodate more entries, a new array is allocated that
// is twice the size of the current array. To avoid rehashing and blocking the
// threads, a rehash is not performed immediately. Instead, a linked list of
// hash table arrays is maintained with the current array at the root and older
// arrays along the list. All lookups are sequentially performed along the
// linked list. If the root array does not have an entry, it is created for
// faster lookup next time. The ThreadSpecific::GetStorage() function is thread
// safe and only blocks when a new array needs to be allocated, which should be
// rare.

#ifndef vtkSMPThreadLocalImpl_h
#define vtkSMPThreadLocalImpl_h

#include "vtkCommonCoreModule.h" // For export macro
#include "vtkAtomic.h"
#include "vtkConfigure.h"
#include "vtkSystemIncludes.h"

#include <omp.h>


namespace detail
{

typedef void* ThreadIdType;
typedef vtkTypeUInt32 HashType;
typedef void* StoragePointerType;


struct Slot
{
  vtkAtomic<ThreadIdType> ThreadId;
  omp_lock_t ModifyLock;
  StoragePointerType Storage;

  Slot();
  ~Slot();

private:
  // not copyable
  Slot(const Slot&);
  void operator=(const Slot&);
};


struct HashTableArray
{
  size_t Size, SizeLg;
  vtkAtomic<size_t> NumberOfEntries;
  Slot *Slots;
  HashTableArray *Prev;

  explicit HashTableArray(size_t sizeLg);
  ~HashTableArray();

private:
  // disallow copying
  HashTableArray(const HashTableArray&);
  void operator=(const HashTableArray&);
};


class VTKCOMMONCORE_EXPORT ThreadSpecific
{
public:
  explicit ThreadSpecific(unsigned numThreads);
  ~ThreadSpecific();

  StoragePointerType& GetStorage();
  size_t Size() const;

private:
  vtkAtomic<HashTableArray*> Root;
  vtkAtomic<size_t> Count;

  friend class ThreadSpecificStorageIterator;
};

inline size_t ThreadSpecific::Size() const
{
  return this->Count;
}


class ThreadSpecificStorageIterator
{
public:
  ThreadSpecificStorageIterator()
    : ThreadSpecificStorage(nullptr), CurrentArray(nullptr), CurrentSlot(0)
  {
  }

  void SetThreadSpecificStorage(ThreadSpecific &threadSpecifc)
  {
    this->ThreadSpecificStorage = &threadSpecifc;
  }

  void SetToBegin()
  {
    this->CurrentArray = this->ThreadSpecificStorage->Root;
    this->CurrentSlot = 0;
    if (!this->CurrentArray->Slots->Storage)
    {
      this->Forward();
    }
  }

  void SetToEnd()
  {
    this->CurrentArray = nullptr;
    this->CurrentSlot = 0;
  }

  bool GetInitialized() const
  {
    return this->ThreadSpecificStorage != nullptr;
  }

  bool GetAtEnd() const
  {
    return this->CurrentArray == nullptr;
  }

  void Forward()
  {
    for (;;)
    {
      if (++this->CurrentSlot >= this->CurrentArray->Size)
      {
        this->CurrentArray = this->CurrentArray->Prev;
        this->CurrentSlot = 0;
        if (!this->CurrentArray)
        {
          break;
        }
      }
      Slot *slot = this->CurrentArray->Slots + this->CurrentSlot;
      if (slot->Storage)
      {
        break;
      }
    }
  }

  StoragePointerType& GetStorage() const
  {
    Slot *slot = this->CurrentArray->Slots + this->CurrentSlot;
    return slot->Storage;
  }

  bool operator==(const ThreadSpecificStorageIterator &it) const
  {
    return (this->ThreadSpecificStorage == it.ThreadSpecificStorage) &&
           (this->CurrentArray == it.CurrentArray) &&
           (this->CurrentSlot == it.CurrentSlot);
  }

private:
  ThreadSpecific *ThreadSpecificStorage;
  HashTableArray *CurrentArray;
  size_t CurrentSlot;
};

} // detail;

#endif
// VTK-HeaderTest-Exclude: vtkSMPThreadLocalImpl.h