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