Return-Path: X-Original-To: apmail-ignite-commits-archive@minotaur.apache.org Delivered-To: apmail-ignite-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 264C018665 for ; Tue, 19 Apr 2016 12:58:20 +0000 (UTC) Received: (qmail 9194 invoked by uid 500); 19 Apr 2016 12:58:20 -0000 Delivered-To: apmail-ignite-commits-archive@ignite.apache.org Received: (qmail 9125 invoked by uid 500); 19 Apr 2016 12:58:20 -0000 Mailing-List: contact commits-help@ignite.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@ignite.apache.org Delivered-To: mailing list commits@ignite.apache.org Received: (qmail 8753 invoked by uid 99); 19 Apr 2016 12:58:19 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 19 Apr 2016 12:58:19 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id BA1F9DFF41; Tue, 19 Apr 2016 12:58:19 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: sboikov@apache.org To: commits@ignite.apache.org Date: Tue, 19 Apr 2016 12:58:47 -0000 Message-Id: <8901798304bd4e6b971ea8f544e4da30@git.apache.org> In-Reply-To: <4f408e32fde8498d8f180871ecbd0990@git.apache.org> References: <4f408e32fde8498d8f180871ecbd0990@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [30/50] [abbrv] ignite git commit: ignite-db - free list 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 Authored: Wed Apr 13 08:35:22 2016 +0300 Committer: S.Vladykin 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 { + /** */ + 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 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 latestInnerIO() { + return FreeInnerIO.VERSIONS.latest(); + } + + /** {@inheritDoc} */ + @Override protected BPlusLeafIO latestLeafIO() { + return FreeLeafIO.VERSIONS.latest(); + } + + /** {@inheritDoc} */ + @Override protected int compare(BPlusIO 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 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 implements FreeIO { + /** */ + public static final IOVersions 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 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 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 implements FreeIO { + /** */ + public static final IOVersions 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 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; /** */