
// trans.cpp

// includes

#include "hash.h"
#include "move.h"
#include "option.h"
#include "protocol.h"
#include "trans.h"
#include "util.h"
#include "value.h"

#include "YBWCManager.h"
extern YBWCManager* g_pYBWCManagerInstance;

// macros

#define MIN(a,b) ((a)<=(b)?(a):(b))
#define MAX(a,b) ((a)>=(b)?(a):(b))

// kh 02.06.08 Thomas Gaksch 14b5c
#define ENTRY_DATE(entry)  ((entry)->date_flags>>4)
#define ENTRY_FLAGS(entry) ((entry)->date_flags&TransFlags)

// constants

static const bool UseModulo = false;

// variables

trans_t Trans[1];

// prototypes

// kh 25.03.08 also extern used now
//static void      trans_set_date (trans_t * trans, int date);

static int       trans_age      (const trans_t * trans, int date);

static entry_t * trans_entry    (trans_t * trans, uint64 key);

static bool      entry_is_ok    (const entry_t * entry);

// functions

// trans_is_ok()

bool trans_is_ok(const trans_t * trans) {

   int date;

   if (trans == NULL) return false;

   if (trans->table == NULL) return false;
   if (trans->size == 0) return false;
   if (trans->mask == 0 || trans->mask >= trans->size) return false;
   if (trans->date >= DateSize) return false;

   for (date = 0; date < DateSize; date++) {
      if (trans->age[date] != trans_age(trans,date)) return false;
   }

   return true;
}

// trans_init()

void trans_init(trans_t * trans) 
{
  ASSERT(trans != NULL);

// kh 21.03.07
#if defined(DEBUG_INTENSIVE)

  ASSERT((sizeof(entry_t) == 16) ||  sizeof(entry_t) == (16 + 16));

#else

  ASSERT(sizeof(entry_t) == 16);

#endif

  trans->size   = 0;
  trans->mask   = 0;
  trans->table  = NULL;

  trans_set_date(trans, 0);

  trans_clear(trans);

  // ASSERT(trans_is_ok(trans));
}

// trans_alloc()

void trans_alloc(trans_t* trans) 
{
  uint32 size;
  uint32 target;

  ASSERT(trans != NULL);

  // calculate size

  target = option_get_int("Hash");
  if(target < 4) 
  {
    target = 16;
  }

// kh 07.02.08 uci setoption Hash ... is supported
/*
  target = g_pYBWCManagerInstance->pFruitConfiguration->nHashTableSizeMB;
*/

  target *= 1024 * 1024;

  for(size = 1; size != 0 && size <= target; size *= 2)
     ;

  size /= 2;
  ASSERT(size > 0 && size <= target);

  // allocate table

  size /= sizeof(entry_t);
  ASSERT(size != 0 && (size & (size - 1)) == 0); // power of 2

  trans->size = size + (ClusterSize - 1); // HACK to avoid testing for end of table
  trans->mask = size - 1;

  trans->pTransLock = NULL;

  if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)
  {
    trans->table = (entry_t*)YBWCManager_InitSharedMem(g_pYBWCManagerInstance, 
                                                       SHARED_MEMORY_KEY_TRANSPOSITION_TABLE,
//                                                     trans->size * sizeof(entry_t));

// kh 18.03.07 add some bytes for debugging lock conflicts 
// (this info is not used to really lock the trans table)
                                                       trans->size * sizeof(entry_t) + sizeof(TransLock));

    trans->pTransLock = (TransLock*)(((size_t)trans->table) + (trans->size * sizeof(entry_t)));
  } // if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)
  else
  {

// kh 18.03.07 add some bytes as space for the rank required for debugging lock conflicts
//  trans->table = (entry_t*) my_malloc(trans->size * sizeof(entry_t));

// kh 18.03.07 add some bytes for debugging lock conflicts 
// not really needed here, but defensive
    trans->table = (entry_t*) my_malloc(trans->size * sizeof(entry_t) + sizeof(TransLock));

    trans->pTransLock = (TransLock*)(((size_t)trans->table) + (trans->size * sizeof(entry_t)));
  } // !if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)

  if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_FORCE_OUTPUT)
  {
    YBWCManager_Printf(g_pYBWCManagerInstance, 
                       "INFO trans_alloc(... &trans->table %u, trans->size %d, sizeof(entry_t) %d, &trans->pTransLock->nLockId %u\n",
                       trans->table,
                       trans->size,
                       sizeof(entry_t),
                       trans->pTransLock);
  }

  ASSERT(trans->pTransLock != NULL);

  trans->pTransLock->nLockId      = -1;
