Geo-LatLon2Place/cdb-embedded.c

/* embeddable/static cdb version by schmorp */

/* cdb.h: public cdb include file
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

#ifndef TINYCDB_VERSION
#define TINYCDB_VERSION 0.78

#ifdef __cplusplus
extern "C" {
#endif

typedef unsigned int cdbi_t; /* compatibility */

/* common routines */
static unsigned cdb_hash(const void *buf, unsigned len);
static unsigned cdb_unpack(const unsigned char buf[4]);
static void cdb_pack(unsigned num, unsigned char buf[4]);

struct cdb {
  int cdb_fd;                   /* file descriptor */
  /* private members */
  unsigned cdb_fsize;           /* datafile size */
  unsigned cdb_dend;            /* end of data ptr */
  const unsigned char *cdb_mem; /* mmap'ed file memory */
  unsigned cdb_vpos, cdb_vlen;  /* found data */
  unsigned cdb_kpos, cdb_klen;  /* found key */
};

#define CDB_STATIC_INIT {0,0,0,0,0,0,0,0}

#define cdb_datapos(c) ((c)->cdb_vpos)
#define cdb_datalen(c) ((c)->cdb_vlen)
#define cdb_keypos(c) ((c)->cdb_kpos)
#define cdb_keylen(c) ((c)->cdb_klen)
#define cdb_fileno(c) ((c)->cdb_fd)

static int cdb_init(struct cdb *cdbp, int fd);
static void cdb_free(struct cdb *cdbp);

static int cdb_read(const struct cdb *cdbp,
             void *buf, unsigned len, unsigned pos);
#define cdb_readdata(cdbp, buf) \
        cdb_read((cdbp), (buf), cdb_datalen(cdbp), cdb_datapos(cdbp))
#define cdb_readkey(cdbp, buf) \
        cdb_read((cdbp), (buf), cdb_keylen(cdbp), cdb_keypos(cdbp))

static const void *cdb_get(const struct cdb *cdbp, unsigned len, unsigned pos);
#define cdb_getdata(cdbp) \
        cdb_get((cdbp), cdb_datalen(cdbp), cdb_datapos(cdbp))
#define cdb_getkey(cdbp) \
        cdb_get((cdbp), cdb_keylen(cdbp), cdb_keypos(cdbp))

static int cdb_find(struct cdb *cdbp, const void *key, unsigned klen);

struct cdb_find {
  struct cdb *cdb_cdbp;
  unsigned cdb_hval;
  const unsigned char *cdb_htp, *cdb_htab, *cdb_htend;
  unsigned cdb_httodo;
  const void *cdb_key;
  unsigned cdb_klen;
};

static int cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
                 const void *key, unsigned klen);
static int cdb_findnext(struct cdb_find *cdbfp);

#define cdb_seqinit(cptr, cdbp) ((*(cptr))=2048)
static int cdb_seqnext(unsigned *cptr, struct cdb *cdbp);

/* old simple interface */
/* open file using standard routine, then: */
static int cdb_seek(int fd, const void *key, unsigned klen, unsigned *dlenp);
static int cdb_bread(int fd, void *buf, int len);

/* cdb_make */

struct cdb_make {
  int cdb_fd;                   /* file descriptor */
  /* private */
  unsigned cdb_dpos;            /* data position so far */
  unsigned cdb_rcnt;            /* record count so far */
  unsigned char cdb_buf[4096];  /* write buffer */
  unsigned char *cdb_bpos;      /* current buf position */
  struct cdb_rl *cdb_rec[256];  /* list of arrays of record infos */
};

enum cdb_put_mode {
  CDB_PUT_ADD = 0,      /* add unconditionnaly, like cdb_make_add() */
#define CDB_PUT_ADD     CDB_PUT_ADD
  CDB_FIND = CDB_PUT_ADD,
  CDB_PUT_REPLACE,      /* replace: do not place to index OLD record */
#define CDB_PUT_REPLACE CDB_PUT_REPLACE
  CDB_FIND_REMOVE = CDB_PUT_REPLACE,
  CDB_PUT_INSERT,       /* add only if not already exists */
#define CDB_PUT_INSERT  CDB_PUT_INSERT
  CDB_PUT_WARN,         /* add unconditionally but ret. 1 if exists */
#define CDB_PUT_WARN    CDB_PUT_WARN
  CDB_PUT_REPLACE0,     /* if a record exists, fill old one with zeros */
#define CDB_PUT_REPLACE0 CDB_PUT_REPLACE0
  CDB_FIND_FILL0 = CDB_PUT_REPLACE0
};

static int cdb_make_start(struct cdb_make *cdbmp, int fd);
static int cdb_make_add(struct cdb_make *cdbmp,
                 const void *key, unsigned klen,
                 const void *val, unsigned vlen);
static int cdb_make_exists(struct cdb_make *cdbmp,
                    const void *key, unsigned klen);
static int cdb_make_find(struct cdb_make *cdbmp,
                  const void *key, unsigned klen,
                  enum cdb_put_mode mode);
