ignite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sboi...@apache.org
Subject [36/50] [abbrv] ignite git commit: ignite-db - move to indexing
Date Tue, 19 Apr 2016 12:58:53 GMT
ignite-db - move to indexing


Project: http://git-wip-us.apache.org/repos/asf/ignite/repo
Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/638458e2
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/638458e2
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/638458e2

Branch: refs/heads/ignite-db-x-10884
Commit: 638458e285c8332804fb3dbc221551dfe39df5ab
Parents: 481b508
Author: S.Vladykin <svladykin@gridgain.com>
Authored: Thu Apr 14 02:23:19 2016 +0300
Committer: S.Vladykin <svladykin@gridgain.com>
Committed: Thu Apr 14 02:23:19 2016 +0300

----------------------------------------------------------------------
 .../cache/database/freelist/FreeItem.java       |  90 -------------
 .../cache/database/freelist/FreeList.java       | 109 ---------------
 .../cache/database/freelist/FreeTree.java       | 131 -------------------
 .../cache/database/freelist/io/FreeIO.java      |  39 ------
 .../cache/database/freelist/io/FreeInnerIO.java |  67 ----------
 .../cache/database/freelist/io/FreeLeafIO.java  |  72 ----------
 .../query/h2/database/freelist/FreeItem.java    |  90 +++++++++++++
 .../query/h2/database/freelist/FreeList.java    | 109 +++++++++++++++
 .../query/h2/database/freelist/FreeTree.java    | 131 +++++++++++++++++++
 .../query/h2/database/freelist/io/FreeIO.java   |  39 ++++++
 .../h2/database/freelist/io/FreeInnerIO.java    |  67 ++++++++++
 .../h2/database/freelist/io/FreeLeafIO.java     |  72 ++++++++++
 12 files changed, 508 insertions(+), 508 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeItem.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeItem.java
