git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/tokyocabinet/tchdb.c

   1 /*************************************************************************************************
   2  * The hash database API of Tokyo Cabinet
   3  *                                                      Copyright (C) 2006-2008 Mikio Hirabayashi
   4  * This file is part of Tokyo Cabinet.
   5  * Tokyo Cabinet is free software; you can redistribute it and/or modify it under the terms of
   6  * the GNU Lesser General Public License as published by the Free Software Foundation; either
   7  * version 2.1 of the License or any later version.  Tokyo Cabinet is distributed in the hope
   8  * that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  10  * License for more details.
  11  * You should have received a copy of the GNU Lesser General Public License along with Tokyo
  12  * Cabinet; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
  13  * Boston, MA 02111-1307 USA.
  14  *************************************************************************************************/
  15
  16
  17 #include "tcutil.h"
  18 #include "tchdb.h"
  19 #include "myconf.h"
  20
  21 #define HDBFILEMODE    00644             // permission of created files
  22 #define HDBIOBUFSIZ    8192              // size of an I/O buffer
  23
  24 #define HDBMAGICDATA   "ToKyO CaBiNeT"   // magic data for identification
  25 #define HDBHEADSIZ     256               // size of the reagion of the header
  26 #define HDBTYPEOFF     32                // offset of the region for the database type
  27 #define HDBFLAGSOFF    33                // offset of the region for the additional flags
  28 #define HDBAPOWOFF     34                // offset of the region for the alignment power
  29 #define HDBFPOWOFF     35                // offset of the region for the free block pool power
  30 #define HDBOPTSOFF     36                // offset of the region for the options
  31 #define HDBBNUMOFF     40                // offset of the region for the bucket number
  32 #define HDBRNUMOFF     48                // offset of the region for the record number
  33 #define HDBFSIZOFF     56                // offset of the region for the file size
  34 #define HDBFRECOFF     64                // offset of the region for the first record offset
  35 #define HDBOPAQUEOFF   128               // offset of the region for the opaque field
  36
  37 #define HDBDEFBNUM     16381             // default bucket number
  38 #define HDBDEFAPOW     4                 // default alignment power
  39 #define HDBMAXAPOW     16                // maximum alignment power
  40 #define HDBDEFFPOW     10                // default free block pool power
  41 #define HDBMAXFPOW     20                // maximum free block pool power
  42 #define HDBMINRUNIT    48                // minimum record reading unit
  43 #define HDBMAXHSIZ     32                // maximum record header size
  44 #define HDBFBPBSIZ     64                // base region size of the free block pool
  45 #define HDBFBPESIZ     4                 // size of each region of the free block pool
  46 #define HDBFBPMGFREQ   256               // frequency to merge the free block pool
  47 #define HDBDRPUNIT     65536             // unit size of the delayed record pool
  48 #define HDBDRPLAT      2048              // latitude size of the delayed record pool
  49 #define HDBCACHEOUT    128               // number of records in a process of cacheout
  50
  51 typedef struct {                         // type of structure for a record
  52   uint64_t off;                          // offset of the record
  53   uint32_t rsiz;                         // size of the whole record
  54   uint8_t magic;                         // magic number
  55   uint8_t hash;                          // second hash value
  56   uint64_t left;                         // offset of the left child record
  57   uint64_t right;                        // offset of the right child record
  58   uint32_t ksiz;                         // size of the key
  59   uint32_t vsiz;                         // size of the value
  60   uint16_t psiz;                         // size of the padding
  61   const char *kbuf;                      // pointer to the key
  62   const char *vbuf;                      // pointer to the value
  63   uint64_t boff;                         // offset of the body
  64   char *bbuf;                            // buffer of the body
  65 } TCHREC;
  66
  67 typedef struct {                         // type of structure for a free block
  68   uint64_t off;                          // offset of the block
  69   uint32_t rsiz;                         // size of the block
  70 } HDBFB;
  71
  72 enum {                                   // enumeration for magic data
  73   HDBMAGICREC = 0xc8,                    // for data block
  74   HDBMAGICFB = 0xb0                      // for free block
  75 };
  76
  77 enum {                                   // enumeration for duplication behavior
  78   HDBPDOVER,                             // overwrite an existing value
  79   HDBPDKEEP,                             // keep the existing value
  80   HDBPDCAT                               // concatenate values
  81 };
  82
  83
  84 /* private macros */
  85 #define HDBLOCKMETHOD(TC_hdb, TC_wr) \
  86   ((TC_hdb)->mmtx ? tchdblockmethod((TC_hdb), (TC_wr)) : true)
  87 #define HDBUNLOCKMETHOD(TC_hdb) \
  88   ((TC_hdb)->mmtx ? tchdbunlockmethod(TC_hdb) : true)
  89 #define HDBLOCKDRP(TC_hdb) \
  90   ((TC_hdb)->mmtx ? tchdblockdrp(TC_hdb) : true)
  91 #define HDBUNLOCKDRP(TC_hdb) \
  92   ((TC_hdb)->mmtx ? tchdbunlockdrp(TC_hdb) : true)
  93
  94
  95 /* private function prototypes */
  96 static bool tcseekwrite(TCHDB *hdb, off_t off, const void *buf, size_t size);
  97 static bool tcseekread(TCHDB *hdb, off_t off, void *buf, size_t size);
  98 static void tcdumpmeta(TCHDB *hdb, char *hbuf);
  99 static void tcloadmeta(TCHDB *hdb, const char *hbuf);
 100 static uint64_t tcgetprime(uint64_t num);
 101 static void tchdbclear(TCHDB *hdb);
 102 static int32_t tchdbpadsize(TCHDB *hdb);
 103 static void tchdbsetflag(TCHDB *hdb, int flag, bool sign);
 104 static uint64_t tchdbbidx(TCHDB *hdb, const char *kbuf, int ksiz, uint8_t *hp);
 105 static off_t tchdbgetbucket(TCHDB *hdb, uint64_t bidx);
 106 static void tchdbsetbucket(TCHDB *hdb, uint64_t bidx, uint64_t off);
 107 static bool tchdbsavefbp(TCHDB *hdb);
 108 static bool tchdbloadfbp(TCHDB *hdb);
 109 static void tcfbpsortbyoff(HDBFB *fbpool, int fbpnum);
 110 static void tcfbpsortbyrsiz(HDBFB *fbpool, int fbpnum);
 111 static void tchdbfbpmerge(TCHDB *hdb);
 112 static void tchdbfbpinsert(TCHDB *hdb, uint64_t off, uint32_t rsiz);
 113 static bool tchdbfbpsearch(TCHDB *hdb, TCHREC *rec);
 114 static bool tchdbfbpsplice(TCHDB *hdb, TCHREC *rec, uint32_t nsiz);
 115 static bool tchdbwritefb(TCHDB *hdb, uint64_t off, uint32_t rsiz);
 116 static bool tchdbwriterec(TCHDB *hdb, TCHREC *rec, uint64_t bidx, off_t entoff);
 117 static bool tchdbreadrec(TCHDB *hdb, TCHREC *rec, char *rbuf);
 118 static bool tchdbreadrecbody(TCHDB *hdb, TCHREC *rec);
 119 static int tcreckeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz);
 120 static bool tchdbflushdrp(TCHDB *hdb);
 121 static void tchdbcacheadjust(TCHDB *hdb);
 122 static bool tchdbopenimpl(TCHDB *hdb, const char *path, int omode);
 123 static bool tchdbcloseimpl(TCHDB *hdb);
 124 static bool tchdbputimpl(TCHDB *hdb, const char *kbuf, int ksiz, const char *vbuf, int vsiz,
 125                          int dmode);
 126 static void tchdbdrpappend(TCHDB *hdb, const char *kbuf, int ksiz, const char *vbuf, int vsiz,
 127                            uint8_t hash);
 128 static bool tchdbputasyncimpl(TCHDB *hdb, const char *kbuf, int ksiz, const char *vbuf, int vsiz);
 129 static bool tchdboutimpl(TCHDB *hdb, const char *kbuf, int ksiz);
 130 static char *tchdbgetimpl(TCHDB *hdb, const char *kbuf, int ksiz, int *sp);
 131 static int tchdbgetintobuf(TCHDB *hdb, const char *kbuf, int ksiz, char *vbuf, int max);
 132 static int tchdbvsizimpl(TCHDB *hdb, const char *kbuf, int ksiz);
 133 static bool tchdbiterinitimpl(TCHDB *hdb);
 134 static char *tchdbiternextimpl(TCHDB *hdb, int *sp);
 135 static bool tchdbiternextintoxstr(TCHDB *hdb, TCXSTR *kxstr, TCXSTR *vxstr);
 136 static bool tchdboptimizeimpl(TCHDB *hdb, int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts);
 137 static bool tchdbvanishimpl(TCHDB *hdb);
 138 static bool tchdblockmethod(TCHDB *hdb, bool wr);
 139 static bool tchdbunlockmethod(TCHDB *hdb);
 140 static bool tchdblockdrp(TCHDB *hdb);
 141 static bool tchdbunlockdrp(TCHDB *hdb);
 142
 143
 144 /* debugging function prototypes */
 145 void tchdbprintmeta(TCHDB *hdb);
 146 void tchdbprintrec(TCHDB *hdb, TCHREC *rec);
 147
 148
 149
 150 /*************************************************************************************************
 151  * API
 152  *************************************************************************************************/
 153
 154
 155 /* Get the message string corresponding to an error code. */
 156 const char *tchdberrmsg(int ecode){
 157   switch(ecode){
 158   case TCESUCCESS: return "success";
 159   case TCETHREAD: return "threading error";
 160   case TCEINVALID: return "invalid operation";
 161   case TCENOFILE: return "file not found";
 162   case TCENOPERM: return "no permission";
 163   case TCEMETA: return "invalid meta data";
 164   case TCERHEAD: return "invalid record header";
 165   case TCEOPEN: return "open error";
 166   case TCECLOSE: return "close error";
 167   case TCETRUNC: return "trunc error";
 168   case TCESYNC: return "sync error";
 169   case TCESTAT: return "stat error";
 170   case TCESEEK: return "seek error";
 171   case TCEREAD: return "read error";
 172   case TCEWRITE: return "write error";
 173   case TCEMMAP: return "mmap error";
 174   case TCELOCK: return "lock error";
 175   case TCEUNLINK: return "unlink error";
 176   case TCERENAME: return "rename error";
 177   case TCEMKDIR: return "mkdir error";
 178   case TCERMDIR: return "rmdir error";
 179   case TCEKEEP: return "existing record";
 180   case TCENOREC: return "no record found";
 181   case TCEMISC: return "miscellaneous error";
 182   }
 183   return "unknown error";
 184 }
 185
 186
 187 /* Create a hash database object. */
 188 TCHDB *tchdbnew(void){
 189   TCHDB *hdb;
 190   TCMALLOC(hdb, sizeof(*hdb));
 191   tchdbclear(hdb);
 192   return hdb;
 193 }
 194
 195
 196 /* Delete a hash database object. */
 197 void tchdbdel(TCHDB *hdb){
 198   assert(hdb);
 199   if(hdb->fd >= 0) tchdbclose(hdb);
 200   if(hdb->mmtx){
 201     pthread_key_delete(*(pthread_key_t *)hdb->eckey);
 202     pthread_mutex_destroy(hdb->dmtx);
 203     pthread_rwlock_destroy(hdb->mmtx);
 204     free(hdb->eckey);
 205     free(hdb->dmtx);
 206     free(hdb->mmtx);
 207   }
 208   free(hdb);
 209 }
 210
 211
 212 /* Get the last happened error code of a hash database object. */
 213 int tchdbecode(TCHDB *hdb){
 214   assert(hdb);
 215   return hdb->mmtx ?
 216     (int)(intptr_t)pthread_getspecific(*(pthread_key_t *)hdb->eckey) : hdb->ecode;
 217 }
 218
 219
 220 /* Set mutual exclusion control of a hash database object for threading. */
 221 bool tchdbsetmutex(TCHDB *hdb){
 222   assert(hdb);
 223   if(!TCUSEPTHREAD) return true;
 224   if(!tcglobalmutexlock()) return false;
 225   if(hdb->mmtx || hdb->fd >= 0){
 226     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 227     tcglobalmutexunlock();
 228     return false;
 229   }
 230   pthread_mutexattr_t rma;
 231   pthread_mutexattr_init(&rma);
 232   TCMALLOC(hdb->mmtx, sizeof(pthread_rwlock_t));
 233   TCMALLOC(hdb->dmtx, sizeof(pthread_mutex_t));
 234   TCMALLOC(hdb->eckey, sizeof(pthread_key_t));
 235   if(pthread_mutexattr_settype(&rma, PTHREAD_MUTEX_RECURSIVE) != 0 ||
 236      pthread_rwlock_init(hdb->mmtx, NULL) != 0 || pthread_mutex_init(hdb->dmtx, &rma) != 0 ||
 237      pthread_key_create(hdb->eckey, NULL) != 0){
 238     tchdbsetecode(hdb, TCETHREAD, __FILE__, __LINE__, __func__);
 239     pthread_mutexattr_destroy(&rma);
 240     free(hdb->eckey);
 241     free(hdb->dmtx);
 242     free(hdb->mmtx);
 243     hdb->eckey = NULL;
 244     hdb->dmtx = NULL;
 245     hdb->mmtx = NULL;
 246     tcglobalmutexunlock();
 247     return false;
 248   }
 249   pthread_mutexattr_destroy(&rma);
 250   tcglobalmutexunlock();
 251   return true;
 252 }
 253
 254
 255 /* Set the tuning parameters of a hash database object. */
 256 bool tchdbtune(TCHDB *hdb, int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts){
 257   assert(hdb);
 258   if(hdb->fd >= 0){
 259     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 260     return false;
 261   }
 262   hdb->bnum = (bnum > 0) ? tcgetprime(bnum) : HDBDEFBNUM;
 263   hdb->apow = (apow >= 0) ? tclmin(apow, HDBMAXAPOW) : HDBDEFAPOW;
 264   hdb->fpow = (fpow >= 0) ? tclmin(fpow, HDBMAXFPOW) : HDBDEFFPOW;
 265   hdb->opts = opts;
 266   if(!_tc_deflate) hdb->opts &= ~HDBTDEFLATE;
 267   return true;
 268 }
 269
 270
 271 /* Set the caching parameters of a hash database object. */
 272 bool tchdbsetcache(TCHDB *hdb, int32_t rcnum){
 273   assert(hdb);
 274   if(hdb->fd >= 0){
 275     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 276     return false;
 277   }
 278   hdb->rcnum = (rcnum > 0) ? tclmin(tclmax(rcnum, HDBCACHEOUT * 2), INT_MAX / 4) : 0;
 279   return true;
 280 }
 281
 282
 283 /* Open a database file and connect a hash database object. */
 284 bool tchdbopen(TCHDB *hdb, const char *path, int omode){
 285   assert(hdb && path);
 286   if(!HDBLOCKMETHOD(hdb, true)) return false;
 287   if(hdb->fd >= 0){
 288     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 289     HDBUNLOCKMETHOD(hdb);
 290     return false;
 291   }
 292   bool rv = tchdbopenimpl(hdb, path, omode);
 293   HDBUNLOCKMETHOD(hdb);
 294   return rv;
 295 }
 296
 297
 298 /* Close a database object. */
 299 bool tchdbclose(TCHDB *hdb){
 300   assert(hdb);
 301   if(!HDBLOCKMETHOD(hdb, true)) return false;
 302   if(hdb->fd < 0){
 303     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 304     HDBUNLOCKMETHOD(hdb);
 305     return false;
 306   }
 307   bool rv = tchdbcloseimpl(hdb);
 308   HDBUNLOCKMETHOD(hdb);
 309   return rv;
 310 }
 311
 312
 313 /* Store a record into a hash database object. */
 314 bool tchdbput(TCHDB *hdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 315   assert(hdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 316   if(!HDBLOCKMETHOD(hdb, true)) return false;
 317   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 318     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 319     HDBUNLOCKMETHOD(hdb);
 320     return false;
 321   }
 322   if(hdb->async && !tchdbflushdrp(hdb)){
 323     HDBUNLOCKMETHOD(hdb);
 324     return false;
 325   }
 326   if(hdb->zmode){
 327     char *zbuf;
 328     if(hdb->opts & HDBTDEFLATE){
 329       zbuf = _tc_deflate(vbuf, vsiz, &vsiz, _TCZMRAW);
 330     } else {
 331       zbuf = tcbsencode(vbuf, vsiz, &vsiz);
 332     }
 333     if(!zbuf){
 334       tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
 335       HDBUNLOCKMETHOD(hdb);
 336       return false;
 337     }
 338     bool rv = tchdbputimpl(hdb, kbuf, ksiz, zbuf, vsiz, HDBPDOVER);
 339     free(zbuf);
 340     HDBUNLOCKMETHOD(hdb);
 341     return rv;
 342   }
 343   bool rv = tchdbputimpl(hdb, kbuf, ksiz, vbuf, vsiz, HDBPDOVER);
 344   HDBUNLOCKMETHOD(hdb);
 345   return rv;
 346 }
 347
 348
 349 /* Store a string record into a hash database object. */
 350 bool tchdbput2(TCHDB *hdb, const char *kstr, const char *vstr){
 351   assert(hdb && kstr && vstr);
 352   return tchdbput(hdb, kstr, strlen(kstr), vstr, strlen(vstr));
 353 }
 354
 355
 356 /* Store a new record into a hash database object. */
 357 bool tchdbputkeep(TCHDB *hdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 358   assert(hdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 359   if(!HDBLOCKMETHOD(hdb, true)) return false;
 360   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 361     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 362     HDBUNLOCKMETHOD(hdb);
 363     return false;
 364   }
 365   if(hdb->async && !tchdbflushdrp(hdb)){
 366     HDBUNLOCKMETHOD(hdb);
 367     return false;
 368   }
 369   if(hdb->zmode){
 370     char *zbuf;
 371     if(hdb->opts & HDBTDEFLATE){
 372       zbuf = _tc_deflate(vbuf, vsiz, &vsiz, _TCZMRAW);
 373     } else {
 374       zbuf = tcbsencode(vbuf, vsiz, &vsiz);
 375     }
 376     if(!zbuf){
 377       tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
 378       HDBUNLOCKMETHOD(hdb);
 379       return false;
 380     }
 381     bool rv = tchdbputimpl(hdb, kbuf, ksiz, zbuf, vsiz, HDBPDKEEP);
 382     free(zbuf);
 383     HDBUNLOCKMETHOD(hdb);
 384     return rv;
 385   }
 386   bool rv = tchdbputimpl(hdb, kbuf, ksiz, vbuf, vsiz, HDBPDKEEP);
 387   HDBUNLOCKMETHOD(hdb);
 388   return rv;
 389 }
 390
 391
 392 /* Store a new string record into a hash database object. */
 393 bool tchdbputkeep2(TCHDB *hdb, const char *kstr, const char *vstr){
 394   return tchdbputkeep(hdb, kstr, strlen(kstr), vstr, strlen(vstr));
 395 }
 396
 397
 398 /* Concatenate a value at the end of the existing record in a hash database object. */
 399 bool tchdbputcat(TCHDB *hdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 400   assert(hdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 401   if(!HDBLOCKMETHOD(hdb, true)) return false;
 402   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 403     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 404     HDBUNLOCKMETHOD(hdb);
 405     return false;
 406   }
 407   if(hdb->async && !tchdbflushdrp(hdb)){
 408     HDBUNLOCKMETHOD(hdb);
 409     return false;
 410   }
 411   if(hdb->zmode){
 412     char *zbuf;
 413     int osiz;
 414     char *obuf = tchdbgetimpl(hdb, kbuf, ksiz, &osiz);
 415     if(obuf){
 416       TCREALLOC(obuf, obuf, osiz + vsiz + 1);
 417       memcpy(obuf + osiz, vbuf, vsiz);
 418       if(hdb->opts & HDBTDEFLATE){
 419         zbuf = _tc_deflate(obuf, osiz + vsiz, &vsiz, _TCZMRAW);
 420       } else {
 421         zbuf = tcbsencode(obuf, osiz + vsiz, &vsiz);
 422       }
 423       free(obuf);
 424     } else {
 425       if(hdb->opts & HDBTDEFLATE){
 426         zbuf = _tc_deflate(vbuf, vsiz, &vsiz, _TCZMRAW);
 427       } else {
 428         zbuf = tcbsencode(vbuf, vsiz, &vsiz);
 429       }
 430     }
 431     if(!zbuf){
 432       tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
 433       HDBUNLOCKMETHOD(hdb);
 434       return false;
 435     }
 436     bool rv = tchdbputimpl(hdb, kbuf, ksiz, zbuf, vsiz, HDBPDOVER);
 437     free(zbuf);
 438     HDBUNLOCKMETHOD(hdb);
 439     return rv;
 440   }
 441   bool rv = tchdbputimpl(hdb, kbuf, ksiz, vbuf, vsiz, HDBPDCAT);
 442   HDBUNLOCKMETHOD(hdb);
 443   return rv;
 444 }
 445
 446
 447 /* Concatenate a string value at the end of the existing record in a hash database object. */
 448 bool tchdbputcat2(TCHDB *hdb, const char *kstr, const char *vstr){
 449   assert(hdb && kstr && vstr);
 450   return tchdbputcat(hdb, kstr, strlen(kstr), vstr, strlen(vstr));
 451 }
 452
 453
 454 /* Store a record into a hash database object in asynchronous fashion. */
 455 bool tchdbputasync(TCHDB *hdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 456   assert(hdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 457   if(!HDBLOCKMETHOD(hdb, true)) return false;
 458   hdb->async = true;
 459   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 460     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 461     HDBUNLOCKMETHOD(hdb);
 462     return false;
 463   }
 464   if(hdb->zmode){
 465     char *zbuf;
 466     if(hdb->opts & HDBTDEFLATE){
 467       zbuf = _tc_deflate(vbuf, vsiz, &vsiz, _TCZMRAW);
 468     } else {
 469       zbuf = tcbsencode(vbuf, vsiz, &vsiz);
 470     }
 471     if(!zbuf){
 472       tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
 473       HDBUNLOCKMETHOD(hdb);
 474       return false;
 475     }
 476     bool rv = tchdbputasyncimpl(hdb, kbuf, ksiz, zbuf, vsiz);
 477     free(zbuf);
 478     HDBUNLOCKMETHOD(hdb);
 479     return rv;
 480   }
 481   bool rv = tchdbputasyncimpl(hdb, kbuf, ksiz, vbuf, vsiz);
 482   HDBUNLOCKMETHOD(hdb);
 483   return rv;
 484 }
 485
 486
 487 /* Store a string record into a hash database object in asynchronous fashion. */
 488 bool tchdbputasync2(TCHDB *hdb, const char *kstr, const char *vstr){
 489   assert(hdb && kstr && vstr);
 490   return tchdbputasync(hdb, kstr, strlen(kstr), vstr, strlen(vstr));
 491 }
 492
 493
 494 /* Remove a record of a hash database object. */
 495 bool tchdbout(TCHDB *hdb, const void *kbuf, int ksiz){
 496   assert(hdb && kbuf && ksiz >= 0);
 497   if(!HDBLOCKMETHOD(hdb, true)) return false;
 498   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 499     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 500     HDBUNLOCKMETHOD(hdb);
 501     return false;
 502   }
 503   if(hdb->async && !tchdbflushdrp(hdb)){
 504     HDBUNLOCKMETHOD(hdb);
 505     return false;
 506   }
 507   bool rv = tchdboutimpl(hdb, kbuf, ksiz);
 508   HDBUNLOCKMETHOD(hdb);
 509   return rv;
 510 }
 511
 512
 513 /* Remove a string record of a hash database object. */
 514 bool tchdbout2(TCHDB *hdb, const char *kstr){
 515   assert(hdb && kstr);
 516   return tchdbout(hdb, kstr, strlen(kstr));
 517 }
 518
 519
 520 /* Retrieve a record in a hash database object. */
 521 void *tchdbget(TCHDB *hdb, const void *kbuf, int ksiz, int *sp){
 522   assert(hdb && kbuf && ksiz >= 0 && sp);
 523   if(!HDBLOCKMETHOD(hdb, false)) return NULL;
 524   if(hdb->fd < 0){
 525     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 526     HDBUNLOCKMETHOD(hdb);
 527     return NULL;
 528   }
 529   if(hdb->async && !tchdbflushdrp(hdb)){
 530     HDBUNLOCKMETHOD(hdb);
 531     return NULL;
 532   }
 533   char *rv = tchdbgetimpl(hdb, kbuf, ksiz, sp);
 534   HDBUNLOCKMETHOD(hdb);
 535   return rv;
 536 }
 537
 538
 539 /* Retrieve a string record in a hash database object. */
 540 char *tchdbget2(TCHDB *hdb, const char *kstr){
 541   assert(hdb && kstr);
 542   int vsiz;
 543   return tchdbget(hdb, kstr, strlen(kstr), &vsiz);
 544 }
 545
 546
 547 /* Retrieve a record in a hash database object and write the value into a buffer. */
 548 int tchdbget3(TCHDB *hdb, const void *kbuf, int ksiz, void *vbuf, int max){
 549   assert(hdb && kbuf && ksiz >= 0 && vbuf && max >= 0);
 550   if(!HDBLOCKMETHOD(hdb, false)) return -1;
 551   if(hdb->fd < 0){
 552     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 553     HDBUNLOCKMETHOD(hdb);
 554     return -1;
 555   }
 556   if(hdb->async && !tchdbflushdrp(hdb)){
 557     HDBUNLOCKMETHOD(hdb);
 558     return -1;
 559   }
 560   int rv = tchdbgetintobuf(hdb, kbuf, ksiz, vbuf, max);
 561   HDBUNLOCKMETHOD(hdb);
 562   return rv;
 563 }
 564
 565
 566 /* Get the size of the value of a record in a hash database object. */
 567 int tchdbvsiz(TCHDB *hdb, const void *kbuf, int ksiz){
 568   assert(hdb && kbuf && ksiz >= 0);
 569   if(!HDBLOCKMETHOD(hdb, false)) return -1;
 570   if(hdb->fd < 0){
 571     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 572     HDBUNLOCKMETHOD(hdb);
 573     return -1;
 574   }
 575   if(hdb->async && !tchdbflushdrp(hdb)){
 576     HDBUNLOCKMETHOD(hdb);
 577     return -1;
 578   }
 579   int rv = tchdbvsizimpl(hdb, kbuf, ksiz);
 580   HDBUNLOCKMETHOD(hdb);
 581   return rv;
 582 }
 583
 584
 585 /* Get the size of the value of a string record in a hash database object. */
 586 int tchdbvsiz2(TCHDB *hdb, const char *kstr){
 587   assert(hdb && kstr);
 588   return tchdbvsiz(hdb, kstr, strlen(kstr));
 589 }
 590
 591
 592 /* Initialize the iterator of a hash database object. */
 593 bool tchdbiterinit(TCHDB *hdb){
 594   assert(hdb);
 595   if(!HDBLOCKMETHOD(hdb, true)) return false;
 596   if(hdb->fd < 0){
 597     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 598     HDBUNLOCKMETHOD(hdb);
 599     return false;
 600   }
 601   if(hdb->async && !tchdbflushdrp(hdb)){
 602     HDBUNLOCKMETHOD(hdb);
 603     return false;
 604   }
 605   bool rv = tchdbiterinitimpl(hdb);
 606   HDBUNLOCKMETHOD(hdb);
 607   return rv;
 608 }
 609
 610
 611 /* Get the next key of the iterator of a hash database object. */
 612 void *tchdbiternext(TCHDB *hdb, int *sp){
 613   assert(hdb && sp);
 614   if(!HDBLOCKMETHOD(hdb, true)) return NULL;
 615   if(hdb->fd < 0 || hdb->iter < 1){
 616     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 617     HDBUNLOCKMETHOD(hdb);
 618     return NULL;
 619   }
 620   if(hdb->async && !tchdbflushdrp(hdb)){
 621     HDBUNLOCKMETHOD(hdb);
 622     return NULL;
 623   }
 624   char *rv = tchdbiternextimpl(hdb, sp);
 625   HDBUNLOCKMETHOD(hdb);
 626   return rv;
 627 }
 628
 629
 630 /* Get the next key string of the iterator of a hash database object. */
 631 char *tchdbiternext2(TCHDB *hdb){
 632   assert(hdb);
 633   int vsiz;
 634   return tchdbiternext(hdb, &vsiz);
 635 }
 636
 637
 638 /* Get the next extensible objects of the iterator of a hash database object. */
 639 bool tchdbiternext3(TCHDB *hdb, TCXSTR *kxstr, TCXSTR *vxstr){
 640   assert(hdb && kxstr && vxstr);
 641   if(!HDBLOCKMETHOD(hdb, true)) return false;
 642   if(hdb->fd < 0 || hdb->iter < 1){
 643     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 644     HDBUNLOCKMETHOD(hdb);
 645     return false;
 646   }
 647   if(hdb->async && !tchdbflushdrp(hdb)){
 648     HDBUNLOCKMETHOD(hdb);
 649     return false;
 650   }
 651   bool rv = tchdbiternextintoxstr(hdb, kxstr, vxstr);
 652   HDBUNLOCKMETHOD(hdb);
 653   return rv;
 654 }
 655
 656
 657 /* Get forward matching keys in a hash database object. */
 658 TCLIST *tchdbfwmkeys(TCHDB *hdb, const void *pbuf, int psiz, int max){
 659   assert(hdb && pbuf && psiz >= 0);
 660   TCLIST* keys = tclistnew();
 661   if(!HDBLOCKMETHOD(hdb, true)) return keys;
 662   if(hdb->fd < 0){
 663     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 664     HDBUNLOCKMETHOD(hdb);
 665     return keys;
 666   }
 667   if(hdb->async && !tchdbflushdrp(hdb)){
 668     HDBUNLOCKMETHOD(hdb);
 669     return keys;
 670   }
 671   if(max < 0) max = INT_MAX;
 672   uint64_t iter = hdb->iter;
 673   tchdbiterinitimpl(hdb);
 674   char *kbuf;
 675   int ksiz;
 676   while(TCLISTNUM(keys) < max && (kbuf = tchdbiternextimpl(hdb, &ksiz)) != NULL){
 677     if(ksiz >= psiz && !memcmp(kbuf, pbuf, psiz)){
 678       tclistpushmalloc(keys, kbuf, ksiz);
 679     } else {
 680       free(kbuf);
 681     }
 682   }
 683   hdb->iter = iter;
 684   HDBUNLOCKMETHOD(hdb);
 685   return keys;
 686 }
 687
 688
 689 /* Get forward matching string keys in a hash database object. */
 690 TCLIST *tchdbfwmkeys2(TCHDB *hdb, const char *pstr, int max){
 691   assert(hdb && pstr);
 692   return tchdbfwmkeys(hdb, pstr, strlen(pstr), max);
 693 }
 694
 695
 696 /* Synchronize updated contents of a hash database object with the file and the device. */
 697 bool tchdbsync(TCHDB *hdb){
 698   assert(hdb);
 699   if(!HDBLOCKMETHOD(hdb, true)) return false;
 700   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 701     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 702     HDBUNLOCKMETHOD(hdb);
 703     return false;
 704   }
 705   if(hdb->async && !tchdbflushdrp(hdb)){
 706     HDBUNLOCKMETHOD(hdb);
 707     return false;
 708   }
 709   bool rv = tchdbmemsync(hdb, true);
 710   HDBUNLOCKMETHOD(hdb);
 711   return rv;
 712 }
 713
 714
 715 /* Optimize the file of a hash database object. */
 716 bool tchdboptimize(TCHDB *hdb, int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts){
 717   assert(hdb);
 718   if(!HDBLOCKMETHOD(hdb, true)) return false;
 719   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 720     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 721     HDBUNLOCKMETHOD(hdb);
 722     return false;
 723   }
 724   if(hdb->async && !tchdbflushdrp(hdb)){
 725     HDBUNLOCKMETHOD(hdb);
 726     return false;
 727   }
 728   bool rv = tchdboptimizeimpl(hdb, bnum, apow, fpow, opts);
 729   HDBUNLOCKMETHOD(hdb);
 730   return rv;
 731 }
 732
 733
 734 /* Remove all records of a hash database object. */
 735 bool tchdbvanish(TCHDB *hdb){
 736   assert(hdb);
 737   if(!HDBLOCKMETHOD(hdb, true)) return false;
 738   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 739     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 740     HDBUNLOCKMETHOD(hdb);
 741     return false;
 742   }
 743   if(hdb->async && !tchdbflushdrp(hdb)){
 744     HDBUNLOCKMETHOD(hdb);
 745     return false;
 746   }
 747   bool rv = tchdbvanishimpl(hdb);
 748   HDBUNLOCKMETHOD(hdb);
 749   return rv;
 750 }
 751
 752
 753 /* Copy the database file of a hash database object. */
 754 bool tchdbcopy(TCHDB *hdb, const char *path){
 755   assert(hdb && path);
 756   if(!HDBLOCKMETHOD(hdb, false)) return false;
 757   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 758     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 759     HDBUNLOCKMETHOD(hdb);
 760     return false;
 761   }
 762   if(hdb->async && !tchdbflushdrp(hdb)){
 763     HDBUNLOCKMETHOD(hdb);
 764     return false;
 765   }
 766   if(!HDBLOCKDRP(hdb)){
 767     HDBUNLOCKMETHOD(hdb);
 768     return false;
 769   }
 770   bool err = false;
 771   hdb->flags &= ~HDBFOPEN;
 772   if(hdb->omode & HDBOWRITER){
 773     if(!tchdbsavefbp(hdb)) err = true;
 774     if(!tchdbmemsync(hdb, false)) err = true;
 775   }
 776   if(*path == '@'){
 777     int len = strlen(hdb->path);
 778     char name[len*2+1];
 779     char *wp = name;
 780     for(int i = 0; i < len; i++){
 781       switch(hdb->path[i]){
 782       case '\\':
 783       case '$':
 784         *(wp++) = '\\';
 785         *(wp++) = hdb->path[i];
 786         break;
 787       default:
 788         *(wp++) = hdb->path[i];
 789         break;
 790       }
 791     }
 792     *wp = '\0';
 793     char *cmd = tcsprintf("%s \"%s\" \"%llu\"",
 794                           path + 1, name, (unsigned long long)(tctime() * 1000000));
 795     if(system(cmd) != 0) err = true;
 796     free(cmd);
 797   } else {
 798     if(!tccopyfile(hdb->path, path)){
 799       tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
 800       err = true;
 801     }
 802   }
 803   hdb->flags |= HDBFOPEN;
 804   HDBUNLOCKDRP(hdb);
 805   HDBUNLOCKMETHOD(hdb);
 806   return !err;
 807 }
 808
 809
 810 /* Get the file path of a hash database object. */
 811 const char *tchdbpath(TCHDB *hdb){
 812   assert(hdb);
 813   if(!HDBLOCKMETHOD(hdb, false)) return NULL;
 814   if(hdb->fd < 0){
 815     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 816     HDBUNLOCKMETHOD(hdb);
 817     return NULL;
 818   }
 819   const char *rv = hdb->path;
 820   HDBUNLOCKMETHOD(hdb);
 821   return rv;
 822 }
 823
 824
 825 /* Get the number of records of a hash database object. */
 826 uint64_t tchdbrnum(TCHDB *hdb){
 827   assert(hdb);
 828   if(!HDBLOCKMETHOD(hdb, false)) return 0;
 829   if(hdb->fd < 0){
 830     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 831     HDBUNLOCKMETHOD(hdb);
 832     return 0;
 833   }
 834   uint64_t rv = hdb->rnum;
 835   HDBUNLOCKMETHOD(hdb);
 836   return rv;
 837 }
 838
 839
 840 /* Get the size of the database file of a hash database object. */
 841 uint64_t tchdbfsiz(TCHDB *hdb){
 842   assert(hdb);
 843   if(!HDBLOCKMETHOD(hdb, false)) return 0;
 844   if(hdb->fd < 0){
 845     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 846     HDBUNLOCKMETHOD(hdb);
 847     return 0;
 848   }
 849   uint64_t rv = hdb->fsiz;
 850   HDBUNLOCKMETHOD(hdb);
 851   return rv;
 852 }
 853
 854
 855
 856 /*************************************************************************************************
 857  * features for experts
 858  *************************************************************************************************/
 859
 860
 861 /* Set the error code of a hash database object. */
 862 void tchdbsetecode(TCHDB *hdb, int ecode, const char *filename, int line, const char *func){
 863   assert(hdb && filename && line >= 1 && func);
 864   if(!hdb->fatal){
 865     hdb->ecode = ecode;
 866     if(hdb->mmtx) pthread_setspecific(*(pthread_key_t *)hdb->eckey, (void *)(intptr_t)ecode);
 867   }
 868   if(ecode != TCEINVALID && ecode != TCEKEEP && ecode != TCENOREC){
 869     hdb->fatal = true;
 870     if(hdb->omode & HDBOWRITER) tchdbsetflag(hdb, HDBFFATAL, true);
 871   }
 872   if(hdb->dbgfd >= 0){
 873     char obuf[HDBIOBUFSIZ];
 874     int osiz = sprintf(obuf, "ERROR:%s:%d:%s:%s:%d:%s\n", filename, line, func,
 875                        hdb->path ? hdb->path : "-", ecode, tchdberrmsg(ecode));
 876     tcwrite(hdb->dbgfd, obuf, osiz);
 877   }
 878 }
 879
 880
 881 /* Set the type of a hash database object. */
 882 void tchdbsettype(TCHDB *hdb, uint8_t type){
 883   assert(hdb);
 884   if(hdb->fd >= 0){
 885     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 886     return;
 887   }
 888   hdb->type = type;
 889 }
 890
 891
 892 /* Set the file descriptor for debugging output. */
 893 void tchdbsetdbgfd(TCHDB *hdb, int fd){
 894   assert(hdb && fd >= 0);
 895   hdb->dbgfd = fd;
 896 }
 897
 898
 899 /* Get the file descriptor for debugging output. */
 900 int tchdbdbgfd(TCHDB *hdb){
 901   assert(hdb);
 902   return hdb->dbgfd;
 903 }
 904
 905
 906 /* Synchronize updating contents on memory. */
 907 bool tchdbmemsync(TCHDB *hdb, bool phys){
 908   assert(hdb);
 909   if(hdb->fd < 0 || !(hdb->omode & HDBOWRITER)){
 910     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 911     return false;
 912   }
 913   bool err = false;
 914   char hbuf[HDBHEADSIZ];
 915   tcdumpmeta(hdb, hbuf);
 916   memcpy(hdb->map, hbuf, HDBOPAQUEOFF);
 917   if(phys){
 918     if(msync(hdb->map, hdb->msiz, MS_SYNC) == -1){
 919       tchdbsetecode(hdb, TCEMMAP, __FILE__, __LINE__, __func__);
 920       err = true;
 921     }
 922     if(fsync(hdb->fd) == -1){
 923       tchdbsetecode(hdb, TCESYNC, __FILE__, __LINE__, __func__);
 924       err = true;
 925     }
 926   }
 927   return !err;
 928 }
 929
 930
 931 /* Get the number of elements of the bucket array of a hash database object. */
 932 uint64_t tchdbbnum(TCHDB *hdb){
 933   assert(hdb);
 934   if(hdb->fd < 0){
 935     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 936     return 0;
 937   }
 938   return hdb->bnum;
 939 }
 940
 941
 942 /* Get the record alignment a hash database object. */
 943 uint32_t tchdbalign(TCHDB *hdb){
 944   assert(hdb);
 945   if(hdb->fd < 0){
 946     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 947     return 0;
 948   }
 949   return hdb->align;
 950 }
 951
 952
 953 /* Get the maximum number of the free block pool of a a hash database object. */
 954 uint32_t tchdbfbpmax(TCHDB *hdb){
 955   assert(hdb);
 956   if(hdb->fd < 0){
 957     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 958     return 0;
 959   }
 960   return hdb->fbpmax;
 961 }
 962
 963
 964 /* Get the inode number of the database file of a hash database object. */
 965 uint64_t tchdbinode(TCHDB *hdb){
 966   assert(hdb);
 967   if(hdb->fd < 0){
 968     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 969     return 0;
 970   }
 971   return hdb->inode;
 972 }
 973
 974
 975 /* Get the modification time of the database file of a hash database object. */
 976 time_t tchdbmtime(TCHDB *hdb){
 977   assert(hdb);
 978   if(hdb->fd < 0){
 979     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 980     return 0;
 981   }
 982   return hdb->mtime;
 983 }
 984
 985
 986 /* Get the connection mode of a hash database object. */
 987 int tchdbomode(TCHDB *hdb){
 988   assert(hdb);
 989   if(hdb->fd < 0){
 990     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
 991     return 0;
 992   }
 993   return hdb->omode;
 994 }
 995
 996
 997 /* Get the database type of a hash database object. */
 998 uint8_t tchdbtype(TCHDB *hdb){
 999   assert(hdb);
1000   if(hdb->fd < 0){
1001     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
1002     return 0;
1003   }
1004   return hdb->type;
1005 }
1006
1007
1008 /* Get the additional flags of a hash database object. */
1009 uint8_t tchdbflags(TCHDB *hdb){
1010   assert(hdb);
1011   if(hdb->fd < 0){
1012     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
1013     return 0;
1014   }
1015   return hdb->flags;
1016 }
1017
1018
1019 /* Get the options of a hash database object. */
1020 uint8_t tchdbopts(TCHDB *hdb){
1021   assert(hdb);
1022   if(hdb->fd < 0){
1023     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
1024     return 0;
1025   }
1026   return hdb->opts;
1027 }
1028
1029
1030 /* Get the pointer to the opaque field of a hash database object. */
1031 char *tchdbopaque(TCHDB *hdb){
1032   assert(hdb);
1033   if(hdb->fd < 0){
1034     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
1035     return NULL;
1036   }
1037   return hdb->map + HDBOPAQUEOFF;
1038 }
1039
1040
1041 /* Get the number of used elements of the bucket array of a hash database object. */
1042 uint64_t tchdbbnumused(TCHDB *hdb){
1043   assert(hdb);
1044   if(hdb->fd < 0){
1045     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
1046     return 0;
1047   }
1048   uint64_t unum = 0;
1049   if(hdb->ba64){
1050     uint64_t *buckets = hdb->ba64;
1051     for(int i = 0; i < hdb->bnum; i++){
1052       if(buckets[i]) unum++;
1053     }
1054   } else {
1055     uint32_t *buckets = hdb->ba32;
1056     for(int i = 0; i < hdb->bnum; i++){
1057       if(buckets[i]) unum++;
1058     }
1059   }
1060   return unum;
1061 }
1062
1063
1064
1065 /*************************************************************************************************
1066  * private features
1067  *************************************************************************************************/
1068
1069
1070 /* Seek and read data from a file.
1071    `hdb' specifies the hash database object.
1072    `off' specifies the offset of the region to seek.
1073    `buf' specifies the buffer to store into.
1074    `size' specifies the size of the buffer.
1075    The return value is true if successful, else, it is false. */
1076 static bool tcseekwrite(TCHDB *hdb, off_t off, const void *buf, size_t size){
1077   assert(hdb && off >= 0 && buf && size >= 0);
1078   while(true){
1079     int wb = pwrite(hdb->fd, buf, size, off);
1080     if(wb >= size){
1081       return true;
1082     } else if(wb > 0){
1083       buf = (char *)buf + wb;
1084       size -= wb;
1085       off += wb;
1086     } else if(wb == -1){
1087       if(errno != EINTR){
1088         tchdbsetecode(hdb, TCEWRITE, __FILE__, __LINE__, __func__);
1089         return false;
1090       }
1091     } else {
1092       if(size > 0){
1093         tchdbsetecode(hdb, TCEWRITE, __FILE__, __LINE__, __func__);
1094         return false;
1095       }
1096     }
1097   }
1098   return true;
1099 }
1100
1101
1102 /* Seek and read data from a file.
1103    `hdb' specifies the hash database object.
1104    `off' specifies the offset of the region to seek.
1105    `buf' specifies the buffer to store into.
1106    `size' specifies the size of the buffer.
1107    The return value is true if successful, else, it is false. */
1108 static bool tcseekread(TCHDB *hdb, off_t off, void *buf, size_t size){
1109   assert(hdb && off >= 0 && buf && size >= 0);
1110   while(true){
1111     int rb = pread(hdb->fd, buf, size, off);
1112     if(rb >= size){
1113       break;
1114     } else if(rb > 0){
1115       buf = (char *)buf + rb;
1116       size -= rb;
1117       off += rb;
1118     } else if(rb == -1){
1119       if(errno != EINTR){
1120         tchdbsetecode(hdb, TCEREAD, __FILE__, __LINE__, __func__);
1121         return false;
1122       }
1123     } else {
1124       if(size > 0){
1125         tchdbsetecode(hdb, TCEREAD, __FILE__, __LINE__, __func__);
1126         return false;
1127       }
1128     }
1129   }
1130   return true;
1131 }
1132
1133
1134 /* Serialize meta data into a buffer.
1135    `hdb' specifies the hash database object.
1136    `hbuf' specifies the buffer. */
1137 static void tcdumpmeta(TCHDB *hdb, char *hbuf){
1138   memset(hbuf, 0, HDBHEADSIZ);
1139   sprintf(hbuf, "%s\n%s:%d\n", HDBMAGICDATA, _TC_FORMATVER, _TC_LIBVER);
1140   memcpy(hbuf + HDBTYPEOFF, &(hdb->type), sizeof(hdb->type));
1141   memcpy(hbuf + HDBFLAGSOFF, &(hdb->flags), sizeof(hdb->flags));
1142   memcpy(hbuf + HDBAPOWOFF, &(hdb->apow), sizeof(hdb->apow));
1143   memcpy(hbuf + HDBFPOWOFF, &(hdb->fpow), sizeof(hdb->fpow));
1144   memcpy(hbuf + HDBOPTSOFF, &(hdb->opts), sizeof(hdb->opts));
1145   uint64_t llnum;
1146   llnum = hdb->bnum;
1147   llnum = TCHTOILL(llnum);
1148   memcpy(hbuf + HDBBNUMOFF, &llnum, sizeof(llnum));
1149   llnum = hdb->rnum;
1150   llnum = TCHTOILL(llnum);
1151   memcpy(hbuf + HDBRNUMOFF, &llnum, sizeof(llnum));
1152   llnum = hdb->fsiz;
1153   llnum = TCHTOILL(llnum);
1154   memcpy(hbuf + HDBFSIZOFF, &llnum, sizeof(llnum));
1155   llnum = hdb->frec;
1156   llnum = TCHTOILL(llnum);
1157   memcpy(hbuf + HDBFRECOFF, &llnum, sizeof(llnum));
1158 }
1159
1160
1161 /* Deserialize meta data from a buffer.
1162    `hdb' specifies the hash database object.
1163    `hbuf' specifies the buffer. */
1164 static void tcloadmeta(TCHDB *hdb, const char *hbuf){
1165   memcpy(&(hdb->type), hbuf + HDBTYPEOFF, sizeof(hdb->type));
1166   memcpy(&(hdb->flags), hbuf + HDBFLAGSOFF, sizeof(hdb->flags));
1167   memcpy(&(hdb->apow), hbuf + HDBAPOWOFF, sizeof(hdb->apow));
1168   memcpy(&(hdb->fpow), hbuf + HDBFPOWOFF, sizeof(hdb->fpow));
1169   memcpy(&(hdb->opts), hbuf + HDBOPTSOFF, sizeof(hdb->opts));
1170   uint64_t llnum;
1171   memcpy(&llnum, hbuf + HDBBNUMOFF, sizeof(llnum));
1172   hdb->bnum = TCITOHLL(llnum);
1173   memcpy(&llnum, hbuf + HDBRNUMOFF, sizeof(llnum));
1174   hdb->rnum = TCITOHLL(llnum);
1175   memcpy(&llnum, hbuf + HDBFSIZOFF, sizeof(llnum));
1176   hdb->fsiz = TCITOHLL(llnum);
1177   memcpy(&llnum, hbuf + HDBFRECOFF, sizeof(llnum));
1178   hdb->frec = TCITOHLL(llnum);
1179 }
1180
1181
1182 /* Get a natural prime number not less than a floor number.
1183    `num' specified the floor number.
1184    The return value is a prime number not less than the floor number. */
1185 static uint64_t tcgetprime(uint64_t num){
1186   uint64_t primes[] = {
1187     1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 71, 79, 83,
1188     89, 103, 109, 113, 127, 139, 157, 173, 191, 199, 223, 239, 251, 283, 317, 349,
1189     383, 409, 443, 479, 509, 571, 631, 701, 761, 829, 887, 953, 1021, 1151, 1279,
1190     1399, 1531, 1663, 1789, 1913, 2039, 2297, 2557, 2803, 3067, 3323, 3583, 3833,
1191     4093, 4603, 5119, 5623, 6143, 6653, 7159, 7673, 8191, 9209, 10223, 11261,
1192     12281, 13309, 14327, 15359, 16381, 18427, 20479, 22511, 24571, 26597, 28669,
1193     30713, 32749, 36857, 40949, 45053, 49139, 53239, 57331, 61417, 65521, 73727,
1194     81919, 90107, 98299, 106487, 114679, 122869, 131071, 147451, 163819, 180221,
1195     196597, 212987, 229373, 245759, 262139, 294911, 327673, 360439, 393209, 425977,
1196     458747, 491503, 524287, 589811, 655357, 720887, 786431, 851957, 917503, 982981,
1197     1048573, 1179641, 1310719, 1441771, 1572853, 1703903, 1835003, 1966079,
1198     2097143, 2359267, 2621431, 2883577, 3145721, 3407857, 3670013, 3932153,
1199     4194301, 4718579, 5242877, 5767129, 6291449, 6815741, 7340009, 7864301,
1200     8388593, 9437179, 10485751, 11534329, 12582893, 13631477, 14680063, 15728611,
1201     16777213, 18874367, 20971507, 23068667, 25165813, 27262931, 29360087, 31457269,
1202     33554393, 37748717, 41943023, 46137319, 50331599, 54525917, 58720253, 62914549,
1203     67108859, 75497467, 83886053, 92274671, 100663291, 109051903, 117440509,
1204     125829103, 134217689, 150994939, 167772107, 184549373, 201326557, 218103799,
1205     234881011, 251658227, 268435399, 301989881, 335544301, 369098707, 402653171,
1206     436207613, 469762043, 503316469, 536870909, 603979769, 671088637, 738197503,
1207     805306357, 872415211, 939524087, 1006632947, 1073741789, 1207959503,
1208     1342177237, 1476394991, 1610612711, 1744830457, 1879048183, 2013265907,
1209     2576980349, 3092376431, 3710851741, 4718021527, 6133428047, 7973456459,
1210     10365493393, 13475141413, 17517683831, 22772988923, 29604885677, 38486351381,
1211     50032256819, 65041933867, 84554514043, 109920868241, 0
1212   };
1213   int i;
1214   for(i = 0; primes[i] > 0; i++){
1215     if(num <= primes[i]) return primes[i];
1216   }
1217   return primes[i-1];
1218 }
1219
1220
1221 /* Clear all members.
1222    `hdb' specifies the hash database object. */
1223 static void tchdbclear(TCHDB *hdb){
1224   assert(hdb);
1225   hdb->mmtx = NULL;
1226   hdb->dmtx = NULL;
1227   hdb->eckey = NULL;
1228   hdb->type = HDBTHASH;
1229   hdb->flags = 0;
1230   hdb->bnum = HDBDEFBNUM;
1231   hdb->apow = HDBDEFAPOW;
1232   hdb->fpow = HDBDEFFPOW;
1233   hdb->opts = 0;
1234   hdb->path = NULL;
1235   hdb->fd = -1;
1236   hdb->omode = 0;
1237   hdb->rnum = 0;
1238   hdb->fsiz = 0;
1239   hdb->frec = 0;
1240   hdb->iter = 0;
1241   hdb->map = NULL;
1242   hdb->msiz = 0;
1243   hdb->ba32 = NULL;
1244   hdb->ba64 = NULL;
1245   hdb->align = 0;
1246   hdb->runit = 0;
1247   hdb->zmode = false;
1248   hdb->fbpmax = 0;
1249   hdb->fbpsiz = 0;
1250   hdb->fbpool = NULL;
1251   hdb->fbpnum = 0;
1252   hdb->fbpmis = 0;
1253   hdb->async = false;
1254   hdb->drpool = NULL;
1255   hdb->drpdef = NULL;
1256   hdb->drpoff = 0;
1257   hdb->recc = NULL;
1258   hdb->rcnum = 0;
1259   hdb->ecode = TCESUCCESS;
1260   hdb->fatal = false;
1261   hdb->dbgfd = -1;
1262   hdb->cnt_writerec = -1;
1263   hdb->cnt_reuserec = -1;
1264   hdb->cnt_moverec = -1;
1265   hdb->cnt_readrec = -1;
1266   hdb->cnt_searchfbp = -1;
1267   hdb->cnt_insertfbp = -1;
1268   hdb->cnt_splicefbp = -1;
1269   hdb->cnt_dividefbp = -1;
1270   hdb->cnt_mergefbp = -1;
1271   hdb->cnt_reducefbp = -1;
1272   hdb->cnt_appenddrp = -1;
1273   hdb->cnt_deferdrp = -1;
1274   hdb->cnt_flushdrp = -1;
1275   hdb->cnt_adjrecc = -1;
1276   TCDODEBUG(hdb->cnt_writerec = 0);
1277   TCDODEBUG(hdb->cnt_reuserec = 0);
1278   TCDODEBUG(hdb->cnt_moverec = 0);
1279   TCDODEBUG(hdb->cnt_readrec = 0);
1280   TCDODEBUG(hdb->cnt_searchfbp = 0);
1281   TCDODEBUG(hdb->cnt_insertfbp = 0);
1282   TCDODEBUG(hdb->cnt_splicefbp = 0);
1283   TCDODEBUG(hdb->cnt_dividefbp = 0);
1284   TCDODEBUG(hdb->cnt_mergefbp = 0);
1285   TCDODEBUG(hdb->cnt_reducefbp = 0);
1286   TCDODEBUG(hdb->cnt_appenddrp = 0);
1287   TCDODEBUG(hdb->cnt_deferdrp = 0);
1288   TCDODEBUG(hdb->cnt_flushdrp = 0);
1289   TCDODEBUG(hdb->cnt_adjrecc = 0);
1290 }
1291
1292
1293 /* Get the padding size to record alignment.
1294    `hdb' specifies the hash database object.
1295    The return value is the padding size. */
1296 static int32_t tchdbpadsize(TCHDB *hdb){
1297   assert(hdb);
1298   int32_t diff = hdb->fsiz & (hdb->align - 1);
1299   return diff > 0 ? hdb->align - diff : 0;
1300 }
1301
1302
1303 /* Set the open flag.
1304    `hdb' specifies the hash database object.
1305    `flag' specifies the flag value.
1306    `sign' specifies the sign. */
1307 static void tchdbsetflag(TCHDB *hdb, int flag, bool sign){
1308   assert(hdb);
1309   char *fp = (char *)hdb->map + HDBFLAGSOFF;
1310   if(sign){
1311     *fp |= (uint8_t)flag;
1312   } else {
1313     *fp &= ~(uint8_t)flag;
1314   }
1315   hdb->flags = *fp;
1316 }
1317
1318
1319 /* Get the bucket index of a record.
1320    `hdb' specifies the hash database object.
1321    `kbuf' specifies the pointer to the region of the key.
1322    `ksiz' specifies the size of the region of the key.
1323    `hp' specifies the pointer to the variable into which the second hash value is assigned.
1324    The return value is the bucket index. */
1325 static uint64_t tchdbbidx(TCHDB *hdb, const char *kbuf, int ksiz, uint8_t *hp){
1326   assert(hdb && kbuf && ksiz >= 0 && hp);
1327   uint64_t idx = 19780211;
1328   uint32_t hash = 751;
1329   const char *rp = kbuf + ksiz;
1330   while(ksiz--){
1331     idx = (idx << 5) + (idx << 2) + idx + *(uint8_t *)kbuf++;
1332     hash = ((hash << 5) - hash) ^ *(uint8_t *)--rp;
1333   }
1334   *hp = hash;
1335   return idx % hdb->bnum;
1336 }
1337
1338
1339 /* Get the offset of the record of a bucket element.
1340    `hdb' specifies the hash database object.
1341    `bidx' specifies the index of the bucket.
1342    The return value is the offset of the record. */
1343 static off_t tchdbgetbucket(TCHDB *hdb, uint64_t bidx){
1344   assert(hdb && bidx >= 0);
1345   if(hdb->ba64){
1346     uint64_t llnum = hdb->ba64[bidx];
1347     return TCITOHLL(llnum) << hdb->apow;
1348   }
1349   uint32_t lnum = hdb->ba32[bidx];
1350   return (off_t)TCITOHL(lnum) << hdb->apow;
1351 }
1352
1353
1354 /* Get the offset of the record of a bucket element.
1355    `hdb' specifies the hash database object.
1356    `bidx' specifies the index of the record.
1357    `off' specifies the offset of the record. */
1358 static void tchdbsetbucket(TCHDB *hdb, uint64_t bidx, uint64_t off){
1359   assert(hdb && bidx >= 0);
1360   if(hdb->ba64){
1361     uint64_t llnum = off >> hdb->apow;
1362     hdb->ba64[bidx] = TCHTOILL(llnum);
1363   } else {
1364     uint32_t lnum = off >> hdb->apow;
1365     hdb->ba32[bidx] = TCHTOIL(lnum);
1366   }
1367 }
1368
1369
1370 /* Load the free block pool from the file.
1371    The return value is true if successful, else, it is false. */
1372 static bool tchdbsavefbp(TCHDB *hdb){
1373   assert(hdb);
1374   if(hdb->fbpnum > (hdb->fbpmax >> 1)){
1375     tchdbfbpmerge(hdb);
1376   } else if(hdb->fbpnum > 1){
1377     tcfbpsortbyoff(hdb->fbpool, hdb->fbpnum);
1378   }
1379   int bsiz = hdb->fbpsiz;
1380   char *buf;
1381   TCMALLOC(buf, bsiz);
1382   char *wp = buf;
1383   HDBFB *cur = hdb->fbpool;
1384   HDBFB *end = cur + hdb->fbpnum;
1385   uint64_t base = 0;
1386   bsiz -= sizeof(HDBFB) + sizeof(uint8_t) + sizeof(uint8_t);
1387   while(cur < end && bsiz > 0){
1388     uint64_t noff = cur->off >> hdb->apow;
1389     int step;
1390     uint64_t llnum = noff - base;
1391     TCSETVNUMBUF64(step, wp, llnum);
1392     wp += step;
1393     bsiz -= step;
1394     uint32_t lnum = cur->rsiz >> hdb->apow;
1395     TCSETVNUMBUF(step, wp, lnum);
1396     wp += step;
1397     bsiz -= step;
1398     base = noff;
1399     cur++;
1400   }
1401   *(wp++) = '\0';
1402   *(wp++) = '\0';
1403   if(!tcseekwrite(hdb, hdb->msiz, buf, wp - buf)){
1404     free(buf);
1405     return false;
1406   }
1407   free(buf);
1408   return true;
1409 }
1410
1411
1412 /* Save the free block pool into the file.
1413    The return value is true if successful, else, it is false. */
1414 static bool tchdbloadfbp(TCHDB *hdb){
1415   int bsiz = hdb->fbpsiz;
1416   char *buf;
1417   TCMALLOC(buf, bsiz);
1418   if(!tcseekread(hdb, hdb->msiz, buf, bsiz)){
1419     free(buf);
1420     return false;
1421   }
1422   const char *rp = buf;
1423   HDBFB *cur = hdb->fbpool;
1424   HDBFB *end = cur + hdb->fbpmax;
1425   uint64_t base = 0;
1426   while(cur < end && *rp != '\0'){
1427     int step;
1428     uint64_t llnum;
1429     TCREADVNUMBUF64(rp, llnum, step);
1430     base += llnum << hdb->apow;
1431     cur->off = base;
1432     rp += step;
1433     uint32_t lnum;
1434     TCREADVNUMBUF(rp, lnum, step);
1435     cur->rsiz = lnum << hdb->apow;
1436     rp += step;
1437     cur++;
1438   }
1439   hdb->fbpnum = cur - (HDBFB *)hdb->fbpool;
1440   free(buf);
1441   return true;
1442 }
1443
1444
1445 /* Sort the free block pool by offset.
1446    `fbpool' specifies the free block pool.
1447    `fbpnum' specifies the number of blocks. */
1448 static void tcfbpsortbyoff(HDBFB *fbpool, int fbpnum){
1449   assert(fbpool && fbpnum >= 0);
1450   fbpnum--;
1451   int bottom = fbpnum / 2 + 1;
1452   int top = fbpnum;
1453   while(bottom > 0){
1454     bottom--;
1455     int mybot = bottom;
1456     int i = 2 * mybot;
1457     while(i <= top){
1458       if(i < top && fbpool[i+1].off > fbpool[i].off) i++;
1459       if(fbpool[mybot].off >= fbpool[i].off) break;
1460       HDBFB swap = fbpool[mybot];
1461       fbpool[mybot] = fbpool[i];
1462       fbpool[i] = swap;
1463       mybot = i;
1464       i = 2 * mybot;
1465     }
1466   }
1467   while(top > 0){
1468     HDBFB swap = fbpool[0];
1469     fbpool[0] = fbpool[top];
1470     fbpool[top] = swap;
1471     top--;
1472     int mybot = bottom;
1473     int i = 2 * mybot;
1474     while(i <= top){
1475       if(i < top && fbpool[i+1].off > fbpool[i].off) i++;
1476       if(fbpool[mybot].off >= fbpool[i].off) break;
1477       swap = fbpool[mybot];
1478       fbpool[mybot] = fbpool[i];
1479       fbpool[i] = swap;
1480       mybot = i;
1481       i = 2 * mybot;
1482     }
1483   }
1484 }
1485
1486
1487 /* Sort the free block pool by record size.
1488    `fbpool' specifies the free block pool.
1489    `fbpnum' specifies the number of blocks. */
1490 static void tcfbpsortbyrsiz(HDBFB *fbpool, int fbpnum){
1491   assert(fbpool && fbpnum >= 0);
1492   fbpnum--;
1493   int bottom = fbpnum / 2 + 1;
1494   int top = fbpnum;
1495   while(bottom > 0){
1496     bottom--;
1497     int mybot = bottom;
1498     int i = 2 * mybot;
1499     while(i <= top){
1500       if(i < top && fbpool[i+1].rsiz > fbpool[i].rsiz) i++;
1501       if(fbpool[mybot].rsiz >= fbpool[i].rsiz) break;
1502       HDBFB swap = fbpool[mybot];
1503       fbpool[mybot] = fbpool[i];
1504       fbpool[i] = swap;
1505       mybot = i;
1506       i = 2 * mybot;
1507     }
1508   }
1509   while(top > 0){
1510     HDBFB swap = fbpool[0];
1511     fbpool[0] = fbpool[top];
1512     fbpool[top] = swap;
1513     top--;
1514     int mybot = bottom;
1515     int i = 2 * mybot;
1516     while(i <= top){
1517       if(i < top && fbpool[i+1].rsiz > fbpool[i].rsiz) i++;
1518       if(fbpool[mybot].rsiz >= fbpool[i].rsiz) break;
1519       swap = fbpool[mybot];
1520       fbpool[mybot] = fbpool[i];
1521       fbpool[i] = swap;
1522       mybot = i;
1523       i = 2 * mybot;
1524     }
1525   }
1526 }
1527
1528
1529 /* Merge successive records in the free block pool.
1530    `hdb' specifies the hash database object. */
1531 static void tchdbfbpmerge(TCHDB *hdb){
1532   assert(hdb);
1533   TCDODEBUG(hdb->cnt_mergefbp++);
1534   int32_t onum = hdb->fbpnum;
1535   tcfbpsortbyoff(hdb->fbpool, hdb->fbpnum);
1536   HDBFB *wp = hdb->fbpool;;
1537   HDBFB *cur = wp;
1538   HDBFB *end = wp + hdb->fbpnum - 1;
1539   while(cur < end){
1540     if(cur->off > 0){
1541       HDBFB *next = cur + 1;
1542       if(cur->off + cur->rsiz == next->off){
1543         if(hdb->iter == next->off) hdb->iter += next->rsiz;
1544         cur->rsiz += next->rsiz;
1545         next->off = 0;
1546       }
1547       *(wp++) = *cur;
1548     }
1549     cur++;
1550   }
1551   if(end->off > 0) *(wp++) = *end;
1552   hdb->fbpnum = wp - (HDBFB *)hdb->fbpool;
1553   hdb->fbpmis = (hdb->fbpnum < onum) ? 0 : hdb->fbpnum * -2;
1554 }
1555
1556
1557 /* Insert a block into the free block pool.
1558    `hdb' specifies the hash database object.
1559    `off' specifies the offset of the block.
1560    `rsiz' specifies the size of the block. */
1561 static void tchdbfbpinsert(TCHDB *hdb, uint64_t off, uint32_t rsiz){
1562   assert(hdb && off > 0 && rsiz > 0);
1563   TCDODEBUG(hdb->cnt_insertfbp++);
1564   if(hdb->fpow < 1) return;
1565   HDBFB *pv = hdb->fbpool;
1566   if(hdb->fbpnum >= hdb->fbpmax){
1567     tchdbfbpmerge(hdb);
1568     tcfbpsortbyrsiz(hdb->fbpool, hdb->fbpnum);
1569     if(hdb->fbpnum >= hdb->fbpmax){
1570       TCDODEBUG(hdb->cnt_reducefbp++);
1571       int32_t dnum = (hdb->fbpmax >> 2) + 1;
1572       memmove(pv, pv + dnum, (hdb->fbpnum - dnum) * sizeof(*pv));
1573       hdb->fbpnum -= dnum;
1574     }
1575     hdb->fbpmis = 0;
1576   }
1577   pv = pv + hdb->fbpnum;
1578   pv->off = off;
1579   pv->rsiz = rsiz;
1580   hdb->fbpnum++;
1581 }
1582
1583
1584 /* Search the free block pool for the minimum region.
1585    `hdb' specifies the hash database object.
1586    `rec' specifies the record object to be stored.
1587    The return value is true if successful, else, it is false. */
1588 static bool tchdbfbpsearch(TCHDB *hdb, TCHREC *rec){
1589   assert(hdb && rec);
1590   TCDODEBUG(hdb->cnt_searchfbp++);
1591   if(hdb->fbpnum < 1){
1592     rec->off = hdb->fsiz;
1593     rec->rsiz = 0;
1594     return true;
1595   }
1596   uint32_t rsiz = rec->rsiz;
1597   HDBFB *pv = hdb->fbpool;
1598   HDBFB *ep = pv + hdb->fbpnum;
1599   while(pv < ep){
1600     if(pv->rsiz > rsiz){
1601       if(pv->rsiz > (rsiz << 1)){
1602         uint64_t fsiz = hdb->fsiz;
1603         hdb->fsiz = pv->off + rsiz;
1604         uint32_t psiz = tchdbpadsize(hdb);
1605         hdb->fsiz = fsiz;
1606         uint64_t noff = pv->off + rsiz + psiz;
1607         if(pv->rsiz >= ((noff - pv->off) << 1)){
1608           TCDODEBUG(hdb->cnt_dividefbp++);
1609           rec->off = pv->off;
1610           rec->rsiz = noff - pv->off;
1611           pv->off = noff;
1612           pv->rsiz -= rec->rsiz;
1613           return tchdbwritefb(hdb, pv->off, pv->rsiz);
1614         }
1615       }
1616       rec->off = pv->off;
1617       rec->rsiz = pv->rsiz;
1618       ep--;
1619       pv->off = ep->off;
1620       pv->rsiz = ep->rsiz;
1621       hdb->fbpnum--;
1622       return true;
1623     }
1624     pv++;
1625   }
1626   rec->off = hdb->fsiz;
1627   rec->rsiz = 0;
1628   hdb->fbpmis++;
1629   if(hdb->fbpmis >= HDBFBPMGFREQ){
1630     tchdbfbpmerge(hdb);
1631     tcfbpsortbyrsiz(hdb->fbpool, hdb->fbpnum);
1632   }
1633   return true;
1634 }
1635
1636
1637 /* Splice the trailing free block
1638    `hdb' specifies the hash database object.
1639    `rec' specifies the record object to be stored.
1640    `nsiz' specifies the needed size.
1641    The return value is whether splicing succeeded or not. */
1642 static bool tchdbfbpsplice(TCHDB *hdb, TCHREC *rec, uint32_t nsiz){
1643   assert(hdb && rec && nsiz > 0);
1644   if(hdb->fbpnum < 1) return false;
1645   uint64_t off = rec->off + rec->rsiz;
1646   uint32_t rsiz = rec->rsiz;
1647   HDBFB *pv = hdb->fbpool;
1648   HDBFB *ep = pv + hdb->fbpnum;
1649   while(pv < ep){
1650     if(pv->off == off && rsiz + pv->rsiz >= nsiz){
1651       if(hdb->iter == pv->off) hdb->iter += pv->rsiz;
1652       rec->rsiz += pv->rsiz;
1653       ep--;
1654       pv->off = ep->off;
1655       pv->rsiz = ep->rsiz;
1656       hdb->fbpnum--;
1657       return true;
1658     }
1659     pv++;
1660   }
1661   return false;
1662 }
1663
1664
1665 /* Write a free block into the file.
1666    `hdb' specifies the hash database object.
1667    `off' specifies the offset of the block.
1668    `rsiz' specifies the size of the block.
1669    The return value is true if successful, else, it is false. */
1670 static bool tchdbwritefb(TCHDB *hdb, uint64_t off, uint32_t rsiz){
1671   assert(hdb && off > 0 && rsiz > 0);
1672   char rbuf[HDBMAXHSIZ];
1673   char *wp = rbuf;
1674   *(uint8_t *)(wp++) = HDBMAGICFB;
1675   uint32_t lnum = TCHTOIL(rsiz);
1676   memcpy(wp, &lnum, sizeof(lnum));
1677   wp += sizeof(lnum);
1678   if(!tcseekwrite(hdb, off, rbuf, wp - rbuf)) return false;
1679   return true;
1680 }
1681
1682
1683 /* Write a record into the file.
1684    `hdb' specifies the hash database object.
1685    `rec' specifies the record object.
1686    `bidx' specifies the index of the bucket.
1687    `entoff' specifies the offset of the tree entry.
1688    The return value is true if successful, else, it is false. */
1689 static bool tchdbwriterec(TCHDB *hdb, TCHREC *rec, uint64_t bidx, off_t entoff){
1690   assert(hdb && rec);
1691   TCDODEBUG(hdb->cnt_writerec++);
1692   uint64_t ofsiz = hdb->fsiz;
1693   char stack[HDBIOBUFSIZ];
1694   int bsiz = rec->rsiz > 0 ? rec->rsiz : HDBMAXHSIZ + rec->ksiz + rec->vsiz + hdb->align;
1695   char *rbuf;
1696   if(bsiz <= HDBIOBUFSIZ){
1697     rbuf = stack;
1698   } else {
1699     TCMALLOC(rbuf, bsiz);
1700   }
1701   char *wp = rbuf;
1702   *(uint8_t *)(wp++) = HDBMAGICREC;
1703   *(uint8_t *)(wp++) = rec->hash;
1704   if(hdb->ba64){
1705     uint64_t llnum;
1706     llnum = rec->left >> hdb->apow;
1707     llnum = TCHTOILL(llnum);
1708     memcpy(wp, &llnum, sizeof(llnum));
1709     wp += sizeof(llnum);
1710     llnum = rec->right >> hdb->apow;
1711     llnum = TCHTOILL(llnum);
1712     memcpy(wp, &llnum, sizeof(llnum));
1713     wp += sizeof(llnum);
1714   } else {
1715     uint32_t lnum;
1716     lnum = rec->left >> hdb->apow;
1717     lnum = TCHTOIL(lnum);
1718     memcpy(wp, &lnum, sizeof(lnum));
1719     wp += sizeof(lnum);
1720     lnum = rec->right >> hdb->apow;
1721     lnum = TCHTOIL(lnum);
1722     memcpy(wp, &lnum, sizeof(lnum));
1723     wp += sizeof(lnum);
1724   }
1725   uint16_t snum;
1726   char *pwp = wp;
1727   wp += sizeof(snum);
1728   int step;
1729   TCSETVNUMBUF(step, wp, rec->ksiz);
1730   wp += step;
1731   TCSETVNUMBUF(step, wp, rec->vsiz);
1732   wp += step;
1733   int32_t hsiz = wp - rbuf;
1734   int32_t rsiz = hsiz + rec->ksiz + rec->vsiz;
1735   if(rec->rsiz < 1){
1736     hdb->fsiz += rsiz;
1737     uint16_t psiz = tchdbpadsize(hdb);
1738     rec->rsiz = rsiz + psiz;
1739     rec->psiz = psiz;
1740     hdb->fsiz += psiz;
1741   } else if(rsiz > rec->rsiz){
1742     if(rbuf != stack) free(rbuf);
1743     if(tchdbfbpsplice(hdb, rec, rsiz)){
1744       TCDODEBUG(hdb->cnt_splicefbp++);
1745       return tchdbwriterec(hdb, rec, bidx, entoff);
1746     }
1747     TCDODEBUG(hdb->cnt_moverec++);
1748     if(!tchdbwritefb(hdb, rec->off, rec->rsiz)) return false;
1749     tchdbfbpinsert(hdb, rec->off, rec->rsiz);
1750     rec->rsiz = rsiz;
1751     if(!tchdbfbpsearch(hdb, rec)) return false;
1752     return tchdbwriterec(hdb, rec, bidx, entoff);
1753   } else {
1754     TCDODEBUG(hdb->cnt_reuserec++);
1755     uint32_t psiz = rec->rsiz - rsiz;
1756     if(psiz > UINT16_MAX){
1757       TCDODEBUG(hdb->cnt_dividefbp++);
1758       uint64_t fsiz = hdb->fsiz;
1759       hdb->fsiz = rec->off + rsiz;
1760       psiz = tchdbpadsize(hdb);
1761       hdb->fsiz = fsiz;
1762       uint64_t noff = rec->off + rsiz + psiz;
1763       uint32_t nsiz = rec->rsiz - rsiz - psiz;
1764       rec->rsiz = noff - rec->off;
1765       rec->psiz = psiz;
1766       if(!tchdbwritefb(hdb, noff, nsiz)) return false;
1767       tchdbfbpinsert(hdb, noff, nsiz);
1768     }
1769     rec->psiz = psiz;
1770   }
1771   snum = rec->psiz;
1772   snum = TCHTOIS(snum);
1773   memcpy(pwp, &snum, sizeof(snum));
1774   rsiz = rec->rsiz;
1775   rsiz -= hsiz;
1776   memcpy(wp, rec->kbuf, rec->ksiz);
1777   wp += rec->ksiz;
1778   rsiz -= rec->ksiz;
1779   memcpy(wp, rec->vbuf, rec->vsiz);
1780   wp += rec->vsiz;
1781   rsiz -= rec->vsiz;
1782   memset(wp, 0, rsiz);
1783   if(!tcseekwrite(hdb, rec->off, rbuf, rec->rsiz)){
1784     if(rbuf != stack) free(rbuf);
1785     hdb->fsiz = ofsiz;
1786     return false;
1787   }
1788   if(hdb->fsiz != ofsiz){
1789     uint64_t llnum = hdb->fsiz;
1790     llnum = TCHTOILL(llnum);
1791     memcpy(hdb->map + HDBFSIZOFF, &llnum, sizeof(llnum));
1792   }
1793   if(rbuf != stack) free(rbuf);
1794   if(entoff > 0){
1795     if(hdb->ba64){
1796       uint64_t llnum = rec->off >> hdb->apow;
1797       llnum = TCHTOILL(llnum);
1798       if(!tcseekwrite(hdb, entoff, &llnum, sizeof(uint64_t))) return false;
1799     } else {
1800       uint32_t lnum = rec->off >> hdb->apow;
1801       lnum = TCHTOIL(lnum);
1802       if(!tcseekwrite(hdb, entoff, &lnum, sizeof(uint32_t))) return false;
1803     }
1804   } else {
1805     tchdbsetbucket(hdb, bidx, rec->off);
1806   }
1807   return true;
1808 }
1809
1810
1811 /* Read a record from the file.
1812    `hdb' specifies the hash database object.
1813    `rec' specifies the record object.
1814    `rbuf' specifies the buffer for reading.
1815    The return value is true if successful, else, it is false. */
1816 static bool tchdbreadrec(TCHDB *hdb, TCHREC *rec, char *rbuf){
1817   assert(hdb && rec && rbuf);
1818   TCDODEBUG(hdb->cnt_readrec++);
1819   off_t rsiz = hdb->fsiz - rec->off;
1820   if(rsiz > hdb->runit){
1821     rsiz = hdb->runit;
1822   } else if(rsiz < (sizeof(uint8_t) + sizeof(uint32_t))){
1823     tchdbsetecode(hdb, TCERHEAD, __FILE__, __LINE__, __func__);
1824     return false;
1825   }
1826   if(!tcseekread(hdb, rec->off, rbuf, rsiz)) return false;
1827   const char *rp = rbuf;
1828   rec->magic = *(uint8_t *)(rp++);
1829   if(rec->magic == HDBMAGICFB){
1830     uint32_t lnum;
1831     memcpy(&lnum, rp, sizeof(lnum));
1832     rec->rsiz = TCITOHL(lnum);
1833     return true;
1834   } else if(rec->magic != HDBMAGICREC){
1835     tchdbsetecode(hdb, TCERHEAD, __FILE__, __LINE__, __func__);
1836     return false;
1837   }
1838   rec->hash = *(uint8_t *)(rp++);
1839   if(hdb->ba64){
1840     uint64_t llnum;
1841     memcpy(&llnum, rp, sizeof(llnum));
1842     rec->left = TCITOHLL(llnum) << hdb->apow;
1843     rp += sizeof(llnum);
1844     memcpy(&llnum, rp, sizeof(llnum));
1845     rec->right = TCITOHLL(llnum) << hdb->apow;
1846     rp += sizeof(llnum);
1847   } else {
1848     uint32_t lnum;
1849     memcpy(&lnum, rp, sizeof(lnum));
1850     rec->left = (uint64_t)TCITOHL(lnum) << hdb->apow;
1851     rp += sizeof(lnum);
1852     memcpy(&lnum, rp, sizeof(lnum));
1853     rec->right = (uint64_t)TCITOHL(lnum) << hdb->apow;
1854     rp += sizeof(lnum);
1855   }
1856   uint16_t snum;
1857   memcpy(&snum, rp, sizeof(snum));
1858   rec->psiz = TCITOHS(snum);
1859   rp += sizeof(snum);
1860   uint32_t lnum;
1861   int step;
1862   TCREADVNUMBUF(rp, lnum, step);
1863   rec->ksiz = lnum;
1864   rp += step;
1865   TCREADVNUMBUF(rp, lnum, step);
1866   rec->vsiz = lnum;
1867   rp += step;
1868   int32_t hsiz = rp - rbuf;
1869   rec->rsiz = hsiz + rec->ksiz + rec->vsiz + rec->psiz;
1870   rec->kbuf = NULL;
1871   rec->vbuf = NULL;
1872   rec->boff = rec->off + hsiz;
1873   rec->bbuf = NULL;
1874   rsiz -= hsiz;
1875   if(rsiz >= rec->ksiz){
1876     rec->kbuf = rp;
1877     rsiz -= rec->ksiz;
1878     rp += rec->ksiz;
1879     if(rsiz >= rec->vsiz) rec->vbuf = rp;
1880   }
1881   return true;
1882 }
1883
1884
1885 /* Read the body of a record from the file.
1886    `hdb' specifies the hash database object.
1887    `rec' specifies the record object.
1888    The return value is true if successful, else, it is false. */
1889 static bool tchdbreadrecbody(TCHDB *hdb, TCHREC *rec){
1890   assert(hdb && rec);
1891   int32_t bsiz = rec->ksiz + rec->vsiz;
1892   TCMALLOC(rec->bbuf, bsiz + 1);
1893   if(!tcseekread(hdb, rec->boff, rec->bbuf, bsiz)) return false;
1894   rec->kbuf = rec->bbuf;
1895   rec->vbuf = rec->bbuf + rec->ksiz;
1896   return true;
1897 }
1898
1899
1900 /* Compare keys of two records.
1901    `abuf' specifies the pointer to the region of the former.
1902    `asiz' specifies the size of the region.
1903    `bbuf' specifies the pointer to the region of the latter.
1904    `bsiz' specifies the size of the region.
1905    The return value is 0 if two equals, positive if the formar is big, else, negative. */
1906 static int tcreckeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz){
1907   assert(abuf && asiz >= 0 && bbuf && bsiz >= 0);
1908   if(asiz > bsiz) return 1;
1909   if(asiz < bsiz) return -1;
1910   return memcmp(abuf, bbuf, asiz);
1911 }
1912
1913
1914 /* Flush the delayed record pool.
1915    `hdb' specifies the hash database object.
1916    The return value is true if successful, else, it is false. */
1917 static bool tchdbflushdrp(TCHDB *hdb){
1918   assert(hdb);
1919   if(!HDBLOCKDRP(hdb)) return false;
1920   if(!hdb->drpool){
1921     HDBUNLOCKDRP(hdb);
1922     return true;
1923   }
1924   TCDODEBUG(hdb->cnt_flushdrp++);
1925   if(!tcseekwrite(hdb, hdb->drpoff, TCXSTRPTR(hdb->drpool), TCXSTRSIZE(hdb->drpool))){
1926     HDBUNLOCKDRP(hdb);
1927     return false;
1928   }
1929   const char *rp = TCXSTRPTR(hdb->drpdef);
1930   int size = TCXSTRSIZE(hdb->drpdef);
1931   while(size > 0){
1932     int ksiz, vsiz;
1933     memcpy(&ksiz, rp, sizeof(int));
1934     rp += sizeof(int);
1935     memcpy(&vsiz, rp, sizeof(int));
1936     rp += sizeof(int);
1937     const char *kbuf = rp;
1938     rp += ksiz;
1939     const char *vbuf = rp;
1940     rp += vsiz;
1941     if(!tchdbputimpl(hdb, kbuf, ksiz, vbuf, vsiz, HDBPDOVER)){
1942       tcxstrdel(hdb->drpdef);
1943       tcxstrdel(hdb->drpool);
1944       hdb->drpool = NULL;
1945       hdb->drpdef = NULL;
1946       hdb->drpoff = 0;
1947       HDBUNLOCKDRP(hdb);
1948       return false;
1949     }
1950     size -= sizeof(int) * 2 + ksiz + vsiz;
1951   }
1952   tcxstrdel(hdb->drpdef);
1953   tcxstrdel(hdb->drpool);
1954   hdb->drpool = NULL;
1955   hdb->drpdef = NULL;
1956   hdb->drpoff = 0;
1957   uint64_t llnum;
1958   llnum = hdb->rnum;
1959   llnum = TCHTOILL(llnum);
1960   memcpy(hdb->map + HDBRNUMOFF, &llnum, sizeof(llnum));
1961   llnum = hdb->fsiz;
1962   llnum = TCHTOILL(llnum);
1963   memcpy(hdb->map + HDBFSIZOFF, &llnum, sizeof(llnum));
1964   HDBUNLOCKDRP(hdb);
1965   return true;
1966 }
1967
1968
1969 /* Adjust the caches for leaves and nodes.
1970    `hdb' specifies the hash tree database object. */
1971 static void tchdbcacheadjust(TCHDB *hdb){
1972   assert(hdb);
1973   TCDODEBUG(hdb->cnt_adjrecc++);
1974   tcmdbcutfront(hdb->recc, HDBCACHEOUT);
1975 }
1976
1977
1978 /* Open a database file and connect a hash database object.
1979    `hdb' specifies the hash database object.
1980    `path' specifies the path of the database file.
1981    `omode' specifies the connection mode.
1982    If successful, the return value is true, else, it is false. */
1983 static bool tchdbopenimpl(TCHDB *hdb, const char *path, int omode){
1984   assert(hdb && path);
1985   int mode = O_RDONLY;
1986   if(omode & HDBOWRITER){
1987     mode = O_RDWR;
1988     if(omode & HDBOCREAT) mode |= O_CREAT;
1989   }
1990   int fd = open(path, mode, HDBFILEMODE);
1991   if(fd < 0){
1992     int ecode = TCEOPEN;
1993     switch(errno){
1994     case EACCES: ecode = TCENOPERM; break;
1995     case ENOENT: ecode = TCENOFILE; break;
1996     }
1997     tchdbsetecode(hdb, ecode, __FILE__, __LINE__, __func__);
1998     return false;
1999   }
2000   if(!(omode & HDBONOLCK)){
2001     if(!tclock(fd, omode & HDBOWRITER, omode & HDBOLCKNB)){
2002       tchdbsetecode(hdb, TCELOCK, __FILE__, __LINE__, __func__);
2003       close(fd);
2004       return false;
2005     }
2006   }
2007   if((omode & HDBOWRITER) && (omode & HDBOTRUNC)){
2008     if(ftruncate(fd, 0) == -1){
2009       tchdbsetecode(hdb, TCETRUNC, __FILE__, __LINE__, __func__);
2010       close(fd);
2011       return false;
2012     }
2013   }
2014   struct stat sbuf;
2015   if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode)){
2016     tchdbsetecode(hdb, TCESTAT, __FILE__, __LINE__, __func__);
2017     close(fd);
2018     return false;
2019   }
2020   char hbuf[HDBHEADSIZ];
2021   if((omode & HDBOWRITER) && sbuf.st_size < 1){
2022     hdb->rnum = 0;
2023     uint32_t fbpmax = 1 << hdb->fpow;
2024     uint32_t fbpsiz = HDBFBPBSIZ + fbpmax * HDBFBPESIZ;
2025     int besiz = (hdb->opts & HDBTLARGE) ? sizeof(int64_t) : sizeof(int32_t);
2026     hdb->align = 1 << hdb->apow;
2027     hdb->fsiz = HDBHEADSIZ + besiz * hdb->bnum + fbpsiz;
2028     uint64_t psiz = tchdbpadsize(hdb);
2029     hdb->fsiz += psiz;
2030     hdb->frec = hdb->fsiz;
2031     tcdumpmeta(hdb, hbuf);
2032     psiz += besiz * hdb->bnum + fbpsiz;
2033     char pbuf[HDBIOBUFSIZ];
2034     memset(pbuf, 0, HDBIOBUFSIZ);
2035     bool err = false;
2036     if(!tcwrite(fd, hbuf, HDBHEADSIZ)) err = true;
2037     while(psiz > 0){
2038       if(psiz > HDBIOBUFSIZ){
2039         if(!tcwrite(fd, pbuf, HDBIOBUFSIZ)) err = true;
2040         psiz -= HDBIOBUFSIZ;
2041       } else {
2042         if(!tcwrite(fd, pbuf, psiz)) err = true;
2043         psiz = 0;
2044       }
2045     }
2046     if(err){
2047       tchdbsetecode(hdb, TCEWRITE, __FILE__, __LINE__, __func__);
2048       close(fd);
2049       return false;
2050     }
2051     sbuf.st_size = hdb->fsiz;
2052   }
2053   if(lseek(fd, 0, SEEK_SET) == -1){
2054     tchdbsetecode(hdb, TCESEEK, __FILE__, __LINE__, __func__);
2055     close(fd);
2056     return false;
2057   }
2058   if(!tcread(fd, hbuf, HDBHEADSIZ)){
2059     tchdbsetecode(hdb, TCEREAD, __FILE__, __LINE__, __func__);
2060     close(fd);
2061     return false;
2062   }
2063   int type = hdb->type;
2064   tcloadmeta(hdb, hbuf);
2065   uint32_t fbpmax = 1 << hdb->fpow;
2066   uint32_t fbpsiz = HDBFBPBSIZ + fbpmax * HDBFBPESIZ;
2067   if(!(omode & HDBONOLCK)){
2068     if(memcmp(hbuf, HDBMAGICDATA, strlen(HDBMAGICDATA)) || hdb->type != type ||
2069        hdb->frec < HDBHEADSIZ + fbpsiz || hdb->frec > hdb->fsiz || sbuf.st_size < hdb->fsiz){
2070       tchdbsetecode(hdb, TCEMETA, __FILE__, __LINE__, __func__);
2071       close(fd);
2072       return false;
2073     }
2074     if(sbuf.st_size > hdb->fsiz) hdb->fsiz = sbuf.st_size;
2075   }
2076   if((hdb->opts & HDBTDEFLATE) && !_tc_deflate){
2077     tchdbsetecode(hdb, TCEINVALID, __FILE__, __LINE__, __func__);
2078     close(fd);
2079     return false;
2080   }
2081   int besiz = (hdb->opts & HDBTLARGE) ? sizeof(int64_t) : sizeof(int32_t);
2082   size_t msiz = HDBHEADSIZ + hdb->bnum * besiz;
2083   void *map = mmap(0, msiz, PROT_READ | ((omode & HDBOWRITER) ? PROT_WRITE : 0),
2084                    MAP_SHARED, fd, 0);
2085   if(map == MAP_FAILED){
2086     tchdbsetecode(hdb, TCEMMAP, __FILE__, __LINE__, __func__);
2087     close(fd);
2088     return false;
2089   }
2090   hdb->fbpmax = fbpmax;
2091   hdb->fbpsiz = fbpsiz;
2092   if(omode & HDBOWRITER){
2093     TCMALLOC(hdb->fbpool, fbpmax * sizeof(HDBFB));
2094   } else {
2095     hdb->fbpool = NULL;
2096   }
2097   hdb->fbpnum = 0;
2098   hdb->fbpmis = 0;
2099   hdb->async = false;
2100   hdb->drpool = NULL;
2101   hdb->drpdef = NULL;
2102   hdb->drpoff = 0;
2103   hdb->recc = (hdb->rcnum > 0) ? tcmdbnew2(hdb->rcnum * 2 + 1) : NULL;
2104   hdb->path = tcstrdup(path);
2105   hdb->omode = omode;
2106   hdb->iter = 0;
2107   hdb->map = map;
2108   hdb->msiz = msiz;
2109   if(hdb->opts & HDBTLARGE){
2110     hdb->ba32 = NULL;
2111     hdb->ba64 = (uint64_t *)((char *)map + HDBHEADSIZ);
2112   } else {
2113     hdb->ba32 = (uint32_t *)((char *)map + HDBHEADSIZ);
2114     hdb->ba64 = NULL;
2115   }
2116   hdb->align = 1 << hdb->apow;
2117   hdb->runit = tclmin(tclmax(hdb->align, HDBMINRUNIT), HDBIOBUFSIZ);
2118   hdb->zmode = (hdb->opts & HDBTDEFLATE) || (hdb->opts & HDBTTCBS);
2119   hdb->ecode = TCESUCCESS;
2120   hdb->fatal = false;
2121   hdb->fd = fd;
2122   if(hdb->omode & HDBOWRITER){
2123     bool err = false;
2124     if(!(hdb->flags & HDBFOPEN) && !tchdbloadfbp(hdb)) err = true;
2125     memset(hbuf, 0, 2);
2126     if(!tcseekwrite(hdb, hdb->msiz, hbuf, 2)) err = true;
2127     if(err){
2128       free(hdb->path);
2129       free(hdb->fbpool);
2130       munmap(hdb->map, hdb->msiz);
2131       close(fd);
2132       hdb->fd = -1;
2133       return false;
2134     }
2135     tchdbsetflag(hdb, HDBFOPEN, true);
2136   }
2137   hdb->inode = (uint64_t)sbuf.st_ino;
2138   hdb->mtime = sbuf.st_mtime;
2139   return true;
2140 }
2141
2142
2143 /* Close a hash database object.
2144    `hdb' specifies the hash database object.
2145    If successful, the return value is true, else, it is false. */
2146 static bool tchdbcloseimpl(TCHDB *hdb){
2147   assert(hdb);
2148   bool err = false;
2149   if(hdb->recc){
2150     tcmdbdel(hdb->recc);
2151     hdb->recc = NULL;
2152   }
2153   if(hdb->omode & HDBOWRITER){
2154     if(!tchdbflushdrp(hdb)) err = true;
2155     if(!tchdbsavefbp(hdb)) err = true;
2156     free(hdb->fbpool);
2157     tchdbsetflag(hdb, HDBFOPEN, false);
2158   }
2159   free(hdb->path);
2160   if((hdb->omode & HDBOWRITER) && !tchdbmemsync(hdb, false)) err = true;
2161   if(munmap(hdb->map, hdb->msiz) == -1){
2162     tchdbsetecode(hdb, TCEMMAP, __FILE__, __LINE__, __func__);
2163     err = true;
2164   }
2165   if(close(hdb->fd) == -1){
2166     tchdbsetecode(hdb, TCECLOSE, __FILE__, __LINE__, __func__);
2167     err = true;
2168   }
2169   hdb->path = NULL;
2170   hdb->fd = -1;
2171   return !err;
2172 }
2173
2174
2175 /* Store a record.
2176    `hdb' specifies the hash database object.
2177    `kbuf' specifies the pointer to the region of the key.
2178    `ksiz' specifies the size of the region of the key.
2179    `vbuf' specifies the pointer to the region of the value.
2180    `vsiz' specifies the size of the region of the value.
2181    `dmode' specifies behavior when the key overlaps.
2182    If successful, the return value is true, else, it is false. */
2183 static bool tchdbputimpl(TCHDB *hdb, const char *kbuf, int ksiz, const char *vbuf, int vsiz,
2184                          int dmode){
2185   assert(hdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
2186   if(hdb->recc) tcmdbout(hdb->recc, kbuf, ksiz);
2187   uint8_t hash;
2188   uint64_t bidx = tchdbbidx(hdb, kbuf, ksiz, &hash);
2189   off_t off = tchdbgetbucket(hdb, bidx);
2190   off_t entoff = 0;
2191   TCHREC rec;
2192   char rbuf[HDBIOBUFSIZ];
2193   while(off > 0){
2194     rec.off = off;
2195     if(!tchdbreadrec(hdb, &rec, rbuf)) return false;
2196     if(hash > rec.hash){
2197       off = rec.left;
2198       entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t));
2199     } else if(hash < rec.hash){
2200       off = rec.right;
2201       entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t)) +
2202         (hdb->ba64 ? sizeof(uint64_t) : sizeof(uint32_t));
2203     } else {
2204       if(!rec.kbuf && !tchdbreadrecbody(hdb, &rec)) return false;
2205       int kcmp = tcreckeycmp(kbuf, ksiz, rec.kbuf, rec.ksiz);
2206       if(kcmp > 0){
2207         off = rec.left;
2208         free(rec.bbuf);
2209         rec.kbuf = NULL;
2210         rec.bbuf = NULL;
2211         entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t));
2212       } else if(kcmp < 0){
2213         off = rec.right;
2214         free(rec.bbuf);
2215         rec.kbuf = NULL;
2216         rec.bbuf = NULL;
2217         entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t)) +
2218           (hdb->ba64 ? sizeof(uint64_t) : sizeof(uint32_t));
2219       } else {
2220         switch(dmode){
2221         case HDBPDKEEP:
2222           free(rec.bbuf);
2223           tchdbsetecode(hdb, TCEKEEP, __FILE__, __LINE__, __func__);
2224           return false;
2225         case HDBPDCAT:
2226           if(vsiz < 1){
2227             free(rec.bbuf);
2228             return true;
2229           }
2230           if(!rec.vbuf && !tchdbreadrecbody(hdb, &rec)) return false;
2231           int nvsiz = rec.vsiz + vsiz;
2232           if(rec.bbuf){
2233             TCREALLOC(rec.bbuf, rec.bbuf, rec.ksiz + nvsiz);
2234             memcpy(rec.bbuf + rec.ksiz + rec.vsiz, vbuf, vsiz);
2235             rec.kbuf = rec.bbuf;
2236             rec.vbuf = rec.kbuf + rec.ksiz;
2237             rec.vsiz = nvsiz;
2238           } else {
2239             TCMALLOC(rec.bbuf, nvsiz);
2240             memcpy(rec.bbuf, rec.vbuf, rec.vsiz);
2241             memcpy(rec.bbuf + rec.vsiz, vbuf, vsiz);
2242             rec.vbuf = rec.bbuf;
2243             rec.vsiz = nvsiz;
2244           }
2245           bool rv = tchdbwriterec(hdb, &rec, bidx, entoff);
2246           free(rec.bbuf);
2247           return rv;
2248         default:
2249           break;
2250         }
2251         free(rec.bbuf);
2252         rec.ksiz = ksiz;
2253         rec.vsiz = vsiz;
2254         rec.kbuf = kbuf;
2255         rec.vbuf = vbuf;
2256         return tchdbwriterec(hdb, &rec, bidx, entoff);
2257       }
2258     }
2259   }
2260   rec.rsiz = HDBMAXHSIZ + ksiz + vsiz;
2261   if(!tchdbfbpsearch(hdb, &rec)) return false;
2262   rec.hash = hash;
2263   rec.left = 0;
2264   rec.right = 0;
2265   rec.ksiz = ksiz;
2266   rec.vsiz = vsiz;
2267   rec.psiz = 0;
2268   rec.kbuf = kbuf;
2269   rec.vbuf = vbuf;
2270   if(!tchdbwriterec(hdb, &rec, bidx, entoff)) return false;
2271   hdb->rnum++;
2272   uint64_t llnum = hdb->rnum;
2273   llnum = TCHTOILL(llnum);
2274   memcpy(hdb->map + HDBRNUMOFF, &llnum, sizeof(llnum));
2275   return true;
2276 }
2277
2278
2279 /* Append a record to the delayed record pool.
2280    `hdb' specifies the hash database object.
2281    `kbuf' specifies the pointer to the region of the key.
2282    `ksiz' specifies the size of the region of the key.
2283    `vbuf' specifies the pointer to the region of the value.
2284    `vsiz' specifies the size of the region of the value.
2285    `hash' specifies the second hash value. */
2286 static void tchdbdrpappend(TCHDB *hdb, const char *kbuf, int ksiz, const char *vbuf, int vsiz,
2287                            uint8_t hash){
2288   assert(hdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
2289   TCDODEBUG(hdb->cnt_appenddrp++);
2290   char rbuf[HDBIOBUFSIZ];
2291   char *wp = rbuf;
2292   *(uint8_t *)(wp++) = HDBMAGICREC;
2293   *(uint8_t *)(wp++) = hash;
2294   if(hdb->ba64){
2295     memset(wp, 0, sizeof(uint64_t) * 2);
2296     wp += sizeof(uint64_t) * 2;
2297   } else {
2298     memset(wp, 0, sizeof(uint32_t) * 2);
2299     wp += sizeof(uint32_t) * 2;
2300   }
2301   uint16_t snum;
2302   char *pwp = wp;
2303   wp += sizeof(snum);
2304   int step;
2305   TCSETVNUMBUF(step, wp, ksiz);
2306   wp += step;
2307   TCSETVNUMBUF(step, wp, vsiz);
2308   wp += step;
2309   int32_t hsiz = wp - rbuf;
2310   int32_t rsiz = hsiz + ksiz + vsiz;
2311   hdb->fsiz += rsiz;
2312   uint16_t psiz = tchdbpadsize(hdb);
2313   hdb->fsiz += psiz;
2314   snum = TCHTOIS(psiz);
2315   memcpy(pwp, &snum, sizeof(snum));
2316   TCXSTR *drpool = hdb->drpool;
2317   TCXSTRCAT(drpool, rbuf, hsiz);
2318   TCXSTRCAT(drpool, kbuf, ksiz);
2319   TCXSTRCAT(drpool, vbuf, vsiz);
2320   if(psiz > 0){
2321     char pbuf[psiz];
2322     memset(pbuf, 0, psiz);
2323     TCXSTRCAT(drpool, pbuf, psiz);
2324   }
2325 }
2326
2327
2328 /* Store a record in asynchronus fashion.
2329    `hdb' specifies the hash database object.
2330    `kbuf' specifies the pointer to the region of the key.
2331    `ksiz' specifies the size of the region of the key.
2332    `vbuf' specifies the pointer to the region of the value.
2333    `vsiz' specifies the size of the region of the value.
2334    If successful, the return value is true, else, it is false. */
2335 static bool tchdbputasyncimpl(TCHDB *hdb, const char *kbuf, int ksiz, const char *vbuf, int vsiz){
2336   assert(hdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
2337   if(hdb->recc) tcmdbout(hdb->recc, kbuf, ksiz);
2338   if(!hdb->drpool){
2339     hdb->drpool = tcxstrnew3(HDBDRPUNIT + HDBDRPLAT);
2340     hdb->drpdef = tcxstrnew3(HDBDRPUNIT);
2341     hdb->drpoff = hdb->fsiz;
2342   }
2343   uint8_t hash;
2344   uint64_t bidx = tchdbbidx(hdb, kbuf, ksiz, &hash);
2345   off_t off = tchdbgetbucket(hdb, bidx);
2346   off_t entoff = 0;
2347   TCHREC rec;
2348   char rbuf[HDBIOBUFSIZ];
2349   while(off > 0){
2350     if(off >= hdb->drpoff - hdb->runit){
2351       TCDODEBUG(hdb->cnt_deferdrp++);
2352       TCXSTR *drpdef = hdb->drpdef;
2353       TCXSTRCAT(drpdef, &ksiz, sizeof(ksiz));
2354       TCXSTRCAT(drpdef, &vsiz, sizeof(vsiz));
2355       TCXSTRCAT(drpdef, kbuf, ksiz);
2356       TCXSTRCAT(drpdef, vbuf, vsiz);
2357       if(TCXSTRSIZE(hdb->drpdef) > HDBDRPUNIT && !tchdbflushdrp(hdb)) return false;
2358       return true;
2359     }
2360     rec.off = off;
2361     if(!tchdbreadrec(hdb, &rec, rbuf)) return false;
2362     if(hash > rec.hash){
2363       off = rec.left;
2364       entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t));
2365     } else if(hash < rec.hash){
2366       off = rec.right;
2367       entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t)) +
2368         (hdb->ba64 ? sizeof(uint64_t) : sizeof(uint32_t));
2369     } else {
2370       TCDODEBUG(hdb->cnt_deferdrp++);
2371       TCXSTR *drpdef = hdb->drpdef;
2372       TCXSTRCAT(drpdef, &ksiz, sizeof(ksiz));
2373       TCXSTRCAT(drpdef, &vsiz, sizeof(vsiz));
2374       TCXSTRCAT(drpdef, kbuf, ksiz);
2375       TCXSTRCAT(drpdef, vbuf, vsiz);
2376       if(TCXSTRSIZE(hdb->drpdef) > HDBDRPUNIT && !tchdbflushdrp(hdb)) return false;
2377       return true;
2378     }
2379   }
2380   if(entoff > 0){
2381     if(hdb->ba64){
2382       uint64_t llnum = hdb->fsiz >> hdb->apow;
2383       llnum = TCHTOILL(llnum);
2384       if(!tcseekwrite(hdb, entoff, &llnum, sizeof(uint64_t))) return false;
2385     } else {
2386       uint32_t lnum = hdb->fsiz >> hdb->apow;
2387       lnum = TCHTOIL(lnum);
2388       if(!tcseekwrite(hdb, entoff, &lnum, sizeof(uint32_t))) return false;
2389     }
2390   } else {
2391     tchdbsetbucket(hdb, bidx, hdb->fsiz);
2392   }
2393   tchdbdrpappend(hdb, kbuf, ksiz, vbuf, vsiz, hash);
2394   hdb->rnum++;
2395   if(TCXSTRSIZE(hdb->drpool) > HDBDRPUNIT && !tchdbflushdrp(hdb)) return false;
2396   return true;
2397 }
2398
2399
2400 /* Remove a record of a hash database object.
2401    `hdb' specifies the hash database object.
2402    `kbuf' specifies the pointer to the region of the key.
2403    `ksiz' specifies the size of the region of the key.
2404    If successful, the return value is true, else, it is false. */
2405 static bool tchdboutimpl(TCHDB *hdb, const char *kbuf, int ksiz){
2406   assert(hdb && kbuf && ksiz >= 0);
2407   if(hdb->recc) tcmdbout(hdb->recc, kbuf, ksiz);
2408   uint8_t hash;
2409   uint64_t bidx = tchdbbidx(hdb, kbuf, ksiz, &hash);
2410   off_t off = tchdbgetbucket(hdb, bidx);
2411   off_t entoff = 0;
2412   TCHREC rec;
2413   char rbuf[HDBIOBUFSIZ];
2414   while(off > 0){
2415     rec.off = off;
2416     if(!tchdbreadrec(hdb, &rec, rbuf)) return false;
2417     if(hash > rec.hash){
2418       off = rec.left;
2419       entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t));
2420     } else if(hash < rec.hash){
2421       off = rec.right;
2422       entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t)) +
2423         (hdb->ba64 ? sizeof(uint64_t) : sizeof(uint32_t));
2424     } else {
2425       if(!rec.kbuf && !tchdbreadrecbody(hdb, &rec)) return false;
2426       int kcmp = tcreckeycmp(kbuf, ksiz, rec.kbuf, rec.ksiz);
2427       if(kcmp > 0){
2428         off = rec.left;
2429         free(rec.bbuf);
2430         rec.kbuf = NULL;
2431         rec.bbuf = NULL;
2432         entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t));
2433       } else if(kcmp < 0){
2434         off = rec.right;
2435         free(rec.bbuf);
2436         rec.kbuf = NULL;
2437         rec.bbuf = NULL;
2438         entoff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t)) +
2439           (hdb->ba64 ? sizeof(uint64_t) : sizeof(uint32_t));
2440       } else {
2441         free(rec.bbuf);
2442         rec.bbuf = NULL;
2443         if(!tchdbwritefb(hdb, rec.off, rec.rsiz)) return false;
2444         tchdbfbpinsert(hdb, rec.off, rec.rsiz);
2445         uint64_t child;
2446         if(rec.left > 0 && rec.right < 1){
2447           child = rec.left;
2448         } else if(rec.left < 1 && rec.right > 0){
2449           child = rec.right;
2450         } else if(rec.left < 1 && rec.left < 1){
2451           child = 0;
2452         } else {
2453           child = rec.left;
2454           uint64_t right = rec.right;
2455           rec.right = child;
2456           while(rec.right > 0){
2457             rec.off = rec.right;
2458             if(!tchdbreadrec(hdb, &rec, rbuf)) return false;
2459           }
2460           if(hdb->ba64){
2461             off_t toff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t) + sizeof(uint64_t));
2462             uint64_t llnum = right >> hdb->apow;
2463             llnum = TCHTOILL(llnum);
2464             if(!tcseekwrite(hdb, toff, &llnum, sizeof(uint64_t))) return false;
2465           } else {
2466             off_t toff = rec.off + (sizeof(uint8_t) + sizeof(uint8_t) + sizeof(uint32_t));
2467             uint32_t lnum = right >> hdb->apow;
2468             lnum = TCHTOIL(lnum);
2469             if(!tcseekwrite(hdb, toff, &lnum, sizeof(uint32_t))) return false;
2470           }
2471         }
2472         if(entoff > 0){
2473           if(hdb->ba64){
2474             uint64_t llnum = child >> hdb->apow;
2475             llnum = TCHTOILL(llnum);
2476             if(!tcseekwrite(hdb, entoff, &llnum, sizeof(uint64_t))) return false;
2477           } else {
2478             uint32_t lnum = child >> hdb->apow;
2479             lnum = TCHTOIL(lnum);
2480             if(!tcseekwrite(hdb, entoff, &lnum, sizeof(uint32_t))) return false;
2481           }
2482         } else {
2483           tchdbsetbucket(hdb, bidx, child);
2484         }
2485         hdb->rnum--;
2486         uint64_t llnum = hdb->rnum;
2487         llnum = TCHTOILL(llnum);
2488         memcpy(hdb->map + HDBRNUMOFF, &llnum, sizeof(llnum));
2489         return true;
2490       }
2491     }
2492   }
2493   tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2494   return false;
2495 }
2496
2497
2498 /* Retrieve a record in a hash database object.
2499    `hdb' specifies the hash database object.
2500    `kbuf' specifies the pointer to the region of the key.
2501    `ksiz' specifies the size of the region of the key.
2502    `sp' specifies the pointer to the variable into which the size of the region of the return
2503    value is assigned.
2504    If successful, the return value is the pointer to the region of the value of the corresponding
2505    record. */
2506 static char *tchdbgetimpl(TCHDB *hdb, const char *kbuf, int ksiz, int *sp){
2507   assert(hdb && kbuf && ksiz >= 0 && sp);
2508   if(hdb->recc){
2509     int tvsiz;
2510     char *tvbuf = tcmdbget(hdb->recc, kbuf, ksiz, &tvsiz);
2511     if(tvbuf){
2512       if(*tvbuf == '*'){
2513         tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2514         free(tvbuf);
2515         return NULL;
2516       }
2517       *sp = tvsiz - 1;
2518       memmove(tvbuf, tvbuf + 1, tvsiz);
2519       return tvbuf;
2520     }
2521   }
2522   uint8_t hash;
2523   uint64_t bidx = tchdbbidx(hdb, kbuf, ksiz, &hash);
2524   off_t off = tchdbgetbucket(hdb, bidx);
2525   TCHREC rec;
2526   char rbuf[HDBIOBUFSIZ];
2527   while(off > 0){
2528     rec.off = off;
2529     if(!tchdbreadrec(hdb, &rec, rbuf)) return NULL;
2530     if(hash > rec.hash){
2531       off = rec.left;
2532     } else if(hash < rec.hash){
2533       off = rec.right;
2534     } else {
2535       if(!rec.kbuf && !tchdbreadrecbody(hdb, &rec)) return NULL;
2536       int kcmp = tcreckeycmp(kbuf, ksiz, rec.kbuf, rec.ksiz);
2537       if(kcmp > 0){
2538         off = rec.left;
2539         free(rec.bbuf);
2540         rec.kbuf = NULL;
2541         rec.bbuf = NULL;
2542       } else if(kcmp < 0){
2543         off = rec.right;
2544         free(rec.bbuf);
2545         rec.kbuf = NULL;
2546         rec.bbuf = NULL;
2547       } else {
2548         if(!rec.vbuf && !tchdbreadrecbody(hdb, &rec)) return NULL;
2549         if(hdb->zmode){
2550           int zsiz;
2551           char *zbuf;
2552           if(hdb->opts & HDBTDEFLATE){
2553             zbuf = _tc_inflate(rec.vbuf, rec.vsiz, &zsiz, _TCZMRAW);
2554           } else {
2555             zbuf = tcbsdecode(rec.vbuf, rec.vsiz, &zsiz);
2556           }
2557           free(rec.bbuf);
2558           if(!zbuf){
2559             tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
2560             return NULL;
2561           }
2562           if(hdb->recc){
2563             if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2564             tcmdbput3(hdb->recc, kbuf, ksiz, "=", 1, zbuf, zsiz);
2565           }
2566           *sp = zsiz;
2567           return zbuf;
2568         }
2569         if(rec.bbuf){
2570           memmove(rec.bbuf, rec.vbuf, rec.vsiz);
2571           rec.bbuf[rec.vsiz] = '\0';
2572           *sp = rec.vsiz;
2573           return rec.bbuf;
2574         }
2575         if(hdb->recc){
2576           if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2577           tcmdbput3(hdb->recc, kbuf, ksiz, "=", 1, rec.vbuf, rec.vsiz);
2578         }
2579         *sp = rec.vsiz;
2580         char *rv;
2581         TCMEMDUP(rv, rec.vbuf, rec.vsiz);
2582         return rv;
2583       }
2584     }
2585   }
2586   if(hdb->recc){
2587     if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2588     tcmdbput(hdb->recc, kbuf, ksiz, "*", 1);
2589   }
2590   tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2591   return NULL;
2592 }
2593
2594
2595 /* Retrieve a record in a hash database object and write the value into a buffer.
2596    `hdb' specifies the hash database object.
2597    `kbuf' specifies the pointer to the region of the key.
2598    `ksiz' specifies the size of the region of the key.
2599    `vbuf' specifies the pointer to the buffer into which the value of the corresponding record is
2600    written.
2601    `max' specifies the size of the buffer.
2602    If successful, the return value is the size of the written data, else, it is -1. */
2603 static int tchdbgetintobuf(TCHDB *hdb, const char *kbuf, int ksiz, char *vbuf, int max){
2604   assert(hdb && kbuf && ksiz >= 0 && vbuf && max >= 0);
2605   if(hdb->recc){
2606     int tvsiz;
2607     char *tvbuf = tcmdbget(hdb->recc, kbuf, ksiz, &tvsiz);
2608     if(tvbuf){
2609       if(*tvbuf == '*'){
2610         tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2611         free(tvbuf);
2612         return -1;
2613       }
2614       tvsiz = tclmin(tvsiz - 1, max);
2615       memcpy(vbuf, tvbuf + 1, tvsiz);
2616       free(tvbuf);
2617       return tvsiz;
2618     }
2619   }
2620   uint8_t hash;
2621   uint64_t bidx = tchdbbidx(hdb, kbuf, ksiz, &hash);
2622   off_t off = tchdbgetbucket(hdb, bidx);
2623   TCHREC rec;
2624   char rbuf[HDBIOBUFSIZ];
2625   while(off > 0){
2626     rec.off = off;
2627     if(!tchdbreadrec(hdb, &rec, rbuf)) return -1;
2628     if(hash > rec.hash){
2629       off = rec.left;
2630     } else if(hash < rec.hash){
2631       off = rec.right;
2632     } else {
2633       if(!rec.kbuf && !tchdbreadrecbody(hdb, &rec)) return -1;
2634       int kcmp = tcreckeycmp(kbuf, ksiz, rec.kbuf, rec.ksiz);
2635       if(kcmp > 0){
2636         off = rec.left;
2637         free(rec.bbuf);
2638         rec.kbuf = NULL;
2639         rec.bbuf = NULL;
2640       } else if(kcmp < 0){
2641         off = rec.right;
2642         free(rec.bbuf);
2643         rec.kbuf = NULL;
2644         rec.bbuf = NULL;
2645       } else {
2646         if(!rec.vbuf && !tchdbreadrecbody(hdb, &rec)) return -1;
2647         if(hdb->zmode){
2648           int zsiz;
2649           char *zbuf;
2650           if(hdb->opts & HDBTDEFLATE){
2651             zbuf = _tc_inflate(rec.vbuf, rec.vsiz, &zsiz, _TCZMRAW);
2652           } else {
2653             zbuf = tcbsdecode(rec.vbuf, rec.vsiz, &zsiz);
2654           }
2655           free(rec.bbuf);
2656           if(!zbuf){
2657             tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
2658             return -1;
2659           }
2660           if(hdb->recc){
2661             if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2662             tcmdbput3(hdb->recc, kbuf, ksiz, "=", 1, zbuf, zsiz);
2663           }
2664           zsiz = tclmin(zsiz, max);
2665           memcpy(vbuf, zbuf, zsiz);
2666           free(zbuf);
2667           return zsiz;
2668         }
2669         if(hdb->recc){
2670           if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2671           tcmdbput3(hdb->recc, kbuf, ksiz, "=", 1, rec.vbuf, rec.vsiz);
2672         }
2673         int vsiz = tclmin(rec.vsiz, max);
2674         memcpy(vbuf, rec.vbuf, vsiz);
2675         free(rec.bbuf);
2676         return vsiz;
2677       }
2678     }
2679   }
2680   if(hdb->recc){
2681     if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2682     tcmdbput(hdb->recc, kbuf, ksiz, "*", 1);
2683   }
2684   tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2685   return -1;
2686 }
2687
2688
2689 /* Get the size of the value of a record in a hash database object.
2690    `hdb' specifies the hash database object.
2691    `kbuf' specifies the pointer to the region of the key.
2692    `ksiz' specifies the size of the region of the key.
2693    If successful, the return value is the size of the value of the corresponding record, else,
2694    it is -1. */
2695 static int tchdbvsizimpl(TCHDB *hdb, const char *kbuf, int ksiz){
2696   assert(hdb && kbuf && ksiz >= 0);
2697   if(hdb->recc){
2698     int tvsiz;
2699     char *tvbuf = tcmdbget(hdb->recc, kbuf, ksiz, &tvsiz);
2700     if(tvbuf){
2701       if(*tvbuf == '*'){
2702         tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2703         free(tvbuf);
2704         return -1;
2705       }
2706       free(tvbuf);
2707       return tvsiz - 1;
2708     }
2709   }
2710   uint8_t hash;
2711   uint64_t bidx = tchdbbidx(hdb, kbuf, ksiz, &hash);
2712   off_t off = tchdbgetbucket(hdb, bidx);
2713   TCHREC rec;
2714   char rbuf[HDBIOBUFSIZ];
2715   while(off > 0){
2716     rec.off = off;
2717     if(!tchdbreadrec(hdb, &rec, rbuf)) return -1;
2718     if(hash > rec.hash){
2719       off = rec.left;
2720     } else if(hash < rec.hash){
2721       off = rec.right;
2722     } else {
2723       if(!rec.kbuf && !tchdbreadrecbody(hdb, &rec)) return -1;
2724       int kcmp = tcreckeycmp(kbuf, ksiz, rec.kbuf, rec.ksiz);
2725       if(kcmp > 0){
2726         off = rec.left;
2727         free(rec.bbuf);
2728         rec.kbuf = NULL;
2729         rec.bbuf = NULL;
2730       } else if(kcmp < 0){
2731         off = rec.right;
2732         free(rec.bbuf);
2733         rec.kbuf = NULL;
2734         rec.bbuf = NULL;
2735       } else {
2736         if(hdb->zmode){
2737           if(!rec.vbuf && !tchdbreadrecbody(hdb, &rec)) return -1;
2738           int zsiz;
2739           char *zbuf;
2740           if(hdb->opts & HDBTDEFLATE){
2741             zbuf = _tc_inflate(rec.vbuf, rec.vsiz, &zsiz, _TCZMRAW);
2742           } else {
2743             zbuf = tcbsdecode(rec.vbuf, rec.vsiz, &zsiz);
2744           }
2745           free(rec.bbuf);
2746           if(!zbuf){
2747             tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
2748             return -1;
2749           }
2750           if(hdb->recc){
2751             if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2752             tcmdbput3(hdb->recc, kbuf, ksiz, "=", 1, zbuf, zsiz);
2753           }
2754           free(zbuf);
2755           return zsiz;
2756         }
2757         if(hdb->recc && rec.vbuf){
2758           if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2759           tcmdbput3(hdb->recc, kbuf, ksiz, "=", 1, rec.vbuf, rec.vsiz);
2760         }
2761         free(rec.bbuf);
2762         return rec.vsiz;
2763       }
2764     }
2765   }
2766   if(hdb->recc){
2767     if(tcmdbrnum(hdb->recc) >= hdb->rcnum) tchdbcacheadjust(hdb);
2768     tcmdbput(hdb->recc, kbuf, ksiz, "*", 1);
2769   }
2770   tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2771   return -1;
2772 }
2773
2774
2775 /* Initialize the iterator of a hash database object.
2776    `hdb' specifies the hash database object.
2777    If successful, the return value is true, else, it is false. */
2778 static bool tchdbiterinitimpl(TCHDB *hdb){
2779   assert(hdb);
2780   hdb->iter = hdb->frec;
2781   return true;
2782 }
2783
2784
2785 /* Get the next key of the iterator of a hash database object.
2786    `hdb' specifies the hash database object.
2787    `sp' specifies the pointer to the variable into which the size of the region of the return
2788    value is assigned.
2789    If successful, the return value is the pointer to the region of the next key, else, it is
2790    `NULL'. */
2791 static char *tchdbiternextimpl(TCHDB *hdb, int *sp){
2792   assert(hdb && sp);
2793   TCHREC rec;
2794   char rbuf[HDBIOBUFSIZ];
2795   while(hdb->iter < hdb->fsiz){
2796     rec.off = hdb->iter;
2797     if(!tchdbreadrec(hdb, &rec, rbuf)) return NULL;
2798     hdb->iter += rec.rsiz;
2799     if(rec.magic == HDBMAGICREC){
2800       if(rec.kbuf){
2801         *sp = rec.ksiz;
2802         char *rv;
2803         TCMEMDUP(rv, rec.kbuf, rec.ksiz);
2804         return rv;
2805       }
2806       if(!tchdbreadrecbody(hdb, &rec)) return NULL;
2807       rec.bbuf[rec.ksiz] = '\0';
2808       *sp = rec.ksiz;
2809       return rec.bbuf;
2810     }
2811   }
2812   tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2813   return NULL;
2814 }
2815
2816
2817 /* Get the next extensible objects of the iterator of a hash database object. */
2818 static bool tchdbiternextintoxstr(TCHDB *hdb, TCXSTR *kxstr, TCXSTR *vxstr){
2819   assert(hdb && kxstr && vxstr);
2820   TCHREC rec;
2821   char rbuf[HDBIOBUFSIZ];
2822   while(hdb->iter < hdb->fsiz){
2823     rec.off = hdb->iter;
2824     if(!tchdbreadrec(hdb, &rec, rbuf)) return false;
2825     hdb->iter += rec.rsiz;
2826     if(rec.magic == HDBMAGICREC){
2827       if(!rec.vbuf && !tchdbreadrecbody(hdb, &rec)) return false;
2828       tcxstrclear(kxstr);
2829       TCXSTRCAT(kxstr, rec.kbuf, rec.ksiz);
2830       tcxstrclear(vxstr);
2831       if(hdb->zmode){
2832         int zsiz;
2833         char *zbuf;
2834         if(hdb->opts & HDBTDEFLATE){
2835           zbuf = _tc_inflate(rec.vbuf, rec.vsiz, &zsiz, _TCZMRAW);
2836         } else {
2837           zbuf = tcbsdecode(rec.vbuf, rec.vsiz, &zsiz);
2838         }
2839         if(!zbuf){
2840           tchdbsetecode(hdb, TCEMISC, __FILE__, __LINE__, __func__);
2841           free(rec.bbuf);
2842           return false;
2843         }
2844         TCXSTRCAT(vxstr, zbuf, zsiz);
2845         free(zbuf);
2846       } else {
2847         TCXSTRCAT(vxstr, rec.vbuf, rec.vsiz);
2848       }
2849       free(rec.bbuf);
2850       return true;
2851     }
2852   }
2853   tchdbsetecode(hdb, TCENOREC, __FILE__, __LINE__, __func__);
2854   return false;
2855 }
2856
2857
2858 /* Optimize the file of a hash database object.
2859    `hdb' specifies the hash database object.
2860    `bnum' specifies the number of elements of the bucket array.
2861    `apow' specifies the size of record alignment by power of 2.
2862    `fpow' specifies the maximum number of elements of the free block pool by power of 2.
2863    `opts' specifies options by bitwise or.
2864    If successful, the return value is true, else, it is false. */
2865 static bool tchdboptimizeimpl(TCHDB *hdb, int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts){
2866   assert(hdb);
2867   if(bnum < 1){
2868     bnum = hdb->rnum * 2 + 1;
2869     if(bnum < HDBDEFBNUM) bnum = HDBDEFBNUM;
2870   }
2871   if(apow < 0) apow = hdb->apow;
2872   if(fpow < 0) fpow = hdb->fpow;
2873   if(opts == UINT8_MAX) opts = hdb->opts;
2874   char *tpath = tcsprintf("%s%ctmp%c%llu", hdb->path, MYEXTCHR, MYEXTCHR, hdb->inode);
2875   TCHDB *thdb = tchdbnew();
2876   tchdbtune(thdb, bnum, apow, fpow, opts);
2877   if(!tchdbopen(thdb, tpath, HDBOWRITER | HDBOCREAT | HDBOTRUNC)){
2878     tchdbsetecode(hdb, thdb->ecode, __FILE__, __LINE__, __func__);
2879     tchdbdel(thdb);
2880     free(tpath);
2881     return false;
2882   }
2883   bool err = false;
2884   if(!tchdbiterinitimpl(hdb)) err = true;
2885   TCXSTR *key = tcxstrnew();
2886   TCXSTR *val = tcxstrnew();
2887   while(!err && tchdbiternextintoxstr(hdb, key, val)){
2888     if(!tchdbputkeep(thdb, TCXSTRPTR(key), TCXSTRSIZE(key), TCXSTRPTR(val), TCXSTRSIZE(val))){
2889       tchdbsetecode(hdb, thdb->ecode, __FILE__, __LINE__, __func__);
2890       err = true;
2891     }
2892   }
2893   tcxstrdel(val);
2894   tcxstrdel(key);
2895   if(!tchdbclose(thdb)){
2896     tchdbsetecode(hdb, thdb->ecode, __FILE__, __LINE__, __func__);
2897     err = true;
2898   }
2899   tchdbdel(thdb);
2900   if(unlink(hdb->path) == -1){
2901     tchdbsetecode(hdb, TCEUNLINK, __FILE__, __LINE__, __func__);
2902     err = true;
2903   }
2904   if(rename(tpath, hdb->path) == -1){
2905     tchdbsetecode(hdb, TCERENAME, __FILE__, __LINE__, __func__);
2906     err = true;
2907   }
2908   free(tpath);
2909   if(err) return false;
2910   tpath = tcstrdup(hdb->path);
2911   int omode = (hdb->omode & ~HDBOCREAT) & ~HDBOTRUNC;
2912   if(!tchdbcloseimpl(hdb)){
2913     free(tpath);
2914     return false;
2915   }
2916   bool rv = tchdbopenimpl(hdb, tpath, omode);
2917   free(tpath);
2918   return rv;
2919 }
2920
2921
2922 /* Remove all records of a hash database object.
2923    `hdb' specifies the hash database object.
2924    If successful, the return value is true, else, it is false. */
2925 static bool tchdbvanishimpl(TCHDB *hdb){
2926   assert(hdb);
2927   char *path = tcstrdup(hdb->path);
2928   int omode = hdb->omode;
2929   bool err = false;
2930   if(!tchdbcloseimpl(hdb)) err = true;
2931   if(!tchdbopenimpl(hdb, path, HDBOTRUNC | omode)) err = true;
2932   free(path);
2933   return !err;
2934 }
2935
2936
2937 /* Lock a method of the hash database object.
2938    `hdb' specifies the hash database object.
2939    `wr' specifies whether the lock is writer or not.
2940    If successful, the return value is true, else, it is false. */
2941 static bool tchdblockmethod(TCHDB *hdb, bool wr){
2942   assert(hdb);
2943   if(wr ? pthread_rwlock_wrlock(hdb->mmtx) != 0 : pthread_rwlock_rdlock(hdb->mmtx) != 0){
2944     tchdbsetecode(hdb, TCETHREAD, __FILE__, __LINE__, __func__);
2945     return false;
2946   }
2947   TCTESTYIELD();
2948   return true;
2949 }
2950
2951
2952 /* Unlock a method of the hash database object.
2953    `hdb' specifies the hash database object.
2954    If successful, the return value is true, else, it is false. */
2955 static bool tchdbunlockmethod(TCHDB *hdb){
2956   assert(hdb);
2957   if(pthread_rwlock_unlock(hdb->mmtx) != 0){
2958     tchdbsetecode(hdb, TCETHREAD, __FILE__, __LINE__, __func__);
2959     return false;
2960   }
2961   TCTESTYIELD();
2962   return true;
2963 }
2964
2965
2966 /* Lock the delayed record pool of the hash database object.
2967    `hdb' specifies the hash database object.
2968    If successful, the return value is true, else, it is false. */
2969 static bool tchdblockdrp(TCHDB *hdb){
2970   assert(hdb);
2971   if(pthread_mutex_lock(hdb->dmtx) != 0){
2972     tchdbsetecode(hdb, TCETHREAD, __FILE__, __LINE__, __func__);
2973     return false;
2974   }
2975   TCTESTYIELD();
2976   return true;
2977 }
2978
2979
2980 /* Unlock the delayed record pool of the hash database object.
2981    `hdb' specifies the hash database object.
2982    If successful, the return value is true, else, it is false. */
2983 static bool tchdbunlockdrp(TCHDB *hdb){
2984   assert(hdb);
2985   if(pthread_mutex_unlock(hdb->dmtx) != 0){
2986     tchdbsetecode(hdb, TCETHREAD, __FILE__, __LINE__, __func__);
2987     return false;
2988   }
2989   TCTESTYIELD();
2990   return true;
2991 }
2992
2993
2994
2995 /*************************************************************************************************
2996  * debugging functions
2997  *************************************************************************************************/
2998
2999
3000 /* Print meta data of the header into the debugging output.
3001    `hdb' specifies the hash database object. */
3002 void tchdbprintmeta(TCHDB *hdb){
3003   assert(hdb);
3004   if(hdb->dbgfd < 0) return;
3005   char buf[HDBIOBUFSIZ];
3006   char *wp = buf;
3007   wp += sprintf(wp, "META:");
3008   wp += sprintf(wp, " mmtx=%p", (void *)hdb->mmtx);
3009   wp += sprintf(wp, " dmtx=%p", (void *)hdb->dmtx);
3010   wp += sprintf(wp, " eckey=%p", (void *)hdb->eckey);
3011   wp += sprintf(wp, " type=%02X", hdb->type);
3012   wp += sprintf(wp, " flags=%02X", hdb->flags);
3013   wp += sprintf(wp, " bnum=%llu", (unsigned long long)hdb->bnum);
3014   wp += sprintf(wp, " apow=%u", hdb->apow);
3015   wp += sprintf(wp, " fpow=%u", hdb->fpow);
3016   wp += sprintf(wp, " opts=%u", hdb->opts);
3017   wp += sprintf(wp, " path=%s", hdb->path ? hdb->path : "-");
3018   wp += sprintf(wp, " fd=%u", hdb->fd);
3019   wp += sprintf(wp, " omode=%u", hdb->omode);
3020   wp += sprintf(wp, " rnum=%llu", (unsigned long long)hdb->rnum);
3021   wp += sprintf(wp, " fsiz=%llu", (unsigned long long)hdb->fsiz);
3022   wp += sprintf(wp, " frec=%llu", (unsigned long long)hdb->frec);
3023   wp += sprintf(wp, " iter=%llu", (unsigned long long)hdb->iter);
3024   wp += sprintf(wp, " map=%p", (void *)hdb->map);
3025   wp += sprintf(wp, " msiz=%llu", (unsigned long long)hdb->msiz);
3026   wp += sprintf(wp, " ba32=%p", (void *)hdb->ba32);
3027   wp += sprintf(wp, " ba64=%p", (void *)hdb->ba64);
3028   wp += sprintf(wp, " align=%u", hdb->align);
3029   wp += sprintf(wp, " runit=%u", hdb->runit);
3030   wp += sprintf(wp, " zmode=%u", hdb->zmode);
3031   wp += sprintf(wp, " fbpmax=%d", hdb->fbpmax);
3032   wp += sprintf(wp, " fbpsiz=%d", hdb->fbpsiz);
3033   wp += sprintf(wp, " fbpool=%p", (void *)hdb->fbpool);
3034   wp += sprintf(wp, " fbpnum=%d", hdb->fbpnum);
3035   wp += sprintf(wp, " fbpmis=%d", hdb->fbpmis);
3036   wp += sprintf(wp, " drpool=%p", (void *)hdb->drpool);
3037   wp += sprintf(wp, " drpdef=%p", (void *)hdb->drpdef);
3038   wp += sprintf(wp, " drpoff=%llu", (unsigned long long)hdb->drpoff);
3039   wp += sprintf(wp, " recc=%p", (void *)hdb->recc);
3040   wp += sprintf(wp, " rcnum=%u", hdb->rcnum);
3041   wp += sprintf(wp, " ecode=%d", hdb->ecode);
3042   wp += sprintf(wp, " fatal=%u", hdb->fatal);
3043   wp += sprintf(wp, " inode=%llu", (unsigned long long)(uint64_t)hdb->inode);
3044   wp += sprintf(wp, " mtime=%llu", (unsigned long long)(uint64_t)hdb->mtime);
3045   wp += sprintf(wp, " dbgfd=%d", hdb->dbgfd);
3046   wp += sprintf(wp, " cnt_writerec=%lld", (long long)hdb->cnt_writerec);
3047   wp += sprintf(wp, " cnt_reuserec=%lld", (long long)hdb->cnt_reuserec);
3048   wp += sprintf(wp, " cnt_moverec=%lld", (long long)hdb->cnt_moverec);
3049   wp += sprintf(wp, " cnt_readrec=%lld", (long long)hdb->cnt_readrec);
3050   wp += sprintf(wp, " cnt_searchfbp=%lld", (long long)hdb->cnt_searchfbp);
3051   wp += sprintf(wp, " cnt_insertfbp=%lld", (long long)hdb->cnt_insertfbp);
3052   wp += sprintf(wp, " cnt_splicefbp=%lld", (long long)hdb->cnt_splicefbp);
3053   wp += sprintf(wp, " cnt_dividefbp=%lld", (long long)hdb->cnt_dividefbp);
3054   wp += sprintf(wp, " cnt_mergefbp=%lld", (long long)hdb->cnt_mergefbp);
3055   wp += sprintf(wp, " cnt_reducefbp=%lld", (long long)hdb->cnt_reducefbp);
3056   wp += sprintf(wp, " cnt_appenddrp=%lld", (long long)hdb->cnt_appenddrp);
3057   wp += sprintf(wp, " cnt_deferdrp=%lld", (long long)hdb->cnt_deferdrp);
3058   wp += sprintf(wp, " cnt_flushdrp=%lld", (long long)hdb->cnt_flushdrp);
3059   wp += sprintf(wp, " cnt_adjrecc=%lld", (long long)hdb->cnt_adjrecc);
3060   *(wp++) = '\n';
3061   tcwrite(hdb->dbgfd, buf, wp - buf);
3062 }
3063
3064
3065 /* Print a record information into the debugging output.
3066    `hdb' specifies the hash database object.
3067    `rec' specifies the record. */
3068 void tchdbprintrec(TCHDB *hdb, TCHREC *rec){
3069   assert(hdb && rec);
3070   if(hdb->dbgfd < 0) return;
3071   char buf[HDBIOBUFSIZ];
3072   char *wp = buf;
3073   wp += sprintf(wp, "REC:");
3074   wp += sprintf(wp, " off=%llu", (unsigned long long)rec->off);
3075   wp += sprintf(wp, " rsiz=%u", rec->rsiz);
3076   wp += sprintf(wp, " magic=%02X", rec->magic);
3077   wp += sprintf(wp, " hash=%02X", rec->hash);
3078   wp += sprintf(wp, " left=%llu", (unsigned long long)rec->left);
3079   wp += sprintf(wp, " right=%llu", (unsigned long long)rec->right);
3080   wp += sprintf(wp, " ksiz=%u", rec->ksiz);
3081   wp += sprintf(wp, " vsiz=%u", rec->vsiz);
3082   wp += sprintf(wp, " psiz=%u", rec->psiz);
3083   wp += sprintf(wp, " kbuf=%p", (void *)rec->kbuf);
3084   wp += sprintf(wp, " vbuf=%p", (void *)rec->vbuf);
3085   wp += sprintf(wp, " boff=%llu", (unsigned long long)rec->boff);
3086   wp += sprintf(wp, " bbuf=%p", (void *)rec->bbuf);
3087   *(wp++) = '\n';
3088   tcwrite(hdb->dbgfd, buf, wp - buf);
3089 }
3090
3091
3092
3093 // END OF FILE