1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.apache.hadoop.hbase.regionserver;
22
23 import org.apache.hadoop.hbase.KeyValue;
24 import org.apache.hadoop.hbase.KeyValue.KVComparator;
25
26 import java.io.IOException;
27 import java.util.Comparator;
28 import java.util.List;
29 import java.util.PriorityQueue;
30
31
32
33
34
35
36
37
38
39
40
41
42
43 public class KeyValueHeap implements KeyValueScanner, InternalScanner {
44 private PriorityQueue<KeyValueScanner> heap = null;
45 private KeyValueScanner current = null;
46 private KVScannerComparator comparator;
47
48
49
50
51
52
53
54 public KeyValueHeap(List<? extends KeyValueScanner> scanners,
55 KVComparator comparator) {
56 this.comparator = new KVScannerComparator(comparator);
57 if (!scanners.isEmpty()) {
58 this.heap = new PriorityQueue<KeyValueScanner>(scanners.size(),
59 this.comparator);
60 for (KeyValueScanner scanner : scanners) {
61 if (scanner.peek() != null) {
62 this.heap.add(scanner);
63 } else {
64 scanner.close();
65 }
66 }
67 this.current = heap.poll();
68 }
69 }
70
71 public KeyValue peek() {
72 if (this.current == null) {
73 return null;
74 }
75 return this.current.peek();
76 }
77
78 public KeyValue next() throws IOException {
79 if(this.current == null) {
80 return null;
81 }
82 KeyValue kvReturn = this.current.next();
83 KeyValue kvNext = this.current.peek();
84 if (kvNext == null) {
85 this.current.close();
86 this.current = this.heap.poll();
87 } else {
88 KeyValueScanner topScanner = this.heap.peek();
89 if (topScanner == null ||
90 this.comparator.compare(kvNext, topScanner.peek()) >= 0) {
91 this.heap.add(this.current);
92 this.current = this.heap.poll();
93 }
94 }
95 return kvReturn;
96 }
97
98
99
100
101
102
103
104
105
106
107
108
109 public boolean next(List<KeyValue> result, int limit) throws IOException {
110 if (this.current == null) {
111 return false;
112 }
113 InternalScanner currentAsInternal = (InternalScanner)this.current;
114 boolean mayContainsMoreRows = currentAsInternal.next(result, limit);
115 KeyValue pee = this.current.peek();
116
117
118
119
120
121
122
123 if (pee == null || !mayContainsMoreRows) {
124 this.current.close();
125 } else {
126 this.heap.add(this.current);
127 }
128 this.current = this.heap.poll();
129 return (this.current != null);
130 }
131
132
133
134
135
136
137
138
139
140
141
142 public boolean next(List<KeyValue> result) throws IOException {
143 return next(result, -1);
144 }
145
146 private static class KVScannerComparator implements Comparator<KeyValueScanner> {
147 private KVComparator kvComparator;
148
149
150
151
152 public KVScannerComparator(KVComparator kvComparator) {
153 this.kvComparator = kvComparator;
154 }
155 public int compare(KeyValueScanner left, KeyValueScanner right) {
156 int comparison = compare(left.peek(), right.peek());
157 if (comparison != 0) {
158 return comparison;
159 } else {
160
161
162 long leftSequenceID = left.getSequenceID();
163 long rightSequenceID = right.getSequenceID();
164 if (leftSequenceID > rightSequenceID) {
165 return -1;
166 } else if (leftSequenceID < rightSequenceID) {
167 return 1;
168 } else {
169 return 0;
170 }
171 }
172 }
173
174
175
176
177
178
179 public int compare(KeyValue left, KeyValue right) {
180 return this.kvComparator.compare(left, right);
181 }
182
183
184
185 public KVComparator getComparator() {
186 return this.kvComparator;
187 }
188 }
189
190 public void close() {
191 if (this.current != null) {
192 this.current.close();
193 }
194 if (this.heap != null) {
195 KeyValueScanner scanner;
196 while ((scanner = this.heap.poll()) != null) {
197 scanner.close();
198 }
199 }
200 }
201
202
203
204
205
206
207
208
209
210
211
212
213 public boolean seek(KeyValue seekKey) throws IOException {
214 if (this.current == null) {
215 return false;
216 }
217 this.heap.add(this.current);
218 this.current = null;
219
220 KeyValueScanner scanner;
221 while((scanner = this.heap.poll()) != null) {
222 KeyValue topKey = scanner.peek();
223 if(comparator.getComparator().compare(seekKey, topKey) <= 0) {
224
225 this.current = scanner;
226 return true;
227 }
228 if(!scanner.seek(seekKey)) {
229 scanner.close();
230 } else {
231 this.heap.add(scanner);
232 }
233 }
234
235 return false;
236 }
237
238 public boolean reseek(KeyValue seekKey) throws IOException {
239
240
241 if (this.current == null) {
242 return false;
243 }
244 this.heap.add(this.current);
245 this.current = null;
246
247 KeyValueScanner scanner;
248 while ((scanner = this.heap.poll()) != null) {
249 KeyValue topKey = scanner.peek();
250 if (comparator.getComparator().compare(seekKey, topKey) <= 0) {
251
252 this.current = scanner;
253 return true;
254 }
255 if (!scanner.reseek(seekKey)) {
256 scanner.close();
257 } else {
258 this.heap.add(scanner);
259 }
260 }
261
262 return false;
263 }
264
265
266
267
268 public PriorityQueue<KeyValueScanner> getHeap() {
269 return this.heap;
270 }
271
272 @Override
273 public long getSequenceID() {
274 return 0;
275 }
276 }