//trans->pTransLock->nLockEntryId = -1;

  trans_clear(trans);

  ASSERT(trans_is_ok(trans));
}

// trans_free()

void trans_free(trans_t * trans) 
{
  ASSERT(trans_is_ok(trans));

  if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)
  {

    // kh 14.02.08 shared memory free is explicitly handled

  } // if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)
  else
  {
     my_free(trans->table);
  } // !if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)

  trans->table = NULL;
  trans->size = 0;
  trans->mask = 0;
}

// trans_clear()

void trans_clear(trans_t * trans) 
{
  entry_t   clear_entry[1];
  entry_t*  entry;
  uint32    index;

  ASSERT(trans  !=  NULL);

  trans_set_date(trans, 0);

// kh 02.06.08 Thomas Gaksch 14b5c
  clear_entry->key        = 0;

  clear_entry->move       = MoveNone;
  clear_entry->depth      = DepthNone;

// kh 02.06.08 Thomas Gaksch 14b5c
  clear_entry->date_flags = (trans->date << 4);

// kh 04.06.08 assertion does not hold any longer for toga 14b5c
//ASSERT(entry_is_ok(clear_entry));

  entry = trans->table;

  for(index = 0; index < trans->size; index++) 
  {
    *entry++ = *clear_entry;
  }

// kh 05.06.08 hash table entries are tranmitted asynchronously, potentially even before a non root master
// supports the search
// use trans date 1 for non root master, assuming the root master has performed a first 
// trans_inc_date(... before sending any hash table entries 
  if(g_pYBWCManagerInstance->bRootMaster)
  {
  }
  else
  {
    trans_set_date(Trans, 1);
  }

}

// trans_inc_date()

void trans_inc_date(trans_t * trans) {

   ASSERT(trans!=NULL);

   trans_set_date(trans,(trans->date+1)%DateSize);
}

void trans_update_date(trans_t * trans, int date) 
{
  ASSERT(trans != NULL);
  ASSERT(date >= 0 && date < DateSize);

  trans->date = date;

  for(date = 0; date < DateSize; date++) 
  {
    trans->age[date] = trans_age(trans,date);
  }
}

// trans_set_date()

void trans_set_date(trans_t * trans, int date) 
{
  ASSERT(trans != NULL);
  ASSERT(date >= 0 && date < DateSize);

  trans->date = date;

  for(date = 0; date < DateSize; date++) 
  {
    trans->age[date] = trans_age(trans,date);
  }

  trans->used            = 0;
  trans->read_nb         = 0;
  trans->read_hit        = 0;
  trans->write_nb        = 0;
  trans->write_hit       = 0;
  trans->write_collision = 0;
}

// trans_age()

static int trans_age(const trans_t * trans, int date) {

   int age;

   ASSERT(trans!=NULL);
   ASSERT(date>=0&&date<DateSize);

   age = trans->date - date;
   if (age < 0) age += DateSize;

   ASSERT(age>=0&&age<DateSize);

   return age;
}

// trans_store()

