ignite-db - free list
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/b79d594d Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/b79d594d Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/b79d594d Branch: refs/heads/ignite-db-x-10884 Commit: b79d594dab48fb0c3008a9816fb7b20d37221deb Parents: 6c9e05d Author: S.Vladykin <[email protected]> Authored: Wed Apr 13 08:35:22 2016 +0300 Committer: S.Vladykin <[email protected]> Committed: Wed Apr 13 08:35:22 2016 +0300 ---------------------------------------------------------------------- .../cache/database/freelist/FreeItem.java | 76 +++++++++++ .../cache/database/freelist/FreeTree.java | 126 +++++++++++++++++++ .../cache/database/freelist/io/FreeIO.java | 32 +++++ .../cache/database/freelist/io/FreeInnerIO.java | 60 +++++++++ .../cache/database/freelist/io/FreeLeafIO.java | 65 ++++++++++ .../cache/database/tree/io/PageIO.java | 6 + 6 files changed, 365 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/b79d594d/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 new file mode 100644 index 0000000..c682910 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeItem.java @@ -0,0 +1,76 @@ +/* + * 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; + } + + /** + * @return Dispersion. + */ + public short dispersion() { + return dispersion; + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/b79d594d/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 new file mode 100644 index 0000000..8c21c86 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java @@ -0,0 +1,126 @@ +/* + * 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 { + 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/b79d594d/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 new file mode 100644 index 0000000..bc78ad6 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeIO.java @@ -0,0 +1,32 @@ +/* + * 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); +} http://git-wip-us.apache.org/repos/asf/ignite/blob/b79d594d/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 new file mode 100644 index 0000000..248bc82 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java @@ -0,0 +1,60 @@ +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 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/b79d594d/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 new file mode 100644 index 0000000..85d7b61 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java @@ -0,0 +1,65 @@ +/* + * 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 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/b79d594d/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java index 8fc780c..01dfe1b 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java @@ -53,6 +53,12 @@ public abstract class PageIO { public static final short T_H2_REF_INNER = 4; /** */ + public static final short T_FREE_LEAF = 5; + + /** */ + public static final short T_FREE_INNER = 6; + + /** */ private final int ver; /** */
