cdbmake_add.c

Go to the documentation of this file.

#include "cdbmake.h"
#include "alloc.h"

void cdbmake_init(struct cdbmake *cdbm)
{
  cdbm->head = 0;
  cdbm->split = 0;
  cdbm->hash = 0;
  cdbm->numentries = 0;
}

int cdbmake_add(struct cdbmake *cdbm,uint32 h,uint32 p,char *(*alloc)())
{
  struct cdbmake_hplist *head;

  head = cdbm->head;
  if (!head || (head->num >= CDBMAKE_HPLIST)) {
    head = (struct cdbmake_hplist *) alloc(sizeof(struct cdbmake_hplist));
    if (!head) return 0;
    head->num = 0;
    head->next = cdbm->head;
    cdbm->head = head;
  }
  head->hp[head->num].h = h;
  head->hp[head->num].p = p;
  ++head->num;
  ++cdbm->numentries;
  return 1;
}

int cdbmake_split(struct cdbmake *cdbm,char *(*alloc)())
{
  int i;
  uint32 u;
  uint32 memsize;
  struct cdbmake_hplist *x;

  for (i = 0;i < 256;++i)
    cdbm->count[i] = 0;

  for (x = cdbm->head;x;x = x->next) {
    i = x->num;
    while (i--)
      ++cdbm->count[255 & x->hp[i].h];
  }

  memsize = 1;
  for (i = 0;i < 256;++i) {
    u = cdbm->count[i] * 2;
    if (u > memsize)
      memsize = u;
  }

  memsize += cdbm->numentries; /* no overflow possible up to now */
  u = (uint32) 0 - (uint32) 1;
  u /= sizeof(struct cdbmake_hp);
  if (memsize > u) return 0;

  cdbm->split = (struct cdbmake_hp *) alloc(memsize * sizeof(struct cdbmake_hp));
  if (!cdbm->split) return 0;

  cdbm->hash = cdbm->split + cdbm->numentries;

  u = 0;
  for (i = 0;i < 256;++i) {
    u += cdbm->count[i]; /* bounded by numentries, so no overflow */
    cdbm->start[i] = u;
  }

  for (x = cdbm->head;x;x = x->next) {
    i = x->num;
    while (i--)
      cdbm->split[--cdbm->start[255 & x->hp[i].h]] = x->hp[i];
  }

  return 1;
}

uint32 cdbmake_throw(struct cdbmake *cdbm,uint32 pos,int b)
{
  uint32 len;
  uint32 j;
  uint32 count;
  struct cdbmake_hp *hp;
  uint32 where;

  count = cdbm->count[b];

  len = count + count; /* no overflow possible */
  cdbmake_pack(cdbm->final + 8 * b,pos);
  cdbmake_pack(cdbm->final + 8 * b + 4,len);

  if (len) {
    for (j = 0;j < len;++j)
      cdbm->hash[j].h = cdbm->hash[j].p = 0;

    hp = cdbm->split + cdbm->start[b];
    for (j = 0;j < count;++j) {
      where = (hp->h >> 8) % len;
      while (cdbm->hash[where].p)
        if (++where == len)
          where = 0;
      cdbm->hash[where] = *hp++;
    }
  }

  return len;
}