// kh 02.06.08 Thomas Gaksch 14b5c
void trans_store(trans_t * trans, uint64 key, int move, int depth, int flags, int value) 
{
  entry_t*  entry;
  entry_t*  best_entry;

  int       score;
  int       best_score;

  int       i;

//int       nMaxRetries = 10;
  int       nMaxRetries = 4;
  bool      bBreak;

  ASSERT(trans_is_ok(trans));
  ASSERT(move >= 0 && move < 65536);

// kh 02.06.08 Thomas Gaksch 14b5c
// kh 04.06.08 assertion does not hold any longer for toga 14b5c
//ASSERT(depth >= 0 && depth < 256);

  ASSERT((flags & ~TransFlags) == 0);
  ASSERT(value >= -32767 && value <= +32767);

// kh 02.06.08 Thomas Gaksch 14b5c
/*
  ASSERT(depth >= -127 && depth <= +127);
  ASSERT(min_value >= -ValueInf && min_value <= +ValueInf);
  ASSERT(max_value >= -ValueInf && max_value <= +ValueInf);
  ASSERT(min_value <= max_value);
*/

  trans->pTransLock->nLockId = g_pYBWCManagerInstance->nRank;

  // init

  trans->write_nb++;

  // probe

  best_entry = NULL;
  best_score = -32767;

  entry = trans_entry(trans, key);

  for(i = 0; i < ClusterSize; i++, entry++) 
  {

#if defined(DEBUG_INTENSIVE)
    entry->nLockId = g_pYBWCManagerInstance->nRank;
#endif

// kh 02.06.08 Thomas Gaksch 14b5c
    if(entry->key == key) 
    {
       // hash hit => update existing entry

      trans->write_hit++;

// kh 02.06.08 Thomas Gaksch 14b5c
      if(ENTRY_DATE(entry) != trans->date) 
      {
        trans->used++;
      }

      i       = 0;
      bBreak  = false;

      while((i < nMaxRetries) && !bBreak)
      {

// kh 02.06.08 start Thomas Gaksch 14b5c
        if(entry->depth <= depth) 
        {
          if(SmartMove && move == MoveNone) 
            move = entry->move;

          if(SmartValue && entry->depth == depth && entry->value == value) 
          {
            flags |= ENTRY_FLAGS(entry); // HACK
          }

          ASSERT(entry->key == key);
          entry->move       = move;
          entry->depth      = depth;
          entry->date_flags = (trans->date << 4) | flags;
          entry->value      = value;
//        entry->size       = node_nb; // TODO: 64->16 mapping
        } 
        else 
        { // deeper entry
          if(SmartMove && entry->move == MoveNone) 
            entry->move = move;

          entry->date_flags = (trans->date << 4) | ENTRY_FLAGS(entry);
        }
// kh 02.06.08 end Thomas Gaksch 14b5c


        if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)
        {
          if(entry_is_ok(entry))
          {
            bBreak = true;
          }
          else
          {
            if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_WARNING_PRIO_1)
            {
              YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_store(... entry not ok (1), retry write %d\n", i + 1);
            }
          }
        }
        else
        {
          bBreak = true;
        }

        i++;
      } // while((i < nMaxRetries ) && !bBreak)

      ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable || entry_is_ok(entry));

#if defined(DEBUG_INTENSIVE)
      if(entry->nLockId == g_pYBWCManagerInstance->nRank)
      {
        // kh 21.03.07 this indicates of course not sufficiently no lock conflicts
      }
      else
      {
        ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

        if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_WARNING_PRIO_1)
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_store(... mutual unsynchronized shared memory transposition table access to specific entry (1)\n");
        }
      }
#endif

      if(trans->pTransLock->nLockId == g_pYBWCManagerInstance->nRank)
      {
        // kh 19.03.07 this indicates of course not sufficiently no lock conflicts
      }
      else
      {
        ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

/*
// kh 19.03.07 avoid heavy logfile output
        if(false && g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_FORCE_OUTPUT)
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_store(... mutual unsynchronized shared memory transposition table access (1)\n");
        }
*/
      }

      return;
    } // if(entry->lock == KEY_LOCK(key)) 

    // evaluate replacement score

// kh 02.06.08 Thomas Gaksch 14b5c
    score = trans->age[ENTRY_DATE(entry)] * 256 - entry->depth;
		if(SmartReplace)
    {
      score = score * 4 - ENTRY_FLAGS(entry);
    }

    ASSERT(score > -32767);

    if(score > best_score) 
    {
      best_entry = entry;
      best_score = score;
    }

