// Copyright 1994 by Jon Dart.

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

struct BIGINT
{
  DWORD low;
  DWORD high;
};

union INT64UNION
{
  BIGINT b;
  hash_t u;
};

static inline int32 quickmod(hash_t hashcode, int32 buckets)
{
   // We do a modulus only on the low order DWORD of the hashcode,
   // to save time.
   INT64UNION un;
   un.u = hashcode;
   return (int32)(un.b.low % buckets);
}

Hash::Hash(const unsigned size, 
        const unsigned long max_entries)
{
   my_size = size;
   my_max_entries = max_entries;
   hash_entries = 0L;
   ht = new CPtrList * [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 )
{
    unsigned probe = (unsigned)(quickmod(to_match.hash_code(),my_size));
    UNCOND_ASSERT(probe < my_size);
    CPtrList *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);
    CPtrList *entry = ht[probe];
    if (!entry)
    {
       ht[probe] = new CPtrList;
       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;
}

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

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