static int cdb_make_put(struct cdb_make *cdbmp,
                 const void *key, unsigned klen,
                 const void *val, unsigned vlen,
                 enum cdb_put_mode mode);
static int cdb_make_finish(struct cdb_make *cdbmp);

#ifdef __cplusplus
} /* extern "C" */
#endif

#endif /* include guard */

/* cdb_int.h: internal cdb library declarations
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

#include <errno.h>
#include <string.h>

#ifndef EPROTO
# define EPROTO EINVAL
#endif

#define internal_function static

struct cdb_rec {
  unsigned hval;
  unsigned rpos;
};

struct cdb_rl {
  struct cdb_rl *next;
  unsigned cnt;
  struct cdb_rec rec[254];
};

static int _cdb_make_write(struct cdb_make *cdbmp,
                    const void *ptr, unsigned len);
static int _cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len);
static int _cdb_make_flush(struct cdb_make *cdbmp);
static int _cdb_make_add(struct cdb_make *cdbmp, unsigned hval,
                  const void *key, unsigned klen,
                  const void *val, unsigned vlen);

/* cdb_find.c: cdb_find routine
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

static int
cdb_find(struct cdb *cdbp, const void *key, unsigned klen)
{
  const unsigned char *htp;     /* hash table pointer */
  const unsigned char *htab;    /* hash table */
  const unsigned char *htend;   /* end of hash table */
  unsigned httodo;              /* ht bytes left to look */
  unsigned pos, n;

  unsigned hval;

  if (klen >= cdbp->cdb_dend)   /* if key size is too large */
    return 0;

  hval = cdb_hash(key, klen);

  /* find (pos,n) hash table to use */
  /* first 2048 bytes (toc) are always available */
  /* (hval % 256) * 8 */
  htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
  n = cdb_unpack(htp + 4);      /* table size */
  if (!n)                       /* empty table */
    return 0;                   /* not found */
  httodo = n << 3;              /* bytes of htab to lookup */
  pos = cdb_unpack(htp);        /* htab position */
  if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
      || pos < cdbp->cdb_dend /* is htab inside data section ? */
      || pos > cdbp->cdb_fsize /* htab start within file ? */
      || httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
    return errno = EPROTO, -1;

  htab = cdbp->cdb_mem + pos;   /* htab pointer */
  htend = htab + httodo;        /* after end of htab */
  /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
  htp = htab + (((hval >> 8) % n) << 3);

  for(;;) {
    pos = cdb_unpack(htp + 4);  /* record position */
    if (!pos)
      return 0;
    if (cdb_unpack(htp) == hval) {
      if (pos > cdbp->cdb_dend - 8) /* key+val lengths */
        return errno = EPROTO, -1;
      if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
        if (cdbp->cdb_dend - klen < pos + 8)
          return errno = EPROTO, -1;
        if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
          n = cdb_unpack(cdbp->cdb_mem + pos + 4);
          pos += 8;
          if (cdbp->cdb_dend < n || cdbp->cdb_dend - n < pos + klen)
            return errno = EPROTO, -1;
          cdbp->cdb_kpos = pos;
          cdbp->cdb_klen = klen;
          cdbp->cdb_vpos = pos + klen;
          cdbp->cdb_vlen = n;
          return 1;
        }
      }
    }
    httodo -= 8;
    if (!httodo)
      return 0;
    if ((htp += 8) >= htend)
      htp = htab;
  }

}

/* cdb_hash.c: cdb hashing routine
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

static unsigned
cdb_hash(const void *buf, unsigned len)
{
  register const unsigned char *p = (const unsigned char *)buf;
  register const unsigned char *end = p + len;
  register unsigned hash = 5381;        /* start value */
  while (p < end)
    hash = (hash + (hash << 5)) ^ *p++;
  return hash;
}

/* cdb_init.c: cdb_init, cdb_free and cdb_read routines
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

#include <sys/types.h>
#ifdef _WIN32
# include <windows.h>
#else
# include <sys/mman.h>
# ifndef MAP_FAILED
#  define MAP_FAILED ((void*)-1)
# endif
#endif
#include <sys/stat.h>

static int
cdb_init(struct cdb *cdbp, int fd)
{
  struct stat st;
  unsigned char *mem;
  unsigned fsize, dend;
#ifdef _WIN32
  HANDLE hFile, hMapping;
#endif

  /* get file size */
  if (fstat(fd, &st) < 0)
    return -1;
  /* trivial sanity check: at least toc should be here */
  if (st.st_size < 2048)
    return errno = EPROTO, -1;
  fsize = st.st_size < 0xffffffffu ? st.st_size : 0xffffffffu;
  /* memory-map file */
#ifdef _WIN32
  hFile = (HANDLE) _get_osfhandle(fd);
  if (hFile == (HANDLE) -1)
    return -1;
  hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
  if (!hMapping)
    return -1;
  mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
  CloseHandle(hMapping);
  if (!mem)
    return -1;
#else
  mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
  if (mem == MAP_FAILED)
    return -1;
