cinelerra-5.1/db/tdb.h

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