View Javadoc

1   /**
2    * Copyright 2010 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.regionserver;
21  
22  import org.apache.hadoop.hbase.KeyValue;
23  
24  import java.util.Collection;
25  import java.util.Comparator;
26  import java.util.Iterator;
27  import java.util.Map;
28  import java.util.NavigableSet;
29  import java.util.SortedSet;
30  import java.util.concurrent.ConcurrentNavigableMap;
31  import java.util.concurrent.ConcurrentSkipListMap;
32  
33  /**
34   * A {@link java.util.Set} of {@link KeyValue}s implemented on top of a
35   * {@link java.util.concurrent.ConcurrentSkipListMap}.  Works like a
36   * {@link java.util.concurrent.ConcurrentSkipListSet} in all but one regard:
37   * An add will overwrite if already an entry for the added key.  In other words,
38   * where CSLS does "Adds the specified element to this set if it is not already
39   * present.", this implementation "Adds the specified element to this set EVEN
40   * if it is already present overwriting what was there previous".  The call to
41   * add returns true if no value in the backing map or false if there was an
42   * entry with same key (though value may be different).
43   * <p>Otherwise,
44   * has same attributes as ConcurrentSkipListSet: e.g. tolerant of concurrent
45   * get and set and won't throw ConcurrentModificationException when iterating.
46   */
47  class KeyValueSkipListSet implements NavigableSet<KeyValue> {
48    private final ConcurrentNavigableMap<KeyValue, KeyValue> delegatee;
49  
50    KeyValueSkipListSet(final KeyValue.KVComparator c) {
51      this.delegatee = new ConcurrentSkipListMap<KeyValue, KeyValue>(c);
52    }
53  
54    KeyValueSkipListSet(final ConcurrentNavigableMap<KeyValue, KeyValue> m) {
55      this.delegatee = m;
56    }
57  
58    /**
59     * Iterator that maps Iterator calls to return the value component of the
60     * passed-in Map.Entry Iterator.
61     */
62    static class MapEntryIterator implements Iterator<KeyValue> {
63      private final Iterator<Map.Entry<KeyValue, KeyValue>> iterator;
64  
65      MapEntryIterator(final Iterator<Map.Entry<KeyValue, KeyValue>> i) {
66        this.iterator = i;
67      }
68  
69      public boolean hasNext() {
70        return this.iterator.hasNext();
71      }
72  
73      public KeyValue next() {
74        return this.iterator.next().getValue();
75      }
76  
77      public void remove() {
78        this.iterator.remove();
79      }
80    }
81  
82    public KeyValue ceiling(KeyValue e) {
83      throw new UnsupportedOperationException("Not implemented");
84    }
85  
86    public Iterator<KeyValue> descendingIterator() {
87      return new MapEntryIterator(this.delegatee.descendingMap().entrySet().
88        iterator());
89    }
90  
91    public NavigableSet<KeyValue> descendingSet() {
92      throw new UnsupportedOperationException("Not implemented");
93    }
94  
95    public KeyValue floor(KeyValue e) {
96      throw new UnsupportedOperationException("Not implemented");
97    }
98  
99    public SortedSet<KeyValue> headSet(final KeyValue toElement) {
100     return headSet(toElement, false);
101   }
102 
103   public NavigableSet<KeyValue> headSet(final KeyValue toElement,
104       boolean inclusive) {
105     return new KeyValueSkipListSet(this.delegatee.headMap(toElement, inclusive));
106   }
107 
108   public KeyValue higher(KeyValue e) {
109     throw new UnsupportedOperationException("Not implemented");
110   }
111 
112   public Iterator<KeyValue> iterator() {
113     return new MapEntryIterator(this.delegatee.entrySet().iterator());
114   }
115 
116   public KeyValue lower(KeyValue e) {
117     throw new UnsupportedOperationException("Not implemented");
118   }
119 
120   public KeyValue pollFirst() {
121     throw new UnsupportedOperationException("Not implemented");
122   }
123 
124   public KeyValue pollLast() {
125     throw new UnsupportedOperationException("Not implemented");
126   }
127 
128   public SortedSet<KeyValue> subSet(KeyValue fromElement, KeyValue toElement) {
129     throw new UnsupportedOperationException("Not implemented");
130   }
131 
132   public NavigableSet<KeyValue> subSet(KeyValue fromElement,
133       boolean fromInclusive, KeyValue toElement, boolean toInclusive) {
134     throw new UnsupportedOperationException("Not implemented");
135   }
136 
137   public SortedSet<KeyValue> tailSet(KeyValue fromElement) {
138     return tailSet(fromElement, true);
139   }
140 
141   public NavigableSet<KeyValue> tailSet(KeyValue fromElement, boolean inclusive) {
142     return new KeyValueSkipListSet(this.delegatee.tailMap(fromElement, inclusive));
143   }
144 
145   public Comparator<? super KeyValue> comparator() {
146     throw new UnsupportedOperationException("Not implemented");
147   }
148 
149   public KeyValue first() {
150     return this.delegatee.get(this.delegatee.firstKey());
151   }
152 
153   public KeyValue last() {
154     return this.delegatee.get(this.delegatee.lastKey());
155   }
156 
157   public boolean add(KeyValue e) {
158     return this.delegatee.put(e, e) == null;
159   }
160 
161   public boolean addAll(Collection<? extends KeyValue> c) {
162     throw new UnsupportedOperationException("Not implemented");
163   }
164 
165   public void clear() {
166     this.delegatee.clear();
167   }
168 
169   public boolean contains(Object o) {
170     //noinspection SuspiciousMethodCalls
171     return this.delegatee.containsKey(o);
172   }
173 
174   public boolean containsAll(Collection<?> c) {
175     throw new UnsupportedOperationException("Not implemented");
176   }
177 
178   public boolean isEmpty() {
179     return this.delegatee.isEmpty();
180   }
181 
182   public boolean remove(Object o) {
183     return this.delegatee.remove(o) != null;
184   }
185 
186   public boolean removeAll(Collection<?> c) {
187     throw new UnsupportedOperationException("Not implemented");
188   }
189 
190   public boolean retainAll(Collection<?> c) {
191     throw new UnsupportedOperationException("Not implemented");
192   }
193 
194   public int size() {
195     return this.delegatee.size();
196   }
197 
198   public Object[] toArray() {
199     throw new UnsupportedOperationException("Not implemented");
200   }
201 
202   public <T> T[] toArray(T[] a) {
203     throw new UnsupportedOperationException("Not implemented");
204   }
205 }