b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeItem.java
deleted file mode 100644
index 7de30c7..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeItem.java
+++ /dev/null
@@ -1,90 +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 org.apache.ignite.internal.pagemem.FullPageId;
-
-/**
- * Free list item.
- */
-public class FreeItem extends FullPageId {
-    /** */
-    private short freeSpace;
-
-    /** */
-    private short dispersion;
-
-    /**
-     * @param freeSpace Free space.
-     * @param dispersion Dispersion.
-     * @param pageId  Page ID.
-     * @param cacheId Cache ID.
-     */
-    public FreeItem(short freeSpace, short dispersion, long pageId, int cacheId) {
-        super(pageId, cacheId);
-
-        assert freeSpace >= 0: freeSpace;
-
-        this.freeSpace = freeSpace;
-        this.dispersion = dispersion;
-    }
-
-    /**
-     * @param freeSpace Free space.
-     * @param dispersion Dispersion.
-     * @return Dispersed free space.
-     */
-    public static int disperse(int freeSpace, int dispersion) {
-        return (freeSpace << 16) | dispersion;
-    }
-
-    /**
-     * @return Dispersed free space.
-     */
-    public int dispersedFreeSpace() {
-        return disperse(freeSpace, dispersion);
-    }
-
-    /**
-     * @return Free space in the page.
-     */
-    public short freeSpace() {
-        return freeSpace;
-    }
-
-    /**
-     * @param freeSpace Free space.
-     */
-    public void freeSpace(short freeSpace) {
-        this.freeSpace = freeSpace;
-    }
-
-    /**
-     * @return Dispersion.
-     */
-    public short dispersion() {
-        return dispersion;
-    }
-
-    /**
-     * @param dispersion Dispersion.
-     */
-    public void dispersion(short dispersion) {
-        this.dispersion = dispersion;
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java
b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java
deleted file mode 100644
index c7f58c0..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java
+++ /dev/null
@@ -1,109 +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.ThreadLocalRandom;
-import org.apache.ignite.IgniteCheckedException;
-import org.apache.ignite.internal.pagemem.FullPageId;
-import org.apache.ignite.internal.pagemem.PageMemory;
-import org.apache.ignite.internal.processors.cache.GridCacheContext;
-import org.apache.ignite.internal.util.future.GridFutureAdapter;
-import org.apache.ignite.lang.IgniteBiTuple;
-import org.jsr166.ConcurrentHashMap8;
-
-/**
- * Free data page list.
- */
-public class FreeList {
-    /** */
-    private final GridCacheContext<?,?> cctx;
-
-    /** */
-    private final PageMemory pageMem;
-
-    /** */
-    private final ConcurrentHashMap8<Integer,GridFutureAdapter<FreeTree>> trees
= new ConcurrentHashMap8<>();
-
-    /**
-     * @param cctx Cache context.
-     */
-    public FreeList(GridCacheContext<?,?> cctx) {
-        assert cctx != null;
-
-        this.cctx = cctx;
-
-        pageMem = cctx.shared().database().pageMemory();
-
-        assert pageMem != null;
-    }
-
-    /**
-     * @param part Partition.
-     * @param neededSpace Needed free space.
-     * @return Page ID or {@code null} if it was impossible to find one.
-     * @throws IgniteCheckedException If failed.
-     */
-    public FullPageId take(int part, short neededSpace) throws IgniteCheckedException {
-        assert part >= 0: part;
-        assert neededSpace > 0 && neededSpace < Short.MAX_VALUE: neededSpace;
-
-        FreeTree tree = tree(part);
-
-        assert tree != null;
-
-        FreeItem res = tree.removeCeil(new FreeItem(neededSpace, dispersion(), 0, 0));
-
-        assert res == null || (res.pageId() != 0 && res.cacheId() == cctx.cacheId()):
res;
-
-        return res;
-    }
-
-    /**
-     * @return Random dispersion value.
-     */
-    private static short dispersion() {
-        return (short)ThreadLocalRandom.current().nextInt(Short.MIN_VALUE, Short.MAX_VALUE);
-    }
-
-    /**
-     * @param part Partition.
-     * @return Tree.
-     * @throws IgniteCheckedException If failed.
-     */
-    private FreeTree tree(Integer part) throws IgniteCheckedException {
-        GridFutureAdapter<FreeTree> fut = trees.get(part);
-
-        if (fut != null) {
-            fut = new GridFutureAdapter<>();
-
-            if (trees.putIfAbsent(part, fut) != null)
-                fut = trees.get(part);
-            else {
-                // Index name will be the same across restarts.
-                String idxName = part + "$$" + cctx.cacheId() + "_free";
-
-                IgniteBiTuple<FullPageId,Boolean> t = cctx.shared().database().meta()
-                    .getOrAllocateForIndex(cctx.cacheId(), idxName);
-
-                fut.onDone(new FreeTree(pageMem, cctx.cacheId(), part, t.get1(), t.get2()));
-            }
-        }
-
-        return fut.get();
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java
b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java
deleted file mode 100644
index 5011363..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java
+++ /dev/null
@@ -1,131 +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.nio.ByteBuffer;
-import org.apache.ignite.IgniteCheckedException;
-import org.apache.ignite.internal.pagemem.FullPageId;
-import org.apache.ignite.internal.pagemem.Page;
-import org.apache.ignite.internal.pagemem.PageIdAllocator;
-import org.apache.ignite.internal.pagemem.PageMemory;
-import org.apache.ignite.internal.processors.cache.database.freelist.io.FreeIO;
-import org.apache.ignite.internal.processors.cache.database.freelist.io.FreeInnerIO;
-import org.apache.ignite.internal.processors.cache.database.freelist.io.FreeLeafIO;
-import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree;
-import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusInnerIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO;
-
-/**
- * Data structure for data pages and their free spaces.
- */
-public class FreeTree extends BPlusTree<FreeItem, FreeItem> {
-    /** */
-    private PageMemory pageMem;
-
-    /** */
-    private int cacheId;
-
-    /** */
-    private int part;
-
-    /**
-     * @param pageMem Page memory.
-     * @param cacheId Cache ID.
-     * @param part Partition.
-     * @param metaPageId Meta page ID.
-     * @param initNew    Initialize new index.
-     * @throws IgniteCheckedException If failed.
-     */
-    public FreeTree(PageMemory pageMem, int cacheId, int part, FullPageId metaPageId, boolean
initNew)
-        throws IgniteCheckedException {
-        super(metaPageId);
-
-        assert pageMem != null;
-
-        this.pageMem = pageMem;
-        this.cacheId = cacheId;
-        this.part = part;
-
-        if (initNew)
-            initNew();
-    }
-
-    /** {@inheritDoc} */
-    @Override protected BPlusIO<FreeItem> io(int type, int ver) {
-        if (type == PageIO.T_FREE_INNER)
-            return FreeInnerIO.VERSIONS.forVersion(ver);
-
-        assert type == PageIO.T_FREE_LEAF: type;
-
-        return FreeLeafIO.VERSIONS.forVersion(ver);
-    }
-
-    /** {@inheritDoc} */
-    @Override protected BPlusInnerIO<FreeItem> latestInnerIO() {
-        return FreeInnerIO.VERSIONS.latest();
-    }
-
-    /** {@inheritDoc} */
-    @Override protected BPlusLeafIO<FreeItem> latestLeafIO() {
-        return FreeLeafIO.VERSIONS.latest();
-    }
-
-    /** {@inheritDoc} */
-    @Override protected int compare(BPlusIO<FreeItem> io, ByteBuffer buf, int idx,
FreeItem row)
-        throws IgniteCheckedException {
-        if (io.isLeaf()) // In a leaf we can do a fair compare.
-            return Short.compare(((FreeIO)io).freeSpace(buf, idx), row.freeSpace());
-
-        // In inner pages we do compare on dispersed free space to avoid contention on a
single page
-        // when all the entries are equal and many pages have the same free space.
-        return Integer.compare(((FreeIO)io).dispersedFreeSpace(buf, idx), row.dispersedFreeSpace());
-    }
-
-    /** {@inheritDoc} */
-    @Override protected FreeItem getRow(BPlusIO<FreeItem> io, ByteBuffer buf, int idx)
throws IgniteCheckedException {
-        assert io.isLeaf();
-
-        FreeItem row = io.getLookupRow(this, buf, idx);
-
-        assert row.pageId() != 0;
-        assert row.cacheId() == cacheId;
-
-        return row;
-    }
-
-    /** {@inheritDoc} */
-    @Override protected Page page(long pageId) throws IgniteCheckedException {
-        return pageMem.page(new FullPageId(pageId, cacheId));
-    }
-
-    /** {@inheritDoc} */
-    @Override protected Page allocatePage() throws IgniteCheckedException {
-        FullPageId pageId = pageMem.allocatePage(cacheId, part, PageIdAllocator.FLAG_IDX);
-
-        return pageMem.page(pageId);
-    }
-
-    /**
-     * @return Cache ID.
-     */
-    public int cacheId() {
-        return cacheId;
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeIO.java
b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeIO.java
deleted file mode 100644
index de28b22..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeIO.java
+++ /dev/null
@@ -1,39 +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.nio.ByteBuffer;
-
-/**
- * Common routines for free list pages.
- */
-public interface FreeIO {
-    /**
-     * @param buf Buffer.
-     * @param idx Index.
-     * @return Dispersed free space.
-     */
-    public int dispersedFreeSpace(ByteBuffer buf, int idx);
-
-    /**
-     * @param buf Buffer.
-     * @param idx Index.
-     * @return Free space.
-     */
-    public short freeSpace(ByteBuffer buf, int idx);
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java
b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java
deleted file mode 100644
index bfaaaa2..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java
+++ /dev/null
@@ -1,67 +0,0 @@
-package org.apache.ignite.internal.processors.cache.database.freelist.io;
-
-import java.nio.ByteBuffer;
-import org.apache.ignite.internal.processors.cache.database.freelist.FreeItem;
-import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree;
-import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusInnerIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions;
-
-/**
- * Routines for free list inner pages.
- */
-public class FreeInnerIO extends BPlusInnerIO<FreeItem> implements FreeIO {
-    /** */
-    public static final IOVersions<FreeInnerIO> VERSIONS = new IOVersions<>(
-        new FreeInnerIO(1)
-    );
-
-    /**
-     * @param ver Page format version.
-     */
-    protected FreeInnerIO(int ver) {
-        super(T_FREE_INNER, ver, false, 4); // freeSpace(2) + dispersion(2)
-    }
-
-    /** {@inheritDoc} */
-    @Override public void store(ByteBuffer buf, int idx, FreeItem row) {
-        store(buf, idx, row.dispersedFreeSpace());
-    }
-
-    /** {@inheritDoc} */
-    @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<FreeItem> srcIo,
ByteBuffer src, int srcIdx) {
-        store(dst, dstIdx, ((FreeIO)srcIo).dispersedFreeSpace(src, srcIdx));
-    }
-
-    /**
-     * @param buf Buffer.
-     * @param idx Index.
-     * @param dispersedFreeSpace Dispersed free space.
-     */
-    private void store(ByteBuffer buf, int idx, int dispersedFreeSpace) {
-        int off = offset(idx, SHIFT_LINK);
-
-        buf.putInt(off, dispersedFreeSpace);
-    }
-
-    /** {@inheritDoc} */
-    @Override public int dispersedFreeSpace(ByteBuffer buf, int idx) {
-        int off = offset(idx, SHIFT_LINK);
-
-        return buf.getInt(off);
-    }
-
-    /** {@inheritDoc} */
-    @Override public short freeSpace(ByteBuffer buf, int idx) {
-        int off = offset(idx, SHIFT_LINK);
-
-        return buf.getShort(off);
-    }
-
-    /** {@inheritDoc} */
-    @Override public FreeItem getLookupRow(BPlusTree<FreeItem, ?> tree, ByteBuffer
buf, int idx) {
-        int off = offset(idx, SHIFT_LINK);
-
-        return new FreeItem(buf.getShort(off), buf.getShort(off + 2), 0, 0);
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java
b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java
deleted file mode 100644
index 4062800..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java
+++ /dev/null
@@ -1,72 +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.nio.ByteBuffer;
-import org.apache.ignite.internal.processors.cache.database.freelist.FreeItem;
-import org.apache.ignite.internal.processors.cache.database.freelist.FreeTree;
-import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree;
-import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO;
-import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions;
-
-/**
- * Routines for free list leaf pages.
- */
-public class FreeLeafIO extends BPlusLeafIO<FreeItem> implements FreeIO {
-    /** */
-    public static final IOVersions<FreeLeafIO> VERSIONS = new IOVersions<>(
-        new FreeLeafIO(1)
-    );
-
-    /**
-     * @param ver Page format version.
-     */
-    protected FreeLeafIO(int ver) {
-        super(T_FREE_LEAF, ver, 12); // freeSpace(2) + dispersion(2) + pageId(8)
-    }
-
-    /** {@inheritDoc} */
-    @Override public final void store(ByteBuffer buf, int idx, FreeItem row) {
-        int off = offset(idx);
-
-        buf.putInt(off, row.dispersedFreeSpace());
-        buf.putLong(off + 4, row.pageId());
-    }
-
-    /** {@inheritDoc} */
-    @Override public int dispersedFreeSpace(ByteBuffer buf, int idx) {
-        int off = offset(idx);
-
-        return buf.getInt(off);
-    }
-
-    /** {@inheritDoc} */
-    @Override public short freeSpace(ByteBuffer buf, int idx) {
-        int off = offset(idx);
-
-        return buf.getShort(off);
-    }
-
-    /** {@inheritDoc} */
-    @Override public FreeItem getLookupRow(BPlusTree<FreeItem, ?> tree, ByteBuffer
buf, int idx) {
-        int off = offset(idx);
-
-        return new FreeItem(buf.getShort(off), buf.getShort(off + 2), buf.getLong(off + 4),
-            ((FreeTree)tree).cacheId());
-    }
-}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeItem.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeItem.java
b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeItem.java
new file mode 100644
index 0000000..71bb32e
--- /dev/null
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeItem.java
@@ -0,0 +1,90 @@
+/*
+ * 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.query.h2.database.freelist;
+
+import org.apache.ignite.internal.pagemem.FullPageId;
+
+/**
+ * Free list item.
+ */
+public class FreeItem extends FullPageId {
+    /** */
+    private short freeSpace;
+
+    /** */
+    private short dispersion;
+
+    /**
+     * @param freeSpace Free space.
+     * @param dispersion Dispersion.
+     * @param pageId  Page ID.
+     * @param cacheId Cache ID.
+     */
+    public FreeItem(short freeSpace, short dispersion, long pageId, int cacheId) {
+        super(pageId, cacheId);
+
+        assert freeSpace >= 0: freeSpace;
+
+        this.freeSpace = freeSpace;
+        this.dispersion = dispersion;
+    }
+
+    /**
+     * @param freeSpace Free space.
+     * @param dispersion Dispersion.
+     * @return Dispersed free space.
+     */
+    public static int disperse(int freeSpace, int dispersion) {
+        return (freeSpace << 16) | dispersion;
+    }
+
+    /**
+     * @return Dispersed free space.
+     */
+    public int dispersedFreeSpace() {
+        return disperse(freeSpace, dispersion);
+    }
+
+    /**
+     * @return Free space in the page.
+     */
+    public short freeSpace() {
+        return freeSpace;
+    }
+
+    /**
+     * @param freeSpace Free space.
+     */
+    public void freeSpace(short freeSpace) {
+        this.freeSpace = freeSpace;
+    }
+
+    /**
+     * @return Dispersion.
+     */
+    public short dispersion() {
+        return dispersion;
+    }
+
+    /**
+     * @param dispersion Dispersion.
+     */
+    public void dispersion(short dispersion) {
+        this.dispersion = dispersion;
+    }
+}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeList.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeList.java
b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeList.java
new file mode 100644
index 0000000..4fc7629
--- /dev/null
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeList.java
@@ -0,0 +1,109 @@
+/*
+ * 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.query.h2.database.freelist;
+
+import java.util.concurrent.ThreadLocalRandom;
+import org.apache.ignite.IgniteCheckedException;
+import org.apache.ignite.internal.pagemem.FullPageId;
+import org.apache.ignite.internal.pagemem.PageMemory;
+import org.apache.ignite.internal.processors.cache.GridCacheContext;
+import org.apache.ignite.internal.util.future.GridFutureAdapter;
+import org.apache.ignite.lang.IgniteBiTuple;
+import org.jsr166.ConcurrentHashMap8;
+
+/**
+ * Free data page list.
+ */
+public class FreeList {
+    /** */
+    private final GridCacheContext<?,?> cctx;
+
+    /** */
+    private final PageMemory pageMem;
+
+    /** */
+    private final ConcurrentHashMap8<Integer,GridFutureAdapter<FreeTree>> trees
= new ConcurrentHashMap8<>();
+
+    /**
+     * @param cctx Cache context.
+     */
+    public FreeList(GridCacheContext<?,?> cctx) {
+        assert cctx != null;
+
+        this.cctx = cctx;
+
+        pageMem = cctx.shared().database().pageMemory();
+
+        assert pageMem != null;
+    }
+
+    /**
+     * @param part Partition.
+     * @param neededSpace Needed free space.
+     * @return Page ID or {@code null} if it was impossible to find one.
+     * @throws IgniteCheckedException If failed.
+     */
+    public FullPageId take(int part, short neededSpace) throws IgniteCheckedException {
+        assert part >= 0: part;
+        assert neededSpace > 0 && neededSpace < Short.MAX_VALUE: neededSpace;
+
+        FreeTree tree = tree(part);
+
+        assert tree != null;
+
+        FreeItem res = tree.removeCeil(new FreeItem(neededSpace, dispersion(), 0, 0));
+
+        assert res == null || (res.pageId() != 0 && res.cacheId() == cctx.cacheId()):
res;
+
+        return res;
+    }
+
+    /**
+     * @return Random dispersion value.
+     */
+    private static short dispersion() {
+        return (short)ThreadLocalRandom.current().nextInt(Short.MIN_VALUE, Short.MAX_VALUE);
+    }
+
+    /**
+     * @param part Partition.
+     * @return Tree.
+     * @throws IgniteCheckedException If failed.
+     */
+    private FreeTree tree(Integer part) throws IgniteCheckedException {
+        GridFutureAdapter<FreeTree> fut = trees.get(part);
+
+        if (fut != null) {
+            fut = new GridFutureAdapter<>();
+
+            if (trees.putIfAbsent(part, fut) != null)
+                fut = trees.get(part);
+            else {
+                // Index name will be the same across restarts.
+                String idxName = part + "$$" + cctx.cacheId() + "_free";
+
+                IgniteBiTuple<FullPageId,Boolean> t = cctx.shared().database().meta()
+                    .getOrAllocateForIndex(cctx.cacheId(), idxName);
+
+                fut.onDone(new FreeTree(pageMem, cctx.cacheId(), part, t.get1(), t.get2()));
+            }
+        }
+
+        return fut.get();
+    }
+}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java
b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java
new file mode 100644
index 0000000..a8a836b
--- /dev/null
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java
@@ -0,0 +1,131 @@
+/*
+ * 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.query.h2.database.freelist;
+
+import java.nio.ByteBuffer;
+import org.apache.ignite.IgniteCheckedException;
+import org.apache.ignite.internal.pagemem.FullPageId;
+import org.apache.ignite.internal.pagemem.Page;
+import org.apache.ignite.internal.pagemem.PageIdAllocator;
+import org.apache.ignite.internal.pagemem.PageMemory;
+import org.apache.ignite.internal.processors.query.h2.database.freelist.io.FreeIO;
+import org.apache.ignite.internal.processors.query.h2.database.freelist.io.FreeInnerIO;
+import org.apache.ignite.internal.processors.query.h2.database.freelist.io.FreeLeafIO;
+import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree;
+import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO;
+import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusInnerIO;
+import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO;
+import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO;
+
+/**
+ * Data structure for data pages and their free spaces.
+ */
+public class FreeTree extends BPlusTree<FreeItem, FreeItem> {
+    /** */
+    private PageMemory pageMem;
+
+    /** */
+    private int cacheId;
+
+    /** */
+    private int part;
+
+    /**
+     * @param pageMem Page memory.
+     * @param cacheId Cache ID.
+     * @param part Partition.
+     * @param metaPageId Meta page ID.
+     * @param initNew    Initialize new index.
+     * @throws IgniteCheckedException If failed.
+     */
+    public FreeTree(PageMemory pageMem, int cacheId, int part, FullPageId metaPageId, boolean
initNew)
+        throws IgniteCheckedException {
+        super(metaPageId);
+
+        assert pageMem != null;
+
+        this.pageMem = pageMem;
+        this.cacheId = cacheId;
+        this.part = part;
+
+        if (initNew)
+            initNew();
+    }
+
+    /** {@inheritDoc} */
+    @Override protected BPlusIO<FreeItem> io(int type, int ver) {
+        if (type == PageIO.T_FREE_INNER)
+            return FreeInnerIO.VERSIONS.forVersion(ver);
+
+        assert type == PageIO.T_FREE_LEAF: type;
+
+        return FreeLeafIO.VERSIONS.forVersion(ver);
+    }
+
+    /** {@inheritDoc} */
+    @Override protected BPlusInnerIO<FreeItem> latestInnerIO() {
+        return FreeInnerIO.VERSIONS.latest();
+    }
+
+    /** {@inheritDoc} */
+    @Override protected BPlusLeafIO<FreeItem> latestLeafIO() {
+        return FreeLeafIO.VERSIONS.latest();
+    }
+
+    /** {@inheritDoc} */
+    @Override protected int compare(BPlusIO<FreeItem> io, ByteBuffer buf, int idx,
FreeItem row)
+        throws IgniteCheckedException {
+        if (io.isLeaf()) // In a leaf we can do a fair compare.
+            return Short.compare(((FreeIO)io).freeSpace(buf, idx), row.freeSpace());
+
+        // In inner pages we do compare on dispersed free space to avoid contention on a
single page
+        // when all the entries are equal and many pages have the same free space.
+        return Integer.compare(((FreeIO)io).dispersedFreeSpace(buf, idx), row.dispersedFreeSpace());
+    }
+
+    /** {@inheritDoc} */
+    @Override protected FreeItem getRow(BPlusIO<FreeItem> io, ByteBuffer buf, int idx)
throws IgniteCheckedException {
+        assert io.isLeaf();
+
+        FreeItem row = io.getLookupRow(this, buf, idx);
+
+        assert row.pageId() != 0;
+        assert row.cacheId() == cacheId;
+
+        return row;
+    }
+
+    /** {@inheritDoc} */
+    @Override protected Page page(long pageId) throws IgniteCheckedException {
+        return pageMem.page(new FullPageId(pageId, cacheId));
+    }
+
+    /** {@inheritDoc} */
+    @Override protected Page allocatePage() throws IgniteCheckedException {
+        FullPageId pageId = pageMem.allocatePage(cacheId, part, PageIdAllocator.FLAG_IDX);
+
+        return pageMem.page(pageId);
+    }
+
+    /**
+     * @return Cache ID.
+     */
+    public int cacheId() {
+        return cacheId;
+    }
+}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeIO.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeIO.java
b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeIO.java
new file mode 100644
index 0000000..5af351c
--- /dev/null
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeIO.java
@@ -0,0 +1,39 @@
+/*
+ * 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.query.h2.database.freelist.io;
+
+import java.nio.ByteBuffer;
+
+/**
+ * Common routines for free list pages.
+ */
+public interface FreeIO {
+    /**
+     * @param buf Buffer.
+     * @param idx Index.
+     * @return Dispersed free space.
+     */
+    public int dispersedFreeSpace(ByteBuffer buf, int idx);
+
+    /**
+     * @param buf Buffer.
+     * @param idx Index.
+     * @return Free space.
+     */
+    public short freeSpace(ByteBuffer buf, int idx);
+}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeInnerIO.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeInnerIO.java
b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeInnerIO.java
new file mode 100644
index 0000000..b8a3872
--- /dev/null
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeInnerIO.java
@@ -0,0 +1,67 @@
+package org.apache.ignite.internal.processors.query.h2.database.freelist.io;
+
+import java.nio.ByteBuffer;
+import org.apache.ignite.internal.processors.query.h2.database.freelist.FreeItem;
+import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree;
+import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO;
+import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusInnerIO;
+import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions;
+
+/**
+ * Routines for free list inner pages.
+ */
+public class FreeInnerIO extends BPlusInnerIO<FreeItem> implements FreeIO {
+    /** */
+    public static final IOVersions<FreeInnerIO> VERSIONS = new IOVersions<>(
+        new FreeInnerIO(1)
+    );
+
+    /**
+     * @param ver Page format version.
+     */
+    protected FreeInnerIO(int ver) {
+        super(T_FREE_INNER, ver, false, 4); // freeSpace(2) + dispersion(2)
+    }
+
+    /** {@inheritDoc} */
+    @Override public void store(ByteBuffer buf, int idx, FreeItem row) {
+        store(buf, idx, row.dispersedFreeSpace());
+    }
+
+    /** {@inheritDoc} */
+    @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<FreeItem> srcIo,
ByteBuffer src, int srcIdx) {
+        store(dst, dstIdx, ((FreeIO)srcIo).dispersedFreeSpace(src, srcIdx));
+    }
+
+    /**
+     * @param buf Buffer.
+     * @param idx Index.
+     * @param dispersedFreeSpace Dispersed free space.
+     */
+    private void store(ByteBuffer buf, int idx, int dispersedFreeSpace) {
+        int off = offset(idx, SHIFT_LINK);
+
+        buf.putInt(off, dispersedFreeSpace);
+    }
+
+    /** {@inheritDoc} */
+    @Override public int dispersedFreeSpace(ByteBuffer buf, int idx) {
+        int off = offset(idx, SHIFT_LINK);
+
+        return buf.getInt(off);
+    }
+
+    /** {@inheritDoc} */
+    @Override public short freeSpace(ByteBuffer buf, int idx) {
+        int off = offset(idx, SHIFT_LINK);
+
+        return buf.getShort(off);
+    }
+
+    /** {@inheritDoc} */
+    @Override public FreeItem getLookupRow(BPlusTree<FreeItem, ?> tree, ByteBuffer
buf, int idx) {
+        int off = offset(idx, SHIFT_LINK);
+
+        return new FreeItem(buf.getShort(off), buf.getShort(off + 2), 0, 0);
+    }
+}

http://git-wip-us.apache.org/repos/asf/ignite/blob/638458e2/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java
----------------------------------------------------------------------
diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java
b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java
new file mode 100644
index 0000000..4c6babe
--- /dev/null
+++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java
@@ -0,0 +1,72 @@
+/*
+ * 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.query.h2.database.freelist.io;
+
+import java.nio.ByteBuffer;
+import org.apache.ignite.internal.processors.query.h2.database.freelist.FreeItem;
+import org.apache.ignite.internal.processors.query.h2.database.freelist.FreeTree;
+import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree;
+import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO;
+import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions;
+
+/**
+ * Routines for free list leaf pages.
+ */
+public class FreeLeafIO extends BPlusLeafIO<FreeItem> implements FreeIO {
+    /** */
+    public static final IOVersions<FreeLeafIO> VERSIONS = new IOVersions<>(
+        new FreeLeafIO(1)
+    );
+
+    /**
+     * @param ver Page format version.
+     */
+    protected FreeLeafIO(int ver) {
+        super(T_FREE_LEAF, ver, 12); // freeSpace(2) + dispersion(2) + pageId(8)
+    }
+
+    /** {@inheritDoc} */
+    @Override public final void store(ByteBuffer buf, int idx, FreeItem row) {
+        int off = offset(idx);
+
+        buf.putInt(off, row.dispersedFreeSpace());
+        buf.putLong(off + 4, row.pageId());
+    }
+
+    /** {@inheritDoc} */
+    @Override public int dispersedFreeSpace(ByteBuffer buf, int idx) {
+        int off = offset(idx);
+
+        return buf.getInt(off);
+    }
+
+    /** {@inheritDoc} */
+    @Override public short freeSpace(ByteBuffer buf, int idx) {
+        int off = offset(idx);
+
+        return buf.getShort(off);
+    }
+
+    /** {@inheritDoc} */
+    @Override public FreeItem getLookupRow(BPlusTree<FreeItem, ?> tree, ByteBuffer
buf, int idx) {
+        int off = offset(idx);
+
+        return new FreeItem(buf.getShort(off), buf.getShort(off + 2), buf.getLong(off + 4),
+            ((FreeTree)tree).cacheId());
+    }
+}


Mime
View raw message