context: namespace Perst.Impl    
  {
      using System;
      using System.Collections;
      using System.Reflection;
      using System.Threading;
      using System.Diagnostics;
      using System.Text;
      using Perst;
  	
      public class StorageImpl:Storage
      {
  #if COMPACT_NET_FRAMEWORK
          static StorageImpl() 
          {
              assemblies = new System.Collections.ArrayList();
          }
          public StorageImpl(Assembly callingAssembly) 
          {
              assemblies.Add(callingAssembly);
              assemblies.Add(Assembly.GetExecutingAssembly());
          }
  #endif
  
          public override IPersistent Root
          {
              get
              {
                  lock(this)
                  {
                      if (!opened)
                      {
                          throw new StorageError(StorageError.ErrorCode.STORAGE_NOT_OPENED);
                      }
                      int rootOid = header.root[1 - currIndex].rootObject;
                      return (rootOid == 0) ? null : lookupObject(rootOid, null);
                  }
              }
  			
              set
              {
                  lock(this)
                  {
                      if (!opened)
                      {
                          throw new StorageError(StorageError.ErrorCode.STORAGE_NOT_OPENED);
                      }
                      if (!value.IsPersistent())
                      {
                          storeObject0(value);
                      }
                      header.root[1 - currIndex].rootObject = value.Oid;
                      modified = true;
                  }
              }
  			
          }
   
          /// <summary> Initialial database index size - increasing it reduce number of inde reallocation but increase
          /// initial database size. Should be set before openning connection.
          /// </summary>
          const int dbDefaultInitIndexSize = 1024;
  		
          /// <summary> Initial capacity of object hash
          /// </summary>
          const int dbDefaultObjectCacheInitSize = 1319;
  		
          /// <summary> Database extension quantum. Memory is allocate by scanning bitmap. If there is no
          /// large enough hole, then database is extended by the value of dbDefaultExtensionQuantum 
          /// This parameter should not be smaller than dbFirstUserId
          /// </summary>
          static long dbDefaultExtensionQuantum = 1024 * 1024;
  
          const int dbDatabaseOffsetBits = 32; // up to 4 gigabyte
          const int dbLargeDatabaseOffsetBits = 40; // up to 1 terabyte
  		
          const int dbAllocationQuantumBits = 5;
          const int dbAllocationQuantum = 1 << dbAllocationQuantumBits;
          const int dbBitmapSegmentBits = Page.pageBits + 3 + dbAllocationQuantumBits;
          const int dbBitmapSegmentSize = 1 << dbBitmapSegmentBits;
          const int dbBitmapPages = 1 << (dbDatabaseOffsetBits - dbBitmapSegmentBits);
          const int dbLargeBitmapPages = 1 << (dbLargeDatabaseOffsetBits - dbBitmapSegmentBits);
          const int dbHandlesPerPageBits = Page.pageBits - 3;
          const int dbHandlesPerPage = 1 << dbHandlesPerPageBits;
          const int dbDirtyPageBitmapSize = 1 << (32 - Page.pageBits - 3);
  		
          const int dbInvalidId = 0;
          const int dbBitmapId = 1;
          const int dbFirstUserId = dbBitmapId + dbBitmapPages;
  		
          internal const int dbPageObjectFlag = 1;
          internal const int dbModifiedFlag = 2;
          internal const int dbFreeHandleFlag = 4;
          internal const int dbFlagsMask = 7;
          internal const int dbFlagsBits = 3;
  		
           
          int getBitmapPageId(int i) 
          { 
              return i < dbBitmapPages ? dbBitmapId + i : header.root[1-currIndex].bitmapExtent + i;
          }
  
          internal long getPos(int oid)
          {
              lock (objectCache) 
              {
                  if (oid == 0 || oid >= currIndexSize)
                  {
                      throw new StorageError(StorageError.ErrorCode.INVALID_OID);
                  }
                  Page pg = pool.getPage(header.root[1 - currIndex].index + (oid >> dbHandlesPerPageBits << Page.pageBits));
                  long pos = Bytes.unpack8(pg.data, (oid & (dbHandlesPerPage - 1)) << 3);
                  pool.unfix(pg);
                  return pos;
              }
          }
  		
          internal void  setPos(int oid, long pos)
          {
              lock (objectCache) 
              {
                  dirtyPagesMap[oid >> (dbHandlesPerPageBits + 5)] |= 1 << ((oid >> dbHandlesPerPageBits) & 31);
                  Page pg = pool.putPage(header.root[1 - currIndex].index + (oid >> dbHandlesPerPageBits << Page.pageBits));
                  Bytes.pack8(pg.data, (oid & (dbHandlesPerPage - 1)) << 3, pos);
                  pool.unfix(pg);
              }
          }
  		
          internal byte[] get(int oid)
          {
              long pos = getPos(oid);
              if ((pos & (dbFreeHandleFlag | dbPageObjectFlag)) != 0)
              {
                  throw new StorageError(StorageError.ErrorCode.INVALID_OID);
              }
              return pool.get(pos & ~ dbFlagsMask);
          }
  		
          internal Page getPage(int oid)
          {
              long pos = getPos(oid);
              if ((pos & (dbFreeHandleFlag | dbPageObjectFlag)) != dbPageObjectFlag)
              {
                  throw new StorageError(StorageError.ErrorCode.DELETED_OBJECT);
              }
              return pool.getPage(pos & ~ dbFlagsMask);
          }
  		
          internal Page putPage(int oid)
          {
              lock (objectCache) 
              {
                  long pos = getPos(oid);
                  if ((pos & (dbFreeHandleFlag | dbPageObjectFlag)) != dbPageObjectFlag)
                  {
                      throw new StorageError(StorageError.ErrorCode.DELETED_OBJECT);
                  }
                  if ((pos & dbModifiedFlag) == 0)
                  {
                      dirtyPagesMap[oid >> (dbHandlesPerPageBits + 5)] |= 1 << ((oid >> dbHandlesPerPageBits) & 31);
                      allocate(Page.pageSize, oid);
                      cloneBitmap(pos & ~ dbFlagsMask, Page.pageSize);
                      pos = getPos(oid);
                  }
                  modified = true;
                  return pool.putPage(pos & ~ dbFlagsMask);
              }
          }
  		
  		
          internal int allocatePage()
          {
              int oid = allocateId();
              setPos(oid, allocate(Page.pageSize, 0) | dbPageObjectFlag | dbModifiedFlag);
              return oid;
          }
  		
          protected internal override void  deallocateObject(IPersistent obj)
          {
              lock(this)
              {
                  lock (objectCache) 
                  { 
                      int oid = obj.Oid;
                      if (oid == 0) 
                      { 
                          return;
                      }       
                      long pos = getPos(oid);
                      objectCache.remove(oid);
                      int offs = (int) pos & (Page.pageSize - 1);
                      if ((offs & (dbFreeHandleFlag | dbPageObjectFlag)) != 0)
                      {
                          throw new StorageError(StorageError.ErrorCode.DELETED_OBJECT);
                      }
                      Page pg = pool.getPage(pos - offs);
                      offs &= ~ dbFlagsMask;
                      int size = ObjectHeader.getSize(pg.data, offs);
                      pool.unfix(pg);
                      freeId(oid);
                      if ((pos & dbModifiedFlag) != 0) 
                      {
                          free(pos & ~ dbFlagsMask, size);
                      }
                      else
                      {
                          cloneBitmap(pos, size);
                      }
                      obj.AssignOid(this, 0, false);
                  }
              }
          }
      		
          internal void  freePage(int oid)
          {
              long pos = getPos(oid);
              Debug.Assert((pos & (dbFreeHandleFlag | dbPageObjectFlag)) == dbPageObjectFlag);
              if ((pos & dbModifiedFlag) != 0)
              {
                  free(pos & ~ dbFlagsMask, Page.pageSize);
              }
              else
              {
                  cloneBitmap(pos & ~ dbFlagsMask, Page.pageSize);
              }
              freeId(oid);
          }
  		
   	
          internal void setDirty() 
          {
              modified = true;
              if (!header.dirty) 
              { 
                  header.dirty = true;
                  Page pg = pool.putPage(0);
                  header.pack(pg.data);
                  pool.flush();
                  pool.unfix(pg);
              }
          }
  
          internal int allocateId()
          {
              lock (objectCache) 
              {
                  int oid;
                  int curr = 1 - currIndex;
                  setDirty();
                  if ((oid = header.root[curr].freeList) != 0)
                  {
                      header.root[curr].freeList = (int) (getPos(oid) >> dbFlagsBits);
                      Debug.Assert(header.root[curr].freeList >= 0);
                      dirtyPagesMap[oid >> (dbHandlesPerPageBits + 5)] 
                          |= 1 << ((oid >> dbHandlesPerPageBits) & 31);
                      return oid;
                  }
  			
                  if (currIndexSize >= header.root[curr].indexSize)
                  {
                      int oldIndexSize = header.root[curr].indexSize;
                      int newIndexSize = oldIndexSize * 2;
                      if (newIndexSize < oldIndexSize) 
                      { 
                          newIndexSize = int.MaxValue & ~(dbHandlesPerPage-1);
                          if (newIndexSize <= oldIndexSize) 
                          { 
                              throw new StorageError(StorageError.ErrorCode.NOT_ENOUGH_SPACE);
                          }
                      }
                      long newIndex = allocate(newIndexSize*8L, 0);
                      if (currIndexSize >= header.root[curr].indexSize) 
                      {
                          long oldIndex = header.root[curr].index;
                          pool.copy(newIndex, oldIndex, currIndexSize*8L);
                          header.root[curr].index = newIndex;
                          header.root[curr].indexSize = newIndexSize;
                          free(oldIndex, oldIndexSize*8L);
                      } 
                      else 
                      { 
                          // index was already reallocated
                          free(newIndex, newIndexSize*8L);
                      }
                  }
                  oid = currIndexSize;
                  header.root[curr].indexUsed = ++currIndexSize;
                  modified = true;
                  return oid;
              }
          }
  		
          internal void  freeId(int oid)
          {
              lock (objectCache) 
              {
                  setPos(oid, ((long) (header.root[1 - currIndex].freeList) << dbFlagsBits) | dbFreeHandleFlag);
                  header.root[1 - currIndex].freeList = oid;
              }
          }
  		
          internal static byte[] firstHoleSize = new byte[]{8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
          internal static byte[] lastHoleSize = new byte[]{8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
          internal static byte[] maxHoleSize = new byte[]{8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 7, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0};
          internal static byte[] maxHoleOffset = new byte[]{0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 0, 1, 5, 5, 5, 5, 5, 5, 0, 5, 5, 5, 5, 5, 5, 5, 0, 1, 2, 2, 0, 3, 3, 3, 0, 1, 6, 6, 0, 6, 6, 6, 0, 1, 2, 2, 0, 6, 6, 6, 0, 1, 6, 6, 0, 6, 6, 6, 0, 1, 2, 2, 3, 3, 3, 3, 0, 1, 4, 4, 0, 4, 4, 4, 0, 1, 2, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 2, 2, 0, 3, 3, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 2, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 2, 2, 3, 3, 3, 3, 0, 4, 4, 4, 4, 4, 4, 4, 0, 1, 2, 2, 0, 5, 5, 5, 0, 1, 5, 5, 0, 5, 5, 5, 0, 1, 2, 2, 0, 3, 3, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 2, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 2, 2, 3, 3, 3, 3, 0, 1, 4, 4, 0, 4, 4, 4, 0, 1, 2, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 2, 2, 0, 3, 3, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 2, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 0};
  		
          internal const int pageBits = Page.pageSize * 8;
          internal const int inc = Page.pageSize / dbAllocationQuantum / 8;
  		
          internal static void  memset(Page pg, int offs, int pattern, int len)
          {
              byte[] arr = pg.data;
              byte pat = (byte) pattern;
              while (--len >= 0)
              {
                  arr[offs++] = pat;
              }
          }
  		
          public override long UsedSize
          { 
              get       
              { 
                  return usedSize;
              }
          }
  
          public override long DatabaseSize
          { 
              get 
              { 
                  return header.root[1-currIndex].size;
              }
          }
  
          internal void  extend(long size)
          {
              if (size > header.root[1 - currIndex].size)
              {
                  header.root[1 - currIndex].size = size;
              }
          }
  		
          internal class Location
          {
              internal long pos;
              internal long size;
              internal Location next;
          }
  		
          internal bool wasReserved(long pos, long size)
          {
              for (Location location = reservedChain; location != null; location = location.next)
              {
                  if ((pos >= location.pos && pos - location.pos < location.size) || (pos <= location.pos && location.pos - pos < size))
                  {
                      return true;
                  }
              }
              return false;
          }
  		
          internal void  reserveLocation(long pos, long size)
          {
              Location location = new Location();
              location.pos = pos;
              location.size = size;
              location.next = reservedChain;
              reservedChain = location;
          }
  		
          internal void  commitLocation()
          {
              reservedChain = reservedChain.next;
          }
  		
          Page putBitmapPage(int i) 
          { 
              return putPage(getBitmapPageId(i));
          }
  
          Page getBitmapPage(int i) 
          { 
              return getPage(getBitmapPageId(i));
          }
  
  		
          internal long allocate(long size, int oid)
          {
              lock (objectCache) 
              {
                  setDirty();
                  size = (size + dbAllocationQuantum - 1) & ~ (dbAllocationQuantum - 1);
                  Debug.Assert(size != 0);
                  allocatedDelta += size;
                  if (allocatedDelta > gcThreshold) 
                  {
                      gc0();
                  }
                  int objBitSize = (int)(size >> dbAllocationQuantumBits);
                  Debug.Assert(objBitSize == (size >> dbAllocationQuantumBits));
                  long pos;
                  int holeBitSize = 0;
                  int alignment = (int)size & (Page.pageSize - 1);
                  int offs, firstPage, lastPage, i, j;
                  int holeBeforeFreePage = 0;
                  int freeBitmapPage = 0;
                  int  curr = 1 - currIndex;
                  Page pg;
  			
                  lastPage = header.root[curr].bitmapEnd - dbBitmapId;
                  usedSize += size;
  			
                  if (alignment == 0)
                  {
                      firstPage = currPBitmapPage;
                      offs = (currPBitmapOffs + inc - 1) & ~ (inc - 1);
                  }
                  else
                  {
                      firstPage = currRBitmapPage;
                      offs = currRBitmapOffs;
                  }
  			
                  while (true)
                  {
                      if (alignment == 0) 
                      { 
                          // allocate page object 
                          for (i = firstPage; i < lastPage; i++)
                          {
  
gt:                             int spaceNeeded = objBitSize - holeBitSize < pageBits 