001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, software 013 * distributed under the License is distributed on an "AS IS" BASIS, 014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 015 * See the License for the specific language governing permissions and 016 * limitations under the License. 017 */ 018package org.apache.hadoop.hbase.regionserver; 019 020import java.util.Collection; 021import java.util.Comparator; 022import java.util.Iterator; 023import java.util.Map; 024import java.util.NavigableMap; 025import java.util.NavigableSet; 026import java.util.Set; 027import org.apache.hadoop.hbase.Cell; 028import org.apache.yetus.audience.InterfaceAudience; 029import org.slf4j.Logger; 030import org.slf4j.LoggerFactory; 031 032/** 033 * CellFlatMap stores a constant number of elements and is immutable after creation stage. Being 034 * immutable, the CellFlatMap can be implemented as array. The actual array can be on- or off-heap 035 * and is implemented in concrete class derived from CellFlatMap. The CellFlatMap uses no 036 * synchronization primitives, it is assumed to be created by a single thread and then it can be 037 * read-only by multiple threads. The "flat" in the name, means that the memory layout of the Map is 038 * sequential array and thus requires less memory than ConcurrentSkipListMap. 039 */ 040@InterfaceAudience.Private 041public abstract class CellFlatMap implements NavigableMap<Cell, Cell> { 042 private static final Logger LOG = LoggerFactory.getLogger(CellFlatMap.class); 043 private final Comparator<? super Cell> comparator; 044 protected int minCellIdx = 0; // the index of the minimal cell (for sub-sets) 045 protected int maxCellIdx = 0; // the index of the cell after the maximal cell (for sub-sets) 046 private boolean descending = false; 047 048 /* C-tor */ 049 public CellFlatMap(Comparator<? super Cell> comparator, int min, int max, boolean d) { 050 this.comparator = comparator; 051 this.minCellIdx = min; 052 this.maxCellIdx = max; 053 this.descending = d; 054 } 055 056 /* Used for abstract CellFlatMap creation, implemented by derived class */ 057 protected abstract CellFlatMap createSubCellFlatMap(int min, int max, boolean descending); 058 059 /* Returns the i-th cell in the cell block */ 060 protected abstract Cell getCell(int i); 061 062 /** 063 * Binary search for a given key in between given boundaries of the array. Positive returned 064 * numbers mean the index. Negative returned numbers means the key not found. The absolute value 065 * of the output is the possible insert index for the searched key In twos-complement, (-1 * 066 * insertion point)-1 is the bitwise not of the insert point. 067 * @param needle The key to look for in all of the entries 068 * @return Same return value as Arrays.binarySearch. 069 */ 070 private int find(Cell needle) { 071 int begin = minCellIdx; 072 int end = maxCellIdx - 1; 073 074 while (begin <= end) { 075 int mid = begin + ((end - begin) >> 1); 076 Cell midCell = getCell(mid); 077 int compareRes = comparator.compare(midCell, needle); 078 079 if (compareRes == 0) { 080 return mid; // 0 means equals. We found the key 081 } 082 // Key not found. Check the comparison results; reverse the meaning of 083 // the comparison in case the order is descending (using XOR) 084 if ((compareRes < 0) ^ descending) { 085 // midCell is less than needle so we need to look at farther up 086 begin = mid + 1; 087 } else { 088 // midCell is greater than needle so we need to look down 089 end = mid - 1; 090 } 091 } 092 093 return (-1 * begin) - 1; 094 } 095 096 /** 097 * Get the index of the given anchor key for creating subsequent set. It doesn't matter whether 098 * the given key exists in the set or not. taking into consideration whether the key should be 099 * inclusive or exclusive. 100 */ 101 private int getValidIndex(Cell key, boolean inclusive, boolean tail) { 102 final int index = find(key); 103 // get the valid (positive) insertion point from the output of the find() method 104 int insertionPoint = index < 0 ? ~index : index; 105 106 // correct the insertion point in case the given anchor key DOES EXIST in the set 107 if (index >= 0) { 108 if (descending && !(tail ^ inclusive)) { 109 // for the descending case 110 // if anchor for head set (tail=false) AND anchor is not inclusive -> move the insertion pt 111 // if anchor for tail set (tail=true) AND the keys is inclusive -> move the insertion point 112 // because the end index of a set is the index of the cell after the maximal cell 113 insertionPoint += 1; 114 } else if (!descending && (tail ^ inclusive)) { 115 // for the ascending case 116 // if anchor for head set (tail=false) AND anchor is inclusive -> move the insertion point 117 // because the end index of a set is the index of the cell after the maximal cell 118 // if anchor for tail set (tail=true) AND the keys is not inclusive -> move the insertion pt 119 insertionPoint += 1; 120 } 121 } 122 // insert the insertion point into the valid range, 123 // as we may enlarge it too much in the above correction 124 return Math.min(Math.max(insertionPoint, minCellIdx), maxCellIdx); 125 } 126 127 @Override 128 public Comparator<? super Cell> comparator() { 129 return comparator; 130 } 131 132 @Override 133 public int size() { 134 return maxCellIdx - minCellIdx; 135 } 136 137 @Override 138 public boolean isEmpty() { 139 return (size() == 0); 140 } 141 142 // ---------------- Sub-Maps ---------------- 143 @Override 144 public NavigableMap<Cell, Cell> subMap(Cell fromKey, boolean fromInclusive, Cell toKey, 145 boolean toInclusive) { 146 final int lessCellIndex = getValidIndex(fromKey, fromInclusive, true); 147 final int greaterCellIndex = getValidIndex(toKey, toInclusive, false); 148 if (descending) { 149 return createSubCellFlatMap(greaterCellIndex, lessCellIndex, descending); 150 } else { 151 return createSubCellFlatMap(lessCellIndex, greaterCellIndex, descending); 152 } 153 } 154 155 @Override 156 public NavigableMap<Cell, Cell> headMap(Cell toKey, boolean inclusive) { 157 if (descending) { 158 return createSubCellFlatMap(getValidIndex(toKey, inclusive, false), maxCellIdx, descending); 159 } else { 160 return createSubCellFlatMap(minCellIdx, getValidIndex(toKey, inclusive, false), descending); 161 } 162 } 163 164 @Override 165 public NavigableMap<Cell, Cell> tailMap(Cell fromKey, boolean inclusive) { 166 if (descending) { 167 return createSubCellFlatMap(minCellIdx, getValidIndex(fromKey, inclusive, true), descending); 168 } else { 169 return createSubCellFlatMap(getValidIndex(fromKey, inclusive, true), maxCellIdx, descending); 170 } 171 } 172 173 @Override 174 public NavigableMap<Cell, Cell> descendingMap() { 175 return createSubCellFlatMap(minCellIdx, maxCellIdx, true); 176 } 177 178 @Override 179 public NavigableMap<Cell, Cell> subMap(Cell k1, Cell k2) { 180 return this.subMap(k1, true, k2, true); 181 } 182 183 @Override 184 public NavigableMap<Cell, Cell> headMap(Cell k) { 185 return this.headMap(k, true); 186 } 187 188 @Override 189 public NavigableMap<Cell, Cell> tailMap(Cell k) { 190 return this.tailMap(k, true); 191 } 192 193 // -------------------------------- Key's getters -------------------------------- 194 @Override 195 public Cell firstKey() { 196 if (isEmpty()) { 197 return null; 198 } 199 return descending ? getCell(maxCellIdx - 1) : getCell(minCellIdx); 200 } 201 202 @Override 203 public Cell lastKey() { 204 if (isEmpty()) { 205 return null; 206 } 207 return descending ? getCell(minCellIdx) : getCell(maxCellIdx - 1); 208 } 209 210 @Override 211 public Cell lowerKey(Cell k) { 212 if (isEmpty()) { 213 return null; 214 } 215 int index = find(k); 216 // If index>=0 there's a key exactly equal 217 index = (index >= 0) ? index - 1 : -(index); 218 return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index); 219 } 220 221 @Override 222 public Cell floorKey(Cell k) { 223 if (isEmpty()) { 224 return null; 225 } 226 int index = find(k); 227 index = (index >= 0) ? index : -(index); 228 return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index); 229 } 230 231 @Override 232 public Cell ceilingKey(Cell k) { 233 if (isEmpty()) { 234 return null; 235 } 236 int index = find(k); 237 index = (index >= 0) ? index : -(index) + 1; 238 return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index); 239 } 240 241 @Override 242 public Cell higherKey(Cell k) { 243 if (isEmpty()) { 244 return null; 245 } 246 int index = find(k); 247 index = (index >= 0) ? index + 1 : -(index) + 1; 248 return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index); 249 } 250 251 @Override 252 public boolean containsKey(Object o) { 253 int index = find((Cell) o); 254 return (index >= 0); 255 } 256 257 @Override 258 public boolean containsValue(Object o) { // use containsKey(Object o) instead 259 throw new UnsupportedOperationException("Use containsKey(Object o) instead"); 260 } 261 262 @Override 263 public Cell get(Object o) { 264 int index = find((Cell) o); 265 return (index >= 0) ? getCell(index) : null; 266 } 267 268 // -------------------------------- Entry's getters -------------------------------- 269 270 private static class CellFlatMapEntry implements Entry<Cell, Cell> { 271 private final Cell cell; 272 273 public CellFlatMapEntry(Cell cell) { 274 this.cell = cell; 275 } 276 277 @Override 278 public Cell getKey() { 279 return cell; 280 } 281 282 @Override 283 public Cell getValue() { 284 return cell; 285 } 286 287 @Override 288 public Cell setValue(Cell value) { 289 throw new UnsupportedOperationException(); 290 } 291 } 292 293 @Override 294 public Entry<Cell, Cell> lowerEntry(Cell k) { 295 Cell cell = lowerKey(k); 296 if (cell == null) { 297 return null; 298 } 299 return new CellFlatMapEntry(cell); 300 } 301 302 @Override 303 public Entry<Cell, Cell> higherEntry(Cell k) { 304 Cell cell = higherKey(k); 305 if (cell == null) { 306 return null; 307 } 308 return new CellFlatMapEntry(cell); 309 } 310 311 @Override 312 public Entry<Cell, Cell> ceilingEntry(Cell k) { 313 Cell cell = ceilingKey(k); 314 if (cell == null) { 315 return null; 316 } 317 return new CellFlatMapEntry(cell); 318 } 319 320 @Override 321 public Entry<Cell, Cell> floorEntry(Cell k) { 322 Cell cell = floorKey(k); 323 if (cell == null) { 324 return null; 325 } 326 return new CellFlatMapEntry(cell); 327 } 328 329 @Override 330 public Entry<Cell, Cell> firstEntry() { 331 Cell cell = firstKey(); 332 if (cell == null) { 333 return null; 334 } 335 return new CellFlatMapEntry(cell); 336 } 337 338 @Override 339 public Entry<Cell, Cell> lastEntry() { 340 Cell cell = lastKey(); 341 if (cell == null) { 342 return null; 343 } 344 return new CellFlatMapEntry(cell); 345 } 346 347 // The following 2 methods (pollFirstEntry, pollLastEntry) are unsupported because these are 348 // updating methods. 349 @Override 350 public Entry<Cell, Cell> pollFirstEntry() { 351 throw new UnsupportedOperationException(); 352 } 353 354 @Override 355 public Entry<Cell, Cell> pollLastEntry() { 356 throw new UnsupportedOperationException(); 357 } 358 359 // -------------------------------- Updates -------------------------------- 360 // All updating methods below are unsupported. 361 // Assuming an array of Cells will be allocated externally, 362 // fill up with Cells and provided in construction time. 363 // Later the structure is immutable. 364 @Override 365 public Cell put(Cell k, Cell v) { 366 throw new UnsupportedOperationException(); 367 } 368 369 @Override 370 public void clear() { 371 throw new UnsupportedOperationException(); 372 } 373 374 @Override 375 public Cell remove(Object o) { 376 throw new UnsupportedOperationException(); 377 } 378 379 @Override 380 public void putAll(Map<? extends Cell, ? extends Cell> map) { 381 throw new UnsupportedOperationException(); 382 } 383 384 // -------------------------------- Sub-Sets -------------------------------- 385 @Override 386 public NavigableSet<Cell> navigableKeySet() { 387 throw new UnsupportedOperationException(); 388 } 389 390 @Override 391 public NavigableSet<Cell> descendingKeySet() { 392 throw new UnsupportedOperationException(); 393 } 394 395 @Override 396 public NavigableSet<Cell> keySet() { 397 throw new UnsupportedOperationException(); 398 } 399 400 @Override 401 public Collection<Cell> values() { 402 return new CellFlatMapCollection(); 403 } 404 405 @Override 406 public Set<Entry<Cell, Cell>> entrySet() { 407 throw new UnsupportedOperationException(); 408 } 409 410 // -------------------------------- Iterator K -------------------------------- 411 private final class CellFlatMapIterator implements Iterator<Cell> { 412 int index; 413 414 private CellFlatMapIterator() { 415 index = descending ? maxCellIdx - 1 : minCellIdx; 416 } 417 418 @Override 419 public boolean hasNext() { 420 return descending ? (index >= minCellIdx) : (index < maxCellIdx); 421 } 422 423 @Override 424 public Cell next() { 425 Cell result = getCell(index); 426 if (descending) { 427 index--; 428 } else { 429 index++; 430 } 431 return result; 432 } 433 434 @Override 435 public void remove() { 436 throw new UnsupportedOperationException(); 437 } 438 } 439 440 // -------------------------------- Collection -------------------------------- 441 private final class CellFlatMapCollection implements Collection<Cell> { 442 443 @Override 444 public int size() { 445 return CellFlatMap.this.size(); 446 } 447 448 @Override 449 public boolean isEmpty() { 450 return CellFlatMap.this.isEmpty(); 451 } 452 453 @Override 454 public void clear() { 455 throw new UnsupportedOperationException(); 456 } 457 458 @Override 459 public boolean contains(Object o) { 460 return containsKey(o); 461 } 462 463 @Override 464 public Iterator<Cell> iterator() { 465 return new CellFlatMapIterator(); 466 } 467 468 @Override 469 public Object[] toArray() { 470 throw new UnsupportedOperationException(); 471 } 472 473 @Override 474 public <T> T[] toArray(T[] ts) { 475 throw new UnsupportedOperationException(); 476 } 477 478 @Override 479 public boolean add(Cell k) { 480 throw new UnsupportedOperationException(); 481 } 482 483 @Override 484 public boolean remove(Object o) { 485 throw new UnsupportedOperationException(); 486 } 487 488 @Override 489 public boolean containsAll(Collection<?> collection) { 490 throw new UnsupportedOperationException(); 491 } 492 493 @Override 494 public boolean addAll(Collection<? extends Cell> collection) { 495 throw new UnsupportedOperationException(); 496 } 497 498 @Override 499 public boolean removeAll(Collection<?> collection) { 500 throw new UnsupportedOperationException(); 501 } 502 503 @Override 504 public boolean retainAll(Collection<?> collection) { 505 throw new UnsupportedOperationException(); 506 } 507 } 508}