1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.hadoop.hbase.util.byterange;
20
21 import java.util.ArrayList;
22 import java.util.List;
23 import java.util.Map;
24
25 import org.apache.hadoop.hbase.classification.InterfaceAudience;
26 import org.apache.hadoop.hbase.util.ArrayUtils;
27 import org.apache.hadoop.hbase.util.ByteRange;
28 import org.apache.hadoop.hbase.util.Bytes;
29 import org.apache.hadoop.hbase.util.SimpleMutableByteRange;
30
31 import com.google.common.collect.Lists;
32
33
34
35
36
37
38
39
40
41 @InterfaceAudience.Private
42 public abstract class ByteRangeSet {
43
44
45
46 protected byte[] byteAppender;
47 protected int numBytes;
48
49 protected Map<ByteRange, Integer> uniqueIndexByUniqueRange;
50
51 protected ArrayList<ByteRange> uniqueRanges;
52 protected int numUniqueRanges = 0;
53
54 protected int[] uniqueRangeIndexByInsertionId;
55 protected int numInputs;
56
57 protected List<Integer> sortedIndexByUniqueIndex;
58 protected int[] sortedIndexByInsertionId;
59 protected ArrayList<ByteRange> sortedRanges;
60
61
62
63
64 protected ByteRangeSet() {
65 this.byteAppender = new byte[0];
66 this.uniqueRanges = Lists.newArrayList();
67 this.uniqueRangeIndexByInsertionId = new int[0];
68 this.sortedIndexByUniqueIndex = Lists.newArrayList();
69 this.sortedIndexByInsertionId = new int[0];
70 this.sortedRanges = Lists.newArrayList();
71 }
72
73 public void reset() {
74 numBytes = 0;
75 uniqueIndexByUniqueRange.clear();
76 numUniqueRanges = 0;
77 numInputs = 0;
78 sortedIndexByUniqueIndex.clear();
79 sortedRanges.clear();
80 }
81
82
83
84
85 public abstract void addToSortedRanges();
86
87
88
89
90
91
92
93
94 public void add(ByteRange bytes) {
95 Integer index = uniqueIndexByUniqueRange.get(bytes);
96 if (index == null) {
97 index = store(bytes);
98 }
99 int minLength = numInputs + 1;
100 uniqueRangeIndexByInsertionId = ArrayUtils.growIfNecessary(uniqueRangeIndexByInsertionId,
101 minLength, 2 * minLength);
102 uniqueRangeIndexByInsertionId[numInputs] = index;
103 ++numInputs;
104 }
105
106 protected int store(ByteRange bytes) {
107 int indexOfNewElement = numUniqueRanges;
108 if (uniqueRanges.size() <= numUniqueRanges) {
109 uniqueRanges.add(new SimpleMutableByteRange());
110 }
111 ByteRange storedRange = uniqueRanges.get(numUniqueRanges);
112 int neededBytes = numBytes + bytes.getLength();
113 byteAppender = ArrayUtils.growIfNecessary(byteAppender, neededBytes, 2 * neededBytes);
114 bytes.deepCopyTo(byteAppender, numBytes);
115 storedRange.set(byteAppender, numBytes, bytes.getLength());
116 numBytes += bytes.getLength();
117 uniqueIndexByUniqueRange.put(storedRange, indexOfNewElement);
118 int newestUniqueIndex = numUniqueRanges;
119 ++numUniqueRanges;
120 return newestUniqueIndex;
121 }
122
123 public ByteRangeSet compile() {
124 addToSortedRanges();
125 for (int i = 0; i < sortedRanges.size(); ++i) {
126 sortedIndexByUniqueIndex.add(null);
127 }
128
129 for (int i = 0; i < sortedIndexByUniqueIndex.size(); ++i) {
130 int uniqueIndex = uniqueIndexByUniqueRange.get(sortedRanges.get(i));
131 sortedIndexByUniqueIndex.set(uniqueIndex, i);
132 }
133 sortedIndexByInsertionId = ArrayUtils.growIfNecessary(sortedIndexByInsertionId, numInputs,
134 numInputs);
135 for (int i = 0; i < numInputs; ++i) {
136 int uniqueRangeIndex = uniqueRangeIndexByInsertionId[i];
137 int sortedIndex = sortedIndexByUniqueIndex.get(uniqueRangeIndex);
138 sortedIndexByInsertionId[i] = sortedIndex;
139 }
140 return this;
141 }
142
143 public int getSortedIndexForInsertionId(int insertionId) {
144 return sortedIndexByInsertionId[insertionId];
145 }
146
147 public int size() {
148 return uniqueIndexByUniqueRange.size();
149 }
150
151
152
153
154 @Override
155 public String toString() {
156 StringBuilder sb = new StringBuilder();
157 int i = 0;
158 for (ByteRange r : sortedRanges) {
159 if (i > 0) {
160 sb.append("\n");
161 }
162 sb.append(i + " " + Bytes.toStringBinary(r.deepCopyToNewArray()));
163 ++i;
164 }
165 sb.append("\ntotalSize:" + numBytes);
166 sb.append("\navgSize:" + getAvgSize());
167 return sb.toString();
168 }
169
170
171
172
173 public ArrayList<ByteRange> getSortedRanges() {
174 return sortedRanges;
175 }
176
177 public long getAvgSize() {
178 return numBytes / numUniqueRanges;
179 }
180
181 }