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

   1 /*************************************************************************************************
   2  * The B+ tree 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 "tcbdb.h"
  20 #include "myconf.h"
  21
  22 #define BDBFILEMODE    00644             // permission of created files
  23 #define BDBOPAQUESIZ   64                // size of using opaque field
  24 #define BDBPAGEBUFSIZ  32768             // size of a buffer to read each page
  25 #define BDBNODEIDBASE   ((1LL<<48)+1)    // base number of node ID
  26 #define BDBLEVELMAX    64                // max level of B+ tree
  27 #define BDBCACHEOUT    8                 // number of pages in a process of cacheout
  28
  29 #define BDBDEFLMEMB    128               // default number of members in each leaf
  30 #define BDBMINLMEMB    4                 // minimum number of members in each leaf
  31 #define BDBDEFNMEMB    256               // default number of members in each node
  32 #define BDBMINNMEMB    4                 // minimum number of members in each node
  33 #define BDBDEFBNUM     16381             // default bucket number
  34 #define BDBDEFAPOW     8                 // default alignment power
  35 #define BDBDEFFPOW     10                // default free block pool power
  36 #define BDBDEFLCNUM    1024              // default number of leaf cache
  37 #define BDBDEFNCNUM    512               // default number of node cache
  38
  39 typedef struct {                         // type of structure for a record
  40   char *kbuf;                            // pointer to the key region
  41   int ksiz;                              // size of the key region
  42   char *vbuf;                            // pointer to the value region
  43   int vsiz;                              // size of the value region
  44   TCLIST *rest;                          // list of value objects
  45 } BDBREC;
  46
  47 typedef struct {                         // type of structure for a leaf page
  48   uint64_t id;                           // ID number of the leaf
  49   TCLIST *recs;                          // list of records
  50   uint64_t prev;                         // ID number of the previous leaf
  51   uint64_t next;                         // ID number of the next leaf
  52   bool dirty;                            // whether to be written back
  53   bool dead;                             // whether to be removed
  54 } BDBLEAF;
  55
  56 typedef struct {                         // type of structure for a page index
  57   uint64_t pid;                          // ID number of the referring page
  58   char *kbuf;                            // pointer to the key region
  59   int ksiz;                              // size of the key region
  60 } BDBIDX;
  61
  62 typedef struct {                         // type of structure for a node page
  63   uint64_t id;                           // ID number of the node
  64   uint64_t heir;                         // ID of the child before the first index
  65   TCLIST *idxs;                          // list of indexes
  66   bool dirty;                            // whether to be written back
  67 } BDBNODE;
  68
  69 enum {                                   // enumeration for duplication behavior
  70   BDBPDOVER,                             // overwrite an existing value
  71   BDBPDKEEP,                             // keep the existing value
  72   BDBPDCAT,                              // concatenate values
  73   BDBPDDUP,                              // allow duplication of keys
  74   BDBPDDUPB,                             // allow backward duplication
  75 };
  76
  77
  78 /* private macros */
  79 #define BDBLOCKMETHOD(TC_bdb, TC_wr) \
  80   ((TC_bdb)->mmtx ? tcbdblockmethod((TC_bdb), (TC_wr)) : true)
  81 #define BDBUNLOCKMETHOD(TC_bdb) \
  82   ((TC_bdb)->mmtx ? tcbdbunlockmethod(TC_bdb) : true)
  83 #define BDBLOCKCACHE(TC_bdb) \
  84   ((TC_bdb)->mmtx ? tcbdblockcache(TC_bdb) : true)
  85 #define BDBUNLOCKCACHE(TC_bdb) \
  86   ((TC_bdb)->mmtx ? tcbdbunlockcache(TC_bdb) : true)
  87 #define BDBLOCKTRAN(TC_bdb) \
  88   ((TC_bdb)->mmtx ? tcbdblocktran(TC_bdb) : true)
  89 #define BDBUNLOCKTRAN(TC_bdb) \
  90   ((TC_bdb)->mmtx ? tcbdbunlocktran(TC_bdb) : true)
  91
  92
  93 /* private function prototypes */
  94 static void tcbdbclear(TCBDB *bdb);
  95 static void tcdumpmeta(TCBDB *bdb);
  96 static void tcloadmeta(TCBDB *bdb);
  97 static BDBLEAF *tcbdbleafnew(TCBDB *bdb, uint64_t prev, uint64_t next);
  98 static bool tcbdbleafcacheout(TCBDB *bdb, BDBLEAF *leaf);
  99 static bool tcbdbleafsave(TCBDB *bdb, BDBLEAF *leaf);
 100 static BDBLEAF *tcbdbleafload(TCBDB *bdb, uint64_t id);
 101 static BDBLEAF *tcbdbgethistleaf(TCBDB *bdb, const char *kbuf, int ksiz);
 102 static bool tcbdbleafaddrec(TCBDB *bdb, BDBLEAF *leaf, int dmode,
 103                             const char *kbuf, int ksiz, const char *vbuf, int vsiz);
 104 static int tcbdbleafdatasize(BDBLEAF *leaf);
 105 static BDBLEAF *tcbdbleafdivide(TCBDB *bdb, BDBLEAF *leaf);
 106 static bool tcbdbleafkill(TCBDB *bdb, BDBLEAF *leaf);
 107 static BDBNODE *tcbdbnodenew(TCBDB *bdb, uint64_t heir);
 108 static bool tcbdbnodecacheout(TCBDB *bdb, BDBNODE *node);
 109 static bool tcbdbnodesave(TCBDB *bdb, BDBNODE *node);
 110 static BDBNODE *tcbdbnodeload(TCBDB *bdb, uint64_t id);
 111 static void tcbdbnodeaddidx(TCBDB *bdb, BDBNODE *node, bool order, uint64_t pid,
 112                             const char *kbuf, int ksiz);
 113 static bool tcbdbnodesubidx(TCBDB *bdb, BDBNODE *node, uint64_t pid);
 114 static uint64_t tcbdbsearchleaf(TCBDB *bdb, const char *kbuf, int ksiz);
 115 static BDBREC *tcbdbsearchrec(TCBDB *bdb, BDBLEAF *leaf, const char *kbuf, int ksiz, int *ip);
 116 static bool tcbdbcacheadjust(TCBDB *bdb);
 117 static void tcbdbcachepurge(TCBDB *bdb);
 118 static bool tcbdbopenimpl(TCBDB *bdb, const char *path, int omode);
 119 static bool tcbdbcloseimpl(TCBDB *bdb);
 120 static bool tcbdbputimpl(TCBDB *bdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz,
 121                          int dmode);
 122 static bool tcbdboutimpl(TCBDB *bdb, const char *kbuf, int ksiz);
 123 static bool tcbdboutlist(TCBDB *bdb, const char *kbuf, int ksiz);
 124 static const char *tcbdbgetimpl(TCBDB *bdb, const char *kbuf, int ksiz, int *sp);
 125 static int tcbdbgetnum(TCBDB *bdb, const char *kbuf, int ksiz);
 126 static TCLIST *tcbdbgetlist(TCBDB *bdb, const char *kbuf, int ksiz);
 127 static bool tcbdbrangeimpl(TCBDB *bdb, const char *bkbuf, int bksiz, bool binc,
 128                            const char *ekbuf, int eksiz, bool einc, int max, TCLIST *keys);
 129 static bool tcbdbrangefwm(TCBDB *bdb, const char *pbuf, int psiz, int max, TCLIST *keys);
 130 static bool tcbdboptimizeimpl(TCBDB *bdb, int32_t lmemb, int32_t nmemb,
 131                               int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts);
 132 static bool tcbdbvanishimpl(TCBDB *bdb);
 133 static bool tcbdblockmethod(TCBDB *bdb, bool wr);
 134 static bool tcbdbunlockmethod(TCBDB *bdb);
 135 static bool tcbdblockcache(TCBDB *bdb);
 136 static bool tcbdbunlockcache(TCBDB *bdb);
 137 static bool tcbdblocktran(TCBDB *bdb);
 138 static bool tcbdbunlocktran(TCBDB *bdb);
 139 static bool tcbdbcurfirstimpl(BDBCUR *cur);
 140 static bool tcbdbcurlastimpl(BDBCUR *cur);
 141 static bool tcbdbcurjumpimpl(BDBCUR *cur, const char *kbuf, int ksiz, bool forward);
 142 static bool tcbdbcuradjust(BDBCUR *cur, bool forward);
 143 static bool tcbdbcurprevimpl(BDBCUR *cur);
 144 static bool tcbdbcurnextimpl(BDBCUR *cur);
 145 static bool tcbdbcurputimpl(BDBCUR *cur, const char *vbuf, int vsiz, int mode);
 146 static bool tcbdbcuroutimpl(BDBCUR *cur);
 147 static bool tcbdbcurrecimpl(BDBCUR *cur, const char **kbp, int *ksp, const char **vbp, int *vsp);
 148
 149
 150 /* debugging function prototypes */
 151 void tcbdbprintmeta(TCBDB *bdb);
 152 void tcbdbprintleaf(TCBDB *bdb, BDBLEAF *leaf);
 153 void tcbdbprintnode(TCBDB *bdb, BDBNODE *node);
 154
 155
 156
 157 /*************************************************************************************************
 158  * API
 159  *************************************************************************************************/
 160
 161
 162 /* Get the message string corresponding to an error code. */
 163 const char *tcbdberrmsg(int ecode){
 164   return tchdberrmsg(ecode);
 165 }
 166
 167
 168 /* Create a B+ tree database object. */
 169 TCBDB *tcbdbnew(void){
 170   TCBDB *bdb;
 171   TCMALLOC(bdb, sizeof(*bdb));
 172   tcbdbclear(bdb);
 173   bdb->hdb = tchdbnew();
 174   TCMALLOC(bdb->hist, sizeof(*bdb->hist) * BDBLEVELMAX);
 175   return bdb;
 176 }
 177
 178
 179 /* Delete a B+ tree database object. */
 180 void tcbdbdel(TCBDB *bdb){
 181   assert(bdb);
 182   if(bdb->open) tcbdbclose(bdb);
 183   free(bdb->hist);
 184   tchdbdel(bdb->hdb);
 185   if(bdb->mmtx){
 186     pthread_mutex_destroy(bdb->tmtx);
 187     pthread_mutex_destroy(bdb->cmtx);
 188     pthread_rwlock_destroy(bdb->mmtx);
 189     free(bdb->tmtx);
 190     free(bdb->cmtx);
 191     free(bdb->mmtx);
 192   }
 193   free(bdb);
 194 }
 195
 196
 197 /* Get the last happened error code of a B+ tree database object. */
 198 int tcbdbecode(TCBDB *bdb){
 199   assert(bdb);
 200   return tchdbecode(bdb->hdb);
 201 }
 202
 203
 204 /* Set mutual exclusion control of a B+ tree database object for threading. */
 205 bool tcbdbsetmutex(TCBDB *bdb){
 206   assert(bdb);
 207   if(!TCUSEPTHREAD) return true;
 208   if(!tcglobalmutexlock()) return false;
 209   if(bdb->mmtx || bdb->open){
 210     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 211     tcglobalmutexunlock();
 212     return false;
 213   }
 214   TCMALLOC(bdb->mmtx, sizeof(pthread_rwlock_t));
 215   TCMALLOC(bdb->cmtx, sizeof(pthread_mutex_t));
 216   TCMALLOC(bdb->tmtx, sizeof(pthread_mutex_t));
 217   if(pthread_rwlock_init(bdb->mmtx, NULL) != 0 || pthread_mutex_init(bdb->cmtx, NULL) != 0 ||
 218      pthread_mutex_init(bdb->tmtx, NULL) != 0){
 219     free(bdb->tmtx);
 220     free(bdb->cmtx);
 221     free(bdb->mmtx);
 222     bdb->tmtx = NULL;
 223     bdb->cmtx = NULL;
 224     bdb->mmtx = NULL;
 225     tcglobalmutexunlock();
 226     return false;
 227   }
 228   tcglobalmutexunlock();
 229   return tchdbsetmutex(bdb->hdb);
 230 }
 231
 232
 233 /* Set the custom comparison function of a B+ tree database object. */
 234 bool tcbdbsetcmpfunc(TCBDB *bdb, BDBCMP cmp, void *cmpop){
 235   assert(bdb && cmp);
 236   if(bdb->open){
 237     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 238     return false;
 239   }
 240   bdb->cmp = cmp;
 241   bdb->cmpop = cmpop;
 242   return true;
 243 }
 244
 245
 246 /* Set the tuning parameters of a B+ tree database object. */
 247 bool tcbdbtune(TCBDB *bdb, int32_t lmemb, int32_t nmemb,
 248                int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts){
 249   assert(bdb);
 250   if(bdb->open){
 251     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 252     return false;
 253   }
 254   bdb->lmemb = (lmemb > 0) ? tclmax(lmemb, BDBMINLMEMB) : BDBDEFLMEMB;
 255   bdb->nmemb = (nmemb > 0) ? tclmax(nmemb, BDBMINNMEMB) : BDBDEFNMEMB;
 256   bdb->opts = opts;
 257   uint8_t hopts = 0;
 258   if(opts & BDBTLARGE) hopts |= HDBTLARGE;
 259   if(opts & BDBTDEFLATE) hopts |= HDBTDEFLATE;
 260   if(opts & BDBTTCBS) hopts |= HDBTTCBS;
 261   bnum = (bnum > 0) ? bnum : BDBDEFBNUM;
 262   apow = (apow >= 0) ? apow : BDBDEFAPOW;
 263   fpow = (fpow >= 0) ? fpow : BDBDEFFPOW;
 264   return tchdbtune(bdb->hdb, bnum, apow, fpow, hopts);
 265 }
 266
 267
 268 /* Set the caching parameters of a B+ tree database object. */
 269 bool tcbdbsetcache(TCBDB *bdb, int32_t lcnum, int32_t ncnum){
 270   assert(bdb);
 271   if(bdb->open){
 272     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 273     return false;
 274   }
 275   if(lcnum > 0) bdb->lcnum = tclmax(lcnum, BDBLEVELMAX);
 276   if(ncnum > 0) bdb->ncnum = tclmax(ncnum, BDBLEVELMAX);
 277   return true;
 278 }
 279
 280
 281 /* Open a database file and connect a B+ tree database object. */
 282 bool tcbdbopen(TCBDB *bdb, const char *path, int omode){
 283   assert(bdb && path);
 284   if(!BDBLOCKMETHOD(bdb, true)) return false;
 285   if(bdb->open){
 286     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 287     BDBUNLOCKMETHOD(bdb);
 288     return false;
 289   }
 290   bool rv = tcbdbopenimpl(bdb, path, omode);
 291   BDBUNLOCKMETHOD(bdb);
 292   return rv;
 293 }
 294
 295
 296 /* Close a B+ tree database object. */
 297 bool tcbdbclose(TCBDB *bdb){
 298   assert(bdb);
 299   if(!BDBLOCKMETHOD(bdb, true)) return false;
 300   if(!bdb->open){
 301     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 302     BDBUNLOCKMETHOD(bdb);
 303     return false;
 304   }
 305   bool rv = tcbdbcloseimpl(bdb);
 306   BDBUNLOCKMETHOD(bdb);
 307   return rv;
 308 }
 309
 310
 311 /* Store a record into a B+ tree database object. */
 312 bool tcbdbput(TCBDB *bdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 313   assert(bdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 314   if(!BDBLOCKMETHOD(bdb, true)) return false;
 315   if(!bdb->open || !bdb->wmode){
 316     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 317     BDBUNLOCKMETHOD(bdb);
 318     return false;
 319   }
 320   bool rv = tcbdbputimpl(bdb, kbuf, ksiz, vbuf, vsiz, BDBPDOVER);
 321   BDBUNLOCKMETHOD(bdb);
 322   return rv;
 323 }
 324
 325
 326 /* Store a string record into a B+ tree database object. */
 327 bool tcbdbput2(TCBDB *bdb, const char *kstr, const char *vstr){
 328   assert(bdb && kstr && vstr);
 329   return tcbdbput(bdb, kstr, strlen(kstr), vstr, strlen(vstr));
 330 }
 331
 332
 333 /* Store a new record into a B+ tree database object. */
 334 bool tcbdbputkeep(TCBDB *bdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 335   assert(bdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 336   if(!BDBLOCKMETHOD(bdb, true)) return false;
 337   if(!bdb->open || !bdb->wmode){
 338     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 339     BDBUNLOCKMETHOD(bdb);
 340     return false;
 341   }
 342   bool rv = tcbdbputimpl(bdb, kbuf, ksiz, vbuf, vsiz, BDBPDKEEP);
 343   BDBUNLOCKMETHOD(bdb);
 344   return rv;
 345 }
 346
 347
 348 /* Store a new string record into a B+ tree database object. */
 349 bool tcbdbputkeep2(TCBDB *bdb, const char *kstr, const char *vstr){
 350   assert(bdb && kstr && vstr);
 351   return tcbdbputkeep(bdb, kstr, strlen(kstr), vstr, strlen(vstr));
 352 }
 353
 354
 355 /* Concatenate a value at the end of the existing record in a B+ tree database object. */
 356 bool tcbdbputcat(TCBDB *bdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 357   assert(bdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 358   if(!BDBLOCKMETHOD(bdb, true)) return false;
 359   if(!bdb->open || !bdb->wmode){
 360     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 361     BDBUNLOCKMETHOD(bdb);
 362     return false;
 363   }
 364   bool rv = tcbdbputimpl(bdb, kbuf, ksiz, vbuf, vsiz, BDBPDCAT);
 365   BDBUNLOCKMETHOD(bdb);
 366   return rv;
 367 }
 368
 369
 370 /* Concatenate a string value at the end of the existing record in a B+ tree database object. */
 371 bool tcbdbputcat2(TCBDB *bdb, const char *kstr, const char *vstr){
 372   assert(bdb && kstr && vstr);
 373   return tcbdbputcat(bdb, kstr, strlen(kstr), vstr, strlen(vstr));
 374 }
 375
 376
 377 /* Store a record into a B+ tree database object with allowing duplication of keys. */
 378 bool tcbdbputdup(TCBDB *bdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
 379   assert(bdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
 380   if(!BDBLOCKMETHOD(bdb, true)) return false;
 381   if(!bdb->open || !bdb->wmode){
 382     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 383     BDBUNLOCKMETHOD(bdb);
 384     return false;
 385   }
 386   bool rv = tcbdbputimpl(bdb, kbuf, ksiz, vbuf, vsiz, BDBPDDUP);
 387   BDBUNLOCKMETHOD(bdb);
 388   return rv;
 389 }
 390
 391
 392 /* Store a string record into a B+ tree database object with allowing duplication of keys. */
 393 bool tcbdbputdup2(TCBDB *bdb, const char *kstr, const char *vstr){
 394   assert(bdb && kstr && vstr);
 395   return tcbdbputdup(bdb, kstr, strlen(kstr), vstr, strlen(vstr));
 396 }
 397
 398
 399 /* Store records into a B+ tree database object with allowing duplication of keys. */
 400 bool tcbdbputdup3(TCBDB *bdb, const void *kbuf, int ksiz, const TCLIST *vals){
 401   assert(bdb && kbuf && ksiz >= 0 && vals);
 402   if(!BDBLOCKMETHOD(bdb, true)) return false;
 403   if(!bdb->open || !bdb->wmode){
 404     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 405     BDBUNLOCKMETHOD(bdb);
 406     return false;
 407   }
 408   bool err = false;
 409   int ln = TCLISTNUM(vals);
 410   for(int i = 0; i < ln; i++){
 411     int vsiz;
 412     const char *vbuf = tclistval(vals, i, &vsiz);
 413     if(!tcbdbputimpl(bdb, kbuf, ksiz, vbuf, vsiz, BDBPDDUP)) err = true;
 414   }
 415   BDBUNLOCKMETHOD(bdb);
 416   return !err;
 417 }
 418
 419
 420 /* Remove a record of a B+ tree database object. */
 421 bool tcbdbout(TCBDB *bdb, const void *kbuf, int ksiz){
 422   assert(bdb && kbuf && ksiz >= 0);
 423   if(!BDBLOCKMETHOD(bdb, true)) return false;
 424   if(!bdb->open || !bdb->wmode){
 425     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 426     BDBUNLOCKMETHOD(bdb);
 427     return false;
 428   }
 429   bool rv = tcbdboutimpl(bdb, kbuf, ksiz);
 430   BDBUNLOCKMETHOD(bdb);
 431   return rv;
 432 }
 433
 434
 435 /* Remove a string record of a B+ tree database object. */
 436 bool tcbdbout2(TCBDB *bdb, const char *kstr){
 437   assert(bdb && kstr);
 438   return tcbdbout(bdb, kstr, strlen(kstr));
 439 }
 440
 441
 442 /* Remove records of a B+ tree database object. */
 443 bool tcbdbout3(TCBDB *bdb, const void *kbuf, int ksiz){
 444   assert(bdb && kbuf && ksiz >= 0);
 445   if(!BDBLOCKMETHOD(bdb, true)) return false;
 446   if(!bdb->open || !bdb->wmode){
 447     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 448     BDBUNLOCKMETHOD(bdb);
 449     return false;
 450   }
 451   bool rv = tcbdboutlist(bdb, kbuf, ksiz);
 452   BDBUNLOCKMETHOD(bdb);
 453   return rv;
 454 }
 455
 456
 457 /* Retrieve a record in a B+ tree database object. */
 458 void *tcbdbget(TCBDB *bdb, const void *kbuf, int ksiz, int *sp){
 459   assert(bdb && kbuf && ksiz >= 0 && sp);
 460   if(!BDBLOCKMETHOD(bdb, false)) return NULL;
 461   if(!bdb->open){
 462     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 463     BDBUNLOCKMETHOD(bdb);
 464     return NULL;
 465   }
 466   const char *vbuf = tcbdbgetimpl(bdb, kbuf, ksiz, sp);
 467   char *rv;
 468   if(vbuf){
 469     TCMEMDUP(rv, vbuf, *sp);
 470   } else {
 471     rv = NULL;
 472   }
 473   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 474   BDBUNLOCKMETHOD(bdb);
 475   if(adj && BDBLOCKMETHOD(bdb, true)){
 476     if(!bdb->tran && !tcbdbcacheadjust(bdb)){
 477       free(rv);
 478       rv = NULL;
 479     }
 480     BDBUNLOCKMETHOD(bdb);
 481   }
 482   return rv;
 483 }
 484
 485
 486 /* Retrieve a string record in a B+ tree database object. */
 487 char *tcbdbget2(TCBDB *bdb, const char *kstr){
 488   assert(bdb && kstr);
 489   int vsiz;
 490   return tcbdbget(bdb, kstr, strlen(kstr), &vsiz);
 491 }
 492
 493
 494 /* Retrieve a record in a B+ tree database object and write the value into a buffer. */
 495 const void *tcbdbget3(TCBDB *bdb, const void *kbuf, int ksiz, int *sp){
 496   assert(bdb && kbuf && ksiz >= 0 && sp);
 497   if(!BDBLOCKMETHOD(bdb, false)) return NULL;
 498   if(!bdb->open){
 499     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 500     BDBUNLOCKMETHOD(bdb);
 501     return NULL;
 502   }
 503   const char *rv = tcbdbgetimpl(bdb, kbuf, ksiz, sp);
 504   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 505   BDBUNLOCKMETHOD(bdb);
 506   if(adj && BDBLOCKMETHOD(bdb, true)){
 507     if(!bdb->tran && !tcbdbcacheadjust(bdb)) rv = NULL;
 508     BDBUNLOCKMETHOD(bdb);
 509   }
 510   return rv;
 511 }
 512
 513
 514 /* Retrieve records in a B+ tree database object. */
 515 TCLIST *tcbdbget4(TCBDB *bdb, const void *kbuf, int ksiz){
 516   assert(bdb && kbuf && ksiz >= 0);
 517   if(!BDBLOCKMETHOD(bdb, false)) return NULL;
 518   if(!bdb->open){
 519     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 520     BDBUNLOCKMETHOD(bdb);
 521     return NULL;
 522   }
 523   TCLIST *rv = tcbdbgetlist(bdb, kbuf, ksiz);
 524   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 525   BDBUNLOCKMETHOD(bdb);
 526   if(adj && BDBLOCKMETHOD(bdb, true)){
 527     if(!bdb->tran && !tcbdbcacheadjust(bdb)){
 528       if(rv) tclistdel(rv);
 529       rv = NULL;
 530     }
 531     BDBUNLOCKMETHOD(bdb);
 532   }
 533   return rv;
 534 }
 535
 536
 537 /* Get the number of records corresponding a key in a B+ tree database object. */
 538 int tcbdbvnum(TCBDB *bdb, const void *kbuf, int ksiz){
 539   assert(bdb && kbuf && ksiz >= 0);
 540   if(!BDBLOCKMETHOD(bdb, false)) return 0;
 541   if(!bdb->open){
 542     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 543     BDBUNLOCKMETHOD(bdb);
 544     return 0;
 545   }
 546   int rv = tcbdbgetnum(bdb, kbuf, ksiz);
 547   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 548   BDBUNLOCKMETHOD(bdb);
 549   if(adj && BDBLOCKMETHOD(bdb, true)){
 550     if(!bdb->tran && !tcbdbcacheadjust(bdb)) rv = 0;
 551     BDBUNLOCKMETHOD(bdb);
 552   }
 553   return rv;
 554 }
 555
 556
 557 /* Get the number of records corresponding a string key in a B+ tree database object. */
 558 int tcbdbvnum2(TCBDB *bdb, const char *kstr){
 559   assert(bdb && kstr);
 560   return tcbdbvnum(bdb, kstr, strlen(kstr));
 561 }
 562
 563
 564 /* Get the size of the value of a record in a B+ tree database object. */
 565 int tcbdbvsiz(TCBDB *bdb, const void *kbuf, int ksiz){
 566   assert(bdb && kbuf && ksiz >= 0);
 567   int vsiz;
 568   if(!tcbdbget3(bdb, kbuf, ksiz, &vsiz)) return -1;
 569   return vsiz;
 570 }
 571
 572
 573 /* Get the size of the value of a string record in a B+ tree database object. */
 574 int tcbdbvsiz2(TCBDB *bdb, const char *kstr){
 575   assert(bdb && kstr);
 576   return tcbdbvsiz(bdb, kstr, strlen(kstr));
 577 }
 578
 579
 580 /* Get keys of ranged records in a B+ tree database object. */
 581 TCLIST *tcbdbrange(TCBDB *bdb, const void *bkbuf, int bksiz, bool binc,
 582                    const void *ekbuf, int eksiz, bool einc, int max){
 583   assert(bdb);
 584   TCLIST *keys = tclistnew();
 585   if(!BDBLOCKMETHOD(bdb, false)) return keys;
 586   if(!bdb->open){
 587     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 588     BDBUNLOCKMETHOD(bdb);
 589     return keys;
 590   }
 591   tcbdbrangeimpl(bdb, bkbuf, bksiz, binc, ekbuf, eksiz, einc, max, keys);
 592   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 593   BDBUNLOCKMETHOD(bdb);
 594   if(adj && BDBLOCKMETHOD(bdb, true)){
 595     tcbdbcacheadjust(bdb);
 596     BDBUNLOCKMETHOD(bdb);
 597   }
 598   return keys;
 599 }
 600
 601
 602 /* Get string keys of ranged records in a B+ tree database object. */
 603 TCLIST *tcbdbrange2(TCBDB *bdb, const char *bkstr, bool binc,
 604                     const char *ekstr, bool einc, int max){
 605   return tcbdbrange(bdb, bkstr, bkstr ? strlen(bkstr) : 0, binc,
 606                     ekstr, ekstr ? strlen(ekstr) : 0, einc, max);
 607 }
 608
 609
 610 /* Get forward matching keys in a B+ tree database object. */
 611 TCLIST *tcbdbfwmkeys(TCBDB *bdb, const void *pbuf, int psiz, int max){
 612   assert(bdb && pbuf && psiz >= 0);
 613   TCLIST *keys = tclistnew();
 614   if(!BDBLOCKMETHOD(bdb, false)) return keys;
 615   if(!bdb->open){
 616     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 617     BDBUNLOCKMETHOD(bdb);
 618     return keys;
 619   }
 620   tcbdbrangefwm(bdb, pbuf, psiz, max, keys);
 621   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 622   BDBUNLOCKMETHOD(bdb);
 623   if(adj && BDBLOCKMETHOD(bdb, true)){
 624     tcbdbcacheadjust(bdb);
 625     BDBUNLOCKMETHOD(bdb);
 626   }
 627   return keys;
 628 }
 629
 630
 631 /* Get forward matching string keys in a B+ tree database object. */
 632 TCLIST *tcbdbfwmkeys2(TCBDB *bdb, const char *pstr, int max){
 633   assert(bdb && pstr);
 634   return tcbdbfwmkeys(bdb, pstr, strlen(pstr), max);
 635 }
 636
 637
 638
 639 /* Synchronize updated contents of a B+ tree database object with the file and the device. */
 640 bool tcbdbsync(TCBDB *bdb){
 641   assert(bdb);
 642   if(!BDBLOCKMETHOD(bdb, true)) return false;
 643   if(!bdb->open || !bdb->wmode || bdb->tran){
 644     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 645     BDBUNLOCKMETHOD(bdb);
 646     return false;
 647   }
 648   bool rv = tcbdbmemsync(bdb, true);
 649   BDBUNLOCKMETHOD(bdb);
 650   return rv;
 651 }
 652
 653
 654 /* Optimize the file of a B+ tree database object. */
 655 bool tcbdboptimize(TCBDB *bdb, int32_t lmemb, int32_t nmemb,
 656                    int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts){
 657   assert(bdb);
 658   if(!BDBLOCKMETHOD(bdb, true)) return false;
 659   if(!bdb->open || !bdb->wmode || bdb->tran){
 660     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 661     BDBUNLOCKMETHOD(bdb);
 662     return false;
 663   }
 664   bool rv = tcbdboptimizeimpl(bdb, lmemb, nmemb, bnum, apow, fpow, opts);
 665   BDBUNLOCKMETHOD(bdb);
 666   return rv;
 667 }
 668
 669
 670 /* Remove all records of a B+ tree database object. */
 671 bool tcbdbvanish(TCBDB *bdb){
 672   assert(bdb);
 673   if(!BDBLOCKMETHOD(bdb, true)) return false;
 674   if(!bdb->open || !bdb->wmode || bdb->tran){
 675     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 676     BDBUNLOCKMETHOD(bdb);
 677     return false;
 678   }
 679   bool rv = tcbdbvanishimpl(bdb);
 680   BDBUNLOCKMETHOD(bdb);
 681   return rv;
 682 }
 683
 684
 685 /* Copy the database file of a B+ tree database object. */
 686 bool tcbdbcopy(TCBDB *bdb, const char *path){
 687   assert(bdb && path);
 688   if(!BDBLOCKMETHOD(bdb, true)) return false;
 689   if(!bdb->open){
 690     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 691     BDBUNLOCKMETHOD(bdb);
 692     return false;
 693   }
 694   TCLIST *lids = tclistnew();
 695   TCLIST *nids = tclistnew();
 696   const char *vbuf;
 697   int vsiz;
 698   TCMAP *leafc = bdb->leafc;
 699   tcmapiterinit(leafc);
 700   while((vbuf = tcmapiternext(leafc, &vsiz)) != NULL){
 701     tclistpush(lids, vbuf, vsiz);
 702   }
 703   TCMAP *nodec = bdb->nodec;
 704   tcmapiterinit(nodec);
 705   while((vbuf = tcmapiternext(nodec, &vsiz)) != NULL){
 706     tclistpush(nids, vbuf, vsiz);
 707   }
 708   BDBUNLOCKMETHOD(bdb);
 709   bool err = false;
 710   int ln = TCLISTNUM(lids);
 711   for(int i = 0; i < ln; i++){
 712     vbuf = TCLISTVALPTR(lids, i);
 713     if(BDBLOCKMETHOD(bdb, true)){
 714       if(bdb->open){
 715         int rsiz;
 716         BDBLEAF *leaf = (BDBLEAF *)tcmapget(bdb->leafc, vbuf, sizeof(leaf->id), &rsiz);
 717         if(leaf && leaf->dirty && !tcbdbleafsave(bdb, leaf)) err = true;
 718       } else {
 719         err = true;
 720       }
 721       BDBUNLOCKMETHOD(bdb);
 722     } else {
 723       err = true;
 724     }
 725   }
 726   ln = TCLISTNUM(nids);
 727   for(int i = 0; i < ln; i++){
 728     vbuf = TCLISTVALPTR(nids, i);
 729     if(BDBLOCKMETHOD(bdb, true)){
 730       if(bdb->open){
 731         int rsiz;
 732         BDBNODE *node = (BDBNODE *)tcmapget(bdb->nodec, vbuf, sizeof(node->id), &rsiz);
 733         if(node && node->dirty && !tcbdbnodesave(bdb, node)) err = true;
 734       } else {
 735         err = true;
 736       }
 737       BDBUNLOCKMETHOD(bdb);
 738     } else {
 739       err = true;
 740     }
 741   }
 742   tclistdel(nids);
 743   tclistdel(lids);
 744   if(!tcbdbtranbegin(bdb)) err = true;
 745   if(BDBLOCKMETHOD(bdb, false)){
 746     if(!tchdbcopy(bdb->hdb, path)) err = true;
 747     BDBUNLOCKMETHOD(bdb);
 748   } else {
 749     err = true;
 750   }
 751   if(!tcbdbtrancommit(bdb)) err = true;
 752   return !err;
 753 }
 754
 755
 756 /* Begin the transaction of a B+ tree database object. */
 757 bool tcbdbtranbegin(TCBDB *bdb){
 758   assert(bdb);
 759   if(!BDBLOCKMETHOD(bdb, true)) return false;
 760   if(!bdb->open || !bdb->wmode || bdb->tran){
 761     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 762     BDBUNLOCKMETHOD(bdb);
 763     return false;
 764   }
 765   if(!tcbdbmemsync(bdb, false)){
 766     BDBUNLOCKMETHOD(bdb);
 767     return false;
 768   }
 769   if(!BDBLOCKTRAN(bdb)){
 770     BDBUNLOCKMETHOD(bdb);
 771     return false;
 772   }
 773   bdb->tran = true;
 774   TCMEMDUP(bdb->rbopaque, bdb->opaque, BDBOPAQUESIZ);
 775   BDBUNLOCKMETHOD(bdb);
 776   return true;
 777 }
 778
 779
 780 /* Commit the transaction of a B+ tree database object. */
 781 bool tcbdbtrancommit(TCBDB *bdb){
 782   assert(bdb);
 783   if(!BDBLOCKMETHOD(bdb, true)) return false;
 784   if(!bdb->open || !bdb->wmode || !bdb->tran){
 785     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 786     BDBUNLOCKMETHOD(bdb);
 787     return false;
 788   }
 789   free(bdb->rbopaque);
 790   bdb->tran = false;
 791   bdb->rbopaque = NULL;
 792   bool err = false;
 793   if(!tcbdbmemsync(bdb, false)) err = true;
 794   BDBUNLOCKTRAN(bdb);
 795   BDBUNLOCKMETHOD(bdb);
 796   return !err;
 797 }
 798
 799
 800 /* Abort the transaction of a B+ tree database object. */
 801 bool tcbdbtranabort(TCBDB *bdb){
 802   assert(bdb);
 803   if(!BDBLOCKMETHOD(bdb, true)) return false;
 804   if(!bdb->open || !bdb->wmode || !bdb->tran){
 805     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 806     BDBUNLOCKMETHOD(bdb);
 807     return false;
 808   }
 809   tcbdbcachepurge(bdb);
 810   memcpy(bdb->opaque, bdb->rbopaque, BDBOPAQUESIZ);
 811   tcloadmeta(bdb);
 812   free(bdb->rbopaque);
 813   bdb->tran = false;
 814   bdb->rbopaque = NULL;
 815   BDBUNLOCKTRAN(bdb);
 816   BDBUNLOCKMETHOD(bdb);
 817   return true;
 818 }
 819
 820
 821 /* Get the file path of a B+ tree database object. */
 822 const char *tcbdbpath(TCBDB *bdb){
 823   assert(bdb);
 824   if(!BDBLOCKMETHOD(bdb, false)) return NULL;
 825   if(!bdb->open){
 826     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 827     BDBUNLOCKMETHOD(bdb);
 828     return NULL;
 829   }
 830   const char *rv = tchdbpath(bdb->hdb);
 831   BDBUNLOCKMETHOD(bdb);
 832   return rv;
 833 }
 834
 835
 836 /* Get the number of records of a B+ tree database object. */
 837 uint64_t tcbdbrnum(TCBDB *bdb){
 838   assert(bdb);
 839   if(!BDBLOCKMETHOD(bdb, false)) return 0;
 840   if(!bdb->open){
 841     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 842     BDBUNLOCKMETHOD(bdb);
 843     return 0;
 844   }
 845   uint64_t rv = bdb->rnum;
 846   BDBUNLOCKMETHOD(bdb);
 847   return rv;
 848 }
 849
 850
 851 /* Get the size of the database file of a B+ tree database object. */
 852 uint64_t tcbdbfsiz(TCBDB *bdb){
 853   assert(bdb);
 854   if(!BDBLOCKMETHOD(bdb, false)) return 0;
 855   if(!bdb->open){
 856     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 857     BDBUNLOCKMETHOD(bdb);
 858     return 0;
 859   }
 860   uint64_t rv = tchdbfsiz(bdb->hdb);
 861   BDBUNLOCKMETHOD(bdb);
 862   return rv;
 863 }
 864
 865
 866 /* Create a cursor object. */
 867 BDBCUR *tcbdbcurnew(TCBDB *bdb){
 868   assert(bdb);
 869   BDBCUR *cur;
 870   TCMALLOC(cur, sizeof(*cur));
 871   cur->bdb = bdb;
 872   cur->id = 0;
 873   cur->kidx = 0;
 874   cur->vidx = 0;
 875   return cur;
 876 }
 877
 878
 879 /* Delete a cursor object. */
 880 void tcbdbcurdel(BDBCUR *cur){
 881   assert(cur);
 882   free(cur);
 883 }
 884
 885
 886 /* Move a cursor object to the first record. */
 887 bool tcbdbcurfirst(BDBCUR *cur){
 888   assert(cur);
 889   TCBDB *bdb = cur->bdb;
 890   if(!BDBLOCKMETHOD(bdb, false)) return false;
 891   if(!bdb->open){
 892     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 893     BDBUNLOCKMETHOD(bdb);
 894     return false;
 895   }
 896   bool rv = tcbdbcurfirstimpl(cur);
 897   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 898   BDBUNLOCKMETHOD(bdb);
 899   if(adj && BDBLOCKMETHOD(bdb, true)){
 900     if(!bdb->tran && !tcbdbcacheadjust(bdb)) rv = false;
 901     BDBUNLOCKMETHOD(bdb);
 902   }
 903   return rv;
 904 }
 905
 906
 907 /* Move a cursor object to the last record. */
 908 bool tcbdbcurlast(BDBCUR *cur){
 909   assert(cur);
 910   TCBDB *bdb = cur->bdb;
 911   if(!BDBLOCKMETHOD(bdb, false)) return false;
 912   if(!bdb->open){
 913     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 914     BDBUNLOCKMETHOD(bdb);
 915     return false;
 916   }
 917   bool rv = tcbdbcurlastimpl(cur);
 918   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 919   BDBUNLOCKMETHOD(bdb);
 920   if(adj && BDBLOCKMETHOD(bdb, true)){
 921     if(!bdb->tran && !tcbdbcacheadjust(bdb)) rv = false;
 922     BDBUNLOCKMETHOD(bdb);
 923   }
 924   return rv;
 925 }
 926
 927
 928 /* Move a cursor object to the front of records corresponding a key. */
 929 bool tcbdbcurjump(BDBCUR *cur, const void *kbuf, int ksiz){
 930   assert(cur && kbuf && ksiz >= 0);
 931   TCBDB *bdb = cur->bdb;
 932   if(!BDBLOCKMETHOD(bdb, false)) return false;
 933   if(!bdb->open){
 934     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 935     BDBUNLOCKMETHOD(bdb);
 936     return false;
 937   }
 938   bool rv = tcbdbcurjumpimpl(cur, kbuf, ksiz, true);
 939   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 940   BDBUNLOCKMETHOD(bdb);
 941   if(adj && BDBLOCKMETHOD(bdb, true)){
 942     if(!bdb->tran && !tcbdbcacheadjust(bdb)) rv = false;
 943     BDBUNLOCKMETHOD(bdb);
 944   }
 945   return rv;
 946 }
 947
 948
 949 /* Move a cursor object to the front of records corresponding a key string. */
 950 bool tcbdbcurjump2(BDBCUR *cur, const char *kstr){
 951   assert(cur && kstr);
 952   return tcbdbcurjump(cur, kstr, strlen(kstr));
 953 }
 954
 955
 956 /* Move a cursor object to the previous record. */
 957 bool tcbdbcurprev(BDBCUR *cur){
 958   assert(cur);
 959   TCBDB *bdb = cur->bdb;
 960   if(!BDBLOCKMETHOD(bdb, false)) return false;
 961   if(!bdb->open){
 962     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 963     BDBUNLOCKMETHOD(bdb);
 964     return false;
 965   }
 966   if(cur->id < 1){
 967     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
 968     BDBUNLOCKMETHOD(bdb);
 969     return false;
 970   }
 971   bool rv = tcbdbcurprevimpl(cur);
 972   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 973   BDBUNLOCKMETHOD(bdb);
 974   if(adj && BDBLOCKMETHOD(bdb, true)){
 975     if(!bdb->tran && !tcbdbcacheadjust(bdb)) rv = false;
 976     BDBUNLOCKMETHOD(bdb);
 977   }
 978   return rv;
 979 }
 980
 981
 982 /* Move a cursor object to the next record. */
 983 bool tcbdbcurnext(BDBCUR *cur){
 984   assert(cur);
 985   TCBDB *bdb = cur->bdb;
 986   if(!BDBLOCKMETHOD(bdb, false)) return false;
 987   if(!bdb->open){
 988     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
 989     BDBUNLOCKMETHOD(bdb);
 990     return false;
 991   }
 992   if(cur->id < 1){
 993     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
 994     BDBUNLOCKMETHOD(bdb);
 995     return false;
 996   }
 997   bool rv = tcbdbcurnextimpl(cur);
 998   bool adj = TCMAPRNUM(bdb->leafc) > bdb->lcnum || TCMAPRNUM(bdb->nodec) > bdb->ncnum;
 999   BDBUNLOCKMETHOD(bdb);
1000   if(adj && BDBLOCKMETHOD(bdb, true)){
1001     if(!bdb->tran && !tcbdbcacheadjust(bdb)) rv = false;
1002     BDBUNLOCKMETHOD(bdb);
1003   }
1004   return rv;
1005 }
1006
1007
1008 /* Insert a record around a cursor object. */
1009 bool tcbdbcurput(BDBCUR *cur, const void *vbuf, int vsiz, int cpmode){
1010   assert(cur && vbuf && vsiz >= 0);
1011   TCBDB *bdb = cur->bdb;
1012   if(!BDBLOCKMETHOD(bdb, true)) return false;
1013   if(!bdb->open || !bdb->wmode){
1014     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1015     BDBUNLOCKMETHOD(bdb);
1016     return false;
1017   }
1018   if(cur->id < 1){
1019     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
1020     BDBUNLOCKMETHOD(bdb);
1021     return false;
1022   }
1023   bool rv = tcbdbcurputimpl(cur, vbuf, vsiz, cpmode);
1024   BDBUNLOCKMETHOD(bdb);
1025   return rv;
1026 }
1027
1028
1029 /* Insert a string record around a cursor object. */
1030 bool tcbdbcurput2(BDBCUR *cur, const char *vstr, int cpmode){
1031   assert(cur && vstr);
1032   return tcbdbcurput(cur, vstr, strlen(vstr), cpmode);
1033 }
1034
1035
1036 /* Delete the record where a cursor object is. */
1037 bool tcbdbcurout(BDBCUR *cur){
1038   assert(cur);
1039   TCBDB *bdb = cur->bdb;
1040   if(!BDBLOCKMETHOD(bdb, true)) return false;
1041   if(!bdb->open || !bdb->wmode){
1042     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1043     BDBUNLOCKMETHOD(bdb);
1044     return false;
1045   }
1046   if(cur->id < 1){
1047     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
1048     BDBUNLOCKMETHOD(bdb);
1049     return false;
1050   }
1051   bool rv = tcbdbcuroutimpl(cur);
1052   BDBUNLOCKMETHOD(bdb);
1053   return rv;
1054 }
1055
1056
1057 /* Get the key of the record where the cursor object is. */
1058 char *tcbdbcurkey(BDBCUR *cur, int *sp){
1059   assert(cur && sp);
1060   TCBDB *bdb = cur->bdb;
1061   if(!BDBLOCKMETHOD(bdb, false)) return false;
1062   if(!bdb->open){
1063     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1064     BDBUNLOCKMETHOD(bdb);
1065     return false;
1066   }
1067   if(cur->id < 1){
1068     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
1069     BDBUNLOCKMETHOD(bdb);
1070     return false;
1071   }
1072   const char *kbuf, *vbuf;
1073   int ksiz, vsiz;
1074   char *rv;
1075   if(tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
1076     TCMEMDUP(rv, kbuf, ksiz);
1077     *sp = ksiz;
1078   } else {
1079     rv = NULL;
1080   }
1081   BDBUNLOCKMETHOD(bdb);
1082   return rv;
1083 }
1084
1085
1086 /* Get the key string of the record where the cursor object is. */
1087 char *tcbdbcurkey2(BDBCUR *cur){
1088   assert(cur);
1089   int ksiz;
1090   return tcbdbcurkey(cur, &ksiz);
1091 }
1092
1093
1094 /* Get the key of the record where the cursor object is, as a volatile buffer. */
1095 const char *tcbdbcurkey3(BDBCUR *cur, int *sp){
1096   assert(cur && sp);
1097   TCBDB *bdb = cur->bdb;
1098   if(!BDBLOCKMETHOD(bdb, false)) return false;
1099   if(!bdb->open){
1100     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1101     BDBUNLOCKMETHOD(bdb);
1102     return false;
1103   }
1104   if(cur->id < 1){
1105     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
1106     BDBUNLOCKMETHOD(bdb);
1107     return false;
1108   }
1109   const char *kbuf, *vbuf;
1110   int ksiz, vsiz;
1111   const char *rv;
1112   if(tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
1113     rv = kbuf;
1114     *sp = ksiz;
1115   } else {
1116     rv = NULL;
1117   }
1118   BDBUNLOCKMETHOD(bdb);
1119   return rv;
1120 }
1121
1122
1123 /* Get the value of the record where the cursor object is. */
1124 char *tcbdbcurval(BDBCUR *cur, int *sp){
1125   assert(cur && sp);
1126   TCBDB *bdb = cur->bdb;
1127   if(!BDBLOCKMETHOD(bdb, false)) return false;
1128   if(!bdb->open){
1129     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1130     BDBUNLOCKMETHOD(bdb);
1131     return false;
1132   }
1133   if(cur->id < 1){
1134     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
1135     BDBUNLOCKMETHOD(bdb);
1136     return false;
1137   }
1138   const char *kbuf, *vbuf;
1139   int ksiz, vsiz;
1140   char *rv;
1141   if(tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
1142     TCMEMDUP(rv, vbuf, vsiz);
1143     *sp = vsiz;
1144   } else {
1145     rv = NULL;
1146   }
1147   BDBUNLOCKMETHOD(bdb);
1148   return rv;
1149 }
1150
1151
1152 /* Get the value string of the record where the cursor object is. */
1153 char *tcbdbcurval2(BDBCUR *cur){
1154   assert(cur);
1155   int vsiz;
1156   return tcbdbcurval(cur, &vsiz);
1157 }
1158
1159
1160 /* Get the value of the record where the cursor object is, as a volatile buffer. */
1161 const char *tcbdbcurval3(BDBCUR *cur, int *sp){
1162   assert(cur && sp);
1163   TCBDB *bdb = cur->bdb;
1164   if(!BDBLOCKMETHOD(bdb, false)) return false;
1165   if(!bdb->open){
1166     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1167     BDBUNLOCKMETHOD(bdb);
1168     return false;
1169   }
1170   if(cur->id < 1){
1171     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
1172     BDBUNLOCKMETHOD(bdb);
1173     return false;
1174   }
1175   const char *kbuf, *vbuf;
1176   int ksiz, vsiz;
1177   const char *rv;
1178   if(tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
1179     rv = vbuf;
1180     *sp = vsiz;
1181   } else {
1182     rv = NULL;
1183   }
1184   BDBUNLOCKMETHOD(bdb);
1185   return rv;
1186 }
1187
1188
1189 /* Get the key and the value of the record where the cursor object is. */
1190 bool tcbdbcurrec(BDBCUR *cur, TCXSTR *kxstr, TCXSTR *vxstr){
1191   assert(cur && kxstr && vxstr);
1192   TCBDB *bdb = cur->bdb;
1193   if(!BDBLOCKMETHOD(bdb, false)) return false;
1194   if(!bdb->open){
1195     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1196     BDBUNLOCKMETHOD(bdb);
1197     return false;
1198   }
1199   if(cur->id < 1){
1200     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
1201     BDBUNLOCKMETHOD(bdb);
1202     return false;
1203   }
1204   const char *kbuf, *vbuf;
1205   int ksiz, vsiz;
1206   bool rv;
1207   if(tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
1208     tcxstrclear(kxstr);
1209     TCXSTRCAT(kxstr, kbuf, ksiz);
1210     tcxstrclear(vxstr);
1211     TCXSTRCAT(vxstr, vbuf, vsiz);
1212     rv = true;
1213   } else {
1214     rv = false;
1215   }
1216   BDBUNLOCKMETHOD(bdb);
1217   return rv;
1218 }
1219
1220
1221
1222 /*************************************************************************************************
1223  * features for experts
1224  *************************************************************************************************/
1225
1226
1227 /* Set the error code of a B+ tree database object. */
1228 void tcbdbsetecode(TCBDB *bdb, int ecode, const char *filename, int line, const char *func){
1229   assert(bdb && filename && line >= 1 && func);
1230   tchdbsetecode(bdb->hdb, ecode, filename, line, func);
1231 }
1232
1233
1234 /* Set the file descriptor for debugging output. */
1235 void tcbdbsetdbgfd(TCBDB *bdb, int fd){
1236   assert(bdb && fd >= 0);
1237   tchdbsetdbgfd(bdb->hdb, fd);
1238 }
1239
1240
1241 /* Get the file descriptor for debugging output. */
1242 int tcbdbdbgfd(TCBDB *bdb){
1243   assert(bdb);
1244   return tchdbdbgfd(bdb->hdb);
1245 }
1246
1247
1248 /* Synchronize updating contents on memory. */
1249 bool tcbdbmemsync(TCBDB *bdb, bool phys){
1250   assert(bdb);
1251   if(!bdb->open || !bdb->wmode){
1252     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1253     return false;
1254   }
1255   bool err = false;
1256   bool clk = BDBLOCKCACHE(bdb);
1257   const char *vbuf;
1258   int vsiz;
1259   TCMAP *leafc = bdb->leafc;
1260   tcmapiterinit(leafc);
1261   while((vbuf = tcmapiternext(leafc, &vsiz)) != NULL){
1262     int rsiz;
1263     BDBLEAF *leaf = (BDBLEAF *)tcmapiterval(vbuf, &rsiz);
1264     if(leaf->dirty && !tcbdbleafsave(bdb, leaf)) err = true;
1265   }
1266   TCMAP *nodec = bdb->nodec;
1267   tcmapiterinit(nodec);
1268   while((vbuf = tcmapiternext(nodec, &vsiz)) != NULL){
1269     int rsiz;
1270     BDBNODE *node = (BDBNODE *)tcmapiterval(vbuf, &rsiz);
1271     if(node->dirty && !tcbdbnodesave(bdb, node)) err = true;
1272   }
1273   if(clk) BDBUNLOCKCACHE(bdb);
1274   tcdumpmeta(bdb);
1275   if(!tchdbmemsync(bdb->hdb, phys)) err = true;
1276   return !err;
1277 }
1278
1279
1280 /* Get the comparison function of a B+ tree database object. */
1281 BDBCMP tcbdbcmpfunc(TCBDB *bdb){
1282   assert(bdb);
1283   return bdb->cmp;
1284 }
1285
1286
1287 /* Get the opaque object for the comparison function of a B+ tree database object. */
1288 void *tcbdbcmpop(TCBDB *bdb){
1289   assert(bdb);
1290   return bdb->cmpop;
1291 }
1292
1293
1294 /* Get the maximum number of cached leaf nodes of a B+ tree database object. */
1295 uint32_t tcbdblmemb(TCBDB *bdb){
1296   assert(bdb);
1297   return bdb->lmemb;
1298 }
1299
1300
1301 /* Get the maximum number of cached non-leaf nodes of a B+ tree database object. */
1302 uint32_t tcbdbnmemb(TCBDB *bdb){
1303   assert(bdb);
1304   return bdb->nmemb;
1305 }
1306
1307
1308 /* Get the number of the leaf nodes of B+ tree database object. */
1309 uint64_t tcbdblnum(TCBDB *bdb){
1310   assert(bdb);
1311   if(!bdb->open){
1312     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1313     return 0;
1314   }
1315   return bdb->lnum;
1316 }
1317
1318
1319 /* Get the number of the non-leaf nodes of B+ tree database object. */
1320 uint64_t tcbdbnnum(TCBDB *bdb){
1321   assert(bdb);
1322   if(!bdb->open){
1323     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1324     return 0;
1325   }
1326   return bdb->nnum;
1327 }
1328
1329
1330 /* Get the number of elements of the bucket array of a B+ tree database object. */
1331 uint64_t tcbdbbnum(TCBDB *bdb){
1332   assert(bdb);
1333   if(!bdb->open){
1334     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1335     return 0;
1336   }
1337   return tchdbbnum(bdb->hdb);
1338 }
1339
1340
1341 /* Get the record alignment of a B+ tree database object. */
1342 uint32_t tcbdbalign(TCBDB *bdb){
1343   assert(bdb);
1344   if(!bdb->open){
1345     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1346     return 0;
1347   }
1348   return tchdbalign(bdb->hdb);
1349 }
1350
1351
1352 /* Get the maximum number of the free block pool of a B+ tree database object. */
1353 uint32_t tcbdbfbpmax(TCBDB *bdb){
1354   assert(bdb);
1355   if(!bdb->open){
1356     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1357     return 0;
1358   }
1359   return tchdbfbpmax(bdb->hdb);
1360 }
1361
1362
1363 /* Get the inode number of the database file of a B+ tree database object. */
1364 uint64_t tcbdbinode(TCBDB *bdb){
1365   assert(bdb);
1366   if(!bdb->open){
1367     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1368     return 0;
1369   }
1370   return tchdbinode(bdb->hdb);
1371 }
1372
1373
1374 /* Get the modification time of the database file of a B+ tree database object. */
1375 time_t tcbdbmtime(TCBDB *bdb){
1376   assert(bdb);
1377   if(!bdb->open){
1378     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1379     return 0;
1380   }
1381   return tchdbmtime(bdb->hdb);
1382 }
1383
1384
1385 /* Get the additional flags of a B+ tree database object. */
1386 uint8_t tcbdbflags(TCBDB *bdb){
1387   assert(bdb);
1388   if(!bdb->open){
1389     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1390     return 0;
1391   }
1392   return tchdbflags(bdb->hdb);
1393 }
1394
1395
1396 /* Get the options of a B+ tree database object. */
1397 uint8_t tcbdbopts(TCBDB *bdb){
1398   assert(bdb);
1399   if(!bdb->open){
1400     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1401     return 0;
1402   }
1403   return bdb->opts;
1404 }
1405
1406
1407 /* Get the pointer to the opaque field of a B+ tree database object. */
1408 char *tcbdbopaque(TCBDB *bdb){
1409   assert(bdb);
1410   if(!bdb->open){
1411     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1412     return 0;
1413   }
1414   return tchdbopaque(bdb->hdb) + BDBOPAQUESIZ;
1415 }
1416
1417
1418 /* Get the number of used elements of the bucket array of a B+ tree database object. */
1419 uint64_t tcbdbbnumused(TCBDB *bdb){
1420   assert(bdb);
1421   if(!bdb->open){
1422     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1423     return 0;
1424   }
1425   return tchdbbnumused(bdb->hdb);
1426 }
1427
1428
1429 /* Set the maximum size of each leaf node. */
1430 bool tcbdbsetlsmax(TCBDB *bdb, uint32_t lsmax){
1431   assert(bdb);
1432   if(bdb->open){
1433     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1434     return false;
1435   }
1436   bdb->lsmax = lsmax;
1437   return true;
1438 }
1439
1440
1441 /* Set the capacity number of records. */
1442 bool tcbdbsetcapnum(TCBDB *bdb, uint64_t capnum){
1443   assert(bdb);
1444   if(bdb->open){
1445     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1446     return false;
1447   }
1448   bdb->capnum = capnum;
1449   return true;
1450 }
1451
1452
1453 /* Store a new record into a B+ tree database object with backward duplication. */
1454 bool tcbdbputdupback(TCBDB *bdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
1455   assert(bdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1456   if(!BDBLOCKMETHOD(bdb, true)) return false;
1457   if(!bdb->open || !bdb->wmode){
1458     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1459     BDBUNLOCKMETHOD(bdb);
1460     return false;
1461   }
1462   bool rv = tcbdbputimpl(bdb, kbuf, ksiz, vbuf, vsiz, BDBPDDUPB);
1463   BDBUNLOCKMETHOD(bdb);
1464   return rv;
1465 }
1466
1467
1468 /* Store a new string record into a B+ tree database object with backward duplication. */
1469 bool tcbdbputdupback2(TCBDB *bdb, const char *kstr, const char *vstr){
1470   assert(bdb && kstr && vstr);
1471   return tcbdbputdupback(bdb, kstr, strlen(kstr), vstr, strlen(vstr));
1472 }
1473
1474
1475 /* Move a cursor object to the rear of records corresponding a key. */
1476 bool tcbdbcurjumpback(BDBCUR *cur, const void *kbuf, int ksiz){
1477   assert(cur && kbuf && ksiz >= 0);
1478   TCBDB *bdb = cur->bdb;
1479   if(!BDBLOCKMETHOD(bdb, false)) return false;
1480   if(!bdb->open){
1481     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
1482     BDBUNLOCKMETHOD(bdb);
1483     return false;
1484   }
1485   bool rv = tcbdbcurjumpimpl(cur, kbuf, ksiz, false);
1486   BDBUNLOCKMETHOD(bdb);
1487   return rv;
1488 }
1489
1490
1491 /* Move a cursor object to the rear of records corresponding a key string. */
1492 bool tcbdbcurjumpback2(BDBCUR *cur, const char *kstr){
1493   assert(cur && kstr);
1494   return tcbdbcurjumpback(cur, kstr, strlen(kstr));
1495 }
1496
1497
1498 /* Compare keys of two records by lexical order. */
1499 int tcbdbcmplexical(const char *aptr, int asiz, const char *bptr, int bsiz, void *op){
1500   assert(aptr && asiz >= 0 && bptr && bsiz >= 0);
1501   int rv;
1502   TCCMPLEXICAL(rv, aptr, asiz, bptr, bsiz);
1503   return rv;
1504 }
1505
1506
1507 /* Compare two keys as decimal strings of real numbers. */
1508 int tcbdbcmpdecimal(const char *aptr, int asiz, const char *bptr, int bsiz, void *op){
1509   assert(aptr && asiz >= 0 && bptr && bsiz >= 0);
1510   int sign;
1511   int64_t anum = 0;
1512   sign = 1;
1513   if(asiz > 0 && *aptr == '-'){
1514     aptr++;
1515     asiz--;
1516     sign = -1;
1517   }
1518   for(int i = 0; i < asiz; i++){
1519     int c = aptr[i];
1520     if(c < '0' || c > '9') continue;
1521     anum = anum * 10 + c - '0';
1522   }
1523   anum *= sign;
1524   int64_t bnum = 0;
1525   sign = 1;
1526   if(bsiz > 0 && *bptr == '-'){
1527     bptr++;
1528     bsiz--;
1529     sign = -1;
1530   }
1531   for(int i = 0; i < bsiz; i++){
1532     int c = bptr[i];
1533     if(c < '0' || c > '9') continue;
1534     bnum = bnum * 10 + c - '0';
1535   }
1536   bnum *= sign;
1537   return (anum < bnum) ? -1 : anum > bnum;
1538 }
1539
1540
1541 /* Compare two keys as 32-bit integers in the native byte order. */
1542 int tcbdbcmpint32(const char *aptr, int asiz, const char *bptr, int bsiz, void *op){
1543   assert(aptr && bptr);
1544   int32_t anum, bnum;
1545   if(asiz == sizeof(int32_t)){
1546     memcpy(&anum, aptr, sizeof(int32_t));
1547   } else if(asiz < sizeof(int32_t)){
1548     memset(&anum, 0, sizeof(int32_t));
1549     memcpy(&anum, aptr, asiz);
1550   } else {
1551     memcpy(&anum, aptr, sizeof(int32_t));
1552   }
1553   if(bsiz == sizeof(int32_t)){
1554     memcpy(&bnum, bptr, sizeof(int32_t));
1555   } else if(bsiz < sizeof(int32_t)){
1556     memset(&bnum, 0, sizeof(int32_t));
1557     memcpy(&bnum, bptr, bsiz);
1558   } else {
1559     memcpy(&bnum, bptr, sizeof(int32_t));
1560   }
1561   return (anum < bnum) ? -1 : anum > bnum;
1562 }
1563
1564
1565 /* Compare two keys as 64-bit integers in the native byte order. */
1566 int tcbdbcmpint64(const char *aptr, int asiz, const char *bptr, int bsiz, void *op){
1567   assert(aptr && bptr);
1568   int64_t anum, bnum;
1569   if(asiz == sizeof(int64_t)){
1570     memcpy(&anum, aptr, sizeof(int64_t));
1571   } else if(asiz < sizeof(int64_t)){
1572     memset(&anum, 0, sizeof(int64_t));
1573     memcpy(&anum, aptr, asiz);
1574   } else {
1575     memcpy(&anum, aptr, sizeof(int64_t));
1576   }
1577   if(bsiz == sizeof(int64_t)){
1578     memcpy(&bnum, bptr, sizeof(int64_t));
1579   } else if(bsiz < sizeof(int64_t)){
1580     memset(&bnum, 0, sizeof(int64_t));
1581     memcpy(&bnum, bptr, bsiz);
1582   } else {
1583     memcpy(&bnum, bptr, sizeof(int64_t));
1584   }
1585   return (anum < bnum) ? -1 : anum > bnum;
1586 }
1587
1588
1589
1590 /*************************************************************************************************
1591  * private features
1592  *************************************************************************************************/
1593
1594
1595 /* Clear all members.
1596    `bdb' specifies the B+ tree database object. */
1597 static void tcbdbclear(TCBDB *bdb){
1598   assert(bdb);
1599   bdb->mmtx = NULL;
1600   bdb->cmtx = NULL;
1601   bdb->tmtx = NULL;
1602   bdb->hdb = NULL;
1603   bdb->opaque = NULL;
1604   bdb->open = false;
1605   bdb->wmode = false;
1606   bdb->lmemb = BDBDEFLMEMB;
1607   bdb->nmemb = BDBDEFNMEMB;
1608   bdb->opts = 0;
1609   bdb->root = 0;
1610   bdb->first = 0;
1611   bdb->last = 0;
1612   bdb->lnum = 0;
1613   bdb->nnum = 0;
1614   bdb->rnum = 0;
1615   bdb->leafc = NULL;
1616   bdb->nodec = NULL;
1617   bdb->cmp = NULL;
1618   bdb->cmpop = NULL;
1619   bdb->lcnum = BDBDEFLCNUM;
1620   bdb->ncnum = BDBDEFNCNUM;
1621   bdb->lsmax = 0;
1622   bdb->lschk = 0;
1623   bdb->capnum = 0;
1624   bdb->hist = NULL;
1625   bdb->hnum = 0;
1626   bdb->hleaf = 0;
1627   bdb->lleaf = 0;
1628   bdb->tran = false;
1629   bdb->rbopaque = NULL;
1630   bdb->cnt_saveleaf = -1;
1631   bdb->cnt_loadleaf = -1;
1632   bdb->cnt_killleaf = -1;
1633   bdb->cnt_adjleafc = -1;
1634   bdb->cnt_savenode = -1;
1635   bdb->cnt_loadnode = -1;
1636   bdb->cnt_adjnodec = -1;
1637   TCDODEBUG(bdb->cnt_saveleaf = 0);
1638   TCDODEBUG(bdb->cnt_loadleaf = 0);
1639   TCDODEBUG(bdb->cnt_killleaf = 0);
1640   TCDODEBUG(bdb->cnt_adjleafc = 0);
1641   TCDODEBUG(bdb->cnt_savenode = 0);
1642   TCDODEBUG(bdb->cnt_loadnode = 0);
1643   TCDODEBUG(bdb->cnt_adjnodec = 0);
1644 }
1645
1646
1647 /* Serialize meta data into the opaque field.
1648    `bdb' specifies the B+ tree database object. */
1649 static void tcdumpmeta(TCBDB *bdb){
1650   assert(bdb);
1651   memset(bdb->opaque, 0, 64);
1652   char *wp = bdb->opaque;
1653   if(bdb->cmp == tcbdbcmplexical){
1654     *(uint8_t *)(wp++) = 0x0;
1655   } else if(bdb->cmp == tcbdbcmpdecimal){
1656     *(uint8_t *)(wp++) = 0x1;
1657   } else if(bdb->cmp == tcbdbcmpint32){
1658     *(uint8_t *)(wp++) = 0x2;
1659   } else if(bdb->cmp == tcbdbcmpint64){
1660     *(uint8_t *)(wp++) = 0x3;
1661   } else {
1662     *(uint8_t *)(wp++) = 0xff;
1663   }
1664   wp += 7;
1665   uint32_t lnum;
1666   lnum = bdb->lmemb;
1667   lnum = TCHTOIL(lnum);
1668   memcpy(wp, &lnum, sizeof(lnum));
1669   wp += sizeof(lnum);
1670   lnum = bdb->nmemb;
1671   lnum = TCHTOIL(lnum);
1672   memcpy(wp, &lnum, sizeof(lnum));
1673   wp += sizeof(lnum);
1674   uint64_t llnum;
1675   llnum = bdb->root;
1676   llnum = TCHTOILL(llnum);
1677   memcpy(wp, &llnum, sizeof(llnum));
1678   wp += sizeof(llnum);
1679   llnum = bdb->first;
1680   llnum = TCHTOILL(llnum);
1681   memcpy(wp, &llnum, sizeof(llnum));
1682   wp += sizeof(llnum);
1683   llnum = bdb->last;
1684   llnum = TCHTOILL(llnum);
1685   memcpy(wp, &llnum, sizeof(llnum));
1686   wp += sizeof(llnum);
1687   llnum = bdb->lnum;
1688   llnum = TCHTOILL(llnum);
1689   memcpy(wp, &llnum, sizeof(llnum));
1690   wp += sizeof(llnum);
1691   llnum = bdb->nnum;
1692   llnum = TCHTOILL(llnum);
1693   memcpy(wp, &llnum, sizeof(llnum));
1694   wp += sizeof(llnum);
1695   llnum = bdb->rnum;
1696   llnum = TCHTOILL(llnum);
1697   memcpy(wp, &llnum, sizeof(llnum));
1698   wp += sizeof(llnum);
1699 }
1700
1701
1702 /* Deserialize meta data from the opaque field.
1703    `bdb' specifies the B+ tree database object. */
1704 static void tcloadmeta(TCBDB *bdb){
1705   const char *rp = bdb->opaque;
1706   uint8_t cnum = *(uint8_t *)(rp++);
1707   if(cnum == 0x0){
1708     bdb->cmp = tcbdbcmplexical;
1709   } else if(cnum == 0x1){
1710     bdb->cmp = tcbdbcmpdecimal;
1711   } else if(cnum == 0x2){
1712     bdb->cmp = tcbdbcmpint32;
1713   } else if(cnum == 0x3){
1714     bdb->cmp = tcbdbcmpint64;
1715   }
1716   rp += 7;
1717   uint32_t lnum;
1718   memcpy(&lnum, rp, sizeof(lnum));
1719   rp += sizeof(lnum);
1720   bdb->lmemb = TCITOHL(lnum);
1721   memcpy(&lnum, rp, sizeof(lnum));
1722   rp += sizeof(lnum);
1723   bdb->nmemb = TCITOHL(lnum);
1724   uint64_t llnum;
1725   memcpy(&llnum, rp, sizeof(llnum));
1726   bdb->root = TCITOHLL(llnum);
1727   rp += sizeof(llnum);
1728   memcpy(&llnum, rp, sizeof(llnum));
1729   bdb->first = TCITOHLL(llnum);
1730   rp += sizeof(llnum);
1731   memcpy(&llnum, rp, sizeof(llnum));
1732   bdb->last = TCITOHLL(llnum);
1733   rp += sizeof(llnum);
1734   memcpy(&llnum, rp, sizeof(llnum));
1735   bdb->lnum = TCITOHLL(llnum);
1736   rp += sizeof(llnum);
1737   memcpy(&llnum, rp, sizeof(llnum));
1738   bdb->nnum = TCITOHLL(llnum);
1739   rp += sizeof(llnum);
1740   memcpy(&llnum, rp, sizeof(llnum));
1741   bdb->rnum = TCITOHLL(llnum);
1742   rp += sizeof(llnum);
1743 }
1744
1745
1746 /* Create a new leaf.
1747    `bdb' specifies the B+ tree database object.
1748    `prev' specifies the ID number of the previous leaf.
1749    `next' specifies the ID number of the next leaf.
1750    The return value is the new leaf object. */
1751 static BDBLEAF *tcbdbleafnew(TCBDB *bdb, uint64_t prev, uint64_t next){
1752   assert(bdb);
1753   BDBLEAF lent;
1754   lent.id = ++bdb->lnum;
1755   lent.recs = tclistnew2(bdb->lmemb + 1);
1756   lent.prev = prev;
1757   lent.next = next;
1758   lent.dirty = true;
1759   lent.dead = false;
1760   tcmapputkeep(bdb->leafc, &(lent.id), sizeof(lent.id), &lent, sizeof(lent));
1761   int rsiz;
1762   return (BDBLEAF *)tcmapget(bdb->leafc, &(lent.id), sizeof(lent.id), &rsiz);
1763 }
1764
1765
1766 /* Remove a leaf from the cache.
1767    `bdb' specifies the B+ tree database object.
1768    `leaf' specifies the leaf object.
1769    If successful, the return value is true, else, it is false. */
1770 static bool tcbdbleafcacheout(TCBDB *bdb, BDBLEAF *leaf){
1771   assert(bdb && leaf);
1772   bool err = false;
1773   if(leaf->dirty && !tcbdbleafsave(bdb, leaf)) err = true;
1774   TCLIST *recs = leaf->recs;
1775   int ln = TCLISTNUM(recs);
1776   for(int i = 0; i < ln; i++){
1777     BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
1778     free(recp->kbuf);
1779     free(recp->vbuf);
1780     if(recp->rest) tclistdel(recp->rest);
1781   }
1782   tclistdel(recs);
1783   tcmapout(bdb->leafc, &(leaf->id), sizeof(leaf->id));
1784   return !err;
1785 }
1786
1787
1788 /* Save a leaf into the internal database.
1789    `bdb' specifies the B+ tree database object.
1790    `leaf' specifies the leaf object.
1791    If successful, the return value is true, else, it is false. */
1792 static bool tcbdbleafsave(TCBDB *bdb, BDBLEAF *leaf){
1793   assert(bdb && leaf);
1794   TCDODEBUG(bdb->cnt_saveleaf++);
1795   TCXSTR *rbuf = tcxstrnew3(BDBPAGEBUFSIZ);
1796   char hbuf[(sizeof(uint64_t)+1)*3];
1797   char *wp = hbuf;
1798   uint64_t llnum;
1799   int step;
1800   llnum = leaf->prev;
1801   TCSETVNUMBUF64(step, wp, llnum);
1802   wp += step;
1803   llnum = leaf->next;
1804   TCSETVNUMBUF64(step, wp, llnum);
1805   wp += step;
1806   TCXSTRCAT(rbuf, hbuf, wp - hbuf);
1807   TCLIST *recs = leaf->recs;
1808   int ln = TCLISTNUM(recs);
1809   for(int i = 0; i < ln; i++){
1810     BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
1811     int lnum;
1812     wp = hbuf;
1813     lnum = recp->ksiz;
1814     TCSETVNUMBUF(step, wp, lnum);
1815     wp += step;
1816     lnum = recp->vsiz;
1817     TCSETVNUMBUF(step, wp, lnum);
1818     wp += step;
1819     TCLIST *rest = recp->rest;
1820     int rnum = rest ? TCLISTNUM(rest) : 0;
1821     TCSETVNUMBUF(step, wp, rnum);
1822     wp += step;
1823     TCXSTRCAT(rbuf, hbuf, wp - hbuf);
1824     TCXSTRCAT(rbuf, recp->kbuf, recp->ksiz);
1825     TCXSTRCAT(rbuf, recp->vbuf, recp->vsiz);
1826     for(int j = 0; j < rnum; j++){
1827       int vsiz;
1828       const char *vbuf = tclistval(rest, j, &vsiz);
1829       TCSETVNUMBUF(step, hbuf, vsiz);
1830       TCXSTRCAT(rbuf, hbuf, step);
1831       TCXSTRCAT(rbuf, vbuf, vsiz);
1832     }
1833   }
1834   bool err = false;
1835   step = sprintf(hbuf, "%llx", (unsigned long long)leaf->id);
1836   if(ln < 1 && !tchdbout(bdb->hdb, hbuf, step) && tchdbecode(bdb->hdb) != TCENOREC)
1837     err = true;
1838   if(!leaf->dead && !tchdbput(bdb->hdb, hbuf, step, TCXSTRPTR(rbuf), TCXSTRSIZE(rbuf)))
1839     err = true;
1840   tcxstrdel(rbuf);
1841   leaf->dirty = false;
1842   return !err;
1843 }
1844
1845
1846 /* Load a leaf from the internal database.
1847    `bdb' specifies the B+ tree database object.
1848    `id' specifies the ID number of the leaf.
1849    The return value is the leaf object or `NULL' on failure. */
1850 static BDBLEAF *tcbdbleafload(TCBDB *bdb, uint64_t id){
1851   assert(bdb && id > 0);
1852   bool clk = BDBLOCKCACHE(bdb);
1853   int rsiz;
1854   BDBLEAF *leaf = (BDBLEAF *)tcmapget3(bdb->leafc, &id, sizeof(id), &rsiz);
1855   if(leaf){
1856     if(clk) BDBUNLOCKCACHE(bdb);
1857     return leaf;
1858   }
1859   if(clk) BDBUNLOCKCACHE(bdb);
1860   TCDODEBUG(bdb->cnt_loadleaf++);
1861   char hbuf[(sizeof(uint64_t)+1)*3];
1862   int step;
1863   step = sprintf(hbuf, "%llx", (unsigned long long)id);
1864   char *rbuf = NULL;
1865   char wbuf[BDBPAGEBUFSIZ];
1866   const char *rp = NULL;
1867   rsiz = tchdbget3(bdb->hdb, hbuf, step, wbuf, BDBPAGEBUFSIZ);
1868   if(rsiz < 1){
1869     tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
1870     return false;
1871   } else if(rsiz < BDBPAGEBUFSIZ){
1872     rp = wbuf;
1873   } else {
1874     if(!(rbuf = tchdbget(bdb->hdb, hbuf, step, &rsiz))){
1875       tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
1876       return false;
1877     }
1878     rp = rbuf;
1879   }
1880   BDBLEAF lent;
1881   lent.id = id;
1882   uint64_t llnum;
1883   TCREADVNUMBUF64(rp, llnum, step);
1884   lent.prev = llnum;
1885   rp += step;
1886   rsiz -= step;
1887   TCREADVNUMBUF64(rp, llnum, step);
1888   lent.next = llnum;
1889   rp += step;
1890   rsiz -= step;
1891   lent.dirty = false;
1892   lent.dead = false;
1893   lent.recs = tclistnew2(bdb->lmemb + 1);
1894   bool err = false;
1895   while(rsiz >= 3){
1896     BDBREC rec;
1897     TCREADVNUMBUF(rp, rec.ksiz, step);
1898     rp += step;
1899     rsiz -= step;
1900     TCREADVNUMBUF(rp, rec.vsiz, step);
1901     rp += step;
1902     rsiz -= step;
1903     int rnum;
1904     TCREADVNUMBUF(rp, rnum, step);
1905     rp += step;
1906     rsiz -= step;
1907     if(rsiz < rec.ksiz + rec.vsiz + rnum){
1908       err = true;
1909       break;
1910     }
1911     TCMEMDUP(rec.kbuf, rp, rec.ksiz);
1912     rp += rec.ksiz;
1913     rsiz -= rec.ksiz;
1914     TCMEMDUP(rec.vbuf, rp, rec.vsiz);
1915     rp += rec.vsiz;
1916     rsiz -= rec.vsiz;
1917     if(rnum > 0){
1918       rec.rest = tclistnew2(rnum);
1919       while(rnum-- > 0 && rsiz > 0){
1920         int vsiz;
1921         TCREADVNUMBUF(rp, vsiz, step);
1922         rp += step;
1923         rsiz -= step;
1924         if(rsiz < vsiz){
1925           err = true;
1926           break;
1927         }
1928         TCLISTPUSH(rec.rest, rp, vsiz);
1929         rp += vsiz;
1930         rsiz -= vsiz;
1931       }
1932     } else {
1933       rec.rest = NULL;
1934     }
1935     TCLISTPUSH(lent.recs, &rec, sizeof(rec));
1936   }
1937   free(rbuf);
1938   if(err || rsiz != 0){
1939     tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
1940     return NULL;
1941   }
1942   clk = BDBLOCKCACHE(bdb);
1943   tcmapputkeep(bdb->leafc, &(lent.id), sizeof(lent.id), &lent, sizeof(lent));
1944   leaf = (BDBLEAF *)tcmapget(bdb->leafc, &(lent.id), sizeof(lent.id), &rsiz);
1945   if(clk) BDBUNLOCKCACHE(bdb);
1946   return leaf;
1947 }
1948
1949
1950 /* Load the historical leaf from the internal database.
1951    `bdb' specifies the B+ tree database object.
1952    `kbuf' specifies the pointer to the region of the key.
1953    `ksiz' specifies the size of the region of the key.
1954    If successful, the return value is the pointer to the leaf, else, it is `NULL'. */
1955 static BDBLEAF *tcbdbgethistleaf(TCBDB *bdb, const char *kbuf, int ksiz){
1956   assert(bdb && kbuf && ksiz >= 0);
1957   BDBLEAF *leaf = tcbdbleafload(bdb, bdb->hleaf);
1958   if(!leaf) return NULL;
1959   int ln = TCLISTNUM(leaf->recs);
1960   if(ln < 2) return NULL;
1961   BDBREC *recp = (BDBREC *)TCLISTVALPTR(leaf->recs, 0);
1962   int rv;
1963   if(bdb->cmp == tcbdbcmplexical){
1964     TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
1965   } else {
1966     rv = bdb->cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, bdb->cmpop);
1967   }
1968   if(rv == 0) return leaf;
1969   if(rv < 0) return NULL;
1970   recp = (BDBREC *)TCLISTVALPTR(leaf->recs, ln - 1);
1971   if(bdb->cmp == tcbdbcmplexical){
1972     TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
1973   } else {
1974     rv = bdb->cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, bdb->cmpop);
1975   }
1976   if(rv <= 0 || leaf->next < 1) return leaf;
1977   return NULL;
1978 }
1979
1980
1981 /* Add a record to a leaf.
1982    `bdb' specifies the B+ tree database object.
1983    `leaf' specifies the leaf object.
1984    `dmode' specifies behavior when the key overlaps.
1985    `kbuf' specifies the pointer to the region of the key.
1986    `ksiz' specifies the size of the region of the key.
1987    `vbuf' specifies the pointer to the region of the value.
1988    `vsiz' specifies the size of the region of the value.
1989    If successful, the return value is true, else, it is false. */
1990 static bool tcbdbleafaddrec(TCBDB *bdb, BDBLEAF *leaf, int dmode,
1991                             const char *kbuf, int ksiz, const char *vbuf, int vsiz){
1992   assert(bdb && leaf && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1993   BDBCMP cmp = bdb->cmp;
1994   void *cmpop = bdb->cmpop;
1995   TCLIST *recs = leaf->recs;
1996   int ln = TCLISTNUM(recs);
1997   int left = 0;
1998   int right = ln;
1999   int i = (left + right) / 2;
2000   while(right >= left && i < ln){
2001     BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
2002     int rv;
2003     if(cmp == tcbdbcmplexical){
2004       TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
2005     } else {
2006       rv = cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, cmpop);
2007     }
2008     if(rv == 0){
2009       break;
2010     } else if(rv <= 0){
2011       right = i - 1;
2012     } else {
2013       left = i + 1;
2014     }
2015     i = (left + right) / 2;
2016   }
2017   while(i < ln){
2018     BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
2019     int rv;
2020     if(cmp == tcbdbcmplexical){
2021       TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
2022     } else {
2023       rv = cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, cmpop);
2024     }
2025     if(rv == 0){
2026       switch(dmode){
2027       case BDBPDKEEP:
2028         return false;
2029       case BDBPDCAT:
2030         TCREALLOC(recp->vbuf, recp->vbuf, recp->vsiz + vsiz + 1);
2031         memcpy(recp->vbuf + recp->vsiz, vbuf, vsiz);
2032         recp->vsiz += vsiz;
2033         recp->vbuf[recp->vsiz] = '\0';
2034         break;
2035       case BDBPDDUP:
2036         if(!recp->rest) recp->rest = tclistnew();
2037         TCLISTPUSH(recp->rest, vbuf, vsiz);
2038         bdb->rnum++;
2039         break;
2040       case BDBPDDUPB:
2041         if(!recp->rest) recp->rest = tclistnew();
2042         tclistunshift(recp->rest, recp->vbuf, recp->vsiz);
2043         if(vsiz > recp->vsiz) TCREALLOC(recp->vbuf, recp->vbuf, vsiz + 1);
2044         memcpy(recp->vbuf, vbuf, vsiz);
2045         recp->vbuf[vsiz] = '\0';
2046         recp->vsiz = vsiz;
2047         bdb->rnum++;
2048         break;
2049       default:
2050         if(vsiz > recp->vsiz) TCREALLOC(recp->vbuf, recp->vbuf, vsiz + 1);
2051         memcpy(recp->vbuf, vbuf, vsiz);
2052         recp->vbuf[vsiz] = '\0';
2053         recp->vsiz = vsiz;
2054         break;
2055       }
2056       break;
2057     } else if(rv < 0){
2058       BDBREC rec;
2059       TCMEMDUP(rec.kbuf, kbuf, ksiz);
2060       rec.ksiz = ksiz;
2061       TCMEMDUP(rec.vbuf, vbuf, vsiz);
2062       rec.vsiz = vsiz;
2063       rec.rest = NULL;
2064       tclistinsert(recs, i, &rec, sizeof(rec));
2065       bdb->rnum++;
2066       break;
2067     }
2068     i++;
2069   }
2070   if(i >= ln){
2071     BDBREC rec;
2072     TCMEMDUP(rec.kbuf, kbuf, ksiz);
2073     rec.ksiz = ksiz;
2074     TCMEMDUP(rec.vbuf, vbuf, vsiz);
2075     rec.vsiz = vsiz;
2076     rec.rest = NULL;
2077     TCLISTPUSH(recs, &rec, sizeof(rec));
2078     bdb->rnum++;
2079   }
2080   leaf->dirty = true;
2081   return true;
2082 }
2083
2084
2085 /* Calculate the size of data of a leaf object.
2086    `bdb' specifies the B+ tree database object.
2087    `leaf' specifies the leaf object.
2088    The return value is size of data of the leaf. */
2089 static int tcbdbleafdatasize(BDBLEAF *leaf){
2090   assert(leaf);
2091   int sum = 0;
2092   TCLIST *recs = leaf->recs;
2093   int ln = TCLISTNUM(recs);
2094   for(int i = 0; i < ln; i++){
2095     BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
2096     sum += recp->ksiz + recp->vsiz;
2097     if(recp->rest){
2098       TCLIST *rest = recp->rest;
2099       int rnum = TCLISTNUM(rest);
2100       for(int j = 0; j < rnum; j++){
2101         int vsiz;
2102         tclistval(rest, j, &vsiz);
2103         sum += vsiz;
2104       }
2105     }
2106   }
2107   return sum;
2108 }
2109
2110
2111 /* Divide a leaf into two.
2112    `bdb' specifies the B+ tree database object.
2113    `leaf' specifies the leaf object.
2114    The return value is the new leaf object or `NULL' on failure. */
2115 static BDBLEAF *tcbdbleafdivide(TCBDB *bdb, BDBLEAF *leaf){
2116   assert(bdb && leaf);
2117   bdb->hleaf = 0;
2118   TCLIST *recs = leaf->recs;
2119   int mid = TCLISTNUM(recs) / 2;
2120   BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, mid);
2121   BDBLEAF *newleaf = tcbdbleafnew(bdb, leaf->id, leaf->next);
2122   if(newleaf->next > 0){
2123     BDBLEAF *nextleaf = tcbdbleafload(bdb, newleaf->next);
2124     if(!nextleaf) return NULL;
2125     nextleaf->prev = newleaf->id;
2126     nextleaf->dirty = true;
2127   }
2128   leaf->next = newleaf->id;
2129   leaf->dirty = true;
2130   int ln = TCLISTNUM(recs);
2131   TCLIST *newrecs = newleaf->recs;
2132   for(int i = mid; i < ln; i++){
2133     recp = (BDBREC *)TCLISTVALPTR(recs, i);
2134     TCLISTPUSH(newrecs, recp, sizeof(*recp));
2135   }
2136   ln = TCLISTNUM(newrecs);
2137   for(int i = 0; i < ln; i++){
2138     int rsiz;
2139     free(tclistpop(recs, &rsiz));
2140   }
2141   return newleaf;
2142 }
2143
2144
2145 /* Cut off the path to a leaf and mark it dead.
2146    `bdb' specifies the B+ tree database object.
2147    `leaf' specifies the leaf object.
2148    If successful, the return value is true, else, it is false. */
2149 static bool tcbdbleafkill(TCBDB *bdb, BDBLEAF *leaf){
2150   assert(bdb && leaf);
2151   BDBNODE *node = tcbdbnodeload(bdb, bdb->hist[bdb->hnum-1]);
2152   if(!node) return false;
2153   if(tcbdbnodesubidx(bdb, node, leaf->id)){
2154     TCDODEBUG(bdb->cnt_killleaf++);
2155     if(bdb->hleaf == leaf->id) bdb->hleaf = 0;
2156     if(leaf->prev > 0){
2157       BDBLEAF *tleaf = tcbdbleafload(bdb, leaf->prev);
2158       if(!tleaf) return false;
2159       tleaf->next = leaf->next;
2160       tleaf->dirty = true;
2161       if(bdb->last == leaf->id) bdb->last = leaf->prev;
2162     }
2163     if(leaf->next > 0){
2164       BDBLEAF *tleaf = tcbdbleafload(bdb, leaf->next);
2165       if(!tleaf) return false;
2166       tleaf->prev = leaf->prev;
2167       tleaf->dirty = true;
2168       if(bdb->first == leaf->id) bdb->first = leaf->next;
2169     }
2170     leaf->dead = true;
2171   }
2172   return true;
2173 }
2174
2175
2176 /* Create a new node.
2177    `bdb' specifies the B+ tree database object.
2178    `heir' specifies the ID of the child before the first index.
2179    The return value is the new node object. */
2180 static BDBNODE *tcbdbnodenew(TCBDB *bdb, uint64_t heir){
2181   assert(bdb && heir > 0);
2182   BDBNODE nent;
2183   nent.id = ++bdb->nnum + BDBNODEIDBASE;
2184   nent.idxs = tclistnew2(bdb->nmemb + 1);
2185   nent.heir = heir;
2186   nent.dirty = true;
2187   tcmapputkeep(bdb->nodec, &(nent.id), sizeof(nent.id), &nent, sizeof(nent));
2188   int rsiz;
2189   return (BDBNODE *)tcmapget(bdb->nodec, &(nent.id), sizeof(nent.id), &rsiz);
2190 }
2191
2192
2193 /* Remove a node from the cache.
2194    `bdb' specifies the B+ tree database object.
2195    `node' specifies the node object.
2196    If successful, the return value is true, else, it is false. */
2197 static bool tcbdbnodecacheout(TCBDB *bdb, BDBNODE *node){
2198   assert(bdb && node);
2199   bool err = false;
2200   if(node->dirty && !tcbdbnodesave(bdb, node)) err = true;
2201   TCLIST *idxs = node->idxs;
2202   int ln = TCLISTNUM(idxs);
2203   for(int i = 0; i < ln; i++){
2204     BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2205     free(idxp->kbuf);
2206   }
2207   tclistdel(idxs);
2208   tcmapout(bdb->nodec, &(node->id), sizeof(node->id));
2209   return !err;
2210 }
2211
2212
2213 /* Save a node into the internal database.
2214    `bdb' specifies the B+ tree database object.
2215    `node' specifies the node object.
2216    If successful, the return value is true, else, it is false. */
2217 static bool tcbdbnodesave(TCBDB *bdb, BDBNODE *node){
2218   assert(bdb && node);
2219   TCDODEBUG(bdb->cnt_savenode++);
2220   TCXSTR *rbuf = tcxstrnew3(BDBPAGEBUFSIZ);
2221   char hbuf[(sizeof(uint64_t)+1)*2];
2222   uint64_t llnum;
2223   int step;
2224   llnum = node->heir;
2225   TCSETVNUMBUF64(step, hbuf, llnum);
2226   TCXSTRCAT(rbuf, hbuf, step);
2227   TCLIST *idxs = node->idxs;
2228   int ln = TCLISTNUM(idxs);
2229   for(int i = 0; i < ln; i++){
2230     BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2231     char *wp = hbuf;
2232     llnum = idxp->pid;
2233     TCSETVNUMBUF64(step, wp, llnum);
2234     wp += step;
2235     uint32_t lnum = idxp->ksiz;
2236     TCSETVNUMBUF(step, wp, lnum);
2237     wp += step;
2238     TCXSTRCAT(rbuf, hbuf, wp - hbuf);
2239     TCXSTRCAT(rbuf, idxp->kbuf, idxp->ksiz);
2240   }
2241   bool err = false;
2242   step = sprintf(hbuf, "#%llx", (unsigned long long)(node->id - BDBNODEIDBASE));
2243   if(!tchdbput(bdb->hdb, hbuf, step, TCXSTRPTR(rbuf), TCXSTRSIZE(rbuf))) err = true;
2244   tcxstrdel(rbuf);
2245   node->dirty = false;
2246   return !err;
2247 }
2248
2249
2250 /* Load a node from the internal database.
2251    `bdb' specifies the B+ tree database object.
2252    `id' specifies the ID number of the node.
2253    The return value is the node object or `NULL' on failure. */
2254 static BDBNODE *tcbdbnodeload(TCBDB *bdb, uint64_t id){
2255   assert(bdb && id > BDBNODEIDBASE);
2256   bool clk = BDBLOCKCACHE(bdb);
2257   int rsiz;
2258   BDBNODE *node = (BDBNODE *)tcmapget3(bdb->nodec, &id, sizeof(id), &rsiz);
2259   if(node){
2260     if(clk) BDBUNLOCKCACHE(bdb);
2261     return node;
2262   }
2263   if(clk) BDBUNLOCKCACHE(bdb);
2264   TCDODEBUG(bdb->cnt_loadnode++);
2265   char hbuf[(sizeof(uint64_t)+1)*2];
2266   int step;
2267   step = sprintf(hbuf, "#%llx", (unsigned long long)(id - BDBNODEIDBASE));
2268   char *rbuf = NULL;
2269   char wbuf[BDBPAGEBUFSIZ];
2270   const char *rp = NULL;
2271   rsiz = tchdbget3(bdb->hdb, hbuf, step, wbuf, BDBPAGEBUFSIZ);
2272   if(rsiz < 1){
2273     tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
2274     return false;
2275   } else if(rsiz < BDBPAGEBUFSIZ){
2276     rp = wbuf;
2277   } else {
2278     if(!(rbuf = tchdbget(bdb->hdb, hbuf, step, &rsiz))){
2279       tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
2280       return false;
2281     }
2282     rp = rbuf;
2283   }
2284   BDBNODE nent;
2285   nent.id = id;
2286   uint64_t llnum;
2287   TCREADVNUMBUF64(rp, llnum, step);
2288   nent.heir = llnum;
2289   rp += step;
2290   rsiz -= step;
2291   nent.dirty = false;
2292   nent.idxs = tclistnew2(bdb->nmemb + 1);
2293   bool err = false;
2294   while(rsiz >= 2){
2295     BDBIDX idx;
2296     TCREADVNUMBUF64(rp, idx.pid, step);
2297     rp += step;
2298     rsiz -= step;
2299     TCREADVNUMBUF(rp, idx.ksiz, step);
2300     rp += step;
2301     rsiz -= step;
2302     if(rsiz < idx.ksiz){
2303       err = true;
2304       break;
2305     }
2306     TCMEMDUP(idx.kbuf, rp, idx.ksiz);
2307     rp += idx.ksiz;
2308     rsiz -= idx.ksiz;
2309     TCLISTPUSH(nent.idxs, &idx, sizeof(idx));
2310   }
2311   free(rbuf);
2312   if(err || rsiz != 0){
2313     tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
2314     return NULL;
2315   }
2316   clk = BDBLOCKCACHE(bdb);
2317   tcmapputkeep(bdb->nodec, &(nent.id), sizeof(nent.id), &nent, sizeof(nent));
2318   node = (BDBNODE *)tcmapget(bdb->nodec, &(nent.id), sizeof(nent.id), &rsiz);
2319   if(clk) BDBUNLOCKCACHE(bdb);
2320   return node;
2321 }
2322
2323
2324 /* Add an index to a node.
2325    `bdb' specifies the B+ tree database object.
2326    `node' specifies the node object.
2327    `order' specifies whether the calling sequence is orderd or not.
2328    `pid' specifies the ID number of referred page.
2329    `kbuf' specifies the pointer to the region of the key.
2330    `ksiz' specifies the size of the region of the key. */
2331 static void tcbdbnodeaddidx(TCBDB *bdb, BDBNODE *node, bool order, uint64_t pid,
2332                             const char *kbuf, int ksiz){
2333   assert(bdb && node && pid > 0 && kbuf && ksiz >= 0);
2334   BDBIDX idx;
2335   idx.pid = pid;
2336   TCMEMDUP(idx.kbuf, kbuf, ksiz);
2337   idx.ksiz = ksiz;
2338   BDBCMP cmp = bdb->cmp;
2339   void *cmpop = bdb->cmpop;
2340   TCLIST *idxs = node->idxs;
2341   if(order){
2342     TCLISTPUSH(idxs, &idx, sizeof(idx));
2343   } else {
2344     int ln = TCLISTNUM(idxs);
2345     int left = 0;
2346     int right = ln;
2347     int i = (left + right) / 2;
2348     while(right >= left && i < ln){
2349       BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2350       int rv;
2351       if(cmp == tcbdbcmplexical){
2352         TCCMPLEXICAL(rv, kbuf, ksiz, idxp->kbuf, idxp->ksiz);
2353       } else {
2354         rv = cmp(kbuf, ksiz, idxp->kbuf, idxp->ksiz, cmpop);
2355       }
2356       if(rv == 0){
2357         break;
2358       } else if(rv <= 0){
2359         right = i - 1;
2360       } else {
2361         left = i + 1;
2362       }
2363       i = (left + right) / 2;
2364     }
2365     while(i < ln){
2366       BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2367       int rv;
2368       if(cmp == tcbdbcmplexical){
2369         TCCMPLEXICAL(rv, kbuf, ksiz, idxp->kbuf, idxp->ksiz);
2370       } else {
2371         rv = cmp(kbuf, ksiz, idxp->kbuf, idxp->ksiz, cmpop);
2372       }
2373       if(rv < 0){
2374         tclistinsert(idxs, i, &idx, sizeof(idx));
2375         break;
2376       }
2377       i++;
2378     }
2379     if(i >= ln) TCLISTPUSH(idxs, &idx, sizeof(idx));
2380   }
2381   node->dirty = true;
2382 }
2383
2384
2385 /* Subtract an index from a node.
2386    `bdb' specifies the B+ tree database object.
2387    `node' specifies the node object.
2388    `pid' specifies the ID number of referred page.
2389    The return value is whether the subtraction is completed. */
2390 static bool tcbdbnodesubidx(TCBDB *bdb, BDBNODE *node, uint64_t pid){
2391   assert(bdb && node && pid > 0);
2392   TCLIST *idxs = node->idxs;
2393   int ln = TCLISTNUM(idxs);
2394   if(ln < 2) return false;
2395   if(node->heir == pid){
2396     int rsiz;
2397     BDBIDX *idxp = (BDBIDX *)tclistshift(idxs, &rsiz);
2398     node->heir = idxp->pid;
2399     free(idxp->kbuf);
2400     free(idxp);
2401     node->dirty = true;
2402     return true;
2403   } else {
2404     int ln = TCLISTNUM(idxs);
2405     for(int i = 0; i < ln; i++){
2406       BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2407       if(idxp->pid == pid){
2408         int rsiz;
2409         free(idxp->kbuf);
2410         free(tclistremove(idxs, i, &rsiz));
2411         node->dirty = true;
2412         return true;
2413       }
2414     }
2415   }
2416   return false;
2417 }
2418
2419
2420 /* Search the leaf object corresponding to a key.
2421    `bdb' specifies the B+ tree database object.
2422    `kbuf' specifies the pointer to the region of the key.
2423    `ksiz' specifies the size of the region of the key.
2424    The return value is the ID number of the leaf object or 0 on failure. */
2425 static uint64_t tcbdbsearchleaf(TCBDB *bdb, const char *kbuf, int ksiz){
2426   assert(bdb && kbuf && ksiz >= 0);
2427   BDBCMP cmp = bdb->cmp;
2428   void *cmpop = bdb->cmpop;
2429   uint64_t *hist = bdb->hist;
2430   uint64_t pid = bdb->root;
2431   int hnum = 0;
2432   bdb->hleaf = 0;
2433   while(pid > BDBNODEIDBASE){
2434     BDBNODE *node = tcbdbnodeload(bdb, pid);
2435     if(!node){
2436       tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
2437       return 0;
2438     }
2439     TCLIST *idxs = node->idxs;
2440     int ln = TCLISTNUM(idxs);
2441     if(ln < 1){
2442       tcbdbsetecode(bdb, TCEMISC, __FILE__, __LINE__, __func__);
2443       return 0;
2444     }
2445     hist[hnum++] = node->id;
2446     int left = 0;
2447     int right = ln;
2448     int i = (left + right) / 2;
2449     BDBIDX *idxp = NULL;
2450     while(right >= left && i < ln){
2451       idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2452       int rv;
2453       if(cmp == tcbdbcmplexical){
2454         TCCMPLEXICAL(rv, kbuf, ksiz, idxp->kbuf, idxp->ksiz);
2455       } else {
2456         rv = cmp(kbuf, ksiz, idxp->kbuf, idxp->ksiz, cmpop);
2457       }
2458       if(rv == 0){
2459         break;
2460       } else if(rv <= 0){
2461         right = i - 1;
2462       } else {
2463         left = i + 1;
2464       }
2465       i = (left + right) / 2;
2466     }
2467     if(i > 0) i--;
2468     while(i < ln){
2469       idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2470       int rv;
2471       if(cmp == tcbdbcmplexical){
2472         TCCMPLEXICAL(rv, kbuf, ksiz, idxp->kbuf, idxp->ksiz);
2473       } else {
2474         rv = cmp(kbuf, ksiz, idxp->kbuf, idxp->ksiz, cmpop);
2475       }
2476       if(rv < 0){
2477         if(i == 0){
2478           pid = node->heir;
2479           break;
2480         }
2481         idxp = (BDBIDX *)TCLISTVALPTR(idxs, i - 1);
2482         pid = idxp->pid;
2483         break;
2484       }
2485       i++;
2486     }
2487     if(i >= ln) pid = idxp->pid;
2488   }
2489   if(!bdb->mmtx){
2490     if(bdb->lleaf == pid) bdb->hleaf = pid;
2491     bdb->lleaf = pid;
2492   }
2493   bdb->hnum = hnum;
2494   return pid;
2495 }
2496
2497
2498 /* Search a record of a leaf.
2499    `bdb' specifies the B+ tree database object.
2500    `leaf' specifies the leaf object.
2501    `kbuf' specifies the pointer to the region of the key.
2502    `ksiz' specifies the size of the region of the key.
2503    `ip' specifies the pointer to a variable to fetch the index of the correspnding record.
2504    The return value is the pointer to a corresponding record or `NULL' on failure. */
2505 static BDBREC *tcbdbsearchrec(TCBDB *bdb, BDBLEAF *leaf, const char *kbuf, int ksiz, int *ip){
2506   assert(bdb && leaf && kbuf && ksiz >= 0);
2507   BDBCMP cmp = bdb->cmp;
2508   void *cmpop = bdb->cmpop;
2509   TCLIST *recs = leaf->recs;
2510   int ln = TCLISTNUM(recs);
2511   int left = 0;
2512   int right = ln;
2513   int i = (left + right) / 2;
2514   while(right >= left && i < ln){
2515     BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
2516     int rv;
2517     if(cmp == tcbdbcmplexical){
2518       TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
2519     } else {
2520       rv = cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, cmpop);
2521     }
2522     if(rv == 0){
2523       if(ip) *ip = i;
2524       return recp;
2525     } else if(rv <= 0){
2526       right = i - 1;
2527     } else {
2528       left = i + 1;
2529     }
2530     i = (left + right) / 2;
2531   }
2532   if(ip) *ip = i;
2533   return NULL;
2534 }
2535
2536
2537 /* Adjust the caches for leaves and nodes.
2538    `bdb' specifies the B+ tree database object.
2539    The return value is true if successful, else, it is false. */
2540 static bool tcbdbcacheadjust(TCBDB *bdb){
2541   bool err = false;
2542   if(TCMAPRNUM(bdb->leafc) > bdb->lcnum){
2543     TCDODEBUG(bdb->cnt_adjleafc++);
2544     bool clk = BDBLOCKCACHE(bdb);
2545     TCMAP *leafc = bdb->leafc;
2546     tcmapiterinit(leafc);
2547     for(int i = 0; i < BDBCACHEOUT; i++){
2548       int rsiz;
2549       if(!tcbdbleafcacheout(bdb, (BDBLEAF *)tcmapiterval(tcmapiternext(leafc, &rsiz), &rsiz)))
2550         err = true;
2551     }
2552     if(clk) BDBUNLOCKCACHE(bdb);
2553   }
2554   if(TCMAPRNUM(bdb->nodec) > bdb->ncnum){
2555     TCDODEBUG(bdb->cnt_adjnodec++);
2556     bool clk = BDBLOCKCACHE(bdb);
2557     TCMAP *nodec = bdb->nodec;
2558     tcmapiterinit(nodec);
2559     for(int i = 0; i < BDBCACHEOUT; i++){
2560       int rsiz;
2561       if(!tcbdbnodecacheout(bdb, (BDBNODE *)tcmapiterval(tcmapiternext(nodec, &rsiz), &rsiz)))
2562         err = true;
2563     }
2564     if(clk) BDBUNLOCKCACHE(bdb);
2565   }
2566   return !err;
2567 }
2568
2569
2570 /* Purge dirty pages of caches for leaves and nodes.
2571    `bdb' specifies the B+ tree database object. */
2572 static void tcbdbcachepurge(TCBDB *bdb){
2573   bool clk = BDBLOCKCACHE(bdb);
2574   int tsiz;
2575   const char *tmp;
2576   tcmapiterinit(bdb->leafc);
2577   while((tmp = tcmapiternext(bdb->leafc, &tsiz)) != NULL){
2578     int lsiz;
2579     BDBLEAF *leaf = (BDBLEAF *)tcmapiterval(tmp, &lsiz);
2580     if(!leaf->dirty) continue;
2581     TCLIST *recs = leaf->recs;
2582     int ln = TCLISTNUM(recs);
2583     for(int i = 0; i < ln; i++){
2584       BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
2585       free(recp->kbuf);
2586       free(recp->vbuf);
2587       if(recp->rest) tclistdel(recp->rest);
2588     }
2589     tclistdel(recs);
2590     tcmapout(bdb->leafc, tmp, tsiz);
2591   }
2592   tcmapiterinit(bdb->nodec);
2593   while((tmp = tcmapiternext(bdb->nodec, &tsiz)) != NULL){
2594     int nsiz;
2595     BDBNODE *node = (BDBNODE *)tcmapiterval(tmp, &nsiz);
2596     if(!node->dirty) continue;
2597     TCLIST *idxs = node->idxs;
2598     int ln = TCLISTNUM(idxs);
2599     for(int i = 0; i < ln; i++){
2600       BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2601       free(idxp->kbuf);
2602     }
2603     tclistdel(idxs);
2604     tcmapout(bdb->nodec, tmp, tsiz);
2605   }
2606   if(clk) BDBUNLOCKCACHE(bdb);
2607 }
2608
2609
2610 /* Open a database file and connect a B+ tree database object.
2611    `bdb' specifies the B+ tree database object.
2612    `path' specifies the path of the internal database file.
2613    `omode' specifies the connection mode.
2614    If successful, the return value is true, else, it is false. */
2615 static bool tcbdbopenimpl(TCBDB *bdb, const char *path, int omode){
2616   assert(bdb && path);
2617   int homode = HDBOREADER;
2618   if(omode & BDBOWRITER){
2619     homode = HDBOWRITER;
2620     if(omode & BDBOCREAT) homode |= HDBOCREAT;
2621     if(omode & BDBOTRUNC) homode |= HDBOTRUNC;
2622     bdb->wmode = true;
2623   } else {
2624     bdb->wmode = false;
2625   }
2626   if(omode & BDBONOLCK) homode |= HDBONOLCK;
2627   if(omode & BDBOLCKNB) homode |= HDBOLCKNB;
2628   tchdbsettype(bdb->hdb, HDBTBTREE);
2629   if(!tchdbopen(bdb->hdb, path, homode)) return false;
2630   bdb->root = 0;
2631   bdb->first = 0;
2632   bdb->last = 0;
2633   bdb->lnum = 0;
2634   bdb->nnum = 0;
2635   bdb->rnum = 0;
2636   bdb->opaque = tchdbopaque(bdb->hdb);
2637   bdb->leafc = tcmapnew2(bdb->lcnum * 2 + 1);
2638   bdb->nodec = tcmapnew2(bdb->ncnum * 2 + 1);
2639   if(bdb->wmode && tchdbrnum(bdb->hdb) < 1){
2640     BDBLEAF *leaf = tcbdbleafnew(bdb, 0, 0);
2641     bdb->root = leaf->id;
2642     bdb->first = leaf->id;
2643     bdb->last = leaf->id;
2644     bdb->lnum = 1;
2645     bdb->nnum = 0;
2646     bdb->rnum = 0;
2647     if(!bdb->cmp){
2648       bdb->cmp = tcbdbcmplexical;
2649       bdb->cmpop = NULL;
2650     }
2651     tcdumpmeta(bdb);
2652     if(!tcbdbleafsave(bdb, leaf)){
2653       tcmapdel(bdb->nodec);
2654       tcmapdel(bdb->leafc);
2655       tchdbclose(bdb->hdb);
2656       return false;
2657     }
2658   }
2659   tcloadmeta(bdb);
2660   if(!bdb->cmp){
2661     tcbdbsetecode(bdb, TCEINVALID, __FILE__, __LINE__, __func__);
2662     tcmapdel(bdb->nodec);
2663     tcmapdel(bdb->leafc);
2664     tchdbclose(bdb->hdb);
2665     return false;
2666   }
2667   if(bdb->lmemb < BDBMINLMEMB || bdb->nmemb < BDBMINNMEMB ||
2668      bdb->root < 1 || bdb->first < 1 || bdb->last < 1 ||
2669      bdb->lnum < 0 || bdb->nnum < 0 || bdb->rnum < 0){
2670     tcbdbsetecode(bdb, TCEMETA, __FILE__, __LINE__, __func__);
2671     tcmapdel(bdb->nodec);
2672     tcmapdel(bdb->leafc);
2673     tchdbclose(bdb->hdb);
2674     return false;
2675   }
2676   bdb->open = true;
2677   uint8_t hopts = tchdbopts(bdb->hdb);
2678   uint8_t opts = 0;
2679   if(hopts & HDBTLARGE) opts |= BDBTLARGE;
2680   if(hopts & HDBTDEFLATE) opts |= BDBTDEFLATE;
2681   if(hopts & HDBTTCBS) opts |= BDBTTCBS;
2682   bdb->opts = opts;
2683   bdb->hleaf = 0;
2684   bdb->lleaf = 0;
2685   bdb->tran = false;
2686   bdb->rbopaque = NULL;
2687   return true;
2688 }
2689
2690
2691 /* Close a B+ tree database object.
2692    `bdb' specifies the B+ tree database object.
2693    If successful, the return value is true, else, it is false. */
2694 static bool tcbdbcloseimpl(TCBDB *bdb){
2695   assert(bdb);
2696   if(bdb->tran){
2697     tcbdbcachepurge(bdb);
2698     memcpy(bdb->opaque, bdb->rbopaque, BDBOPAQUESIZ);
2699     tcloadmeta(bdb);
2700     free(bdb->rbopaque);
2701     bdb->tran = false;
2702     bdb->rbopaque = NULL;
2703     BDBUNLOCKTRAN(bdb);
2704   }
2705   bool err = false;
2706   bdb->open = false;
2707   const char *vbuf;
2708   int vsiz;
2709   TCMAP *leafc = bdb->leafc;
2710   tcmapiterinit(leafc);
2711   while((vbuf = tcmapiternext(leafc, &vsiz)) != NULL){
2712     if(!tcbdbleafcacheout(bdb, (BDBLEAF *)tcmapiterval(vbuf, &vsiz))) err = true;
2713   }
2714   TCMAP *nodec = bdb->nodec;
2715   tcmapiterinit(nodec);
2716   while((vbuf = tcmapiternext(nodec, &vsiz)) != NULL){
2717     if(!tcbdbnodecacheout(bdb, (BDBNODE *)tcmapiterval(vbuf, &vsiz))) err = true;
2718   }
2719   if(bdb->wmode) tcdumpmeta(bdb);
2720   tcmapdel(bdb->nodec);
2721   tcmapdel(bdb->leafc);
2722   if(!tchdbclose(bdb->hdb)) err = true;
2723   return !err;
2724 }
2725
2726
2727 /* Store a record into a B+ tree database object.
2728    `bdb' specifies the B+ tree database object.
2729    `kbuf' specifies the pointer to the region of the key.
2730    `ksiz' specifies the size of the region of the key.
2731    `vbuf' specifies the pointer to the region of the value.
2732    `vsiz' specifies the size of the region of the value.
2733    `dmode' specifies behavior when the key overlaps.
2734    If successful, the return value is true, else, it is false. */
2735 static bool tcbdbputimpl(TCBDB *bdb, const void *kbuf, int ksiz, const void *vbuf, int vsiz,
2736                          int dmode){
2737   assert(bdb && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
2738   BDBLEAF *leaf = NULL;
2739   if(bdb->hleaf < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz))){
2740     uint64_t pid = tcbdbsearchleaf(bdb, kbuf, ksiz);
2741     if(pid < 1) return false;
2742     if(!(leaf = tcbdbleafload(bdb, pid))) return false;
2743   }
2744   if(!tcbdbleafaddrec(bdb, leaf, dmode, kbuf, ksiz, vbuf, vsiz)){
2745     tcbdbsetecode(bdb, TCEKEEP, __FILE__, __LINE__, __func__);
2746     return false;
2747   }
2748   int rnum = TCLISTNUM(leaf->recs);
2749   if(rnum > bdb->lmemb ||
2750      (bdb->lsmax > 0 && rnum > BDBMINLMEMB && (bdb->lschk++ & (0x8 - 1)) == 0 &&
2751       tcbdbleafdatasize(leaf) > bdb->lsmax)){
2752     bdb->lschk = 0;
2753     BDBLEAF *newleaf = tcbdbleafdivide(bdb, leaf);
2754     if(!newleaf) return false;
2755     if(leaf->id == bdb->last) bdb->last = newleaf->id;
2756     uint64_t heir = leaf->id;
2757     uint64_t pid = newleaf->id;
2758     BDBREC *recp = (BDBREC *)TCLISTVALPTR(newleaf->recs, 0);
2759     int ksiz = recp->ksiz;
2760     char *kbuf;
2761     TCMEMDUP(kbuf, recp->kbuf, ksiz);
2762     while(true){
2763       BDBNODE *node;
2764       if(bdb->hnum < 1){
2765         node = tcbdbnodenew(bdb, heir);
2766         tcbdbnodeaddidx(bdb, node, true, pid, kbuf, ksiz);
2767         bdb->root = node->id;
2768         free(kbuf);
2769         break;
2770       }
2771       uint64_t parent = bdb->hist[--bdb->hnum];
2772       if(!(node = tcbdbnodeload(bdb, parent))){
2773         free(kbuf);
2774         return false;
2775       }
2776       tcbdbnodeaddidx(bdb, node, false, pid, kbuf, ksiz);
2777       free(kbuf);
2778       TCLIST *idxs = node->idxs;
2779       int ln = TCLISTNUM(idxs);
2780       if(ln <= bdb->nmemb) break;
2781       int mid = ln / 2;
2782       BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, mid);
2783       BDBNODE *newnode = tcbdbnodenew(bdb, idxp->pid);
2784       heir = node->id;
2785       pid = newnode->id;
2786       TCMEMDUP(kbuf, idxp->kbuf, idxp->ksiz);
2787       ksiz = idxp->ksiz;
2788       for(int i = mid + 1; i < ln; i++){
2789         idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
2790         tcbdbnodeaddidx(bdb, newnode, true, idxp->pid, idxp->kbuf, idxp->ksiz);
2791       }
2792       ln = TCLISTNUM(newnode->idxs);
2793       for(int i = 0; i < ln; i++){
2794         int rsiz;
2795         idxp = (BDBIDX *)tclistpop(idxs, &rsiz);
2796         free(idxp->kbuf);
2797         free(idxp);
2798       }
2799       node->dirty = true;
2800     }
2801     if(bdb->capnum > 0 && bdb->rnum > bdb->capnum){
2802       uint64_t xnum = bdb->rnum - bdb->capnum;
2803       BDBCUR *cur = tcbdbcurnew(bdb);
2804       tcbdbcurfirstimpl(cur);
2805       while((xnum--) > 0){
2806         if(!tcbdbcuroutimpl(cur)){
2807           tcbdbcurdel(cur);
2808           return false;
2809         }
2810       }
2811       tcbdbcurdel(cur);
2812     }
2813   }
2814   if(!bdb->tran && !tcbdbcacheadjust(bdb)) return false;
2815   return true;
2816 }
2817
2818
2819 /* Remove a record of a B+ tree database object.
2820    `hdb' specifies the B+ tree database object.
2821    `kbuf' specifies the pointer to the region of the key.
2822    `ksiz' specifies the size of the region of the key.
2823    If successful, the return value is true, else, it is false. */
2824 static bool tcbdboutimpl(TCBDB *bdb, const char *kbuf, int ksiz){
2825   assert(bdb && kbuf && ksiz >= 0);
2826   BDBLEAF *leaf = NULL;
2827   if(bdb->hleaf < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz))){
2828     uint64_t pid = tcbdbsearchleaf(bdb, kbuf, ksiz);
2829     if(pid < 1) return false;
2830     if(!(leaf = tcbdbleafload(bdb, pid))) return false;
2831   }
2832   int ri;
2833   BDBREC *recp = tcbdbsearchrec(bdb, leaf, kbuf, ksiz, &ri);
2834   if(!recp){
2835     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
2836     return false;
2837   }
2838   if(recp->rest){
2839     free(recp->vbuf);
2840     recp->vbuf = tclistshift(recp->rest, &(recp->vsiz));
2841     if(TCLISTNUM(recp->rest) < 1){
2842       tclistdel(recp->rest);
2843       recp->rest = NULL;
2844     }
2845   } else {
2846     free(recp->vbuf);
2847     free(recp->kbuf);
2848     int rsiz;
2849     free(tclistremove(leaf->recs, ri, &rsiz));
2850   }
2851   leaf->dirty = true;
2852   bdb->rnum--;
2853   if(TCLISTNUM(leaf->recs) < 1 && bdb->hnum > 0 && !tcbdbleafkill(bdb, leaf)) return false;
2854   if(!bdb->tran && !tcbdbcacheadjust(bdb)) return false;
2855   return true;
2856 }
2857
2858
2859 /* Remove records of a B+ tree database object.
2860    `bdb' specifies the B+ tree database object.
2861    `kbuf' specifies the pointer to the region of the key.
2862    `ksiz' specifies the size of the region of the key.
2863    If successful, the return value is true, else, it is false. */
2864 static bool tcbdboutlist(TCBDB *bdb, const char *kbuf, int ksiz){
2865   assert(bdb && kbuf && ksiz >= 0);
2866   BDBLEAF *leaf = NULL;
2867   if(bdb->hleaf < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz))){
2868     uint64_t pid = tcbdbsearchleaf(bdb, kbuf, ksiz);
2869     if(pid < 1) return false;
2870     if(!(leaf = tcbdbleafload(bdb, pid))) return false;
2871   }
2872   int ri;
2873   BDBREC *recp = tcbdbsearchrec(bdb, leaf, kbuf, ksiz, &ri);
2874   if(!recp){
2875     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
2876     return false;
2877   }
2878   int rnum = 1;
2879   if(recp->rest){
2880     rnum += TCLISTNUM(recp->rest);
2881     tclistdel(recp->rest);
2882   }
2883   free(recp->vbuf);
2884   free(recp->kbuf);
2885   int rsiz;
2886   free(tclistremove(leaf->recs, ri, &rsiz));
2887   leaf->dirty = true;
2888   bdb->rnum -= rnum;
2889   if(TCLISTNUM(leaf->recs) < 1 && bdb->hnum > 0 && !tcbdbleafkill(bdb, leaf)) return false;
2890   if(!bdb->tran && !tcbdbcacheadjust(bdb)) return false;
2891   return true;
2892 }
2893
2894
2895 /* Retrieve a record in a B+ tree database object.
2896    `bdb' specifies the B+ tree database object.
2897    `kbuf' specifies the pointer to the region of the key.
2898    `ksiz' specifies the size of the region of the key.
2899    `sp' specifies the pointer to the variable into which the size of the region of the return
2900    value is assigned.
2901    If successful, the return value is the pointer to the region of the value of the corresponding
2902    record. */
2903 static const char *tcbdbgetimpl(TCBDB *bdb, const char *kbuf, int ksiz, int *sp){
2904   assert(bdb && kbuf && ksiz >= 0 && sp);
2905   BDBLEAF *leaf = NULL;
2906   if(bdb->hleaf < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz))){
2907     uint64_t pid = tcbdbsearchleaf(bdb, kbuf, ksiz);
2908     if(pid < 1) return NULL;
2909     if(!(leaf = tcbdbleafload(bdb, pid))) return NULL;
2910   }
2911   BDBREC *recp = tcbdbsearchrec(bdb, leaf, kbuf, ksiz, NULL);
2912   if(!recp){
2913     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
2914     return NULL;
2915   }
2916   *sp = recp->vsiz;
2917   return recp->vbuf;
2918 }
2919
2920
2921 /* Get the number of records corresponding a key in a B+ tree database object.
2922    `bdb' specifies the B+ tree database object.
2923    `kbuf' specifies the pointer to the region of the key.
2924    `ksiz' specifies the size of the region of the key.
2925    If successful, the return value is the number of the corresponding records, else, it is 0. */
2926 static int tcbdbgetnum(TCBDB *bdb, const char *kbuf, int ksiz){
2927   assert(bdb && kbuf && ksiz >= 0);
2928   BDBLEAF *leaf = NULL;
2929   if(bdb->hleaf < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz))){
2930     uint64_t pid = tcbdbsearchleaf(bdb, kbuf, ksiz);
2931     if(pid < 1) return 0;
2932     if(!(leaf = tcbdbleafload(bdb, pid))) return 0;
2933   }
2934   BDBREC *recp = tcbdbsearchrec(bdb, leaf, kbuf, ksiz, NULL);
2935   if(!recp){
2936     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
2937     return 0;
2938   }
2939   return recp->rest ? TCLISTNUM(recp->rest) + 1 : 1;
2940 }
2941
2942
2943 /* Retrieve records in a B+ tree database object.
2944    `bdb' specifies the B+ tree database object.
2945    `kbuf' specifies the pointer to the region of the key.
2946    `ksiz' specifies the size of the region of the key.
2947    If successful, the return value is a list object of the values of the corresponding records. */
2948 static TCLIST *tcbdbgetlist(TCBDB *bdb, const char *kbuf, int ksiz){
2949   assert(bdb && kbuf && ksiz >= 0);
2950   BDBLEAF *leaf = NULL;
2951   if(bdb->hleaf < 1 || !(leaf = tcbdbgethistleaf(bdb, kbuf, ksiz))){
2952     uint64_t pid = tcbdbsearchleaf(bdb, kbuf, ksiz);
2953     if(pid < 1) return NULL;
2954     if(!(leaf = tcbdbleafload(bdb, pid))) return NULL;
2955   }
2956   BDBREC *recp = tcbdbsearchrec(bdb, leaf, kbuf, ksiz, NULL);
2957   if(!recp){
2958     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
2959     return NULL;
2960   }
2961   TCLIST *vals;
2962   TCLIST *rest = recp->rest;
2963   if(rest){
2964     int ln = TCLISTNUM(rest);
2965     vals = tclistnew2(ln + 1);
2966     TCLISTPUSH(vals, recp->vbuf, recp->vsiz);
2967     for(int i = 0; i < ln; i++){
2968       int vsiz;
2969       const char *vbuf = tclistval(rest, i, &vsiz);
2970       TCLISTPUSH(vals, vbuf, vsiz);
2971     }
2972   } else {
2973     vals = tclistnew2(1);
2974     TCLISTPUSH(vals, recp->vbuf, recp->vsiz);
2975   }
2976   return vals;
2977 }
2978
2979
2980 /* Get keys of ranged records in a B+ tree database object.
2981    `bdb' specifies the B+ tree database object.
2982    `bkbuf' specifies the pointer to the region of the key of the beginning border.
2983    `bksiz' specifies the size of the region of the beginning key.
2984    `binc' specifies whether the beginning border is inclusive or not.
2985    `ekbuf' specifies the pointer to the region of the key of the ending border.
2986    `eksiz' specifies the size of the region of the ending key.
2987    `einc' specifies whether the ending border is inclusive or not.
2988    `max' specifies the maximum number of keys to be fetched.
2989    `keys' specifies a list object to store the result.
2990    If successful, the return value is true, else, it is false. */
2991 static bool tcbdbrangeimpl(TCBDB *bdb, const char *bkbuf, int bksiz, bool binc,
2992                            const char *ekbuf, int eksiz, bool einc, int max, TCLIST *keys){
2993   assert(bdb && keys);
2994   bool err = false;
2995   BDBCUR *cur = tcbdbcurnew(bdb);
2996   if(bkbuf){
2997     tcbdbcurjumpimpl(cur, bkbuf, bksiz, true);
2998   } else {
2999     tcbdbcurfirstimpl(cur);
3000   }
3001   BDBCMP cmp = bdb->cmp;
3002   void *cmpop = bdb->cmpop;
3003   const char *lbuf = NULL;
3004   int lsiz = 0;
3005   while(cur->id > 0){
3006     const char *kbuf, *vbuf;
3007     int ksiz, vsiz;
3008     if(!tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
3009       if(tchdbecode(bdb->hdb) != TCEINVALID && tchdbecode(bdb->hdb) != TCENOREC) err = true;
3010       break;
3011     }
3012     if(bkbuf && !binc){
3013       if(cmp(kbuf, ksiz, bkbuf, bksiz, cmpop) == 0){
3014         tcbdbcurnext(cur);
3015         continue;
3016       }
3017       bkbuf = NULL;
3018     }
3019     if(ekbuf){
3020       if(einc){
3021         if(cmp(kbuf, ksiz, ekbuf, eksiz, cmpop) > 0) break;
3022       } else {
3023         if(cmp(kbuf, ksiz, ekbuf, eksiz, cmpop) >= 0) break;
3024       }
3025     }
3026     if(!lbuf || lsiz != ksiz || memcmp(kbuf, lbuf, ksiz)){
3027       TCLISTPUSH(keys, kbuf, ksiz);
3028       if(max >= 0 && TCLISTNUM(keys) >= max) break;
3029       lbuf = kbuf;
3030       lsiz = ksiz;
3031     }
3032     tcbdbcurnextimpl(cur);
3033   }
3034   tcbdbcurdel(cur);
3035   return !err;
3036 }
3037
3038
3039 /* Get forward matching keys in a B+ tree database object.
3040    `bdb' specifies the B+ tree database object.
3041    `pbuf' specifies the pointer to the region of the prefix.
3042    `psiz' specifies the size of the region of the prefix.
3043    `max' specifies the maximum number of keys to be fetched.
3044    `keys' specifies a list object to store the result.
3045    If successful, the return value is true, else, it is false. */
3046 static bool tcbdbrangefwm(TCBDB *bdb, const char *pbuf, int psiz, int max, TCLIST *keys){
3047   assert(bdb && pbuf && psiz >= 0 && keys);
3048   bool err = false;
3049   if(max < 0) max = INT_MAX;
3050   BDBCUR *cur = tcbdbcurnew(bdb);
3051   tcbdbcurjumpimpl(cur, pbuf, psiz, true);
3052   const char *lbuf = NULL;
3053   int lsiz = 0;
3054   while(cur->id > 0){
3055     const char *kbuf, *vbuf;
3056     int ksiz, vsiz;
3057     if(!tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
3058       if(tchdbecode(bdb->hdb) != TCEINVALID && tchdbecode(bdb->hdb) != TCENOREC) err = true;
3059       break;
3060     }
3061     if(ksiz < psiz || memcmp(kbuf, pbuf, psiz)) break;
3062     if(!lbuf || lsiz != ksiz || memcmp(kbuf, lbuf, ksiz)){
3063       TCLISTPUSH(keys, kbuf, ksiz);
3064       if(TCLISTNUM(keys) >= max) break;
3065       lbuf = kbuf;
3066       lsiz = ksiz;
3067     }
3068     tcbdbcurnextimpl(cur);
3069   }
3070   tcbdbcurdel(cur);
3071   return !err;
3072 }
3073
3074
3075 /* Optimize the file of a B+ tree database object.
3076    `bdb' specifies the B+ tree database object.
3077    `lmemb' specifies the number of members in each leaf page.
3078    `nmemb' specifies the number of members in each non-leaf page.
3079    `bnum' specifies the number of elements of the bucket array.
3080    `apow' specifies the size of record alignment by power of 2.
3081    `fpow' specifies the maximum number of elements of the free block pool by power of 2.
3082    `opts' specifies options by bitwise or.
3083    If successful, the return value is true, else, it is false. */
3084 static bool tcbdboptimizeimpl(TCBDB *bdb, int32_t lmemb, int32_t nmemb,
3085                               int64_t bnum, int8_t apow, int8_t fpow, uint8_t opts){
3086   assert(bdb);
3087   if(lmemb < 1) lmemb = bdb->lmemb;
3088   if(nmemb < 1) nmemb = bdb->nmemb;
3089   if(bnum < 1) bnum = tchdbrnum(bdb->hdb) * 2 + 1;
3090   if(opts == UINT8_MAX) opts = bdb->opts;
3091   const char *path = tchdbpath(bdb->hdb);
3092   char *tpath = tcsprintf("%s%ctmp%c%llu", path, MYEXTCHR, MYEXTCHR, tchdbinode(bdb->hdb));
3093   TCBDB *tbdb = tcbdbnew();
3094   tcbdbsetcmpfunc(tbdb, bdb->cmp, bdb->cmpop);
3095   tcbdbtune(tbdb, lmemb, nmemb, bnum, apow, fpow, opts);
3096   tcbdbsetlsmax(tbdb, bdb->lsmax);
3097   if(!tcbdbopen(tbdb, tpath, BDBOWRITER | BDBOCREAT | BDBOTRUNC)){
3098     tcbdbsetecode(bdb, tcbdbecode(tbdb), __FILE__, __LINE__, __func__);
3099     tcbdbdel(tbdb);
3100     free(tpath);
3101     return false;
3102   }
3103   bool err = false;
3104   BDBCUR *cur = tcbdbcurnew(bdb);
3105   tcbdbcurfirstimpl(cur);
3106   const char *kbuf, *vbuf;
3107   int ksiz, vsiz;
3108   while(!err && cur->id > 0 && tcbdbcurrecimpl(cur, &kbuf, &ksiz, &vbuf, &vsiz)){
3109     if(!tcbdbputdup(tbdb, kbuf, ksiz, vbuf, vsiz)){
3110       tcbdbsetecode(bdb, tcbdbecode(tbdb), __FILE__, __LINE__, __func__);
3111       err = true;
3112     }
3113     tcbdbcurnextimpl(cur);
3114   }
3115   tcbdbcurdel(cur);
3116   if(!tcbdbclose(tbdb)){
3117     tcbdbsetecode(bdb, tcbdbecode(tbdb), __FILE__, __LINE__, __func__);
3118     err = true;
3119   }
3120   tcbdbdel(tbdb);
3121   if(unlink(path) == -1){
3122     tcbdbsetecode(bdb, TCEUNLINK, __FILE__, __LINE__, __func__);
3123     err = true;
3124   }
3125   if(rename(tpath, path) == -1){
3126     tcbdbsetecode(bdb, TCERENAME, __FILE__, __LINE__, __func__);
3127     err = true;
3128   }
3129   free(tpath);
3130   if(err) return false;
3131   tpath = tcstrdup(path);
3132   int omode = (tchdbomode(bdb->hdb) & ~BDBOCREAT) & ~BDBOTRUNC;
3133   if(!tcbdbcloseimpl(bdb)){
3134     free(tpath);
3135     return false;
3136   }
3137   bool rv = tcbdbopenimpl(bdb, tpath, omode);
3138   free(tpath);
3139   return rv;
3140 }
3141
3142
3143 /* Remove all records of a B+ tree database object.
3144    `bdb' specifies the B+ tree database object.
3145    If successful, the return value is true, else, it is false. */
3146 static bool tcbdbvanishimpl(TCBDB *bdb){
3147   assert(bdb);
3148   char *path = tcstrdup(tchdbpath(bdb->hdb));
3149   int omode = tchdbomode(bdb->hdb);
3150   bool err = false;
3151   if(!tcbdbcloseimpl(bdb)) err = true;
3152   if(!tcbdbopenimpl(bdb, path, BDBOTRUNC | omode)) err = true;
3153   free(path);
3154   return !err;
3155 }
3156
3157
3158 /* Lock a method of the B+ tree database object.
3159    `bdb' specifies the B+ tree database object.
3160    `wr' specifies whether the lock is writer or not.
3161    If successful, the return value is true, else, it is false. */
3162 static bool tcbdblockmethod(TCBDB *bdb, bool wr){
3163   assert(bdb);
3164   if(wr ? pthread_rwlock_wrlock(bdb->mmtx) != 0 : pthread_rwlock_rdlock(bdb->mmtx) != 0){
3165     tcbdbsetecode(bdb, TCETHREAD, __FILE__, __LINE__, __func__);
3166     return false;
3167   }
3168   TCTESTYIELD();
3169   return true;
3170 }
3171
3172
3173 /* Unlock a method of the B+ tree database object.
3174    `hdb' specifies the B+ tree database object.
3175    If successful, the return value is true, else, it is false. */
3176 static bool tcbdbunlockmethod(TCBDB *bdb){
3177   assert(bdb);
3178   if(pthread_rwlock_unlock(bdb->mmtx) != 0){
3179     tcbdbsetecode(bdb, TCETHREAD, __FILE__, __LINE__, __func__);
3180     return false;
3181   }
3182   TCTESTYIELD();
3183   return true;
3184 }
3185
3186
3187 /* Lock the cache of the B+ tree database object.
3188    `hdb' specifies the B+ tree database object.
3189    If successful, the return value is true, else, it is false. */
3190 static bool tcbdblockcache(TCBDB *bdb){
3191   assert(bdb);
3192   if(pthread_mutex_lock(bdb->cmtx) != 0){
3193     tcbdbsetecode(bdb, TCETHREAD, __FILE__, __LINE__, __func__);
3194     return false;
3195   }
3196   TCTESTYIELD();
3197   return true;
3198 }
3199
3200
3201 /* Unlock the cache of the B+ tree database object.
3202    `hdb' specifies the B+ tree database object.
3203    If successful, the return value is true, else, it is false. */
3204 static bool tcbdbunlockcache(TCBDB *bdb){
3205   assert(bdb);
3206   if(pthread_mutex_unlock(bdb->cmtx) != 0){
3207     tcbdbsetecode(bdb, TCETHREAD, __FILE__, __LINE__, __func__);
3208     return false;
3209   }
3210   TCTESTYIELD();
3211   return true;
3212 }
3213
3214
3215 /* Lock the transaction of the B+ tree database object.
3216    `hdb' specifies the B+ tree database object.
3217    If successful, the return value is true, else, it is false. */
3218 static bool tcbdblocktran(TCBDB *bdb){
3219   assert(bdb);
3220   if(pthread_mutex_lock(bdb->tmtx) != 0){
3221     tcbdbsetecode(bdb, TCETHREAD, __FILE__, __LINE__, __func__);
3222     return false;
3223   }
3224   TCTESTYIELD();
3225   return true;
3226 }
3227
3228
3229 /* Unlock the transaction of the B+ tree database object.
3230    `hdb' specifies the B+ tree database object.
3231    If successful, the return value is true, else, it is false. */
3232 static bool tcbdbunlocktran(TCBDB *bdb){
3233   assert(bdb);
3234   if(pthread_mutex_unlock(bdb->tmtx) != 0){
3235     tcbdbsetecode(bdb, TCETHREAD, __FILE__, __LINE__, __func__);
3236     return false;
3237   }
3238   TCTESTYIELD();
3239   return true;
3240 }
3241
3242
3243 /* Move a cursor object to the first record.
3244    `cur' specifies the cursor object.
3245    If successful, the return value is true, else, it is false. */
3246 static bool tcbdbcurfirstimpl(BDBCUR *cur){
3247   assert(cur);
3248   cur->id = cur->bdb->first;
3249   cur->kidx = 0;
3250   cur->vidx = 0;
3251   return tcbdbcuradjust(cur, true);
3252 }
3253
3254
3255 /* Move a cursor object to the last record.
3256    `cur' specifies the cursor object.
3257    If successful, the return value is true, else, it is false. */
3258 static bool tcbdbcurlastimpl(BDBCUR *cur){
3259   assert(cur);
3260   cur->id = cur->bdb->last;
3261   cur->kidx = INT_MAX;
3262   cur->vidx = INT_MAX;
3263   return tcbdbcuradjust(cur, false);
3264 }
3265
3266
3267 /* Move a cursor object to around records corresponding a key.
3268    `cur' specifies the cursor object.
3269    `kbuf' specifies the pointer to the region of the key.
3270    `ksiz' specifies the size of the region of the key.
3271    `forward' specifies whether the cursor is to be the front of records.
3272    If successful, the return value is true, else, it is false. */
3273 static bool tcbdbcurjumpimpl(BDBCUR *cur, const char *kbuf, int ksiz, bool forward){
3274   assert(cur && kbuf && ksiz >= 0);
3275   TCBDB *bdb = cur->bdb;
3276   uint64_t pid = tcbdbsearchleaf(bdb, kbuf, ksiz);
3277   if(pid < 1){
3278     cur->id = 0;
3279     cur->kidx = 0;
3280     cur->vidx = 0;
3281     return false;
3282   }
3283   BDBLEAF *leaf = tcbdbleafload(bdb, pid);
3284   if(!leaf){
3285     cur->id = 0;
3286     cur->kidx = 0;
3287     cur->vidx = 0;
3288     return false;
3289   }
3290   if(TCLISTNUM(leaf->recs) < 1){
3291     cur->id = pid;
3292     cur->kidx = 0;
3293     cur->vidx = 0;
3294     return forward ? tcbdbcurnextimpl(cur) : tcbdbcurprevimpl(cur);
3295   }
3296   int ri;
3297   BDBREC *recp = tcbdbsearchrec(bdb, leaf, kbuf, ksiz, &ri);
3298   if(recp){
3299     cur->id = pid;
3300     cur->kidx = ri;
3301     if(forward){
3302       cur->vidx = 0;
3303     } else {
3304       cur->vidx = recp->rest ? TCLISTNUM(recp->rest) : 0;
3305     }
3306     return true;
3307   }
3308   cur->id = leaf->id;
3309   if(ri > 0 && ri >= TCLISTNUM(leaf->recs)) ri = TCLISTNUM(leaf->recs) - 1;
3310   cur->kidx = ri;
3311   recp = (BDBREC *)TCLISTVALPTR(leaf->recs, ri);
3312   if(forward){
3313     int rv;
3314     if(bdb->cmp == tcbdbcmplexical){
3315       TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
3316     } else {
3317       rv = bdb->cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, bdb->cmpop);
3318     }
3319     if(rv < 0) return true;
3320     cur->vidx = recp->rest ? TCLISTNUM(recp->rest) : 0;
3321     return tcbdbcurnextimpl(cur);
3322   }
3323   int rv;
3324   if(bdb->cmp == tcbdbcmplexical){
3325     TCCMPLEXICAL(rv, kbuf, ksiz, recp->kbuf, recp->ksiz);
3326   } else {
3327     rv = bdb->cmp(kbuf, ksiz, recp->kbuf, recp->ksiz, bdb->cmpop);
3328   }
3329   if(rv > 0) return true;
3330   cur->vidx = 0;
3331   return tcbdbcurprevimpl(cur);
3332 }
3333
3334
3335 /* Adjust a cursor object forward to the suitable record.
3336    `cur' specifies the cursor object.
3337    If successful, the return value is true, else, it is false. */
3338 static bool tcbdbcuradjust(BDBCUR *cur, bool forward){
3339   assert(cur);
3340   TCBDB *bdb = cur->bdb;
3341   while(true){
3342     if(cur->id < 1){
3343       tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
3344       cur->id = 0;
3345       cur->kidx = 0;
3346       cur->vidx = 0;
3347       return false;
3348     }
3349     BDBLEAF *leaf = tcbdbleafload(bdb, cur->id);
3350     if(!leaf) return false;
3351     TCLIST *recs = leaf->recs;
3352     int knum = TCLISTNUM(recs);
3353     if(cur->kidx < 0){
3354       if(forward){
3355         cur->kidx = 0;
3356         cur->vidx = 0;
3357       } else {
3358         cur->id = leaf->prev;
3359         cur->kidx = INT_MAX;
3360         cur->vidx = INT_MAX;
3361       }
3362     } else if(cur->kidx >= knum){
3363       if(forward){
3364         cur->id = leaf->next;
3365         cur->kidx = 0;
3366         cur->vidx = 0;
3367       } else {
3368         cur->kidx = knum - 1;
3369         cur->vidx = INT_MAX;
3370       }
3371     } else {
3372       BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, cur->kidx);
3373       int vnum = recp->rest ? TCLISTNUM(recp->rest) + 1 : 1;
3374       if(cur->vidx < 0){
3375         if(forward){
3376           cur->vidx = 0;
3377         } else {
3378           cur->kidx--;
3379           cur->vidx = INT_MAX;
3380         }
3381       } else if(cur->vidx >= vnum){
3382         if(forward){
3383           cur->kidx++;
3384           cur->vidx = 0;
3385           if(cur->kidx >= knum){
3386             cur->id = leaf->next;
3387             cur->kidx = 0;
3388             cur->vidx = 0;
3389           } else {
3390             break;
3391           }
3392         } else {
3393           cur->vidx = vnum - 1;
3394           if(cur->vidx >= 0) break;
3395         }
3396       } else {
3397         break;
3398       }
3399     }
3400   }
3401   return true;
3402 }
3403
3404
3405 /* Move a cursor object to the previous record.
3406    `cur' specifies the cursor object.
3407    If successful, the return value is true, else, it is false. */
3408 static bool tcbdbcurprevimpl(BDBCUR *cur){
3409   assert(cur);
3410   cur->vidx--;
3411   return tcbdbcuradjust(cur, false);
3412 }
3413
3414
3415 /* Move a cursor object to the next record.
3416    `cur' specifies the cursor object.
3417    If successful, the return value is true, else, it is false. */
3418 static bool tcbdbcurnextimpl(BDBCUR *cur){
3419   assert(cur);
3420   cur->vidx++;
3421   return tcbdbcuradjust(cur, true);
3422 }
3423
3424
3425 /* Insert a record around a cursor object.
3426    `cur' specifies the cursor object.
3427    `vbuf' specifies the pointer to the region of the value.
3428    `vsiz' specifies the size of the region of the value.
3429    `cpmode' specifies detail adjustment.
3430    If successful, the return value is true, else, it is false. */
3431 static bool tcbdbcurputimpl(BDBCUR *cur, const char *vbuf, int vsiz, int cpmode){
3432   assert(cur && vbuf && vsiz >= 0);
3433   TCBDB *bdb = cur->bdb;
3434   BDBLEAF *leaf = tcbdbleafload(bdb, cur->id);
3435   if(!leaf) return false;
3436   TCLIST *recs = leaf->recs;
3437   if(cur->kidx >= TCLISTNUM(recs)){
3438     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
3439     return false;
3440   }
3441   BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, cur->kidx);
3442   int vnum = recp->rest ? TCLISTNUM(recp->rest) + 1 : 1;
3443   if(cur->vidx >= vnum){
3444     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
3445     return false;
3446   }
3447   switch(cpmode){
3448   case BDBCPCURRENT:
3449     if(cur->vidx < 1){
3450       if(vsiz > recp->vsiz) TCREALLOC(recp->vbuf, recp->vbuf, vsiz + 1);
3451       memcpy(recp->vbuf, vbuf, vsiz);
3452       recp->vbuf[vsiz] = '\0';
3453       recp->vsiz = vsiz;
3454     } else {
3455       tclistover(recp->rest, cur->vidx - 1, vbuf, vsiz);
3456     }
3457     break;
3458   case BDBCPBEFORE:
3459     if(cur->vidx < 1){
3460       if(!recp->rest) recp->rest = tclistnew();
3461       tclistunshift(recp->rest, recp->vbuf, recp->vsiz);
3462       if(vsiz > recp->vsiz) TCREALLOC(recp->vbuf, recp->vbuf, vsiz + 1);
3463       memcpy(recp->vbuf, vbuf, vsiz);
3464       recp->vbuf[vsiz] = '\0';
3465       recp->vsiz = vsiz;
3466     } else {
3467       tclistinsert(recp->rest, cur->vidx - 1, vbuf, vsiz);
3468     }
3469     bdb->rnum++;
3470     break;
3471   case BDBCPAFTER:
3472     if(!recp->rest) recp->rest = tclistnew();
3473     tclistinsert(recp->rest, cur->vidx, vbuf, vsiz);
3474     cur->vidx++;
3475     bdb->rnum++;
3476     break;
3477   }
3478   leaf->dirty = true;
3479   return true;
3480 }
3481
3482
3483 /* Delete the record where a cursor object is.
3484    `cur' specifies the cursor object.
3485    If successful, the return value is true, else, it is false. */
3486 static bool tcbdbcuroutimpl(BDBCUR *cur){
3487   assert(cur);
3488   TCBDB *bdb = cur->bdb;
3489   BDBLEAF *leaf = tcbdbleafload(bdb, cur->id);
3490   if(!leaf) return false;
3491   TCLIST *recs = leaf->recs;
3492   if(cur->kidx >= TCLISTNUM(recs)){
3493     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
3494     return false;
3495   }
3496   BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, cur->kidx);
3497   int vnum = recp->rest ? TCLISTNUM(recp->rest) + 1 : 1;
3498   if(cur->vidx >= vnum){
3499     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
3500     return false;
3501   }
3502   if(recp->rest){
3503     if(cur->vidx < 1){
3504       free(recp->vbuf);
3505       recp->vbuf = tclistshift(recp->rest, &(recp->vsiz));
3506     } else {
3507       int vsiz;
3508       free(tclistremove(recp->rest, cur->vidx - 1, &vsiz));
3509     }
3510     if(TCLISTNUM(recp->rest) < 1){
3511       tclistdel(recp->rest);
3512       recp->rest = NULL;
3513     }
3514   } else {
3515     if(TCLISTNUM(recs) < 2 && bdb->hnum > 0){
3516       uint64_t pid = tcbdbsearchleaf(bdb, recp->kbuf, recp->ksiz);
3517       if(pid < 1) return false;
3518       if(!(leaf = tcbdbleafload(bdb, pid))) return false;
3519       if(!tcbdbleafkill(bdb, leaf)) return false;
3520     }
3521     free(recp->vbuf);
3522     free(recp->kbuf);
3523     int rsiz;
3524     free(tclistremove(leaf->recs, cur->kidx, &rsiz));
3525   }
3526   bdb->rnum--;
3527   leaf->dirty = true;
3528   return tcbdbcuradjust(cur, true) || tchdbecode(bdb->hdb) == TCENOREC;
3529 }
3530
3531
3532 /* Get the key and the value of the current record of the cursor object.
3533    `cur' specifies the cursor object.
3534    `kbp' specifies the pointer to the variable into which the pointer to the region of the key is
3535    assgined.
3536    `ksp' specifies the pointer to the variable into which the size of the key region is assigned.
3537    `vbp' specifies the pointer to the variable into which the pointer to the region of the value
3538    is assgined.
3539    `vsp' specifies the pointer to the variable into which the size of the value region is
3540    assigned. */
3541 static bool tcbdbcurrecimpl(BDBCUR *cur, const char **kbp, int *ksp, const char **vbp, int *vsp){
3542   assert(cur && kbp && ksp && vbp && vsp);
3543   TCBDB *bdb = cur->bdb;
3544   BDBLEAF *leaf = tcbdbleafload(bdb, cur->id);
3545   if(!leaf) return false;
3546   TCLIST *recs = leaf->recs;
3547   if(cur->kidx >= TCLISTNUM(recs)){
3548     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
3549     return false;
3550   }
3551   BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, cur->kidx);
3552   int vnum = recp->rest ? TCLISTNUM(recp->rest) + 1 : 1;
3553   if(cur->vidx >= vnum){
3554     tcbdbsetecode(bdb, TCENOREC, __FILE__, __LINE__, __func__);
3555     return false;
3556   }
3557   *kbp = recp->kbuf;
3558   *ksp = recp->ksiz;
3559   if(cur->vidx > 0){
3560     *vbp = tclistval(recp->rest, cur->vidx - 1, vsp);
3561   } else {
3562     *vbp = recp->vbuf;
3563     *vsp = recp->vsiz;
3564   }
3565   return true;
3566 }
3567
3568
3569
3570 /*************************************************************************************************
3571  * debugging functions
3572  *************************************************************************************************/
3573
3574
3575 /* Print meta data of the header into the debugging output.
3576    `bdb' specifies the B+ tree database object. */
3577 void tcbdbprintmeta(TCBDB *bdb){
3578   assert(bdb);
3579   int dbgfd = tchdbdbgfd(bdb->hdb);
3580   if(dbgfd < 0) return;
3581   char buf[BDBPAGEBUFSIZ];
3582   char *wp = buf;
3583   wp += sprintf(wp, "META:");
3584   wp += sprintf(wp, " mmtx=%p", (void *)bdb->mmtx);
3585   wp += sprintf(wp, " cmtx=%p", (void *)bdb->cmtx);
3586   wp += sprintf(wp, " tmtx=%p", (void *)bdb->tmtx);
3587   wp += sprintf(wp, " hdb=%p", (void *)bdb->hdb);
3588   wp += sprintf(wp, " opaque=%p", (void *)bdb->opaque);
3589   wp += sprintf(wp, " open=%d", bdb->open);
3590   wp += sprintf(wp, " wmode=%d", bdb->wmode);
3591   wp += sprintf(wp, " lmemb=%u", bdb->lmemb);
3592   wp += sprintf(wp, " nmemb=%u", bdb->nmemb);
3593   wp += sprintf(wp, " opts=%u", bdb->opts);
3594   wp += sprintf(wp, " root=%llu", (unsigned long long)bdb->root);
3595   wp += sprintf(wp, " first=%llu", (unsigned long long)bdb->first);
3596   wp += sprintf(wp, " last=%llu", (unsigned long long)bdb->last);
3597   wp += sprintf(wp, " lnum=%llu", (unsigned long long)bdb->lnum);
3598   wp += sprintf(wp, " nnum=%llu", (unsigned long long)bdb->nnum);
3599   wp += sprintf(wp, " rnum=%llu", (unsigned long long)bdb->rnum);
3600   wp += sprintf(wp, " leafc=%p", (void *)bdb->leafc);
3601   wp += sprintf(wp, " nodec=%p", (void *)bdb->nodec);
3602   wp += sprintf(wp, " cmp=%p", (void *)(intptr_t)bdb->cmp);
3603   wp += sprintf(wp, " cmpop=%p", (void *)bdb->cmpop);
3604   wp += sprintf(wp, " lcnum=%u", bdb->lcnum);
3605   wp += sprintf(wp, " ncnum=%u", bdb->ncnum);
3606   wp += sprintf(wp, " lsmax=%u", bdb->lsmax);
3607   wp += sprintf(wp, " lschk=%u", bdb->lschk);
3608   wp += sprintf(wp, " capnum=%llu", (unsigned long long)bdb->capnum);
3609   wp += sprintf(wp, " hist=%p", (void *)bdb->hist);
3610   wp += sprintf(wp, " hnum=%d", bdb->hnum);
3611   wp += sprintf(wp, " hleaf=%llu", (unsigned long long)bdb->hleaf);
3612   wp += sprintf(wp, " lleaf=%llu", (unsigned long long)bdb->lleaf);
3613   wp += sprintf(wp, " tran=%d", bdb->tran);
3614   wp += sprintf(wp, " rbopaque=%p", (void *)bdb->rbopaque);
3615   wp += sprintf(wp, " cnt_saveleaf=%lld", (long long)bdb->cnt_saveleaf);
3616   wp += sprintf(wp, " cnt_loadleaf=%lld", (long long)bdb->cnt_loadleaf);
3617   wp += sprintf(wp, " cnt_killleaf=%lld", (long long)bdb->cnt_killleaf);
3618   wp += sprintf(wp, " cnt_adjleafc=%lld", (long long)bdb->cnt_adjleafc);
3619   wp += sprintf(wp, " cnt_savenode=%lld", (long long)bdb->cnt_savenode);
3620   wp += sprintf(wp, " cnt_loadnode=%lld", (long long)bdb->cnt_loadnode);
3621   wp += sprintf(wp, " cnt_adjnodec=%lld", (long long)bdb->cnt_adjnodec);
3622   *(wp++) = '\n';
3623   tcwrite(dbgfd, buf, wp - buf);
3624 }
3625
3626
3627 /* Print records of a leaf object into the debugging output.
3628    `bdb' specifies the B+ tree database object.
3629    `leaf' specifies the leaf object. */
3630 void tcbdbprintleaf(TCBDB *bdb, BDBLEAF *leaf){
3631   assert(bdb && leaf);
3632   int dbgfd = tchdbdbgfd(bdb->hdb);
3633   TCLIST *recs = leaf->recs;
3634   if(dbgfd < 0) return;
3635   char buf[BDBPAGEBUFSIZ];
3636   char *wp = buf;
3637   wp += sprintf(wp, "LEAF:");
3638   wp += sprintf(wp, " id:%llx", (unsigned long long)leaf->id);
3639   wp += sprintf(wp, " prev:%llx", (unsigned long long)leaf->prev);
3640   wp += sprintf(wp, " next:%llx", (unsigned long long)leaf->next);
3641   wp += sprintf(wp, " dirty:%d", leaf->dirty);
3642   wp += sprintf(wp, " dead:%d", leaf->dead);
3643   wp += sprintf(wp, " rnum:%d", TCLISTNUM(recs));
3644   *(wp++) = ' ';
3645   for(int i = 0; i < TCLISTNUM(recs); i++){
3646     tcwrite(dbgfd, buf, wp - buf);
3647     wp = buf;
3648     BDBREC *recp = (BDBREC *)TCLISTVALPTR(recs, i);
3649     wp += sprintf(wp, " [%s:%s]", recp->kbuf, recp->vbuf);
3650     TCLIST *rest = recp->rest;
3651     if(rest){
3652       for(int j = 0; j < TCLISTNUM(rest); j++){
3653         wp += sprintf(wp, ":%s", (char *)TCLISTVALPTR(rest, j));
3654       }
3655     }
3656   }
3657   *(wp++) = '\n';
3658   tcwrite(dbgfd, buf, wp - buf);
3659 }
3660
3661
3662 /* Print indexes of a node object into the debugging output.
3663    `bdb' specifies the B+ tree database object.
3664    `node' specifies the node object. */
3665 void tcbdbprintnode(TCBDB *bdb, BDBNODE *node){
3666   assert(bdb && node);
3667   int dbgfd = tchdbdbgfd(bdb->hdb);
3668   TCLIST *idxs = node->idxs;
3669   if(dbgfd < 0) return;
3670   char buf[BDBPAGEBUFSIZ];
3671   char *wp = buf;
3672   wp += sprintf(wp, "NODE:");
3673   wp += sprintf(wp, " id:%llx", (unsigned long long)node->id);
3674   wp += sprintf(wp, " heir:%llx", (unsigned long long)node->heir);
3675   wp += sprintf(wp, " dirty:%d", node->dirty);
3676   wp += sprintf(wp, " rnum:%d", TCLISTNUM(idxs));
3677   *(wp++) = ' ';
3678   for(int i = 0; i < TCLISTNUM(idxs); i++){
3679     tcwrite(dbgfd, buf, wp - buf);
3680     wp = buf;
3681     BDBIDX *idxp = (BDBIDX *)TCLISTVALPTR(idxs, i);
3682     wp += sprintf(wp, " [%llx:%s]", (unsigned long long)idxp->pid, idxp->kbuf);
3683   }
3684   *(wp++) = '\n';
3685   tcwrite(dbgfd, buf, wp - buf);
3686 }
3687
3688
3689
3690 // END OF FILE