#if defined(DEBUG_INTENSIVE)
    if(entry->nLockId == g_pYBWCManagerInstance->nRank)
    {
      // kh 21.03.07 this indicates of course not sufficiently no lock conflicts
    }
    else
    {
      ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

      if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_WARNING_PRIO_1)
      {
        YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_store(... mutual unsynchronized shared memory transposition table access to specific entry (2)\n");
      }
    }
#endif

  } // for(i = 0; i < ClusterSize; i++, entry++) 

  // "best" entry found

  entry = best_entry;

  ASSERT(entry != NULL);

#if defined(DEBUG_INTENSIVE)
  entry->nLockId = g_pYBWCManagerInstance->nRank;
#endif

// kh 02.06.08 Thomas Gaksch 14b5c
  ASSERT(    (entry->key != key)
          || g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

// kh 02.06.08 Thomas Gaksch 14b5c
  if (ENTRY_DATE(entry) == trans->date)
  {
    trans->write_collision++;

// kh 02.06.08 Thomas Gaksch 14b5c
    if(!AlwaysWrite && entry->depth > depth) 
    {
        return; // do not replace deeper entries
    }
  }
  else
  {
    trans->used++;
  }

  // store

  ASSERT(entry != NULL);

// kh 02.06.08 Thomas Gaksch 14b5c
  entry->key  = key;

  i       = 0;
  bBreak  = false;

  while((i < nMaxRetries) && !bBreak)
  {

// kh 02.06.08 start Thomas Gaksch 14b5c
    entry->move       = move;
    entry->depth      = depth;
    entry->date_flags = (trans->date << 4) | flags;

    entry->value      = value;
//  entry->size       = node_nb; // TODO: 64->16 mapping
// kh 02.06.08 end Thomas Gaksch 14b5c

    if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)
    {
      if(entry_is_ok(entry))
      {
        bBreak = true;
      }
      else
      {
        if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_WARNING_PRIO_1)
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_store(... entry not ok (2), retry write %d\n", i + 1);
        }
      }
    }
    else
    {
      bBreak = true;
    }

    i++;
  } // while((i < nMaxRetries ) && !bBreak)

  ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable || entry_is_ok(entry));

#if defined(DEBUG_INTENSIVE)
  if(entry->nLockId == g_pYBWCManagerInstance->nRank)
  {
    // kh 21.03.07 this indicates of course not sufficiently no lock conflicts
  }
  else
  {
    ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

    if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_WARNING_PRIO_1)
    {
      YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_store(... mutual unsynchronized shared memory transposition table access to specific entry (1)\n");
    }
  }
#endif

  if(trans->pTransLock->nLockId == g_pYBWCManagerInstance->nRank)
  {
    // kh 19.03.07 this indicates of course not sufficiently no lock conflicts
  }
  else
  {
    ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

/*
// kh 19.03.07 avoid heavy logfile output
    if(false && g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_FORCE_OUTPUT)
    {
      YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_store(... mutual unsynchronized shared memory transposition table access (2)\n");
    }
*/
  }
}

// trans_retrieve()

