1 /******************************************************************************* 2 * Copyright (c) 2009, 2018 IBM Corporation and others. 3 * 4 * This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * which accompanies this distribution, and is available at 7 * https://www.eclipse.org/legal/epl-2.0/ 8 * 9 * SPDX-License-Identifier: EPL-2.0 10 * 11 * Contributors: 12 * IBM Corporation - initial API and implementation 13 * Cloudsmith Inc. - rewrite for smaller memory footprint 14 *******************************************************************************/ 15 package org.eclipse.equinox.internal.p2.metadata; 16 17 import java.util.Collection; 18 import java.util.Collections; 19 import java.util.HashMap; 20 import java.util.Iterator; 21 import java.util.Map; 22 import java.util.Map.Entry; 23 import java.util.NoSuchElementException; 24 import org.eclipse.equinox.internal.p2.core.helpers.CollectionUtils; 25 import org.eclipse.equinox.p2.core.IPool; 26 import org.eclipse.equinox.p2.metadata.IInstallableUnit; 27 import org.eclipse.equinox.p2.metadata.Version; 28 import org.eclipse.equinox.p2.query.CollectionResult; 29 import org.eclipse.equinox.p2.query.Collector; 30 import org.eclipse.equinox.p2.query.IQuery; 31 import org.eclipse.equinox.p2.query.IQueryResult; 32 import org.eclipse.equinox.p2.query.QueryUtil; 33 34 /** 35 * A map that stores {@link IInstallableUnit} instances in a way that is efficient to query 36 */ 37 public class IUMap implements Cloneable { 38 /** 39 * Iterator over all the {@link IInstallableUnit} instances in the map. 40 */ 41 public class MapIterator implements Iterator<IInstallableUnit> { 42 //iterator over the keys in UIMap 43 private final Iterator<Object> unitIterator; 44 private IInstallableUnit[] currentBucket; 45 private int bucketIndex = 0; 46 private IInstallableUnit nextElement = null; 47 MapIterator()48 MapIterator() { 49 super(); 50 unitIterator = units.values().iterator(); 51 } 52 53 @Override hasNext()54 public boolean hasNext() { 55 return positionNext(); 56 } 57 58 @Override next()59 public IInstallableUnit next() { 60 if (!positionNext()) 61 throw new NoSuchElementException(); 62 63 IInstallableUnit nxt = nextElement; 64 nextElement = null; 65 return nxt; 66 } 67 68 @Override remove()69 public void remove() { 70 throw new UnsupportedOperationException(); 71 } 72 positionNext()73 private boolean positionNext() { 74 if (nextElement != null) 75 return true; 76 77 if (currentBucket != null) { 78 nextElement = currentBucket[bucketIndex]; 79 if (++bucketIndex == currentBucket.length) { 80 currentBucket = null; 81 bucketIndex = -1; 82 } 83 return true; 84 } 85 86 if (!unitIterator.hasNext()) 87 return false; 88 89 Object val = unitIterator.next(); 90 if (val instanceof IInstallableUnit) 91 nextElement = (IInstallableUnit) val; 92 else { 93 currentBucket = (IInstallableUnit[]) val; 94 nextElement = currentBucket[0]; 95 bucketIndex = 1; 96 } 97 return true; 98 } 99 } 100 101 /** 102 * Map<String,Object> mapping IU id to either arrays of iu's or a single iu with that id. 103 */ 104 final Map<String, Object> units = new HashMap<>(); 105 IUMap()106 public IUMap() { 107 // 108 } 109 IUMap(IUMap cloneSource)110 private IUMap(IUMap cloneSource) { 111 units.putAll(cloneSource.units); 112 } 113 add(IInstallableUnit unit)114 public void add(IInstallableUnit unit) { 115 String key = unit.getId(); 116 Object matching = units.get(key); 117 if (matching == null) { 118 units.put(key, unit); 119 return; 120 } 121 122 // We already had something at this key position. It must be 123 // preserved. 124 if (matching.getClass().isArray()) { 125 // Entry is an array. Add unique 126 IInstallableUnit[] iuArr = (IInstallableUnit[]) matching; 127 int idx = iuArr.length; 128 while (--idx >= 0) 129 if (iuArr[idx].equals(unit)) 130 // This unit has already been added 131 return; 132 133 IInstallableUnit[] iuArrPlus = new IInstallableUnit[iuArr.length + 1]; 134 System.arraycopy(iuArr, 0, iuArrPlus, 0, iuArr.length); 135 iuArrPlus[iuArr.length] = unit; 136 units.put(unit.getId(), iuArrPlus); 137 } else { 138 IInstallableUnit old = (IInstallableUnit) matching; 139 if (!old.equals(unit)) 140 units.put(key, new IInstallableUnit[] {old, unit}); 141 } 142 } 143 addAll(IInstallableUnit[] toAdd)144 public void addAll(IInstallableUnit[] toAdd) { 145 for (IInstallableUnit toAdd1 : toAdd) { 146 add(toAdd1); 147 } 148 } 149 addAll(Collection<IInstallableUnit> toAdd)150 public void addAll(Collection<IInstallableUnit> toAdd) { 151 for (IInstallableUnit unit : toAdd) { 152 add(unit); 153 } 154 } 155 clear()156 public void clear() { 157 units.clear(); 158 } 159 160 @Override clone()161 public IUMap clone() { 162 return new IUMap(this); 163 } 164 iterator()165 public Iterator<IInstallableUnit> iterator() { 166 return new MapIterator(); 167 } 168 contains(IInstallableUnit unit)169 public boolean contains(IInstallableUnit unit) { 170 return !internalGet(unit.getId(), unit.getVersion()).isEmpty(); 171 } 172 173 /** 174 * Returns a collection of units that has the given <code>id</code>. 175 * @param id The id of the desired units. Must not be <code>null</code>. 176 * @return The units corresponding to the given <code>id</code>. 177 */ getUnits(String id)178 public Collection<IInstallableUnit> getUnits(String id) { 179 Object bucket = units.get(id); 180 if (bucket == null) 181 return Collections.emptyList(); 182 return bucket.getClass().isArray() ? CollectionUtils.unmodifiableList((IInstallableUnit[]) bucket) : Collections.singletonList((IInstallableUnit) bucket); 183 } 184 get(String id)185 public IQueryResult<IInstallableUnit> get(String id) { 186 return internalGet(id, null); 187 } 188 internalGet(String id, Version version)189 private IQueryResult<IInstallableUnit> internalGet(String id, Version version) { 190 if (id == null) { 191 IQuery<IInstallableUnit> query = version == null ? QueryUtil.createIUAnyQuery() : QueryUtil.createIUQuery(null, version); 192 return query.perform(iterator()); 193 } 194 195 Collection<IInstallableUnit> idUnits = getUnits(id); 196 if (idUnits.isEmpty()) 197 return Collector.emptyCollector(); 198 return version == null ? new CollectionResult<>(idUnits) : QueryUtil.createIUQuery(id, version).perform(idUnits.iterator()); 199 } 200 get(String id, Version version)201 public IInstallableUnit get(String id, Version version) { 202 IQueryResult<IInstallableUnit> result = internalGet(id, version); 203 return result.isEmpty() ? null : result.iterator().next(); 204 } 205 remove(IInstallableUnit unit)206 public void remove(IInstallableUnit unit) { 207 String key = unit.getId(); 208 Object matching = units.get(key); 209 if (matching == null) 210 return; 211 212 if (matching instanceof IInstallableUnit) { 213 if (matching.equals(unit)) 214 units.remove(key); 215 return; 216 } 217 218 IInstallableUnit[] array = (IInstallableUnit[]) matching; 219 int idx = array.length; 220 while (--idx >= 0) { 221 if (unit.equals(array[idx])) { 222 if (array.length == 2) { 223 // We no longer need this array. Replace it with the 224 // entry that we keep. 225 units.put(key, idx == 0 ? array[1] : array[0]); 226 break; 227 } 228 229 // Shrink the array 230 IInstallableUnit[] newArray = new IInstallableUnit[array.length - 1]; 231 if (idx > 0) 232 System.arraycopy(array, 0, newArray, 0, idx); 233 if (idx + 1 < array.length) 234 System.arraycopy(array, idx + 1, newArray, idx, array.length - (idx + 1)); 235 units.put(key, newArray); 236 break; 237 } 238 } 239 } 240 removeAll(Collection<IInstallableUnit> toRemove)241 public void removeAll(Collection<IInstallableUnit> toRemove) { 242 for (IInstallableUnit iu : toRemove) 243 remove(iu); 244 } 245 246 /** 247 * Replace all instances of the IInstallableUnits in the receiver 248 * with the shared IInstallableUnits from the provided iuPool. 249 * This operation is a no-op if iuPool is null. 250 * 251 * @param iuPool an IPool containing the shared IInstallableUnits 252 */ compress(IPool<IInstallableUnit> iuPool)253 public void compress(IPool<IInstallableUnit> iuPool) { 254 if (iuPool == null) { 255 return; 256 } 257 258 Iterator<Entry<String, Object>> entries = units.entrySet().iterator(); 259 while (entries.hasNext()) { 260 Entry<String, Object> entry = entries.next(); 261 Object value = entry.getValue(); 262 if (value.getClass().isArray()) { 263 IInstallableUnit[] array = (IInstallableUnit[]) value; 264 for (int i = 0; i < array.length; i++) { 265 array[i] = iuPool.add(array[i]); 266 } 267 } else { 268 entry.setValue(iuPool.add((IInstallableUnit) value)); 269 } 270 } 271 } 272 } 273