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.2
Committed:	Tue Mar 15 07:33:40 2022 UTC (2 years, 2 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-0_9
Changes since 1.1:	+1 -0 lines
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	root	1.2
163	root	1.1	/* 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 unsigned char ptr, unsigned len)
488			{
489			unsigned l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
490			cdbmp->cdb_dpos += len;
491			if (len > l) {
492			memcpy(cdbmp->cdb_bpos, ptr, l);
493			cdbmp->cdb_bpos += l;
494			if (_cdb_make_flush(cdbmp) < 0)
495			return -1;
496			ptr += l; len -= l;
497			l = len / sizeof(cdbmp->cdb_buf);
498			if (l) {
499			l *= sizeof(cdbmp->cdb_buf);
500			if (_cdb_make_fullwrite(cdbmp->cdb_fd, ptr, l) < 0)
501			return -1;
502			ptr += l; len -= l;
503			}
504			}
505			if (len) {
506			memcpy(cdbmp->cdb_bpos, ptr, len);
507			cdbmp->cdb_bpos += len;
508			}
509			return 0;
510			}
511
512			static int
513			cdb_make_finish_internal(struct cdb_make *cdbmp)
514			{
515			unsigned hcnt[256]; /* hash table counts */
516			unsigned hpos[256]; /* hash table positions */
517			struct cdb_rec *htab;
518			unsigned char *p;
519			struct cdb_rl *rl;
520			unsigned hsize;
521			unsigned t, i;
522
523			if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt)
524			return errno = ENOMEM, -1;
525
526			/* count htab sizes and reorder reclists */
527			hsize = 0;
528			for (t = 0; t < 256; ++t) {
529			struct cdb_rl *rlt = NULL;
530			i = 0;
531			rl = cdbmp->cdb_rec[t];
532			while(rl) {
533			struct cdb_rl *rln = rl->next;
534			rl->next = rlt;
535			rlt = rl;
536			i += rl->cnt;
537			rl = rln;
538			}
539			cdbmp->cdb_rec[t] = rlt;
540			if (hsize < (hcnt[t] = i << 1))
541			hsize = hcnt[t];
542			}
543
544			/* allocate memory to hold max htable */
545			htab = (struct cdb_rec)malloc((hsize + 2) sizeof(struct cdb_rec));
546			if (!htab)
547			return errno = ENOENT, -1;
548			p = (unsigned char *)htab;
549			htab += 2;
550
551			/* build hash tables */
552			for (t = 0; t < 256; ++t) {
553			unsigned len, hi;
554			hpos[t] = cdbmp->cdb_dpos;
555			if ((len = hcnt[t]) == 0)
556			continue;
557			for (i = 0; i < len; ++i)
558			htab[i].hval = htab[i].rpos = 0;
559			for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
560			for (i = 0; i < rl->cnt; ++i) {
561			hi = (rl->rec[i].hval >> 8) % len;
562			while(htab[hi].rpos)
563			if (++hi == len)
564			hi = 0;
565			htab[hi] = rl->rec[i];
566			}
567			for (i = 0; i < len; ++i) {
568			cdb_pack(htab[i].hval, p + (i << 3));
569			cdb_pack(htab[i].rpos, p + (i << 3) + 4);
570			}
571			if (_cdb_make_write(cdbmp, p, len << 3) < 0) {
572			free(p);
573			return -1;
574			}
575			}
576			free(p);
577			if (_cdb_make_flush(cdbmp) < 0)
578			return -1;
579			p = cdbmp->cdb_buf;
580			for (t = 0; t < 256; ++t) {
581			cdb_pack(hpos[t], p + (t << 3));
582			cdb_pack(hcnt[t], p + (t << 3) + 4);
583			}
584			if (lseek(cdbmp->cdb_fd, 0, 0) != 0 \|\|
585			_cdb_make_fullwrite(cdbmp->cdb_fd, p, 2048) != 0)
586			return -1;
587
588			return 0;
589			}
590
591			static void
592			cdb_make_free(struct cdb_make *cdbmp)
593			{
594			unsigned t;
595			for(t = 0; t < 256; ++t) {
596			struct cdb_rl *rl = cdbmp->cdb_rec[t];
597			while(rl) {
598			struct cdb_rl *tm = rl;
599			rl = rl->next;
600			free(tm);
601			}
602			}
603			}
604
605			static int
606			cdb_make_finish(struct cdb_make *cdbmp)
607			{
608			int r = cdb_make_finish_internal(cdbmp);
609			cdb_make_free(cdbmp);
610			return r;
611			}
612