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