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