#endif /* _WIN32 */

  cdbp->cdb_fd = fd;
  cdbp->cdb_fsize = fsize;
  cdbp->cdb_mem = mem;

#if 0
  /* XXX don't know well about madvise syscall -- is it legal
     to set different options for parts of one mmap() region?
     There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc...
  */
#ifdef MADV_RANDOM
  /* set madvise() parameters. Ignore errors for now if system
     doesn't support it */
  madvise(mem, 2048, MADV_WILLNEED);
  madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM);
#endif
#endif

  cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
  cdbp->cdb_kpos = cdbp->cdb_klen = 0;
  dend = cdb_unpack(mem);
  if (dend < 2048) dend = 2048;
  else if (dend >= fsize) dend = fsize;
  cdbp->cdb_dend = dend;

  return 0;
}

static void
cdb_free(struct cdb *cdbp)
{
  if (cdbp->cdb_mem) {
#ifdef _WIN32
    UnmapViewOfFile((void*) cdbp->cdb_mem);
#else
    munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
#endif /* _WIN32 */
    cdbp->cdb_mem = NULL;
  }
  cdbp->cdb_fsize = 0;
}

static const void *
cdb_get(const struct cdb *cdbp, unsigned len, unsigned pos)
{
  if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) {
    errno = EPROTO;
    return NULL;
  }
  return cdbp->cdb_mem + pos;
}

static int
cdb_read(const struct cdb *cdbp, void *buf, unsigned len, unsigned pos)
{
  const void *data = cdb_get(cdbp, len, pos);
  if (!data) return -1;
  memcpy(buf, data, len);
  return 0;
}

/* cdb_make_add.c: basic cdb_make_add routine
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

#include <stdlib.h> /* for malloc */

int internal_function
_cdb_make_add(struct cdb_make *cdbmp, unsigned hval,
              const void *key, unsigned klen,
              const void *val, unsigned vlen)
{
  unsigned char rlen[8];
  struct cdb_rl *rl;
  unsigned i;
  if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
      vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8))
    return errno = ENOMEM, -1;
  i = hval & 255;
  rl = cdbmp->cdb_rec[i];
  if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
    rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
    if (!rl)
      return errno = ENOMEM, -1;
    rl->cnt = 0;
    rl->next = cdbmp->cdb_rec[i];
    cdbmp->cdb_rec[i] = rl;
  }
  i = rl->cnt++;
  rl->rec[i].hval = hval;
  rl->rec[i].rpos = cdbmp->cdb_dpos;
  ++cdbmp->cdb_rcnt;
  cdb_pack(klen, rlen);
  cdb_pack(vlen, rlen + 4);
  if (_cdb_make_write(cdbmp, rlen, 8) < 0 ||
      _cdb_make_write(cdbmp, key, klen) < 0 ||
      _cdb_make_write(cdbmp, val, vlen) < 0)
    return -1;
  return 0;
}

static int
cdb_make_add(struct cdb_make *cdbmp,
             const void *key, unsigned klen,
             const void *val, unsigned vlen) {
  return _cdb_make_add(cdbmp, cdb_hash(key, klen), key, klen, val, vlen);
}

/* cdb_unpack.c: unpack 32bit integer
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

static inline unsigned
cdb_unpack(const unsigned char buf[4])
{
  unsigned n = buf[3];
  n <<= 8; n |= buf[2];
  n <<= 8; n |= buf[1];
  n <<= 8; n |= buf[0];
  return n;
}

/* cdb_make.c: basic cdb creation routines
 *
 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
 * Public domain.
 */

#include <unistd.h>
#include <stdlib.h>
#include <string.h>

static inline void
cdb_pack(unsigned num, unsigned char buf[4])
{
  buf[0] = num & 255; num >>= 8;
  buf[1] = num & 255; num >>= 8;
  buf[2] = num & 255;
  buf[3] = num >> 8;
}

static int
cdb_make_start(struct cdb_make *cdbmp, int fd)
{
  memset(cdbmp, 0, sizeof(*cdbmp));
  cdbmp->cdb_fd = fd;
  cdbmp->cdb_dpos = 2048;
  cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
  return 0;
}

int internal_function
_cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len)
{
  while(len) {
    int l = write(fd, buf, len);
    if (l > 0) {
      len -= l;
      buf += l;
    }
    else if (l < 0 && errno != EINTR)
      return -1;
  }
  return 0;
}

int internal_function
_cdb_make_flush(struct cdb_make *cdbmp) {
  unsigned len = cdbmp->cdb_bpos - cdbmp->cdb_buf;
  if (len) {
    if (_cdb_make_fullwrite(cdbmp->cdb_fd, cdbmp->cdb_buf, len) < 0)
      return -1;
    cdbmp->cdb_bpos = cdbmp->cdb_buf;
  }
  return 0;
}

