Repository: wangguanquan/eec
Pull request #111 (2020-03-12 15:22:41)

Fix#110
修复读取SharedString字符时引起结果错位的BUG


Patch:
diff --git a/src/main/java/org/ttzero/excel/entity/SharedStringTable.java b/src/main/java/org/ttzero/excel/entity/SharedStringTable.java
index 96741dd5..ec7aaa83 100644
--- a/src/main/java/org/ttzero/excel/entity/SharedStringTable.java
+++ b/src/main/java/org/ttzero/excel/entity/SharedStringTable.java
@@ -117,11 +117,7 @@ public class SharedStringTable implements AutoCloseable, Iterable<String> {
      * @throws IOException if io error occur
      */
     public int push(char c) throws IOException {
-        if (buffer.remaining() < 4) {
-            flush();
-        }
-        buffer.putInt(~c);
-        return count++;
+        return pushChar(c);
     }
 
     /**
@@ -134,10 +130,10 @@ public class SharedStringTable implements AutoCloseable, Iterable<String> {
     public int push(String key) throws IOException {
         int len;
         if (key == null || (len = key.length()) == 0) {
-            return push((char) 0xFFFF);
+            return pushChar((char) 0xFFFF);
         }
         if (len == 1) {
-            return push(key.charAt(0));
+            return pushChar(key.charAt(0));
         }
         byte[] bytes = key.getBytes(UTF_8);
         if (buffer.remaining() < bytes.length + 4) {
@@ -148,6 +144,21 @@ public class SharedStringTable implements AutoCloseable, Iterable<String> {
         return count++;
     }
 
+    /**
+     * Write character value into table
+     *
+     * @param c the character value
+     * @return the value index of table
+     * @throws IOException if io error occur
+     */
+    private int pushChar(char c) throws IOException {
+        if (buffer.remaining() < 4) {
+            flush();
+        }
+        buffer.putInt(~c);
+        return count++;
+    }
+
     /**
      * Find character value from begging
      *
diff --git a/src/main/java/org/ttzero/excel/reader/SharedStrings.java b/src/main/java/org/ttzero/excel/reader/SharedStrings.java
index 7b987eef..a0ca0391 100644
--- a/src/main/java/org/ttzero/excel/reader/SharedStrings.java
+++ b/src/main/java/org/ttzero/excel/reader/SharedStrings.java
@@ -24,8 +24,7 @@ import java.io.BufferedReader;
 import java.io.IOException;
 import java.nio.file.Files;
 import java.nio.file.Path;
-import java.util.HashMap;
-import java.util.Map;
+import java.util.Arrays;
 
 import static org.ttzero.excel.util.StringUtil.EMPTY;
 
@@ -126,9 +125,9 @@ public class SharedStrings implements AutoCloseable {
      */
     private int limit_backward;
     /**
-     * Count the number of visits to each segment
+     * A tester of SharedString's cache
      */
-    private Map<Integer, Integer> count_area = null;
+    private Tester tester = null;
     /**
      * High frequency word
      */
@@ -156,7 +155,7 @@ public class SharedStrings implements AutoCloseable {
 
     private IndexSharedStringTable sst;
     // For debug
-    private int total, total_forward, total_backward, total_hot;
+    private int total, total_forward, total_backward, total_hot, total_sst;
 
     /**
      * @return the shared string unique count
@@ -178,14 +177,12 @@ public class SharedStrings implements AutoCloseable {
             max = uniqueCount();
             LOGGER.debug("Size of SharedString: {}", max);
             // Unknown size or big than page
-            int default_cap = 10;
             if (max < 0 || max > page) {
                 forward = new String[page];
                 backward = new String[page];
 
-                if (max > 0 && max / page + 1 > default_cap)
-                    default_cap = max / page + 1;
-                count_area = new HashMap<>(default_cap);
+                // Cache 8KB binary, it will store 1^16 strings.
+                tester = new Tester.FixBinaryTester(max > 1 << 16 ? 1 << 16 : max);
 
                 if (hotSize > 0) hot = FixSizeLRUCache.create(hotSize);
                 else hot = FixSizeLRUCache.create();
@@ -260,7 +257,6 @@ public class SharedStrings implements AutoCloseable {
             if (vt < 0) vt = 0;
 
             loadXml();
-            test(index);
         }
 
         String value;
@@ -268,6 +264,7 @@ public class SharedStrings implements AutoCloseable {
         if (forwardRange(index)) {
             value = forward[index - offset_forward];
             total_forward++;
+            if (test(index)) hot.put(index, value);
             return value;
         }
 
@@ -275,6 +272,7 @@ public class SharedStrings implements AutoCloseable {
         if (backwardRange(index)) {
             value = backward[index - offset_backward];
             total_backward++;
+            if (test(index)) hot.put(index, value);
             return value;
         }
 
@@ -296,18 +294,16 @@ public class SharedStrings implements AutoCloseable {
                 } catch (IOException e) {
                     throw new ExcelWriteException(e);
                 }
+                total_sst++;
             } else {
                 loadXml();
+                total_forward++;
             }
             if (forward[0] == null) {
                 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + max);
             }
             value = forward[index - offset_forward];
-            if (test(index)) {
-                LOGGER.debug("put hot {}", index);
-                hot.put(index, value);
-            }
-            total_forward++;
+            if (test(index)) hot.put(index, value);
         } else {
             total_hot++;
         }
@@ -318,13 +314,13 @@ public class SharedStrings implements AutoCloseable {
     // Check the forward range
     private boolean forwardRange(int index) {
         return offset_forward >= 0 && offset_forward <= index
-            && offset_forward + limit_forward >= index;
+            && offset_forward + limit_forward > index;
     }
 
     // Check the backward range
     private boolean backwardRange(int index) {
         return offset_backward >= 0 && offset_backward <= index
-            && offset_backward + limit_backward >= index;
+            && offset_backward + limit_backward > index;
     }
 
     // Check the current index if out of bound
@@ -336,11 +332,7 @@ public class SharedStrings implements AutoCloseable {
 
     // Check the current index has been loaded twice
     private boolean test(int index) {
-        if (max < page) return false;
-        int idx = index / page;
-        int n = count_area.getOrDefault(idx, 0) + 1;
-        count_area.put(idx, n);
-        return n > 1;
+        return tester != null && tester.test(index);
     }
 
     /**
@@ -368,7 +360,7 @@ public class SharedStrings implements AutoCloseable {
     private int readData() throws IOException {
         // Read forward area data
         int n = 0, length, nChar;
-        while ((length = reader.read(cb, offset, cb.length - offset)) > 0 || offset > 0) {
+        for (; (length = reader.read(cb, offset, cb.length - offset)) > 0 || offset > 0; ) {
             length += offset;
             nChar = offset &= 0;
             int len0 = length - 3, len1 = len0 - 1;
@@ -556,16 +548,15 @@ public class SharedStrings implements AutoCloseable {
     public void close() throws IOException {
         if (reader != null) {
             // Debug hit rate
-            LOGGER.debug("total: {}, forward: {}, backward: {}, hot: {}"
-                , total, total_forward, total_backward, total_hot);
+            LOGGER.debug("total: {}, forward: {}, backward: {}, sst: {}, hot: {}"
+                , total, total_forward, total_backward, total_sst, total_hot);
             reader.close();
         }
         cb = null;
         forward = null;
         backward = null;
-        if (count_area != null) {
-            count_area.clear();
-            count_area = null;
+        if (tester != null) {
+            tester = null;
         }
         escapeBuf = null;
         if (sst != null) {
@@ -574,3 +565,84 @@ public class SharedStrings implements AutoCloseable {
     }
 
 }
+
+interface Tester {
+
+    /**
+     * Test if a string needs to be cached
+     *
+     * @param i the string index in {@link IndexSharedStringTable}
+     * @return true if the string should be cached
+     */
+    boolean test(int i);
+
+    /**
+     * Returns the limit index of {@link Tester}
+     *
+     * @return limit index
+     */
+    int limit();
+
+    /**
+     * Returns the block size of {@link Tester}
+     *
+     * @return the mark array length
+     */
+    int size();
+
+    class FixBinaryTester implements Tester {
+        private int start, limit, initial_size;
+        private long[] marks;
+
+        FixBinaryTester(int expectedInsertions) {
+            marks = new long[initial_size = ((expectedInsertions - 1) >> 6) + 1];
+            limit = (initial_size << 6) - 1;
+        }
+
+        @Override
+        public boolean test(int i) {
+            if (i < start) return true;
+            // Check bound of bit-set
+            if (i > limit) resize(i);
+            i = i - start;
+            int n = i >> 6, m = i - (n << 6);
+            boolean a = ((marks[n] >> (63 - m)) & 1) == 1;
+            marks[n] |= 1L << (63 - m);
+            return a;
+        }
+
+        @Override
+        public int limit() {
+            return limit;
+        }
+
+        @Override
+        public int size() {
+            return marks.length;
+        }
+
+        private void resize(int i) {
+            int ii = 0, n = marks.length, l = ((i - start) >> 6) + 1;
+
+            for (; ii < n && marks[ii] == -1; ii++) ;
+
+            if (l - ii <= initial_size) {
+                // Clean old mark
+                if (ii > 0) {
+                    int j = 0;
+                    for (int m = ii; m < n; marks[j++] = marks[m++]) ;
+                    for (; j < n; marks[j++] &= 0) ;
+                    start += (ii << 6);
+                } else {
+                    marks = Arrays.copyOf(marks, l);
+                }
+            } else {
+                long[] newMarks = new long[l - ii];
+                System.arraycopy(marks, ii, newMarks, 0, marks.length - ii);
+                marks = newMarks;
+                start += (ii << 6);
+            }
+            limit = (marks.length << 6) + start - 1;
+        }
+    }
+}
\ No newline at end of file


Test patch:
diff --git a/src/test/java/org/ttzero/excel/entity/ListObjectSheetTest.java b/src/test/java/org/ttzero/excel/entity/ListObjectSheetTest.java
index a0fd1509..0f245c64 100644
--- a/src/test/java/org/ttzero/excel/entity/ListObjectSheetTest.java
+++ b/src/test/java/org/ttzero/excel/entity/ListObjectSheetTest.java
@@ -434,7 +434,7 @@ public class ListObjectSheetTest extends WorkbookTest{
 
             @Override
             public List<ExcelReaderTest.LargeData> more() {
-                if (n++ >= 200) return null;
+                if (n++ >= 10) return null;
                 List<ExcelReaderTest.LargeData> list = new ArrayList<>();
                 int size = i + 5000;
                 for (; i < size; i++) {
diff --git a/src/test/java/org/ttzero/excel/reader/CacheTesterTest.java b/src/test/java/org/ttzero/excel/reader/CacheTesterTest.java
new file mode 100644
index 00000000..0fe2a6d8
--- /dev/null
+++ b/src/test/java/org/ttzero/excel/reader/CacheTesterTest.java
@@ -0,0 +1,57 @@
+/*
+ * Copyright (c) 2017-2020, guanquan.wang@yandex.com All Rights Reserved.
+ *
+ * Licensed 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.ttzero.excel.reader;
+
+import org.junit.Test;
+
+/**
+ * @author guanquan.wang at 2020-03-11 15:39
+ */
+public class CacheTesterTest {
+    @Test public void test() {
+        Tester tester = new Tester.FixBinaryTester(1024);
+        assert !tester.test(0);
+        assert !tester.test(1);
+        assert !tester.test(9);
+        assert tester.test(1);
+        assert tester.test(9);
+        assert !tester.test(5);
+        assert tester.test(0);
+
+        for (int i = 0; i < 63; tester.test(i++)) ;
+
+        assert !tester.test(1000);
+
+        assert tester.size() == 16;
+
+        assert tester.test(32);
+        assert tester.test(1000);
+        assert !tester.test(64);
+
+        assert !tester.test(63);
+        assert !tester.test(1024);
+
+        assert tester.size() == 16;
+        assert tester.limit() == 1087;
+
+        assert tester.test(1024);
+        assert !tester.test(1087);
+
+        assert tester.size() == 16;
+    }
+}
diff --git a/src/test/java/org/ttzero/excel/reader/ExcelReaderSharedTest.java b/src/test/java/org/ttzero/excel/reader/ExcelReaderSharedTest.java
new file mode 100644
index 00000000..a5461383
--- /dev/null
+++ b/src/test/java/org/ttzero/excel/reader/ExcelReaderSharedTest.java
@@ -0,0 +1,96 @@
+/*
+ * Copyright (c) 2017-2020, guanquan.wang@yandex.com All Rights Reserved.
+ *
+ * Licensed 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.ttzero.excel.reader;
+
+import org.junit.Test;
+
+import java.io.IOException;
+
+import static org.ttzero.excel.Print.println;
+import static org.ttzero.excel.reader.ExcelReaderTest.testResourceRoot;
+
+/**
+ * @author guanquan.wang at 2020-03-11 10:23
+ */
+public class ExcelReaderSharedTest {
+
+    @Test public void testSharedRead() {
+        try (ExcelReader reader = ExcelReader.read(testResourceRoot().resolve("eec shared 100.xlsx"))) {
+            reader.sheets().flatMap(Sheet::rows).forEach(row -> println(row.getRowNumber() + "| " + row.toString()));
+        } catch (IOException e) {
+            e.printStackTrace();
+        }
+    }
+
+//    public static class LargeSharedData {
+//        private int nv;
+//        private long lv;
+//        private double dv;
+//        private Date av;
+//        @ExcelColumn(value = "省", share = true)
+//        private String province;
+//        @ExcelColumn(value = "市", share = true)
+//        private String city;
+//        @ExcelColumn(value = "区/市/县", share = true)
+//        private String area;
+//        @ExcelColumn(share = true)
+//        private String str4;
+//        @ExcelColumn(share = true)
+//        private String str5;
+//        @ExcelColumn(share = true)
+//        private String str6;
+//        @ExcelColumn(share = true)
+//        private String str7;
+//        @ExcelColumn(share = true)
+//        private String str8;
+//        @ExcelColumn(share = true)
+//        private String str9;
+//        @ExcelColumn(share = true)
+//        private String str10;
+//        @ExcelColumn(share = true)
+//        private String str11;
+//        @ExcelColumn(share = true)
+//        private String str12;
+//        @ExcelColumn(share = true)
+//        private String str13;
+//        @ExcelColumn(share = true)
+//        private String str14;
+//        @ExcelColumn(share = true)
+//        private String str15;
+//        @ExcelColumn(share = true)
+//        private String str16;
+//        @ExcelColumn(share = true)
+//        private String str17;
+//        @ExcelColumn(share = true)
+//        private String str18;
+//        @ExcelColumn(share = true)
+//        private String str19;
+//        @ExcelColumn(share = true)
+//        private String str20;
+//        @ExcelColumn(share = true)
+//        private String str21;
+//        @ExcelColumn(share = true)
+//        private String str22;
+//        @ExcelColumn(share = true)
+//        private String str23;
+//        @ExcelColumn(share = true)
+//        private String str24;
+//        @ExcelColumn(share = true)
+//        private String str25;
+//    }
+}