tinycdb.d

   1 /* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
   2  *
   3  * This program is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, version 3 of the License ONLY.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  14  *
  15  * D translation by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
  16  */
  17 // CDB key/value database reader
  18 module iv.tinycdb /*is aliced*/;
  19 import iv.alice;
  20
  21
  22 struct CDB {
  23 public:
  24   enum Version { Major = 0, Minor = 78 }
  25
  26 private:
  27   int mFD = -1; /* file descriptor */
  28   bool mCloseFD; /* true: close fd on close() */
  29   uint mFSize; /* datafile size */
  30   uint mDataEnd; /* end of data ptr */
  31   const(ubyte)* mDataPtr; /* mmap'ed file memory */
  32
  33 public:
  34 nothrow:
  35   @disable this (this); // no copying
  36
  37   this (string fname) { open(fname); }
  38
  39   bool open (string fname) {
  40     import std.string : toStringz;
  41     import core.sys.posix.fcntl : xopen = open, O_RDONLY;
  42     close();
  43     int fd = xopen(fname.toStringz, O_RDONLY);
  44     if (fd >= 0) {
  45       mCloseFD = true;
  46       if (open(fd)) return true;
  47       import core.sys.posix.unistd : xclose = close;
  48       xclose(fd);
  49       mFD = -1;
  50       mCloseFD = false;
  51       mFSize = 0;
  52       mDataEnd = 0;
  53       mDataPtr = null;
  54     }
  55     return false;
  56   }
  57
  58 @nogc:
  59   ~this () { close(); }
  60
  61   this (int fd) @nogc { open(fd); }
  62
  63   @property bool opened () const pure @safe { return (mFD >= 0 && mDataPtr !is null); }
  64
  65   // was int, -1 == err
  66   bool open (int fd) {
  67     import core.sys.posix.sys.mman : mmap, PROT_READ, MAP_SHARED, MAP_FAILED;
  68     import core.sys.posix.sys.stat : fstat, stat_t;
  69     stat_t st;
  70     ubyte *mem;
  71     uint fsize, dend;
  72     close();
  73     /* get file size */
  74     if (fd < 0 || fstat(fd, &st) < 0) return false;
  75     /* trivial sanity check: at least toc should be here */
  76     if (st.st_size < 2048) return false;
  77     fsize = (st.st_size < 0xffffffffu ? cast(uint)st.st_size : 0xffffffffu);
  78     /* memory-map file */
  79     mem = cast(ubyte*)mmap(null, fsize, PROT_READ, MAP_SHARED, fd, 0);
  80     if (mem == MAP_FAILED) return false;
  81     mFD = fd;
  82     mFSize = fsize;
  83     mDataPtr = mem;
  84     /* set madvise() parameters. Ignore errors for now if system doesn't support it */
  85     {
  86       import core.sys.posix.sys.mman : posix_madvise, POSIX_MADV_WILLNEED, POSIX_MADV_RANDOM;
  87       posix_madvise(mem, 2048, POSIX_MADV_WILLNEED);
  88       posix_madvise(mem+2048, mFSize-2048, POSIX_MADV_RANDOM);
  89     }
  90     dend = unpack(mem);
  91     if (dend < 2048) dend = 2048; else if (dend >= fsize) dend = fsize;
  92     mDataEnd = dend;
  93     return true;
  94   }
  95
  96   bool close () {
  97     if (mDataPtr) {
  98       import core.sys.posix.sys.mman : munmap;
  99       munmap(cast(void*)mDataPtr, mFSize);
 100       mDataPtr = null;
 101       bool wasError = false;
 102       if (mCloseFD) {
 103         import core.sys.posix.unistd : xclose = close;
 104         wasError = (xclose(mFD) != 0);
 105       }
 106       mFD = -1;
 107       mCloseFD = false;
 108       mFSize = 0;
 109       mDataEnd = 0;
 110       mDataPtr = null;
 111       return wasError;
 112     } else {
 113       return true;
 114     }
 115   }
 116
 117   const(char)[] opIndex (const(char)[] key) const { return find(key); }
 118
 119   // null: not found (or some error occured)
 120   const(T)[] find(T=char) (const(void)[] key) const
 121   if (is(T == char) || is(T == byte) || is(T == ubyte) || is(T == void))
 122   {
 123     uint httodo; /* ht bytes left to look */
 124     uint pos, n;
 125     if (key.length < 1 || key.length >= mDataEnd) return null; /* if key size is too small or too large */
 126     immutable klen = cast(uint)key.length;
 127     immutable hval = hash(key);
 128     /* find (pos,n) hash table to use */
 129     /* first 2048 bytes (toc) are always available */
 130     /* (hval%256)*8 */
 131     auto htp = cast(const(ubyte)*)mDataPtr+((hval<<3)&2047); /* index in toc (256x8) */
 132     n = unpack(htp+4); /* table size */
 133     if (!n) return null; /* empty table: not found */
 134     httodo = n<<3; /* bytes of htab to lookup */
 135     pos = unpack(htp); /* htab position */
 136     if (n > (mFSize>>3) || /* overflow of httodo ? */
 137         pos < mDataEnd || /* is htab inside data section ? */
 138         pos > mFSize || /* htab start within file ? */
 139         httodo > mFSize-pos) /* entrie htab within file ? */
 140       return null; // error
 141     auto htab = mDataPtr+pos; /* hash table */
 142     auto htend = htab+httodo; /* after end of hash table */
 143     /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
 144     htp = htab+(((hval>>8)%n)<<3); /* hash table pointer */
 145     for (;;) {
 146       pos = unpack(htp+4); /* record position */
 147       if (!pos) return null;
 148       if (unpack(htp) == hval) {
 149         if (pos > mDataEnd-8) return null; /* key+val lengths: error */
 150         if (unpack(mDataPtr+pos) == klen) {
 151           import core.stdc.string : memcmp;
 152           if (mDataEnd-klen < pos+8) return null; // error
 153           if (memcmp(key.ptr, mDataPtr+pos+8, klen) == 0) {
 154             n = unpack(mDataPtr+pos+4);
 155             pos += 8;
 156             if (mDataEnd < n || mDataEnd-n < pos+klen) return /*errno = EPROTO, -1*/null; // error
 157             // key: [pos..pos+klen]
 158             // val: [pos+klen..pos+klen+n]
 159             return cast(const(T)[])mDataPtr[pos+klen..pos+klen+n];
 160           }
 161         }
 162       }
 163       httodo -= 8;
 164       if (!httodo) return null;
 165       if ((htp += 8) >= htend) htp = htab;
 166     }
 167   }
 168
 169   //WARNING! returned range should not outlive this object!
 170   auto findFirst(T=char) (const(void)[] key) const nothrow @nogc
 171   if (is(T == char) || is(T == byte) || is(T == ubyte) || is(T == void))
 172   {
 173     static struct Iter {
 174     private:
 175       const(CDB)* cdbp;
 176       uint hval;
 177       const(ubyte)* htp, htab, htend;
 178       uint httodo;
 179       const(void)[] key;
 180       uint vpos, vlen;
 181
 182     public:
 183     nothrow:
 184     @nogc:
 185       @disable this ();
 186
 187       @property bool empty () const @safe pure { return (cdbp is null || !cdbp.opened); }
 188       @property const(T)[] front () const @trusted pure nothrow @nogc {
 189         return (empty ? null : cast(const(T)[])cdbp.mDataPtr[vpos..vpos+vlen]);
 190       }
 191       void close () { cdbp = null; key = null; htp = htab = htend = null; }
 192       void popFront () {
 193         if (empty) return;
 194         auto cdb = cdbp;
 195         uint pos, n;
 196         immutable uint klen = cast(uint)key.length;
 197         while (httodo) {
 198           pos = unpack(htp+4);
 199           if (!pos) { close(); return; }
 200           n = (unpack(htp) == hval);
 201           if ((htp += 8) >= htend) htp = htab;
 202           httodo -= 8;
 203           if (n) {
 204             if (pos > cdb.mFSize-8) { close(); return; }
 205             if (unpack(cdb.mDataPtr+pos) == klen) {
 206               import core.stdc.string : memcmp;
 207               if (cdb.mFSize-klen < pos+8) { close(); return; }
 208               if (memcmp(key.ptr, cdb.mDataPtr+pos+8, klen) == 0) {
 209                 n = unpack(cdb.mDataPtr+pos+4);
 210                 pos += 8;
 211                 if (cdb.mFSize < n || cdb.mFSize-n < pos+klen) { close(); return; }
 212                 // key: [pos..pos+klen]
 213                 // val: [pos+klen..pos+klen+n]
 214                 vpos = pos+klen;
 215                 vlen = n;
 216                 return;
 217               }
 218             }
 219           }
 220         }
 221         close();
 222       }
 223     }
 224
 225     if (key.length < 1 || key.length >= mDataEnd) return Iter.init; /* if key size is too large */
 226     immutable klen = cast(uint)key.length;
 227
 228     auto it = Iter.init;
 229     it.cdbp = &this;
 230     it.key = key;
 231     it.hval = hash(key);
 232
 233     it.htp = mDataPtr+((it.hval<<3)&2047);
 234     uint n = unpack(it.htp+4);
 235     it.httodo = n<<3;
 236     if (!n) return Iter.init;
 237     uint pos = unpack(it.htp);
 238     if (n > (mFSize >> 3) ||
 239         pos < mDataEnd ||
 240         pos > mFSize ||
 241         it.httodo > mFSize-pos)
 242       return Iter.init;
 243
 244     it.htab = mDataPtr+pos;
 245     it.htend = it.htab+it.httodo;
 246     it.htp = it.htab+(((it.hval>>8)%n)<<3);
 247
 248     it.popFront(); // prepare first item
 249     return it;
 250   }
 251
 252 static:
 253   uint hash() (const(void)[] buf) {
 254     auto p = cast(const(ubyte)*)buf.ptr;
 255     uint hash = 5381; /* start value */
 256     foreach (immutable nothing; 0..buf.length) hash = (hash+(hash<<5))^*p++;
 257     return hash;
 258   }
 259
 260 private:
 261   uint unpack() (const(ubyte)* buf) {
 262     //assert(buf !is null);
 263     uint n = buf[3];
 264     n <<= 8; n |= buf[2];
 265     n <<= 8; n |= buf[1];
 266     n <<= 8; n |= buf[0];
 267     return n;
 268   }
 269 }