int internal_function
_cdb_make_write(struct cdb_make *cdbmp, const void *ptr_, unsigned len)
{
  const unsigned char *ptr = (const unsigned char *)ptr_;
  unsigned l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
  cdbmp->cdb_dpos += len;
  if (len > l) {
    memcpy(cdbmp->cdb_bpos, ptr, l);
    cdbmp->cdb_bpos += l;
    if (_cdb_make_flush(cdbmp) < 0)
      return -1;
    ptr += l; len -= l;
    l = len / sizeof(cdbmp->cdb_buf);
    if (l) {
      l *= sizeof(cdbmp->cdb_buf);
      if (_cdb_make_fullwrite(cdbmp->cdb_fd, ptr, l) < 0)
        return -1;
      ptr += l; len -= l;
    }
  }
  if (len) {
    memcpy(cdbmp->cdb_bpos, ptr, len);
    cdbmp->cdb_bpos += len;
  }
  return 0;
}

static int
cdb_make_finish_internal(struct cdb_make *cdbmp)
{
  unsigned hcnt[256];           /* hash table counts */
  unsigned hpos[256];           /* hash table positions */
  struct cdb_rec *htab;
  unsigned char *p;
  struct cdb_rl *rl;
  unsigned hsize;
  unsigned t, i;

  if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt)
    return errno = ENOMEM, -1;

  /* count htab sizes and reorder reclists */
  hsize = 0;
  for (t = 0; t < 256; ++t) {
    struct cdb_rl *rlt = NULL;
    i = 0;
    rl = cdbmp->cdb_rec[t];
    while(rl) {
      struct cdb_rl *rln = rl->next;
      rl->next = rlt;
      rlt = rl;
      i += rl->cnt;
      rl = rln;
    }
    cdbmp->cdb_rec[t] = rlt;
    if (hsize < (hcnt[t] = i << 1))
      hsize = hcnt[t];
  }

  /* allocate memory to hold max htable */
  htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
  if (!htab)
    return errno = ENOENT, -1;
  p = (unsigned char *)htab;
  htab += 2;

  /* build hash tables */
  for (t = 0; t < 256; ++t) {
    unsigned len, hi;
    hpos[t] = cdbmp->cdb_dpos;
    if ((len = hcnt[t]) == 0)
      continue;
    for (i = 0; i < len; ++i)
      htab[i].hval = htab[i].rpos = 0;
    for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
      for (i = 0; i < rl->cnt; ++i) {
       hi = (rl->rec[i].hval >> 8) % len;
        while(htab[hi].rpos)
          if (++hi == len)
            hi = 0;
        htab[hi] = rl->rec[i];
      }
    for (i = 0; i < len; ++i) {
      cdb_pack(htab[i].hval, p + (i << 3));
      cdb_pack(htab[i].rpos, p + (i << 3) + 4);
    }
    if (_cdb_make_write(cdbmp, p, len << 3) < 0) {
      free(p);
      return -1;
    }
  }
  free(p);
  if (_cdb_make_flush(cdbmp) < 0)
    return -1;
  p = cdbmp->cdb_buf;
  for (t = 0; t < 256; ++t) {
    cdb_pack(hpos[t], p + (t << 3));
    cdb_pack(hcnt[t], p + (t << 3) + 4);
  }
  if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
      _cdb_make_fullwrite(cdbmp->cdb_fd, p, 2048) != 0)
    return -1;

  return 0;
}

static void
cdb_make_free(struct cdb_make *cdbmp)
{
  unsigned t;
  for(t = 0; t < 256; ++t) {
    struct cdb_rl *rl = cdbmp->cdb_rec[t];
    while(rl) {
      struct cdb_rl *tm = rl;
      rl = rl->next;
      free(tm);
    }
  }
}

static int
cdb_make_finish(struct cdb_make *cdbmp)
{
  int r = cdb_make_finish_internal(cdbmp);
  cdb_make_free(cdbmp);
  return r;
}

