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 <[email protected]> Authored: Thu Apr 14 02:23:19 2016 +0300 Committer: S.Vladykin <[email protected]> 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()); + } +}
