001/* 002 * CDDL HEADER START 003 * 004 * The contents of this file are subject to the terms of the 005 * Common Development and Distribution License, Version 1.0 only 006 * (the "License"). You may not use this file except in compliance 007 * with the License. 008 * 009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt 010 * or http://forgerock.org/license/CDDLv1.0.html. 011 * See the License for the specific language governing permissions 012 * and limitations under the License. 013 * 014 * When distributing Covered Code, include this CDDL HEADER in each 015 * file and include the License file at legal-notices/CDDLv1_0.txt. 016 * If applicable, add the following below this CDDL HEADER, with the 017 * fields enclosed by brackets "[]" replaced with your own identifying 018 * information: 019 * Portions Copyright [yyyy] [name of copyright owner] 020 * 021 * CDDL HEADER END 022 * 023 * Copyright 2014-2015 ForgeRock AS 024 */ 025package org.opends.server.types; 026 027import java.util.*; 028 029/** 030 * A small map of values. This map implementation is optimized to use as little 031 * memory as possible in the case where there zero or one elements. In addition, 032 * any normalization of entries is delayed until the second entry is added 033 * (normalization may be triggered by invoking {@link Object#hashCode()} or 034 * {@link Object#equals(Object)}. 035 * <p> 036 * Null keys are not supported by this map. 037 * 038 * @param <K> 039 * the type of keys maintained by this map 040 * @param <V> 041 * the type of mapped values 042 */ 043public class SmallMap<K, V> extends AbstractMap<K, V> 044{ 045 046 /** The map of entries if there are more than one. */ 047 private LinkedHashMap<K, V> entries; 048 049 /** The first key of the Map. */ 050 private K firstKey; 051 /** The first value of the Map. */ 052 private V firstValue; 053 054 055 /** Creates a new small map which is initially empty. */ 056 public SmallMap() 057 { 058 // No implementation required. 059 } 060 061 private void rejectIfNull(Object key) 062 { 063 if (key == null) 064 { 065 throw new NullPointerException("null keys are not allowed"); 066 } 067 } 068 069 /** {@inheritDoc} */ 070 @Override 071 public V get(Object key) 072 { 073 rejectIfNull(key); 074 if (entries != null) 075 { // >= 2 entries case 076 return entries.get(key); 077 } 078 // 0 and 1 case 079 if (firstKey != null && firstKey.equals(key)) 080 { 081 return firstValue; 082 } 083 return null; 084 } 085 086 /** {@inheritDoc} */ 087 @Override 088 public V put(K key, V value) 089 { 090 rejectIfNull(key); 091 if (entries != null) 092 { // >= 2 entries case 093 return entries.put(key, value); 094 } 095 if (firstKey == null) 096 { // 0 entries case 097 firstKey = key; 098 firstValue = value; 099 return null; 100 } 101 // 1 entry case 102 if (firstKey.equals(key)) 103 { // replace value 104 V oldValue = firstValue; 105 firstValue = value; 106 return oldValue; 107 } 108 // overflow to the underlying map 109 entries = new LinkedHashMap<>(2); 110 entries.put(firstKey, firstValue); 111 firstKey = null; 112 firstValue = null; 113 return entries.put(key, value); 114 } 115 116 /** {@inheritDoc} */ 117 @Override 118 public void putAll(Map<? extends K, ? extends V> m) 119 { 120 for (Entry<? extends K, ? extends V> entry : m.entrySet()) 121 { 122 put(entry.getKey(), entry.getValue()); 123 } 124 } 125 126 /** {@inheritDoc} */ 127 @Override 128 public V remove(Object key) 129 { 130 if (entries != null) 131 { 132 // Note: if there is one or zero values left we could stop using the map. 133 // However, lets assume that if the map was multi-valued before 134 // then it may become multi-valued again. 135 return entries.remove(key); 136 } 137 138 if (firstKey != null && firstKey.equals(key)) 139 { 140 V oldV = firstValue; 141 firstKey = null; 142 firstValue = null; 143 return oldV; 144 } 145 return null; 146 } 147 148 /** {@inheritDoc} */ 149 @Override 150 public boolean containsKey(Object key) 151 { 152 rejectIfNull(key); 153 if (entries != null) 154 { 155 return entries.containsKey(key); 156 } 157 return firstKey != null && firstKey.equals(key); 158 } 159 160 /** {@inheritDoc} */ 161 @Override 162 public boolean containsValue(Object value) 163 { 164 if (entries != null) 165 { 166 return entries.containsValue(value); 167 } 168 if (firstKey == null) 169 { 170 return false; 171 } 172 if (firstValue == null) 173 { 174 return value == null; 175 } 176 return firstValue.equals(value); 177 } 178 179 /** {@inheritDoc} */ 180 @Override 181 public void clear() 182 { 183 firstKey = null; 184 firstValue = null; 185 entries = null; 186 } 187 188 /** {@inheritDoc} */ 189 @Override 190 public int size() 191 { 192 if (entries != null) 193 { 194 return entries.size(); 195 } 196 return firstKey != null ? 1 : 0; 197 } 198 199 /** {@inheritDoc} */ 200 @Override 201 public Set<Entry<K, V>> entrySet() 202 { 203 if (entries != null) 204 { 205 return entries.entrySet(); 206 } 207 if (firstKey == null) 208 { 209 return Collections.emptySet(); 210 } 211 212 return new AbstractSet<Entry<K, V>>() 213 { 214 215 @Override 216 public Iterator<Entry<K, V>> iterator() 217 { 218 return new Iterator<Entry<K, V>>() 219 { 220 221 private boolean isFirst = true; 222 223 @Override 224 public boolean hasNext() 225 { 226 return isFirst; 227 } 228 229 @Override 230 public Entry<K, V> next() 231 { 232 if (!isFirst) 233 { 234 throw new NoSuchElementException(); 235 } 236 isFirst = false; 237 return new SimpleEntry<>(firstKey, firstValue); 238 } 239 240 @Override 241 public void remove() 242 { 243 firstKey = null; 244 firstValue = null; 245 } 246 }; 247 } 248 249 @Override 250 public int size() 251 { 252 return 1; 253 } 254 }; 255 } 256 257}