hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellFlatMap.java

   1 /**
   2  *
   3  * Licensed to the Apache Software Foundation (ASF) under one
   4  * or more contributor license agreements.  See the NOTICE file
   5  * distributed with this work for additional information
   6  * regarding copyright ownership.  The ASF licenses this file
   7  * to you under the Apache License, Cellersion 2.0 (the
   8  * "License"); you may not use this file except in compliance
   9  * with the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY CellIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19 package org.apache.hadoop.hbase.regionserver;
  20
  21 import org.apache.hadoop.hbase.Cell;
  22 import org.apache.yetus.audience.InterfaceAudience;
  23 import org.slf4j.Logger;
  24 import org.slf4j.LoggerFactory;
  25
  26 import java.util.Collection;
  27 import java.util.Comparator;
  28 import java.util.Iterator;
  29 import java.util.Map;
  30 import java.util.NavigableSet;
  31 import java.util.NavigableMap;
  32 import java.util.Set;
  33
  34
  35 /**
  36  * CellFlatMap stores a constant number of elements and is immutable after creation stage.
  37  * Being immutable, the CellFlatMap can be implemented as array.
  38  * The actual array can be on- or off-heap and is implemented in concrete class derived from CellFlatMap.
  39  * The CellFlatMap uses no synchronization primitives, it is assumed to be created by a
  40  * single thread and then it can be read-only by multiple threads.
  41  *
  42  * The "flat" in the name, means that the memory layout of the Map is sequential array and thus
  43  * requires less memory than ConcurrentSkipListMap.
  44  */
  45 @InterfaceAudience.Private
  46 public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
  47   private static final Logger LOG = LoggerFactory.getLogger(CellFlatMap.class);
  48   private final Comparator<? super Cell> comparator;
  49   protected int minCellIdx   = 0;   // the index of the minimal cell (for sub-sets)
  50   protected int maxCellIdx   = 0;   // the index of the cell after the maximal cell (for sub-sets)
  51   private boolean descending = false;
  52
  53   /* C-tor */
  54   public CellFlatMap(Comparator<? super Cell> comparator, int min, int max, boolean d){
  55     this.comparator = comparator;
  56     this.minCellIdx = min;
  57     this.maxCellIdx = max;
  58     this.descending = d;
  59   }
  60
  61   /* Used for abstract CellFlatMap creation, implemented by derived class */
  62   protected abstract CellFlatMap createSubCellFlatMap(int min, int max, boolean descending);
  63
  64   /* Returns the i-th cell in the cell block */
  65   protected abstract Cell getCell(int i);
  66
  67   /**
  68    * Binary search for a given key in between given boundaries of the array.
  69    * Positive returned numbers mean the index.
  70    * Negative returned numbers means the key not found.
  71    *
  72    * The absolute value of the output is the
  73    * possible insert index for the searched key
  74    *
  75    * In twos-complement, (-1 * insertion point)-1 is the bitwise not of the insert point.
  76    *
  77    *
  78    * @param needle The key to look for in all of the entries
  79    * @return Same return value as Arrays.binarySearch.
  80    */
  81   private int find(Cell needle) {
  82     int begin = minCellIdx;
  83     int end = maxCellIdx - 1;
  84
  85     while (begin <= end) {
  86       int mid = begin + ((end - begin) >> 1);
  87       Cell midCell = getCell(mid);
  88       int compareRes = comparator.compare(midCell, needle);
  89
  90       if (compareRes == 0) {
  91         return mid;  // 0 means equals. We found the key
  92       }
  93       // Key not found. Check the comparison results; reverse the meaning of
  94       // the comparison in case the order is descending (using XOR)
  95       if ((compareRes < 0) ^ descending) {
  96         // midCell is less than needle so we need to look at farther up
  97         begin = mid + 1;
  98       } else {
  99         // midCell is greater than needle so we need to look down
 100         end = mid - 1;
 101       }
 102     }
 103
 104     return (-1 * begin)-1;
 105   }
 106
 107   /**
 108    * Get the index of the given anchor key for creating subsequent set.
 109    * It doesn't matter whether the given key exists in the set or not.
 110    * taking into consideration whether
 111    * the key should be inclusive or exclusive.
 112    */
 113   private int getValidIndex(Cell key, boolean inclusive, boolean tail) {
 114     final int index = find(key);
 115     // get the valid (positive) insertion point from the output of the find() method
 116     int insertionPoint = index < 0 ? ~index : index;
 117
 118     // correct the insertion point in case the given anchor key DOES EXIST in the set
 119     if (index >= 0) {
 120       if ( descending && !(tail ^ inclusive)) {
 121         // for the descending case
 122         // if anchor for head set (tail=false) AND anchor is not inclusive -> move the insertion pt
 123         // if anchor for tail set (tail=true) AND the keys is inclusive -> move the insertion point
 124         // because the end index of a set is the index of the cell after the maximal cell
 125         insertionPoint += 1;
 126       } else if ( !descending && (tail ^ inclusive)) {
 127         // for the ascending case
 128         // if anchor for head set (tail=false) AND anchor is inclusive -> move the insertion point
 129         // because the end index of a set is the index of the cell after the maximal cell
 130         // if anchor for tail set (tail=true) AND the keys is not inclusive -> move the insertion pt
 131         insertionPoint += 1;
 132       }
 133     }
 134     // insert the insertion point into the valid range,
 135     // as we may enlarge it too much in the above correction
 136     return Math.min(Math.max(insertionPoint, minCellIdx), maxCellIdx);
 137 }
 138
 139   @Override
 140   public Comparator<? super Cell> comparator() {
 141     return comparator;
 142   }
 143
 144   @Override
 145   public int size() {
 146     return maxCellIdx-minCellIdx;
 147   }
 148
 149   @Override
 150   public boolean isEmpty() {
 151     return ( size() == 0 );
 152   }
 153
 154
 155   // ---------------- Sub-Maps ----------------
 156   @Override
 157   public NavigableMap<Cell, Cell> subMap( Cell fromKey,
 158                                                     boolean fromInclusive,
 159                                                     Cell toKey,
 160                                                     boolean toInclusive) {
 161     final int lessCellIndex = getValidIndex(fromKey, fromInclusive, true);
 162     final int greaterCellIndex = getValidIndex(toKey, toInclusive, false);
 163     if (descending) {
 164       return createSubCellFlatMap(greaterCellIndex, lessCellIndex, descending);
 165     } else {
 166       return createSubCellFlatMap(lessCellIndex, greaterCellIndex, descending);
 167     }
 168   }
 169
 170   @Override
 171   public NavigableMap<Cell, Cell> headMap(Cell toKey, boolean inclusive) {
 172     if (descending) {
 173       return createSubCellFlatMap(getValidIndex(toKey, inclusive, false), maxCellIdx, descending);
 174     } else {
 175       return createSubCellFlatMap(minCellIdx, getValidIndex(toKey, inclusive, false), descending);
 176     }
 177   }
 178
 179   @Override
 180   public NavigableMap<Cell, Cell> tailMap(Cell fromKey, boolean inclusive) {
 181     if (descending) {
 182       return createSubCellFlatMap(minCellIdx, getValidIndex(fromKey, inclusive, true), descending);
 183     } else {
 184       return createSubCellFlatMap(getValidIndex(fromKey, inclusive, true), maxCellIdx, descending);
 185     }
 186   }
 187
 188   @Override
 189   public NavigableMap<Cell, Cell> descendingMap() {
 190     return createSubCellFlatMap(minCellIdx, maxCellIdx, true);
 191   }
 192
 193   @Override
 194   public NavigableMap<Cell, Cell> subMap(Cell k1, Cell k2) {
 195     return this.subMap(k1, true, k2, true);
 196   }
 197
 198   @Override
 199   public NavigableMap<Cell, Cell> headMap(Cell k) {
 200     return this.headMap(k, true);
 201   }
 202
 203   @Override
 204   public NavigableMap<Cell, Cell> tailMap(Cell k) {
 205     return this.tailMap(k, true);
 206   }
 207
 208
 209   // -------------------------------- Key's getters --------------------------------
 210   @Override
 211   public Cell firstKey() {
 212     if (isEmpty()) {
 213       return null;
 214     }
 215     return descending ? getCell(maxCellIdx - 1) : getCell(minCellIdx);
 216   }
 217
 218   @Override
 219   public Cell lastKey() {
 220     if (isEmpty()) {
 221       return null;
 222     }
 223     return descending ? getCell(minCellIdx) : getCell(maxCellIdx - 1);
 224   }
 225
 226   @Override
 227   public Cell lowerKey(Cell k) {
 228     if (isEmpty()) {
 229       return null;
 230     }
 231     int index = find(k);
 232     // If index>=0 there's a key exactly equal
 233     index = (index>=0) ? index-1 : -(index);
 234     return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index);
 235   }
 236
 237   @Override
 238   public Cell floorKey(Cell k) {
 239     if (isEmpty()) {
 240       return null;
 241     }
 242     int index = find(k);
 243     index = (index>=0) ? index : -(index);
 244     return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index);
 245   }
 246
 247   @Override
 248   public Cell ceilingKey(Cell k) {
 249     if (isEmpty()) {
 250       return null;
 251     }
 252     int index = find(k);
 253     index = (index>=0) ? index : -(index)+1;
 254     return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index);
 255   }
 256
 257   @Override
 258   public Cell higherKey(Cell k) {
 259     if (isEmpty()) {
 260       return null;
 261     }
 262     int index = find(k);
 263     index = (index>=0) ? index+1 : -(index)+1;
 264     return (index < minCellIdx || index >= maxCellIdx) ? null : getCell(index);
 265   }
 266
 267   @Override
 268   public boolean containsKey(Object o) {
 269     int index = find((Cell) o);
 270     return (index >= 0);
 271   }
 272
 273   @Override
 274   public boolean containsValue(Object o) { // use containsKey(Object o) instead
 275     throw new UnsupportedOperationException("Use containsKey(Object o) instead");
 276   }
 277
 278   @Override
 279   public Cell get(Object o) {
 280     int index = find((Cell) o);
 281     return (index >= 0) ? getCell(index) : null;
 282   }
 283
 284   // -------------------------------- Entry's getters --------------------------------
 285
 286   private static class CellFlatMapEntry implements Entry<Cell, Cell> {
 287     private final Cell cell;
 288
 289     public CellFlatMapEntry (Cell cell) {
 290       this.cell = cell;
 291     }
 292
 293     @Override
 294     public Cell getKey() {
 295       return cell;
 296     }
 297
 298     @Override
 299     public Cell getValue() {
 300       return cell;
 301     }
 302
 303     @Override
 304     public Cell setValue(Cell value) {
 305       throw new UnsupportedOperationException();
 306     }
 307   }
 308
 309   @Override
 310   public Entry<Cell, Cell> lowerEntry(Cell k) {
 311     Cell cell = lowerKey(k);
 312     if (cell == null) {
 313       return null;
 314     }
 315     return new CellFlatMapEntry(cell);
 316   }
 317
 318   @Override
 319   public Entry<Cell, Cell> higherEntry(Cell k) {
 320     Cell cell = higherKey(k);
 321     if (cell == null) {
 322       return null;
 323     }
 324     return new CellFlatMapEntry(cell);
 325   }
 326
 327   @Override
 328   public Entry<Cell, Cell> ceilingEntry(Cell k) {
 329     Cell cell = ceilingKey(k);
 330     if (cell == null) {
 331       return null;
 332     }
 333     return new CellFlatMapEntry(cell);
 334   }
 335
 336   @Override
 337   public Entry<Cell, Cell> floorEntry(Cell k) {
 338     Cell cell = floorKey(k);
 339     if (cell == null) {
 340       return null;
 341     }
 342     return new CellFlatMapEntry(cell);
 343   }
 344
 345   @Override
 346   public Entry<Cell, Cell> firstEntry() {
 347     Cell cell = firstKey();
 348     if (cell == null) {
 349       return null;
 350     }
 351     return new CellFlatMapEntry(cell);
 352   }
 353
 354   @Override
 355   public Entry<Cell, Cell> lastEntry() {
 356     Cell cell = lastKey();
 357     if (cell == null) {
 358       return null;
 359     }
 360     return new CellFlatMapEntry(cell);
 361   }
 362
 363   // The following 2 methods (pollFirstEntry, pollLastEntry) are unsupported because these are updating methods.
 364   @Override
 365   public Entry<Cell, Cell> pollFirstEntry() {
 366     throw new UnsupportedOperationException();
 367   }
 368
 369   @Override
 370   public Entry<Cell, Cell> pollLastEntry() {
 371     throw new UnsupportedOperationException();
 372   }
 373
 374   // -------------------------------- Updates --------------------------------
 375   // All updating methods below are unsupported.
 376   // Assuming an array of Cells will be allocated externally,
 377   // fill up with Cells and provided in construction time.
 378   // Later the structure is immutable.
 379   @Override
 380   public Cell put(Cell k, Cell v) {
 381     throw new UnsupportedOperationException();
 382   }
 383
 384   @Override
 385   public void clear() {
 386     throw new UnsupportedOperationException();
 387   }
 388
 389   @Override
 390   public Cell remove(Object o) {
 391     throw new UnsupportedOperationException();
 392   }
 393
 394   @Override
 395   public void putAll(Map<? extends Cell, ? extends Cell> map) {
 396     throw new UnsupportedOperationException();
 397   }
 398
 399   // -------------------------------- Sub-Sets --------------------------------
 400   @Override
 401   public NavigableSet<Cell> navigableKeySet() {
 402     throw new UnsupportedOperationException();
 403   }
 404
 405   @Override
 406   public NavigableSet<Cell> descendingKeySet() {
 407     throw new UnsupportedOperationException();
 408   }
 409
 410   @Override
 411   public NavigableSet<Cell> keySet() {
 412     throw new UnsupportedOperationException();
 413   }
 414
 415   @Override
 416   public Collection<Cell> values() {
 417     return new CellFlatMapCollection();
 418   }
 419
 420   @Override
 421   public Set<Entry<Cell, Cell>> entrySet() {
 422     throw new UnsupportedOperationException();
 423   }
 424
 425
 426   // -------------------------------- Iterator K --------------------------------
 427   private final class CellFlatMapIterator implements Iterator<Cell> {
 428     int index;
 429
 430     private CellFlatMapIterator() {
 431       index = descending ? maxCellIdx-1 : minCellIdx;
 432     }
 433
 434     @Override
 435     public boolean hasNext() {
 436       return descending ? (index >= minCellIdx) : (index < maxCellIdx);
 437     }
 438
 439     @Override
 440     public Cell next() {
 441       Cell result = getCell(index);
 442       if (descending) {
 443         index--;
 444       } else {
 445         index++;
 446       }
 447       return result;
 448     }
 449
 450     @Override
 451     public void remove() {
 452       throw new UnsupportedOperationException();
 453     }
 454   }
 455
 456   // -------------------------------- Collection --------------------------------
 457   private final class CellFlatMapCollection implements Collection<Cell> {
 458
 459     @Override
 460     public int size() {
 461       return CellFlatMap.this.size();
 462     }
 463
 464     @Override
 465     public boolean isEmpty()  {
 466       return CellFlatMap.this.isEmpty();
 467     }
 468
 469     @Override
 470     public void clear()       {
 471       throw new UnsupportedOperationException();
 472     }
 473
 474     @Override
 475     public boolean contains(Object o) {
 476       return containsKey(o);
 477     }
 478
 479     @Override
 480     public Iterator<Cell> iterator() {
 481       return new CellFlatMapIterator();
 482     }
 483
 484     @Override
 485     public Object[] toArray() {
 486       throw new UnsupportedOperationException();
 487     }
 488
 489     @Override
 490     public <T> T[] toArray(T[] ts) {
 491       throw new UnsupportedOperationException();
 492     }
 493
 494     @Override
 495     public boolean add(Cell k) {
 496       throw new UnsupportedOperationException();
 497     }
 498
 499     @Override
 500     public boolean remove(Object o) {
 501       throw new UnsupportedOperationException();
 502     }
 503
 504     @Override
 505     public boolean containsAll(Collection<?> collection) {
 506       throw new UnsupportedOperationException();
 507     }
 508
 509     @Override
 510     public boolean addAll(Collection<? extends Cell> collection) {
 511       throw new UnsupportedOperationException();
 512     }
 513
 514     @Override
 515     public boolean removeAll(Collection<?> collection) {
 516       throw new UnsupportedOperationException();
 517     }
 518
 519     @Override
 520     public boolean retainAll(Collection<?> collection) {
 521       throw new UnsupportedOperationException();
 522     }
 523   }
 524 }