storageimpl.cs

Perst开源实时数据库

                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 long UsedSize
        { 
            get       
            { 
                return usedSize;
            }
        }

        public 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++)
                        {
                            int spaceNeeded = objBitSize - holeBitSize < pageBits 
                                ? objBitSize - holeBitSize : pageBits;
                            if (bitmapPageAvailableSpace[i] <= spaceNeeded) 
                            {
                                holeBitSize = 0;
                                offs = 0;
                                continue;
                            }
                            pg = getBitmapPage(i);
                            int startOffs = offs;   
                            while (offs < Page.pageSize) 
                            { 
                                if (pg.data[offs++] != 0) 
                                { 
                                    offs = (offs + inc - 1) & ~(inc-1);
                                    holeBitSize = 0;
                                } 
                                else if ((holeBitSize += 8) == objBitSize) 
                                { 
                                    pos = (((long)i*Page.pageSize + offs)*8 - holeBitSize) 
                                        << dbAllocationQuantumBits;
                                    if (wasReserved(pos, size)) 
                                    { 
                                        startOffs = offs = (offs+inc) & ~(inc-1);
                                        holeBitSize = 0;
                                        continue;
                                    }       
                                    reserveLocation(pos, size);
                                    currPBitmapPage = i;
                                    currPBitmapOffs = offs;
                                    extend(pos + size);
                                    if (oid != 0) 
                                    { 
                                        long prev = getPos(oid);
                                        uint marker = (uint)prev & dbFlagsMask;
                                        pool.copy(pos, prev - marker, size);
                                        setPos(oid, pos | marker | dbModifiedFlag);
                                    }
                                    pool.unfix(pg);
                                    pg = putBitmapPage(i);
                                    int holeBytes = holeBitSize >> 3;
                                    if (holeBytes > offs) 
                                    { 
                                        memset(pg, 0, 0xFF, offs);
                                        holeBytes -= offs;
                                        pool.unfix(pg);
                                        pg = putBitmapPage(--i);
                                        offs = Page.pageSize;
                                    }
                                    while (holeBytes > Page.pageSize) 
                                    { 
                                        memset(pg, 0, 0xFF, Page.pageSize);
                                        holeBytes -= Page.pageSize;
                                        bitmapPageAvailableSpace[i] = 0;
                                        pool.unfix(pg);
                                        pg = putBitmapPage(--i);
                                    }
                                    memset(pg, offs-holeBytes, 0xFF, holeBytes);
                                    commitLocation();
                                    pool.unfix(pg);
                                    return pos;
                                }
                            }
                            if (startOffs == 0 && holeBitSize == 0
                                && spaceNeeded < bitmapPageAvailableSpace[i]) 
                            { 
                                bitmapPageAvailableSpace[i] = spaceNeeded;
                            }
                            offs = 0;
                            pool.unfix(pg);
                        }
                    } 
                    else 
                    { 
                        for (i = firstPage; i < lastPage; i++)
                        {
                            int spaceNeeded = objBitSize - holeBitSize < pageBits 
                                ? objBitSize - holeBitSize : pageBits;
                            if (bitmapPageAvailableSpace[i] <= spaceNeeded) 
                            {
                                holeBitSize = 0;
                                offs = 0;
                                continue;
                            }
                            pg = getBitmapPage(i);
                            int startOffs = offs;
                            while (offs < Page.pageSize) 
                            { 
                                int mask = pg.data[offs] & 0xFF; 
                                if (holeBitSize + firstHoleSize[mask] >= objBitSize) 
                                { 
                                    pos = (((long)i*Page.pageSize + offs)*8 
                                        - holeBitSize) << dbAllocationQuantumBits;
                                    if (wasReserved(pos, size)) 
                                    {                       
                                        startOffs = offs += 1;
                                        holeBitSize = 0;
                                        continue;
                                    }       
                                    reserveLocation(pos, size);