You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by vo...@apache.org on 2015/11/18 14:40:04 UTC
[30/50] [abbrv] ignite git commit: IGNITE-1917: Simplifying schema.
IGNITE-1917: Simplifying schema.
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo
Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/678314fe
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/678314fe
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/678314fe
Branch: refs/heads/ignite-1917
Commit: 678314fe20112e3ffd98f8e2537519bad312a433
Parents: 8200031
Author: vozerov-gridgain <vo...@gridgain.com>
Authored: Tue Nov 17 18:13:20 2015 +0300
Committer: vozerov-gridgain <vo...@gridgain.com>
Committed: Tue Nov 17 18:13:20 2015 +0300
----------------------------------------------------------------------
.../internal/portable/PortableSchema.java | 191 ++++++++++++++++-
.../portable/PortableSchemaIntIntMap.java | 214 -------------------
2 files changed, 183 insertions(+), 222 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/ignite/blob/678314fe/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java b/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java
index f970290..7738ae5 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java
@@ -38,14 +38,23 @@ public class PortableSchema implements Externalizable {
/** Order returned if field is not found. */
public static final int ORDER_NOT_FOUND = -1;
+ /** Minimum sensible size. */
+ private static final int MAP_MIN_SIZE = 32;
+
+ /** Empty cell. */
+ private static final int MAP_EMPTY = 0;
+
/** Inline flag. */
private boolean inline;
/** IDs depending on order. */
private int[] ids;
- /** Map form field ID to order. */
- private PortableSchemaIntIntMap idToOrder;
+ /** ID-to-order data. */
+ private int[] idToOrderData;
+
+ /** ID-to-order mask. */
+ private int idToOrderMask;
/** ID 1. */
private int id0;
@@ -103,8 +112,6 @@ public class PortableSchema implements Externalizable {
id5 = iter.hasNext() ? iter.next() : 0;
id6 = iter.hasNext() ? iter.next() : 0;
id7 = iter.hasNext() ? iter.next() : 0;
-
- idToOrder = null;
}
else {
inline = false;
@@ -116,7 +123,7 @@ public class PortableSchema implements Externalizable {
for (int i = 0; i < fieldIds.size(); i++)
ids[i] = fieldIds.get(i);
- idToOrder = new PortableSchemaIntIntMap(ids);
+ initializeMap(ids);
}
}
@@ -204,8 +211,33 @@ public class PortableSchema implements Externalizable {
return ORDER_NOT_FOUND;
}
- else
- return idToOrder.get(id);
+ else {
+ int idx = (id & idToOrderMask) << 1;
+
+ int curId = idToOrderData[idx];
+
+ if (id == curId) // Hit!
+ return idToOrderData[idx + 1];
+ else if (curId == MAP_EMPTY) // No such ID!
+ return ORDER_NOT_FOUND;
+ else {
+ // Unlikely collision scenario.
+ for (int i = 2; i < idToOrderData.length; i += 2) {
+ int newIdx = (idx + i) % idToOrderData.length;
+
+ assert newIdx < idToOrderData.length - 1;
+
+ curId = idToOrderData[newIdx];
+
+ if (id == curId)
+ return idToOrderData[newIdx + 1];
+ else if (curId == MAP_EMPTY)
+ return ORDER_NOT_FOUND;
+ }
+
+ return ORDER_NOT_FOUND;
+ }
+ }
}
/** {@inheritDoc} */
@@ -270,8 +302,129 @@ public class PortableSchema implements Externalizable {
for (int i = 0; i < size; i++)
ids[i] = in.readInt();
- idToOrder = new PortableSchemaIntIntMap(ids);
+ initializeMap(ids);
+ }
+ }
+
+ /**
+ * Parse values.
+ *
+ * @param vals Values.
+ * @param size Proposed result size.
+ * @return Parse result.
+ */
+ private static ParseResult parse(int[] vals, int size) {
+ int mask = maskForPowerOfTwo(size);
+
+ int totalSize = size * 2;
+
+ int[] data = new int[totalSize];
+ int collisions = 0;
+
+ for (int order = 0; order < vals.length; order++) {
+ int id = vals[order];
+
+ assert id != 0;
+
+ int idIdx = (id & mask) << 1;
+
+ if (data[idIdx] == 0) {
+ // Found empty slot.
+ data[idIdx] = id;
+ data[idIdx + 1] = order;
+ }
+ else {
+ // Collision!
+ collisions++;
+
+ boolean placeFound = false;
+
+ for (int i = 2; i < totalSize; i += 2) {
+ int newIdIdx = (idIdx + i) % totalSize;
+
+ if (data[newIdIdx] == 0) {
+ data[newIdIdx] = id;
+ data[newIdIdx + 1] = order;
+
+ placeFound = true;
+
+ break;
+ }
+ }
+
+ assert placeFound : "Should always have a place for entry!";
+ }
}
+
+ return new ParseResult(data, collisions);
+ }
+
+ /**
+ * Get next power of two which greater or equal to the given number.
+ * This implementation is not meant to be very efficient, so it is expected to be used relatively rare.
+ *
+ * @param val Number
+ * @return Nearest pow2.
+ */
+ private static int nextPowerOfTwo(int val) {
+ int res = 1;
+
+ while (res < val)
+ res = res << 1;
+
+ if (res < 0)
+ throw new IllegalArgumentException("Value is too big to find positive pow2: " + val);
+
+ return res;
+ }
+
+ /**
+ * Calculate mask for the given value which is a power of two.
+ *
+ * @param val Value.
+ * @return Mask.
+ */
+ private static int maskForPowerOfTwo(int val) {
+ int mask = 0;
+ int comparand = 1;
+
+ while (comparand < val) {
+ mask |= comparand;
+
+ comparand <<= 1;
+ }
+
+ return mask;
+ }
+
+ /**
+ * Initialize the map.
+ *
+ * @param vals Values.
+ */
+ private void initializeMap(int[] vals) {
+ int size = Math.max(nextPowerOfTwo(vals.length) << 2, MAP_MIN_SIZE);
+
+ assert size > 0;
+
+ ParseResult finalRes;
+
+ ParseResult res1 = parse(vals, size);
+
+ if (res1.collisions == 0)
+ finalRes = res1;
+ else {
+ ParseResult res2 = parse(vals, size * 2);
+
+ // Failed to decrease aom
+ if (res2.collisions == 0)
+ finalRes = res2;
+ else
+ finalRes = parse(vals, size * 4);
+ }
+
+ idToOrderData = finalRes.data;
+ idToOrderMask = maskForPowerOfTwo(idToOrderData.length / 2);
}
/**
@@ -320,4 +473,26 @@ public class PortableSchema implements Externalizable {
return new PortableSchema(schemaId, fields);
}
}
+
+ /**
+ * Result of map parsing.
+ */
+ private static class ParseResult {
+ /** Data. */
+ private int[] data;
+
+ /** Collisions. */
+ private int collisions;
+
+ /**
+ * Constructor.
+ *
+ * @param data Data.
+ * @param collisions Collisions.
+ */
+ private ParseResult(int[] data, int collisions) {
+ this.data = data;
+ this.collisions = collisions;
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/ignite/blob/678314fe/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java b/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java
deleted file mode 100644
index 8b8f7cf..0000000
--- a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java
+++ /dev/null
@@ -1,214 +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.portable;
-
-/**
- * Map for fast access to field order by ID.
- */
-// TODO: IGNITE-1917: Inline into schema.
-public class PortableSchemaIntIntMap {
- /** Minimum sensible size. */
- private static final int MIN_SIZE = 32;
-
- /** Empty cell. */
- private static final int EMPTY = 0;
-
- /** Data. */
- private final int[] data;
-
- /** Mask for index calculation. */
- private final int mask;
-
- /**
- * Constructor.
- *
- * @param vals Values.
- */
- public PortableSchemaIntIntMap(int[] vals) {
- int size = Math.max(nextPowerOfTwo(vals.length) << 2, MIN_SIZE);
-
- assert size > 0;
-
- ParseResult finalRes;
-
- ParseResult res1 = parse(vals, size);
-
- if (res1.collisions == 0)
- finalRes = res1;
- else {
- ParseResult res2 = parse(vals, size * 2);
-
- // Failed to decrease aom
- if (res2.collisions == 0)
- finalRes = res2;
- else
- finalRes = parse(vals, size * 4);
- }
-
- data = finalRes.data;
-
- mask = maskForPowerOfTwo(data.length / 2);
- }
-
- /**
- * Get order.
- *
- * @param id ID.
- * @return Order.
- */
- public int get(int id) {
- int idx = (id & mask) << 1;
-
- int curId = data[idx];
-
- if (id == curId) // Hit!
- return data[idx + 1];
- else if (curId == EMPTY) // No such ID!
- return PortableSchema.ORDER_NOT_FOUND;
- else {
- // Unlikely collision scenario.
- for (int i = 2; i < data.length; i += 2) {
- int newIdx = (idx + i) % data.length;
-
- assert newIdx < data.length - 1;
-
- curId = data[newIdx];
-
- if (id == curId)
- return data[newIdx + 1];
- else if (curId == EMPTY)
- return PortableSchema.ORDER_NOT_FOUND;
- }
-
- return PortableSchema.ORDER_NOT_FOUND;
- }
- }
-
- /**
- * Parse values.
- *
- * @param vals Values.
- * @param size Proposed result size.
- * @return Parse result.
- */
- private static ParseResult parse(int[] vals, int size) {
- int mask = maskForPowerOfTwo(size);
-
- int totalSize = size * 2;
-
- int[] data = new int[totalSize];
- int collisions = 0;
-
- for (int order = 0; order < vals.length; order++) {
- int id = vals[order];
-
- assert id != 0;
-
- int idIdx = (id & mask) << 1;
-
- if (data[idIdx] == 0) {
- // Found empty slot.
- data[idIdx] = id;
- data[idIdx + 1] = order;
- }
- else {
- // Collision!
- collisions++;
-
- boolean placeFound = false;
-
- for (int i = 2; i < totalSize; i += 2) {
- int newIdIdx = (idIdx + i) % totalSize;
-
- if (data[newIdIdx] == 0) {
- data[newIdIdx] = id;
- data[newIdIdx + 1] = order;
-
- placeFound = true;
-
- break;
- }
- }
-
- assert placeFound : "Should always have a place for entry!";
- }
- }
-
- return new ParseResult(data, collisions);
- }
-
- /**
- * Get next power of two which greater or equal to the given number.
- * This implementation is not meant to be very efficient, so it is expected to be used relatively rare.
- *
- * @param val Number
- * @return Nearest pow2.
- */
- private static int nextPowerOfTwo(int val) {
- int res = 1;
-
- while (res < val)
- res = res << 1;
-
- if (res < 0)
- throw new IllegalArgumentException("Value is too big to find positive pow2: " + val);
-
- return res;
- }
-
- /**
- * Calculate mask for the given value which is a power of two.
- *
- * @param val Value.
- * @return Mask.
- */
- private static int maskForPowerOfTwo(int val) {
- int mask = 0;
- int comparand = 1;
-
- while (comparand < val) {
- mask |= comparand;
-
- comparand <<= 1;
- }
-
- return mask;
- }
-
- /**
- * Result of map parsing.
- */
- private static class ParseResult {
- /** Data. */
- public int[] data;
-
- /** Collisions. */
- public int collisions;
-
- /**
- * Constructor.
- *
- * @param data Data.
- * @param collisions Collisions.
- */
- public ParseResult(int[] data, int collisions) {
- this.data = data;
- this.collisions = collisions;
- }
- }
-}