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, Version 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 KIND, 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 java.util.Collection; 022import java.util.Comparator; 023import java.util.Iterator; 024import java.util.NavigableSet; 025import java.util.NavigableMap; 026import java.util.SortedSet; 027import java.util.concurrent.ConcurrentSkipListMap; 028 029import org.apache.hadoop.hbase.Cell; 030import org.apache.hadoop.hbase.CellComparator; 031import org.apache.hadoop.hbase.HConstants; 032import org.apache.yetus.audience.InterfaceAudience; 033 034/** 035 * A {@link java.util.Set} of {@link Cell}s, where an add will overwrite the entry if already 036 * exists in the set. The call to add returns true if no value in the backing map or false if 037 * there was an entry with same key (though value may be different). 038 * implementation is tolerant of concurrent get and set and won't throw 039 * ConcurrentModificationException when iterating. 040 */ 041@InterfaceAudience.Private 042public class CellSet implements NavigableSet<Cell> { 043 044 public static final int UNKNOWN_NUM_UNIQUES = -1; 045 // Implemented on top of a {@link java.util.concurrent.ConcurrentSkipListMap} 046 // Differ from CSLS in one respect, where CSLS does "Adds the specified element to this set if it 047 // is not already present.", this implementation "Adds the specified element to this set EVEN 048 // if it is already present overwriting what was there previous". 049 // Otherwise, has same attributes as ConcurrentSkipListSet 050 private final NavigableMap<Cell, Cell> delegatee; /// 051 052 private final int numUniqueKeys; 053 054 public CellSet(final CellComparator c) { 055 this.delegatee = new ConcurrentSkipListMap<>(c.getSimpleComparator()); 056 this.numUniqueKeys = UNKNOWN_NUM_UNIQUES; 057 } 058 059 CellSet(final NavigableMap<Cell, Cell> m, int numUniqueKeys) { 060 this.delegatee = m; 061 this.numUniqueKeys = numUniqueKeys; 062 } 063 064 CellSet(final NavigableMap<Cell, Cell> m) { 065 this.delegatee = m; 066 this.numUniqueKeys = UNKNOWN_NUM_UNIQUES; 067 } 068 069 NavigableMap<Cell, Cell> getDelegatee() { 070 return delegatee; 071 } 072 073 @Override 074 public Cell ceiling(Cell e) { 075 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 076 } 077 078 @Override 079 public Iterator<Cell> descendingIterator() { 080 return this.delegatee.descendingMap().values().iterator(); 081 } 082 083 @Override 084 public NavigableSet<Cell> descendingSet() { 085 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 086 } 087 088 @Override 089 public Cell floor(Cell e) { 090 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 091 } 092 093 @Override 094 public SortedSet<Cell> headSet(final Cell toElement) { 095 return headSet(toElement, false); 096 } 097 098 @Override 099 public NavigableSet<Cell> headSet(final Cell toElement, 100 boolean inclusive) { 101 return new CellSet(this.delegatee.headMap(toElement, inclusive), UNKNOWN_NUM_UNIQUES); 102 } 103 104 @Override 105 public Cell higher(Cell e) { 106 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 107 } 108 109 @Override 110 public Iterator<Cell> iterator() { 111 return this.delegatee.values().iterator(); 112 } 113 114 @Override 115 public Cell lower(Cell e) { 116 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 117 } 118 119 @Override 120 public Cell pollFirst() { 121 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 122 } 123 124 @Override 125 public Cell pollLast() { 126 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 127 } 128 129 @Override 130 public SortedSet<Cell> subSet(Cell fromElement, Cell toElement) { 131 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 132 } 133 134 @Override 135 public NavigableSet<Cell> subSet(Cell fromElement, 136 boolean fromInclusive, Cell toElement, boolean toInclusive) { 137 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 138 } 139 140 @Override 141 public SortedSet<Cell> tailSet(Cell fromElement) { 142 return tailSet(fromElement, true); 143 } 144 145 @Override 146 public NavigableSet<Cell> tailSet(Cell fromElement, boolean inclusive) { 147 return new CellSet(this.delegatee.tailMap(fromElement, inclusive), UNKNOWN_NUM_UNIQUES); 148 } 149 150 @Override 151 public Comparator<? super Cell> comparator() { 152 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 153 } 154 155 @Override 156 public Cell first() { 157 return this.delegatee.firstEntry().getValue(); 158 } 159 160 @Override 161 public Cell last() { 162 return this.delegatee.lastEntry().getValue(); 163 } 164 165 @Override 166 public boolean add(Cell e) { 167 return this.delegatee.put(e, e) == null; 168 } 169 170 @Override 171 public boolean addAll(Collection<? extends Cell> c) { 172 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 173 } 174 175 @Override 176 public void clear() { 177 this.delegatee.clear(); 178 } 179 180 @Override 181 public boolean contains(Object o) { 182 //noinspection SuspiciousMethodCalls 183 return this.delegatee.containsKey(o); 184 } 185 186 @Override 187 public boolean containsAll(Collection<?> c) { 188 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 189 } 190 191 @Override 192 public boolean isEmpty() { 193 return this.delegatee.isEmpty(); 194 } 195 196 @Override 197 public boolean remove(Object o) { 198 return this.delegatee.remove(o) != null; 199 } 200 201 @Override 202 public boolean removeAll(Collection<?> c) { 203 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 204 } 205 206 @Override 207 public boolean retainAll(Collection<?> c) { 208 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 209 } 210 211 public Cell get(Cell kv) { 212 return this.delegatee.get(kv); 213 } 214 215 @Override 216 public int size() { 217 if (delegatee instanceof ConcurrentSkipListMap) { 218 throw new UnsupportedOperationException("ConcurrentSkipListMap.size() is time-consuming"); 219 } 220 return this.delegatee.size(); 221 } 222 223 @Override 224 public Object[] toArray() { 225 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 226 } 227 228 @Override 229 public <T> T[] toArray(T[] a) { 230 throw new UnsupportedOperationException(HConstants.NOT_IMPLEMENTED); 231 } 232 233 public int getNumUniqueKeys() { 234 return numUniqueKeys; 235 } 236}