tinycdbmk.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 creator
  19 module iv.tinycdbmk /*is aliced*/;
  20
  21 import iv.alice;
  22
  23
  24 struct CDBMaker {
  25 private static import iv.tinycdb;
  26 public:
  27   alias hash = iv.tinycdb.CDB.hash;
  28
  29 private:
  30   align(1) static struct Rec {
  31   align(1):
  32     uint hval;
  33     uint rpos;
  34   }
  35
  36   static struct RecList {
  37     RecList *next;
  38     uint count;
  39     Rec[254] rec;
  40   }
  41
  42   int mFD = -1; /* file descriptor */
  43   bool mCloseFD;
  44   uint mDataPos; /* data position so far */
  45   uint mRCount; /* record count so far */
  46   ubyte[4096] mBuf = void; /* write buffer */
  47   ubyte* mBufPos; /* current buf position */
  48   RecList*[256] mTables; /* list of arrays of record infos */
  49   bool mWasError;
  50
  51 public:
  52   enum {
  53     PUT_ADD = 0,      /* add unconditionnaly, like cdb_make_add() */
  54     PUT_REPLACE,      /* replace: do not place to index OLD record */
  55     PUT_INSERT,       /* add only if not already exists */
  56     PUT_WARN,         /* add unconditionally but ret. 1 if exists */
  57     PUT_REPLACE0,     /* if a record exists, fill old one with zeros */
  58     //
  59     FIND = PUT_ADD,
  60     FIND_REMOVE = PUT_REPLACE,
  61     FIND_FILL0 = PUT_REPLACE0,
  62   }
  63
  64 public:
  65 nothrow:
  66   @disable this (this); // no copying
  67
  68   this (string fname) { create(fname); }
  69
  70   bool create (string fname) {
  71     import std.string : toStringz;
  72     import core.sys.posix.fcntl : xopen = open, O_CREAT, O_RDWR, O_TRUNC;
  73     close();
  74     int fd = xopen(fname.toStringz, O_RDWR|O_CREAT|O_TRUNC, 384);
  75     if (fd >= 0) {
  76       mCloseFD = true;
  77       create(fd);
  78       return true;
  79     }
  80     return false;
  81   }
  82
  83 @nogc:
  84   ~this () { close(); }
  85
  86   this (int fd) @nogc { create(fd); }
  87
  88   @property bool opened () const pure @safe { return (mFD >= 0); }
  89   @property bool valid () const pure @safe { return (mFD >= 0 && !mWasError); }
  90
  91   //TODO: seek to start and truncate
  92   void create (int fd) {
  93     close();
  94     mFD = fd;
  95     mDataPos = 2048;
  96     mBufPos = mBuf.ptr+2048;
  97     mBuf[] = 0;
  98     if (!seek(0)) mWasError = true;
  99   }
 100
 101   bool close () {
 102     bool res = true;
 103     if (mFD >= 0) {
 104       res = finish();
 105       if (mCloseFD) {
 106         import core.sys.posix.unistd : xclose = close;
 107         xclose(mFD);
 108       }
 109       foreach (immutable t; 0..256) {
 110         auto rl = mTables[t];
 111         while (rl !is null) {
 112           import core.stdc.stdlib : free;
 113           auto tm = rl;
 114           rl = rl.next;
 115           free(tm);
 116         }
 117       }
 118       res = !mWasError;
 119       mFD = -1;
 120       mCloseFD = false;
 121       mDataPos = 0;
 122       mRCount = 0;
 123       mBufPos = null;
 124       mTables[] = null;
 125       mWasError = false;
 126     }
 127     return res;
 128   }
 129
 130   bool find (const(void)[] key, int mode, bool *err=null) {
 131     if (err !is null) *err = false;
 132     auto res = findRecord(key, hash(key), mode);
 133     if (err !is null && res == FindRes.ERROR) *err = true;
 134     return (res == FindRes.FOUND);
 135   }
 136   bool exists (const(void)[] key) { return (findRecord(key, hash(key), FIND) == FindRes.FOUND); }
 137
 138   bool add (const(void)[] key, const(void)[] val) { return addRecord(hash(key), key, val); }
 139
 140   // true: record was replaced
 141   // false: new record or error
 142   bool put (const(void)[] key, const(void)[] val, int mode=PUT_ADD, bool *err=null) {
 143     if (err !is null) *err = false;
 144     uint hval = hash(key);
 145     FindRes r;
 146     switch (mode) {
 147       case PUT_REPLACE:
 148       case PUT_INSERT:
 149       case PUT_WARN:
 150       case PUT_REPLACE0:
 151         r = findRecord(key, hval, mode);
 152         if (r == FindRes.ERROR) {
 153           if (err !is null) *err = true;
 154           return false;
 155         }
 156         if (r == FindRes.FOUND && mode == PUT_INSERT) return /*errno = EEXIST,*/true;
 157         break;
 158       case PUT_ADD:
 159         r = FindRes.NOT_FOUND;
 160         break;
 161       default:
 162         if (err !is null) *err = true;
 163         return /*errno = EINVAL,*/false;
 164     }
 165     if (!addRecord(hval, key, val)) {
 166       if (err !is null) *err = true;
 167       return false;
 168     }
 169     return (r == FindRes.FOUND);
 170   }
 171
 172 private:
 173   private bool seek (uint pos) {
 174     import core.sys.posix.unistd : lseek;
 175     import core.stdc.stdio : SEEK_SET;
 176     return (lseek(mFD, pos, SEEK_SET) >= 0);
 177   }
 178
 179   private bool fullRead (ubyte* buf, uint len) {
 180     while (len) {
 181       import core.stdc.errno;
 182       import core.sys.posix.unistd : read;
 183       auto l = read(mFD, cast(void*)buf, len);
 184       if (l > 0) {
 185         len -= l;
 186         buf += l;
 187       } else if (l == 0 || (l < 0 && errno != EINTR)) {
 188         return false;
 189       }
 190     }
 191     return true;
 192   }
 193
 194   private int read (ubyte* buf, uint len) {
 195     immutable flen = len;
 196     while (len) {
 197       import core.stdc.errno;
 198       static import core.sys.posix.unistd;
 199       auto l = core.sys.posix.unistd.read(mFD, cast(void*)buf, len);
 200       if (l > 0) {
 201         len -= l;
 202         buf += l;
 203       } else if (l < 0 && errno != EINTR) {
 204         return -1;
 205       } else if (l == 0) {
 206         break;
 207       }
 208     }
 209     return cast(int)(flen-len);
 210   }
 211
 212   private bool fullWrite (const(void)* bufp, uint len) {
 213     auto buf = cast(const(ubyte)*)bufp;
 214     while (len) {
 215       import core.stdc.errno;
 216       import core.sys.posix.unistd : write;
 217       auto l = write(mFD, cast(const void*)buf, len);
 218       if (l > 0) {
 219         len -= l;
 220         buf += l;
 221       } else if (l == 0 || (l < 0 && errno != EINTR)) {
 222         return false;
 223       }
 224     }
 225     return true;
 226   }
 227
 228   private bool flush () {
 229     uint len = cast(uint)(mBufPos-mBuf.ptr);
 230     if (len) {
 231       if (!fullWrite(mBuf.ptr, len)) return false;
 232       mBufPos = mBuf.ptr;
 233     }
 234     return true;
 235   }
 236
 237   private bool write (const(void)* ptrp, uint len) {
 238     import core.stdc.string : memcpy;
 239     auto ptr = cast(const(ubyte)*)ptrp;
 240     uint l = cast(uint)(mBuf.sizeof-(mBufPos-mBuf.ptr));
 241     mDataPos += len;
 242     if (len > l) {
 243       if (l) memcpy(mBufPos, ptr, l);
 244       mBufPos += l;
 245       if (!flush()) return false;
 246       ptr += l;
 247       len -= l;
 248       l = cast(uint)(len/mBuf.sizeof);
 249       if (l) {
 250         l *= cast(uint)mBuf.sizeof;
 251         if (!fullWrite(ptr, l)) return false;
 252         ptr += l;
 253         len -= l;
 254       }
 255     }
 256     if (len) {
 257       memcpy(mBufPos, ptr, len);
 258       mBufPos += len;
 259     }
 260     return true;
 261   }
 262
 263   private bool finish () {
 264     uint[256] hcnt; /* hash table counts */
 265     uint[256] hpos; /* hash table positions */
 266     Rec* htab;
 267     ubyte* p;
 268     RecList* rl;
 269     uint hsize;
 270
 271     if (((0xffffffffu-mDataPos)>>3) < mRCount) {
 272       mWasError = true;
 273       return /*errno = ENOMEM, -1*/false;
 274     }
 275
 276     /* count htab sizes and reorder reclists */
 277     hsize = 0;
 278     foreach (immutable uint t; 0..256) {
 279       RecList* rlt = null;
 280       uint i = 0;
 281       rl = mTables[t];
 282       while (rl) {
 283         RecList* rln = rl.next;
 284         rl.next = rlt;
 285         rlt = rl;
 286         i += rl.count;
 287         rl = rln;
 288       }
 289       mTables[t] = rlt;
 290       if (hsize < (hcnt[t] = i<<1)) hsize = hcnt[t];
 291     }
 292
 293     import core.stdc.stdlib : malloc, free;
 294     /* allocate memory to hold max htable */
 295     htab = cast(Rec*)malloc((hsize+2)*htab[0].sizeof);
 296     if (htab is null) {
 297       mWasError = true;
 298       return /*errno = ENOENT, -1*/false;
 299     }
 300     p = cast(ubyte*)htab;
 301     htab += 2;
 302
 303     /* build hash tables */
 304     foreach (immutable uint t; 0..256) {
 305       uint len, hi;
 306       hpos[t] = mDataPos;
 307       if ((len = hcnt[t]) == 0) continue;
 308       foreach (immutable i; 0..len) htab[i].hval = htab[i].rpos = 0;
 309       for (rl = mTables[t]; rl !is null; rl = rl.next) {
 310         foreach (immutable i; 0..rl.count) {
 311           hi = (rl.rec[i].hval>>8)%len;
 312           while (htab[hi].rpos) if (++hi == len) hi = 0;
 313           htab[hi] = rl.rec[i];
 314         }
 315       }
 316       foreach (immutable i; 0..len) {
 317         pack(htab[i].hval, p+(i<<3));
 318         pack(htab[i].rpos, p+(i<<3)+4);
 319       }
 320       if (!write(p, len<<3)) {
 321         mWasError = true;
 322         free(p);
 323         return false;
 324       }
 325     }
 326     free(p);
 327     if (!flush()) {
 328       mWasError = true;
 329       return false;
 330     }
 331
 332     p = mBuf.ptr;
 333     foreach (immutable t; 0..256) {
 334       pack(hpos[t], p+(t<<3));
 335       pack(hcnt[t], p+(t<<3)+4);
 336     }
 337
 338     if (!seek(0) || !fullWrite(p, 2048)) {
 339       mWasError = true;
 340       return false;
 341     }
 342
 343     return true;
 344   }
 345
 346   private bool addRecord (uint hval, const(void)[] key, const(void)[] val) {
 347     immutable klen = cast(uint)key.length;
 348     if (klen == 0) return false;
 349     immutable vlen = cast(uint)val.length;
 350     ubyte[8] rlen;
 351     RecList *rl;
 352     uint i;
 353     if (klen > 0xffffffffu-(mDataPos+8) || vlen > 0xffffffffu-(mDataPos+klen+8)) {
 354       mWasError = true;
 355       return /*errno = ENOMEM, -1*/false;
 356     }
 357     i = hval&0xff; // hash table number
 358     rl = mTables[i];
 359     if (rl is null || rl.count >= rl.rec.length) {
 360       // new chunk
 361       import core.stdc.stdlib : malloc;
 362       rl = cast(RecList*)malloc(RecList.sizeof);
 363       if (rl is null) return /*errno = ENOMEM, -1*/false;
 364       rl.count = 0;
 365       rl.next = mTables[i];
 366       mTables[i] = rl;
 367     }
 368     i = rl.count++;
 369     rl.rec[i].hval = hval;
 370     rl.rec[i].rpos = mDataPos;
 371     ++mRCount;
 372     pack(klen, rlen.ptr);
 373     pack(vlen, rlen.ptr+4);
 374     if (!write(rlen.ptr, 8) || !write(key.ptr, klen) || !write(val.ptr, vlen)) {
 375       mWasError = true;
 376       return false;
 377     }
 378     return true;
 379   }
 380
 381   void fixupRPos (uint rpos, uint rlen) {
 382     hashloop: foreach (immutable i; 0..256) {
 383       for (auto rl = mTables[i]; rl !is null; rl = rl.next) {
 384         Rec *rp, rs;
 385         for (rs = rl.rec.ptr, rp = rs+rl.count; --rp >= rs;) {
 386           if (rp.rpos <= rpos) continue hashloop;
 387           else rp.rpos -= rlen;
 388         }
 389       }
 390     }
 391   }
 392
 393   bool removeRecord (uint rpos, uint rlen) {
 394     uint len = cast(uint)(mDataPos-rpos-rlen);
 395     uint pos;
 396     int r;
 397     mDataPos -= rlen;
 398     if (!len) return false; /* it was the last record, nothing to do */
 399     pos = rpos;
 400     do {
 401       r = cast(int)(len > mBuf.sizeof ? mBuf.sizeof : len);
 402       if (!seek(pos+rlen) || (r = read(mBuf.ptr, r)) <= 0) {
 403         mWasError = true;
 404         return false;
 405       }
 406       if (!seek(pos) || !fullWrite(mBuf.ptr, r)) {
 407         mWasError = true;
 408         return false;
 409       }
 410       pos += r;
 411       len -= r;
 412     } while (len);
 413     assert(mDataPos == pos);
 414     fixupRPos(rpos, rlen);
 415     return true;
 416   }
 417
 418   bool zeroFillRecord (uint rpos, uint rlen) {
 419     if (rpos+rlen == mDataPos) {
 420       mDataPos = rpos;
 421       return true;
 422     }
 423     if (!seek(rpos)) return false;
 424     mBuf[] = 0;
 425     pack(rlen-8, mBuf.ptr+4);
 426     for (;;) {
 427       rpos = cast(uint)(rlen > mBuf.sizeof ? mBuf.sizeof : rlen);
 428       if (!fullWrite(mBuf.ptr, rpos)) {
 429         mWasError = true;
 430         return false;
 431       }
 432       rlen -= rpos;
 433       if (!rlen) return true;
 434       mBuf[4..8] = 0;
 435     }
 436   }
 437
 438   enum ERR = 1;
 439   enum NOTF = 0;
 440   /* return: 0 = not found, 1 = error; >1 = record length */
 441   uint matchKey (uint pos, const(void)[] key) {
 442     auto klen = cast(uint)key.length;
 443     if (klen < 1) return ERR;
 444     if (!seek(pos)) return ERR;
 445     if (!fullRead(mBuf.ptr, 8)) return ERR;
 446     if (unpack(mBuf.ptr) != klen) return NOTF;
 447     /* record length; check its validity */
 448     uint rlen = unpack(mBuf.ptr+4);
 449     if (rlen > mDataPos-pos-klen-8) return /*errno = EPROTO, 1*/ERR; /* someone changed our file? */
 450     rlen += klen+8;
 451     /* compare key */
 452     if (klen < mBuf.sizeof) {
 453       import core.stdc.string : memcmp;
 454       if (!fullRead(mBuf.ptr, klen)) return ERR;
 455       if (memcmp(mBuf.ptr, key.ptr, klen) != 0) return 0;
 456     } else {
 457       while (klen) {
 458         import core.stdc.string : memcmp;
 459         uint len = cast(uint)(klen > mBuf.sizeof ? mBuf.sizeof : klen);
 460         if (!fullRead(mBuf.ptr, len)) return ERR;
 461         if (memcmp(mBuf.ptr, key.ptr, len) != 0) return 0;
 462         key = key[len..$];
 463         klen -= len;
 464       }
 465     }
 466     return rlen;
 467   }
 468
 469   enum FindRes { ERROR = -1, NOT_FOUND = 0, FOUND = 1 }
 470   FindRes findRecord (const(void)[] key, uint hval, int mode) {
 471     RecList *rl;
 472     Rec *rp, rs;
 473     uint r;
 474     bool seeked = false;
 475     FindRes ret = FindRes.NOT_FOUND;
 476     outerloop: for (rl = mTables[hval&0xff]; rl !is null; rl = rl.next) {
 477       for (rs = rl.rec.ptr, rp = rs+rl.count; --rp >= rs;) {
 478         import core.stdc.string : memmove;
 479         if (rp.hval != hval) continue;
 480         /*XXX this explicit flush may be unnecessary having
 481          * smarter matchKey() that looks into mBuf too, but
 482          * most of a time here spent in finding hash values
 483          * (above), not keys */
 484         if (!seeked && !flush()) {
 485           mWasError = true;
 486           return FindRes.ERROR;
 487         }
 488         seeked = true;
 489         r = matchKey(rp.rpos, key);
 490         if (r == NOTF) continue; // not found
 491         if (r == ERR) {
 492           mWasError = true;
 493           return FindRes.ERROR;
 494         }
 495         ret = FindRes.FOUND;
 496         switch (mode) {
 497           case FIND_REMOVE:
 498             if (!removeRecord(rp.rpos, r)) return FindRes.ERROR;
 499             break;
 500           case FIND_FILL0:
 501             if (!zeroFillRecord(rp.rpos, r)) return FindRes.ERROR;
 502             break;
 503           default: break outerloop;
 504         }
 505         memmove(rp, rp+1, (rs+rl.count-1-rp)*rp[0].sizeof);
 506         --rl.count;
 507         --mRCount;
 508       }
 509     }
 510     if (seeked && !seek(mDataPos)) {
 511       mWasError = true;
 512       return FindRes.ERROR;
 513     }
 514     return ret;
 515   }
 516
 517 static:
 518   uint unpack() (const(ubyte)* buf) {
 519     //assert(buf !is null);
 520     uint n = buf[3];
 521     n <<= 8; n |= buf[2];
 522     n <<= 8; n |= buf[1];
 523     n <<= 8; n |= buf[0];
 524     return n;
 525   }
 526
 527   void pack() (uint num, ubyte* buf) nothrow @nogc {
 528     //assert(buf !is null);
 529     buf[0] = num&0xff; num >>= 8;
 530     buf[1] = num&0xff; num >>= 8;
 531     buf[2] = num&0xff;
 532     buf[3] = (num>>8)&0xff;
 533   }
 534 }