// Copyright (C) 1999,2000 Bruce Guenter <bruceg@em.ca>

//

// This program is free software; you can redistribute it and/or modify

// it under the terms of the GNU General Public License as published by

// the Free Software Foundation; either version 2 of the License, or

// (at your option) any later version.

//

// This program is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

//

// You should have received a copy of the GNU General Public License

// along with this program; if not, write to the Free Software

// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#include "cdb++.h"

#include "internal.h"

cdbmake::cdbmake()

  : head(0), split(0), hash(0), numentries(0)

{

}

cdbmake::~cdbmake()

{

  delete[] split;

  hplist* x = head;

  while(x) {

    hplist* next = x->next;

    delete x;

    x = next;

  }

}

int cdbmake::add(uint32 h, uint32 p)

{

  hplist *chead = head;

  if (!chead || (chead->num >= CDBMAKE_HPLIST)) {

    chead = new hplist;

    if (!chead) return 0;

    chead->num = 0;

    chead->next = head;

    head = chead;

  }

  chead->hp[chead->num].h = h;

  chead->hp[chead->num].p = p;

  ++chead->num;

  ++numentries;

  return 1;

}

int cdbmake::split_hashes()

{

  for (int i = 0; i < 256; ++i)

    count[i] = 0;

  for (hplist* x = head; x; x = x->next) {

    for(int i = x->num; i--; )

      ++count[255 & x->hp[i].h];

  }

  uint32 memsize = 1;

  for (int i = 0; i < 256; ++i) {

    uint32 u = count[i] * 2;

    if (u > memsize)

      memsize = u;

  }

  memsize += numentries;	// no overflow possible up to now

  uint32 u = (uint32) 0 - (uint32) 1;

  u /= sizeof(hp);

  if (memsize > u) return 0;

  split = new hp[memsize];

  if (!split) return 0;

  hash = split + numentries;

  u = 0;

  for (int i = 0;i < 256;++i) {

    u += count[i];		// bounded by numentries, so no overflow

    start[i] = u;

  }

  for (hplist* x = head; x; x = x->next) {

    int i = x->num;

    while (i--)

      split[--start[255 & x->hp[i].h]] = x->hp[i];

  }

  return 1;

}

uint32 cdbmake::throw_hash(uint32 pos, int b)

{

  uint32 c = count[b];

  uint32 len = c + c;		// no overflow possible

  pack(final + 8 * b, pos);

  pack(final + 8 * b + 4, len);

  if (len) {

    for (uint32 j = 0; j < len; ++j)

      hash[j].h = hash[j].p = 0;

    hp* hp = split + start[b];

    for (uint32 j = 0; j < count[b]; ++j) {

      uint32 where = (hp->h >> 8) % len;

      while (hash[where].p)

	if (++where == len)

	  where = 0;

      hash[where] = *hp++;

    }

  }

  return len;

}