// kh 02.06.08 Thomas Gaksch 14b5c
bool trans_retrieve(trans_t * trans, entry_t ** found_entry, uint64 key, int * move, int * depth, int * flags, int * value) {
  entry_t*  entry;
  int       i;

  ASSERT(trans_is_ok(trans));
  ASSERT(move != NULL);

// kh 02.06.08 Thomas Gaksch 14b5c
  ASSERT(depth != NULL);
  ASSERT(flags != NULL);
  ASSERT(value != NULL);

// kh 02.06.08 Thomas Gaksch 14b5c
/*
  ASSERT(min_depth != NULL);
  ASSERT(max_depth != NULL);
  ASSERT(min_value != NULL);
  ASSERT(max_value != NULL);
*/

// kh 19.03.07
  trans->pTransLock->nLockId = g_pYBWCManagerInstance->nRank;

  // init

  trans->read_nb++;

   // probe

  entry = trans_entry(trans, key);

  for(i = 0; i < ClusterSize; i++, entry++) 
  {

#if defined(DEBUG_INTENSIVE)
    entry->nLockId = g_pYBWCManagerInstance->nRank;
#endif

// kh 02.06.08 Thomas Gaksch 14b5c
    if(entry->key == key) 
    {
      // found

      trans->read_hit++;

// kh 02.06.08 start Thomas Gaksch 14b5c
      *move   = entry->move;
      *depth  = entry->depth;
      *flags  = ENTRY_FLAGS(entry);
      *value  = entry->value;

		 *found_entry = entry;
// kh 02.06.08 end Thomas Gaksch 14b5c

#if defined(DEBUG_INTENSIVE)
      if(entry->nLockId == g_pYBWCManagerInstance->nRank)
      {
        // kh 21.03.07 this indicates of course not sufficiently no lock conflicts
      }
      else
      {
        ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

        if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_WARNING_PRIO_1)
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_retrieve(... mutual unsynchronized shared memory transposition table access to specific entry\n");
        }
      }
#endif

      if(trans->pTransLock->nLockId == g_pYBWCManagerInstance->nRank)
      {
        // kh 19.03.07 this indicates of course not sufficiently no lock conflicts
      }
      else
      {
        ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

/*
// kh 19.03.07 avoid heavy logfile output
        if(false && g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_FORCE_OUTPUT)
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_retrieve(... mutual unsynchronized shared memory transposition table access (1)\n");
        }
*/
      }

      return true;

    } // if (entry->lock == KEY_LOCK(key)) 
  } // for(i = 0; i < ClusterSize; i++, entry++) 

  // not found

  if(trans->pTransLock->nLockId == g_pYBWCManagerInstance->nRank)
  {
    // kh 19.03.07 this indicates of course not sufficiently no lock conflicts
  }
  else
  {
    ASSERT(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable);

/*
// kh 19.03.07 avoid heavy logfile output
    if(false && g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_FORCE_OUTPUT)
    {
      YBWCManager_Printf(g_pYBWCManagerInstance, "WARNING trans_retrieve(... mutual unsynchronized shared memory transposition table access (2)\n");
    }
*/
  }

// kh 02.06.08 Thomas Gaksch 14b5c
 *found_entry = entry;

  return false;
}

// trans_stats()

void trans_stats(const trans_t * trans) 
{
   double full;
   // double hit, collision;

   ASSERT(trans_is_ok(trans));

   if(g_pYBWCManagerInstance->pFruitConfiguration->bUseSharedMemoryTranspositionTable)
   {
     full = double(trans->used + YBWCManager_CalcRootNodeSlavesTransUsed(g_pYBWCManagerInstance)) / double(trans->size);
   }
   else
   {
    full = double(trans->used) / double(trans->size);
    // hit = double(trans->read_hit) / double(trans->read_nb);
    // collision = double(trans->write_collision) / double(trans->write_nb);
   }

   send("info hashfull %.0f", full * 1000.0);
}

// trans_entry()

static entry_t * trans_entry(trans_t * trans, uint64 key) {

  uint32 index;

  ASSERT(trans_is_ok(trans));

  if (UseModulo) 
  {

// kh 02.06.08 Thomas Gaksch 14b5c
// kh 02.06.08 todo: check cast 
    index = (uint32)(key % (trans->mask + 1)); 
  } 
  else 
  {

// kh 02.06.08 Thomas Gaksch 14b5c
// kh 02.06.08 todo: check cast 
    index = (uint32)(key & trans->mask);
  }

  ASSERT(index<=trans->mask);

  return &trans->table[index];
}

// entry_is_ok()

static bool entry_is_ok(const entry_t * entry) {

// kh 06.12.08 function needs revision for 14b5c
   return true;

   if (entry == NULL) return false;

// kh 02.06.08 Thomas Gaksch 14b5c
   if (ENTRY_DATE(entry) >= DateSize) return false;

// kh 02.06.08 Thomas Gaksch 14b5c
   if (entry->move == MoveNone) return false;

   return true;
}

// end of trans.cpp
