cinelerra-5.1/db/tdb.C

   1 #include <cstdio>
   2 #include <cstring>
   3 #include <new>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include <stdarg.h>
   7 #include <fcntl.h>
   8 #include <errno.h>
   9 #include <time.h>
  10 #include <sys/file.h>
  11 #include <sys/ipc.h>
  12 #include <sys/time.h>
  13 #include <sys/types.h>
  14 #include <sys/shm.h>
  15 #include <sys/stat.h>
  16
  17 #include "tdb.h"
  18
  19 #if 0
  20 #include <execinfo.h>
  21 extern "C" void traceback(const char *fmt,...)
  22 {
  23   FILE *fp = fopen("/tmp/x","a");
  24   if( !fp ) return;
  25   va_list ap;  va_start(ap, fmt);
  26   vfprintf(fp, fmt, ap);
  27   va_end(ap);
  28   int nptrs;  void *buffer[100];
  29   nptrs = backtrace(buffer, lengthof(buffer));
  30   struct timeval now; gettimeofday(&now,0);
  31   fprintf(fp,"@%ld.03%ld %5d: ",now.tv_sec,now.tv_usec/1000,getpid());
  32   fprintf(fp,"*** stack %d\n",nptrs);
  33   char **strings = backtrace_symbols(buffer, nptrs);
  34   if( !strings ) return;
  35   for( int i=0; i<nptrs; ++i ) fprintf(fp,"%s\n", strings[i]);
  36   free(strings);
  37   fclose(fp);
  38 }
  39 #endif
  40
  41 // spif mods
  42 //  use repeated string byte move for decompress operation.
  43 //  page table design should be changed to hierachical bit
  44 //    field, so that only the trace of page table blocks in
  45 //    the update path are written at commit time.  Writing
  46 //    the entire page table on commit can be expensive.
  47
  48 // local memory allocator
  49 void *Db::get_mem8_t(int id)
  50 {
  51   return 0;
  52 }
  53
  54 void *Db::new_mem8_t(int size, int &id)
  55 {
  56   return new uint8_t[size];
  57 }
  58
  59 int Db::del_mem8_t(const void *vp, int id)
  60 {
  61   delete [] (uint8_t*)vp;
  62   return 0;
  63 }
  64
  65 volatile int gdb_wait;
  66
  67 void wait_gdb()
  68 {
  69   gdb_wait = 1;
  70   while( gdb_wait )
  71     sleep(1);
  72 }
  73
  74 // shared memory allocator
  75 void *Db::
  76 get_shm8_t(int id)
  77 {
  78   void *vp = shmat(id, NULL, 0);
  79   if( vp == (void*)-1 ) { perror("shmat"); wait_gdb(); vp = 0; }
  80   return (uint8_t *)vp;
  81 }
  82
  83 void *Db::
  84 new_shm8_t(int size, int &id)
  85 {
  86   id = shmget(IPC_PRIVATE, size, IPC_CREAT+0666);
  87   if( id < 0 ) { perror("shmget"); return 0; }
  88   uint8_t *addr = (uint8_t *)get_shm8_t(id);
  89   if( addr ) shmctl(id, IPC_RMID, 0);
  90   return addr;
  91 }
  92
  93 int Db::
  94 del_shm8_t(const void *vp, int id)
  95 {
  96   int ret = 0;
  97   if( id >= 0 ) {
  98     struct shmid_ds ds;
  99     if( !shmctl(id, IPC_STAT, &ds) ) ret = ds.shm_nattch;
 100     else { perror("shmctl"); wait_gdb(); ret = errIoStat; }
 101   }
 102   if( vp ) shmdt(vp);
 103   return ret;
 104 }
 105
 106
 107 // memory allocator
 108 uint8_t *Db::
 109 get_uint8_t(int id, int pg)
 110 {
 111   uint8_t *bp = (uint8_t *) get_mem(id);
 112   return bp;
 113 }
 114
 115 uint8_t *Db::
 116 new_uint8_t(int size, int &id, int pg)
 117 {
 118   void *vp = new_mem(size, id);
 119   return (uint8_t *)vp;
 120 }
 121
 122 int Db::
 123 del_uint8_t(const void *vp, int id, int pg)
 124 {
 125   return del_mem(vp, id);
 126 }
 127
 128
 129 void Db::
 130 error(int v)
 131 {
 132   if( !err_no ) {
 133     err_no = v;
 134     if( err_callback ) err_callback(this, v);
 135   }
 136 }
 137
 138 //int Db::debug = DBBUG_ERR + DBBUG_FAIL;
 139 int Db::debug = DBBUG_ERR;
 140
 141 #ifdef DEBUG
 142
 143 void dmp(unsigned char *bp, int len)
 144 {
 145   unsigned char ch[16], lch[16];
 146   int llen = lengthof(lch)+1;
 147   int dups = 0;
 148   unsigned char *adr = 0;
 149   int i, n;
 150
 151   do {
 152     if( !adr ) adr = bp;
 153     for( n=0; n<lengthof(ch) && --len>=0; ch[n++]=*bp++ );
 154     if( (i=n) >= llen ) // check for a duplicate
 155       while( --i>=0 && ch[i]==lch[i] );
 156     if( i >= 0 || len < 0 ) { /* not a duplicate */
 157       if( dups > 0 ) fprintf(stderr," ...%d\n",dups);
 158       dups = 0;
 159       fprintf(stderr,"%p:",adr);
 160       for( i=0; i<n; ++i ) fprintf(stderr," %02x",lch[i]=ch[i]);
 161       for( i=n; i<lengthof(ch); ++i ) fprintf(stderr,"   ");
 162       fprintf(stderr," ");
 163       for( i=0; i<n; ++i )
 164         fprintf(stderr,"%c", ch[i]>=' ' && ch[i]<='~' ? ch[i] : '.');
 165       fprintf(stderr,"\n");
 166       adr += n;
 167     }
 168     else {
 169       dups += n;
 170       adr = 0;
 171     }
 172     llen = n;
 173   } while( len > 0 );
 174 }
 175
 176 const char *Db::
 177 errMsgs[] = {
 178     "NoCmprFn", "NotFound", "Duplicate", "NoPage", "NoMemory",
 179     "IoRead", "IoWrite", "IoSeek", "IoStat", "BadMagic", "Corrupt",
 180     "Invalid", "Previous", "ObjEntity", "Limit", "User",
 181 };
 182
 183 void Db::
 184 dmsg(int msk, const char *msg,...)
 185 {
 186   if( !(msk & debug) ) return;
 187 #ifdef DEBUG_TIMESTAMPS
 188   struct timeval now; gettimeofday(&now,0);
 189   printf("@%ld.03%ld: ",now.tv_sec,now.tv_usec/1000);
 190 #endif
 191   va_list ap;
 192   va_start(ap, msg);
 193   vprintf(msg, ap);
 194   va_end(ap);
 195 FILE *fp = fopen("/tmp/x","a"); if( !fp ) return;
 196 fprintf(fp,"@%ld.03%ld %5d: ",now.tv_sec,now.tv_usec/1000,getpid());
 197 va_start(ap, msg); vfprintf(fp, msg, ap); va_end(ap);
 198 fclose(fp);
 199 }
 200
 201 int Db::
 202 _err_(int v,const char *fn,int ln)
 203 {
 204   error(v);
 205   dmsg(DBBUG_ERR,"%s:%d errored %d (%s)\n",fn,ln,v,errMsgs[-v]);
 206   wait_gdb();
 207   return v;
 208 }
 209
 210 int Db::
 211 _fail_(int v,const char *fn,int ln)
 212 {
 213   dmsg(DBBUG_FAIL,"%s:%d failed %d (%s)\n",fn,ln,v,errMsgs[-v]);
 214   return v;
 215 }
 216
 217 void Db::
 218 Error(int v,const char *msg)
 219 {
 220   error(v);
 221   dmsg(DBBUG_ERR,"%s\n",msg);
 222 }
 223
 224 void Db::
 225 dmp()
 226 {
 227   tdmp();  pdmp();
 228   printf("\n");
 229 }
 230
 231 void Db::
 232 tdmp()
 233 {
 234   printf("dmp  root_info->file_size %016lx\n",
 235     root_info->file_size);
 236   printf(" rootInfo root_info->transaction_id %d\n",
 237     root_info->transaction_id);
 238   printf("   root_info->root_info_addr/size %016lx/%08x\n",
 239     root_info->root_info_addr,root_info->root_info_size);
 240   printf("   root_info->last_info_addr/size %016lx/%08x\n",
 241     root_info->last_info_addr,root_info->last_info_size);
 242   printf("   root_info->indeciesUsed %d\n",
 243     root_info->indeciesUsed);
 244   printf("   alloc_cache: "); alloc_cache.dmp();
 245   for( int idx=0; idx<root_info->indeciesUsed; ++idx ) {
 246     IndexBase *ib = indecies[idx];
 247     if( !ib ) continue;
 248     printf("     idx %d. %-24s %s%c pop %5ld"
 249       "   root %-5d rhs %-5d ky/Dt %2d/%-2d ",
 250       idx, &ib->st->name[0], ib->st->type==idxBin ? "bin" :
 251       ib->st->type==idxStr ? "str" : "???",
 252       ib->st->key_type >= ktyBin && ib->st->key_type <= ktyDir ?
 253         " *="[ib->st->key_type] : '?', ib->st->count,
 254       ib->st->rootPageId, ib->st->rightHandSide,
 255       ib->st->keySz, ib->st->dataSz);
 256     printf("   free %d/",ib->st->freeBlocks);
 257     int n = 0;
 258     for( pageId id=ib->st->freeBlocks; id>=0; ++n ) {
 259       pgRef loc; loc.id = id;  loc.offset = 0;
 260       keyBlock *kbb;  addrRead_(loc,kbb);
 261       if( (id=kbb->right_link()) < 0 ) break;
 262       //printf(", %d",id);
 263     }
 264     printf("%d pages\n",n);
 265   }
 266
 267   printf("   Entities,  count %ld\n", entityIdIndex->Count());
 268   Entity e(this);  EntityLoc &ent = e.ent;  int eid;
 269   if( !entityIdIndex->First(&eid,&ent.obj) ) do {
 270     int nidxs = ent->nidxs;
 271     printf("     id %d. %s  maxId %d, recdSz %d, count %d, nidxs %d:",
 272       eid, &ent->name[0], ent->maxId, ent->recdSz, ent->count, nidxs);
 273     printf("   alloc_cache: "); ent->alloc_cache.dmp();
 274     for( int i=0; i<nidxs; ++i ) {
 275       int idx = ent->indexs[i];
 276       printf(" %d(%s),", idx, idx < 0 ? "" :
 277          !indecies[idx] ? "(err)" : &indecies[idx]->st->name[0]);
 278     }
 279     printf("\n");
 280   } while( !entityIdIndex->Next(&eid,&ent.obj) );
 281 }
 282
 283 void Db::
 284 pdmp()
 285 {
 286   printf("   root_info->pageTableUsed %d\n",root_info->pageTableUsed);
 287   for( int pid=0; pid<root_info->pageTableUsed; ++pid ) {
 288     Page &pg = *get_page(pid);
 289     if( !pg.addr && !pg->io_allocated && pg->io_addr==NIL &&
 290         pg->trans_id < 0 && pg->shmid < 0 && !pg->flags &&
 291         !pg->wr_allocated && pg->wr_io_addr==NIL ) continue;
 292     printf("     pid %d.  used %d, type %d, link %d, flags %04x addr %p\n",
 293       pid, pg->used, pg->type, pg->link, pg->flags, pg.addr);
 294     printf("     allocated %d io_alloc/io_addr %d/%016lx, wr_alloc/io_addr %d/%016lx\n",
 295       pg->allocated, pg->io_allocated, pg->io_addr,
 296       pg->wr_allocated, pg->wr_io_addr);
 297   }
 298   printf("   root_info->freePages %d",root_info->freePages);
 299   int n = 0;
 300   for( pageId id=root_info->freePages; id>=0; ++n ) id = (*get_page(id))->link;
 301     // printf(" %d\n",(id=(*get_page(id))->link));
 302   printf(",  pages = %d\n",n);
 303 }
 304
 305 void Db::
 306 fdmp()
 307 {
 308   freeStoreRecord free;
 309   if( !freeStoreIndex->First(&free,0) ) do {
 310       printf("free=%04lx/%012lx\n", free.size,free.io_addr);
 311   } while( !freeStoreIndex->Next(&free,0) );
 312 }
 313
 314 void Db::
 315 admp()
 316 {
 317   addrStoreRecord addr;
 318   if( !addrStoreIndex->First(&addr,0) ) do {
 319       printf("addr=%012lx/%04lx\n", addr.io_addr,addr.size);
 320   } while( !addrStoreIndex->Next(&addr,0) );
 321 }
 322
 323 void Db::
 324 cdmp()
 325 {
 326   Entity e(this);  EntityLoc &ent = e.ent;  int ret, eid;
 327   if( !(ret=entityIdIndex->First(&eid,&ent.obj)) ) do {
 328     printf(" %d. %-32s  %5d/%-5d  %d\n",eid,ent->name,
 329       ent->alloc_cache.loc.id, ent->alloc_cache.loc.offset,
 330       ent->alloc_cache.avail);
 331   } while( !(ret=entityIdIndex->Next(&eid,&ent.obj)) );
 332 }
 333
 334 void Db::
 335 achk()
 336 {
 337   if( !indecies ) return;  addrStoreRecord addr;
 338   addrStoreRecord last;  last.io_addr = 0; last.size = 0;
 339   if( !addrStoreIndex->First(&addr,0) ) do {
 340       if( last.io_addr > addr.io_addr ||
 341          (last.io_addr == addr.io_addr && last.size >= addr.size ) ) {
 342         printf("last=%012lx/%04lx, addr=%012lx/%04lx\n",
 343            addr.io_addr, addr.size, last.io_addr, last.size);
 344         wait_gdb();
 345       }
 346       last = addr;
 347   } while( !addrStoreIndex->Next(&addr,0) );
 348 }
 349
 350 void Db::
 351 fchk()
 352 {
 353   if( !indecies ) return;  freeStoreRecord free;
 354   freeStoreRecord last;  last.size = 0; last.io_addr = 0;
 355   if( !freeStoreIndex->First(&free,0) ) do {
 356       if( last.size > free.size ||
 357          (last.size == free.size && last.io_addr >= free.io_addr ) ) {
 358         printf("last=%04lx/%012lx, free=%04lx/%012lx\n",
 359            free.size, free.io_addr, last.size, last.io_addr);
 360         wait_gdb();
 361       }
 362       last = free;
 363   } while( !freeStoreIndex->Next(&free,0) );
 364 }
 365
 366 void Db::
 367 edmp(AllocCache &cache)
 368 {
 369   freeSpaceRecord free;
 370   if( !freeSpaceIndex->First(&free,0) ) do {
 371       printf("free=%04lx %d/%d\n", free.size,free.id,free.offset);
 372   } while( !freeSpaceIndex->Next(&free,0) );
 373 }
 374
 375 void Db::
 376 bdmp(AllocCache &cache)
 377 {
 378   addrSpaceRecord addr;
 379   if( !addrSpaceIndex->First(&addr,0) ) do {
 380     printf("addr=%d/%d %04lx\n", addr.id,addr.offset,addr.size);
 381   } while( !addrSpaceIndex->Next(&addr,0) );
 382 }
 383
 384 void Db::
 385 stats()
 386 {
 387   long store_allocated=0, store_used=0;
 388   long loaded_allocated=0, loaded_used=0;
 389   long written_allocated=0, written_used=0;
 390   int pages_written=0, pages_loaded=0, pages_deleted=0;
 391   for( int id=0,n=root_info->pageTableUsed; --n>=0; ++id ) {
 392     Page &pg = *get_page(id);
 393     store_allocated += pg->allocated;
 394     store_used += pg->used;
 395     if( pg.addr ) {
 396       ++pages_loaded;
 397       loaded_allocated += pg->allocated;
 398       loaded_used += pg->used;
 399     }
 400     if( pg->chk_flags(fl_wr) ) {
 401       ++pages_written;
 402       written_allocated += pg->allocated;
 403       written_used += pg->used;
 404       if( !pg.addr ) ++pages_deleted;
 405     }
 406   }
 407 #define percent(a,b) (!(a) || !(b) ? 0.0 : (100.0*(a)) / (b))
 408   long read_allocated = loaded_allocated - written_allocated;
 409   long read_used = loaded_used - written_used;
 410   int pages_read = pages_loaded - pages_written;
 411   printf("\ncommit %d\n", root_info->transaction_id);
 412   printf("    pages  %8d/del %-4d  alloc:%-12ld  used:%-12ld  %7.3f%%\n",
 413     root_info->pageTableUsed, pages_deleted, store_allocated, store_used,
 414     percent(store_used,store_allocated));
 415   printf("    loaded %8d/%-7.3f%%  alloc:%-12ld  used:%-12ld  %7.3f%%\n",
 416     pages_loaded, percent(pages_loaded, root_info->pageTableUsed),
 417     loaded_allocated, loaded_used, percent(loaded_used, loaded_allocated));
 418   printf("    read   %8d/%-7.3f%%  alloc:%-12ld  used:%-12ld  %7.3f%%\n",
 419     pages_read, percent(pages_read, root_info->pageTableUsed),
 420     read_allocated, read_used, percent(read_used, read_allocated));
 421   printf("    write  %8d/%-7.3f%%  alloc:%-12ld  used:%-12ld  %7.3f%%\n",
 422     pages_written, percent(pages_written, root_info->pageTableUsed),
 423     written_allocated, written_used, percent(written_used, written_allocated));
 424 #undef percent
 425 }
 426
 427 #endif
 428
 429
 430 #ifdef ZFUTEX
 431
 432 int Db::zloc_t::
 433 zyield()
 434 {
 435   return syscall(SYS_sched_yield);
 436 }
 437
 438 int Db::zloc_t::
 439 zgettid()
 440 {
 441   return syscall(SYS_gettid);
 442 }
 443
 444 int Db::zloc_t::
 445 zwake(int nwakeups)
 446 {
 447   int ret;
 448   while( (ret=zfutex(FUTEX_WAKE, nwakeups)) < 0 );
 449   return ret;
 450 }
 451
 452 int Db::zloc_t::
 453 zwait(int val, timespec *ts)
 454 {
 455   return zfutex(FUTEX_WAIT, val, ts);
 456 }
 457
 458 int Db::zlock_t::
 459 zemsg1()
 460 {
 461   fprintf(stderr,"unlocking and not locked\n");
 462   return -1;
 463 }
 464
 465 int Db::zlock_t::
 466 zlock(int v)
 467 {
 468   if( v || zxchg(1,loc) >= 0 ) do {
 469     zwait(1);
 470   } while ( zxchg(1,loc) >= 0 );
 471   return 1;
 472 }
 473
 474 int Db::zlock_t::
 475 zunlock(int nwakeups)
 476 {
 477   loc = -1;
 478   return zwake(1);
 479 }
 480
 481 void Db::zrwlock_t::
 482 zenter()
 483 {
 484   zdecr(loc); lk.lock(); lk.unlock(); zincr(loc);
 485 }
 486
 487 void Db::zrwlock_t::
 488 zleave()
 489 {
 490   if( lk.loc >= 0 ) zwake(1);
 491 }
 492
 493 void Db::zrwlock_t::
 494 write_enter()
 495 {
 496   lk.lock();  timespec ts = { 1, 0 };
 497   int v;  while( (v=loc) >= 0 ) zwait(v, &ts);
 498 }
 499
 500 void Db::zrwlock_t::
 501 write_leave()
 502 {
 503   lk.unlock();
 504 }
 505
 506 #endif
 507
 508 int Db::attach_wr()
 509 {
 510   if( !db_info ) return -1;
 511   if( is_locked() > 0 && db_info->owner == my_pid ) return 0;
 512   write_enter();
 513 //traceback(" attach_wr %d/%d/%d\n",my_pid,db_info->owner,db_info->last_owner);
 514   db_info->last_owner = db_info->owner;
 515   db_info->owner = my_pid;
 516   return 1;
 517 }
 518
 519 int Db::attach_rd()
 520 {
 521   if( db_info ) {
 522     enter();
 523 //traceback(" attach_rd %d/%d\n",my_pid,db_info->owner);
 524   }
 525   return 1;
 526 }
 527
 528 void Db::detach_rw()
 529 {
 530   if( !db_info ) return;
 531   int v = is_locked();
 532   if( v < 0 ) return;
 533 //fchk();  achk();
 534   if( v > 0 )
 535     write_leave();
 536   else
 537     leave();
 538 //traceback(" detach_rw %d\n",my_pid);
 539 }
 540
 541 // persistent pageTable element initial constructor
 542 void Db::PageStorage::
 543 init()
 544 {
 545   used = 0;
 546   allocated = 0;
 547   flags = 0;
 548   type = pg_unknown;
 549   io_allocated = 0;
 550   wr_allocated = 0;
 551   shmid = -1;
 552   link = NIL;
 553   trans_id = -1;
 554   io_addr = NIL;
 555   wr_io_addr = NIL;
 556 }
 557
 558 // non-persistent pageTable element initial constructor
 559 void Db::Page::
 560 init()
 561 {
 562   addr = 0;
 563   shm_id = -1;
 564 }
 565
 566 void Db::Page::
 567 reset_to(Page *pp)
 568 {
 569   addr = pp->addr;
 570   shm_id = pp->shm_id;
 571   pp->init();
 572   *st = *pp->st;
 573   pp->st->init();
 574 }
 575
 576 // deletes storage next start_transaction
 577 int Db::Page::
 578 release()
 579 {
 580   st->used = 0;  st->set_flags(fl_wr);
 581   return 0;
 582 }
 583
 584 // locked pageTable access
 585 Db::Page *Db::
 586 get_page(pageId pid)
 587 {
 588   read_locked by(db_info->pgTblLk);
 589   return get_Page(pid);
 590 }
 591
 592 /***
 593  *  Db::alloc_pageTable -- alloc page table
 594  *
 595  *  parameters
 596  *    sz      int        input         page table size
 597  *  returns error code
 598  */
 599 int Db::
 600 alloc_pageTable(int sz)
 601 {
 602   write_blocked by(db_info->pgTblLk);
 603   int n = pageTableHunks(sz) * pageTableHunkSize;
 604   Page **pt = new Page*[n];
 605   if( !pt ) Err(errNoMemory);
 606   int info_id, info_sz = n*sizeof(PageStorage);
 607   PageStorage *new_page_info = (PageStorage *)new_uint8_t(info_sz, info_id);
 608   if( !new_page_info ) { delete pt;  Err(errNoMemory); }
 609   int i = 0;
 610   if( page_info ) {
 611     for( ; i<root_info->pageTableUsed; ++i ) {
 612       pt[i] = get_Page(i);
 613       new_page_info[i] = *pt[i]->st;
 614       pt[i]->st = &new_page_info[i];
 615     }
 616   }
 617   for( ; i<n; ++i ) pt[i] = 0;
 618   db_info->page_info_id = page_info_id = info_id;
 619   del_uint8_t(page_info);  page_info = new_page_info;
 620   delete [] pageTable;  pageTable = pt;
 621   pageTableAllocated = n;
 622   return 0;
 623 }
 624
 625 /***
 626  *  Db::new_page -- access/construct new page
 627  *
 628  *  parameters: none
 629  *  returns page id on success (>=zero), error code otherwise(< 0)
 630  */
 631
 632 Db::pageId Db::
 633 new_page()
 634 {
 635   locked by(db_info->pgAlLk);
 636   pageId id = root_info->freePages;
 637   if( id < 0 ) {
 638     if( root_info->pageTableUsed >= pageTableAllocated ) {
 639       int sz = root_info->pageTableUsed + root_info->pageTableUsed/2 + 1;
 640       if_err( alloc_pageTable(sz) );
 641     }
 642     id = root_info->pageTableUsed;
 643     Page * pp = new Page(*new(&page_info[id]) PageStorage());
 644     if( !pp ) Err(errNoMemory);
 645     set_Page(id, pp);
 646     page_table_sz = ++root_info->pageTableUsed;
 647   }
 648   else {
 649     Page &pg = *get_page(id);
 650     root_info->freePages = pg->link;
 651     new(&pg) Page(*new(&page_info[id]) PageStorage());
 652   }
 653   return id;
 654 }
 655
 656 void Db::
 657 del_page(pageId id)
 658 {
 659   Page *pp = get_Page(id);
 660   pageDealloc(*pp);
 661   delete pp;
 662   set_Page(id, 0);
 663 }
 664
 665 /***
 666  *  Db::free_page -- link to root_info->freePages
 667  *
 668  *  parameters
 669  *    pid     pageId     input         page id
 670  */
 671
 672 void Db::
 673 free_page_(int pid)
 674 {
 675   Page &pg = *get_Page(pid);
 676   pageDealloc(pg);
 677   pg->allocated = 0;
 678   pg->used = 0;
 679   pg->clr_flags(fl_wr | fl_rd);
 680   pg->set_flags(fl_free);
 681   pageId id = root_info->freePages;
 682 #if 0
 683   Page *lpp = 0;  // use sorted order
 684   while( id >= 0 && id < pid ) {
 685     lpp = get_Page(id);
 686     id = (*lpp)->link;
 687   }
 688   if( lpp )
 689     (*lpp)->link = pid;
 690   else
 691 #endif
 692     root_info->freePages = pid;
 693   pg->link = id;
 694 }
 695
 696 Db::pageId Db::
 697 lower_page(pageId mid)
 698 {
 699   locked by(db_info->pgAlLk);
 700   pageId id = root_info->freePages;
 701   pageId lid = mid;
 702   Page *pp = 0, *lpp = 0;
 703   while( id >= 0 ) {
 704     if( id < lid ) { lid = id;  lpp = pp; }
 705     pp = get_Page(id);
 706     id = (*pp)->link;
 707   }
 708   if( lid < mid ) {
 709     Page &pg = *get_Page(lid);
 710     if( lpp )
 711       (*lpp)->link = pg->link;
 712     else
 713       root_info->freePages = pg->link;
 714     lpp = get_Page(mid);
 715     pg.reset_to(lpp);
 716     free_page_(mid);
 717   }
 718   return lid;
 719 }
 720
 721 int Db::
 722 get_index(const char *nm, CmprFn cmpr)
 723 {
 724   int idx = root_info->indeciesUsed;
 725   while( --idx >= 0  ) {
 726     IndexBase *ib = indecies[idx];
 727     if( !ib ) continue;
 728     if( !strncmp(&ib->st->name[0],nm,nmSz) ) break;
 729   }
 730   if( idx >= 0 && cmpr && indecies[idx]->st->type == idxBin ) {
 731     IndexBinary *bidx = (IndexBinary *)indecies[idx];
 732     bidx->compare = cmpr;
 733     bidx->bst->cmprId = findCmprFn(cmpr);
 734   }
 735   return idx;
 736 }
 737
 738 long Db::
 739 get_count(int r)
 740 {
 741   if( r < 0 || r >= root_info->indeciesUsed ) Fail(errInvalid);
 742   if( !indecies[r] ) Fail(errNotFound);
 743   return indecies[r]->Count();
 744 }
 745
 746 int Db::
 747 alloc_indecies(int n)
 748 {
 749   IndexBase **it = new IndexBase*[n];
 750   if( !it ) Err(errNoMemory);
 751   int info_id;
 752   IndexInfo *info = (IndexInfo *)new_uint8_t(n*sizeof(*info), info_id);
 753   if( !info ) { delete it; Err(errNoMemory); }
 754   memcpy(info, index_info, indeciesAllocated*sizeof(*info));
 755   int i = 0;
 756   for( ; i<root_info->indeciesUsed; ++i ) {
 757     if( !(it[i] = indecies[i]) ) continue;
 758     switch( it[i]->st->type ) {
 759     case idxBin: {
 760       IndexBinary *bidx = (IndexBinary *)it[i];
 761       bidx->st = info[i].bin;
 762       bidx->bst = info[i].bin;
 763       break; }
 764     case idxStr: {
 765       IndexString *sidx = (IndexString *)it[i];
 766       sidx->st = info[i].str;
 767       sidx->sst = info[i].str;
 768       break; }
 769     default:
 770       it[i]->st = 0;
 771       break;
 772     }
 773   }
 774   for( ; i<n; ++i ) it[i] = 0;
 775   db_info->index_info_id = index_info_id = info_id;
 776   del_uint8_t(index_info);  index_info = info;
 777   delete [] indecies;  indecies = it;
 778   indeciesAllocated = n;
 779   return 0;
 780 }
 781
 782 int Db::
 783 new_index()
 784 {
 785   int idx = 0;
 786   while( idx < root_info->indeciesUsed && indecies[idx] )
 787     ++idx;
 788   if( idx >= indeciesAllocated ) {
 789     int n = indeciesAllocated + indexTableHunkSize;
 790     if( alloc_indecies(n) ) Err(errNoMemory);
 791   }
 792   if( idx >= root_info->indeciesUsed ) {
 793     if( idx >= max_index_type ) Err(errLimit);
 794     root_info->indeciesUsed = idx+1;
 795     indecies_sz = root_info->indeciesUsed;
 796   }
 797   indecies[idx] = 0;
 798   return idx;
 799 }
 800
 801 void Db::
 802 del_index(int idx)
 803 {
 804   delete indecies[idx];
 805   indecies[idx] = 0;
 806   for( idx=root_info->indeciesUsed; idx>0 && indecies[idx-1]==0; --idx );
 807   indecies_sz = root_info->indeciesUsed = idx;
 808 }
 809
 810 int Db::
 811 new_index(IndexBase *&ibp, IndexBaseInfo *b, IndexBinaryInfo *bi)
 812 {
 813   IndexBaseStorage *st = new(b) IndexBaseStorage();
 814   IndexBinaryStorage *bst = new(bi) IndexBinaryStorage();
 815   IndexBinary *bidx = new IndexBinary(this, st, bst);
 816   if( !bidx || !bidx->ikey() || !bidx->tkey() ) {
 817     if( bidx ) delete bidx;
 818     Err(errNoMemory);
 819   }
 820   ibp = bidx;
 821   return 0;
 822 }
 823
 824 int Db::
 825 new_binary_index(const char *nm, int ksz, int dsz, CmprFn cmpr)
 826 {
 827   if( get_index(nm) >= 0 ) Err(errDuplicate);
 828   int idx = new_index();
 829   if( idx < 0 ) Err(errNoMemory);
 830   IndexBinary *bidx = new IndexBinary(this, idx, ksz, dsz, cmpr);
 831   if( !bidx || !bidx->ikey() || !bidx->tkey() ) {
 832     del_index(idx);
 833     Err(errNoMemory);
 834   }
 835   if( nm ) strncpy(&bidx->st->name[0],nm,sizeof(bidx->st->name));
 836   indecies[idx] = bidx;
 837   return idx;
 838 }
 839
 840 int Db::
 841 new_index(IndexBase *&ibp, IndexBaseInfo *b, IndexStringInfo *si)
 842 {
 843   IndexBaseStorage *st = new(b) IndexBaseStorage();
 844   IndexStringStorage *sst = new(si) IndexStringStorage();
 845   IndexString *sidx = new IndexString(this, st, sst);
 846   if( !sidx ) Err(errNoMemory);
 847   ibp = sidx;
 848   return 0;
 849 }
 850
 851 int Db::
 852 new_string_index(const char *nm, int dsz)
 853 {
 854   if( get_index(nm) >= 0 ) Err(errDuplicate);
 855   int idx = new_index();
 856   if( idx < 0 ) Err(errNoMemory);
 857   IndexString *sidx = new IndexString(this, idx, dsz);
 858   if( !sidx ) {
 859     del_index(idx);
 860     Err(errNoMemory);
 861   }
 862   if( nm ) strncpy(&sidx->st->name[0],nm,sizeof(sidx->st->name));
 863   indecies[idx] = sidx;
 864   return idx;
 865 }
 866
 867 /***
 868  *  Db::IndexBinary::keyMap - map function on index pages
 869  *
 870  *  parameters
 871  *      s      pageId     input        current id
 872  *
 873  *  returns 0 on success,
 874  *          errNotFound if index is empty
 875  *          error code otherwise
 876  */
 877
 878 int Db::IndexBinary::
 879 keyMap(pageId s, int(IndexBase::*fn)(pageId id))
 880 {
 881   pageId r;
 882   keyBlock *sbb;  Page *spp;  char *sn;
 883   if_err( db->indexRead(s,0,sbb,spp,sn) );
 884   if( (r=sbb->right_link()) >= 0 ) {
 885     int lkdSz = kdSz + sizeof(pageId);
 886     int n = spp->iused() / lkdSz;
 887     for( int i=0; i<n; ++i ) {
 888       pageId l = readPageId(sn);
 889       if_ret( keyMap(l,fn) );
 890       sn += lkdSz;
 891     }
 892     if_ret( keyMap(r,fn) );
 893   }
 894   if_err( (this->*fn)(s) );
 895   return 0;
 896 }
 897
 898 /***
 899  *  Db::IndexBinary::setLastKey -- conditionally update lastAccess
 900  *
 901  *  parameters
 902  *     s       pageId     input        page of last insert
 903  *     u       pageId     input        rightLink of page
 904  *     k       int        input        insert offset in block
 905  */
 906
 907 void Db::IndexBinary::
 908 setLastKey(pageId s, pageId u, int k)
 909 {
 910   if( keyInterior < 0 ) {
 911     if( u >= 0 ) {
 912       keyInterior = 1;
 913       k += sizeof(pageId);
 914     }
 915     else
 916       keyInterior = 0;
 917     lastAccess.id = s;
 918     lastAccess.offset = sizeof(keyBlock) + k;
 919   }
 920 }
 921
 922 /***
 923  *  Db::IndexBinary::keyLocate -- generalized database key retreival
 924  *
 925  *  parameters
 926  *      s      pageId     input        current id
 927  *   cmpr      CmprFn     input        key compare function
 928  *
 929  * returns 0 on success
 930  *         errNotFound if not found,
 931  *         error code otherwise
 932  */
 933
 934 int Db::IndexBinary::
 935 keyLocate(pgRef &last, pageId s, int op,void *ky,CmprFn cmpr)
 936 {
 937   int ret = errNotFound;
 938   keyBlock *sbb;  Page *spp;  char *sn;
 939   if_err( db->indexRead(s,0,sbb,spp,sn) );
 940   int len = spp->iused();
 941   int lkdSz = kdSz;
 942   if( sbb->right_link() >= 0 )
 943      lkdSz += sizeof(pageId);
 944
 945   int l = -1;
 946   int r = len / lkdSz;
 947   // binary search block for key
 948   while( (r - l) > 1 ) {
 949     int i = (l+r) >> 1;
 950     int k = i * lkdSz;
 951     if( sbb->right_link() >= 0 )
 952        k += sizeof(pageId);
 953     char *kn = sn + k;
 954     int n = cmpr((char*)ky,kn);
 955     if( n == 0 ) {
 956       if( op >= keyLE && op <= keyGE ) {
 957         last.id = s;
 958         last.offset = sizeof(keyBlock) + k;
 959         ret = 0;
 960       }
 961       if( op == keyLE || op == keyGT ) n = 1;
 962     }
 963     if( n > 0 ) l = i; else r = i;
 964   }
 965
 966   r *= lkdSz;
 967   int k = op < keyEQ ? l*lkdSz : (r < len ? r : -1);
 968   if( op != keyEQ && k >= 0 ) {
 969     if( sbb->right_link() >= 0 )
 970       k += sizeof(pageId);
 971     last.id = s;
 972     last.offset = sizeof(keyBlock) + k;
 973     ret = 0;
 974   }
 975
 976   if( (s = sbb->right_link()) >= 0 ) {
 977     if( r < len ) s = readPageId(sn+r);
 978     k = ret;
 979     ret = keyLocate(last,s,op,ky,cmpr);
 980     if( k == 0 ) ret = 0;
 981   }
 982
 983   return ret;
 984 }
 985
 986 /***
 987  *  Db::IndexBinary::Locate -- interface to generalized database key retreival
 988  *
 989  *  parameters
 990  * op          int             input        key relation in keyLT..keyGT
 991  * key         void *          input        retreival key image
 992  * cmpr        CmprFn          input        retreival key image
 993  * rtnKey      void *          output       resulting key value
 994  * rtnData     void *          output       resulting recd value
 995  *
 996  * returns 0 on success
 997  *         errNotFound on not found,
 998  *         error code otherwise
 999  */
