cinelerra-5.1/db/tdb.h

   1 #ifndef __DB_H__
   2 #define __DB_H__
   3 #include <cstring>
   4 #include <stdint.h>
   5 #include <malloc.h>
   6 #include <limits.h>
   7 #include <sys/types.h>
   8
   9 #define freeStoreIndex indecies[freeStoreIdx]
  10 #define addrStoreIndex indecies[addrStoreIdx]
  11 #define freeSpaceIndex indecies[freeSpaceIdx]
  12 #define addrSpaceIndex indecies[addrSpaceIdx]
  13 #define entityIdIndex indecies[entityIdIdx]
  14 #define entityNmIndex indecies[entityNmIdx]
  15
  16 #define noThrow std::nothrow
  17 #ifndef likely
  18 #define likely(x)   (__builtin_constant_p(x) ? !!(x) : __builtin_expect(!!(x), 1))
  19 #define unlikely(x) (__builtin_constant_p(x) ? !!(x) : __builtin_expect(!!(x), 0))
  20 #endif
  21 #ifndef lengthof
  22 #define lengthof(x) ((int)(sizeof(x)/sizeof(x[0])))
  23 #endif
  24
  25 #if 0
  26 inline void *operator new(size_t n) { void *vp = malloc(n); bzero(vp,n); return vp; }
  27 inline void operator delete(void *t) { free(t); }
  28 inline void operator delete(void *t,size_t n) { free(t); }
  29 inline void *operator new[](size_t n) { void *vp = malloc(n); bzero(vp,n); return vp; }
  30 inline void operator delete[](void *t) { free(t); }
  31 inline void operator delete[](void *t,size_t n) { free(t); }
  32 #endif
  33
  34 #define ZMEDIA
  35 #define ZFUTEX
  36 #ifdef ZFUTEX
  37 #include <unistd.h>
  38 #include <endian.h>
  39 #include <linux/futex.h>
  40 #include <sys/syscall.h>
  41 #else
  42 #include <pthread.h>
  43 #endif
  44
  45 #if 1
  46 //entity definitions
  47 #define DbObj(nm) \
  48   class nm##Obj : public Db::Obj { public:
  49
  50 #define DbLoc(nm) \
  51   class nm##Loc : public Db::ObjectLoc { public: \
  52     nm##Obj *operator ->() { return (nm##Obj *)addr(); } \
  53     nm##Loc(Db::Entity *ep) : Db::ObjectLoc(ep) {} \
  54     nm##Loc(Db::Entity &e) : Db::ObjectLoc(&e) {}
  55
  56 //basic definitions
  57 #define basic_def(ty,n) class t_##n { public: ty v; t_##n() {} \
  58  t_##n(const ty &i) : v(i) {} \
  59  t_##n(const t_##n &i) : v(i.v) {} \
  60  t_##n &operator =(const t_##n &i) { v = i.v; return *this; } \
  61  ty &operator =(const ty &i) { return v = i; } \
  62  ty *addr() { return &v; } int size() { return sizeof(v); } \
  63  } v_##n \
  64
  65 //array definitions
  66 #define array_def(ty,n,l) class t_##n { public: ty v[l]; t_##n() {} \
  67  t_##n(const t_##n &i) { memcpy(&v,&i.v,sizeof(v)); } \
  68  t_##n(ty *i) { memcpy(&v,i,sizeof(v)); } \
  69  t_##n(ty(*i)[l]) { memcpy(&v,i,sizeof(v)); } \
  70  ty *operator =(const ty *i) { memcpy(&v,i,sizeof(v)); return &v[0]; } \
  71  ty *addr() { return &v[0]; } int size() { return sizeof(v); } \
  72  } v_##n \
  73
  74 // variable array definitions
  75 #define varray_def(ty,n) \
  76  class t_##n { public: char *v; int l; t_##n() {} \
  77  t_##n(const char *i, int sz) { v = (char *)i; l = sz; } \
  78  t_##n(const unsigned char *i, int sz) { v = (char *)i; l = sz; } \
  79  ty *addr() { return (ty *)v; } int size() { return l; } \
  80  }; Db::varObj v_##n \
  81
  82 // string array definitions
  83 #define sarray_def(ty,n) \
  84  class t_##n { public: char *v; int l; t_##n() {} \
  85  t_##n(const char *i, int sz) { v = (char *)i; l = sz; } \
  86  t_##n(const unsigned char *i, int sz) { v = (char *)i; l = sz; } \
  87  t_##n(const char *i) { t_##n(i,strlen(i)+1); } \
  88  t_##n(const unsigned char *i) { t_##n(i,strlen(v)+1); } \
  89  ty *addr() { return (ty *)v; } int size() { return l; } \
  90  }; Db::varObj v_##n \
  91
  92 //basic type ref
  93 #define basic_ref(ty,n) \
  94  ty *_##n() { return (*this)->v_##n.addr(); } \
  95  ty n() { return *_##n(); } \
  96  void n(ty i) { _wr(); *_##n() = i; } \
  97  int size_##n() { return (*this)->v_##n.size(); } \
  98
  99 //array type ref
 100 #define array_ref(ty,n,l) \
 101  ty *_##n() { return (*this)->v_##n.addr(); } \
 102  ty (&n())[l] { return *(ty (*)[l])_##n(); } \
 103  void n(const ty *i,int m) { _wr(); if( m > 0 ) memcpy(n(),i,m); } \
 104  void n(const ty *i) { n(i,(*this)->v_##n.size()); } \
 105  int size_##n() { return (*this)->v_##n.size(); } \
 106
 107 //variable array type ref
 108 #define varray_ref(ty,n) \
 109  ty *_##n() { return (ty *)addr((*this)->v_##n); } \
 110  ty *_##n(int sz) { size((*this)->v_##n, sz); \
 111    return sz > 0 ? (ty *)addr_wr((*this)->v_##n) : 0; } \
 112  ty (&n())[] { return *(ty (*)[])_##n(); } \
 113  int n(const ty *v, int sz) { ty *vp=_##n(sz); \
 114   if( vp && sz > 0 ) memcpy(vp, v, sz); return 0; } \
 115  int size_##n() { return (*this)->v_##n.size(); } \
 116
 117 //string array type ref
 118 #define sarray_ref(ty,n) \
 119  ty *_##n() { return (ty *)addr((*this)->v_##n); } \
 120  ty *_##n(int sz) { size((*this)->v_##n, sz); \
 121    return sz > 0 ? (ty *)addr_wr((*this)->v_##n) : 0; } \
 122  ty (&n())[] { return *(ty (*)[])_##n(); } \
 123  int n(const ty *v, int sz) { ty *vp=_##n(sz); \
 124   if( vp && sz > 0 ) memcpy(vp, v, sz); return 0; } \
 125  int n(const char *v) { return n((ty *)v,strlen(v)+1); } \
 126  int n(const unsigned char *v) { return n((const char *)v); } \
 127  int size_##n() { return (*this)->v_##n.size(); } \
 128
 129 #endif
 130
 131 #define DEBUG
 132 #define DEBUG_TIMESTAMPS
 133 #define DBBUG_ERR   0x00000001
 134 #define DBBUG_FAIL  0x00000002
 135 #define CHK
 136 //#define CHK 1 ? 0 :
 137
 138 class Db;
 139
 140 class Db {
 141 public:
 142   typedef int pageId;
 143   typedef int transId;
 144   typedef long ioAddr;
 145
 146 private:
 147   int root_info_id;
 148   int index_info_id;
 149   int page_info_id;
 150
 151   class RootInfo {
 152   public:
 153     int root_magic;           // info_magic label
 154     int root_info_size;       // root_info blob size
 155     int last_info_size;
 156     int entity_max_id;
 157     int entity_count;
 158     ioAddr root_info_addr;
 159     ioAddr last_info_addr;
 160     transId transaction_id;   // current transaction
 161     ioAddr file_size;         // current file size
 162     pageId freePages;         // free page table page list
 163     int indeciesUsed;         // number of active indecies
 164     int pageTableUsed;        // number of active pages
 165
 166     int init();
 167   } *root_info;
 168
 169   int shm_init, no_shm;
 170
 171   static void *get_mem8_t(int id);
 172   static void *new_mem8_t(int size, int &id);
 173   static int del_mem8_t(const void *vp, int id);
 174   static void *get_shm8_t(int id);
 175   static void *new_shm8_t(int size, int &id);
 176   static int del_shm8_t(const void *vp, int id);
 177   void *(*get_mem)(int id);
 178   void *(*new_mem)(int size, int &id);
 179   int (*del_mem)(const void *vp, int id);
 180
 181 protected:
 182   uint8_t *get_uint8_t(int id, int pg=-1);
 183   uint8_t *new_uint8_t(int size, int &id, int pg=-1);
 184   int del_uint8_t(const void *vp, int id=-1, int pg=-1);
 185
 186 public:
 187   typedef int (*CmprFn)(char *,char *);
 188   static int cmprFrSt(char *a, char *b);
 189   static int cmprAdSt(char *a, char *b);
 190   static int cmprFrSp(char *a, char *b);
 191   static int cmprAdSp(char *a, char *b);
 192   static int cmprOIds(char *a, char *b);
 193   static int cmprStr(char *a, char *b);
 194   static int cmprKey(char *a, char *b);
 195   static int cmprLast(char *a, char *b);
 196   static CmprFn cmprFns[];
 197   typedef void (*errCallback)(Db *db, int v);
 198   static const pageId NIL=-1, DDONE=-2;
 199   enum {
 200     errNoCmprFn = 0,
 201     errNotFound = -1,
 202     errDuplicate = -2,
 203     errNoPage = -3,
 204     errNoMemory = -4,
 205     errIoRead = -5,
 206     errIoWrite = -6,
 207     errIoSeek = -7,
 208     errIoStat = -8,
 209     errBadMagic = -9,
 210     errCorrupt = -10,
 211     errInvalid = -11,
 212     errPrevious = -12,
 213     errObjEntity = -13,
 214     errLimit = -14,
 215     errUser = -15,
 216     idxId = 0, nmSz = 32,
 217     keysz = 256,
 218     keyLT=-2, keyLE=-1, keyEQ=0, keyGE=1, keyGT=2,
 219   };
 220
 221   class pgRef {
 222   public:
 223     pageId id;
 224     int offset;
 225   };
 226
 227   static void zincr(volatile int &v) { /* atomic(++v) */
 228     asm ( " lock incl %1\n" : "+m" (v) :: );
 229   }
 230   static void zdecr(volatile int &v) { /* atomic(--v) */
 231     asm ( " lock decl %1\n" : "+m" (v) :: );
 232   }
 233   static char tdecr(volatile int &v) {
 234     char ret; /* ret = atomic(--loc >= 0 ? 1 : 0) */
 235     asm ( " lock decl %1\n setge %0\n" : "=r" (ret), "+m" (v) :: );
 236     return ret;
 237   }
 238   static char tincr(volatile int &v) {
 239     char ret; /* ret = atomic(++loc > 0 ? 1 : 0) */
 240     asm ( " lock incl %1\n setg %0\n" : "=r" (ret), "+m" (v) :: );
 241     return ret;
 242   }
 243   static int zcmpxchg(int old, int val, volatile int &v) {
 244     int ret = old;
 245     asm volatile( " lock\n cmpxchgl %2,%1\n"
 246       : "+a" (ret), "+m" (v) :  "r" (val) : "memory" );
 247     return ret;
 248   }
 249   static int zxchg(int val, volatile int &v) {
 250     asm volatile( " xchgl %0,%1\n"
 251       : "+r" (val), "+m" (v) :: "memory" );
 252     return val;
 253   }
 254   static int zadd(int n, volatile int &v) {
 255     int old, mod, val;
 256     do { val = (old=v)+n; mod = zcmpxchg(old,val,v);
 257     } while( mod != old );
 258     return val;
 259   }
 260   static void zmfence() {
 261     asm volatile ( " mfence\n" ::: "memory" );
 262   }
 263
 264   class zlock_t;
 265   class zblock_t;
 266   class zrwlock_t;
 267
 268 #ifdef ZFUTEX
 269 #define ZLOCK_INIT zzlock_t()
 270   class zloc_t {
 271   protected:
 272     volatile int loc;
 273     int zfutex(int op, int val, timespec *time=0) {
 274       return syscall(SYS_futex,&loc,op,val,time,0,0);
 275     }
 276     int zyield();
 277     int zgettid();
 278   public:
 279     int zwake(int nwakeups);
 280     int zwait(int val, timespec *ts=0);
 281     int zwait() { return zwait(loc); }
 282     zloc_t() : loc(-1) {}
 283     ~zloc_t() {}
 284   };
 285
 286   class zlock_t : zloc_t {
 287     void *owner;
 288     void *self() {
 289 #ifdef __x86_64__
 290      void *vp; asm ("movq %%fs:%c1,%q0" : "=r" (vp) : "i" (16));
 291 #else
 292      void *vp; asm ("mov %%fs:%c1,%q0" : "=r" (vp) : "i" (16));
 293 #endif
 294      return vp;
 295    }
 296   protected:
 297     friend class zblock_t;
 298     friend class zrwlock_t;
 299     int zlock(int v);
 300     int zunlock(int nwakeups=1);
 301     static int zemsg1();
 302   public:
 303     int lock() {
 304       int v, ret = unlikely( (v=zcmpxchg(-1,0,loc)) >= 0 ) ? zlock(v) : 0;
 305       owner = self();
 306       return ret;
 307     }
 308     int unlock() {
 309       if( unlikely(loc < 0) ) { return zemsg1(); }
 310       owner = 0;
 311       int v, ret = unlikely( (v=zcmpxchg(0,-1,loc)) != 0 ) ? zunlock() : 0;
 312       return ret;
 313     }
 314     zlock_t() { owner = 0; }
 315     ~zlock_t() {}
 316   };
 317
 318   class zblock_t : zlock_t {
 319   public:
 320     void block() { loc = 0; zwait(0); }
 321     void unblock() { loc = -1; zwake(INT_MAX); }
 322     zblock_t() {}
 323     ~zblock_t() {}
 324   };
 325
 326   class zrwlock_t : zloc_t {
 327     zlock_t lk;
 328     void zenter();
 329     void zleave();
 330   public:
 331     void enter() { zincr(loc); if( unlikely( lk.loc >= 0 ) ) zenter(); }
 332     void leave() { if( unlikely( !tdecr(loc) ) ) zleave(); }
 333     void write_enter();
 334     void write_leave();
 335     int locked() { return loc >= 0 ? 0 : lk.loc >= 0 ? 1 : -1; }
 336     int blocked() { return lk.loc >= 0 ? 1 : 0; }
 337     zrwlock_t() {}
 338     ~zrwlock_t() {}
 339   };
 340
 341 #else
 342 #define ZLOCK_INIT { PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER }
 343
 344   class zlock_t {
 345   protected:
 346     pthread_mutex_t zlock;
 347   public:
 348     void lock() { pthread_mutex_lock(&zlock); }
 349     void unlock() { pthread_mutex_unlock(&zlock); }
 350     zlock_t() { pthread_mutex_init(&zlock, 0); }
 351     ~zlock_t() { pthread_mutex_destroy(&zlock); }
 352   };
 353
 354   class zblock_t {
 355     pthread_mutex_t zblock;
 356     pthread_cond_t cond;
 357   public:
 358     zblock_t() {
 359       pthread_mutex_init(&zblock, 0);
 360       pthread_cond_init(&cond, 0);
 361     }
 362     ~zblock_t() {
 363       pthread_mutex_destroy(&zblock);
 364       pthread_cond_destroy(&cond);
 365     }
 366     void block() {
 367       pthread_mutex_lock(&zblock);
 368       pthread_cond_wait(&cond, &zblock);
 369       pthread_mutex_unlock(&zblock);
 370     }
 371     void unblock() { pthread_cond_broadcast(&cond); }
 372   };
 373
 374   class zrwlock_t : zlock_t {
 375     volatile int blocking, users;
 376     zlock_t lk;
 377     pthread_cond_t cond;
 378     void wait() { pthread_cond_wait(&cond, &zlock); }
 379     void wake() { pthread_cond_signal(&cond); }
 380   public:
 381     void enter() { lock();
 382       while( blocking ) { unlock(); lk.lock(); lk.unlock(); lock(); }
 383       ++users;  unlock();
 384     }
 385     void leave() { lock();  if( !--users && blocking ) wake();  unlock(); }
 386     void write_enter() { lk.lock();  blocking = 1;
 387       lock(); while( users ) wait(); unlock();
 388     }
 389     void write_leave() { blocking = 0; lk.unlock(); }
 390     int count() { return users; }
 391     int locked() { return users ? 0 : blocking ? 1 : -1; }
 392     int blocked() { return blocking; }
 393
 394     zrwlock_t() { pthread_cond_init(&cond, 0); users = 0; blocking = 0; }
 395     ~zrwlock_t() { pthread_cond_destroy(&cond); }
 396   };
 397
 398 #endif
 399
 400   class locked {
 401     zlock_t &lk;
 402   public:
 403     locked(zlock_t &l) : lk(l) { lk.lock(); }
 404     ~locked() { lk.unlock(); }
 405   };
 406
 407   class read_locked {
 408     zrwlock_t &rwlk;
 409   public:
 410     read_locked(zrwlock_t &l) : rwlk(l) { rwlk.enter(); }
 411     ~read_locked() { rwlk.leave(); }
 412   };
 413
 414   class write_blocked {
 415     zrwlock_t &rwlk;
 416   public:
 417     write_blocked(zrwlock_t &l) : rwlk(l) { rwlk.write_enter(); }
 418     ~write_blocked() { rwlk.write_leave(); }
 419   };
 420
 421 private:
 422   enum {
 423     db_magic_offset=0,
 424     db_magic=0x00624474,   // tDb
 425     idx_magic=0x00786469,  // idx
 426     info_magic=0x6f666e69, // info
 427     root_magic=0x746f6f72, // root
 428     page_magic=0x6770,     // pg
 429     entity_magic = 0x6d65, // em
 430     root_info_offset=4,
 431     root_info_extra_pages = 2,
 432     idxNil=0, idxBin=1, idxStr=2,
 433     opDelete=-1, opFind=0, opInsert=1,
 434     pg_unknown=0, pg_root_info=1, pg_free=2,
 435     pg_entity=0x0100, pg_index=0x1000,
 436     max_entity_type = pg_index-pg_entity-1,
 437     max_index_type = 0x10000-pg_index-1,
 438     min_heap_allocation = 32,
 439     freeStoreIdx = 0, addrStoreIdx = 1,
 440     freeSpaceIdx = 2, addrSpaceIdx = 3,
 441     entityIdIdx = 4, entityNmIdx = 5, usrIdx = 6,
 442     fl_wr=1, fl_rd=2, fl_new=4, fl_free=8,
 443     defaultNoShm = 1,
 444     defaultStoreBlockSize = 8192,
 445     defaultPageTableHunkSize = 8192,
 446     defaultIndexTableHunkSize = 4096,
 447     defaultBinaryBlockSize = 16384,
 448     defaultStringBlockSize = 4096,
 449     defaultEntityPageSize = 65536,
 450   };
 451
 452   int key, fd;
 453   int err_no;
 454   errCallback err_callback;
 455   int my_pid;
 456   transId active_transaction;
 457
 458 #ifdef DEBUG
 459   static int debug;
 460   static const char *errMsgs[];
 461   static void dmsg(int msk, const char *msg,...);
 462   int _err_(int v,const char *fn,int ln);
 463   int _fail_(int v,const char *fn,int ln);
 464 #define err_(v) _err_(v,__func__,__LINE__)
 465 #define fail_(v) _fail_(v,__func__,__LINE__)
 466 #else
 467   static void dmsg(int msk, const char *msg,...) {}
 468   int _err_(int v) { error(v); return v; }
 469   int _fail_(int v) { return v; }
 470 #define err_(v) _err_(v)
 471 #define fail_(v) _fail_(v)
 472 #endif
 473
 474 #define Err(v) return err_(v)
 475 #define Fail(v) return fail_(v)
 476
 477 #define if_ret(fn) do{ int _ret; \
 478  if(unlikely((_ret=(fn))<0)) return _ret; \
 479 }while(0)
 480 #define if_err(fn) do{ int _ret; \
 481  if(unlikely((_ret=(fn))<0)) Err(_ret); \
 482 }while(0)
 483 #define if_fail(fn) do{ int _ret; \
 484  if(unlikely((_ret=(fn))<0)) Fail(_ret); \
 485 }while(0)
 486
 487   class DbInfo {
 488   public:
 489     int magic;
 490     int owner, last_owner;
 491     int info_key, info_id;
 492     int root_info_id;
 493     int index_info_id;
 494     int page_info_id;
 495     zlock_t infoLk;   // lock dbinfo up to here
 496     zrwlock_t dbRwLk; // global lock
 497     zrwlock_t pgTblLk;// pageTable realloc
 498     zlock_t pgAlLk;   // new page pagesUsed/pagesAllocated
 499     zlock_t pgLdLk;   // pageLoad
 500     zlock_t blkAlLk;  // blockAllocate/Free
 501     zlock_t objAlLk;  // objectAllocate/Free
 502     zrwlock_t rw_locks[max_entity_type];
 503
 504     DbInfo(int pid, int key, int id);
 505   } *db_info;
 506   int new_info(int key);
 507   int get_info(int key);
 508   int del_info();
 509
 510   int attach_wr();
 511   int attach_rd();
 512   int attach_rw(int zrw) { return zrw ? attach_wr() : attach_rd(); }
 513   void detach_rw();
 514
 515   class Page;
 516
 517   class pagePrefix {
 518   public:
 519     unsigned short magic;
 520     unsigned short type;
 521     int used;
 522   };
 523
 524   Page *get_Page(pageId pid) volatile { return pageTable[pid]; }
 525   void set_Page(pageId pid, Page *pp) { pageTable[pid] = pp; }
 526   //Page *get_page(pageId pid) { blocked by(pgTblk); return get_Page(pid); }
 527   Page *get_page(pageId pid); // locked pageTable access
 528
 529   static pageId getPageId(unsigned char *&bp) {
 530     int i = sizeof(pageId);  pageId id;
 531     for( id = *bp++; --i > 0; id |= *bp++ ) id <<= 8;
 532     return id;
 533   }
 534   static void putPageId(unsigned char *&bp, pageId id) {
 535     int i = sizeof(pageId) * 8;
 536     while( (i -= 8) >= 0 ) *bp++ = id >> i;
 537   }
 538   static pageId readPageId(char *cp) {
 539     unsigned char *bp = (unsigned char *)cp;
 540     return getPageId(bp);
 541   }
 542   static void writePageId(char *cp, pageId id) {
 543     unsigned char *bp = (unsigned char *)cp;
 544     putPageId(bp,id);
 545   }
 546
 547   class keyBlock : public pagePrefix {
 548     char rightLink[sizeof(pageId)];
 549   public:
 550     int right_link() { return readPageId(&rightLink[0]); }
 551     void right_link(pageId id) { writePageId(&rightLink[0],id); }
 552   };
 553
 554   static int defaultBlockSizes[];
 555
 556   class IndexTypeInfo {
 557   public:
 558     int magic;
 559     int type;                      /* type of index */
 560     char name[nmSz];               /* index string identifier */
 561   };
 562
 563   class IndexBaseType : public IndexTypeInfo {
 564   public:
 565     IndexBaseType(int typ);
 566   };
 567
 568   class IndexRecdInfo {
 569   public:
 570     int idx;                       /* index in db->indecies[] */
 571     int keySz, dataSz;             /* sizeof key/data fields in bytes */
 572     pageId rootPageId;             /* index root page ID */
 573     pageId rightHandSide;          /* the right hand side of the tree for this index */
 574     pageId freeBlocks;             /* free index page list */
 575     unsigned int blockSize;        /* size of new index blocks */
 576     int pad1;
 577     long count;                    /* index population count */
 578   };
 579
 580   class IndexBaseRecd : public IndexRecdInfo {
 581   public:
 582     IndexBaseRecd(int typ, int zidx, int ksz, int dsz);
 583   };
 584
 585   class IndexBaseStorage;
 586   class IndexBaseInfo : public IndexTypeInfo, public IndexRecdInfo {
 587   public:
 588     operator IndexBaseStorage *() { return (IndexBaseStorage *)this; }
 589   };
 590
 591   class IndexBaseStorage : public IndexBaseInfo {
 592   public:
 593     IndexBaseStorage(int typ, int zidx, int ksz, int dsz);
 594     IndexBaseStorage() {}
 595     ~IndexBaseStorage() {}
 596   };
 597
 598   class IndexBase {
 599     IndexBaseStorage *st;
 600     friend class Db;
 601     Db *db;                        /* owner db */
 602     zlock_t idxLk;
 603     pgRef lastAccess, lastFind;    /* last operational access/find location */
 604     pgRef lastInsert, lastDelete;  /* last operational insert/delete location */
 605     pgRef lastNext;                /* last operational next location */
 606     int kdSz;                      /* keySz + dataSz */
 607     int lastOp;                    /* last operation, delete=-1/find=0/insert=1 */
 608     int cInsCount;                 /* number of consecutive insertions */
 609     int cFindCount;                /* number of consecutive finds */
 610     int cDelCount;                 /* number of consecutive deletions */
 611
 612     void init(Db *zdb);
 613     virtual int keyMap(pageId s, int(IndexBase::*fn)(pageId id)) = 0;
 614     virtual int keyCopy(pageId s, IndexBase *ib) = 0;
 615     int blockAllocate(pageId &pid, keyBlock *&bp);
 616     int blockAllocate(pageId &pid, keyBlock *&bp, Page *&pp, char *&cp) {
 617       pp = 0;  cp = 0;  if_err( blockAllocate(pid, bp) );
 618       pp = db->get_page(pid);  cp = (char *)(bp + 1);
 619       return 0;
 620     }
 621     int blockFree(pageId pid);
 622     int blockRelease(pageId pid);
 623     int deleteFreeBlocks();
 624     void chkLastInsert();
 625     void chkLastDelete();
 626     void chkLastFind(pgRef &last);
 627   public:
 628 #ifdef DEBUG
 629     int _err_(int v,const char *fn,int ln) { return db->_err_(v,fn,ln); }
 630     int _fail_(int v,const char *fn,int ln) { return db->_fail_(v,fn,ln); }
 631 #else
 632     int _err_(int v) { return db->_err_(v); }
 633     int _fail_(int v) { return db->_fail_(v); }
 634 #endif
 635     virtual int Locate(int op,void *key,CmprFn cmpr,void *rtnKey,void *rtnData) = 0;
 636     virtual int Find(void *key,void *rtnData) = 0;
 637     virtual int Insert(void *key,void *data) = 0;
 638     virtual int Delete(void *key) = 0;
 639     virtual int First(void *rtnKey,void *rtnData) = 0;
 640     virtual int Last(void *rtnKey,void *rtnData) = 0;
 641     virtual int Modify(void *key,void *recd) = 0;
 642     virtual int Next(pgRef &loc,void *rtnKey,void *rtnData) = 0;
 643     int First(pgRef &loc,void *rtnKey,void *rtnData) {
 644       if_fail( First(rtnKey, rtnData) );
 645       loc = lastNext;
 646       return 0;
 647     }
 648     int Next(void *rtnKey,void *rtnData) {
 649       if( lastNext.id < 0 ) Fail(errInvalid);
 650       return Next(lastNext,rtnKey,rtnData);
 651     }
 652     long Count() { return st->count; }
 653     int MakeRoot();
 654     int UnmakeRoot();
 655     int Clear();
 656     int NextLoc(pgRef &loc) { loc = lastNext; return 0; }
 657     IndexBase(Db *zdb, int typ, int zidx, int ksz, int dsz);
 658     IndexBase(Db *zdb, IndexBaseStorage &d);
 659     virtual ~IndexBase();
 660   } **indecies;
 661
 662   int indeciesAllocated, indecies_sz;
 663
 664   class IndexBinaryStorage;
 665   class IndexBinaryInfo {
 666   public:
 667     operator IndexBinaryStorage *() { return (IndexBinaryStorage *)this; }
 668     int cmprId;
 669   };
 670
 671   class IndexBinaryStorage : public IndexBinaryInfo {
 672   public:
 673     IndexBinaryStorage(int cmprId) { this->cmprId = cmprId; }
 674     IndexBinaryStorage() {}
 675     ~IndexBinaryStorage() {}
 676   };
 677
 678   class IndexBinary : public IndexBase {
 679     IndexBinaryStorage *bst;
 680     friend class Db;
 681     CmprFn compare;                /* the key compare function type */
 682     char *akey;                    /* pointer to key argument */
 683     int keyInterior;               /* last insert interior/exterior */
 684     int idf;                       /* interior delete flag */
 685     char *iky, *tky;               /* search/promoted temp key storage */
 686
 687     void init();
 688     int keyMap(pageId s, int(IndexBase::*fn)(pageId id));
 689     int keyCopy(pageId s, IndexBase *ib);
 690     int keyBlockUnderflow(int &t,keyBlock *lbb,pageId p,keyBlock *pbb,int pi);
 691     void makeKey(char *cp,char *key,int l,char *recd,int n);
 692     void setLastKey(pageId s,pageId u,int k);
 693     int keyLocate(pgRef &last,pageId s, int op,void *ky, CmprFn cmpr);
 694     int chkNext(pgRef &loc, char *&kp);
 695     int keyNext(pgRef &loc, char *kp);
 696     int chkFind(pgRef &loc, char *key);
 697     int keyFind(pgRef &loc,void *ky, pageId s);
 698     int chkInsert(void *key,void *data);
 699     int keyInsert(pageId s, pageId &t);
 700     int chkDelete(pgRef &loc, void *kp);
 701     int keyDelete(int &t,void *kp,pageId s,pageId p,keyBlock *pbb,int pi);
 702     int keyFirst(pgRef &loc, pageId s);
 703     int keyLast(pgRef &loc, pageId s);
 704
 705     int refLocate(pgRef &loc, int op,void *key, CmprFn cmpr);
 706     int Locate(int op,void *key,CmprFn cmpr,void *rtnKey,void *rtnData);
 707     int refFind(pgRef &loc, void *key);
 708     int Find(void *key,void *rtnData);
 709     int Insert(void *key,void *data);
 710     int Delete(void *key);
 711     int First(void *rtnKey,void *rtnData);
 712     int Last(void *rtnKey,void *rtnData);
 713     int Modify(void *key,void *recd);
 714     int Next(pgRef &loc,void *rtnKey,void *rtnData);
 715     int Next(void *rtnKey,void *rtnData) {
 716       return IndexBase::Next(rtnKey,rtnData);
 717     }
 718
 719     char *ikey() { return iky; }
 720     char *tkey() { return tky; }
 721   public:
 722     IndexBinary(Db *zdb, int zidx, int ksz, int dsz, CmprFn cmpr);
 723     IndexBinary(Db *zdb, IndexBaseStorage *b, IndexBinaryStorage *d);
 724     IndexBinary(IndexBase *ib, IndexBaseStorage *b, IndexBinaryStorage *d);
 725     ~IndexBinary();
 726   };
 727   friend class IndexBinary;
 728
 729   class IndexStringStorage;
 730   class IndexStringInfo {
 731     char dummy; // compiler needs this for some reason
 732   public:
 733     operator IndexStringStorage *() { return (IndexStringStorage *)this; }
 734   };
 735
 736   class IndexStringStorage : public IndexStringInfo {
 737   public:
 738     IndexStringStorage() {}
 739     ~IndexStringStorage() {}
 740   };
 741
 742   class IndexString : public IndexBase {
 743     IndexStringStorage *sst;
 744     friend class Db;
 745     static int ustrcmp(unsigned char *a, unsigned char *b) {
 746       return strncmp((char *)a,(char *)b,keysz);
 747     }
 748     static void ustrcpy(unsigned char *a, unsigned char *b) {
 749       strncpy((char *)a,(char *)b,keysz);
 750     }
 751     static void umemmove(unsigned char *&a, unsigned char *b, int n) {
 752       memmove(a,b,n);  a += n;
 753     }
 754     static int kpress(unsigned char *kp, unsigned char *lp, unsigned char *cp);
 755     int split(int n, int i, pageId s, pageId &l, pageId r);
 756     void init();
 757     int keyMap(pageId s, int(IndexBase::*fn)(pageId id));
 758     int keyCopy(pageId s, IndexBase *ib);
 759     int chkInsert(void *key,void *data);
 760     int keyInsert(pageId &t, pageId s);
 761     int keyFirst(pageId s);
 762     int keyLast(pageId s);
 763     int keyLocate(pgRef &last,pageId s,int &t, int op,
 764         unsigned char *ky,CmprFn cmpr, unsigned char *rky);
 765     int chkFind(pgRef &loc, char *key, unsigned char *lkey, unsigned char *lky=0);
 766     int keyFind(pgRef &loc, unsigned char *ky);
 767     int keyNext(pgRef &loc, unsigned char *rky);
 768     int keyUnderflow(pageId s, pageId &t, int k);
 769     int keyOverflow(pageId s, pageId &t, int k, int o);
 770     int keyRemap(pageId s, pageId &t, int k, int o);
 771     int keyDelete(pageId s, pageId &t);
 772
 773     unsigned char lastAccKey[keysz], lastFndKey[keysz];
 774     unsigned char lastInsKey[keysz], lastDelKey[keysz];
 775     unsigned char lastNxtKey[keysz];
 776     unsigned char *tky, *dky;   // dataSz+keysz+1
 777     unsigned char *tbfr;        // 3*allocated
 778     unsigned char akey[keysz];  // key in use
 779     int idf;                    /* interior delete flag */
 780
 781     int refLocate(pgRef &loc, int op, void *key, CmprFn cmpr, unsigned char *rkey);
 782     int Locate(int op,void *key,CmprFn cmpr,void *rtnKey,void *rtnData);
 783     int refFind(pgRef &loc, void *key);
 784     int Find(void *key,void *rtnData);
 785     int Insert(void *key,void *data);
 786     int Delete(void *key);
 787     int First(void *rtnKey,void *rtnData);
 788     int Last(void *rtnKey,void *rtnData);
 789     int Modify(void *key,void *recd);
 790     int Next(pgRef &loc,void *rtnKey,void *rtnData);
 791     int Next(void *rtnKey,void *rtnData) {
 792       return IndexBase::Next(rtnKey,rtnData);
 793     }
 794
 795   public:
 796     IndexString(Db *zdb, int zidx, int dsz);
 797     IndexString(Db *zdb, IndexBaseStorage *b, IndexStringStorage *d);
 798     IndexString(IndexBase *ib, IndexBaseStorage *b, IndexStringStorage *d);
 799     ~IndexString();
 800   };
 801   friend class IndexString;
 802
 803   class IndexBinaryData : public IndexBaseInfo, public IndexBinaryInfo {};
 804   class IndexStringData : public IndexBaseInfo, public IndexStringInfo {};
 805
 806   typedef union {
 807     IndexBaseInfo base;
 808     IndexBinaryData bin;
 809     IndexStringData str;
 810   } IndexInfo;
 811   IndexInfo *index_info;        /* image for index storage */
 812
 813   class allocPrefix {
 814   public:
 815     unsigned short magic;
 816     unsigned short type;
 817     int size;
 818   };
 819
 820   class freeStoreRecord {
 821   public:
 822     long size;
 823     ioAddr io_addr;
 824   };
 825
 826   class addrStoreRecord {
 827   public:
 828     ioAddr io_addr;
 829     long size;
 830   };
 831
 832   class freeSpaceRecord {
 833   public:
 834     long size;
 835     pageId id;
 836     int offset;
 837   };
 838
 839   class addrSpaceRecord {
 840   public:
 841     pageId id;
 842     int offset;
 843     long size;
 844   };
 845
 846   class AllocCache {
 847     pgRef loc;
 848     int avail;
 849   public:
 850     int cacheFlush(Db *db);
 851     int Get(Db *db,int &size, pgRef &ref);
 852     int Load(Db *db, pageId id, int ofs, int sz);
 853     void init() { loc.id = NIL; loc.offset = 0; avail = 0; }
 854     void init(pageId id, int ofs, int sz) {
 855       loc.id = id; loc.offset = ofs; avail = sz;
 856     }
 857     void dmp() {
 858       printf("loc: %d/%d  avl: %d\n", loc.id,loc.offset,avail);
 859     }
 860   } alloc_cache;
 861   int cacheFlush() {
 862     return alloc_cache.cacheFlush(this);
 863   }
 864   int cache_all_flush();
 865
 866   class PageStorage {
 867   public:
 868     unsigned int used;
 869     unsigned int allocated;
 870     unsigned short flags;
 871     unsigned short type;
 872     int io_allocated;
 873     int wr_allocated;
 874     int shmid;
 875     pageId link;
 876     transId trans_id;
 877     ioAddr io_addr;
 878     ioAddr wr_io_addr;
 879
 880     void init();
 881     PageStorage() { init(); }
 882     ~PageStorage() {}
 883     int chk_flags(int fl) { return flags & fl; }
 884     int set_flags(int fl) { return flags |= fl; }
 885     int clr_flags(int fl) { return flags &= ~fl; }
 886   } *page_info;
 887
 888   class Page {
 889     zlock_t pgLk;
 890     PageStorage *st;
 891     pagePrefix *addr;
 892     int shm_id;
 893     void init();
 894   public:
 895     // PageStorage access
 896     int iused() { return st->used-sizeof(keyBlock); }
 897     void iused(int v) { st->used = v+sizeof(keyBlock); }
 898     int iallocated() { return st->allocated-sizeof(keyBlock); }
 899     void iallocated(int v) { st->allocated = v+sizeof(keyBlock); }
 900     PageStorage *operator ->() { return st; }
 901     int release();
 902     void reset_to(Page *pp);
 903     Page(PageStorage &d) { st = &d; init(); }
 904     ~Page() {}
 905     friend class Db;
 906   } **pageTable;
 907   int pageTableAllocated, page_table_sz;
 908
 909   int entityPageSize;
 910   int storeBlockSize;
 911   int pageTableHunkSize;
 912   int indexTableHunkSize;
 913
 914   class undoData {
 915   public:
 916     class cfnData {
 917       public:
 918       int cmprId;
 919       CmprFn compare;
 920     } *cfn;
 921     int cfnAllocated, cfnUsed;
 922     undoData() : cfn(0), cfnAllocated(0), cfnUsed(0) {}
 923     ~undoData() { delete [] cfn; cfnAllocated = cfnUsed = 0; }
 924     int save(Db *db);
 925     int restore(Db *db);
 926   } undata;
 927
 928   ioAddr file_position;
 929
 930   char *bfr, *lmt, *inp;
 931   int open_bfr();
 932   int close_bfr();
 933   int flush_bfr();
 934   int write_bfr(char *dp, int sz);
 935
 936 public:
 937 #ifdef ZMEDIA
 938
 939   // count of on bits
 940   inline static unsigned int on_bits(unsigned int n) {
 941     n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
 942     n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
 943     n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
 944     n += n >> 8;  n += n >> 16;  //ok, fldsz > 5 bits
 945     return n & 0x1f;
 946   }
 947
 948   // lowest on bit
 949   inline static unsigned int low_bit(unsigned int n) {
 950     return n & ~(n-1);
 951   }
 952
 953   // bit number of lowest on bit
 954   inline static unsigned int low_bit_no(unsigned int n) {
 955     return on_bits(low_bit(n) - 1);
 956   }
 957
 958   // highest on bit, and all lower bits set
 959   inline static unsigned int high_bit_mask(unsigned int n) {
 960     n |= n >> 1;   n |= n >> 2;
 961     n |= n >> 4;   n |= n >> 8;
 962     n |= n >> 16;
 963     return n;
 964   }
 965
 966   // highest on bit
 967   inline static unsigned int high_bit(unsigned int n) {
 968     unsigned m = high_bit_mask(n);
 969     return m & ~(m>>1);
 970   }
 971
 972   // bit number of highest on bit
 973   inline static unsigned int high_bit_no(unsigned int n) {
 974     return on_bits(high_bit_mask(n)) - 1;
 975   }
 976
 977   class pack {
 978     static inline int cpu_aligned() {
 979       unsigned long flags;
 980       asm volatile( "pushf\n" "pop %0\n" : "=rm" (flags) );
 981       return (flags>>18) & 1;
 982     }
 983     static int aligned;
 984     int idx;
 985     uint8_t *bits;
 986     uint64_t vmx;
 987     uint64_t clip(int64_t v) { return v<0 ? 0 : (uint64_t)v>vmx ? vmx : v; }
 988   public:
 989     enum { alignBits = 8, };
 990
 991     static void init(int v=-1) { aligned = v >= 0 ? v : cpu_aligned(); }
 992     void put(uint64_t v, int n);
 993     void putc(uint64_t v, int n) { put(clip(v), n); }
 994     void iput(int v) { put(v, 8*sizeof(int)); }
 995     void lput(int64_t v) { put(v, 8*sizeof(int64_t)); }
 996     uint64_t get(int n);
 997     int iget() { return get(8*sizeof(int)); }
 998     int64_t lget() { return get(8*sizeof(int64_t)); }
 999     int pos() { return idx; }
1000     void seek(int i) { idx = i; }
1001     void init(uint8_t *bp) { bits = bp; idx = 0; vmx = 0; }
1002     uint8_t *bfr() { return this->bits; }
1003     void align() { idx = (idx+alignBits-1) & ~(alignBits-1); }
1004     void *addr() { return &bits[idx/8]; }
1005     void set_max(uint64_t v) { vmx = v; }
1006
1007     pack() : bits(0) { idx = 0; }
1008     pack(uint8_t *bp) { init(bp); }
1009     ~pack() {}
1010   };
1011
1012   class mediaKey {
1013     int w, len;
1014     int64_t cnt;
1015     uint8_t *bp;
1016
1017   public:
1018     static int64_t bit_size(int len, int w);
1019     static int64_t byte_size(int len, int w);
1020     static void build(uint8_t *kp, uint8_t *bp, int w, int len) {
1021       mediaKey key(kp, bp, w, len);
1022     }
1023     static int64_t count(void *kp) {
1024       mediaKey *mkp = (mediaKey *)kp;
1025       return be64toh(mkp->cnt);
1026     }
1027     static int64_t set_count(void *kp, int64_t v) {
1028       mediaKey *mkp = (mediaKey *)kp;
1029       return mkp->cnt = htobe64(v);
1030     }
1031     static int64_t incr_count(void *kp, int64_t dv) {
1032       return set_count(kp, count(kp) + dv);
1033     }
1034     static int64_t count1(uint8_t *kp);
1035     mediaKey(uint8_t *kp, uint8_t *bp, int w, int len);
1036     ~mediaKey();
1037   };
1038
1039   class mediaLoad {
1040     pack pb, pk;
1041     int w, len, dsz, psz, spos;
1042     int64_t cnt, *dat, **dp;
1043     void get_fields(int n, int k);
1044     int dsize(int n) { int m = (n+1)/2; return m>1 ? m+dsize(m) : 1; }
1045
1046   public:
1047     void load(uint8_t *kp);
1048
1049     mediaLoad(uint8_t *bp);
1050     ~mediaLoad();
1051   };
1052
1053   class mediaCmpr {
1054     pack pb, pk;
1055     int w, len, dsz, psz, spos;
1056     int64_t acnt, bcnt, *adat, *bdat, **adp, **bdp;
1057     uint64_t err, lmt;
1058     uint64_t sqr(int64_t v) { return v*v; }
1059     int dsize(int n) { int m = (n+1)/2; return m>1 ? m+dsize(m) : 1; }
1060     uint64_t chk_fields(int m, int k);
1061     int cmpr_fields(int m, int k);
1062
1063   public:
1064     uint64_t chk(uint8_t *kp, uint64_t lmt=~0);
1065     int cmpr(uint8_t *kp, uint64_t lmt=~0);
1066
1067     mediaCmpr(uint8_t *bp);
1068     ~mediaCmpr();
1069   };
1070 #endif
1071
1072   class Entity;
1073   class ObjectLoc;
1074   typedef IndexBase *Index;
1075   int new_entity(Entity &entity, const char *nm, int sz);
1076   int get_entity(Entity &entity, const char *nm);
1077   int del_entity(Entity &entity);
1078
1079   class Obj {                    /* per object storage base class */
1080   public:
1081     int id;
1082   };
1083
1084   class varObj {
1085   public:
1086     int len;  pgRef loc;
1087     int size() { return len; }
1088     void init() { len = -1;  loc.id = NIL;  loc.offset = 0; }
1089     void del(Entity *entity) { len = -1;  entity->deallocate(loc); }
1090   };
1091   typedef varObj Obj::*vRef;
1092
1093   class ObjectLoc {
1094   public:
1095     Entity *entity;
1096     pgRef obj;
1097     Obj *addr(pgRef &loc) {
1098       char *op = 0;
1099       return loc.id < 0 || entity->db->addrRead(loc,op) ? 0 : (Obj *)op;
1100     }
1101     Obj *addr_wr(pgRef &loc) {
1102       char *op = 0;
1103       return loc.id < 0 || entity->db->addrWrite(loc,op) ? 0 : (Obj *)op;
1104     }
1105     void _wr() { Page &pg = *entity->db->get_page(obj.id); pg->set_flags(fl_wr); }
1106     Obj *addr() { return addr(obj); }
1107     Obj *addr_wr() { return addr_wr(obj); }
1108     void *addr(varObj &vobj) { return addr(vobj.loc); }
1109     void *addr_wr(varObj &vobj) { return addr_wr(vobj.loc); }
1110     Obj *operator ->() { return (Obj *)addr(); }
1111     ObjectLoc(Entity *ep) : entity(ep) { obj.id = NIL;  obj.offset = 0; }
1112     ~ObjectLoc() {}
1113
1114     virtual int allocate(int sz=0) { return entity->allocate(*this,sz); }
1115     virtual int construct() { return entity->construct(*this); }
1116     virtual int destruct() { return entity->destruct(*this); }
1117     virtual int deallocate() { return entity->deallocate(*this); }
1118     virtual int insertCascade() { return 0; }
1119     virtual int insertProhibit() { return 0; }
1120     virtual int deleteCascade() { return 0; }
1121     virtual int deleteProhibit() { return 0; }
1122     virtual int modifyCascade() { return 0; }
1123     virtual int modifyProhibit() { return 0; }
1124     virtual int copy(ObjectLoc &dobj);
1125     int id() { ObjectLoc &oloc = *this; return oloc->id; }
1126     const int *_id() { ObjectLoc &oloc = *this; return &oloc->id; }
1127     int _id_size() { return sizeof(int); }
1128     int size(varObj &vobj) { return vobj.len; }
1129     int size(varObj &vobj, int sz);
1130     Index index(int i) { return entity->index(i); }
1131     void v_init();
1132     void v_del();
1133
1134     int FindId(int id) { return index(idxId)->Find(&id,&obj); }
1135     int LocateId(int op, int id) { return index(idxId)->Locate(op,&id,0,0,&obj); }
1136     int FirstId() { return index(idxId)->First(0,&obj); }
1137     int LastId() { return index(idxId)->Last(0,&obj); }
1138     int NextId() { return index(idxId)->Next(0,&obj); }
1139     int FirstId(pgRef &loc) { return index(idxId)->First(loc,0,&obj); }
1140     int NextId(pgRef &loc) { return index(idxId)->Next(loc,0,&obj); }
1141     int NextLocId(pgRef &loc) { return index(idxId)->NextLoc(loc); }
1142
1143     static int cmpr_char(const char *ap, int asz, const char *bp, int bsz);
1144     static int cmpr_uchar(const unsigned char *ap, int asz, const unsigned char *bp, int bsz);
1145     static int cmpr_short(const short *ap, int asz, const short *bp, int bsz);
1146     static int cmpr_ushort(const unsigned short *ap, int asz, const unsigned short *bp, int bsz);
1147     static int cmpr_int(const int *ap, int asz, const int *bp, int bsz);
1148     static int cmpr_uint(const unsigned int *ap, int asz, const unsigned int *bp, int bsz);
1149     static int cmpr_long(const long *ap, int asz, const long *bp, int bsz);
1150     static int cmpr_ulong(const unsigned long *ap, int asz, const unsigned long *bp, int bsz);
1151     static int cmpr_float(const float *ap, int asz, const float *bp, int bsz);
1152     static int cmpr_double(const double *ap, int asz, const double *bp, int bsz);
1153 #ifdef ZMEDIA
1154     static int cmpr_media(const unsigned char *ap, int asz, const unsigned char *bp, int bsz);
1155 #endif
1156
1157 #ifdef DEBUG
1158     int _err_(int v,const char *fn,int ln) { return entity->db->_err_(v,fn,ln); }
1159     int _fail_(int v,const char *fn,int ln) { return entity->db->_fail_(v,fn,ln); }
1160 #else
1161     int _err_(int v) { return entity->db->_err_(v); }
1162     int _fail_(int v) { return entity->db->_fail_(v); }
1163 #endif
1164
1165     int last(int idx,int (ObjectLoc::*ip)());
1166     int last(const char *nm,int (ObjectLoc::*ip)());
1167     unsigned int last(int idx,unsigned int (ObjectLoc::*ip)());
1168     unsigned int last(const char *nm,unsigned int (ObjectLoc::*ip)());
1169   };
1170
1171   class Key {
1172   public:
1173     ObjectLoc &loc;
1174     Index idx;
1175     CmprFn cmpr;
1176     Key(Index i, ObjectLoc &l, CmprFn c) : loc(l), idx(i), cmpr(c) {}
1177     Key(const char *nm, ObjectLoc &l, CmprFn c) : loc(l), cmpr(c) {
1178       idx = loc.entity->index(nm);
1179     }
1180     operator void *() { return (void *)this; }
1181 #ifdef DEBUG
1182     int _err_(int v,const char *fn,int ln) { return loc._err_(v,fn,ln); }
1183     int _fail_(int v,const char *fn,int ln) { return loc._fail_(v,fn,ln); }
1184 #else
1185     int _err_(int v) { return loc._err_(v); }
1186     int _fail_(int v) { return loc._fail_(v); }
1187 #endif
1188   };
1189
1190   class iKey : public Key {
1191   public:
1192     iKey(Index i, ObjectLoc &l, CmprFn c) : Key(i,l,c) {}
1193     iKey(const char *nm, ObjectLoc &l, CmprFn c) : Key(nm,l,c) {}
1194     int NextLoc(pgRef &pos) { return idx->NextLoc(pos); }
1195     int Find();
1196     int Locate(int op=keyGE);
1197   };
1198
1199   class rKey : public Key {
1200   public:
1201     rKey(Index i, ObjectLoc &l, CmprFn c) : Key(i,l,c) {}
1202     rKey(const char *nm, ObjectLoc &l, CmprFn c) : Key(nm,l,c) {}
1203     int NextLoc(pgRef &pos) { return idx->NextLoc(pos); }
1204     int First();  int First(pgRef &pos);
1205     int Next();   int Next(pgRef &pos);
1206     int Last();
1207     int Locate(int op=keyGE);
1208   };
1209
1210 private:
1211   class EntityObj : public Obj { /* entity storage */
1212   public:
1213     char name[nmSz];             /* string identifier */
1214     AllocCache alloc_cache;      /* entity allocator cache */
1215     int maxId;                   /* highest ID value */
1216     int recdSz;                  /* record size in bytes */
1217     int count;                   /* number of records */
1218     int nidxs;                   /* index count */
1219     int indexs[1];               /* id/loc index */
1220     EntityObj(EntityObj &eobj, int eid);
1221   };
1222
1223   class EntityLoc : public ObjectLoc {
1224   public:
1225     EntityObj *operator ->() { return (EntityObj *)addr(); }
1226     EntityLoc(Entity *ep) : ObjectLoc(ep) {}
1227     ~EntityLoc() {}
1228     int cacheFlush() {
1229       EntityLoc &eloc = *this;  _wr();
1230       return eloc->alloc_cache.cacheFlush(entity->db);
1231     }
1232   };
1233
1234   class varObjRef;
1235   typedef varObjRef *varObjs;
1236   class varObjRef {
1237   public:
1238     varObjs next;
1239     vRef ref;
1240     varObjRef(varObjs &lp, vRef rp) : next(lp), ref(rp) {}
1241   };
1242
1243   static int ioCmpr(const void *a, const void *b, void *c);
1244 public:
1245
1246   class Entity {
1247   public:
1248     Db *const db;
1249     EntityLoc ent;
1250     varObjs vobjs;
1251     zrwlock_t *rw_lock;
1252     operator zrwlock_t&() { return *rw_lock; }
1253
1254 #ifdef DEBUG
1255     int _err_(int v,const char *fn,int ln) { return db->_err_(v,fn,ln); }
1256     int _fail_(int v,const char *fn,int ln) { return db->_fail_(v,fn,ln); }
1257 #else
1258     int _err_(int v) { return db->_err_(v); }
1259     int _fail_(int v) { return db->_fail_(v); }
1260 #endif
1261     Entity(Db *const db) : db(db), ent(this), vobjs(0) {}
1262     ~Entity() {}
1263
1264     int allocate(ObjectLoc &loc,int sz=0);
1265     int construct_(ObjectLoc &loc, int id);
1266     int construct(ObjectLoc &loc) { return construct_(loc,ent->maxId); }
1267     int destruct_(ObjectLoc &loc, int id);
1268     int destruct(ObjectLoc &loc) { return destruct_(loc, loc->id); }
1269     int deallocate(pgRef &obj) { return db->deallocate(obj,ent->alloc_cache); }
1270     int deallocate(ObjectLoc &loc) { return deallocate(loc.obj); }
1271     int get_index(const char *nm, CmprFn cmpr=0);
1272     int key_index(const char *nm) { return get_index(nm,Db::cmprKey); }
1273     Index index(int i) { return db->indecies[ent->indexs[i]]; }
1274     Index index(const char *nm) {
1275       int idx = get_index(nm);
1276       return idx >= 0 ? index(idx) : 0;
1277     }
1278     int MaxId() { return ent->maxId; }
1279     int Count() { return ent->count; }
1280     int add_index(int idx);
1281     int add_bindex(const char *nm,int keySz,int dataSz) {
1282       int idx = db->new_binary_index(nm,keySz,dataSz);
1283       if_err( idx );  if_err( add_index(idx) );
1284       return 0;
1285     }
1286     int add_kindex(const char *nm) { return add_bindex(nm,0,sizeof(int)); }
1287     int add_sindex(const char *nm,int dataSz) {
1288       int idx = db->new_string_index(nm,dataSz);
1289       if_err( idx );  if_err( add_index(idx) );
1290       return 0;
1291     }
1292     int del_index_(int idx);
1293     int del_index(int idx);
1294     int del_index(const char *nm);
1295     int new_entity(const char *nm, int sz) { return db->new_entity(*this,nm,sz); }
1296     int get_entity(const char *nm) { return db->get_entity(*this,nm); }
1297     int del_entity() { return db->del_entity(*this); }
1298     void add_vref(vRef rp) { vobjs = new varObjRef(vobjs,rp); }
1299   };
1300
1301   class ObjectList;
1302   typedef ObjectList *Objects;
1303   static void finit(Objects objects);
1304
1305   class ObjectList {
1306   public:
1307     Objects next;
1308     ObjectLoc *obj;
1309     ObjectList(Objects op, ObjectLoc &o) : next(op), obj(&o) {}
1310   };
1311
1312 private:
1313   int new_entity_(Entity &entity, const char *nm, int sz);
1314
1315   int findCmprFn(CmprFn fn);
1316   int pageLoad(pageId id, Page &pg);
1317   int addrRead_(pgRef &loc, char *&vp, int mpsz=0) {
1318     Page &pg = *get_page(loc.id);  vp = 0;
1319     if( unlikely( !pg.addr || pg->chk_flags(fl_rd) ) ) {
1320       if_err( pageLoad(loc.id, pg) );
1321     }
1322     vp = (char *)pg.addr+loc.offset+mpsz;
1323     return 0;
1324   }
1325   int addrRead_(pgRef &loc, keyBlock *&vp, int mpsz=0) {
1326     return addrRead_(loc,*(char**)&vp, mpsz);
1327   }
1328   int addrRead_(pgRef &loc, allocPrefix *&vp, int mpsz=0) {
1329     return addrRead_(loc,*(char**)&vp, mpsz);
1330   }
1331   int addrRead_(pgRef &loc, pagePrefix *&vp, int mpsz=0) {
1332     return addrRead_(loc,*(char**)&vp, mpsz);
1333   }
1334   int addrWrite_(pgRef &loc, char *&vp, int mpsz=0) {
1335     Page &pg = *get_page(loc.id);  vp = 0;
1336     if( unlikely( !pg.addr || pg->chk_flags(fl_rd) ) ) {
1337       if_err( pageLoad(loc.id, pg) );
1338     }
1339     pg->set_flags(fl_wr);
1340     vp = (char *)pg.addr+loc.offset+mpsz;
1341     return 0;
1342   }
1343   int addrWrite_(pgRef &loc, keyBlock *&vp, int mpsz=0) {
1344     return addrWrite_(loc,*(char**)&vp, mpsz);
1345   }
1346   int addrWrite_(pgRef &loc, allocPrefix *&vp, int mpsz=0) {
1347     return addrWrite_(loc,*(char**)&vp, mpsz);
1348   }
1349   int addrWrite_(pgRef &loc, pagePrefix *&vp, int mpsz=0) {
1350     return addrWrite_(loc,*(char**)&vp, mpsz);
1351   }
1352   int addrRead(pgRef &loc, char *&vp) {
1353     return addrRead_(loc, vp, sizeof(allocPrefix));
1354   }
1355   int addrWrite(pgRef &loc, char *&vp) {
1356     return addrWrite_(loc, vp, sizeof(allocPrefix));
1357   }
1358
1359   int objectHeapInsert(int sz,int pg,int off);
1360   int objectHeapDelete(int sz,int pg,int off);
1361   int objectAllocate(int typ, int &size, pgRef &loc,AllocCache &cache);
1362   int objectFree(pgRef &loc);
1363   int pgRefGet(int &size, pgRef &loc,AllocCache &cache);
1364   int pgRefNew(int &size, pgRef &lo,AllocCache &cache);
1365   int pgRefAllocate(int &size, pgRef &lo,AllocCache &cache);
1366
1367   int storeInsert(long size, ioAddr io_addr);
1368   int storeDelete(long size, ioAddr io_addr);
1369   int storeGet(int &size, ioAddr &io_addr);
1370   int storeNew(int &size, ioAddr &io_addr);
1371   int storeAllocate(int &size, ioAddr &io_addr);
1372   int storeFree(int size, ioAddr io_addr);
1373
1374   int icommit(int force);
1375   int iundo();
1376   int iclose();
1377   int ireopen();
1378   int iattach();
1379   int iopen(int undo_save=1);
1380
1381 protected:
1382
1383   pageId new_page();
1384   void del_page(int id);
1385   int alloc_pageTable(int sz);
1386   void free_page_(int pid);
1387   void free_page(int pid) { locked by(db_info->pgAlLk); free_page_(pid); }
1388   pageId lower_page(int mid);
1389   int alloc_indecies(int n);
1390   int new_index();
1391   void del_index(int idx);
1392   int new_index(IndexBase *&ibp, IndexBaseInfo *b, IndexBinaryInfo *d);
1393   int new_index(IndexBase *&ibp, IndexBaseInfo *b, IndexStringInfo *d);
1394   int indexRead(pageId pid, int df, keyBlock *&bp) {
1395     pgRef pg;  pg.id = pid;  pg.offset = 0;
1396     return !df ? addrRead_(pg,*(char**)&bp) : addrWrite_(pg,*(char**)&bp);
1397   }
1398   int indexRead(pageId pid,int df,keyBlock *&bp, Page *&pp, char *&cp) {
1399     pp = 0;  cp = 0;  if_err( indexRead(pid, df, bp) );
1400     pp = get_page(pid);  cp = (char *)(bp + 1);
1401     return 0;
1402   }
1403   void pageDealloc(Page &pg, int mode=1);
1404   int pageRead(ioAddr io_adr, uint8_t *bp, int len);
1405   int pageWrite(Page &pg);
1406   int seek_data(ioAddr io_addr);
1407   int size_data(char *dp, int sz);
1408   int read_data(char *dp, int sz);
1409   int write_data(char *dp, int sz);
1410   int write_zeros(ioAddr io_addr);
1411   int write_padding(ioAddr io_addr);
1412   int readRootInfo(int(Db::*fn)(char *dp,int sz));
1413   int writeRootInfo(int(Db::*fn)(char *dp,int sz));
1414   ioAddr storeBlocks(ioAddr sz) { return (sz+storeBlockSize-1)/storeBlockSize; }
1415   ioAddr entityPages(ioAddr sz) { return (sz+entityPageSize-1)/entityPageSize; }
1416   int indeciesHunks(int sz) { return (sz+indexTableHunkSize-1)/indexTableHunkSize; }
1417   int pageTableHunks(int sz) { return (sz+pageTableHunkSize-1)/pageTableHunkSize; }
1418   int pagePrefixHunks(int sz) { return (sz+sizeof(pagePrefix)-1)/sizeof(pagePrefix); }
1419   int init_idx();
1420   void init_shm();
1421   void init();
1422   void deinit();
1423   void reset();
1424   int start_transaction(int undo_save=1);
1425   void enter() { db_info->dbRwLk.enter(); }
1426   void leave() { db_info->dbRwLk.leave(); }
1427   void write_enter() { db_info->dbRwLk.write_enter(); }
1428   void write_leave() { db_info->dbRwLk.write_leave(); }
1429
1430 public:
1431   // 1:wr, 0:rd, -1:unlocked
1432   int is_locked() { return db_info->dbRwLk.locked(); }
1433   int is_blocked() { return db_info->dbRwLk.blocked(); }
1434
1435   int make(int zfd);
1436   int open(int zfd, int zkey=-1);
1437   int close();
1438
1439   int attach(int zrw, int zfd, int zkey);
1440   int attach(int zrw=0) { return attach(fd, key, zrw); }
1441   int detach();
1442
1443   int copy(Db *db, Objects objs);
1444   int new_binary_index(const char *nm, int ksz, int dsz, CmprFn cmpr=0);
1445   int new_string_index(const char *nm, int dsz);
1446   int get_index(const char *nm, CmprFn cmpr=0);
1447   long get_count(int r);
1448   int ins   (int r, void *key, void *data);
1449   int del   (int r, void *key);
1450   int find  (int r, void *key, void *rtnData=0);
1451   int locate(int r, int op, void *key, CmprFn cmpr, void *rtnKey, void *rtnData=0);
1452   int locate(int r, int op, void *key, void *rtnKey, void *rtnData=0) {
1453     return locate(r,op,key,0,rtnKey,rtnData);
1454   }
1455   int first (int r, void *key, void *rtnData=0);
1456   int last  (int r, void *key, void *rtnData=0);
1457   int next  (int r, void *key, void *rtnData=0);
1458   int nextloc(int r, pgRef &loc);
1459   int allocate(int typ, int size, pgRef &loc, AllocCache &cache);
1460   int reallocate(int size, pgRef &loc, AllocCache &cache);
1461   int deallocate(pgRef &loc, AllocCache &cache);
1462   int commit(int force=0);
1463   int flush ();
1464   int undo  ();
1465
1466   int transaction() { return !root_info ? -1 : root_info->transaction_id; }
1467   int64_t filesize() { return !root_info ? -1 : root_info->file_size; }
1468   int opened() { return fd>=0 ? 1 : 0; }
1469   void use_shm(int v) { no_shm = v ? 0 : 1; }
1470   int error() { return err_no; }
1471   void error(int v);
1472   void Error(int v,const char *msg);
1473   int load();
1474
1475   Db();
1476   ~Db();
1477
1478 #ifdef DEBUG
1479   void dmp();
1480   void tdmp();
1481   void pdmp();
1482   void fdmp();
1483   void admp(); void achk(); void fchk();
1484   void edmp();
1485   void bdmp();
1486   void stats(int chk=1);
1487 #endif
1488
1489 };
1490
1491 #endif