1 /* 2 * Copyright 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.util; 21 22 23 import com.google.common.base.Supplier; 24 25 import java.util.Comparator; 26 import java.util.Set; 27 import java.util.concurrent.ConcurrentHashMap; 28 import java.util.concurrent.ConcurrentMap; 29 import java.util.concurrent.ConcurrentSkipListSet; 30 31 import org.apache.hadoop.hbase.classification.InterfaceAudience; 32 import org.apache.hadoop.hbase.classification.InterfaceStability; 33 34 /** 35 * A simple concurrent map of sets. This is similar in concept to 36 * {@link com.google.common.collect.Multiset}, with the following exceptions: 37 * <ul> 38 * <li>The set is thread-safe and concurrent: no external locking or 39 * synchronization is required. This is important for the use case where 40 * this class is used to index cached blocks by filename for their 41 * efficient eviction from cache when the file is closed or compacted.</li> 42 * <li>The expectation is that all entries may only be removed for a key 43 * once no more additions of values are being made under that key.</li> 44 * </ul> 45 * @param <K> Key type 46 * @param <V> Value type 47 */ 48 @InterfaceAudience.Private 49 @InterfaceStability.Evolving 50 public class ConcurrentIndex<K, V> { 51 52 /** Container for the sets, indexed by key */ 53 private final ConcurrentMap<K, Set<V>> container; 54 55 /** 56 * A factory that constructs new instances of the sets if no set is 57 * associated with a given key. 58 */ 59 private final Supplier<Set<V>> valueSetFactory; 60 61 /** 62 * Creates an instance with a specified factory object for sets to be 63 * associated with a given key. 64 * @param valueSetFactory The factory instance 65 */ 66 public ConcurrentIndex(Supplier<Set<V>> valueSetFactory) { 67 this.valueSetFactory = valueSetFactory; 68 this.container = new ConcurrentHashMap<K, Set<V>>(); 69 } 70 71 /** 72 * Creates an instance using the DefaultValueSetFactory for sets, 73 * which in turn creates instances of {@link ConcurrentSkipListSet} 74 * @param valueComparator A {@link Comparator} for value types 75 */ 76 public ConcurrentIndex(Comparator<V> valueComparator) { 77 this(new DefaultValueSetFactory<V>(valueComparator)); 78 } 79 80 /** 81 * Associate a new unique value with a specified key. Under the covers, the 82 * method employs optimistic concurrency: if no set is associated with a 83 * given key, we create a new set; if another thread comes in, creates, 84 * and associates a set with the same key in the mean-time, we simply add 85 * the value to the already created set. 86 * @param key The key 87 * @param value An additional unique value we want to associate with a key 88 */ 89 public void put(K key, V value) { 90 Set<V> set = container.get(key); 91 if (set != null) { 92 set.add(value); 93 } else { 94 set = valueSetFactory.get(); 95 set.add(value); 96 Set<V> existing = container.putIfAbsent(key, set); 97 if (existing != null) { 98 // If a set is already associated with a key, that means another 99 // writer has already come in and created the set for the given key. 100 // Pursuant to an optimistic concurrency policy, in this case we will 101 // simply add the value to the existing set associated with the key. 102 existing.add(value); 103 } 104 } 105 } 106 107 /** 108 * Get all values associated with a specified key or null if no values are 109 * associated. <b>Note:</b> if the caller wishes to add or removes values 110 * to under the specified as they're iterating through the returned value, 111 * they should make a defensive copy; otherwise, a 112 * {@link java.util.ConcurrentModificationException} may be thrown. 113 * @param key The key 114 * @return All values associated with the specified key or null if no values 115 * are associated with the key. 116 */ 117 public Set<V> values(K key) { 118 return container.get(key); 119 } 120 121 /** 122 * Removes the association between a specified key and value. If as a 123 * result of removing a value a set becomes empty, we remove the given 124 * set from the mapping as well. 125 * @param key The specified key 126 * @param value The value to disassociate with the key 127 */ 128 public boolean remove(K key, V value) { 129 Set<V> set = container.get(key); 130 boolean success = false; 131 if (set != null) { 132 success = set.remove(value); 133 if (set.isEmpty()) { 134 container.remove(key); 135 } 136 } 137 return success; 138 } 139 140 /** 141 * Default factory class for the sets associated with given keys. Creates 142 * a {@link ConcurrentSkipListSet} using the comparator passed into the 143 * constructor. 144 * @see ConcurrentSkipListSet 145 * @see Supplier 146 * @param <V> The value type. Should match value type of the 147 * ConcurrentIndex instances of this object are passed to. 148 */ 149 private static class DefaultValueSetFactory<V> implements Supplier<Set<V>> { 150 private final Comparator<V> comparator; 151 152 /** 153 * Creates an instance that passes a specified comparator to the 154 * {@link ConcurrentSkipListSet} 155 * @param comparator The specified comparator 156 */ 157 public DefaultValueSetFactory(Comparator<V> comparator) { 158 this.comparator = comparator; 159 } 160 161 /** 162 * Creates a new {@link ConcurrentSkipListSet} instance using the 163 * comparator specified when the class instance was constructed. 164 * @return The instantiated {@link ConcurrentSkipListSet} object 165 */ 166 @Override 167 public Set<V> get() { 168 return new ConcurrentSkipListSet<V>(comparator); 169 } 170 } 171 }