1000
1001 int Db::IndexBinary::
1002 refLocate(pgRef &loc, int op, void *key, CmprFn cmpr)
1003 {
1004   if( st->rootPageId == NIL )
1005     Fail(errNotFound);
1006   if( op == keyEQ ) op = keyLE;
1007   if( !cmpr ) cmpr = compare;
1008   if_fail( keyLocate(loc,st->rootPageId,op, key,cmpr) );
1009 { locked by(idxLk);
1010   chkLastFind(loc); }
1011   return 0;
1012 }
1013
1014 int Db::IndexBinary::
1015 Locate(int op, void *key, CmprFn cmpr, void *rtnKey, void *rtnData)
1016 {
1017   pgRef last;
1018   if_fail( refLocate(last, op, key, cmpr) );
1019   char *kp = 0;
1020   if_err( db->addrRead_(last,kp) );
1021   if( rtnKey && st->keySz > 0 )
1022     wr_key(kp, (char*)rtnKey,st->keySz);
1023   if( rtnData && st->dataSz > 0 )
1024     memmove(rtnData,kp+st->keySz,st->dataSz);
1025   return 0;
1026 }
1027
1028 /***
1029  *  Db::IndexBinary::chkFind - check lastAccess block for key
1030  *
1031  *  parameters
1032  *    key      char *          input        key image
1033  *    last     pgRef *         input        last position loc
1034  *
1035  *  returns 0 if not found
1036  *          error code otherwise
1037  */
1038
1039 int Db::IndexBinary::
1040 chkFind(pgRef &loc, char *key)
1041 {
1042   pageId s = loc.id;
1043   if( s < 0 ) return 0;                         // must be valid block
1044   keyBlock *sbb;  Page *spp;  char *sn;
1045   if_err( db->indexRead(s,0,sbb,spp,sn) );
1046   if( sbb->right_link() >= 0 ) return 0;        // must be leaf
1047   int slen = spp->iused();
1048   int k = loc.offset - sizeof(keyBlock);
1049   if( k < 0 || k > slen ) return 0;             // must be inside/end of block
1050   int cmpr0 = k>=slen ? -1 : compare(key,sn+k); // compare last access
1051   if( cmpr0 ) {                                 // not found here
1052     int l = k;
1053     if( cmpr0 < 0 ? (k-=kdSz) < 0 : (k+=kdSz) >= slen ) return 0;
1054     int cmpr1 = compare(key,sn+k);
1055     if( !cmpr1 ) goto xit;                        // found here
1056     if( cmpr1 > 0 ) {
1057       if( l >= slen ) return 0;                   // no curr
1058       if( cmpr0 < 0 ) Fail(errNotFound);          // btwn prev/curr
1059       k = slen - kdSz;
1060       cmpr1 = compare(key,sn+k);
1061       if( !cmpr1 ) goto xit;                      // found here
1062       if( cmpr1 > 0 ) return 0;                   // key after last in block
1063     }
1064     else {
1065       if( cmpr0 > 0 ) Fail(errNotFound);          // btwn curr/next
1066       k = 0;
1067       cmpr1 = compare(key,sn);
1068       if( !cmpr1 ) goto xit;                      // found here
1069       if( cmpr1 < 0 ) return 0;                   // key before first in block
1070     }
1071     return errNotFound;                           // key in block range, but not found
1072   }
1073 xit:
1074   loc.offset = sizeof(keyBlock) + k;
1075   return 1;
1076 }
1077
1078 /***
1079  *  Db::IndexBinary::keyFind -- database unique key retreival
1080  *
1081  *  parameters
1082  *      s      pageId     input        current id
1083  *
1084  * returns 0 on success
1085  *         errNotFound on not found,
1086  *         error code otherwise
1087  */
1088
1089 int Db::IndexBinary::
1090 keyFind(pgRef &loc, void *ky, pageId s)
1091 {
1092   for(;;) {
1093     keyBlock *sbb;  Page *spp;  char *sn;
1094     if_err( db->indexRead(s,0,sbb,spp,sn) );
1095     int lkdSz = kdSz;
1096     if( sbb->right_link() >= 0 )
1097       lkdSz += sizeof(pageId);
1098     int len = spp->iused();
1099
1100     int l = -1;
1101     int r = len/lkdSz;
1102     // binary search block for key
1103     while( (r - l) > 1 ) {
1104       int i = (l+r) >> 1;
1105       int k = i*lkdSz;
1106       if( sbb->right_link() >= 0 )
1107         k += sizeof(pageId);
1108       char *kn = sn + k;
1109       int n = compare((char*)ky,kn);
1110       if( n == 0 ) {
1111         loc.id = s;
1112         loc.offset = sizeof(keyBlock) + k;
1113         return 0;
1114       }
1115       if( n > 0 ) l = i; else r = i;
1116     }
1117
1118     if( (s = sbb->right_link()) < 0 ) break;
1119     if( (r*=lkdSz) < len ) s = readPageId(sn+r);
1120   }
1121
1122   Fail(errNotFound);
1123 }
1124
1125 /***
1126  *  Db::IndexBinary::Find -- interface to database unique key retreival
1127  *
1128  *  parameters
1129  * key         void *          input        retreival key image
1130  * rtnData     void *          output       resulting recd value
1131  *
1132  * returns 0 on success
1133  *         errNotFound on not found,
1134  *         error code otherwise
1135  */
1136
1137 int Db::IndexBinary::
1138 refFind(pgRef &loc, void *ky)
1139 {
1140   if( st->rootPageId == NIL )
1141     Fail(errNotFound);
1142   pageId r = st->rootPageId;
1143   int ret = 0;
1144 { locked by(idxLk);
1145   loc = lastFind;
1146   if( CHK cFindCount > 2 ) ret = 1; }
1147   if( ret ) {                                   // try the easy way
1148     ret = chkFind(loc, (char *)ky);
1149     if( ret == errNotFound ) {
1150       r = loc.id;  ret = 0;
1151     }
1152   }
1153   if_err( ret );
1154   if( !ret ) {                                  // try the hard way
1155     if_fail( keyFind(loc,ky,r) );
1156   }
1157 { locked by(idxLk);
1158   chkLastFind(loc); }
1159   return 0;
1160 }
1161
1162 int Db::IndexBinary::
1163 Find(void *ky, void *rtnData)
1164 {
1165   pgRef last;
1166   if_fail( refFind(last, ky) );
1167   char *kp = 0;
1168   if_err( db->addrRead_(last,kp) );
1169   if( rtnData )
1170     memmove(rtnData,kp+st->keySz,st->dataSz);
1171   return 0;
1172 }
1173
1174
1175 int Db::IndexBinary::
1176 chkInsert(void *key, void *data)
1177 {
1178   int rhs = 0;
1179   char *ky = (char *)key;
1180   pageId s = lastInsert.id;
1181   if( s < 0 || cInsCount < 2 ) return 0;        /* >= 2 in a row */
1182   keyBlock *sbb;  Page *spp;  char *sn;
1183   if_err( db->indexRead(s,1,sbb,spp,sn) );
1184   if( sbb->right_link() >= 0 ) return 0;        /* must be exterior */
1185   int slen = spp->iused();
1186   int k = lastInsert.offset - sizeof(keyBlock);
1187   char *kp = sn + k;
1188   char *kn = kp + kdSz;
1189   char *rp = sn + slen;
1190   int n = compare(ky,kp);
1191   if( n == 0 ) Fail(errDuplicate);
1192   if( n > 0 ) {                                 /* after last one */
1193     if( kn >= rp ) {                            /* no next one */
1194       if( st->rightHandSide == s )
1195         rhs = 1;                                /* rhs */
1196     }
1197     else {
1198       n = compare(ky,kn);
1199       if( n == 0 ) Fail(errDuplicate);
1200       if( n < 0 )
1201         rhs = 1;                                /* before next one */
1202     }
1203   }
1204   if( !rhs ) return 0;                          /* not a hit */
1205   if( spp->iallocated()-slen < kdSz ) return 0; /* doesnt fit */
1206   if( rp > kn ) memmove(kn+kdSz,kn,rp-kn);      /* move data up */
1207   if( key && st->keySz > 0 )
1208     wr_key(key, kn,st->keySz);
1209   if( data && st->dataSz > 0 )
1210     memmove(kn+st->keySz,data,st->dataSz);        /* add new key/data */
1211   spp->iused(slen + kdSz);
1212   keyInterior = 0;
1213   lastAccess.id = s;
1214   lastAccess.offset = sizeof(keyBlock) + kn-sn;
1215   return 1;
1216 }
1217
1218 /***
1219  *  Db::IndexBinary::keyInsert - add unique key to database
1220  *
1221  *  parameters
1222  *      s      pageId     input        current id
1223  *  uses:
1224  *     iky     char *     input        assembled insertion key
1225  *
1226  *  returns 0 on success,
1227  *          errDuplicate if key already exists in database
1228  *          error code otherwise
1229  */
1230
1231 int Db::IndexBinary::
1232 keyInsert(pageId s, pageId &t)
1233 {
1234   char *kn;
1235 /* mark no continued insertion, and check end of search */
1236 /*  if not end, read current pageId, search for key */
1237 /*  return error if found.  */
1238   keyBlock *sbb;  Page *spp;  char *sn;
1239   if_err( db->indexRead(s,1,sbb,spp,sn) );
1240   int lkdSz = kdSz;
1241   pageId u = sbb->right_link();
1242   if( u >= 0 )
1243     lkdSz += sizeof(pageId);
1244   int slen = spp->iused();
1245   int keyCount = slen / lkdSz;
1246   int maxKeysInBlock = spp->iallocated() / lkdSz;
1247   int l = -1;
1248   int r = keyCount;
1249
1250 /* binary search block for key */
1251   while( (r - l) > 1 ) {
1252     int i = (l+r) >> 1;
1253     int k = i*lkdSz;
1254     if( sbb->right_link() >= 0 )
1255       k += sizeof(pageId);
1256     kn = sn + k;
1257     int n = compare(this->akey,kn);
1258     if( n == 0 ) {
1259       lastAccess.id = s;
1260       lastAccess.offset = sizeof(keyBlock) + k;
1261       Fail(errDuplicate);
1262     }
1263     if( n > 0 ) l = i; else r = i;
1264   }
1265
1266 /* not found in this pageId, continue search at lower levels. */
1267 /*  process insertion if lower level splits ( t>=0 ).  */
1268   int i = sizeof(pageId);
1269   int k = r * lkdSz;
1270   if( u >= 0 ) {
1271     if( k < slen )
1272       u = readPageId(sn+k);
1273     if_ret( keyInsert(u, t) );
1274     if( t < 0 ) return 0;
1275     if( k < slen )
1276       writePageId(sn+k,t);
1277     else
1278       sbb->right_link(t);
1279     i = 0;
1280   }
1281
1282 /* if current pageId is not full, insert into this pageId. */
1283   if( keyCount < maxKeysInBlock ) {
1284     t = NIL;
1285     kn = sn + k;
1286     memmove(kn+lkdSz,kn,slen-k);
1287     spp->iused(slen + lkdSz);
1288     memmove(kn,&iky[i],lkdSz);
1289     setLastKey(s,u,k);                  /*  save insert loc */
1290     return 0;
1291   }
1292
1293 /* current pageId is full, split pageId and promote new parent key */
1294   keyBlock *tbb;  Page *tpp;  char *tn;
1295   if_err( blockAllocate(t,tbb,tpp,tn) );
1296 /* split point is middle, or end if inserting consecutive on rhs */
1297   int promoted = maxKeysInBlock/2;
1298   if( cInsCount > 2 && s == st->rightHandSide )
1299     promoted = maxKeysInBlock-1;
1300   promoted *= lkdSz;
1301   int tlen = slen - promoted;
1302   if( st->rightHandSide == s ) st->rightHandSide = t;
1303
1304   if( k <= promoted ) {                 /*  at or left of promoted key */
1305     if( k != promoted ) {               /*  not promoting current key */
1306       kn = sn+promoted-lkdSz;
1307       memmove(&tky[0],kn,lkdSz);         /*  save promoted key */
1308       kn = sn+k;
1309       memmove(kn+lkdSz,kn,promoted-lkdSz-k);
1310       memmove(kn,&iky[i],lkdSz);         /*  insert new key */
1311       memmove(&iky[i],&tky[0],lkdSz);    /*  promote key */
1312       setLastKey(s,u,k);                /*  save insert loc */
1313     }
1314     memmove(tn,sn+promoted,tlen);
1315   }
1316   else {                                /*  key is > center */
1317     kn = sn+promoted;
1318     memmove(&tky[0],kn,lkdSz);           /*  save promoted key */
1319     int j = k - promoted - lkdSz;
1320     memmove(tn,kn+=lkdSz,j);
1321     memmove(kn=tn+j,&iky[i],lkdSz);      /*  insert new key */
1322     setLastKey(t,u,j);                  /*  save insert loc */
1323     memmove(kn+=lkdSz,sn+k,slen-k);
1324     memmove(&iky[i],&tky[0],lkdSz);      /*  promote key */
1325   }
1326
1327 /* set newly split blocks half full, and set new links. */
1328   slen = promoted;
1329   spp->iused(slen);
1330   tpp->iused(tlen);
1331   tbb->right_link(sbb->right_link());
1332   sbb->right_link(readPageId(&iky[0]));
1333   writePageId(&iky[0],s);
1334 /* if root is splitting, create new left */
1335   if( s == st->rootPageId ) {
1336     keyBlock *ubb;  Page *upp;  char *un;
1337     if_err( blockAllocate(u,ubb,upp,un) );
1338     memmove(un,sn,slen);
1339     upp->iused(slen);
1340     ubb->right_link(sbb->right_link());
1341     writePageId(&iky[0],u);
1342     k = st->keySz + st->dataSz + sizeof(pageId);
1343     memmove(sn,&iky[0],k);
1344     spp->iused(k);
1345     sbb->right_link(t);
1346     setLastKey(s,t,sizeof(pageId));
1347   }
1348 /* t >= 0 indicates continued insertion, return success */
1349   return 0;
1350 }
1351
1352 void Db::IndexBinary::
1353 makeKey(char *cp,char *key,int l,char *recd,int n)
1354 {
1355   writePageId(cp,NIL);  cp += sizeof(pageId);
1356   if( l > 0 ) { wr_key(key, cp,l);  cp += l; }
1357   if( n > 0 && recd ) memmove(cp,recd,n);
1358 }
1359
1360 /***
1361  *  Db::Insert - interface to database unique key insertion
1362  *
1363  *  parameters
1364  * key         void *          input        key image
1365  * data        void *          input        recd value
1366  *
1367  *  returns 0 on success,
1368  *          errDuplicate if key already exists in database
1369  *          error code otherwise
1370  */
1371
1372 int Db::IndexBinary::
1373 Insert(void *key, void *data)
1374 {
1375   if_err( MakeRoot() );
1376   keyInterior = -1;
1377   int ret = 0;
1378   if( CHK cInsCount > 2 ) {                     // try the easy way
1379     ret = chkInsert(key,data);
1380     if_ret( ret );
1381   }
1382   if( !ret ) {                                  // try the hard way
1383     makeKey(&iky[0],this->akey=(char *)key,st->keySz,(char *)data,st->dataSz);
1384     pageId t = NIL;  lastAccess.id = NIL;
1385     if_ret( keyInsert(st->rootPageId, t) );
1386   }
1387   if( keyInterior > 0 ) lastAccess.id = NIL;
1388   chkLastInsert();
1389   ++st->count;
1390   return 0;
1391 }
1392
1393 /***
1394  *  Db::keyBlockUnderflow -- balences/merges blocks after a deletion
1395  *
1396  *  parameters
1397  *      t      int           output       continuation flag
1398  *    lbb      keyBlock *    input        left sibling keyBlock
1399  *      p      pageId        input        parent keyBlock id
1400  *    pbb      keyBlock *    input        parent keyBlock
1401  *     pi      int           input        deletion key offset parent
1402  *
1403  *
1404  *  returns 0 on success, errorcode otherwise
1405  */
1406
1407 int Db::IndexBinary::
1408 keyBlockUnderflow(int &t,keyBlock *lbb,pageId p,keyBlock *pbb,int pi)
1409 {
1410   int i, k;
1411   char *kn;
1412   pageId l, r;
1413   keyBlock *rbb;
1414   int psiz = kdSz + sizeof(pageId);
1415 /*
1416  *  if deletion was at right end of block
1417  *    back up one key otherwise use this key
1418  */
1419   char *pn = (char *)(pbb+1);
1420   Page *ppp = db->get_page(p);
1421   int plen = ppp->iused();
1422   if( pi >= plen ) {                            /* read lt side */
1423     r = pbb->right_link();
1424     rbb = lbb;
1425     pi -= psiz;
1426     l = readPageId(pn+pi);
1427     if_err( db->indexRead(l,1,lbb) );
1428   }
1429   else {                                        /* read rt side */
1430     l = readPageId(pn+pi);
1431     i = pi + psiz;
1432     r = i >= plen ? pbb->right_link() : readPageId(pn+i);
1433     if_err( db->indexRead(r,1,rbb) );
1434   }
1435
1436   int lsz = lbb->right_link() >= 0 ? sizeof(pageId) : 0;
1437   int lkdSz = kdSz + lsz;
1438   char *ln = (char *)(lbb+1);
1439   Page *lpp = db->get_page(l);
1440   int llen = lpp->iused();
1441   char *rn = (char *)(rbb+1);
1442   Page *rpp = db->get_page(r);
1443   int rlen = rpp->iused();
1444
1445 /*
1446  * if both lt&rt blocks+parent key all fit in one block, merge them
1447  */
1448   int n = llen + rlen;
1449   if( n <= rpp->iallocated()-lkdSz ) {          /* merge */
1450     writePageId(pn+pi,lbb->right_link());       /* reset parent key left ptr */
1451     memmove(ln+llen,pn+pi+sizeof(pageId)-lsz,lkdSz);
1452     llen += lkdSz;
1453     memmove(ln+llen,rn,rlen);                    /* move right to left */
1454     llen += rlen;
1455     lbb->right_link(rbb->right_link());
1456     i = pi + psiz;
1457     memmove(pn+pi,pn+i,plen-i);                 /* remove parent key */
1458     plen -= psiz;
1459     if( plen == 0 && p == st->rootPageId ) {        /* totally mashed root */
1460       if( st->rightHandSide == r ) st->rightHandSide = p;
1461       if_err( blockFree(r) );
1462       memmove(pn,ln,llen);                       /* copy to parent page */
1463       pbb->right_link(lbb->right_link());
1464       ppp->iused(llen);
1465       if_err( blockFree(l) );
1466     }
1467     else {
1468       if( r != pbb->right_link() )              /* not rightLink */
1469         writePageId(pn+pi,l);                   /* must be next key */
1470       else
1471         pbb->right_link(l);
1472       if( st->rightHandSide == r ) st->rightHandSide = l;
1473       if_err( blockFree(r) );
1474       lpp->iused(llen);
1475       ppp->iused(plen);
1476     }
1477     lastAccess.id = NIL;
1478     return 0;                                   /* continue underflow */
1479   }
1480
1481   int tsiz = n / 6;
1482   if( tsiz < lkdSz ) tsiz = lkdSz;              /* slosh threshold */
1483   if( plen > psiz && plen > tsiz ) t = 0;       /* discontinue underflow */
1484   if( (i=(n/=2)-llen) >= tsiz || !llen ) {      /* slosh left */
1485     writePageId(pn+pi,lbb->right_link());       /* reset parent key left ptr */
1486     k = pi+sizeof(pageId);
1487     memmove(kn=ln+llen,pn+k-lsz,lkdSz);          /* move parent to left */
1488     i = (i/lkdSz)-1;
1489     memmove(kn+=lkdSz,rn,i*=lkdSz);              /* migrate keys left */
1490     llen += i+lkdSz;  kn = rn+i;
1491     if( lbb->right_link() >=0 )
1492       lbb->right_link(readPageId(kn));
1493     writePageId(pn+pi,l);                       /* change parent key */
1494     memmove(pn+k,kn+lsz,kdSz);
1495     kn += lkdSz;  i += lkdSz;
1496     memmove(rn,kn,rlen-=i);                      /* migrate keys left */
1497   }
1498   else if( (i=n-rlen) >= tsiz || !rlen ) {      /* slosh right */
1499     i /= lkdSz; i *= lkdSz;
1500     memmove(kn=rn+i,rn,rlen);
1501     rlen += i;                                  /* migrate keys right */
1502     writePageId(pn+pi,lbb->right_link());
1503     k = pi+sizeof(pageId);
1504     memmove(kn-=lkdSz,pn+k-lsz,lkdSz);           /* move parent key */
1505     i -= lkdSz;  n = llen-i;
1506     memmove(rn,kn=ln+n,i);
1507     kn -= lkdSz;                                /* migrate keys right */
1508     if( lbb->right_link() >=0 )
1509       lbb->right_link(readPageId(kn));
1510     memmove(pn+k,kn+lsz,kdSz);                   /* change parent key */
1511     writePageId(pn+pi,l);
1512     llen = n - lkdSz;
1513   }
1514   else
1515     return 0;
1516   lastAccess.id = NIL;
1517   lpp->iused(llen);                             /* update lengths */
1518   rpp->iused(rlen);
1519   ppp->iused(plen);
1520   return 0;
1521 }
1522
1523 /***
1524  *  Db::IndexBinary::keyDelete - remove unique key from database
1525  *
1526  *  parameters
1527  *      t      int        input/output check underflow flag
1528  *     kp      void *     input        key image to be removed
1529  *      s      pageId     input        current id
1530  *      p      pageId     input        parent id
1531  *    pbb      keyBlock * input        parent
1532  *     pi      int        input        deletion key offset parent
1533  *
1534  *  returns 0 on success,
1535  *          errNotFound if key does not exists in database
1536  *          error code otherwise
1537  */
1538
1539 int Db::IndexBinary::
1540 keyDelete(int &t,void *kp,pageId s,pageId p,keyBlock *pbb,int pi)
1541 {
1542   pageId u;
1543   keyBlock *sbb;  Page *spp;  char *sn;
1544   if_err( db->indexRead(s,1,sbb,spp,sn) );
1545   int slen = spp->iused();
1546   t = 1;                                        /* check underflow */
1547   if( idf == 0 ) {                              /* not interior deletion */
1548     int lkdSz = kdSz;
1549     if( sbb->right_link() >= 0 )
1550       lkdSz += sizeof(pageId);
1551     int l = -1;
1552     int r = slen / lkdSz;
1553     while( (r - l) > 1 ) {                      /* binary search for key */
1554       int i = (l+r) >> 1;
1555       int k = i * lkdSz;
1556       if( sbb->right_link() >= 0 )
1557         k += sizeof(pageId);
1558       char *kn = sn + k;
1559       int n = compare(this->akey,kn);
1560       if( n == 0 ) {
1561         if( sbb->right_link() < 0 ) {           /* terminal key */
1562           slen -= lkdSz;
1563           memmove(kn,kn+lkdSz,slen-k);
1564           spp->iused(slen);                     /* delete key */
1565           lastAccess.id = s;                    /* lastAccess = key */
1566           lastAccess.offset = sizeof(keyBlock) + k;
1567         }
1568         else {                                  /* interior key */
1569           k -= sizeof(pageId);
1570           kn = sn + k;
1571           u = readPageId(kn);
1572           idf = 1;                              /* interior delete */
1573           if_ret( keyDelete(t,(void *)kn,u,s,sbb,k) );
1574         }
1575         goto xit;
1576       }
1577       if( n > 0 ) l = i; else r = i;
1578     }
1579     if( (u=sbb->right_link()) < 0 ) {           /* could not find it */
1580       t = 0;
1581       Fail(errNotFound);
1582     }
1583     if( (r *= lkdSz) < slen )
1584       u = readPageId(sn+r);
1585     if_ret( keyDelete(t,kp,u,s,sbb,r) );        /* continue search */
1586   }
1587   else {                                        /* interior deletion */
1588     if( (u=sbb->right_link()) < 0 ) {           /* equivalent exterior key */
1589       int i = slen - kdSz;
1590       char *kn = sn + i;                        /* translate to interior */
1591       memmove((char *)kp+sizeof(pageId),kn,kdSz);
1592       spp->iused(i);                            /* remove key */
1593     }
1594     else {                                      /* continue decending */
1595       if_ret( keyDelete(t,kp,u,s,sbb,slen) );
1596     }
1597   }
1598 xit:
1599   if( t != 0 ) {                                /* underflow possible */
1600     if( !pbb )
1601       t = 0;                                    /* no parent, root */
1602     else
1603       if_err( keyBlockUnderflow(t,sbb,p,pbb,pi) );
1604   }
1605   return 0;
1606 }
1607
1608 int Db::IndexBinary::
1609 chkDelete(pgRef &loc, void *kp)
1610 {
1611   int ret = 0;
1612   loc = lastDelete;
1613   ret = chkFind(loc, (char*)kp);                // try last delete
1614   if( !ret && lastFind.id != loc.id ) {
1615     loc = lastFind;
1616     ret = chkFind(loc, (char*)kp);              // try last find
1617   }
1618   if( !ret ) return 0;
1619   if( ret == errNotFound ) ret = 0;
1620   if_err( ret );
1621   pageId s = loc.id;
1622   keyBlock *sbb;  Page *spp;  char *sn;
1623   if_err( db->indexRead(s,1,sbb,spp,sn) );
1624   int dlen = spp->iused() - kdSz;
1625   if( dlen < kdSz ) return 0;                   // at least 1 key must remain
1626   if( !ret ) return errNotFound;
1627   spp->iused(dlen);                             // delete
1628   int k = loc.offset - sizeof(keyBlock);
1629   if( dlen > k ) {
1630     char *kp = sn + k;
1631     memmove(kp,kp+kdSz,dlen-k);
1632   }
1633   return 1;
1634 }
1635
1636 /***
1637  *  Db::IndexBinary::Delete - interface to remove unique key
1638  *
1639  *  parameters
1640  *    key      void *          input        key image to be removed
1641  *
1642  *  returns 0 on success,
1643  *          errNotFound key does not exists in database
1644  *          error code otherwise
1645  */
1646
1647 int Db::IndexBinary::
1648 Delete(void *key)
1649 {
1650   if( st->rootPageId == NIL ) Fail(errNotFound);
1651   this->akey = (char *)key;
1652   this->idf = 0;
1653   pageId r = st->rootPageId;
1654   int ret = 0;
1655   if( CHK cDelCount > 2 ) {                     // try the easy way
1656     pgRef loc;
1657     ret = chkDelete(loc, key);
1658     if( ret == errNotFound ) {                  // in exterior block
1659       r = loc.id;  ret = 0;
1660     }
1661   }
1662   if( !ret ) {                                  // try the hard way
1663     makeKey(&iky[0],this->akey=(char *)key,st->keySz,0,0);
1664     lastAccess.id = NIL;  int t = 1;
1665     (void)r; // use full search, r works but is not traditional
1666     if_fail( keyDelete(t,(void *)&iky[0],/*r*/st->rootPageId,0,0,0) );
1667     if_err( UnmakeRoot() );
1668   }
1669   chkLastDelete();
1670   --st->count;
1671   return 0;
1672 }
1673
1674 /***
1675  *  Db::IndexBinary::keyFirst - access leftmost key in tree
1676  *
1677  *  parameters
1678  *      s      pageId     input        current id
1679  *
1680  *  returns 0 on success,
1681  *          errNotFound if index is empty
1682  *          error code otherwise
1683  */
1684
1685 int Db::IndexBinary::
1686 keyFirst(pgRef &loc, pageId s)
1687 {
1688   for(;;) {
1689     keyBlock *sbb;
1690     if_err( db->indexRead(s,0,sbb) );
1691     if( sbb->right_link() < 0 ) break;
1692     char *sn = (char *)(sbb+1);
1693     s = readPageId(sn);
1694   }
1695
1696   loc.id = s;
1697   loc.offset = sizeof(keyBlock);
1698   return 0;
1699 }
1700
1701 /***
1702  *  Db::IndexBinary::First -- interface to database access leftmost key in tree
1703  *
1704  *  parameters
1705  * rtnKey      void *          output       resulting key value
1706  * rtnData     void *          output       resulting recd value
1707  *
1708  * returns 0 on success
1709  *         errNotFound on not found,
1710  *         error code otherwise
1711  */
1712
1713 int Db::IndexBinary::
1714 First(void *rtnKey,void *rtnData)
1715 {
1716   if( st->rootPageId == NIL ) Fail(errNotFound);
1717   pgRef first;
1718   if_fail( keyFirst(first, st->rootPageId) );
1719   char *kp = 0;
1720   if_err( db->addrRead_(first,kp) );
1721   if( rtnKey && st->keySz > 0 )
1722     wr_key(kp, (char*)rtnKey,st->keySz);
1723   if( rtnData && st->dataSz > 0 )
1724     memmove(rtnData,kp+st->keySz,st->dataSz);
1725 { locked by(idxLk);
1726   lastNext = lastAccess = first; }
1727   return 0;
1728 }
1729
1730 /***
1731  *  Db::IndexBinary::keyLast - access rightmost key in tree
1732  *
1733  *  parameters
1734  *      s      pageId     input        current id
1735  *
1736  *  returns 0 on success,
1737  *          errNotFound if index is empty
1738  *          error code otherwise
1739  */
1740
1741 int Db::IndexBinary::
1742 keyLast(pgRef &loc, pageId s)
1743 {
1744   for(;;) {
1745     keyBlock *sbb;
1746     if_err( db->indexRead(s,0,sbb) );
1747     pageId u = sbb->right_link();
1748     if( u < 0 ) break;
1749     s = u;
1750   }
1751
1752   Page *spp = db->get_page(s);
1753   loc.id = s;
1754   int k = spp->iused() - kdSz;
1755   loc.offset = sizeof(keyBlock) + k;
1756   return 0;
1757 }
1758
1759 /***
1760  *  Db::IndexBinary::Last -- interface to database access rightmost key in tree
1761  *
1762  *  parameters
1763  * rtnKey      void *          output       resulting key value
1764  * rtnData     void *          output       resulting recd value
1765  *
1766  * returns 0 on success
1767  *         errNotFound on not found,
1768  *         error code otherwise
1769  */
1770
1771 int Db::IndexBinary::
1772 Last(void *rtnKey,void *rtnData)
1773 {
1774   if( st->rootPageId == NIL ) Fail(errNotFound);
1775   pgRef last;
1776   if_fail( keyLast(last, st->rootPageId) );
1777   char *kp = 0;
1778   if_err( db->addrRead_(last,kp) );
1779   if( rtnKey && st->keySz > 0 )
1780     wr_key(kp, (char*)rtnKey,st->keySz);
1781   if( rtnData && st->dataSz > 0 )
1782     memmove(rtnData,kp+st->keySz,st->dataSz);
1783 { locked by(idxLk);
1784   lastNext = lastAccess = last; }
1785   return 0;
1786 }
1787
1788 /***
1789  *  Db::IndexBinary::Modify -- interface to database record modify
1790  *
1791  *  parameters
1792  *  keyDef      index         input        key definition block
1793  *  key         void *          input        retreival key image
1794  *  recd        void *          input        new recd value
1795  *
1796  * returns 0 on success
1797  *         errNotFound on not found,
1798  *         error code otherwise
1799  */
1800
1801 int Db::IndexBinary::
1802 Modify(void *key,void *recd)
1803 {
1804   if_fail( Find(key,0) );
1805   char *bp = 0;
1806   if_err( db->addrWrite_(lastAccess,bp) );
1807   memmove(bp+st->keySz,recd,st->dataSz);
1808   return 0;
1809 }
1810
1811 int Db::IndexBinary::
1812 chkNext(pgRef &loc, char *&kp)
1813 {
1814   pageId s = loc.id;
1815   if( s < 0 ) return 0;                         // must be valid
1816   keyBlock *sbb;  Page *spp;  char *sn;
1817   if_err( db->indexRead(s,0,sbb,spp,sn) );
1818   if( sbb->right_link() >= 0 ) return 0;        // must be leaf
1819   int k = loc.offset - sizeof(keyBlock);
1820   if( k < 0 || k >= spp->iused() ) return 0;    // curr must be in block
1821   if( (k+=kdSz) >= spp->iused() ) return 0;     // next must be in block
1822   kp = sn + k;
1823   loc.offset = sizeof(keyBlock) + k;
1824   return 1;
1825 }
1826
1827 int Db::IndexBinary::
1828 keyNext(pgRef &loc, char *kp)
1829 {
1830   if_fail( keyLocate(loc,st->rootPageId, keyGT,kp,compare) );
1831   return 0;
1832 }
1833
1834 /***
1835  *  Db::IndexBinary::Next -- interface to sequential database key retreival
1836  *
1837  *  parameters
1838  * loc         pgRef &         input        last known retreival key
1839  * rtnKey      void *          output       resulting key value
1840  * rtnData     void *          output       resulting recd value
1841  *
1842  * returns 0 on success
1843  *         error code otherwise
1844  */
1845
1846 int Db::IndexBinary::
1847 Next(pgRef &loc,void *rtnKey,void *rtnData)
1848 {
1849   if( st->rootPageId == NIL ) Fail(errNotFound);
1850   char *kp;
1851   int ret = CHK chkNext(loc,kp);                // try the easy way
1852   if_ret( ret );
1853   if( !ret ) {
1854     char *ky = 0;
1855     switch( st->key_type ) {
1856     case ktyInd:
1857       ky = (char *)rtnKey;
1858       break;
1859     case ktyBin: case ktyDir:
1860       if_err( db->addrRead_(loc,ky) );
1861       break;
1862     }
1863     if_ret( keyNext(loc, ky) );                 // try the hard way
1864   }
1865   if_err( db->addrRead_(loc,kp) );
1866   if( rtnKey && st->keySz > 0 )
1867     wr_key(kp, (char*)rtnKey,st->keySz);
1868   if( rtnData && st->dataSz > 0 )
1869     memmove(rtnData,kp+st->keySz,st->dataSz);
1870 { locked by(idxLk);
1871   lastAccess = loc; }
1872   return 0;
1873 }
1874
1875 void Db::IndexBinary::
1876 init()
1877 {
1878   keyInterior = 0;
1879   idf = 0;  akey = 0;
1880 }
1881
1882 Db::IndexBinary::
1883 IndexBinary(Db *zdb, int zidx, int ksz, int dsz, CmprFn cmpr)
1884  : IndexBase(zdb, idxBin, zidx, ksz, dsz)
1885 {
1886   compare = cmpr;
1887   bst = new(st+1) IndexBinaryStorage(zdb->findCmprFn(compare));
1888   iky = new char[st->blockSize/2+1];
1889   tky = new char[st->blockSize/2+1];
1890   init();
1891 }
1892
1893 Db::IndexBinary::
1894 IndexBinary(Db *zdb, IndexBaseStorage *b, IndexBinaryStorage *d)
1895  : IndexBase(zdb, *b)
1896 {
1897   bst = new(d) IndexBinaryStorage();
1898   compare = cmprFns[bst->cmprId];
1899   iky = new char[st->blockSize/2+1];
1900   tky = new char[st->blockSize/2+1];
1901   init();
1902 }
1903
1904 Db::IndexBinary::
1905 IndexBinary(IndexBase *ib, IndexBaseStorage *b, IndexBinaryStorage *d)
1906  : IndexBase(ib->db, *b)
1907 {
1908   bst = new(d) IndexBinaryStorage();
1909   compare = cmprFns[bst->cmprId];
1910   init();
1911 }
1912
1913 Db::IndexBinary::
1914 ~IndexBinary()
1915 {
1916   delete [] iky;
1917   delete [] tky;
1918 }
1919
1920
1921 int Db::IndexString::
1922 keyMap(pageId s, int(IndexBase::*fn)(pageId id))
1923 {
1924   pageId r;
1925   keyBlock *sbb;  Page *spp;  char *sn;
1926   if_err( db->indexRead(s,0,sbb,spp,sn) );
1927   unsigned char *lp = (unsigned char *)sn;
1928   unsigned char *rp = lp + spp->iused();
1929   if( (r=sbb->right_link()) >= 0 ) {
1930     while( lp < rp ) {
1931       pageId l = getPageId(lp);
1932       lp += st->dataSz;  ++lp;
1933       while( *lp++ != 0 );
1934       if_ret( keyMap(l,fn) );
1935     }
1936     if_ret( keyMap(r,fn) );
1937   }
1938   if_err( (this->*fn)(s) );
1939   return 0;
1940 }
1941
1942 /***
1943  *  Db::IndexString::kpress -- compresses kp with prefix
1944  *
1945  *  parameters
1946  * kp     unsigned char *    input        key string to compress
1947  * lp     unsigned char *    input        left prefix
1948  * cp     unsigned char *    output       compressed string
1949  *
1950  * returns length of compressed string cp
1951  *   safe to kpress buffer in place over cp or lp
1952  */
1953
1954 int Db::IndexString::
1955 kpress(unsigned char *kp, unsigned char *lp, unsigned char *cp)
1956 {
1957   unsigned char ch;
1958   int n = 0, len = 0;
1959   while( *kp == *lp ) {
1960     ++n; ++lp; ++kp;
1961   }
1962   do {
1963     ch = *kp++;  *cp++ = n;
1964     ++len;       n = ch;
1965   } while( n != 0);
1966   *cp = 0;
1967   return ++len;
1968 }
1969
1970 /*
1971  *  divide tbfr length n into sectors l and s with rlink r
1972  *   if i >= 0 then the insert point is i
1973  *   if l<0 allocate l
1974  *  promoted key in tky, return left sector
1975  */
1976
1977 int Db::IndexString::
1978 split(int n, int i, pageId s, pageId &l, pageId r)
1979 {
1980   unsigned char lky[keysz];
1981   unsigned char *bp = &tbfr[0];
1982   unsigned char *lp = bp;
1983   unsigned char *rp = bp + n;
1984   unsigned char *kp = lp;
1985   unsigned char *tp = 0;
1986   pageId t = NIL, u = NIL;
1987   keyBlock *lbb;  Page *lpp;  char *ln;
1988   if_err( l >= 0 ?
1989     db->indexRead(l,1,lbb,lpp,ln) :
1990     blockAllocate(l,lbb,lpp,ln) );
1991   int rlen = n;
1992   int blen = lpp->iallocated()-1 - st->dataSz;
1993   if( r >= 0 ) blen -= sizeof(pageId);
1994   if( n > blen ) n = blen;
1995 /* split point is middle, or end if inserting consecutive on rhs */
1996   int promoted = n/2;
1997   if( i >= 0 && cInsCount > 2 && s == st->rightHandSide )
1998     promoted = n-1;
1999   unsigned char *mp = lp + promoted;
2000   // get promoted key in lky
2001   i = 0;  lky[0] = 0;
2002   while( lp < rp ) {
2003     // expand key to lky
2004     if( r >= 0 ) u = getPageId(lp);
2005     tp = lp;  lp += st->dataSz;
2006     for( i=*lp++; (lky[i++]=*lp++) != 0; );
2007     // stop copy if past mid pt and
2008     //   remaining bytes + expanded key bytes fit in block
2009     rlen = rp - lp;
2010     if( kp != &tbfr[0] && lp >= mp && rlen+i <= blen )
2011       break;
2012     // copy promoted data/key
2013     unsigned char *tkp = tky;
2014     umemmove(tkp, tp, st->dataSz);
2015     ustrcpy(tkp, lky);
2016     // save end of left block, move to next key
2017     kp = bp;  bp = lp;  t = u;
2018   }
2019   // store left block
2020   n = kp - &tbfr[0];
2021   // must be at least 3 keys in tbfr (left,parent,right)
2022   if( !n || bp >= rp ) Err(errCorrupt);
2023   memmove(ln,&tbfr[0],n);
2024   lpp->iused(n);
2025   lbb->right_link(t);
2026   // add first key in next block, order of moves important
2027   //  memmove may be move up since key may expand past split
2028   mp = &tbfr[0];
2029   if( r >= 0 ) putPageId(mp,u);
2030   umemmove(mp, tp, st->dataSz);  // data recd
2031   *mp++ = 0;                // first prefix is zero length
2032   memmove(mp+i, lp, rlen);  // rest of block
2033   memmove(mp, &lky[0], i);   // expanded key
2034   mp += rlen + i;
2035   int slen = mp - &tbfr[0];
2036 /*
2037  *  if root is splitting, allocate new right sibling
2038  *  and set root to contain only new parent key.
2039  */
2040   keyBlock *sbb;  Page *spp;  char *sn;
2041   if_err( db->indexRead(s,1,sbb,spp,sn) );
2042   if( s == st->rootPageId ) {
2043     keyBlock *rbb;  Page *rpp;  char *rn;
2044     if_err( blockAllocate(u,rbb,rpp,rn) );
2045     rpp->iused(slen);
2046     rbb->right_link(r);
2047     memmove(rn,&tbfr[0],slen);
2048     r = u;
2049     if( st->rightHandSide == s ) st->rightHandSide = r;
2050     mp = (unsigned char *)sn;
2051     putPageId(mp,l);
2052     umemmove(mp, kp=&tky[0], st->dataSz);
2053     kp += st->dataSz;
2054     for( *mp++=0; (*mp++=*kp++)!=0; );
2055     slen = mp - (unsigned char *)sn;
2056   }
2057   else
2058     memmove(sn, &tbfr[0], slen);
2059   sbb->right_link(r);
2060   spp->iused(slen);
2061   return 0;
2062 }
2063
2064 int Db::IndexString::
2065 chkInsert(void *key, void *data)
2066 {
2067   unsigned char *ky = (unsigned char *)key;
2068   pageId s = lastInsert.id;
2069   if( s < 0 ) return 0;                         // must be valid
2070   int n = ustrcmp(&lastInsKey[0],ky);
2071   if( !n ) Fail(errDuplicate);
2072   keyBlock *sbb;  Page *spp;  char *sn;
2073   if_err( db->indexRead(s,0,sbb,spp,sn) );
2074   if( sbb->right_link() >= 0 ) return 0;        // must be leaf
2075   int slen = spp->iused();
2076   int k = lastInsert.offset - sizeof(keyBlock);
2077   if( k < 0 || k >= slen ) return 0;            // must be inside block
2078   unsigned char *bp = (unsigned char *)sn;
2079   unsigned char *lp = bp;
2080   unsigned char *rp = bp + k;                   // beginning to current
2081   unsigned char *tp = bp + slen;
2082   unsigned char nky[keysz];  nky[0] = 0;
2083   if( n < 0 ) {                                 // past here
2084     ustrcpy(&nky[0],&lastInsKey[0]);
2085     lp = rp;  rp = tp;
2086   }
2087   else {                                        // before here
2088     n = ustrcmp(bp+st->dataSz+1,ky);
2089     if( !n ) Fail(errDuplicate);
2090     if( n > 0 ) return 0;                       // before first
2091     unsigned char rb;  rp += st->dataSz;        // move past curr data
2092     for( int i=*rp++; (rb=*rp++) == lastInsKey[i] && rb != 0; ++i );
2093     if( rb ) return 0;                          // must match curr
2094   }
2095   unsigned char lky[keysz];  lky[0] = 0;
2096   unsigned char *kp;  n = 0;
2097   while( (kp=lp) < rp ) {
2098     lp += st->dataSz;                           // scan next
2099     for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2100     n = ustrcmp(ky,&nky[0]);
2101     if( !n ) Fail(errDuplicate);
2102     if( n < 0 ) break;                          // btwn last,next
2103     ustrcpy(&lky[0],&nky[0]);
2104   }
2105   if( lp >= tp && s != st->rightHandSide ) return 0;// not found, not rhs
2106   // recompress and compute storage demand
2107   int llen = kp - (unsigned char *)sn;          // left
2108   int lsz = kpress(ky, &lky[0], &lky[0]);       // lky = kpress new key
2109   int mlen = st->dataSz + lsz;
2110   int klen = mlen;                              // new key demand
2111   int nsz = 0;
2112   if( kp < rp ) {                               // if next key exists
2113     nsz = kpress(&nky[0], ky, &nky[0]);
2114     mlen += st->dataSz + nsz;                   // new+next key demand
2115   }
2116   int rlen = tp - lp;                           // right
2117   int blen = llen + mlen + rlen;                // left + demand + right
2118
2119   if( blen > spp->iallocated() ) return 0;      // if insertion wont fit
2120   Page &spg = *spp;
2121   spg->set_flags(fl_wr);
2122   if( kp < rp ) {                               // insert not at end of block
2123     memmove(kp+mlen, lp, rlen);                 // move right up
2124     memmove(kp+klen, kp, st->dataSz);           // move next data up
2125     memmove(kp+klen+st->dataSz,&nky[0],nsz);    // kpress next key
2126   }
2127   k = kp - (unsigned char *)sn;
2128   lastAccess.id = lastInsert.id;
2129   lastAccess.offset = sizeof(keyBlock) + k;
2130   ustrcpy(&lastAccKey[0],ky);
2131   umemmove(kp,(unsigned char *)data,st->dataSz); // insert new key
2132   umemmove(kp,&lky[0],lsz);
2133   spp->iused(blen);
2134   return 1;
2135 }
2136
2137 /*
2138  *      insert - add node to compressed b-tree.
2139  *      entry - tky - data/key to add
2140  *              s  - root of tree/subtree
2141  *              t  - NIL/discontinue or tky->left_link
2142  */
2143 int Db::IndexString::
2144 keyInsert(pageId &t, pageId s)
2145 {
2146   unsigned char lky[keysz];         // last key
2147   unsigned char nky[keysz];         // next key
2148   keyBlock *sbb;  Page *spp;  char *sn;
2149   if_err( db->indexRead(s,1,sbb,spp,sn) );
2150   t = NIL;  // set discontinue insertion
2151   pageId l = NIL;
2152   pageId r = sbb->right_link();
2153   lky[0] = 0;
2154   int n = spp->iused();
2155   unsigned char *lp = (unsigned char *)sn;      // rest of block
2156   unsigned char *rp = lp + n;                   // end of block
2157   unsigned char *kp = 0;                        // insertion point
2158   unsigned char *tkp = &tky[st->dataSz];            // tky = data/key
2159
2160   while( (kp=lp) < rp ) {                       // search
2161     if( r >= 0 ) l = getPageId(lp);
2162     lp += st->dataSz;
2163     for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2164     n = ustrcmp(&tkp[0], &nky[0]);
2165     if( n < 0 ) break;
2166     if( n == 0 ) Fail(errDuplicate);
2167     ustrcpy(lky, nky);
2168   }
2169   // if non-terminal block, continue search at lower levels
2170   // if lower level splits( t>=0 ), process insertion
2171   if( r >= 0 ) {
2172     if_ret( keyInsert(t, kp>=rp ? r : l) );
2173     if( t < 0 ) return 0;                       // discontinue
2174   }
2175
2176   // recompress and compute storage demand
2177   int llen = kp - (unsigned char *)sn;          // left
2178   int lsz = kpress(tkp, &lky[0], &lky[0]);      // lky = kpress new key
2179   int dsz = st->dataSz;
2180   if( r >= 0 ) dsz += sizeof(pageId);           // link+data size
2181   int mlen = dsz + lsz;
2182   int klen = mlen;                              // new key demand
2183   int nsz = 0;
2184   if( kp < rp ) {                               // if next key exists
2185     nsz = kpress(&nky[0], &tkp[0], &nky[0]);
2186     mlen += dsz + nsz;                          // new+next key demand
2187   }
2188   int rlen = rp - lp;                           // right
2189   int blen = llen + mlen + rlen;                // left + demand + right
2190
2191   if( blen <= spp->iallocated() ) {             // if insertion will fit
2192     if( kp < rp ) {                             // insert not at end of block
2193       memmove(kp+mlen, lp, rlen);               // move right up
2194       memmove(kp+klen, kp, dsz);                // move next link/data up
2195       memmove(kp+klen+dsz,&nky[0],nsz);         // kpress next key
2196     }
2197     if( r >= 0 ) putPageId(kp, t);
2198     if( lastAccess.id < 0 ) {                   // update lastAccess
2199       lastAccess.id = s;
2200       int k = kp - (unsigned char *)sn;
2201       lastAccess.offset = sizeof(keyBlock) + k;
2202       ustrcpy(&lastAccKey[0],&tkp[0]);
2203     }
2204     umemmove(kp,&tky[0],st->dataSz);            // insert new key
2205     memmove(kp,&lky[0],lsz);
2206     t = NIL;
2207     spp->iused(blen);
2208   }
2209   else {
2210     unsigned char *bp = &tbfr[0];               // overflowed, insert to tbfr
2211     umemmove(bp,(unsigned char *)sn,llen);
2212     if( r >= 0 ) putPageId(bp, t);
2213     umemmove(bp,&tky[0],st->dataSz);            // insert new key
2214     umemmove(bp,&lky[0],lsz);
2215     if( kp < rp ) {                             // insert not at end of block
2216       umemmove(bp,kp,dsz);
2217       umemmove(bp,&nky[0],nsz);                 // kpress next key
2218       umemmove(bp,lp,rlen);                     // copy rest of block
2219     }
2220     t = NIL;
2221     if_err( split(blen,llen,s,t,r) );           // split block, and continue
2222   }
2223   return 0;
2224 }
2225
2226 int Db::IndexString::
2227 Insert(void *key,void *data)
2228 {
2229   if_err( MakeRoot() );
2230   int ret = 0;
2231   if( CHK cInsCount > 2 ) {                     // try the easy way
2232     ret = chkInsert(key,data);
2233     if_ret( ret );
2234   }
2235   if( !ret ) {                                  // try the hard way
2236     unsigned char *tp = &tky[0];
2237     umemmove(tp,(unsigned char *)data,st->dataSz);
2238     ustrcpy(tp,(unsigned char*)key);
2239     pageId t = NIL;  lastAccess.id = NIL;
2240     if_ret( keyInsert(t, st->rootPageId) );
2241   }
2242   ustrcpy(&lastInsKey[0],&lastAccKey[0]);
2243   chkLastInsert();
2244   ++st->count;
2245   return 0;
2246 }
2247
2248
2249 int Db::IndexString::
2250 keyFirst(pageId s)
2251 {
2252   keyBlock *sbb;
2253   if_err( db->indexRead(s,0,sbb) );
2254   char *sn = (char *)(sbb+1);
2255
2256   while( sbb->right_link() >= 0 ) {
2257     s = readPageId(sn);
2258     if_err( db->indexRead(s,0,sbb) );
2259     sn = (char *)(sbb+1);
2260   }
2261
2262   lastAccess.id = s;
2263   lastAccess.offset = sizeof(keyBlock);
2264   unsigned char *kp = (unsigned char *)sn;
2265   ustrcpy(&lastAccKey[0],kp+st->dataSz+1);
2266   return 0;
2267 }
2268
2269 int Db::IndexString::
2270 First(void *rtnKey,void *rtnData)
2271 {
2272   if( st->rootPageId == NIL ) Fail(errNotFound);
2273   if_ret( keyFirst(st->rootPageId) );
2274   if( rtnKey )
2275     ustrcpy((unsigned char *)rtnKey,&lastAccKey[0]);
2276   if( rtnData ) {
2277     char *kp = 0;
2278     if_err( db->addrRead_(lastAccess,kp) );
2279     memmove(rtnData,kp,st->dataSz);
2280   }
2281   ustrcpy(&lastNxtKey[0],&lastAccKey[0]);
2282   lastNext = lastAccess;
2283   return 0;
2284 }
2285
2286 int Db::IndexString::
2287 keyLast(pageId s)
2288 {
2289   keyBlock *sbb;
2290   if_err( db->indexRead(s,0,sbb) );
2291   pageId u;
2292
2293   while( (u=sbb->right_link()) >= 0 ) {
2294     if_err( db->indexRead(s=u,0,sbb) );
2295   }
2296
2297   unsigned char lky[keysz];
2298   Page *spp = db->get_page(s);
2299   char *sn = (char *)(sbb+1);
2300   unsigned char *lp = (unsigned char *)sn;
2301   unsigned char *rp = lp + spp->iused();
2302   unsigned char *kp = 0;
2303   lky[0] = 0;
2304
2305   while( lp < rp ) {
2306     kp = lp;  lp += st->dataSz;
2307     for( int i=*lp++; (lky[i]=*lp++) != 0; ++i );
2308   }
2309
2310   if( !kp ) Fail(errNotFound);
2311   int k = kp - (unsigned char *)sn;
2312   lastAccess.id = s;
2313   lastAccess.offset = sizeof(keyBlock) + k;
2314   ustrcpy(&lastAccKey[0],&lky[0]);
2315   return 0;
2316 }
2317
2318 int Db::IndexString::
2319 Last(void *rtnKey,void *rtnData)
2320 {
2321   if( st->rootPageId == NIL ) Fail(errNotFound);
2322   if_ret( keyLast(st->rootPageId) );
2323   if( rtnKey )
2324     ustrcpy((unsigned char *)rtnKey,&lastAccKey[0]);
2325   if( rtnData ) {
2326     char *kp = 0;
2327     if_err( db->addrRead_(lastAccess,kp) );
2328     memmove(rtnData,kp,st->dataSz);
2329   }
2330   ustrcpy(&lastNxtKey[0],&lastAccKey[0]);
2331   lastNext = lastAccess;
2332   return 0;
2333 }
2334
2335 int Db::IndexString::
2336 chkFind(pgRef &loc, char *key, unsigned char *lkey, unsigned char *lkp)
2337 {
2338   pageId s = loc.id;
2339   if( s < 0 ) return 0;                         // must be valid block
2340   keyBlock *sbb;  Page *spp;  char *sn;
2341   if_err( db->indexRead(s,0,sbb,spp,sn) );
2342   if( sbb->right_link() >= 0 ) return 0;        // must be leaf
2343   int slen = spp->iused();
2344   int k = loc.offset - sizeof(keyBlock);
2345   if( k < 0 || k >= slen ) return 0;            // must be inside/end of block
2346   unsigned char *ky = (unsigned char *)key;
2347   unsigned char *bp = (unsigned char *)sn;
2348   unsigned char *kp = bp + k;
2349   unsigned char *rp = bp + slen;
2350   unsigned char *lp = kp;  kp += st->dataSz;
2351   unsigned char *ip = &lkey[*kp++];
2352   while( kp<rp && *kp!=0 && *ip==*kp ) { ++ip; ++kp; }
2353   if( *ip || *kp++ ) return 0;                  // must match curr
2354   int n = ustrcmp(&lkey[0], ky);
2355   if( !n && !lkp ) goto xit;                    // found here, and no last key
2356   unsigned char lky[keysz];
2357   ip = lkey;
2358   if( n > 0 ) {                                 // before here
2359     rp = lp;  lp = kp = bp;
2360     ip = lp + st->dataSz;
2361     if( *ip++ ) Err(errCorrupt);
2362     if( (n=ustrcmp(ip, ky)) > 0 ) return 0;     // before first
2363     if( !n ) { lky[0] = 0;  goto xit; }         // found here, first
2364   }
2365   ustrcpy(&lky[0], ip);
2366   while( kp < rp ) {
2367     lp = kp;  kp += st->dataSz;
2368     unsigned char nky[keysz];
2369     ustrcpy(&nky[0], &lky[0]);
2370     for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2371     n = ustrcmp(ky, &nky[0]);
2372     if( !n ) goto xit;                          // found here
2373     if( n < 0 ) Fail(errNotFound);              // btwn prev,next
2374     ustrcpy(&lky[0], &nky[0]);
2375   }
2376   return 0;                                     // not in block
2377 xit:
2378   if( lkp ) ustrcpy(lkp, &lky[0]);
2379   k = lp - bp;
2380   loc.offset = sizeof(keyBlock) + k;
2381   return 1;
2382 }
2383
2384 int Db::IndexString::
2385 keyFind(pgRef &loc,unsigned char *ky)
2386 {
2387   unsigned char nky[keysz];
2388
2389   for( pageId s=st->rootPageId; s>=0; ) {
2390     keyBlock *sbb;  Page *spp;  char *sn;
2391     if_err( db->indexRead(s,0,sbb,spp,sn) );
2392     unsigned char *lp = (unsigned char *)sn;
2393     unsigned char *rp = lp + spp->iused();
2394     pageId l = NIL;
2395     pageId r = sbb->right_link();
2396     while( lp < rp ) {
2397       if( r >= 0 ) l = getPageId(lp);
2398       unsigned char *kp = lp;
2399       lp += st->dataSz;
2400       for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2401       int n = ustrcmp(ky, &nky[0]);
2402       if( n == 0 ) {
2403         loc.id = s;
2404         int k = kp - (unsigned char *)sn;
2405         loc.offset = sizeof(keyBlock) + k;
2406         return 0;
2407       }
2408       if( n < 0 ) { r = l; break; }
2409     }
2410     s = r;
2411   }
2412   Fail(errNotFound);
2413 }
2414
2415
2416 int Db::IndexString::
2417 refFind(pgRef &loc, void *key)
2418 {
2419   if( st->rootPageId == NIL ) Fail(errNotFound);
2420   int ret = 0;
2421 { locked by(idxLk);
2422   loc = lastFind;
2423   if( CHK cFindCount > 2 ) ret = 1; }
2424   if( ret ) {                   // try the easy way
2425     ret = chkFind(loc,(char *)key,&lastFndKey[0]);
2426     if_ret( ret );
2427   }
2428   if( !ret ) {                  // try the hard way
2429     if_fail( keyFind(loc, (unsigned char *)key) );
2430   }
2431 { locked by(idxLk);
2432   chkLastFind(loc);
2433   ustrcpy(&lastAccKey[0],(unsigned char *)key);
2434   ustrcpy(&lastFndKey[0],&lastAccKey[0]);
2435   ustrcpy(&lastNxtKey[0],&lastAccKey[0]); }
2436   return 0;
2437 }
2438
2439 int Db::IndexString::
2440 Find(void *key, void *rtnData)
2441 {
2442   pgRef last;
2443   if_fail( refFind(last, key) );
2444   char *kp = 0;
2445   if( !db->addrRead_(last,kp) ) {
2446     if( rtnData )
2447       memmove(rtnData,kp,st->dataSz);
2448   }
2449   return 0;
2450 }
2451
2452
2453 /*
2454  *  remap sectors on underflow
2455  *    s - parent sector, t - pageId if overflowed
2456  *    k - parent key offset
2457  *    updates tky with parent data/key
2458  */
2459
2460 int Db::IndexString::
2461 keyUnderflow(pageId s, pageId &t, int k)
2462 {
2463   unsigned char lky[keysz], nky[keysz];
2464   keyBlock *sbb;  Page *spp;  char *sn;
2465   if_err( db->indexRead(s,1,sbb,spp,sn) );
2466   unsigned char *lp = (unsigned char *)sn;
2467   unsigned char *rp = lp + spp->iused();
2468   unsigned char *kp = lp + k;
2469   unsigned char *mp = &tbfr[0];
2470   // mark continue underlow
2471   t = NIL;
2472   pageId r = sbb->right_link();
2473   lky[0] = nky[0] = 0;
2474   //  if underflow, copy to parent key offset
2475   while( lp < kp ) {
2476     putPageId(mp,getPageId(lp));
2477     umemmove(mp,lp,st->dataSz);  lp += st->dataSz;
2478     for( int i=*mp++=*lp++; (lky[i]=*mp++=*lp++) != 0; ++i );
2479   }
2480   // read l, key, r --  remove key from parent block
2481   unsigned char *tp = &tky[0];
2482   pageId l = getPageId(lp);
2483   umemmove(tp,lp,st->dataSz);  lp += st->dataSz;
2484   ustrcpy(tp,&lky[0]);
2485   for( int i=*lp++; (tp[i]=*lp++) != 0; ++i );
2486   if( lp < rp ) {
2487     putPageId(mp, r=getPageId(lp));
2488     umemmove(mp,lp,st->dataSz);  lp += st->dataSz;
2489     ustrcpy(&nky[0],tp);
2490     for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2491     mp += kpress(&nky[0],&lky[0],mp);
2492     umemmove(mp,lp,rp-lp);
2493   }
2494   int n = mp-&tbfr[0];
2495   memmove(sn,&tbfr[0],n);
2496   spp->iused(n);
2497   // copy l to tbfr
2498   keyBlock *lbb;  Page *lpp;  char *ln;
2499   if_err( db->indexRead(l,1,lbb,lpp,ln) );
2500   lp = (unsigned char *)ln;
2501   rp = lp + lpp->iused();
2502   pageId m = lbb->right_link();
2503   mp = &tbfr[0];  nky[0] = 0;
2504   while( lp < rp ) {
2505     if( m >= 0 ) putPageId(mp,getPageId(lp));
2506     umemmove(mp,lp,st->dataSz);  lp += st->dataSz;
2507     for( int i=*mp++=*lp++; (nky[i]=*mp++=*lp++) != 0; ++i );
2508   }
2509   // parent key to tbfr
2510   if( m >= 0 ) putPageId(mp,m);
2511   umemmove(mp,&tky[0],st->dataSz);
2512   mp += kpress(tp,&nky[0],mp);
2513   // copy r to tbfr
2514   keyBlock *rbb;  Page *rpp;  char *rn;
2515   if_err( db->indexRead(r,1,rbb,rpp,rn) );
2516   lp = (unsigned char *)rn;
2517   rp = lp + rpp->iused();
2518   m = rbb->right_link();
2519   if( lp < rp ) {
2520     if( m >= 0 ) putPageId(mp,getPageId(lp));
2521     umemmove(mp,lp,st->dataSz);  lp += st->dataSz;
2522     for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2523     mp += kpress(&nky[0],tp,mp);
2524     umemmove(mp,lp,rp-lp);
2525   }
2526   n = mp - &tbfr[0];
2527   if( n > rpp->iallocated() ) {
2528     // tbfr too big for r
2529     if_err( split(n, -1, r, l, m) );
2530     t = l;   // start overflow
2531   }
2532   else {
2533     if( s == st->rootPageId && !spp->iused() ) {
2534       // if root, delete r
2535       memmove(sn,&tbfr[0],n);
2536       spp->iused(n);
2537       sbb->right_link(m);
2538       if_err( blockFree(r) );
2539       st->rightHandSide = s;
2540     }
2541     else {
2542       // update r with tbfr
2543       memmove(rn,&tbfr[0],n);
2544       rpp->iused(n);
2545       rbb->right_link(m);
2546     }
2547     if_err( blockFree(l) );
2548   }
2549   return 0;
2550 }
2551
2552 /*
2553  *  remap sectors on overflow
2554  *    s - parent sector, k - parent key offset, o - insertion offset
2555  *    t parent link on input,
2556  *    t == DDONE on output, end overflow
2557  *    tky with parent data/key
2558  */
2559 int Db::IndexString::
2560 keyOverflow(pageId s, pageId &t, int k, int o)
2561 {
2562   unsigned char lky[keysz], nky[keysz];
2563   keyBlock *sbb;  Page *spp;  char *sn;
2564   if_err( db->indexRead(s,1,sbb,spp,sn) );
2565   unsigned char *lp = (unsigned char *)sn;
2566   unsigned char *rp = lp + spp->iused();
2567   unsigned char *kp = lp + k;
2568   unsigned char *mp = &tbfr[0];
2569   pageId r = sbb->right_link();
2570   lky[0] = nky[0] = 0;
2571   // copy parent up to parent key to tbfr
2572   while( lp < kp ) {
2573     putPageId(mp,getPageId(lp));
2574     umemmove(mp,lp,st->dataSz);  lp += st->dataSz;
2575     for( int i=*mp++=*lp++; (lky[i]=*mp++=*lp++) != 0; ++i );
2576   }
2577   // if at insertion point, add new key
2578   if( o <= k ) {
2579     putPageId(mp,t);
2580     unsigned char *tp = &tky[0];
2581     umemmove(mp,tp,st->dataSz);  tp += st->dataSz;
2582     mp += kpress(kp=tp, &lky[0], mp);
2583   }
2584   else
2585     kp = &lky[0];
2586   // copy parent key, if insertion - add tky, copy rest
2587   if( lp < rp ) {
2588     ustrcpy(&nky[0],kp);
2589     putPageId(mp,getPageId(lp));
2590     umemmove(mp,lp,st->dataSz);  lp += st->dataSz;
2591     for( int i=*lp++; (lky[i]=*lp++) != 0; ++i );
2592     mp += kpress(&lky[0],&nky[0],mp);
2593     if( o > k ) {
2594       putPageId(mp,t);
2595       unsigned char *tp = &tky[0];
2596       umemmove(mp,tp,st->dataSz);  tp += st->dataSz;
2597       mp += kpress(tp, &lky[0], mp);
2598       ustrcpy(&lky[0],tp);
2599     }
2600     if( lp < rp ) {
2601       putPageId(mp,getPageId(lp));
2602       umemmove(mp,lp,st->dataSz);  lp += st->dataSz;
2603       ustrcpy(&nky[0],&lky[0]);
2604       for( int i=*lp++; (lky[i]=*lp++) != 0; ++i );
2605       mp += kpress(&lky[0],&nky[0],mp);
2606     }
2607     umemmove(mp,lp,rp-lp);
2608   }
2609   int n = mp - &tbfr[0];
2610   // if overflow, split sector and promote new parent key
2611   if( n > spp->iallocated() ) {
2612     t = NIL;  lastAccess.id = NIL;
2613     if_ret( split(n, -1, s, t, r) );
2614   }
2615   else {
2616     t = DDONE;
2617     spp->iused(n);
2618     sbb->right_link(r);
2619     memmove(sn,&tbfr[0],n);
2620   }
2621   return 0;
2622 }
2623
2624 int Db::IndexString::
2625 keyRemap(pageId s, pageId &t, int k, int o)
2626 {
2627   if( t < 0 ) {
2628     if_err( keyUnderflow(s,t,k) );
2629     o = k;
2630   }
2631   if( t >= 0 )
2632     if_err( keyOverflow(s,t,k,o) );
2633   return 0;
2634 }
2635
2636 /*
2637  *  delete or replace key
2638  *   s  - starting sector, nky - replacement key if != 0
2639  *   t - returned state -2/done,-1/underflow,pageid/overflow
2640  */
2641
2642 int Db::IndexString::
2643 keyDelete(pageId s, pageId &t)
2644 {
2645   unsigned char lky[keysz], nky[keysz];
2646   unsigned char *ky = &akey[0];
2647
2648   keyBlock *sbb;  Page *spp;  char *sn;
2649   if_err( db->indexRead(s,1,sbb,spp,sn) );
2650   unsigned char *bp = (unsigned char *)sn;
2651   unsigned char *lp = bp;
2652   unsigned char *rp = lp + spp->iused();
2653   unsigned char *kp = lp;
2654   unsigned char *mp = 0;
2655   int n = -1;
2656   pageId l = NIL;
2657   pageId r = sbb->right_link();
2658   lky[0] = nky[0] = 0;
2659   // mark delete done and search
2660   t = DDONE;
2661   while( (kp=lp) < rp ) {
2662     mp = lp;
2663     if( r >= 0 ) l = getPageId(lp);
2664     lp += st->dataSz;
2665     for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2666     if( idf <= 0 && (n=ustrcmp(ky,&nky[0])) <= 0)
2667       break;
2668     ustrcpy(&lky[0],&nky[0]);
2669   }
2670   if( n != 0 ) {
2671     if( r < 0 ) {
2672       if( !idf ) Fail(errNotFound);
2673       // found greatest node less than ky, delete and return with underflow
2674       // deleted key must be on rt side of block to be next to interior key
2675       unsigned char *dp = &dky[0];
2676       umemmove(dp,mp,st->dataSz);
2677       ustrcpy(dp,&nky[0]);
2678       spp->iused(mp-bp);
2679       t = NIL;  // start underflow
2680     }
2681     else {
2682       // not found in block, try next level
2683       int status = keyDelete(kp<rp ? l : r,t);
2684       if_ret( status );
2685       if( t != DDONE )
2686         if_ret( keyRemap(s,t,mp-bp,kp-bp) );
2687     }
2688   }
2689   else if( r < 0 || idf < 0 ) {                 // found here
2690     int llen = kp - bp;
2691     int mlen = 0;
2692     int dsz = st->dataSz;
2693     if( r >= 0 ) dsz += sizeof(pageId);
2694     unsigned char *tp = &lky[0];
2695     int lsz = 0;
2696     if( idf < 0 ) {                             // translating data/key
2697       lsz = kpress(&dky[st->dataSz],tp,tp);     // kpress dky to lky
2698       mlen += dsz + lsz;
2699       tp = &dky[st->dataSz];
2700     }
2701     int nsz = 0;
2702     unsigned char *np = lp;
2703     lastAccKey[0] = 0;
2704     if( lp < rp ) {
2705       lp += dsz;                                // get next key
2706       for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2707       if( r < 0 ) ustrcpy(&lastAccKey[0],&nky[0]);// new curr key
2708       nsz = kpress(&nky[0],tp,&nky[0]);
2709       mlen += dsz + nsz;
2710     }
2711     int rlen = rp - lp;
2712     int slen = llen + mlen + rlen;
2713     unsigned char *sp = &tbfr[0];
2714     mp = sp;
2715     if( (llen > 0 || rlen > 0) &&               // at least 3 data/keys
2716         slen <= spp->iallocated() ) {           // and fits in block
2717       sp = bp;  mp = kp;                        // edit in place
2718     }
2719     else
2720       umemmove(mp,bp,llen);                      // use tbfr, copy left
2721     if( np < rp ) {                             // next exists
2722       tp = mp + mlen;
2723       unsigned char *ip = mp;
2724       if( idf < 0 ) ip += dsz + lsz;
2725       if( sp == bp && tp > lp ) {
2726         memmove(tp,lp,rlen);                    // up copy/move right
2727         memmove(ip,np,dsz);  ip += dsz;         // next link/data/key
2728         memmove(ip,&nky[0],nsz);
2729       }
2730       else {
2731         memmove(ip,np,dsz);  ip += dsz;         // next link/data/key
2732         memmove(ip,&nky[0],nsz);
2733         if( tp != lp )
2734           memmove(tp,lp,rlen);                  // down copy/move right
2735       }
2736     }
2737     if( idf < 0 ) {                             // move exterior key
2738       if(r >= 0) putPageId(mp,getPageId(kp));
2739       umemmove(mp,&dky[0],st->dataSz);          // add dky data/key
2740       umemmove(mp,&lky[0],lsz);
2741     }
2742     if( sp == bp ) {                            // in place
2743       t = DDONE;
2744       spp->iused(slen);
2745       if( r < 0 ) {
2746         lastAccess.id = s;                      // position to curr
2747         lastAccess.offset = sizeof(keyBlock) + llen;
2748         ustrcpy(&lastAccKey[0],ky);
2749       }
2750     }
2751     else {
2752       t = NIL;
2753       if( slen > spp->iallocated() ) {
2754         if_ret( split(slen, -1, s, t, r) );     // continue with overflow
2755       }
2756       else {
2757         memmove(sn,&tbfr[0],slen);               // continue with underflow
2758         spp->iused(slen);
2759       }
2760     }
2761   }
2762   else {
2763     // deleting nonterminal key, translate to greatest node less than ky
2764     idf = 1;
2765     int status = keyDelete(l,t);
2766     if_ret( status );
2767      if( t != DDONE )
2768       if_ret( keyRemap(s,t,mp-bp,kp-bp) );
2769   }
2770   return 0;
2771 }
2772
2773
2774 int Db::IndexString::
2775 Delete(void *key)
2776 {
2777   if( st->rootPageId == NIL ) Fail(errNotFound);
2778   unsigned char lky[keysz];  lky[0] = 0;
2779   pgRef *last = &lastDelete;
2780   unsigned char *lkey = &lastDelKey[0];
2781   int ret = 0;
2782   if( CHK cDelCount > 2 ) {                     // try the easy way
2783     if( lastFind.id >= 0 ) {                    // chk find/delete
2784       if( !ustrcmp((unsigned char *)key,&lastFndKey[0]) ) {
2785         last = &lastFind;  lkey = &lastFndKey[0];
2786       }
2787     }
2788     ret = chkFind(*last,(char *)key,lkey,&lky[0]);
2789     if_ret( ret );
2790     if( ret > 0 ) {
2791       ret = 0;
2792       pageId s = lastAccess.id;
2793       keyBlock *sbb;  Page *spp;  char *sn;
2794       if_err( db->indexRead(s,1,sbb,spp,sn) );
2795       unsigned char *bp = (unsigned char *)sn;
2796       int slen = spp->iused();
2797       int llen = lastAccess.offset - sizeof(keyBlock);
2798       unsigned char *kp = bp + llen;            // curr data/key
2799       unsigned char *lp = kp;
2800       unsigned char *rp = bp + slen;
2801       if( lp < rp ) {
2802         lp += st->dataSz;  ++lp;  while( *lp++ ); // skip curr
2803       }
2804       int mlen = 0;
2805       int nsz = 0;
2806       unsigned char *np = lp;
2807       unsigned char nky[keysz]; nky[0] = 0;
2808       if( lp < rp ) {
2809         lp += st->dataSz;                       // get next key
2810         ustrcpy(&nky[0],(unsigned char *)key);
2811         for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2812         nsz = kpress(&nky[0],&lky[0],&lky[0]);
2813         mlen += st->dataSz + nsz;
2814       }
2815       int rlen = rp - lp;
2816       slen = llen + mlen + rlen;
2817       if( (llen > 0 || rlen > 0 ) &&            // at least 3 data/keys
2818           slen <= spp->iallocated() ) {         // and fits in block
2819         if( np < rp ) {                         // right exists
2820           unsigned char *tp = kp + mlen;
2821           umemmove(kp,np,st->dataSz);           // next data/key
2822           memmove(kp,&lky[0],nsz);
2823           if( tp != lp && rlen > 0 )
2824             memmove(tp,lp,rlen);                // move right down
2825         }
2826         spp->iused(slen);
2827         ustrcpy(&lastAccKey[0],&nky[0]);        // new curr key
2828         ret = 1;
2829       }
2830     }
2831   }
2832   if( !ret ) {                                  // try the hard way
2833     ustrcpy(&this->akey[0],(unsigned char*)key);
2834     lastAccess.id = NIL;
2835     pageId t = NIL;  idf = 0;
2836     if_ret( keyDelete(st->rootPageId,t) );
2837     if( idf ) {
2838       idf = -1;
2839       if_ret( keyDelete(st->rootPageId,t) );
2840     }
2841     if_err( UnmakeRoot() );
2842   }
2843   ustrcpy(&lastDelKey[0],&lastAccKey[0]);
2844   chkLastDelete();
2845   --st->count;
2846   return 0;
2847 }
2848
2849 int Db::IndexString::
2850 keyLocate(pgRef &last,pageId s, int &t, int op,
2851     unsigned char *ky, CmprFn cmpr, unsigned char *rky)
2852 {
2853   unsigned char lky[keysz], nky[keysz];
2854   keyBlock *sbb;  Page *spp;  char *sn;
2855   if_err( db->indexRead(s,0,sbb,spp,sn) );
2856   pageId l = NIL;
2857   pageId r = sbb->right_link();
2858   unsigned char *lp = (unsigned char *)sn;
2859   unsigned char *rp = lp + spp->iused();
2860   unsigned char *kp = 0, *mp = 0;
2861   lky[0] = nky[0] = 0;
2862   t = 0;
2863
2864   while( (kp=lp) < rp ) {
2865     if( r >= 0 ) l = getPageId(lp);
2866     kp = lp;  lp += st->dataSz;
2867     for( int i=*lp++; (nky[i]=*lp++) != 0; ++i );
2868     int n = cmpr((char *)ky,(char *)&nky[0]);
2869     if( op <= keyEQ ? n <= 0 : n < 0 ) break;
2870     ustrcpy(&lky[0],&nky[0]);
2871     mp = kp;
2872   }
2873
2874   if( r >= 0 ) {
2875     int status = keyLocate(last, (kp<rp ? l : r), t, op, ky, cmpr, rky);
2876     if( !t && status == errNotFound ) status = 0;
2877     if_ret( status );
2878   }
2879
2880   if( !t ) {
2881     if( op == keyLT || op == keyGE ) {
2882       if( !mp ) Fail(errNotFound);
2883       kp = mp;
2884       ustrcpy(rky,&lky[0]);
2885     }
2886     else {
2887       if( kp >= rp ) Fail(errNotFound);
2888       ustrcpy(rky,&nky[0]);
2889     }
2890     last.id = s;
2891     int k = kp - (unsigned char *)sn;
2892     last.offset = sizeof(keyBlock) + k;
2893     t = 1;
2894   }
2895   return 0;
2896 }
2897
2898
2899 int Db::IndexString::
2900 refLocate(pgRef &loc, int op,void *key,CmprFn cmpr, unsigned char *rkey)
2901 {
2902   if( st->rootPageId == NIL ) Fail(errNotFound);
2903   if( op == keyEQ ) op = keyLE;
2904   if( !cmpr ) cmpr = cmprStr;
2905   int t = 0;
2906   if_fail( keyLocate(loc,st->rootPageId,t,op,(unsigned char*)key,cmpr, rkey) );
2907 { locked by(idxLk);
2908   chkLastFind(loc);
2909   ustrcpy(&lastAccKey[0], rkey);
2910   ustrcpy(&lastNxtKey[0],&lastAccKey[0]); }
2911   return 0;
2912 }
2913
2914 int Db::IndexString::
2915 Locate(int op,void *key,CmprFn cmpr,void *rtnKey,void *rtnData)
2916 {
2917   pgRef last;  uint8_t rkey[keysz];
2918   if_fail( refLocate(last, op, key, cmpr, rkey) );
2919   if( rtnKey )
2920     ustrcpy((unsigned char *)rtnKey, rkey);
2921   if( rtnData ) {
2922     char *kp = 0;
2923     if_err( db->addrRead_(last,kp) );
2924     memmove(rtnData,kp,st->dataSz);
2925   }
2926   return 0;
2927 }
2928
2929
2930 int Db::IndexString::
2931 Modify(void *key,void *recd)
2932 {
2933   if_fail( Find(key,0) );
2934   char *bp = 0;
2935   if_err( db->addrWrite_(lastAccess,bp) );
2936   memmove(bp,recd,st->dataSz);
2937   return 0;
2938 }
2939
2940 int Db::IndexString::
2941 keyNext(pgRef &loc, unsigned char *rky)
2942 {
2943   unsigned char lky[keysz];  lky[0] = 0;
2944   pageId s = loc.id;
2945   keyBlock *sbb;  Page *spp;  char *sn;
2946   if_err( db->indexRead(s,0,sbb,spp,sn) );
2947   unsigned char *bp = (unsigned char *)sn;
2948   int k = loc.offset - sizeof(keyBlock);
2949   unsigned char *lp = bp;
2950   unsigned char *kp = bp + k;
2951   unsigned char *rp = bp + spp->iused();
2952   if( kp >= rp ) Err(errInvalid);
2953   pageId r = sbb->right_link();
2954   if( &loc != &lastNext ) {                     // find last key
2955     while( lp <= kp ) {                         // until past last
2956       if( r >= 0 ) lp += sizeof(pageId);
2957       bp = lp;  lp += st->dataSz;
2958       for( int i=*lp++; (lky[i]=*lp++) != 0; ++i );
2959     }
2960   }
2961   else {
2962     ustrcpy(&lky[0],&lastNxtKey[0]);
2963     lp = kp;  lp += st->dataSz;                 // verify lastNext
2964     unsigned char *ip = &lky[*lp++];
2965     while( lp<rp && *lp!=0 && *ip==*lp ) { ++ip; ++lp; }
2966     if( *ip || *lp++ ) Fail(errInvalid);        // bad lastNxtKey
2967   }
2968   if( r < 0 && lp < rp ) {                      // exterior and more data
2969     ustrcpy(rky, lky);
2970     bp = lp;  lp += st->dataSz;
2971     for( int i=*lp++; lp<rp && (rky[i]=*lp) != 0; ++i,++lp );
2972     if( *lp ) Err(errCorrupt);
2973     loc.offset = (bp-(unsigned char *)sn) + sizeof(keyBlock);
2974     return 0;
2975   }
2976   int t = 0;
2977   if_fail( keyLocate(loc,st->rootPageId,t,keyGT,lky,cmprStr, rky) );
2978   return 0;
2979 }
2980
2981 int Db::IndexString::
2982 Next(pgRef &loc,void *rtnKey,void *rtnData)
2983 {
2984   if( st->rootPageId == NIL ) Fail(errNotFound);
2985   unsigned char rky[keysz];
2986   if_ret( keyNext(loc, rky) );
2987 { locked by(idxLk);
2988   ustrcpy(&lastAccKey[0], rky);
2989   if( rtnKey )
2990     ustrcpy((unsigned char *)rtnKey,&lastAccKey[0]);
2991   if( rtnData ) {
2992     char *kp = 0;
2993     if_err( db->addrRead_(loc,kp) );
2994     memmove(rtnData,kp,st->dataSz);
2995   }
2996   if( &loc == &lastNext )
2997     ustrcpy(&lastNxtKey[0],&lastAccKey[0]);
2998   lastAccess = lastNext = loc; }
2999   return 0;
3000 }
3001
3002 void Db::IndexString::
3003 init()
3004 {
3005 }
3006
3007 Db::IndexString::
3008 IndexString(Db *zdb, int zidx, int dsz)
3009  : IndexBase(zdb, idxStr, zidx, 0, dsz)
3010 {
3011   sst = new(st+1) IndexStringStorage();
3012   dky = new unsigned char[st->dataSz+keysz+1];
3013   tky = new unsigned char[st->dataSz+keysz+1];
3014   tbfr = new unsigned char[3*st->blockSize];
3015   init();
3016 }
3017
3018 Db::IndexString::
3019 IndexString(Db *zdb, IndexBaseStorage *b, IndexStringStorage *d)
3020  : IndexBase(zdb, *b)
3021 {
3022   sst = d;
3023   dky = new unsigned char[st->dataSz+keysz+1];
3024   tky = new unsigned char[st->dataSz+keysz+1];
3025   tbfr = new unsigned char[3*st->blockSize];
3026   init();
3027 }
3028
3029 Db::IndexString::
3030 IndexString(IndexBase *ib, IndexBaseStorage *b, IndexStringStorage *d)
3031  : IndexBase(ib->db, *b)
3032 {
3033   sst = new(d) IndexStringStorage();
3034   init();
3035 }
3036
3037 Db::IndexString::
3038 ~IndexString()
3039 {
3040   delete [] tbfr;
3041   delete [] tky;
3042   delete [] dky;
3043 }
3044
3045
3046
3047 /***
3048  *  Db::IndexBase::Clear - clear index
3049  *
3050  *  parameters: none
3051  *
3052  *  returns 0 on success,
3053  *          error code otherwise
3054  */
3055
3056 int Db::IndexBase::
3057 Clear()
3058 {
3059   while( st->freeBlocks >= 0 ) {
3060     keyBlock *kbb;  pgRef loc;
3061     pageId id = st->freeBlocks;
3062     loc.id = id; loc.offset = 0;
3063     if_err( db->addrWrite_(loc,kbb) );
3064     st->freeBlocks = kbb->right_link();
3065     blockRelease(id);
3066   }
3067   if( st->rootPageId >= 0 ) {
3068     if_err( keyMap(st->rootPageId, &Db::IndexBase::blockRelease) );
3069     st->rootPageId = st->rightHandSide = NIL;
3070   }
3071   init(db);
3072   return 0;
3073 }
3074
3075 int Db::IndexBase::
3076 MakeRoot()
3077 {
3078   if( st->rootPageId == NIL ) {
3079     pageId u;  keyBlock *ubb;  Page *upp;  char *un;
3080     if_err( blockAllocate(u,ubb,upp,un) );
3081     upp->iused(0);
3082     ubb->right_link(NIL);
3083     st->rootPageId = st->rightHandSide = u;
3084   }
3085   return 0;
3086 }
3087
3088 int Db::IndexBase::
3089 UnmakeRoot()
3090 {
3091   pageId u = st->rootPageId;
3092   Page *upp = db->get_page(u);
3093   if( !upp->iused() ) {
3094     if_err( blockFree(u) );
3095     st->rootPageId = st->rightHandSide = NIL;
3096   }
3097   return 0;
3098 }
3099
3100 void Db::IndexBase::
3101 chkLastReset()
3102 {
3103   lastOp = opFind;
3104   lastAccess.id = lastDelete.id = lastInsert.id =
3105     lastFind.id = lastNext.id = NIL;
3106   lastAccess.offset = lastDelete.offset = lastInsert.offset =
3107     lastFind.offset = lastNext.offset = 0;
3108   cFindCount = cDelCount = cInsCount = 0;
3109 }
3110
3111 void Db::IndexBase::
3112 chkLastInsert()
3113 {
3114   if( lastAccess.id >= 0 && lastAccess.id == lastInsert.id )
3115     ++cInsCount;
3116   else
3117     cInsCount = 0;
3118   lastInsert = lastAccess;
3119   cDelCount = 0;  lastDelete.id = NIL;
3120   cFindCount = 0; lastFind.id = NIL;
3121   lastOp = opInsert; lastNext.id = NIL;
3122 }
3123
3124 void Db::IndexBase::
3125 chkLastDelete()
3126 {
3127   if( lastAccess.id >= 0 && lastAccess.id == lastDelete.id )
3128     ++cDelCount;
3129   else
3130     cDelCount = 0;
3131   lastDelete = lastAccess;
3132   cInsCount = 0;  lastInsert.id = NIL;
3133   cFindCount = 0; lastFind.id = NIL;
3134   lastOp = opDelete;  lastNext.id = NIL;
3135 }
3136
3137 void Db::IndexBase::
3138 chkLastFind(pgRef &last)
3139 {
3140   if( last.id >= 0 && last.id == lastFind.id )
3141     ++cFindCount;
3142   else
3143     cFindCount = 0;
3144   lastAccess = last;
3145   lastFind = last;
3146   lastNext = last;
3147   lastOp = opFind;
3148 }
3149
3150 Db::IndexBaseType::
3151 IndexBaseType(int typ)
3152 {
3153   magic = idx_magic;
3154   memset(&name[0],0,sizeof(name));
3155   type = typ;
3156 }
3157
3158 int Db::
3159 defaultBlockSizes[] = {
3160   0,                       // idxNil
3161   defaultBinaryBlockSize,  // idxBin
3162   defaultStringBlockSize,  // idxStr
3163 };
3164
3165 Db::IndexBaseRecd::
3166 IndexBaseRecd(int typ, int zidx, int ksz, int dsz)
3167 {
3168   idx = zidx;
3169   keySz = ksz;
3170   dataSz = dsz;
3171   rootPageId = NIL;
3172   rightHandSide = NIL;
3173   freeBlocks = NIL;
3174   count = 0;  pad1 = 0;
3175   blockSize = defaultBlockSizes[typ];
3176 }
3177
3178 Db::IndexBaseStorage::
3179 IndexBaseStorage(int typ, int zidx, int ksz, int dsz)
3180 {
3181   new((IndexTypeInfo *)this) IndexBaseType(typ);
3182   new((IndexRecdInfo *)this) IndexBaseRecd(typ, zidx, ksz, dsz);
3183 }
3184
3185 void Db::IndexBase::
3186 init(Db *zdb)
3187 {
3188   db = zdb;
3189   kdSz = st->keySz + st->dataSz;
3190   lastAccess.id = lastDelete.id = lastInsert.id =
3191     lastFind.id = lastNext.id = NIL;
3192   lastAccess.offset = lastDelete.offset = lastInsert.offset =
3193     lastFind.offset = lastNext.offset = 0;
3194   cFindCount = cDelCount = cInsCount = 0;
3195 }
3196
3197 Db::IndexBase::
3198 IndexBase(Db *zdb, IndexBaseStorage &d)
3199 {
3200   st = &d;
3201   init(zdb);
3202 }
3203
3204 Db::IndexBase::
3205 IndexBase(Db *db, int typ, int zidx, int ksz, int dsz)
3206 {
3207   st = new(&db->index_info[zidx]) IndexBaseStorage(typ, zidx, ksz, dsz);
3208   init(db);
3209 }
3210
3211 Db::IndexBase::
3212 ~IndexBase()
3213 {
3214 }
3215
3216
3217
3218 /*** int Db::objectHeapInsert(int sz,int pg,int off)
3219  *
3220  * insert a free space record into the entity heap
3221  *
3222  * Input
3223  *   sz     int      record size
3224  *   id     int      record id
3225  *  offset  int      record offset
3226  *
3227  * returns zero on success, error code on failure
3228  */
3229
3230 int Db::
3231 objectHeapInsert(int sz,int id,int offset,AllocCache &cache)
3232 {
3233   freeSpaceRecord free;
3234   free.size = sz;  free.id = id;  free.offset = offset;
3235   if_err( freeSpaceIndex->Insert(&free,0) );
3236   addrSpaceRecord addr;
3237   addr.id = id;  addr.offset = offset;  addr.size = sz;
3238   if_err( addrSpaceIndex->Insert(&addr,0) );
3239   return 0;
3240 }
3241
3242 /*** int Db::objectHeapDelete(int sz,int pg,int off)
3243  *
3244  * delete a free space record from the entity heap
3245  *
3246  * Input
3247  *   sz     int      record size
3248  *   id     int      record id
3249  *  offset  int      record offset
3250  *
3251  * returns zero on success, error code on failure
3252  */
3253
3254 int Db::
3255 objectHeapDelete(int sz,int id,int offset,AllocCache &cache)
3256 {
3257   freeSpaceRecord free;
3258   free.size = sz;  free.id = id;  free.offset = offset;
3259   if_err( freeSpaceIndex->Delete(&free) );
3260   addrSpaceRecord addr;
3261   addr.id = id;  addr.offset = offset;  addr.size = sz;
3262   if_err( addrSpaceIndex->Delete(&addr) );
3263   return 0;
3264 }
3265
3266 /*** int Db::pgRefGet(int &size, pgRef &loc, AllocCache &cache)
3267  *
3268  *  find existing persistent free storage.
3269  *
3270  *  parameters
3271  *   size    int        input/output requested/allocated size
3272  *   loc     pgRef &    output       locator returned for new storage
3273  *   cache   AllocCache& output      allocator cache to operate
3274  *
3275  * returns: zero on success, error code (< 0) on failure, (> 0) no avail
3276  */
3277
3278 int Db::
3279 pgRefGet(int &size, pgRef &loc, AllocCache &cache)
3280 {
3281   freeSpaceRecord look, find;
3282   look.size = size; look.id = 0; look.offset = 0;
3283   int status = freeSpaceIndex->Locate(keyGE, &look, 0, &find, 0);
3284   if( status == errNotFound ) return 1;
3285   if_err( status );
3286   // if record is at offset 0, need extra space for prefix
3287   while( !find.offset && look.size+(int)sizeof(pagePrefix) > find.size ) {
3288     status = freeSpaceIndex->Next(&find, 0);
3289     if( status == errNotFound ) return 1;
3290     if_err( status );
3291   }
3292   if_err( objectHeapDelete(find.size,find.id,find.offset,cache) );
3293   loc.id = find.id;
3294   loc.offset = find.offset ? find.offset : sizeof(pagePrefix);
3295   Page &pg = *get_page(loc.id);
3296   unsigned int ofs = loc.offset + look.size;
3297   if( ofs > pg->used ) pg->used = ofs;
3298   int sz = find.offset+find.size - ofs;
3299   if( sz >= min_heap_allocation ) {
3300     //if_err( objectHeapInsert(sz,find.id,ofs,cache) );
3301     if_err( cache.Load(this, find.id, ofs, sz) );
3302   }
3303   else
3304     size = look.size + sz;
3305   return 0;
3306 }
3307
3308 /*** int Db::pgRefNew(int &size, pgRef &loc, AllocCache &cache)
3309  *
3310  *  allocate new persistent free storage.
3311  *
3312  *  parameters
3313  *   size    int        input/output requested/allocated size
3314  *   loc     pgRef &    output       locator returned for new storage
3315  *   cache   AllocCache& output      allocator cache to operate
3316  *
3317  * returns: zero on success, error code.
3318  */
3319
3320 int Db::
3321 pgRefNew(int &size, pgRef &loc, AllocCache &cache)
3322 {
3323   pageId id = new_page();
3324   if_err( id );
3325   unsigned int sz = size + sizeof(pagePrefix);
3326   sz = entityPages(sz) * entityPageSize;
3327   Page &pg = *get_page(id);
3328   if( pg->allocated != sz ) {
3329     pageDealloc(pg);
3330     pg->allocated = sz;
3331   }
3332   pg->used = 0;
3333   loc.id = id;
3334   loc.offset = sizeof(pagePrefix);
3335   int used = loc.offset + size;
3336   int free = pg->allocated - used;
3337   if( free >= min_heap_allocation ) {
3338     //if_err( objectHeapInsert(free,id,used,cache) );
3339     if_err( cache.Load(this, id, used, free) );
3340   }
3341   else
3342     size = pg->allocated - loc.offset;
3343   return 0;
3344 }
3345
3346 /*** int Db::pgRefAllocate(int &size, pgRef &loc)
3347  *
3348  *  find persistent free storage. existing/new
3349  *    does not allocate virtual memory storage
3350  *
3351  *  parameters
3352  *   size    int        input/output requested/allocated size
3353  *   loc     pgRef &    output       locator returned for new storage
3354  *   cache   AllocCache& output      allocator cache to operate
3355  *
3356  * returns: zero on success, error code (< 0) on failure, (> 0) no avail
3357  */
3358
3359 int Db::
3360 pgRefAllocate(int &size, pgRef &loc, AllocCache &cache)
3361 {
3362   int status = pgRefGet(size, loc, cache);
3363   if_err( status );
3364   if( status )
3365     if_err( pgRefNew(size, loc, cache) );
3366   return 0;
3367 }
3368
3369 /*** int Db::objectAllocate(int typ, int &size, pgRef &loc)
3370  *
3371  *  find persistent free storage. existing/new
3372  *    does allocate virtual memory storage
3373  *    inits pagePrefix, inits allocPrefix
3374  *
3375  *  parameters
3376  *   type    int        input        entity type id
3377  *   size    int        input/output requested/allocated size
3378  *   loc     pgRef &    output       locator returned for new storage
3379  *   cache   AllocCache& output      allocator cache to operate
3380  *
3381  * returns: zero on success, error code (< 0) on failure, (> 0) no avail
3382  */
3383
3384 int Db::
3385 objectAllocate(int typ, int &size, pgRef &loc, AllocCache &cache)
3386 {
3387   int status = cache.Get(this, size, loc);
3388   if_err( status );
3389   if( !status ) {
3390     if_err( pgRefAllocate(size, loc, cache) );
3391     Page &pg = *get_page(loc.id);
3392     if( !pg->used ) {
3393       pagePrefix *bpp;  pgRef ref;
3394       ref.id = loc.id;  ref.offset = 0;
3395       if_err( addrWrite_(ref,bpp) );
3396       bpp->magic = page_magic;
3397       bpp->type = pg_entity + typ;
3398       pg->type = bpp->type;
3399     }
3400     unsigned int sz = loc.offset + size;
3401     if( pg->used < sz )
3402       pg->used = sz;
3403   }
3404   return 0;
3405 }
3406
3407 /*** int Db::objectFree(pgRef &loc)
3408  *
3409  * Purpose: Immediate release of entity memory
3410  *
3411  * Input
3412  *   loc   pgRef &    Page/offset
3413  *
3414  * returns zero on success, error code on failure
3415  */
3416
3417 int Db::objectFree(pgRef &loc,AllocCache &cache)
3418 {
3419   allocPrefix *mp;
3420   if_err( addrRead_(loc,mp) );
3421   if( mp->magic != entity_magic ) Err(errBadMagic);
3422   addrSpaceRecord addr, prev, next;
3423   /* get prev, next addrSpace free heap items near this addr */
3424   addr.size = mp->size;
3425   addr.id = loc.id;
3426   addr.offset = loc.offset;
3427   int status = addrSpaceIndex->Locate(keyLT,&addr,0,&prev,0);
3428   if( status == errNotFound ) {
3429     prev.id = NIL;
3430     status = addrSpaceIndex->Locate(keyGT,&addr,0,&next,0);
3431   }
3432   else if( !status )
3433     status = addrSpaceIndex->Next(&next,0);
3434   if( status == errNotFound ) {
3435     next.id = NIL;
3436     status = 0;
3437   }
3438   if_err( status );
3439   /* merge with prev if possible */
3440   if( prev.id == addr.id &&
3441     prev.offset + prev.size == addr.offset ) {
3442     if_err( objectHeapDelete(prev.size,prev.id,prev.offset,cache) );
3443     addr.offset = prev.offset;
3444     addr.size += prev.size;
3445   }
3446   /* merge with next if possible */
3447   if( addr.id == next.id &&
3448       addr.offset + addr.size == next.offset ) {
3449     if_err( objectHeapDelete(next.size,next.id,next.offset,cache) );
3450     addr.size += next.size;
3451   }
3452   /* reduce used block bytes if possible */
3453   Page &pg = *get_page(loc.id);
3454   if( pg->used <= addr.offset + addr.size )
3455     pg->used = addr.offset;
3456   // if only page prefix, release page, otherwise save new fragment
3457   if( pg->used == sizeof(pagePrefix) )
3458     pg.release();
3459   else
3460     if_err( objectHeapInsert(addr.size,addr.id,addr.offset,cache) );
3461   return 0;
3462 }
3463
3464 /*** int Db::blockAllocate(pageId *pid, keyBlock *&pkbb)
3465  *
3466  *  allocate persistent storage.
3467  *
3468  * Output
3469  *   pageId &     pid       page allocated
3470  *   keyBlock *&  pkbb      keyblock* pointer
3471  */
3472
3473 int Db::IndexBase::
3474 blockAllocate(pageId &pid, keyBlock *&pkbb)
3475 {
3476   locked by(db->db_info->blkAlLk);
3477   pageId id;  Page *kpp;
3478   pgRef loc;  keyBlock *kbb;
3479   if( st->freeBlocks != NIL ) {
3480     pgRef loc;
3481     id = st->freeBlocks;
3482     loc.id = id; loc.offset = 0;
3483     if_err( db->addrWrite_(loc,kbb) );
3484     st->freeBlocks = kbb->right_link();
3485     Page &kpg = *db->get_page(id);
3486     if( kpg->allocated != st->blockSize ) {
3487       db->pageDealloc(kpg);
3488       kpg->allocated = st->blockSize;
3489       if_err( db->addrWrite_(loc, kbb) );
3490     }
3491     kpp = &kpg;
3492   }
3493   else {
3494     id = db->new_page();
3495     if_err( id );
3496     loc.id = id;  loc.offset = 0;
3497     Page &kpg = *db->get_page(id);
3498     kpg->allocated = st->blockSize;
3499     if_err( db->addrWrite_(loc, kbb) );
3500     kpp = &kpg;
3501   }
3502   kbb->magic = page_magic;
3503   kbb->used = 0;
3504   kbb->type = pg_index + st->idx;
3505   kpp->iused(0);
3506   Page &kpg = *kpp;
3507   kpg->type = kbb->type;
3508   pkbb = kbb;
3509   pid = id;
3510   return 0;
3511 }
3512
3513 /*** int Db::blockFree(pageId pid)
3514  *
3515  * Purpose: delayed release database memory
3516  *
3517  * Input
3518  *   pid        int     input     Page
3519  *
3520  * returns zero on success, error code on failure
3521  */
3522
3523 int Db::IndexBase::
3524 blockFree(pageId pid)
3525 {
3526   locked by(db->db_info->blkAlLk);
3527   keyBlock *kbb = 0;
3528   pageId id = st->freeBlocks;  pgRef loc;
3529   loc.id = NIL;  loc.offset = 0;
3530 #if 0
3531   // use sorted order
3532   while( id >= 0 && id < pid ) {
3533     loc.id = id;
3534     if_err( db->addrRead_(loc,kbb) );
3535     id = kbb->right_link();
3536   }
3537 #endif
3538   if( loc.id >= 0 ) {
3539     if_err( db->addrWrite_(loc,kbb) );
3540     kbb->right_link(pid);
3541   }
3542   else
3543     st->freeBlocks = pid;
3544   loc.id = pid;
3545   if_err( db->addrWrite_(loc,kbb) );
3546   kbb->right_link(id);
3547   Page *kpp = db->get_page(pid);
3548   kpp->iused(0);
3549   return 0;
3550 }
3551
3552 int Db::IndexBase::
3553 blockRelease(pageId pid)
3554 {
3555   Page *pp = db->get_page(pid);
3556   return pp->release();
3557 }
3558
3559 int Db::IndexBase::
3560 blockLoad(pageId pid)
3561 {
3562   pgRef loc;  char *op = 0;
3563   loc.id = pid;  loc.offset = 0;
3564   return db->addrRead(loc, op);
3565 }
3566
3567 /*** int Db::deleteFreeBlock()
3568  *
3569  * Purpose: release database memory/storage
3570  *
3571  * returns zero on success, error code on failure
3572  */
3573
3574 int Db::IndexBase::
3575 deleteFreeBlocks()
3576 {
3577   pageId id;
3578   while( (id=st->freeBlocks) != NIL ) {
3579     keyBlock *kbb;  pgRef loc;
3580     loc.id = id;  loc.offset = 0;
3581     if_err( db->addrRead_(loc,kbb) );
3582     st->freeBlocks = kbb->right_link();
3583     Page &pg = *db->get_Page(id);
3584     if_err( db->storeFree(pg->wr_allocated, pg->wr_io_addr) );
3585     pg->wr_allocated = 0;  pg->wr_io_addr = NIL;
3586     if_err( db->storeFree(pg->io_allocated, pg->io_addr) );
3587     pg->io_allocated = 0;  pg->io_addr = NIL;
3588     db->free_page(id);
3589   }
3590   return 0;
3591 }
3592
3593 /*** int Db::storeInsert(int sz, ioAddr io_addr)
3594  *
3595  * insert a storage record into the storage heap
3596  *
3597  * Input
3598  *   sz      int      blob size
3599  *   io_addr ioAddr   blob addr
3600  *
3601  * returns zero on success, error code on failure
3602  */
3603
3604 int Db::
3605 storeInsert(long sz, ioAddr io_addr)
3606 {
3607 //dmsg(-1, "storeInsert %08lx/%012lx\n",sz,io_addr);
3608   freeStoreRecord free;
3609   free.size = sz;  free.io_addr = io_addr;
3610   if_err( freeStoreIndex->Insert(&free,0) );
3611 //fchk();
3612   addrStoreRecord addr;
3613   addr.io_addr = io_addr;  addr.size = sz;
3614   if_err( addrStoreIndex->Insert(&addr,0) );
3615 //achk();
3616   return 0;
3617 }
3618
3619 /*** int Db::storeDelete(int sz, ioAddr io_addr)
3620  *
3621  * delete a storage record from the storage heap
3622  *
3623  * Input
3624  *   sz      int      blob size
3625  *   io_addr ioAddr   blob addr
3626  *
3627  * returns zero on success, error code on failure
3628  */
3629
3630 int Db::
3631 storeDelete(long sz, ioAddr io_addr)
3632 {
3633 //dmsg(-1, "storeDelete %08lx/%012lx\n",sz,io_addr);
3634   freeStoreRecord free;
3635   free.size = sz;  free.io_addr = io_addr;
3636   if_err( freeStoreIndex->Delete(&free) );
3637 //fchk();
3638   addrStoreRecord addr;
3639   addr.io_addr = io_addr;  addr.size = sz;
3640   if_err( addrStoreIndex->Delete(&addr) );
3641 //achk();
3642   return 0;
3643 }
3644
3645 /*** int Db::storeGet(int &size, ioAddr &io_addr)
3646  *
3647  * allocate storage record from the storage heap
3648  *
3649  *   size    int        input/output requested/allocated blob size
3650  *   io_addr ioAddr     output       blob addr
3651  *
3652  * returns: zero on success, error code (< 0) on failure, (> 0) no avail
3653  */
3654
3655 int Db::
3656 storeGet(int &size, ioAddr &io_addr)
3657 {
3658   freeStoreRecord look, find;
3659   look.size = size;  look.io_addr = 0;
3660   int status = freeStoreIndex->Locate(keyGE, &look,0, &find,0);
3661   if( status == errNotFound ) return 1;
3662   if_err( status );
3663   if_err( storeDelete(find.size,find.io_addr) );
3664   io_addr = find.io_addr;
3665   long sz = find.size - look.size;
3666   if( sz >= min_heap_allocation ) {
3667     /* put back extra */
3668     find.size = sz;  find.io_addr += look.size;
3669     if_err( storeInsert(find.size,find.io_addr) );
3670   }
3671   else
3672     look.size = find.size;
3673   size = look.size;
3674   return 0;
3675 }
3676
3677 /*** int Db::storeNew(int &size, ioAddr &io_addr)
3678  *
3679  * allocate storage by extending file
3680  *
3681  *   size    int        input/output requested/allocated blob size
3682  *   io_addr ioAddr     output       blob addr
3683  *
3684  * returns: zero on success, error code (< 0) on failure, (> 0) no avail