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 unsigned char *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 unsigned char *ptr, unsigned len)
{
  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.1
Committed:	Mon Mar 14 22:48:05 2022 UTC (2 years, 2 months ago) by root
Content type:	text/plain
Branch:	MAIN
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.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 unsigned char *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			/* cdb_find.c: cdb_find routine
163			*
164			* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
165			* Public domain.
166			*/
167
168			static int
169			cdb_find(struct cdb cdbp, const void key, unsigned klen)
170			{
171			const unsigned char htp; / hash table pointer */
172			const unsigned char htab; / hash table */
173			const unsigned char htend; / end of hash table */
174			unsigned httodo; /* ht bytes left to look */
175			unsigned pos, n;
176
177			unsigned hval;
178
179			if (klen >= cdbp->cdb_dend) /* if key size is too large */
180			return 0;
181
182			hval = cdb_hash(key, klen);
183
184			/* find (pos,n) hash table to use */
185			/* first 2048 bytes (toc) are always available */
186			/* (hval % 256) * 8 */
187			htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
188			n = cdb_unpack(htp + 4); /* table size */
189			if (!n) /* empty table */
190			return 0; /* not found */
191			httodo = n << 3; /* bytes of htab to lookup */
192			pos = cdb_unpack(htp); /* htab position */
193			if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
194			\|\| pos < cdbp->cdb_dend /* is htab inside data section ? */
195			\|\| pos > cdbp->cdb_fsize /* htab start within file ? */
196			\|\| httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
197			return errno = EPROTO, -1;
198
199			htab = cdbp->cdb_mem + pos; /* htab pointer */
200			htend = htab + httodo; /* after end of htab */
201			/* htab starting position: rest of hval modulo htsize, 8bytes per elt */
202			htp = htab + (((hval >> 8) % n) << 3);
203
204			for(;;) {
205			pos = cdb_unpack(htp + 4); /* record position */
206			if (!pos)
207			return 0;
208			if (cdb_unpack(htp) == hval) {
209			if (pos > cdbp->cdb_dend - 8) /* key+val lengths */
210			return errno = EPROTO, -1;
211			if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
212			if (cdbp->cdb_dend - klen < pos + 8)
213			return errno = EPROTO, -1;
214			if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
215			n = cdb_unpack(cdbp->cdb_mem + pos + 4);
216			pos += 8;
217			if (cdbp->cdb_dend < n \|\| cdbp->cdb_dend - n < pos + klen)
218			return errno = EPROTO, -1;
219			cdbp->cdb_kpos = pos;
220			cdbp->cdb_klen = klen;
221			cdbp->cdb_vpos = pos + klen;
222			cdbp->cdb_vlen = n;
223			return 1;
224			}
225			}
226			}
227			httodo -= 8;
228			if (!httodo)
229			return 0;
230			if ((htp += 8) >= htend)
231			htp = htab;
232			}
233
234			}
235
236			/* cdb_hash.c: cdb hashing routine
237			*
238			* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
239			* Public domain.
240			*/
241
242			static unsigned
243			cdb_hash(const void *buf, unsigned len)
244			{
245			register const unsigned char p = (const unsigned char )buf;
246			register const unsigned char *end = p + len;
247			register unsigned hash = 5381; /* start value */
248			while (p < end)
249			hash = (hash + (hash << 5)) ^ *p++;
250			return hash;
251			}
252
253			/* cdb_init.c: cdb_init, cdb_free and cdb_read routines
254			*
255			* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
256			* Public domain.
257			*/
258
259			#include <sys/types.h>
260			#ifdef _WIN32
261			# include <windows.h>
262			#else
263			# include <sys/mman.h>
264			# ifndef MAP_FAILED
265			# define MAP_FAILED ((void*)-1)
266			# endif
267			#endif
268			#include <sys/stat.h>
269
270			static int
271			cdb_init(struct cdb *cdbp, int fd)
272			{
273			struct stat st;
274			unsigned char *mem;
275			unsigned fsize, dend;
276			#ifdef _WIN32
277			HANDLE hFile, hMapping;
278			#endif
279
280			/* get file size */
281			if (fstat(fd, &st) < 0)
282			return -1;
283			/* trivial sanity check: at least toc should be here */
284			if (st.st_size < 2048)
285			return errno = EPROTO, -1;
286			fsize = st.st_size < 0xffffffffu ? st.st_size : 0xffffffffu;
287			/* memory-map file */
288			#ifdef _WIN32
289			hFile = (HANDLE) _get_osfhandle(fd);
290			if (hFile == (HANDLE) -1)
291			return -1;
292			hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
293			if (!hMapping)
294			return -1;
295			mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
296			CloseHandle(hMapping);
297			if (!mem)
298			return -1;
299			#else
300			mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
301			if (mem == MAP_FAILED)
302			return -1;
303			#endif /* _WIN32 */
304
305			cdbp->cdb_fd = fd;
306			cdbp->cdb_fsize = fsize;
307			cdbp->cdb_mem = mem;
308
309			#if 0
310			/* XXX don't know well about madvise syscall -- is it legal
311			to set different options for parts of one mmap() region?
312			There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc...
313			*/
314			#ifdef MADV_RANDOM
315			/* set madvise() parameters. Ignore errors for now if system
316			doesn't support it */
317			madvise(mem, 2048, MADV_WILLNEED);
318			madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM);
319			#endif
320			#endif
321
322			cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
323			cdbp->cdb_kpos = cdbp->cdb_klen = 0;
324			dend = cdb_unpack(mem);
325			if (dend < 2048) dend = 2048;
326			else if (dend >= fsize) dend = fsize;
327			cdbp->cdb_dend = dend;
328
329			return 0;
330			}
331
332			static void
333			cdb_free(struct cdb *cdbp)
334			{
335			if (cdbp->cdb_mem) {
336			#ifdef _WIN32
337			UnmapViewOfFile((void*) cdbp->cdb_mem);
338			#else
339			munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
340			#endif /* _WIN32 */
341			cdbp->cdb_mem = NULL;
342			}
343			cdbp->cdb_fsize = 0;
344			}
345
346			static const void *
347			cdb_get(const struct cdb *cdbp, unsigned len, unsigned pos)
348			{
349			if (pos > cdbp->cdb_fsize \|\| cdbp->cdb_fsize - pos < len) {
350			errno = EPROTO;
351			return NULL;
352			}
353			return cdbp->cdb_mem + pos;
354			}
355
356			static int
357			cdb_read(const struct cdb cdbp, void buf, unsigned len, unsigned pos)
358			{
359			const void *data = cdb_get(cdbp, len, pos);
360			if (!data) return -1;
361			memcpy(buf, data, len);
362			return 0;
363			}
364
365			/* cdb_make_add.c: basic cdb_make_add routine
366			*
367			* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
368			* Public domain.
369			*/
370
371			#include <stdlib.h> /* for malloc */
372
373			int internal_function
374			_cdb_make_add(struct cdb_make *cdbmp, unsigned hval,
375			const void *key, unsigned klen,
376			const void *val, unsigned vlen)
377			{
378			unsigned char rlen[8];
379			struct cdb_rl *rl;
380			unsigned i;
381			if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) \|\|
382			vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8))
383			return errno = ENOMEM, -1;
384			i = hval & 255;
385			rl = cdbmp->cdb_rec[i];
386			if (!rl \|\| rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
387			rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
388			if (!rl)
389			return errno = ENOMEM, -1;
390			rl->cnt = 0;
391			rl->next = cdbmp->cdb_rec[i];
392			cdbmp->cdb_rec[i] = rl;
393			}
394			i = rl->cnt++;
395			rl->rec[i].hval = hval;
396			rl->rec[i].rpos = cdbmp->cdb_dpos;
397			++cdbmp->cdb_rcnt;
398			cdb_pack(klen, rlen);
399			cdb_pack(vlen, rlen + 4);
400			if (_cdb_make_write(cdbmp, rlen, 8) < 0 \|\|
401			_cdb_make_write(cdbmp, key, klen) < 0 \|\|
402			_cdb_make_write(cdbmp, val, vlen) < 0)
403			return -1;
404			return 0;
405			}
406
407			static int
408			cdb_make_add(struct cdb_make *cdbmp,
409			const void *key, unsigned klen,
410			const void *val, unsigned vlen) {
411			return _cdb_make_add(cdbmp, cdb_hash(key, klen), key, klen, val, vlen);
412			}
413
414			/* cdb_unpack.c: unpack 32bit integer
415			*
416			* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
417			* Public domain.
418			*/
419
420			static inline unsigned
421			cdb_unpack(const unsigned char buf[4])
422			{
423			unsigned n = buf[3];
424			n <<= 8; n \|= buf[2];
425			n <<= 8; n \|= buf[1];
426			n <<= 8; n \|= buf[0];
427			return n;
428			}
429
430			/* cdb_make.c: basic cdb creation routines
431			*
432			* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
433			* Public domain.
434			*/
435
436			#include <unistd.h>
437			#include <stdlib.h>
438			#include <string.h>
439
440			static inline void
441			cdb_pack(unsigned num, unsigned char buf[4])
442			{
443			buf[0] = num & 255; num >>= 8;
444			buf[1] = num & 255; num >>= 8;
445			buf[2] = num & 255;
446			buf[3] = num >> 8;
447			}
448
449			static int
450			cdb_make_start(struct cdb_make *cdbmp, int fd)
451			{
452			memset(cdbmp, 0, sizeof(*cdbmp));
453			cdbmp->cdb_fd = fd;
454			cdbmp->cdb_dpos = 2048;
455			cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
456			return 0;
457			}
458
459			int internal_function
460			_cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len)
461			{
462			while(len) {
463			int l = write(fd, buf, len);
464			if (l > 0) {
465			len -= l;
466			buf += l;
467			}
468			else if (l < 0 && errno != EINTR)
469			return -1;
470			}
471			return 0;
472			}
473
474			int internal_function
475			_cdb_make_flush(struct cdb_make *cdbmp) {
476			unsigned len = cdbmp->cdb_bpos - cdbmp->cdb_buf;
477			if (len) {
478			if (_cdb_make_fullwrite(cdbmp->cdb_fd, cdbmp->cdb_buf, len) < 0)
479			return -1;
480			cdbmp->cdb_bpos = cdbmp->cdb_buf;
481			}
482			return 0;
483			}
484
485			int internal_function
486			_cdb_make_write(struct cdb_make cdbmp, const unsigned char ptr, unsigned len)
487			{
488			unsigned l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
489			cdbmp->cdb_dpos += len;
490			if (len > l) {
491			memcpy(cdbmp->cdb_bpos, ptr, l);
492			cdbmp->cdb_bpos += l;
493			if (_cdb_make_flush(cdbmp) < 0)
494			return -1;
495			ptr += l; len -= l;
496			l = len / sizeof(cdbmp->cdb_buf);
497			if (l) {
498			l *= sizeof(cdbmp->cdb_buf);
499			if (_cdb_make_fullwrite(cdbmp->cdb_fd, ptr, l) < 0)
500			return -1;
501			ptr += l; len -= l;
502			}
503			}
504			if (len) {
505			memcpy(cdbmp->cdb_bpos, ptr, len);
506			cdbmp->cdb_bpos += len;
507			}
508			return 0;
509			}
510
511			static int
512			cdb_make_finish_internal(struct cdb_make *cdbmp)
513			{
514			unsigned hcnt[256]; /* hash table counts */
515			unsigned hpos[256]; /* hash table positions */
516			struct cdb_rec *htab;
517			unsigned char *p;
518			struct cdb_rl *rl;
519			unsigned hsize;
520			unsigned t, i;
521
522			if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt)
523			return errno = ENOMEM, -1;
524
525			/* count htab sizes and reorder reclists */
526			hsize = 0;
527			for (t = 0; t < 256; ++t) {
528			struct cdb_rl *rlt = NULL;
529			i = 0;
530			rl = cdbmp->cdb_rec[t];
531			while(rl) {
532			struct cdb_rl *rln = rl->next;
533			rl->next = rlt;
534			rlt = rl;
535			i += rl->cnt;
536			rl = rln;
537			}
538			cdbmp->cdb_rec[t] = rlt;
539			if (hsize < (hcnt[t] = i << 1))
540			hsize = hcnt[t];
541			}
542
543			/* allocate memory to hold max htable */
544			htab = (struct cdb_rec)malloc((hsize + 2) sizeof(struct cdb_rec));
545			if (!htab)
546			return errno = ENOENT, -1;
547			p = (unsigned char *)htab;
548			htab += 2;
549
550			/* build hash tables */
551			for (t = 0; t < 256; ++t) {
552			unsigned len, hi;
553			hpos[t] = cdbmp->cdb_dpos;
554			if ((len = hcnt[t]) == 0)
555			continue;
556			for (i = 0; i < len; ++i)
557			htab[i].hval = htab[i].rpos = 0;
558			for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
559			for (i = 0; i < rl->cnt; ++i) {
560			hi = (rl->rec[i].hval >> 8) % len;
561			while(htab[hi].rpos)
562			if (++hi == len)
563			hi = 0;
564			htab[hi] = rl->rec[i];
565			}
566			for (i = 0; i < len; ++i) {
567			cdb_pack(htab[i].hval, p + (i << 3));
568			cdb_pack(htab[i].rpos, p + (i << 3) + 4);
569			}
570			if (_cdb_make_write(cdbmp, p, len << 3) < 0) {
571			free(p);
572			return -1;
573			}
574			}
575			free(p);
576			if (_cdb_make_flush(cdbmp) < 0)
577			return -1;
578			p = cdbmp->cdb_buf;
579			for (t = 0; t < 256; ++t) {
580			cdb_pack(hpos[t], p + (t << 3));
581			cdb_pack(hcnt[t], p + (t << 3) + 4);
582			}
583			if (lseek(cdbmp->cdb_fd, 0, 0) != 0 \|\|
584			_cdb_make_fullwrite(cdbmp->cdb_fd, p, 2048) != 0)
585			return -1;
586
587			return 0;
588			}
589
590			static void
591			cdb_make_free(struct cdb_make *cdbmp)
592			{
593			unsigned t;
594			for(t = 0; t < 256; ++t) {
595			struct cdb_rl *rl = cdbmp->cdb_rec[t];
596			while(rl) {
597			struct cdb_rl *tm = rl;
598			rl = rl->next;
599			free(tm);
600			}
601			}
602			}
603
604			static int
605			cdb_make_finish(struct cdb_make *cdbmp)
606			{
607			int r = cdb_make_finish_internal(cdbmp);
608			cdb_make_free(cdbmp);
609			return r;
610			}
611