You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ag...@apache.org on 2017/06/11 20:04:10 UTC

[44/47] ignite git commit: IGNITE-5267 - Moved ignite-ps module to ignite-core

http://git-wip-us.apache.org/repos/asf/ignite/blob/6bf5ce46/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java
deleted file mode 100644
index fadd685..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java
+++ /dev/null
@@ -1,594 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.ignite.internal.processors.cache.database.freelist;
-
-import java.util.concurrent.atomic.AtomicReferenceArray;
-import org.apache.ignite.IgniteCheckedException;
-import org.apache.ignite.IgniteLogger;
-import org.apache.ignite.internal.pagemem.PageIdAllocator;
-import org.apache.ignite.internal.pagemem.PageIdUtils;
-import org.apache.ignite.internal.pagemem.PageUtils;
-import org.apache.ignite.internal.pagemem.wal.IgniteWriteAheadLogManager;
-import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageInsertFragmentRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageInsertRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageRemoveRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageUpdateRecord;
-import org.apache.ignite.internal.processors.cache.database.CacheDataRow;
-import org.apache.ignite.internal.processors.cache.database.MemoryMetricsImpl;
-import org.apache.ignite.internal.processors.cache.database.MemoryPolicy;
-import org.apache.ignite.internal.processors.cache.database.evict.PageEvictionTracker;
-import org.apache.ignite.internal.processors.cache.database.tree.io.CacheVersionIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.DataPageIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.DataPagePayload;
-import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO;
-import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseBag;
-import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseList;
-import org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler;
-import org.apache.ignite.internal.util.typedef.internal.U;
-
-/**
- */
-public class FreeListImpl extends PagesList implements FreeList, ReuseList {
-    /** */
-    private static final int BUCKETS = 256; // Must be power of 2.
-
-    /** */
-    private static final int REUSE_BUCKET = BUCKETS - 1;
-
-    /** */
-    private static final Integer COMPLETE = Integer.MAX_VALUE;
-
-    /** */
-    private static final Integer FAIL_I = Integer.MIN_VALUE;
-
-    /** */
-    private static final Long FAIL_L = Long.MAX_VALUE;
-
-    /** */
-    private static final int MIN_PAGE_FREE_SPACE = 8;
-
-    /** */
-    private final int shift;
-
-    /** */
-    private final AtomicReferenceArray<Stripe[]> buckets = new AtomicReferenceArray<>(BUCKETS);
-
-    /** */
-    private final int MIN_SIZE_FOR_DATA_PAGE;
-
-    /** */
-    private final int emptyDataPagesBucket;
-
-    /** */
-    private final PageHandler<CacheDataRow, Boolean> updateRow = new UpdateRowHandler();
-
-    /** */
-    private final MemoryMetricsImpl memMetrics;
-
-    /** */
-    private final PageEvictionTracker evictionTracker;
-
-    /**
-     *
-     */
-    private final class UpdateRowHandler extends PageHandler<CacheDataRow, Boolean> {
-        @Override public Boolean run(
-            int cacheId,
-            long pageId,
-            long page,
-            long pageAddr,
-            PageIO iox,
-            Boolean walPlc,
-            CacheDataRow row,
-            int itemId)
-            throws IgniteCheckedException {
-            DataPageIO io = (DataPageIO)iox;
-
-            int rowSize = getRowSize(row);
-
-            boolean updated = io.updateRow(pageAddr, itemId, pageSize(), null, row, rowSize);
-
-            evictionTracker.touchPage(pageId);
-
-            if (updated && needWalDeltaRecord(pageId, page, walPlc)) {
-                // TODO This record must contain only a reference to a logical WAL record with the actual data.
-                byte[] payload = new byte[rowSize];
-
-                DataPagePayload data = io.readPayload(pageAddr, itemId, pageSize());
-
-                assert data.payloadSize() == rowSize;
-
-                PageUtils.getBytes(pageAddr, data.offset(), payload, 0, rowSize);
-
-                wal.log(new DataPageUpdateRecord(
-                    cacheId,
-                    pageId,
-                    itemId,
-                    payload));
-            }
-
-            return updated;
-        }
-    }
-
-    /** */
-    private final PageHandler<CacheDataRow, Integer> writeRow = new WriteRowHandler();
-
-    /**
-     *
-     */
-    private final class WriteRowHandler extends PageHandler<CacheDataRow, Integer> {
-        @Override public Integer run(
-            int cacheId,
-            long pageId,
-            long page,
-            long pageAddr,
-            PageIO iox,
-            Boolean walPlc,
-            CacheDataRow row,
-            int written)
-            throws IgniteCheckedException {
-            DataPageIO io = (DataPageIO)iox;
-
-            int rowSize = getRowSize(row);
-            int oldFreeSpace = io.getFreeSpace(pageAddr);
-
-            assert oldFreeSpace > 0 : oldFreeSpace;
-
-            // If the full row does not fit into this page write only a fragment.
-            written = (written == 0 && oldFreeSpace >= rowSize) ? addRow(pageId, page, pageAddr, io, row, rowSize):
-                addRowFragment(pageId, page, pageAddr, io, row, written, rowSize);
-
-            // Reread free space after update.
-            int newFreeSpace = io.getFreeSpace(pageAddr);
-
-            if (newFreeSpace > MIN_PAGE_FREE_SPACE) {
-                int bucket = bucket(newFreeSpace, false);
-
-                put(null, pageId, page, pageAddr, bucket);
-            }
-
-            if (written == rowSize)
-                evictionTracker.touchPage(pageId);
-
-            // Avoid boxing with garbage generation for usual case.
-            return written == rowSize ? COMPLETE : written;
-        }
-
-        /**
-         * @param pageId Page ID.
-         * @param page Page pointer.
-         * @param pageAddr Page address.
-         * @param io IO.
-         * @param row Row.
-         * @param rowSize Row size.
-         * @return Written size which is always equal to row size here.
-         * @throws IgniteCheckedException If failed.
-         */
-        private int addRow(
-            long pageId,
-            long page,
-            long pageAddr,
-            DataPageIO io,
-            CacheDataRow row,
-            int rowSize
-        ) throws IgniteCheckedException {
-            io.addRow(pageAddr, row, rowSize, pageSize());
-
-            if (needWalDeltaRecord(pageId, page, null)) {
-                // TODO This record must contain only a reference to a logical WAL record with the actual data.
-                byte[] payload = new byte[rowSize];
-
-                DataPagePayload data = io.readPayload(pageAddr, PageIdUtils.itemId(row.link()), pageSize());
-
-                assert data.payloadSize() == rowSize;
-
-                PageUtils.getBytes(pageAddr, data.offset(), payload, 0, rowSize);
-
-                wal.log(new DataPageInsertRecord(
-                    cacheId,
-                    pageId,
-                    payload));
-            }
-
-            return rowSize;
-        }
-
-        /**
-         * @param pageId Page ID.
-         * @param page Page pointer.
-         * @param pageAddr Page address.
-         * @param io IO.
-         * @param row Row.
-         * @param written Written size.
-         * @param rowSize Row size.
-         * @return Updated written size.
-         * @throws IgniteCheckedException If failed.
-         */
-        private int addRowFragment(
-            long pageId,
-            long page,
-            long pageAddr,
-            DataPageIO io,
-            CacheDataRow row,
-            int written,
-            int rowSize
-        ) throws IgniteCheckedException {
-            // Read last link before the fragment write, because it will be updated there.
-            long lastLink = row.link();
-
-            int payloadSize = io.addRowFragment(pageMem, pageAddr, row, written, rowSize, pageSize());
-
-            assert payloadSize > 0 : payloadSize;
-
-            if (needWalDeltaRecord(pageId, page, null)) {
-                // TODO This record must contain only a reference to a logical WAL record with the actual data.
-                byte[] payload = new byte[payloadSize];
-
-                DataPagePayload data = io.readPayload(pageAddr, PageIdUtils.itemId(row.link()), pageSize());
-
-                PageUtils.getBytes(pageAddr, data.offset(), payload, 0, payloadSize);
-
-                wal.log(new DataPageInsertFragmentRecord(cacheId, pageId, payload, lastLink));
-            }
-
-            return written + payloadSize;
-        }
-    }
-
-
-    /** */
-    private final PageHandler<Void, Long> rmvRow = new RemoveRowHandler();
-
-    /**
-     *
-     */
-    private final class RemoveRowHandler extends PageHandler<Void, Long> {
-        @Override public Long run(
-            int cacheId,
-            long pageId,
-            long page,
-            long pageAddr,
-            PageIO iox,
-            Boolean walPlc,
-            Void ignored,
-            int itemId)
-            throws IgniteCheckedException {
-            DataPageIO io = (DataPageIO)iox;
-
-            int oldFreeSpace = io.getFreeSpace(pageAddr);
-
-            assert oldFreeSpace >= 0: oldFreeSpace;
-
-            long nextLink = io.removeRow(pageAddr, itemId, pageSize());
-
-            if (needWalDeltaRecord(pageId, page, walPlc))
-                wal.log(new DataPageRemoveRecord(cacheId, pageId, itemId));
-
-            int newFreeSpace = io.getFreeSpace(pageAddr);
-
-            if (newFreeSpace > MIN_PAGE_FREE_SPACE) {
-                int newBucket = bucket(newFreeSpace, false);
-
-                if (oldFreeSpace > MIN_PAGE_FREE_SPACE) {
-                    int oldBucket = bucket(oldFreeSpace, false);
-
-                    if (oldBucket != newBucket) {
-                        // It is possible that page was concurrently taken for put, in this case put will handle bucket change.
-                        if (removeDataPage(pageId, page, pageAddr, io, oldBucket))
-                            put(null, pageId, page, pageAddr, newBucket);
-                    }
-                }
-                else
-                    put(null, pageId, page, pageAddr, newBucket);
-
-                if (io.isEmpty(pageAddr))
-                    evictionTracker.forgetPage(pageId);
-            }
-
-            // For common case boxed 0L will be cached inside of Long, so no garbage will be produced.
-            return nextLink;
-        }
-    }
-
-    /**
-     * @param cacheId Cache ID.
-     * @param name Name (for debug purpose).
-     * @param memMetrics Memory metrics.
-     * @param memPlc Memory policy.
-     * @param reuseList Reuse list or {@code null} if this free list will be a reuse list for itself.
-     * @param wal Write ahead log manager.
-     * @param metaPageId Metadata page ID.
-     * @param initNew {@code True} if new metadata should be initialized.
-     * @throws IgniteCheckedException If failed.
-     */
-    public FreeListImpl(
-        int cacheId,
-        String name,
-        MemoryMetricsImpl memMetrics,
-        MemoryPolicy memPlc,
-        ReuseList reuseList,
-        IgniteWriteAheadLogManager wal,
-        long metaPageId,
-        boolean initNew) throws IgniteCheckedException {
-        super(cacheId, name, memPlc.pageMemory(), BUCKETS, wal, metaPageId);
-        this.evictionTracker = memPlc.evictionTracker();
-        this.reuseList = reuseList == null ? this : reuseList;
-        int pageSize = pageMem.pageSize();
-
-        assert U.isPow2(pageSize) : "Page size must be a power of 2: " + pageSize;
-        assert U.isPow2(BUCKETS);
-        assert BUCKETS <= pageSize : pageSize;
-
-        // TODO this constant is used because currently we cannot reuse data pages as index pages
-        // TODO and vice-versa. It should be removed when data storage format is finalized.
-        MIN_SIZE_FOR_DATA_PAGE = pageSize - DataPageIO.MIN_DATA_PAGE_OVERHEAD;
-
-        int shift = 0;
-
-        while (pageSize > BUCKETS) {
-            shift++;
-            pageSize >>>= 1;
-        }
-
-        this.shift = shift;
-
-        this.memMetrics = memMetrics;
-
-        emptyDataPagesBucket = bucket(MIN_SIZE_FOR_DATA_PAGE, false);
-
-        init(metaPageId, initNew);
-    }
-
-    /**
-     * Calculates average fill factor over FreeListImpl instance.
-     */
-    public float fillFactor() {
-        long pageSize = pageSize();
-
-        long totalSize = 0;
-        long loadSize = 0;
-
-        for (int b = BUCKETS - 2; b > 0; b--) {
-            long bsize = pageSize - ((REUSE_BUCKET - b) << shift);
-
-            long pages = bucketsSize[b].longValue();
-
-            loadSize += pages * (pageSize - bsize);
-
-            totalSize += pages * pageSize;
-        }
-
-        return totalSize == 0 ? -1L : ((float) loadSize / totalSize);
-    }
-
-    /** {@inheritDoc} */
-    @Override public void dumpStatistics(IgniteLogger log) {
-        long dataPages = 0;
-
-        final boolean dumpBucketsInfo = false;
-
-        for (int b = 0; b < BUCKETS; b++) {
-            long size = bucketsSize[b].longValue();
-
-            if (!isReuseBucket(b))
-                dataPages += size;
-
-            if (dumpBucketsInfo) {
-                Stripe[] stripes = getBucket(b);
-
-                boolean empty = true;
-
-                if (stripes != null) {
-                    for (Stripe stripe : stripes) {
-                        if (!stripe.empty) {
-                            empty = false;
-
-                            break;
-                        }
-                    }
-                }
-
-                log.info("Bucket [b=" + b +
-                    ", size=" + size +
-                    ", stripes=" + (stripes != null ? stripes.length : 0) +
-                    ", stripesEmpty=" + empty + ']');
-            }
-        }
-
-        if (dataPages > 0) {
-            log.info("FreeList [name=" + name +
-                ", buckets=" + BUCKETS +
-                ", dataPages=" + dataPages +
-                ", reusePages=" + bucketsSize[REUSE_BUCKET].longValue() + "]");
-        }
-    }
-
-    /**
-     * @param freeSpace Page free space.
-     * @param allowReuse {@code True} if it is allowed to get reuse bucket.
-     * @return Bucket.
-     */
-    private int bucket(int freeSpace, boolean allowReuse) {
-        assert freeSpace > 0 : freeSpace;
-
-        int bucket = freeSpace >>> shift;
-
-        assert bucket >= 0 && bucket < BUCKETS : bucket;
-
-        if (!allowReuse && isReuseBucket(bucket))
-            bucket--;
-
-        return bucket;
-    }
-
-    /**
-     * @param part Partition.
-     * @return Page ID.
-     * @throws IgniteCheckedException If failed.
-     */
-    private long allocateDataPage(int part) throws IgniteCheckedException {
-        assert part <= PageIdAllocator.MAX_PARTITION_ID;
-        assert part != PageIdAllocator.INDEX_PARTITION;
-
-        return pageMem.allocatePage(cacheId, part, PageIdAllocator.FLAG_DATA);
-    }
-
-    /** {@inheritDoc} */
-    @Override public void insertDataRow(CacheDataRow row) throws IgniteCheckedException {
-        int rowSize = getRowSize(row);
-
-        int written = 0;
-
-        do {
-            if (written != 0)
-                memMetrics.incrementLargeEntriesPages();
-
-            int freeSpace = Math.min(MIN_SIZE_FOR_DATA_PAGE, rowSize - written);
-
-            long pageId = 0L;
-
-            if (freeSpace == MIN_SIZE_FOR_DATA_PAGE)
-                pageId = takeEmptyPage(emptyDataPagesBucket, DataPageIO.VERSIONS);
-
-            boolean reuseBucket = false;
-
-            // TODO: properly handle reuse bucket.
-            if (pageId == 0L) {
-                for (int b = bucket(freeSpace, false) + 1; b < BUCKETS - 1; b++) {
-                    pageId = takeEmptyPage(b, DataPageIO.VERSIONS);
-
-                    if (pageId != 0L) {
-                        reuseBucket = isReuseBucket(b);
-
-                        break;
-                    }
-                }
-            }
-
-            boolean allocated = pageId == 0L;
-
-            if (allocated)
-                pageId = allocateDataPage(row.partition());
-
-            DataPageIO init = reuseBucket || allocated ? DataPageIO.VERSIONS.latest() : null;
-
-            written = write(pageId, writeRow, init, row, written, FAIL_I);
-
-            assert written != FAIL_I; // We can't fail here.
-        }
-        while (written != COMPLETE);
-    }
-
-    /** {@inheritDoc} */
-    @Override public boolean updateDataRow(long link, CacheDataRow row) throws IgniteCheckedException {
-        assert link != 0;
-
-        long pageId = PageIdUtils.pageId(link);
-        int itemId = PageIdUtils.itemId(link);
-
-        Boolean updated = write(pageId, updateRow, row, itemId, null);
-
-        assert updated != null; // Can't fail here.
-
-        return updated;
-    }
-
-    /** {@inheritDoc} */
-    @Override public void removeDataRowByLink(long link) throws IgniteCheckedException {
-        assert link != 0;
-
-        long pageId = PageIdUtils.pageId(link);
-        int itemId = PageIdUtils.itemId(link);
-
-        long nextLink = write(pageId, rmvRow, itemId, FAIL_L);
-
-        assert nextLink != FAIL_L; // Can't fail here.
-
-        while (nextLink != 0L) {
-            memMetrics.decrementLargeEntriesPages();
-
-            itemId = PageIdUtils.itemId(nextLink);
-            pageId = PageIdUtils.pageId(nextLink);
-
-            nextLink = write(pageId, rmvRow, itemId, FAIL_L);
-
-            assert nextLink != FAIL_L; // Can't fail here.
-        }
-    }
-
-    /** {@inheritDoc} */
-    @Override protected Stripe[] getBucket(int bucket) {
-        return buckets.get(bucket);
-    }
-
-    /** {@inheritDoc} */
-    @Override protected boolean casBucket(int bucket, Stripe[] exp, Stripe[] upd) {
-        return buckets.compareAndSet(bucket, exp, upd);
-    }
-
-    /** {@inheritDoc} */
-    @Override protected boolean isReuseBucket(int bucket) {
-        return bucket == REUSE_BUCKET;
-    }
-
-    /**
-     * @return Number of empty data pages in free list.
-     */
-    public int emptyDataPages() {
-        return bucketsSize[emptyDataPagesBucket].intValue();
-    }
-
-    /** {@inheritDoc} */
-    @Override public void addForRecycle(ReuseBag bag) throws IgniteCheckedException {
-        assert reuseList == this: "not allowed to be a reuse list";
-
-        put(bag, 0, 0, 0L, REUSE_BUCKET);
-    }
-
-    /** {@inheritDoc} */
-    @Override public long takeRecycledPage() throws IgniteCheckedException {
-        assert reuseList == this: "not allowed to be a reuse list";
-
-        return takeEmptyPage(REUSE_BUCKET, null);
-    }
-
-    /** {@inheritDoc} */
-    @Override public long recycledPagesCount() throws IgniteCheckedException {
-        assert reuseList == this: "not allowed to be a reuse list";
-
-        return storedPagesCount(REUSE_BUCKET);
-    }
-
-    /**
-     * @param row Row.
-     * @return Entry size on page.
-     * @throws IgniteCheckedException If failed.
-     */
-    private static int getRowSize(CacheDataRow row) throws IgniteCheckedException {
-        int keyLen = row.key().valueBytesLength(null);
-        int valLen = row.value().valueBytesLength(null);
-
-        return keyLen + valLen + CacheVersionIO.size(row.version(), false) + 8 + (row.cacheId() == 0 ? 0 : 4);
-    }
-
-    /** {@inheritDoc} */
-    @Override public String toString() {
-        return "FreeList [name=" + name + ']';
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/6bf5ce46/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/PagesList.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/PagesList.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/PagesList.java
deleted file mode 100644
index a8f3037..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/PagesList.java
+++ /dev/null
@@ -1,1484 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.ignite.internal.processors.cache.database.freelist;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-import java.util.concurrent.atomic.AtomicLong;
-import org.apache.ignite.IgniteCheckedException;
-import org.apache.ignite.IgniteSystemProperties;
-import org.apache.ignite.internal.pagemem.PageIdUtils;
-import org.apache.ignite.internal.pagemem.PageMemory;
-import org.apache.ignite.internal.pagemem.wal.IgniteWriteAheadLogManager;
-import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageSetFreeListPageRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.InitNewPageRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.PageListMetaResetCountRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListAddPageRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListInitNewPageRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListRemovePageRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListSetNextRecord;
-import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListSetPreviousRecord;
-import org.apache.ignite.internal.processors.cache.database.DataStructure;
-import org.apache.ignite.internal.processors.cache.database.freelist.io.PagesListMetaIO;
-import org.apache.ignite.internal.processors.cache.database.freelist.io.PagesListNodeIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.DataPageIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions;
-import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO;
-import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseBag;
-import org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler;
-import org.apache.ignite.internal.util.GridArrays;
-import org.apache.ignite.internal.util.GridLongList;
-import org.apache.ignite.internal.util.typedef.F;
-import org.apache.ignite.internal.util.typedef.internal.S;
-import org.apache.ignite.internal.util.typedef.internal.U;
-import org.jetbrains.annotations.Nullable;
-
-import static java.lang.Boolean.FALSE;
-import static java.lang.Boolean.TRUE;
-import static org.apache.ignite.internal.pagemem.PageIdAllocator.FLAG_DATA;
-import static org.apache.ignite.internal.pagemem.PageIdAllocator.FLAG_IDX;
-import static org.apache.ignite.internal.processors.cache.database.tree.io.PageIO.getPageId;
-
-/**
- * Striped doubly-linked list of page IDs optionally organized in buckets.
- */
-public abstract class PagesList extends DataStructure {
-    /** */
-    private static final int TRY_LOCK_ATTEMPTS =
-            IgniteSystemProperties.getInteger("IGNITE_PAGES_LIST_TRY_LOCK_ATTEMPTS", 10);
-
-    /** */
-    private static final int MAX_STRIPES_PER_BUCKET =
-        IgniteSystemProperties.getInteger("IGNITE_PAGES_LIST_STRIPES_PER_BUCKET",
-            Math.min(8, Runtime.getRuntime().availableProcessors() * 2));
-
-    /** */
-    protected final AtomicLong[] bucketsSize;
-
-    /** */
-    protected volatile boolean changed;
-
-    /** Page ID to store list metadata. */
-    private final long metaPageId;
-
-    /** Number of buckets. */
-    private final int buckets;
-
-    /** Name (for debug purposes). */
-    protected final String name;
-
-    /** */
-    private final PageHandler<Void, Boolean> cutTail = new CutTail();
-
-    /**
-     *
-     */
-    private final class CutTail extends PageHandler<Void, Boolean> {
-        @Override public Boolean run(
-            int cacheId,
-            long pageId,
-            long page,
-            long pageAddr,
-            PageIO iox,
-            Boolean walPlc,
-            Void ignore,
-            int bucket) throws IgniteCheckedException {
-            assert getPageId(pageAddr) == pageId;
-
-            PagesListNodeIO io = (PagesListNodeIO)iox;
-
-            long tailId = io.getNextId(pageAddr);
-
-            assert tailId != 0;
-
-            io.setNextId(pageAddr, 0L);
-
-            if (needWalDeltaRecord(pageId, page, walPlc))
-                wal.log(new PagesListSetNextRecord(cacheId, pageId, 0L));
-
-            updateTail(bucket, tailId, pageId);
-
-            return TRUE;
-        }
-    }
-
-    /**
-     * @param cacheId Cache ID.
-     * @param name Name (for debug purpose).
-     * @param pageMem Page memory.
-     * @param buckets Number of buckets.
-     * @param wal Write ahead log manager.
-     * @param metaPageId Metadata page ID.
-     */
-    protected PagesList(
-        int cacheId,
-        String name,
-        PageMemory pageMem,
-        int buckets,
-        IgniteWriteAheadLogManager wal,
-        long metaPageId
-    ) {
-        super(cacheId, pageMem, wal);
-
-        this.name = name;
-        this.buckets = buckets;
-        this.metaPageId = metaPageId;
-
-        bucketsSize = new AtomicLong[buckets];
-
-        for (int i = 0; i < buckets; i++)
-            bucketsSize[i] = new AtomicLong();
-    }
-
-    /**
-     * @param metaPageId Metadata page ID.
-     * @param initNew {@code True} if new list if created, {@code false} if should be initialized from metadata.
-     * @throws IgniteCheckedException If failed.
-     */
-    protected final void init(long metaPageId, boolean initNew) throws IgniteCheckedException {
-        if (metaPageId != 0L) {
-            if (initNew) {
-                init(metaPageId, PagesListMetaIO.VERSIONS.latest());
-            }
-            else {
-                Map<Integer, GridLongList> bucketsData = new HashMap<>();
-
-                long nextId = metaPageId;
-
-                while (nextId != 0) {
-                    final long pageId = nextId;
-                    final long page = acquirePage(pageId);
-
-                    try {
-                        long pageAddr = readLock(pageId, page); // No concurrent recycling on init.
-
-                        assert pageAddr != 0L;
-
-                        try {
-                            PagesListMetaIO io = PagesListMetaIO.VERSIONS.forPage(pageAddr);
-
-                            io.getBucketsData(pageAddr, bucketsData);
-
-                            nextId = io.getNextMetaPageId(pageAddr);
-
-                            assert nextId != pageId :
-                                "Loop detected [next=" + U.hexLong(nextId) + ", cur=" + U.hexLong(pageId) + ']';
-
-
-                        }
-                        finally {
-                            readUnlock(pageId, page, pageAddr);
-                        }
-                    }
-                    finally {
-                        releasePage(pageId, page);
-                    }
-                }
-
-                for (Map.Entry<Integer, GridLongList> e : bucketsData.entrySet()) {
-                    int bucket = e.getKey();
-                    long bucketSize = 0;
-
-                    Stripe[] old = getBucket(bucket);
-                    assert old == null;
-
-                    long[] upd = e.getValue().array();
-
-                    Stripe[] tails = new Stripe[upd.length];
-
-                    for (int i = 0; i < upd.length; i++) {
-                        long tailId = upd[i];
-
-                        long prevId = tailId;
-                        int cnt = 0;
-
-                        while (prevId != 0L) {
-                            final long pageId = prevId;
-                            final long page = acquirePage(pageId);
-                            try  {
-                                long pageAddr = readLock(pageId, page);
-
-                                assert pageAddr != 0L;
-
-                                try {
-                                    PagesListNodeIO io = PagesListNodeIO.VERSIONS.forPage(pageAddr);
-
-                                    cnt += io.getCount(pageAddr);
-                                    prevId = io.getPreviousId(pageAddr);
-
-                                    // In reuse bucket the page itself can be used as a free page.
-                                    if (isReuseBucket(bucket) && prevId != 0L)
-                                        cnt++;
-                                }
-                                finally {
-                                    readUnlock(pageId, page, pageAddr);
-                                }
-                            }
-                            finally {
-                                releasePage(pageId, page);
-                            }
-                        }
-
-                        Stripe stripe = new Stripe(tailId, cnt == 0);
-                        tails[i] = stripe;
-                        bucketSize += cnt;
-                    }
-
-                    boolean ok = casBucket(bucket, null, tails);
-                    assert ok;
-
-                    bucketsSize[bucket].set(bucketSize);
-
-                    changed = true;
-                }
-            }
-        }
-    }
-
-    /**
-     * @throws IgniteCheckedException If failed.
-     */
-    public void saveMetadata() throws IgniteCheckedException {
-        assert metaPageId != 0;
-
-        long curId = 0L;
-        long curPage = 0L;
-        long curAddr = 0L;
-
-        PagesListMetaIO curIo = null;
-
-        long nextPageId = metaPageId;
-
-        if (!changed)
-            return;
-
-        try {
-            for (int bucket = 0; bucket < buckets; bucket++) {
-                Stripe[] tails = getBucket(bucket);
-
-                if (tails != null) {
-                    int tailIdx = 0;
-
-                    while (tailIdx < tails.length) {
-                        int written = curPage != 0L ? curIo.addTails(pageMem.pageSize(), curAddr, bucket, tails, tailIdx) : 0;
-
-                        if (written == 0) {
-                            if (nextPageId == 0L) {
-                                nextPageId = allocatePageNoReuse();
-
-                                if (curPage != 0L) {
-                                    curIo.setNextMetaPageId(curAddr, nextPageId);
-
-                                    releaseAndClose(curId, curPage, curAddr);
-                                }
-
-                                curId = nextPageId;
-                                curPage = acquirePage(curId);
-                                curAddr = writeLock(curId, curPage);
-
-                                curIo = PagesListMetaIO.VERSIONS.latest();
-
-                                curIo.initNewPage(curAddr, curId, pageSize());
-                            }
-                            else {
-                                releaseAndClose(curId, curPage, curAddr);
-
-                                curId = nextPageId;
-                                curPage = acquirePage(curId);
-                                curAddr = writeLock(curId, curPage);
-
-                                curIo = PagesListMetaIO.VERSIONS.forPage(curAddr);
-
-                                curIo.resetCount(curAddr);
-                            }
-
-                            nextPageId = curIo.getNextMetaPageId(curAddr);
-                        }
-                        else
-                            tailIdx += written;
-                    }
-                }
-            }
-        }
-        finally {
-            releaseAndClose(curId, curPage, curAddr);
-        }
-
-        while (nextPageId != 0L) {
-            long pageId = nextPageId;
-
-            long page = acquirePage(pageId);
-            try {
-                long pageAddr = writeLock(pageId, page);
-
-                try {
-                    PagesListMetaIO io = PagesListMetaIO.VERSIONS.forPage(pageAddr);
-
-                    io.resetCount(pageAddr);
-
-                    if (needWalDeltaRecord(pageId, page, null))
-                        wal.log(new PageListMetaResetCountRecord(cacheId, pageId));
-
-                    nextPageId = io.getNextMetaPageId(pageAddr);
-                }
-                finally {
-                    writeUnlock(pageId, page, pageAddr, true);
-                }
-            }
-            finally {
-                releasePage(pageId, page);
-            }
-        }
-
-        changed = false;
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page absolute pointer.
-     * @param pageAddr Page address.
-     * @throws IgniteCheckedException If failed.
-     */
-    private void releaseAndClose(long pageId, long page, long pageAddr) throws IgniteCheckedException {
-        if (page != 0L) {
-            try {
-                // No special WAL record because we most likely changed the whole page.
-                writeUnlock(pageId, page, pageAddr, TRUE, true);
-            }
-            finally {
-                releasePage(pageId, page);
-            }
-        }
-    }
-
-    /**
-     * @param bucket Bucket index.
-     * @return Bucket.
-     */
-    protected abstract Stripe[] getBucket(int bucket);
-
-    /**
-     * @param bucket Bucket index.
-     * @param exp Expected bucket.
-     * @param upd Updated bucket.
-     * @return {@code true} If succeeded.
-     */
-    protected abstract boolean casBucket(int bucket, Stripe[] exp, Stripe[] upd);
-
-    /**
-     * @param bucket Bucket index.
-     * @return {@code true} If it is a reuse bucket.
-     */
-    protected abstract boolean isReuseBucket(int bucket);
-
-    /**
-     * @param io IO.
-     * @param prevId Previous page ID.
-     * @param prev Previous page buffer.
-     * @param nextId Next page ID.
-     * @param next Next page buffer.
-     */
-    private void setupNextPage(PagesListNodeIO io, long prevId, long prev, long nextId, long next) {
-        assert io.getNextId(prev) == 0L;
-
-        io.initNewPage(next, nextId, pageSize());
-        io.setPreviousId(next, prevId);
-
-        io.setNextId(prev, nextId);
-    }
-
-    /**
-     * Adds stripe to the given bucket.
-     *
-     * @param bucket Bucket.
-     * @param reuse {@code True} if possible to use reuse list.
-     * @throws IgniteCheckedException If failed.
-     * @return Tail page ID.
-     */
-    private Stripe addStripe(int bucket, boolean reuse) throws IgniteCheckedException {
-        long pageId = reuse ? allocatePage(null) : allocatePageNoReuse();
-
-        init(pageId, PagesListNodeIO.VERSIONS.latest());
-
-        Stripe stripe = new Stripe(pageId, true);
-
-        for (;;) {
-            Stripe[] old = getBucket(bucket);
-            Stripe[] upd;
-
-            if (old != null) {
-                int len = old.length;
-
-                upd = Arrays.copyOf(old, len + 1);
-
-                upd[len] = stripe;
-            }
-            else
-                upd = new Stripe[]{stripe};
-
-            if (casBucket(bucket, old, upd))
-                return stripe;
-        }
-    }
-
-    /**
-     * @param bucket Bucket index.
-     * @param oldTailId Old tail page ID to replace.
-     * @param newTailId New tail page ID.
-     * @return {@code True} if stripe was removed.
-     */
-    private boolean updateTail(int bucket, long oldTailId, long newTailId) {
-        int idx = -1;
-
-        for (;;) {
-            Stripe[] tails = getBucket(bucket);
-
-            // Tail must exist to be updated.
-            assert !F.isEmpty(tails) : "Missing tails [bucket=" + bucket + ", tails=" + Arrays.toString(tails) +
-                ", metaPage=" + U.hexLong(metaPageId) + ']';
-
-            idx = findTailIndex(tails, oldTailId, idx);
-
-            assert tails[idx].tailId == oldTailId;
-
-            if (newTailId == 0L) {
-                if (tails.length <= MAX_STRIPES_PER_BUCKET / 2) {
-                    tails[idx].empty = true;
-
-                    return false;
-                }
-
-                Stripe[] newTails;
-
-                if (tails.length != 1)
-                    newTails = GridArrays.remove(tails, idx);
-                else
-                    newTails = null; // Drop the bucket completely.
-
-                if (casBucket(bucket, tails, newTails))
-                    return true;
-            }
-            else {
-                // It is safe to assign new tail since we do it only when write lock on tail is held.
-                tails[idx].tailId = newTailId;
-
-                return true;
-            }
-        }
-    }
-
-    /**
-     * @param tails Tails.
-     * @param tailId Tail ID to find.
-     * @param expIdx Expected index.
-     * @return First found index of the given tail ID.
-     */
-    private static int findTailIndex(Stripe[] tails, long tailId, int expIdx) {
-        if (expIdx != -1 && tails.length > expIdx && tails[expIdx].tailId == tailId)
-            return expIdx;
-
-        for (int i = 0; i < tails.length; i++) {
-            if (tails[i].tailId == tailId)
-                return i;
-        }
-
-        throw new IllegalStateException("Tail not found: " + tailId);
-    }
-
-    /**
-     * @param bucket Bucket.
-     * @return Page ID where the given page
-     * @throws IgniteCheckedException If failed.
-     */
-    private Stripe getPageForPut(int bucket) throws IgniteCheckedException {
-        Stripe[] tails = getBucket(bucket);
-
-        if (tails == null)
-            return addStripe(bucket, true);
-
-        return randomTail(tails);
-    }
-
-    /**
-     * @param tails Tails.
-     * @return Random tail.
-     */
-    private static Stripe randomTail(Stripe[] tails) {
-        int len = tails.length;
-
-        assert len != 0;
-
-        return tails[randomInt(len)];
-    }
-
-    /**
-     * !!! For tests only, does not provide any correctness guarantees for concurrent access.
-     *
-     * @param bucket Bucket index.
-     * @return Number of pages stored in this list.
-     * @throws IgniteCheckedException If failed.
-     */
-    protected final long storedPagesCount(int bucket) throws IgniteCheckedException {
-        long res = 0;
-
-        Stripe[] tails = getBucket(bucket);
-
-        if (tails != null) {
-            for (Stripe tail : tails) {
-                long tailId = tail.tailId;
-
-                while (tailId != 0L) {
-                    final long pageId = tailId;
-                    final long page = acquirePage(pageId);
-                    try {
-                        long pageAddr = readLock(pageId, page);
-
-                        assert pageAddr != 0L;
-
-                        try {
-                            PagesListNodeIO io = PagesListNodeIO.VERSIONS.forPage(pageAddr);
-
-                            int cnt = io.getCount(pageAddr);
-
-                            assert cnt >= 0;
-
-                            res += cnt;
-                            tailId = io.getPreviousId(pageAddr);
-
-                            // In reuse bucket the page itself can be used as a free page.
-                            if (isReuseBucket(bucket) && tailId != 0L)
-                                res++;
-                        }
-                        finally {
-                            readUnlock(pageId, page, pageAddr);
-                        }
-                    }
-                    finally {
-                        releasePage(pageId, page);
-                    }
-                }
-            }
-        }
-
-        assert res == bucketsSize[bucket].get() : "Wrong bucket size counter [exp=" + res + ", cntr=" + bucketsSize[bucket].get() + ']';
-
-        return res;
-    }
-
-    /**
-     * @param bag Reuse bag.
-     * @param dataId Data page ID.
-     * @param dataPage Data page pointer.
-     * @param dataAddr Data page address.
-     * @param bucket Bucket.
-     * @throws IgniteCheckedException If failed.
-     */
-    protected final void put(
-        ReuseBag bag,
-        final long dataId,
-        final long dataPage,
-        final long dataAddr,
-        int bucket)
-        throws IgniteCheckedException {
-        assert bag == null ^ dataAddr == 0L;
-
-        for (int lockAttempt = 0; ;) {
-            Stripe stripe = getPageForPut(bucket);
-
-            final long tailId = stripe.tailId;
-            final long tailPage = acquirePage(tailId);
-
-            try {
-                long tailAddr = writeLockPage(tailId, tailPage, bucket, lockAttempt++); // Explicit check.
-
-                if (tailAddr == 0L) {
-                    if (isReuseBucket(bucket) && lockAttempt == TRY_LOCK_ATTEMPTS)
-                        addStripeForReuseBucket(bucket);
-
-                    continue;
-                }
-
-                assert PageIO.getPageId(tailAddr) == tailId : "pageId = " + PageIO.getPageId(tailAddr) + ", tailId = " + tailId;
-                assert PageIO.getType(tailAddr) == PageIO.T_PAGE_LIST_NODE;
-
-                boolean ok = false;
-
-                try {
-                    PagesListNodeIO io = PageIO.getPageIO(tailAddr);
-
-                    ok = bag != null ?
-                        // Here we can always take pages from the bag to build our list.
-                        putReuseBag(tailId, tailPage, tailAddr, io, bag, bucket) :
-                        // Here we can use the data page to build list only if it is empty and
-                        // it is being put into reuse bucket. Usually this will be true, but there is
-                        // a case when there is no reuse bucket in the free list, but then deadlock
-                        // on node page allocation from separate reuse list is impossible.
-                        // If the data page is not empty it can not be put into reuse bucket and thus
-                        // the deadlock is impossible as well.
-                        putDataPage(tailId, tailPage, tailAddr, io, dataId, dataPage, dataAddr, bucket);
-
-                    if (ok) {
-                        stripe.empty = false;
-
-                        return;
-                    }
-                }
-                finally {
-                    writeUnlock(tailId, tailPage, tailAddr, ok);
-                }
-            }
-            finally {
-                releasePage(tailId, tailPage);
-            }
-        }
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page pointer.
-     * @param pageAddr Page address.
-     * @param io IO.
-     * @param dataId Data page ID.
-     * @param dataPage Data page pointer.
-     * @param dataAddr Data page address.
-     * @param bucket Bucket.
-     * @return {@code true} If succeeded.
-     * @throws IgniteCheckedException If failed.
-     */
-    private boolean putDataPage(
-        final long pageId,
-        final long page,
-        final long pageAddr,
-        PagesListNodeIO io,
-        final long dataId,
-        final long dataPage,
-        final long dataAddr,
-        int bucket
-    ) throws IgniteCheckedException {
-        if (io.getNextId(pageAddr) != 0L)
-            return false; // Splitted.
-
-        int idx = io.addPage(pageAddr, dataId, pageSize());
-
-        if (idx == -1)
-            handlePageFull(pageId, page, pageAddr, io, dataId, dataPage, dataAddr, bucket);
-        else {
-            incrementBucketSize(bucket);
-
-            if (needWalDeltaRecord(pageId, page, null))
-                wal.log(new PagesListAddPageRecord(cacheId, pageId, dataId));
-
-            DataPageIO dataIO = DataPageIO.VERSIONS.forPage(dataAddr);
-            dataIO.setFreeListPageId(dataAddr, pageId);
-
-            if (needWalDeltaRecord(dataId, dataPage, null))
-                wal.log(new DataPageSetFreeListPageRecord(cacheId, dataId, pageId));
-        }
-
-        return true;
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page pointer.
-     * @param pageAddr Page address.
-     * @param io IO.
-     * @param dataId Data page ID.
-     * @param data Data page pointer.
-     * @param dataAddr Data page address.
-     * @param bucket Bucket index.
-     * @throws IgniteCheckedException If failed.
-     * */
-    private void handlePageFull(
-        final long pageId,
-        final long page,
-        final long pageAddr,
-        PagesListNodeIO io,
-        final long dataId,
-        final long data,
-        final long dataAddr,
-        int bucket
-    ) throws IgniteCheckedException {
-        DataPageIO dataIO = DataPageIO.VERSIONS.forPage(dataAddr);
-
-        // Attempt to add page failed: the node page is full.
-        if (isReuseBucket(bucket)) {
-            // If we are on the reuse bucket, we can not allocate new page, because it may cause deadlock.
-            assert dataIO.isEmpty(dataAddr); // We can put only empty data pages to reuse bucket.
-
-            // Change page type to index and add it as next node page to this list.
-            long newDataId = PageIdUtils.changeType(dataId, FLAG_IDX);
-
-            setupNextPage(io, pageId, pageAddr, newDataId, dataAddr);
-
-            if (needWalDeltaRecord(pageId, page, null))
-                wal.log(new PagesListSetNextRecord(cacheId, pageId, newDataId));
-
-            if (needWalDeltaRecord(dataId, data, null))
-                wal.log(new PagesListInitNewPageRecord(
-                    cacheId,
-                    dataId,
-                    io.getType(),
-                    io.getVersion(),
-                    newDataId,
-                    pageId, 0L));
-
-            // In reuse bucket the page itself can be used as a free page.
-            incrementBucketSize(bucket);
-
-            updateTail(bucket, pageId, newDataId);
-        }
-        else {
-            // Just allocate a new node page and add our data page there.
-            final long nextId = allocatePage(null);
-            final long nextPage = acquirePage(nextId);
-
-            try {
-                long nextPageAddr = writeLock(nextId, nextPage); // Newly allocated page.
-
-                assert nextPageAddr != 0L;
-
-                // Here we should never write full page, because it is known to be new.
-                Boolean nextWalPlc = FALSE;
-
-                try {
-                    setupNextPage(io, pageId, pageAddr, nextId, nextPageAddr);
-
-                    if (needWalDeltaRecord(pageId, page, null))
-                        wal.log(new PagesListSetNextRecord(cacheId, pageId, nextId));
-
-                    int idx = io.addPage(nextPageAddr, dataId, pageSize());
-
-                    if (needWalDeltaRecord(nextId, nextPage, nextWalPlc))
-                        wal.log(new PagesListInitNewPageRecord(
-                            cacheId,
-                            nextId,
-                            io.getType(),
-                            io.getVersion(),
-                            nextId,
-                            pageId,
-                            dataId
-                        ));
-
-                    assert idx != -1;
-
-                    dataIO.setFreeListPageId(dataAddr, nextId);
-
-                    if (needWalDeltaRecord(dataId, data, null))
-                        wal.log(new DataPageSetFreeListPageRecord(cacheId, dataId, nextId));
-
-                    incrementBucketSize(bucket);
-
-                    updateTail(bucket, pageId, nextId);
-                }
-                finally {
-                    writeUnlock(nextId, nextPage, nextPageAddr, nextWalPlc, true);
-                }
-            }
-            finally {
-                releasePage(nextId, nextPage);
-            }
-        }
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page pointer.
-     * @param pageAddr Page address.
-     * @param io IO.
-     * @param bag Reuse bag.
-     * @param bucket Bucket.
-     * @return {@code true} If succeeded.
-     * @throws IgniteCheckedException if failed.
-     */
-    @SuppressWarnings("ForLoopReplaceableByForEach")
-    private boolean putReuseBag(
-        final long pageId,
-        final long page,
-        final long pageAddr,
-        PagesListNodeIO io,
-        ReuseBag bag,
-        int bucket
-    ) throws IgniteCheckedException {
-        if (io.getNextId(pageAddr) != 0L)
-            return false; // Splitted.
-
-        long nextId;
-
-        long prevId = pageId;
-        long prevPage = page;
-        long prevAddr = pageAddr;
-
-        Boolean walPlc = null;
-
-        GridLongList locked = null; // TODO may be unlock right away and do not keep all these pages locked?
-
-        try {
-            while ((nextId = bag.pollFreePage()) != 0L) {
-                int idx = io.addPage(prevAddr, nextId, pageSize());
-
-                if (idx == -1) { // Attempt to add page failed: the node page is full.
-
-                    final long nextPage = acquirePage(nextId);
-
-                    try {
-                        long nextPageAddr = writeLock(nextId, nextPage); // Page from reuse bag can't be concurrently recycled.
-
-                        assert nextPageAddr != 0L;
-
-                        if (locked == null) {
-                            locked = new GridLongList(6);
-                        }
-
-                        locked.add(nextId);
-                        locked.add(nextPage);
-                        locked.add(nextPageAddr);
-
-                        setupNextPage(io, prevId, prevAddr, nextId, nextPageAddr);
-
-                        if (needWalDeltaRecord(prevId, prevPage, walPlc))
-                            wal.log(new PagesListSetNextRecord(cacheId, prevId, nextId));
-
-                        // Here we should never write full page, because it is known to be new.
-                        if (needWalDeltaRecord(nextId, nextPage, FALSE))
-                            wal.log(new PagesListInitNewPageRecord(
-                                cacheId,
-                                nextId,
-                                io.getType(),
-                                io.getVersion(),
-                                nextId,
-                                prevId,
-                                0L
-                            ));
-
-                        // In reuse bucket the page itself can be used as a free page.
-                        if (isReuseBucket(bucket))
-                            incrementBucketSize(bucket);
-
-                        // Switch to this new page, which is now a part of our list
-                        // to add the rest of the bag to the new page.
-                        prevAddr = nextPageAddr;
-                        prevId = nextId;
-                        prevPage = nextPage;
-                        // Starting from tis point all wal records are written for reused pages from the bag.
-                        // This mean that we use delta records only.
-                        walPlc = FALSE;
-                    }
-                    finally {
-                        releasePage(nextId, nextPage);
-                    }
-                }
-                else {
-                    // TODO: use single WAL record for bag?
-                    if (needWalDeltaRecord(prevId, prevPage, walPlc))
-                        wal.log(new PagesListAddPageRecord(cacheId, prevId, nextId));
-
-                    incrementBucketSize(bucket);
-                }
-            }
-        }
-        finally {
-            if (locked != null) {
-                // We have to update our bucket with the new tail.
-                updateTail(bucket, pageId, prevId);
-
-                // Release write.
-                for (int i = 0; i < locked.size(); i+=3) {
-                    writeUnlock(locked.get(i), locked.get(i + 1), locked.get(i + 2), FALSE, true);
-                }
-            }
-        }
-
-        return true;
-    }
-
-    /**
-     * @param bucket Bucket index.
-     * @return Page for take.
-     */
-    private Stripe getPageForTake(int bucket) {
-        Stripe[] tails = getBucket(bucket);
-
-        if (tails == null || bucketsSize[bucket].get() == 0)
-            return null;
-
-        int len = tails.length;
-        int init = randomInt(len);
-        int cur = init;
-
-        while (true) {
-            Stripe stripe = tails[cur];
-
-            if (!stripe.empty)
-                return stripe;
-
-            if ((cur = (cur + 1) % len) == init)
-                return null;
-        }
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page pointer.
-     * @param bucket Bucket.
-     * @param lockAttempt Lock attempts counter.
-     * @return Page address if page is locked of {@code null} if can retry lock.
-     * @throws IgniteCheckedException If failed.
-     */
-    private long writeLockPage(long pageId, long page, int bucket, int lockAttempt)
-        throws IgniteCheckedException {
-        long pageAddr = tryWriteLock(pageId, page);
-
-        if (pageAddr != 0L)
-            return pageAddr;
-
-        if (lockAttempt == TRY_LOCK_ATTEMPTS) {
-            Stripe[] stripes = getBucket(bucket);
-
-            if (stripes == null || stripes.length < MAX_STRIPES_PER_BUCKET) {
-                if (!isReuseBucket(bucket))
-                    addStripe(bucket, true);
-
-                return 0L;
-            }
-        }
-
-        return lockAttempt < TRY_LOCK_ATTEMPTS ? 0L : writeLock(pageId, page); // Must be explicitly checked further.
-    }
-
-    /**
-     * @param bucket Bucket.
-     * @throws IgniteCheckedException If failed.
-     */
-    private void addStripeForReuseBucket(int bucket) throws IgniteCheckedException {
-        assert isReuseBucket(bucket);
-
-        Stripe[] stripes = getBucket(bucket);
-
-        if (stripes == null || stripes.length < MAX_STRIPES_PER_BUCKET)
-            addStripe(bucket, false);
-    }
-
-    /**
-     * @param bucket Bucket index.
-     * @param initIoVers Optional IO to initialize page.
-     * @return Removed page ID.
-     * @throws IgniteCheckedException If failed.
-     */
-    protected final long takeEmptyPage(int bucket, @Nullable IOVersions initIoVers) throws IgniteCheckedException {
-        for (int lockAttempt = 0; ;) {
-            Stripe stripe = getPageForTake(bucket);
-
-            if (stripe == null)
-                return 0L;
-
-            final long tailId = stripe.tailId;
-            final long tailPage = acquirePage(tailId);
-
-            try {
-                long tailAddr = writeLockPage(tailId, tailPage, bucket, lockAttempt++); // Explicit check.
-
-                if (tailAddr == 0L) {
-                    if (isReuseBucket(bucket) && lockAttempt == TRY_LOCK_ATTEMPTS)
-                        addStripeForReuseBucket(bucket);
-
-                    continue;
-                }
-
-                if (stripe.empty) {
-                    // Another thread took the last page.
-                    writeUnlock(tailId, tailPage, tailAddr, false);
-
-                    if (bucketsSize[bucket].get() > 0) {
-                        lockAttempt--; // Ignore current attempt.
-
-                        continue;
-                    }
-                    else
-                        return 0L;
-                }
-
-                assert PageIO.getPageId(tailAddr) == tailId : "tailId = " + tailId + ", tailPageId = " + PageIO.getPageId(tailAddr);
-                assert PageIO.getType(tailAddr) == PageIO.T_PAGE_LIST_NODE;
-
-                boolean dirty = false;
-                long dataPageId;
-                long recycleId = 0L;
-
-                try {
-                    PagesListNodeIO io = PagesListNodeIO.VERSIONS.forPage(tailAddr);
-
-                    if (io.getNextId(tailAddr) != 0) {
-                        // It is not a tail anymore, retry.
-                        continue;
-                    }
-
-                    long pageId = io.takeAnyPage(tailAddr);
-
-                    if (pageId != 0L) {
-                        decrementBucketSize(bucket);
-
-                        if (needWalDeltaRecord(tailId, tailPage, null))
-                            wal.log(new PagesListRemovePageRecord(cacheId, tailId, pageId));
-
-                        dirty = true;
-
-                        dataPageId = pageId;
-
-                        if (io.isEmpty(tailAddr)) {
-                            long prevId = io.getPreviousId(tailAddr);
-
-                            // If we got an empty page in non-reuse bucket, move it back to reuse list
-                            // to prevent empty page leak to data pages.
-                            if (!isReuseBucket(bucket)) {
-                                if (prevId != 0L) {
-                                    Boolean ok = write(prevId, cutTail, null, bucket, FALSE);
-
-                                    assert ok == TRUE : ok;
-
-                                    recycleId = recyclePage(tailId, tailPage, tailAddr, null);
-                                }
-                                else
-                                    stripe.empty = true;
-                            }
-                            else
-                                stripe.empty = prevId == 0L;
-                        }
-                    }
-                    else {
-                        // The tail page is empty, but stripe is not. It might
-                        // happen only if we are in reuse bucket and it has
-                        // a previous page, so, the current page can be collected
-                        assert isReuseBucket(bucket);
-
-                        long prevId = io.getPreviousId(tailAddr);
-
-                        assert prevId != 0L;
-
-                        Boolean ok = write(prevId, cutTail, bucket, FALSE);
-
-                        assert ok == TRUE : ok;
-
-                        decrementBucketSize(bucket);
-
-                        if (initIoVers != null) {
-                            dataPageId = PageIdUtils.changeType(tailId, FLAG_DATA);
-
-                            PageIO initIo = initIoVers.latest();
-
-                            initIo.initNewPage(tailAddr, dataPageId, pageSize());
-
-                            if (needWalDeltaRecord(tailId, tailPage, null)) {
-                                wal.log(new InitNewPageRecord(cacheId, tailId, initIo.getType(),
-                                    initIo.getVersion(), dataPageId));
-                            }
-                        }
-                        else
-                            dataPageId = recyclePage(tailId, tailPage, tailAddr, null);
-
-                        dirty = true;
-                    }
-
-                    // If we do not have a previous page (we are at head), then we still can return
-                    // current page but we have to drop the whole stripe. Since it is a reuse bucket,
-                    // we will not do that, but just return 0L, because this may produce contention on
-                    // meta page.
-                }
-                finally {
-                    writeUnlock(tailId, tailPage, tailAddr, dirty);
-                }
-
-                // Put recycled page (if any) to the reuse bucket after tail is unlocked.
-                if (recycleId != 0L) {
-                    assert !isReuseBucket(bucket);
-
-                    reuseList.addForRecycle(new SingletonReuseBag(recycleId));
-                }
-
-                return dataPageId;
-            }
-            finally {
-                releasePage(tailId, tailPage);
-            }
-        }
-    }
-
-    /**
-     * @param dataId Data page ID.
-     * @param dataPage Data page pointer.
-     * @param dataAddr Data page address.
-     * @param dataIO Data page IO.
-     * @param bucket Bucket index.
-     * @throws IgniteCheckedException If failed.
-     * @return {@code True} if page was removed.
-     */
-    protected final boolean removeDataPage(
-        final long dataId,
-        final long dataPage,
-        final long dataAddr,
-        DataPageIO dataIO,
-        int bucket)
-        throws IgniteCheckedException {
-        final long pageId = dataIO.getFreeListPageId(dataAddr);
-
-        assert pageId != 0;
-
-        final long page = acquirePage(pageId);
-        try {
-            long nextId;
-
-            long recycleId = 0L;
-
-            long pageAddr = writeLock(pageId, page); // Explicit check.
-
-            if (pageAddr == 0L)
-                return false;
-
-            boolean rmvd = false;
-
-            try {
-                PagesListNodeIO io = PagesListNodeIO.VERSIONS.forPage(pageAddr);
-
-                rmvd = io.removePage(pageAddr, dataId);
-
-                if (!rmvd)
-                    return false;
-
-                decrementBucketSize(bucket);
-
-                if (needWalDeltaRecord(pageId, page, null))
-                    wal.log(new PagesListRemovePageRecord(cacheId, pageId, dataId));
-
-                // Reset free list page ID.
-                dataIO.setFreeListPageId(dataAddr, 0L);
-
-                if (needWalDeltaRecord(dataId, dataPage, null))
-                    wal.log(new DataPageSetFreeListPageRecord(cacheId, dataId, 0L));
-
-                if (!io.isEmpty(pageAddr))
-                    return true; // In optimistic case we still have something in the page and can leave it as is.
-
-                // If the page is empty, we have to try to drop it and link next and previous with each other.
-                nextId = io.getNextId(pageAddr);
-
-                // If there are no next page, then we can try to merge without releasing current write lock,
-                // because if we will need to lock previous page, the locking order will be already correct.
-                if (nextId == 0L) {
-                    long prevId = io.getPreviousId(pageAddr);
-
-                    recycleId = mergeNoNext(pageId, page, pageAddr, prevId, bucket);
-                }
-            }
-            finally {
-                writeUnlock(pageId, page, pageAddr, rmvd);
-            }
-
-            // Perform a fair merge after lock release (to have a correct locking order).
-            if (nextId != 0L)
-                recycleId = merge(pageId, page, nextId, bucket);
-
-            if (recycleId != 0L)
-                reuseList.addForRecycle(new SingletonReuseBag(recycleId));
-
-            return true;
-        }
-        finally {
-            releasePage(pageId, page);
-        }
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page pointer.
-     * @param pageAddr Page address.
-     * @param prevId Previous page ID.
-     * @param bucket Bucket index.
-     * @return Page ID to recycle.
-     * @throws IgniteCheckedException If failed.
-     */
-    private long mergeNoNext(
-        long pageId,
-        long page,
-        long pageAddr,
-        long prevId,
-        int bucket)
-        throws IgniteCheckedException {
-        // If we do not have a next page (we are tail) and we are on reuse bucket,
-        // then we can leave as is as well, because it is normal to have an empty tail page here.
-        if (isReuseBucket(bucket))
-            return 0L;
-
-        if (prevId != 0L) { // Cut tail if we have a previous page.
-            Boolean ok = write(prevId, cutTail, null, bucket, FALSE);
-
-            assert ok == TRUE: ok;
-        }
-        else {
-            // If we don't have a previous, then we are tail page of free list, just drop the stripe.
-            boolean rmvd = updateTail(bucket, pageId, 0L);
-
-            if (!rmvd)
-                return 0L;
-        }
-
-        return recyclePage(pageId, page, pageAddr, null);
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page pointer.
-     * @param nextId Next page ID.
-     * @param bucket Bucket index.
-     * @return Page ID to recycle.
-     * @throws IgniteCheckedException If failed.
-     */
-    private long merge(
-        final long pageId,
-        final long page,
-        long nextId,
-        int bucket)
-        throws IgniteCheckedException {
-        assert nextId != 0; // We should do mergeNoNext then.
-
-        // Lock all the pages in correct order (from next to previous) and do the merge in retry loop.
-        for (;;) {
-            final long curId = nextId;
-            final long curPage = curId == 0L ? 0L : acquirePage(curId);
-            try {
-                boolean write = false;
-
-                final long curAddr = curPage == 0L ? 0L : writeLock(curId, curPage); // Explicit check.
-                final long pageAddr = writeLock(pageId, page); // Explicit check.
-
-                if (pageAddr == 0L) {
-                    if (curAddr != 0L) // Unlock next page if needed.
-                        writeUnlock(curId, curPage, curAddr, false);
-
-                    return 0L; // Someone has merged or taken our empty page concurrently. Nothing to do here.
-                }
-
-                try {
-                    PagesListNodeIO io = PagesListNodeIO.VERSIONS.forPage(pageAddr);
-
-                    if (!io.isEmpty(pageAddr))
-                        return 0L; // No need to merge anymore.
-
-                    // Check if we see a consistent state of the world.
-                    if (io.getNextId(pageAddr) == curId && (curId == 0L) == (curAddr == 0L)) {
-                        long recycleId = doMerge(pageId, page, pageAddr, io, curId, curPage, curAddr, bucket);
-
-                        write = true;
-
-                        return recycleId; // Done.
-                    }
-
-                    // Reread next page ID and go for retry.
-                    nextId = io.getNextId(pageAddr);
-                }
-                finally {
-                    if (curAddr != 0L)
-                        writeUnlock(curId, curPage, curAddr, write);
-
-                    writeUnlock(pageId, page, pageAddr, write);
-                }
-            }
-            finally {
-                if (curPage != 0L)
-                    releasePage(curId, curPage);
-            }
-        }
-    }
-
-    /**
-     * @param pageId Page ID.
-     * @param page Page absolute pointer.
-     * @param pageAddr Page address.
-     * @param io IO.
-     * @param nextId Next page ID.
-     * @param nextPage Next page absolute pointer.
-     * @param nextAddr Next page address.
-     * @param bucket Bucket index.
-     * @return Page to recycle.
-     * @throws IgniteCheckedException If failed.
-     */
-    private long doMerge(
-        long pageId,
-        long page,
-        long pageAddr,
-        PagesListNodeIO io,
-        long nextId,
-        long nextPage,
-        long nextAddr,
-        int bucket
-    ) throws IgniteCheckedException {
-        long prevId = io.getPreviousId(pageAddr);
-
-        if (nextId == 0L)
-            return mergeNoNext(pageId, page, pageAddr, prevId, bucket);
-        else {
-            // No one must be able to merge it while we keep a reference.
-            assert getPageId(nextAddr) == nextId;
-
-            if (prevId == 0L) { // No previous page: we are at head.
-                // These references must be updated at the same time in write locks.
-                assert PagesListNodeIO.VERSIONS.forPage(nextAddr).getPreviousId(nextAddr) == pageId;
-
-                PagesListNodeIO nextIO = PagesListNodeIO.VERSIONS.forPage(nextAddr);
-                nextIO.setPreviousId(nextAddr, 0);
-
-                if (needWalDeltaRecord(nextId, nextPage, null))
-                    wal.log(new PagesListSetPreviousRecord(cacheId, nextId, 0L));
-            }
-            else // Do a fair merge: link previous and next to each other.
-                fairMerge(prevId, pageId, nextId, nextPage, nextAddr);
-
-            return recyclePage(pageId, page, pageAddr, null);
-        }
-    }
-
-    /**
-     * Link previous and next to each other.
-     * @param prevId Previous Previous page ID.
-     * @param pageId Page ID.
-     * @param nextId Next page ID.
-     * @param nextPage Next page absolute pointer.
-     * @param nextAddr Next page address.
-     * @throws IgniteCheckedException If failed.
-     */
-    private void fairMerge(
-        final long prevId,
-        long pageId,
-        long nextId,
-        long nextPage,
-        long nextAddr)
-        throws IgniteCheckedException {
-        long prevPage = acquirePage(prevId);
-
-        try {
-            final long prevAddr = writeLock(prevId, prevPage); // No check, we keep a reference.
-            assert prevAddr != 0L;
-            try {
-                PagesListNodeIO prevIO = PagesListNodeIO.VERSIONS.forPage(prevAddr);
-                PagesListNodeIO nextIO = PagesListNodeIO.VERSIONS.forPage(nextAddr);
-
-                // These references must be updated at the same time in write locks.
-                assert prevIO.getNextId(prevAddr) == pageId;
-                assert nextIO.getPreviousId(nextAddr) == pageId;
-
-                prevIO.setNextId(prevAddr, nextId);
-
-                if (needWalDeltaRecord(prevId, prevPage, null))
-                    wal.log(new PagesListSetNextRecord(cacheId, prevId, nextId));
-
-                nextIO.setPreviousId(nextAddr, prevId);
-
-                if (needWalDeltaRecord(nextId, nextPage, null))
-                    wal.log(new PagesListSetPreviousRecord(cacheId, nextId, prevId));
-            }
-            finally {
-                writeUnlock(prevId, prevPage, prevAddr, true);
-            }
-        }
-        finally {
-            releasePage(prevId, prevPage);
-        }
-    }
-
-    /**
-     * Increments bucket size and updates changed flag.
-     *
-     * @param bucket Bucket number.
-     */
-    private void incrementBucketSize(int bucket) {
-        bucketsSize[bucket].incrementAndGet();
-
-        // Ok to have a race here, see the field javadoc.
-        if (!changed)
-            changed = true;
-    }
-
-    /**
-     * Increments bucket size and updates changed flag.
-     *
-     * @param bucket Bucket number.
-     */
-    private void decrementBucketSize(int bucket) {
-        bucketsSize[bucket].decrementAndGet();
-
-        // Ok to have a race here, see the field javadoc.
-        if (!changed)
-            changed = true;
-    }
-
-    /**
-     * Singleton reuse bag.
-     */
-    private static final class SingletonReuseBag implements ReuseBag {
-        /** */
-        long pageId;
-
-        /**
-         * @param pageId Page ID.
-         */
-        SingletonReuseBag(long pageId) {
-            this.pageId = pageId;
-        }
-
-        /** {@inheritDoc} */
-        @Override public void addFreePage(long pageId) {
-            throw new IllegalStateException("Should never be called.");
-        }
-
-        /** {@inheritDoc} */
-        @Override public long pollFreePage() {
-            long res = pageId;
-
-            pageId = 0L;
-
-            return res;
-        }
-
-        /** {@inheritDoc} */
-        @Override public String toString() {
-            return S.toString(SingletonReuseBag.class, this, "pageId", U.hexLong(pageId));
-        }
-    }
-
-    /**
-     *
-     */
-    public static final class Stripe {
-        /** */
-        public volatile long tailId;
-
-        /** */
-        volatile boolean empty;
-
-        /**
-         * @param tailId Tail ID.
-         * @param empty Empty flag.
-         */
-        Stripe(long tailId, boolean empty) {
-            this.tailId = tailId;
-            this.empty = empty;
-        }
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/6bf5ce46/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListMetaIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListMetaIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListMetaIO.java
deleted file mode 100644
index 6bd50a3..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListMetaIO.java
+++ /dev/null
@@ -1,186 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.ignite.internal.processors.cache.database.freelist.io;
-
-import java.util.Map;
-import org.apache.ignite.internal.pagemem.PageUtils;
-import org.apache.ignite.internal.processors.cache.database.freelist.PagesList;
-import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions;
-import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO;
-import org.apache.ignite.internal.util.GridLongList;
-
-/**
- *
- */
-public class PagesListMetaIO extends PageIO {
-    /** */
-    private static final int CNT_OFF = COMMON_HEADER_END;
-
-    /** */
-    private static final int NEXT_META_PAGE_OFF = CNT_OFF + 2;
-
-    /** */
-    private static final int ITEMS_OFF = NEXT_META_PAGE_OFF + 8;
-
-    /** */
-    private static final int ITEM_SIZE = 10;
-
-    /** */
-    public static final IOVersions<PagesListMetaIO> VERSIONS = new IOVersions<>(
-        new PagesListMetaIO(1)
-    );
-
-    /**
-     * @param ver  Page format version.
-     */
-    private PagesListMetaIO(int ver) {
-        super(T_PAGE_LIST_META, ver);
-    }
-
-    /** {@inheritDoc} */
-    @Override public void initNewPage(long pageAddr, long pageId, int pageSize) {
-        super.initNewPage(pageAddr, pageId, pageSize);
-
-        setCount(pageAddr, 0);
-        setNextMetaPageId(pageAddr, 0L);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @return Stored items count.
-     */
-    private int getCount(long pageAddr) {
-        return PageUtils.getShort(pageAddr, CNT_OFF);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @param cnt Stored items count.
-     */
-    private void setCount(long pageAddr, int cnt) {
-        assert cnt >= 0 && cnt <= Short.MAX_VALUE : cnt;
-
-        PageUtils.putShort(pageAddr, CNT_OFF, (short)cnt);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @return Next meta page ID.
-     */
-    public long getNextMetaPageId(long pageAddr) {
-        return PageUtils.getLong(pageAddr, NEXT_META_PAGE_OFF);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @param metaPageId Next meta page ID.
-     */
-    public void setNextMetaPageId(long pageAddr, long metaPageId) {
-        PageUtils.putLong(pageAddr, NEXT_META_PAGE_OFF, metaPageId);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     */
-    public void resetCount(long pageAddr) {
-        setCount(pageAddr, 0);
-    }
-
-    /**
-     * @param pageSize Page size.
-     * @param pageAddr Page address.
-     * @param bucket Bucket number.
-     * @param tails Tails.
-     * @param tailsOff Tails offset.
-     * @return Number of items written.
-     */
-    public int addTails(int pageSize, long pageAddr, int bucket, PagesList.Stripe[] tails, int tailsOff) {
-        assert bucket >= 0 && bucket <= Short.MAX_VALUE : bucket;
-
-        int cnt = getCount(pageAddr);
-        int cap = getCapacity(pageSize, pageAddr);
-
-        if (cnt == cap)
-            return 0;
-
-        int off = offset(cnt);
-
-        int write = Math.min(cap - cnt, tails.length - tailsOff);
-
-        for (int i = 0; i < write; i++) {
-            PageUtils.putShort(pageAddr, off, (short)bucket);
-            PageUtils.putLong(pageAddr, off + 2, tails[tailsOff].tailId);
-
-            tailsOff++;
-
-            off += ITEM_SIZE;
-        }
-
-        setCount(pageAddr, cnt + write);
-
-        return write;
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @param res Results map.
-     */
-    public void getBucketsData(long pageAddr, Map<Integer, GridLongList> res) {
-        int cnt = getCount(pageAddr);
-
-        assert cnt >= 0 && cnt <= Short.MAX_VALUE : cnt;
-
-        if (cnt == 0)
-            return;
-
-        int off = offset(0);
-
-        for (int i = 0; i < cnt; i++) {
-            Integer bucket = (int)PageUtils.getShort(pageAddr, off);
-            assert bucket >= 0 && bucket <= Short.MAX_VALUE : bucket;
-
-            long tailId = PageUtils.getLong(pageAddr, off + 2);
-            assert tailId != 0;
-
-            GridLongList list = res.get(bucket);
-
-            if (list == null)
-                res.put(bucket, list = new GridLongList());
-
-            list.add(tailId);
-
-            off += ITEM_SIZE;
-        }
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @return Maximum number of items which can be stored in buffer.
-     */
-    private int getCapacity(int pageSize, long pageAddr) {
-        return (pageSize - ITEMS_OFF) / ITEM_SIZE;
-    }
-
-    /**
-     * @param idx Item index.
-     * @return Item offset.
-     */
-    private int offset(int idx) {
-        return ITEMS_OFF + ITEM_SIZE * idx;
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/6bf5ce46/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListNodeIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListNodeIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListNodeIO.java
deleted file mode 100644
index 6bd0532..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/PagesListNodeIO.java
+++ /dev/null
@@ -1,231 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.ignite.internal.processors.cache.database.freelist.io;
-
-import org.apache.ignite.internal.pagemem.PageUtils;
-import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions;
-import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO;
-
-import static org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler.copyMemory;
-
-/**
- * TODO optimize: now we have slow {@link #removePage(long, long)}
- */
-public class PagesListNodeIO extends PageIO {
-    /** */
-    public static final IOVersions<PagesListNodeIO> VERSIONS = new IOVersions<>(
-        new PagesListNodeIO(1)
-    );
-
-    /** */
-    private static final int PREV_PAGE_ID_OFF = COMMON_HEADER_END;
-
-    /** */
-    private static final int NEXT_PAGE_ID_OFF = PREV_PAGE_ID_OFF + 8;
-
-    /** */
-    private static final int CNT_OFF = NEXT_PAGE_ID_OFF + 8;
-
-    /** */
-    private static final int PAGE_IDS_OFF = CNT_OFF + 2;
-
-    /**
-     * @param ver  Page format version.
-     */
-    protected PagesListNodeIO(int ver) {
-        super(T_PAGE_LIST_NODE, ver);
-    }
-
-    /** {@inheritDoc} */
-    @Override public void initNewPage(long pageAddr, long pageId, int pageSize) {
-        super.initNewPage(pageAddr, pageId, pageSize);
-
-        setEmpty(pageAddr);
-
-        setPreviousId(pageAddr, 0L);
-        setNextId(pageAddr, 0L);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     */
-    private void setEmpty(long pageAddr) {
-        setCount(pageAddr, 0);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @return Next page ID.
-     */
-    public long getNextId(long pageAddr) {
-        return PageUtils.getLong(pageAddr, NEXT_PAGE_ID_OFF);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @param nextId Next page ID.
-     */
-    public void setNextId(long pageAddr, long nextId) {
-        PageUtils.putLong(pageAddr, NEXT_PAGE_ID_OFF, nextId);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @return Previous page ID.
-     */
-    public long getPreviousId(long pageAddr) {
-        return PageUtils.getLong(pageAddr, PREV_PAGE_ID_OFF);
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @param prevId Previous  page ID.
-     */
-    public void setPreviousId(long pageAddr, long prevId) {
-        PageUtils.putLong(pageAddr, PREV_PAGE_ID_OFF, prevId);
-    }
-
-    /**
-     * Gets total count of entries in this page. Does not change the buffer state.
-     *
-     * @param pageAddr Page address to get count from.
-     * @return Total number of entries.
-     */
-    public int getCount(long pageAddr) {
-        return PageUtils.getShort(pageAddr, CNT_OFF);
-    }
-
-    /**
-     * Sets total count of entries in this page. Does not change the buffer state.
-     *
-     * @param pageAddr Page address to write to.
-     * @param cnt Count.
-     */
-    private void setCount(long pageAddr, int cnt) {
-        assert cnt >= 0 && cnt <= Short.MAX_VALUE : cnt;
-
-        PageUtils.putShort(pageAddr, CNT_OFF, (short)cnt);
-    }
-
-    /**
-     * Gets capacity of this page in items.
-     *
-     * @param pageSize Page size.
-     * @return Capacity of this page in items.
-     */
-    private int getCapacity(int pageSize) {
-        return (pageSize - PAGE_IDS_OFF) >>> 3; // /8
-    }
-
-    /**
-     * @param idx Item index.
-     * @return Item offset.
-     */
-    private int offset(int idx) {
-        return PAGE_IDS_OFF + 8 * idx;
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @param idx Item index.
-     * @return Item at the given index.
-     */
-    private long getAt(long pageAddr, int idx) {
-        return PageUtils.getLong(pageAddr, offset(idx));
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @param idx Item index.
-     * @param pageId Item value to write.
-     */
-    private void setAt(long pageAddr, int idx, long pageId) {
-        PageUtils.putLong(pageAddr, offset(idx), pageId);
-    }
-
-    /**
-     * Adds page to the end of pages list.
-     *
-     * @param pageAddr Page address.
-     * @param pageId Page ID.
-     * @param pageSize Page size.
-     * @return Total number of items in this page.
-     */
-    public int addPage(long pageAddr, long pageId, int pageSize) {
-        int cnt = getCount(pageAddr);
-
-        if (cnt == getCapacity(pageSize))
-            return -1;
-
-        setAt(pageAddr, cnt, pageId);
-        setCount(pageAddr, cnt + 1);
-
-        return cnt;
-    }
-
-    /**
-     * Removes any page from the pages list.
-     *
-     * @param pageAddr Page address.
-     * @return Removed page ID.
-     */
-    public long takeAnyPage(long pageAddr) {
-        int cnt = getCount(pageAddr);
-
-        if (cnt == 0)
-            return 0L;
-
-        setCount(pageAddr, --cnt);
-
-        return getAt(pageAddr, cnt);
-    }
-
-    /**
-     * Removes the given page ID from the pages list.
-     *
-     * @param pageAddr Page address.
-     * @param dataPageId Page ID to remove.
-     * @return {@code true} if page was in the list and was removed, {@code false} otherwise.
-     */
-    public boolean removePage(long pageAddr, long dataPageId) {
-        assert dataPageId != 0;
-
-        int cnt = getCount(pageAddr);
-
-        for (int i = 0; i < cnt; i++) {
-            if (getAt(pageAddr, i) == dataPageId) {
-                if (i != cnt - 1)
-                    copyMemory(pageAddr, pageAddr, offset(i + 1), offset(i), 8 * (cnt - i - 1));
-
-                setCount(pageAddr, cnt - 1);
-
-                return true;
-            }
-        }
-
-        return false;
-    }
-
-    /**
-     * @param pageAddr Page address.
-     * @return {@code True} if there are no items in this page.
-     */
-    public boolean isEmpty(long pageAddr) {
-        return getCount(pageAddr) == 0;
-    }
-}