Revision:	1.3
Committed:	Thu Mar 17 22:55:34 2022 UTC (3 years, 11 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-1_0, HEAD
Changes since 1.2:	+3 -2 lines
Log Message:	convert to c++
#	Content
1	/* embeddable/static cdb version by schmorp */
2
3	/* cdb.h: public cdb include file
4	*
5	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
6	* Public domain.
7	*/
8
9	#ifndef TINYCDB_VERSION
10	#define TINYCDB_VERSION 0.78
11
12	#ifdef __cplusplus
13	extern "C" {
14	#endif
15
16	typedef unsigned int cdbi_t; /* compatibility */
17
18	/* common routines */
19	static unsigned cdb_hash(const void *buf, unsigned len);
20	static unsigned cdb_unpack(const unsigned char buf[4]);
21	static void cdb_pack(unsigned num, unsigned char buf[4]);
22
23	struct cdb {
24	int cdb_fd; /* file descriptor */
25	/* private members */
26	unsigned cdb_fsize; /* datafile size */
27	unsigned cdb_dend; /* end of data ptr */
28	const unsigned char cdb_mem; / mmap'ed file memory */
29	unsigned cdb_vpos, cdb_vlen; /* found data */
30	unsigned cdb_kpos, cdb_klen; /* found key */
31	};
32
33	#define CDB_STATIC_INIT {0,0,0,0,0,0,0,0}
34
35	#define cdb_datapos(c) ((c)->cdb_vpos)
36	#define cdb_datalen(c) ((c)->cdb_vlen)
37	#define cdb_keypos(c) ((c)->cdb_kpos)
38	#define cdb_keylen(c) ((c)->cdb_klen)
39	#define cdb_fileno(c) ((c)->cdb_fd)
40
41	static int cdb_init(struct cdb *cdbp, int fd);
42	static void cdb_free(struct cdb *cdbp);
43
44	static int cdb_read(const struct cdb *cdbp,
45	void *buf, unsigned len, unsigned pos);
46	#define cdb_readdata(cdbp, buf) \
47	cdb_read((cdbp), (buf), cdb_datalen(cdbp), cdb_datapos(cdbp))
48	#define cdb_readkey(cdbp, buf) \
49	cdb_read((cdbp), (buf), cdb_keylen(cdbp), cdb_keypos(cdbp))
50
51	static const void cdb_get(const struct cdb cdbp, unsigned len, unsigned pos);
52	#define cdb_getdata(cdbp) \
53	cdb_get((cdbp), cdb_datalen(cdbp), cdb_datapos(cdbp))
54	#define cdb_getkey(cdbp) \
55	cdb_get((cdbp), cdb_keylen(cdbp), cdb_keypos(cdbp))
56
57	static int cdb_find(struct cdb cdbp, const void key, unsigned klen);
58
59	struct cdb_find {
60	struct cdb *cdb_cdbp;
61	unsigned cdb_hval;
62	const unsigned char cdb_htp, cdb_htab, *cdb_htend;
63	unsigned cdb_httodo;
64	const void *cdb_key;
65	unsigned cdb_klen;
66	};
67
68	static int cdb_findinit(struct cdb_find cdbfp, struct cdb cdbp,
69	const void *key, unsigned klen);
70	static int cdb_findnext(struct cdb_find *cdbfp);
71
72	#define cdb_seqinit(cptr, cdbp) ((*(cptr))=2048)
73	static int cdb_seqnext(unsigned cptr, struct cdb cdbp);
74
75	/* old simple interface */
76	/* open file using standard routine, then: */
77	static int cdb_seek(int fd, const void key, unsigned klen, unsigned dlenp);
78	static int cdb_bread(int fd, void *buf, int len);
79
80	/* cdb_make */
81
82	struct cdb_make {
83	int cdb_fd; /* file descriptor */
84	/* private */
85	unsigned cdb_dpos; /* data position so far */
86	unsigned cdb_rcnt; /* record count so far */
87	unsigned char cdb_buf[4096]; /* write buffer */
88	unsigned char cdb_bpos; / current buf position */
89	struct cdb_rl cdb_rec[256]; / list of arrays of record infos */
90	};
91
92	enum cdb_put_mode {
93	CDB_PUT_ADD = 0, /* add unconditionnaly, like cdb_make_add() */
94	#define CDB_PUT_ADD CDB_PUT_ADD
95	CDB_FIND = CDB_PUT_ADD,
96	CDB_PUT_REPLACE, /* replace: do not place to index OLD record */
97	#define CDB_PUT_REPLACE CDB_PUT_REPLACE
98	CDB_FIND_REMOVE = CDB_PUT_REPLACE,
99	CDB_PUT_INSERT, /* add only if not already exists */
100	#define CDB_PUT_INSERT CDB_PUT_INSERT
101	CDB_PUT_WARN, /* add unconditionally but ret. 1 if exists */
102	#define CDB_PUT_WARN CDB_PUT_WARN
103	CDB_PUT_REPLACE0, /* if a record exists, fill old one with zeros */
104	#define CDB_PUT_REPLACE0 CDB_PUT_REPLACE0
105	CDB_FIND_FILL0 = CDB_PUT_REPLACE0
106	};
107
108	static int cdb_make_start(struct cdb_make *cdbmp, int fd);
109	static int cdb_make_add(struct cdb_make *cdbmp,
110	const void *key, unsigned klen,
111	const void *val, unsigned vlen);
112	static int cdb_make_exists(struct cdb_make *cdbmp,
113	const void *key, unsigned klen);
114	static int cdb_make_find(struct cdb_make *cdbmp,
115	const void *key, unsigned klen,
116	enum cdb_put_mode mode);
117	static int cdb_make_put(struct cdb_make *cdbmp,
118	const void *key, unsigned klen,
119	const void *val, unsigned vlen,
120	enum cdb_put_mode mode);
121	static int cdb_make_finish(struct cdb_make *cdbmp);
122
123	#ifdef __cplusplus
124	} /* extern "C" */
125	#endif
126
127	#endif /* include guard */
128
129	/* cdb_int.h: internal cdb library declarations
130	*
131	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
132	* Public domain.
133	*/
134
135	#include <errno.h>
136	#include <string.h>
137
138	#ifndef EPROTO
139	# define EPROTO EINVAL
140	#endif
141
142	#define internal_function static
143
144	struct cdb_rec {
145	unsigned hval;
146	unsigned rpos;
147	};
148
149	struct cdb_rl {
150	struct cdb_rl *next;
151	unsigned cnt;
152	struct cdb_rec rec[254];
153	};
154
155	static int _cdb_make_write(struct cdb_make *cdbmp,
156	const void *ptr, unsigned len);
157	static int _cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len);
158	static int _cdb_make_flush(struct cdb_make *cdbmp);
159	static int _cdb_make_add(struct cdb_make *cdbmp, unsigned hval,
160	const void *key, unsigned klen,
161	const void *val, unsigned vlen);
162
163	/* cdb_find.c: cdb_find routine
164	*
165	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
166	* Public domain.
167	*/
168
169	static int
170	cdb_find(struct cdb cdbp, const void key, unsigned klen)
171	{
172	const unsigned char htp; / hash table pointer */
173	const unsigned char htab; / hash table */
174	const unsigned char htend; / end of hash table */
175	unsigned httodo; /* ht bytes left to look */
176	unsigned pos, n;
177
178	unsigned hval;
179
180	if (klen >= cdbp->cdb_dend) /* if key size is too large */
181	return 0;
182
183	hval = cdb_hash(key, klen);
184
185	/* find (pos,n) hash table to use */
186	/* first 2048 bytes (toc) are always available */
187	/* (hval % 256) * 8 */
188	htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
189	n = cdb_unpack(htp + 4); /* table size */
190	if (!n) /* empty table */
191	return 0; /* not found */
192	httodo = n << 3; /* bytes of htab to lookup */
193	pos = cdb_unpack(htp); /* htab position */
194	if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
195	\|\| pos < cdbp->cdb_dend /* is htab inside data section ? */
196	\|\| pos > cdbp->cdb_fsize /* htab start within file ? */
197	\|\| httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
198	return errno = EPROTO, -1;
199
200	htab = cdbp->cdb_mem + pos; /* htab pointer */
201	htend = htab + httodo; /* after end of htab */
202	/* htab starting position: rest of hval modulo htsize, 8bytes per elt */
203	htp = htab + (((hval >> 8) % n) << 3);
204
205	for(;;) {
206	pos = cdb_unpack(htp + 4); /* record position */
207	if (!pos)
208	return 0;
209	if (cdb_unpack(htp) == hval) {
210	if (pos > cdbp->cdb_dend - 8) /* key+val lengths */
211	return errno = EPROTO, -1;
212	if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
213	if (cdbp->cdb_dend - klen < pos + 8)
214	return errno = EPROTO, -1;
215	if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
216	n = cdb_unpack(cdbp->cdb_mem + pos + 4);
217	pos += 8;
218	if (cdbp->cdb_dend < n \|\| cdbp->cdb_dend - n < pos + klen)
219	return errno = EPROTO, -1;
220	cdbp->cdb_kpos = pos;
221	cdbp->cdb_klen = klen;
222	cdbp->cdb_vpos = pos + klen;
223	cdbp->cdb_vlen = n;
224	return 1;
225	}
226	}
227	}
228	httodo -= 8;
229	if (!httodo)
230	return 0;
231	if ((htp += 8) >= htend)
232	htp = htab;
233	}
234
235	}
236
237	/* cdb_hash.c: cdb hashing routine
238	*
239	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
240	* Public domain.
241	*/
242
243	static unsigned
244	cdb_hash(const void *buf, unsigned len)
245	{
246	register const unsigned char p = (const unsigned char )buf;
247	register const unsigned char *end = p + len;
248	register unsigned hash = 5381; /* start value */
249	while (p < end)
250	hash = (hash + (hash << 5)) ^ *p++;
251	return hash;
252	}
253
254	/* cdb_init.c: cdb_init, cdb_free and cdb_read routines
255	*
256	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
257	* Public domain.
258	*/
259
260	#include <sys/types.h>
261	#ifdef _WIN32
262	# include <windows.h>
263	#else
264	# include <sys/mman.h>
265	# ifndef MAP_FAILED
266	# define MAP_FAILED ((void*)-1)
267	# endif
268	#endif
269	#include <sys/stat.h>
270
271	static int
272	cdb_init(struct cdb *cdbp, int fd)
273	{
274	struct stat st;
275	unsigned char *mem;
276	unsigned fsize, dend;
277	#ifdef _WIN32
278	HANDLE hFile, hMapping;
279	#endif
280
281	/* get file size */
282	if (fstat(fd, &st) < 0)
283	return -1;
284	/* trivial sanity check: at least toc should be here */
285	if (st.st_size < 2048)
286	return errno = EPROTO, -1;
287	fsize = st.st_size < 0xffffffffu ? st.st_size : 0xffffffffu;
288	/* memory-map file */
289	#ifdef _WIN32
290	hFile = (HANDLE) _get_osfhandle(fd);
291	if (hFile == (HANDLE) -1)
292	return -1;
293	hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
294	if (!hMapping)
295	return -1;
296	mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
297	CloseHandle(hMapping);
298	if (!mem)
299	return -1;
300	#else
301	mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
302	if (mem == MAP_FAILED)
303	return -1;
304	#endif /* _WIN32 */
305
306	cdbp->cdb_fd = fd;
307	cdbp->cdb_fsize = fsize;
308	cdbp->cdb_mem = mem;
309
310	#if 0
311	/* XXX don't know well about madvise syscall -- is it legal
312	to set different options for parts of one mmap() region?
313	There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc...
314	*/
315	#ifdef MADV_RANDOM
316	/* set madvise() parameters. Ignore errors for now if system
317	doesn't support it */
318	madvise(mem, 2048, MADV_WILLNEED);
319	madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM);
320	#endif
321	#endif
322
323	cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
324	cdbp->cdb_kpos = cdbp->cdb_klen = 0;
325	dend = cdb_unpack(mem);
326	if (dend < 2048) dend = 2048;
327	else if (dend >= fsize) dend = fsize;
328	cdbp->cdb_dend = dend;
329
330	return 0;
331	}
332
333	static void
334	cdb_free(struct cdb *cdbp)
335	{
336	if (cdbp->cdb_mem) {
337	#ifdef _WIN32
338	UnmapViewOfFile((void*) cdbp->cdb_mem);
339	#else
340	munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
341	#endif /* _WIN32 */
342	cdbp->cdb_mem = NULL;
343	}
344	cdbp->cdb_fsize = 0;
345	}
346
347	static const void *
348	cdb_get(const struct cdb *cdbp, unsigned len, unsigned pos)
349	{
350	if (pos > cdbp->cdb_fsize \|\| cdbp->cdb_fsize - pos < len) {
351	errno = EPROTO;
352	return NULL;
353	}
354	return cdbp->cdb_mem + pos;
355	}
356
357	static int
358	cdb_read(const struct cdb cdbp, void buf, unsigned len, unsigned pos)
359	{
360	const void *data = cdb_get(cdbp, len, pos);
361	if (!data) return -1;
362	memcpy(buf, data, len);
363	return 0;
364	}
365
366	/* cdb_make_add.c: basic cdb_make_add routine
367	*
368	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
369	* Public domain.
370	*/
371
372	#include <stdlib.h> /* for malloc */
373
374	int internal_function
375	_cdb_make_add(struct cdb_make *cdbmp, unsigned hval,
376	const void *key, unsigned klen,
377	const void *val, unsigned vlen)
378	{
379	unsigned char rlen[8];
380	struct cdb_rl *rl;
381	unsigned i;
382	if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) \|\|
383	vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8))
384	return errno = ENOMEM, -1;
385	i = hval & 255;
386	rl = cdbmp->cdb_rec[i];
387	if (!rl \|\| rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
388	rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
389	if (!rl)
390	return errno = ENOMEM, -1;
391	rl->cnt = 0;
392	rl->next = cdbmp->cdb_rec[i];
393	cdbmp->cdb_rec[i] = rl;
394	}
395	i = rl->cnt++;
396	rl->rec[i].hval = hval;
397	rl->rec[i].rpos = cdbmp->cdb_dpos;
398	++cdbmp->cdb_rcnt;
399	cdb_pack(klen, rlen);
400	cdb_pack(vlen, rlen + 4);
401	if (_cdb_make_write(cdbmp, rlen, 8) < 0 \|\|
402	_cdb_make_write(cdbmp, key, klen) < 0 \|\|
403	_cdb_make_write(cdbmp, val, vlen) < 0)
404	return -1;
405	return 0;
406	}
407
408	static int
409	cdb_make_add(struct cdb_make *cdbmp,
410	const void *key, unsigned klen,
411	const void *val, unsigned vlen) {
412	return _cdb_make_add(cdbmp, cdb_hash(key, klen), key, klen, val, vlen);
413	}
414
415	/* cdb_unpack.c: unpack 32bit integer
416	*
417	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
418	* Public domain.
419	*/
420
421	static inline unsigned
422	cdb_unpack(const unsigned char buf[4])
423	{
424	unsigned n = buf[3];
425	n <<= 8; n \|= buf[2];
426	n <<= 8; n \|= buf[1];
427	n <<= 8; n \|= buf[0];
428	return n;
429	}
430
431	/* cdb_make.c: basic cdb creation routines
432	*
433	* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
434	* Public domain.
435	*/
436
437	#include <unistd.h>
438	#include <stdlib.h>
439	#include <string.h>
440
441	static inline void
442	cdb_pack(unsigned num, unsigned char buf[4])
443	{
444	buf[0] = num & 255; num >>= 8;
445	buf[1] = num & 255; num >>= 8;
446	buf[2] = num & 255;
447	buf[3] = num >> 8;
448	}
449
450	static int
451	cdb_make_start(struct cdb_make *cdbmp, int fd)
452	{
453	memset(cdbmp, 0, sizeof(*cdbmp));
454	cdbmp->cdb_fd = fd;
455	cdbmp->cdb_dpos = 2048;
456	cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
457	return 0;
458	}
459
460	int internal_function
461	_cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len)
462	{
463	while(len) {
464	int l = write(fd, buf, len);
465	if (l > 0) {
466	len -= l;
467	buf += l;
468	}
469	else if (l < 0 && errno != EINTR)
470	return -1;
471	}
472	return 0;
473	}
474
475	int internal_function
476	_cdb_make_flush(struct cdb_make *cdbmp) {
477	unsigned len = cdbmp->cdb_bpos - cdbmp->cdb_buf;
478	if (len) {
479	if (_cdb_make_fullwrite(cdbmp->cdb_fd, cdbmp->cdb_buf, len) < 0)
480	return -1;
481	cdbmp->cdb_bpos = cdbmp->cdb_buf;
482	}
483	return 0;
484	}
485
486	int internal_function
487	_cdb_make_write(struct cdb_make cdbmp, const void ptr_, unsigned len)
488	{
489	const unsigned char ptr = (const unsigned char )ptr_;
490	unsigned l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
491	cdbmp->cdb_dpos += len;
492	if (len > l) {
493	memcpy(cdbmp->cdb_bpos, ptr, l);
494	cdbmp->cdb_bpos += l;
495	if (_cdb_make_flush(cdbmp) < 0)
496	return -1;
497	ptr += l; len -= l;
498	l = len / sizeof(cdbmp->cdb_buf);
499	if (l) {
500	l *= sizeof(cdbmp->cdb_buf);
501	if (_cdb_make_fullwrite(cdbmp->cdb_fd, ptr, l) < 0)
502	return -1;
503	ptr += l; len -= l;
504	}
505	}
506	if (len) {
507	memcpy(cdbmp->cdb_bpos, ptr, len);
508	cdbmp->cdb_bpos += len;
509	}
510	return 0;
511	}
512
513	static int
514	cdb_make_finish_internal(struct cdb_make *cdbmp)
515	{
516	unsigned hcnt[256]; /* hash table counts */
517	unsigned hpos[256]; /* hash table positions */
518	struct cdb_rec *htab;
519	unsigned char *p;
520	struct cdb_rl *rl;
521	unsigned hsize;
522	unsigned t, i;
523
524	if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt)
525	return errno = ENOMEM, -1;
526
527	/* count htab sizes and reorder reclists */
528	hsize = 0;
529	for (t = 0; t < 256; ++t) {
530	struct cdb_rl *rlt = NULL;
531	i = 0;
532	rl = cdbmp->cdb_rec[t];
533	while(rl) {
534	struct cdb_rl *rln = rl->next;
535	rl->next = rlt;
536	rlt = rl;
537	i += rl->cnt;
538	rl = rln;
539	}
540	cdbmp->cdb_rec[t] = rlt;
541	if (hsize < (hcnt[t] = i << 1))
542	hsize = hcnt[t];
543	}
544
545	/* allocate memory to hold max htable */
546	htab = (struct cdb_rec)malloc((hsize + 2) sizeof(struct cdb_rec));
547	if (!htab)
548	return errno = ENOENT, -1;
549	p = (unsigned char *)htab;
550	htab += 2;
551
552	/* build hash tables */
553	for (t = 0; t < 256; ++t) {
554	unsigned len, hi;
555	hpos[t] = cdbmp->cdb_dpos;
556	if ((len = hcnt[t]) == 0)
557	continue;
558	for (i = 0; i < len; ++i)
559	htab[i].hval = htab[i].rpos = 0;
560	for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
561	for (i = 0; i < rl->cnt; ++i) {
562	hi = (rl->rec[i].hval >> 8) % len;
563	while(htab[hi].rpos)
564	if (++hi == len)
565	hi = 0;
566	htab[hi] = rl->rec[i];
567	}
568	for (i = 0; i < len; ++i) {
569	cdb_pack(htab[i].hval, p + (i << 3));
570	cdb_pack(htab[i].rpos, p + (i << 3) + 4);
571	}
572	if (_cdb_make_write(cdbmp, p, len << 3) < 0) {
573	free(p);
574	return -1;
575	}
576	}
577	free(p);
578	if (_cdb_make_flush(cdbmp) < 0)
579	return -1;
580	p = cdbmp->cdb_buf;
581	for (t = 0; t < 256; ++t) {
582	cdb_pack(hpos[t], p + (t << 3));
583	cdb_pack(hcnt[t], p + (t << 3) + 4);
584	}
585	if (lseek(cdbmp->cdb_fd, 0, 0) != 0 \|\|
586	_cdb_make_fullwrite(cdbmp->cdb_fd, p, 2048) != 0)
587	return -1;
588
589	return 0;
590	}
591
592	static void
593	cdb_make_free(struct cdb_make *cdbmp)
594	{
595	unsigned t;
596	for(t = 0; t < 256; ++t) {
597	struct cdb_rl *rl = cdbmp->cdb_rec[t];
598	while(rl) {
599	struct cdb_rl *tm = rl;
600	rl = rl->next;
601	free(tm);
602	}
603	}
604	}
605
606	static int
607	cdb_make_finish(struct cdb_make *cdbmp)
608	{
609	int r = cdb_make_finish_internal(cdbmp);
610	cdb_make_free(cdbmp);
611	return r;
612	}
613