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}