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;
20
21 import java.util.ArrayList;
22 import java.util.Collection;
23 import java.util.Comparator;
24 import java.util.List;
25 import java.util.Map.Entry;
26 import java.util.TreeMap;
27 import java.util.TreeSet;
28
29 import org.apache.commons.logging.Log;
30 import org.apache.commons.logging.LogFactory;
31 import org.apache.hadoop.hbase.classification.InterfaceAudience;
32 import org.apache.hadoop.hbase.util.Bytes.ByteArrayComparator;
33
34 import com.google.common.collect.ArrayListMultimap;
35 import com.google.common.collect.Multimap;
36 import com.google.common.collect.TreeMultimap;
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 @InterfaceAudience.Private
55 public class RegionSplitCalculator<R extends KeyRange> {
56 private static final Log LOG = LogFactory.getLog(RegionSplitCalculator.class);
57
58 private final Comparator<R> rangeCmp;
59
60
61
62
63
64
65 private final TreeSet<byte[]> splits = new TreeSet<byte[]>(BYTES_COMPARATOR);
66
67
68
69
70
71
72 private final Multimap<byte[], R> starts = ArrayListMultimap.create();
73
74
75
76
77 private final static byte[] ENDKEY = null;
78
79 public RegionSplitCalculator(Comparator<R> cmp) {
80 rangeCmp = cmp;
81 }
82
83 public final static Comparator<byte[]> BYTES_COMPARATOR = new ByteArrayComparator() {
84 @Override
85 public int compare(byte[] l, byte[] r) {
86 if (l == null && r == null)
87 return 0;
88 if (l == null)
89 return 1;
90 if (r == null)
91 return -1;
92 return super.compare(l, r);
93 }
94 };
95
96
97
98
99
100
101 private static <R extends KeyRange> byte[] specialEndKey(R range) {
102 byte[] end = range.getEndKey();
103 if (end.length == 0) {
104 return ENDKEY;
105 }
106 return end;
107 }
108
109
110
111
112
113
114 public boolean add(R range) {
115 byte[] start = range.getStartKey();
116 byte[] end = specialEndKey(range);
117
118 if (end != ENDKEY && Bytes.compareTo(start, end) > 0) {
119
120 LOG.debug("attempted to add backwards edge: " + Bytes.toString(start)
121 + " " + Bytes.toString(end));
122 return false;
123 }
124
125 splits.add(start);
126 splits.add(end);
127 starts.put(start, range);
128 return true;
129 }
130
131
132
133
134
135
136
137 public Multimap<byte[], R> calcCoverage() {
138
139
140 Multimap<byte[], R> regions = TreeMultimap.create(BYTES_COMPARATOR,
141 rangeCmp);
142
143
144 for (Entry<byte[], Collection<R>> start : starts.asMap().entrySet()) {
145 byte[] key = start.getKey();
146 for (R r : start.getValue()) {
147 regions.put(key, r);
148
149 for (byte[] coveredSplit : splits.subSet(r.getStartKey(),
150 specialEndKey(r))) {
151 regions.put(coveredSplit, r);
152 }
153 }
154 }
155 return regions;
156 }
157
158 public TreeSet<byte[]> getSplits() {
159 return splits;
160 }
161
162 public Multimap<byte[], R> getStarts() {
163 return starts;
164 }
165
166
167
168
169
170
171
172
173
174
175
176
177 public static <R extends KeyRange> List<R>
178 findBigRanges(Collection<R> bigOverlap, int count) {
179 List<R> bigRanges = new ArrayList<R>();
180
181
182
183 TreeMap<Integer, List<R>> overlapRangeMap = new TreeMap<Integer, List<R>>();
184 for (R r: bigOverlap) {
185
186
187 byte[] startKey = r.getStartKey();
188 byte[] endKey = specialEndKey(r);
189
190 int overlappedRegions = 0;
191 for (R rr: bigOverlap) {
192 byte[] start = rr.getStartKey();
193 byte[] end = specialEndKey(rr);
194
195 if (BYTES_COMPARATOR.compare(startKey, end) < 0
196 && BYTES_COMPARATOR.compare(endKey, start) > 0) {
197 overlappedRegions++;
198 }
199 }
200
201
202
203
204 if (overlappedRegions > 1) {
205 Integer key = Integer.valueOf(overlappedRegions);
206 List<R> ranges = overlapRangeMap.get(key);
207 if (ranges == null) {
208 ranges = new ArrayList<R>();
209 overlapRangeMap.put(key, ranges);
210 }
211 ranges.add(r);
212 }
213 }
214 int toBeAdded = count;
215 for (Integer key: overlapRangeMap.descendingKeySet()) {
216 List<R> chunk = overlapRangeMap.get(key);
217 int chunkSize = chunk.size();
218 if (chunkSize <= toBeAdded) {
219 bigRanges.addAll(chunk);
220 toBeAdded -= chunkSize;
221 if (toBeAdded > 0) continue;
222 } else {
223
224
225
226
227 int start = (chunkSize - toBeAdded)/2;
228 int end = start + toBeAdded;
229 for (int i = start; i < end; i++) {
230 bigRanges.add(chunk.get(i));
231 }
232 }
233 break;
234 }
235 return bigRanges;
236 }
237 }