You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by ji...@apache.org on 2019/06/27 09:43:18 UTC
[incubator-iotdb] branch feature_async_close_tsfile updated:
refactor TVList
This is an automated email from the ASF dual-hosted git repository.
jiangtian pushed a commit to branch feature_async_close_tsfile
in repository https://gitbox.apache.org/repos/asf/incubator-iotdb.git
The following commit(s) were added to refs/heads/feature_async_close_tsfile by this push:
new a837a63 refactor TVList
a837a63 is described below
commit a837a632326951a7836a38c981ab12d6d22e0beb
Author: 江天 <jt...@163.com>
AuthorDate: Thu Jun 27 17:41:09 2019 +0800
refactor TVList
---
.../iotdb/db/utils/datastructure/LongTVList.java | 111 ++-------------------
.../iotdb/db/utils/datastructure/TVList.java | 97 +++++++++++++++++-
2 files changed, 102 insertions(+), 106 deletions(-)
diff --git a/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java b/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java
index 14eb813..215adbe 100644
--- a/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java
+++ b/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java
@@ -111,117 +111,20 @@ public class LongTVList extends TVList {
timestamps = null;
}
- protected void merge(int lo, int mid, int hi) {
- int tmpIdx = 0;
-
- int leftIdx = lo;
- int rightIdx = mid;
-
- long leftFirstT = getTime(leftIdx);
- long leftFirstV = getLong(leftIdx);
- long rightFirstT = getTime(rightIdx);
- long rightFirstV = getLong(rightIdx);
-
- int endSide = 0;
- while (endSide == 0) {
- if (leftFirstT <= rightFirstT) {
- sortedTimestamps[lo + tmpIdx] = leftFirstT;
- sortedValues[lo + tmpIdx] = leftFirstV;
- tmpIdx ++;
- leftIdx ++;
- if (leftIdx == mid) {
- endSide = 1;
- } else {
- leftFirstT = getTime(leftIdx);
- leftFirstV = getLong(leftIdx);
- }
- } else {
- sortedTimestamps[lo + tmpIdx] = rightFirstT;
- sortedValues[lo + tmpIdx] = rightFirstV;
- tmpIdx ++;
- rightIdx ++;
- if (rightIdx == hi) {
- endSide = 2;
- } else {
- rightFirstT = getTime(rightIdx);
- rightFirstV = getLong(rightIdx);
- }
- }
- }
- if (endSide == 1) {
- for (; rightIdx < hi; rightIdx++) {
- rightFirstT = getTime(rightIdx);
- rightFirstV = getLong(rightIdx);
- sortedTimestamps[lo + tmpIdx] = rightFirstT;
- sortedValues[lo + tmpIdx] = rightFirstV;
- tmpIdx ++;
- }
- } else {
- for(; leftIdx < mid; leftIdx++) {
- leftFirstT = getTime(leftIdx);
- leftFirstV = getLong(leftIdx);
- sortedTimestamps[lo + tmpIdx] = leftFirstT;
- sortedValues[lo + tmpIdx] = leftFirstV;
- tmpIdx ++;
- }
- }
- for (int i = lo; i < hi; i++) {
- set(i, sortedTimestamps[i], sortedValues[i]);
- }
+ @Override
+ protected void setFromSorted(int src, int dest) {
+ set(dest, sortedTimestamps[src], sortedValues[src]);
}
- private void set(int src, int dest) {
+ protected void set(int src, int dest) {
long srcT = getTime(src);
long srcV = getLong(src);
set(dest, srcT, srcV);
}
- /**
- * From TimSort.java
- */
- protected void binarySort(int lo, int hi, int start) {
- assert lo <= start && start <= hi;
- if (start == lo)
- start++;
- for ( ; start < hi; start++) {
- long pivotT = getTime(start);
- long pivotV = getLong(start);
-
- // Set left (and right) to the index where a[start] (pivot) belongs
- int left = lo;
- int right = start;
- assert left <= right;
- /*
- * Invariants:
- * pivot >= all in [lo, left).
- * pivot < all in [right, start).
- */
- while (left < right) {
- int mid = (left + right) >>> 1;
- if (pivotT < getTime(mid))
- right = mid;
- else
- left = mid + 1;
- }
- assert left == right;
-
- /*
- * The invariants still hold: pivot >= all in [lo, left) and
- * pivot < all in [left, start), so pivot belongs at left. Note
- * that if there are elements equal to pivot, left points to the
- * first slot after them -- that's why this sort is stable.
- * Slide elements over to make room for pivot.
- */
- int n = start - left; // The number of elements to move
- for (int i = n; i >= 1; i--) {
- set(left + i - 1, left + i);
- }
- set(left, pivotT, pivotV);
- }
- for (int i = lo; i < hi; i++) {
- sortedTimestamps[i] = getTime(i);
- sortedValues[i] = getLong(i);
- }
+ protected void setSorted(int src, int dest) {
+ sortedTimestamps[dest] = getTime(src);
+ sortedValues[dest] = getLong(src);
}
protected void reverseRange(int lo, int hi) {
diff --git a/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/TVList.java b/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/TVList.java
index 4dc7ed0..6e6b7c4 100644
--- a/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/TVList.java
+++ b/iotdb/src/main/java/org/apache/iotdb/db/utils/datastructure/TVList.java
@@ -109,9 +109,11 @@ public abstract class TVList {
public abstract void sort();
- protected abstract void binarySort(int lo, int hi, int start);
+ protected abstract void set(int src, int dest);
- protected abstract void merge(int lo, int mid, int hi);
+ protected abstract void setFromSorted(int src, int dest);
+
+ protected abstract void setSorted(int src, int dest);
protected abstract void reverseRange(int lo, int hi);
@@ -176,4 +178,95 @@ public abstract class TVList {
public void setTimeOffset(long timeOffset) {
this.timeOffset = timeOffset;
}
+
+ protected int compare(int idx1, int idx2) {
+ long t1 = getTime(idx1);
+ long t2 = getTime(idx2);
+ return Long.compare(t1, t2);
+ }
+
+ /**
+ * From TimSort.java
+ */
+ protected void binarySort(int lo, int hi, int start) {
+ assert lo <= start && start <= hi;
+ if (start == lo)
+ start++;
+ for ( ; start < hi; start++) {
+
+ // Set left (and right) to the index where a[start] (pivot) belongs
+ int left = lo;
+ int right = start;
+ assert left <= right;
+ /*
+ * Invariants:
+ * pivot >= all in [lo, left).
+ * pivot < all in [right, start).
+ */
+ while (left < right) {
+ int mid = (left + right) >>> 1;
+ if (compare(start, mid) < 0)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ assert left == right;
+
+ /*
+ * The invariants still hold: pivot >= all in [lo, left) and
+ * pivot < all in [left, start), so pivot belongs at left. Note
+ * that if there are elements equal to pivot, left points to the
+ * first slot after them -- that's why this sort is stable.
+ * Slide elements over to make room for pivot.
+ */
+ int n = start - left; // The number of elements to move
+ for (int i = n; i >= 1; i--) {
+ set(left + i - 1, left + i);
+ }
+ set(left, start);
+ }
+ for (int i = lo; i < hi; i++) {
+ setSorted(i, i);
+ }
+ }
+
+ protected void merge(int lo, int mid, int hi) {
+ int tmpIdx = 0;
+
+ int leftIdx = lo;
+ int rightIdx = mid;
+
+ int endSide = 0;
+ while (endSide == 0) {
+ if (compare(leftIdx, rightIdx) <= 0) {
+ setSorted(leftIdx, lo + tmpIdx);
+ tmpIdx ++;
+ leftIdx ++;
+ if (leftIdx == mid) {
+ endSide = 1;
+ }
+ } else {
+ setSorted(rightIdx, lo + tmpIdx);
+ tmpIdx ++;
+ rightIdx ++;
+ if (rightIdx == hi) {
+ endSide = 2;
+ }
+ }
+ }
+ if (endSide == 1) {
+ for (; rightIdx < hi; rightIdx++) {
+ setSorted(rightIdx, lo + tmpIdx);
+ tmpIdx ++;
+ }
+ } else {
+ for(; leftIdx < mid; leftIdx++) {
+ setSorted(leftIdx, lo + tmpIdx);
+ tmpIdx ++;
+ }
+ }
+ for (int i = lo; i < hi; i++) {
+ setFromSorted(i, i);
+ }
+ }
}