-rw-r--r-- 3729 cdb-20251021/cdb_make.c raw
/* Public domain. */

#include <stdlib.h>
#include <errno.h>
#include "seek.h"
#include "cdb.h"
#include "cdb_make.h"

num cdb_make_start(struct cdb_make *c,num fd)
{
  c->head = 0;
  c->split = 0;
  c->hash = 0;
  c->numentries = 0;
  c->fd = fd;
  c->pos = sizeof c->final;
  outbuf_init(&c->b,outbuf_unixwrite,fd,c->bspace,sizeof c->bspace);
  return seek_set(fd,c->pos);
}

static num posplus(struct cdb_make *c,num len)
{
  num newpos = c->pos + len;
  if (newpos > CDB_LIMIT) { errno = ENOMEM; return -1; }
  c->pos = newpos;
  return 0;
}

num cdb_make_addend(struct cdb_make *c,num keylen,num datalen,num h)
{
  struct cdb_hplist *head;

  head = c->head;
  if (!head || (head->cdb_num >= CDB_HPLIST)) {
    head = (struct cdb_hplist *) malloc(sizeof(struct cdb_hplist));
    if (!head) return -1;
    head->cdb_num = 0;
    head->next = c->head;
    c->head = head;
  }
  head->hp[head->cdb_num].h = h;
  head->hp[head->cdb_num].p = c->pos;
  ++head->cdb_num;
  ++c->numentries;
  if (posplus(c,2*CDB_MAKE_NUMBYTES) == -1) return -1;
  if (posplus(c,keylen) == -1) return -1;
  if (posplus(c,datalen) == -1) return -1;
  return 0;
}

num cdb_make_addbegin(struct cdb_make *c,num keylen,num datalen)
{
  char buf[2*CDB_MAKE_NUMBYTES];

  if (keylen > CDB_LIMIT) { errno = ENOMEM; return -1; }
  if (datalen > CDB_LIMIT) { errno = ENOMEM; return -1; }

  cdb_packnum(buf,keylen);
  cdb_packnum(buf + CDB_MAKE_NUMBYTES,datalen);
  if (outbuf_putalign(&c->b,buf,2*CDB_MAKE_NUMBYTES) == -1) return -1;
  return 0;
}

num cdb_make_add(struct cdb_make *c,const char *key,num keylen,const char *data,num datalen)
{
  if (cdb_make_addbegin(c,keylen,datalen) == -1) return -1;
  if (outbuf_putalign(&c->b,key,keylen) == -1) return -1;
  if (outbuf_putalign(&c->b,data,datalen) == -1) return -1;
  return cdb_make_addend(c,keylen,datalen,cdb_hash(key,keylen));
}

num cdb_make_finish(struct cdb_make *c)
{
  char buf[2*CDB_MAKE_NUMBYTES];
  num i;
  num len;
  num u;
  num memsize;
  num count;
  num where;
  struct cdb_hplist *x;
  struct cdb_hp *hp;

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

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

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

  memsize += c->numentries; /* no overflow possible up to now */

  c->split = (struct cdb_hp *) calloc(memsize,sizeof(struct cdb_hp));
  if (!c->split) return -1;

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

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

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

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

    len = count + count; /* no overflow possible */
    cdb_packnum(c->final + 2*CDB_MAKE_NUMBYTES * i,c->pos);
    cdb_packnum(c->final + 2*CDB_MAKE_NUMBYTES * i + CDB_MAKE_NUMBYTES,len);

    for (u = 0;u < len;++u)
      c->hash[u].h = c->hash[u].p = 0;

    hp = c->split + c->start[i];
    for (u = 0;u < count;++u) {
      where = CDB_HASHTOP(hp->h) % len;
      while (c->hash[where].p)
	if (++where == len)
	  where = 0;
      c->hash[where] = *hp++;
    }

    for (u = 0;u < len;++u) {
      cdb_packnum(buf,c->hash[u].h);
      cdb_packnum(buf + CDB_MAKE_NUMBYTES,c->hash[u].p);
      if (outbuf_putalign(&c->b,buf,2*CDB_MAKE_NUMBYTES) == -1) return -1;
      if (posplus(c,2*CDB_MAKE_NUMBYTES) == -1) return -1;
    }
  }

  if (outbuf_flush(&c->b) == -1) return -1;
  if (seek_begin(c->fd) == -1) return -1;
  return outbuf_putflush(&c->b,c->final,sizeof c->final);
}