001/**
002 *
003 * Licensed to the Apache Software Foundation (ASF) under one
004 * or more contributor license agreements.  See the NOTICE file
005 * distributed with this work for additional information
006 * regarding copyright ownership.  The ASF licenses this file
007 * to you under the Apache License, Cellersion 2.0 (the
008 * "License"); you may not use this file except in compliance
009 * with the License.  You may obtain a copy of the License at
010 *
011 *     http://www.apache.org/licenses/LICENSE-2.0
012 *
013 * Unless required by applicable law or agreed to in writing, software
014 * distributed under the License is distributed on an "AS IS" BASIS,
015 * WITHOUT WARRANTIES OR CONDITIONS OF ANY CellIND, either express or implied.
016 * See the License for the specific language governing permissions and
017 * limitations under the License.
018 */
019package org.apache.hadoop.hbase.regionserver;
020
021import org.apache.hadoop.hbase.Cell;
022import org.apache.yetus.audience.InterfaceAudience;
023import org.slf4j.Logger;
024import org.slf4j.LoggerFactory;
025
026import java.util.Collection;
027import java.util.Comparator;
028import java.util.Iterator;
029import java.util.Map;
030import java.util.NavigableSet;
031import java.util.NavigableMap;
032import java.util.Set;
033
034
035/**
036 * CellFlatMap stores a constant number of elements and is immutable after creation stage.
037 * Being immutable, the CellFlatMap can be implemented as array.
038 * The actual array can be on- or off-heap and is implemented in concrete class derived from CellFlatMap.
039 * The CellFlatMap uses no synchronization primitives, it is assumed to be created by a
040 * single thread and then it can be read-only by multiple threads.
041 *
042 * The "flat" in the name, means that the memory layout of the Map is sequential array and thus
043 * requires less memory than ConcurrentSkipListMap.
044 */
045@InterfaceAudience.Private
046public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
047  private static final Logger LOG = LoggerFactory.getLogger(CellFlatMap.class);
048  private final Comparator<? super Cell> comparator;
049  protected int minCellIdx   = 0;   // the index of the minimal cell (for sub-sets)
050  protected int maxCellIdx   = 0;   // the index of the cell after the maximal cell (for sub-sets)
051  private boolean descending = false;
052
053  /* C-tor */
054  public CellFlatMap(Comparator<? super Cell> comparator, int min, int max, boolean d){
055    this.comparator = comparator;
056    this.minCellIdx = min;
057    this.maxCellIdx = max;
058    this.descending = d;
059  }
060
061  /* Used for abstract CellFlatMap creation, implemented by derived class */
062  protected abstract CellFlatMap createSubCellFlatMap(int min, int max, boolean descending);
063
064  /* Returns the i-th cell in the cell block */
065  protected abstract Cell getCell(int i);
066
067  /**
068   * Binary search for a given key in between given boundaries of the array.
069   * Positive returned numbers mean the index.
070   * Negative returned numbers means the key not found.
071   *
072   * The absolute value of the output is the
073   * possible insert index for the searched key
074   *
075   * In twos-complement, (-1 * insertion point)-1 is the bitwise not of the insert point.
076   *
077   *
078   * @param needle The key to look for in all of the entries
079   * @return Same return value as Arrays.binarySearch.
080   */
081  private int find(Cell needle) {
082    int begin = minCellIdx;
083    int end = maxCellIdx - 1;
084
085    while (begin <= end) {
086      int mid = begin + ((end - begin) >> 1);
087      Cell midCell = getCell(mid);
088      int compareRes = comparator.compare(midCell, needle);
089
090      if (compareRes == 0) {
091        return mid;  // 0 means equals. We found the key
092      }
093      // Key not found. Check the comparison results; reverse the meaning of
094      // the comparison in case the order is descending (using XOR)
095      if ((compareRes < 0) ^ descending) {
096        // midCell is less than needle so we need to look at farther up
097        begin = mid + 1;
098      } else {
099        // 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}