// Copyright 1994 by Jon Dart.

#include "stdafx.h"
#include "hash.h"
#include "debug.h"
#include "pinfo.h"
#include "util.h"

Hash::Hash(const unsigned size, 
        const unsigned long max_entries)
{
   my_size = size;
   my_max_entries = max_entries;
   hash_entries = 0L;
   ht = new HashList * [my_size];
   ASSERT(ht);
   for (unsigned i=0;i<my_size;i++)
      ht[i] = NULL;
}


Hash::~Hash()
{
   clear();
   delete [] ht;
}

Hashable * Hash::search( const Hashable &to_match ) const
{
    unsigned probe = (unsigned)(quickmod(to_match.hash_code(),my_size));
    UNCOND_ASSERT(probe < my_size);
    HashList *entry = ht[probe];
    if (!entry)
       return NULL;
    POSITION pos = entry->GetHeadPosition();
    while (pos)
    {
       Hashable *c = (Hashable*)entry->GetNext(pos);
       if (c->is_equal(to_match))
          return c;
    }
    return NULL;
}

BOOL Hash::insert(Hashable *p, BOOL checkPresent)
{
    if (hash_entries >= my_max_entries)
    {
        return FALSE;
    }
    hash_t h = p->hash_code();
    unsigned probe = (unsigned)(quickmod(h,my_size));
    UNCOND_ASSERT(probe < my_size);
    HashList *entry = ht[probe];
    if (!entry)
    {
       ht[probe] = new HashList;
       ASSERT(ht[probe]);
       ht[probe]->AddTail(p);
    }
    else
    {
       if (checkPresent)
       {
           POSITION pos = entry->GetHeadPosition();
           while (pos)
           {
              Hashable *c = (Hashable*)entry->GetNext(pos);
              if (c->is_equal(*p))
                 return FALSE; // already in there
           }
       }
       entry->AddHead(p);
    }
    hash_entries++;
    return TRUE;
}

int Hash::replace(const Hashable &p)
{
    hash_t h = p.hash_code();
    unsigned probe = (unsigned)(quickmod(h,my_size));
    UNCOND_ASSERT(probe < my_size);
    HashList *entry = ht[probe];
    Position_Info *newEntry = (Position_Info*)&p;
    if (!entry)
    {
       if (hash_entries >= my_max_entries) // can't replace
       {
          return 2;
       }
       ht[probe] = new HashList();
       ASSERT(ht[probe]);
       ht[probe]->AddTail(new Position_Info(*newEntry));
       hash_entries++;
       return 0; // inserted
    }
    else
    {
       Hashable *retVal = NULL;
       if (hash_entries >= my_max_entries)
       {
          POSITION pos = entry->lastReplacePos;
          if (pos == NULL)
          {
             pos = entry->GetHeadPosition();
          }
          Position_Info *leastValuable = NULL;
          int minDepth = newEntry->depth();
          int count = 0;
          while (pos && count < 4)
          {
              Position_Info *oldEntry = (Position_Info*)entry->GetNext(pos);
              if (oldEntry->type() != Position_Info::Pv)
              {
              if (oldEntry->age() != newEntry->age())
              {
                 leastValuable = oldEntry;
                 break;
              }
              else if (oldEntry->depth() < minDepth)
              {
                 minDepth = oldEntry->depth();
                 leastValuable = oldEntry;
              }
              }
              ++count;
          }
          entry->lastReplacePos = pos; // save for next search
          if (leastValuable)
          {
              *leastValuable = *newEntry; // replaced
              return 1;
          }
          return 2; // insert failed
       }
       else 
       {
          entry->AddTail(new Position_Info(*newEntry));
          hash_entries++;
          return 0; // inserted
       }
    }
}

void Hash::remove(Hashable *p)
{
    hash_t h = p->hash_code();
    unsigned probe = (unsigned)(quickmod(h,my_size));
    UNCOND_ASSERT(probe < my_size);
    HashList *entry = ht[probe];
    if (entry)
    {
    POSITION pos = entry->GetHeadPosition();
    while (pos)
    {
       POSITION prev = pos;
       Hashable *c = (Hashable*)entry->GetNext(pos);
       if (c->is_equal(*p))
       {
          entry->RemoveAt(prev);
          delete c;
          hash_entries--;
          return;
       }
    }
    }
}

void Hash::clear(BOOL final)
{
   for (unsigned i = 0; i < my_size; i++)
   {
       if (ht[i])
       {
           HashList *list = ht[i];
           delete list;
           ht[i] = NULL;
       }
   }
   hash_entries = 0;
}

unsigned long Hash::num_entries() const
{
   return hash_entries;
}



