1.1 --- a/lookup/src/main/java/org/openide/util/lookup/ArrayStorage.java Wed Jan 27 17:46:23 2010 -0500
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,477 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 1997-2009 Sun Microsystems, Inc. All rights reserved.
1.8 - *
1.9 - * The contents of this file are subject to the terms of either the GNU
1.10 - * General Public License Version 2 only ("GPL") or the Common
1.11 - * Development and Distribution License("CDDL") (collectively, the
1.12 - * "License"). You may not use this file except in compliance with the
1.13 - * License. You can obtain a copy of the License at
1.14 - * http://www.netbeans.org/cddl-gplv2.html
1.15 - * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
1.16 - * specific language governing permissions and limitations under the
1.17 - * License. When distributing the software, include this License Header
1.18 - * Notice in each file and include the License file at
1.19 - * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
1.20 - * particular file as subject to the "Classpath" exception as provided
1.21 - * by Sun in the GPL Version 2 section of the License file that
1.22 - * accompanied this code. If applicable, add the following below the
1.23 - * License Header, with the fields enclosed by brackets [] replaced by
1.24 - * your own identifying information:
1.25 - * "Portions Copyrighted [year] [name of copyright owner]"
1.26 - *
1.27 - * Contributor(s):
1.28 - *
1.29 - * The Original Software is NetBeans. The Initial Developer of the Original
1.30 - * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
1.31 - * Microsystems, Inc. All Rights Reserved.
1.32 - *
1.33 - * If you wish your version of this file to be governed by only the CDDL
1.34 - * or only the GPL Version 2, indicate your decision by adding
1.35 - * "[Contributor] elects to include this software in this distribution
1.36 - * under the [CDDL or GPL Version 2] license." If you do not indicate a
1.37 - * single choice of license, a recipient has the option to distribute
1.38 - * your version of this file under either the CDDL, the GPL Version 2 or
1.39 - * to extend the choice of license to its licensees as provided above.
1.40 - * However, if you add GPL Version 2 code and therefore, elected the GPL
1.41 - * Version 2 license, then the option applies only if the new code is
1.42 - * made subject to such option by the copyright holder.
1.43 - */
1.44 -package org.openide.util.lookup;
1.45 -
1.46 -import org.openide.util.Lookup;
1.47 -
1.48 -
1.49 -
1.50 -import java.util.*;
1.51 -import org.openide.util.lookup.AbstractLookup.Pair;
1.52 -
1.53 -
1.54 -/** ArrayStorage of Pairs from AbstractLookup.
1.55 - * @author Jaroslav Tulach
1.56 - */
1.57 -final class ArrayStorage extends Object
1.58 -implements AbstractLookup.Storage<ArrayStorage.Transaction> {
1.59 - /** default trashold */
1.60 - static final Integer DEFAULT_TRASH = new Integer(11);
1.61 -
1.62 - /** list of items */
1.63 - private Object content;
1.64 -
1.65 - /** linked list of refernces to results */
1.66 - private transient AbstractLookup.ReferenceToResult<?> results;
1.67 -
1.68 - /** Constructor
1.69 - */
1.70 - public ArrayStorage() {
1.71 - this(DEFAULT_TRASH);
1.72 - }
1.73 -
1.74 - /** Constructs new ArrayStorage */
1.75 - public ArrayStorage(Integer treshhold) {
1.76 - this.content = treshhold;
1.77 - }
1.78 -
1.79 - /** Adds an item into the tree.
1.80 - * @param item to add
1.81 - * @return true if the Item has been added for the first time or false if some other
1.82 - * item equal to this one already existed in the lookup
1.83 - */
1.84 - public boolean add(AbstractLookup.Pair<?> item, Transaction changed) {
1.85 - Object[] arr = changed.current;
1.86 -
1.87 - if (changed.arr == null) {
1.88 - // just simple add of one item
1.89 - for (int i = 0; i < arr.length; i++) {
1.90 - if (arr[i] == null) {
1.91 - arr[i] = item;
1.92 - changed.add(item);
1.93 -
1.94 - return true;
1.95 - }
1.96 -
1.97 - if (arr[i].equals(item)) {
1.98 - // reassign the item number
1.99 - item.setIndex(null, ((AbstractLookup.Pair) arr[i]).getIndex());
1.100 -
1.101 - // already there, but update it
1.102 - arr[i] = item;
1.103 -
1.104 - return false;
1.105 - }
1.106 - }
1.107 -
1.108 - // cannot happen as the beginTransaction ensured we can finish
1.109 - // correctly
1.110 - throw new IllegalStateException();
1.111 - } else {
1.112 - // doing remainAll after that, let Transaction hold the new array
1.113 - int newIndex = changed.addPair(item);
1.114 -
1.115 - for (int i = 0; i < arr.length; i++) {
1.116 - if (arr[i] == null) {
1.117 - changed.add(item);
1.118 -
1.119 - return true;
1.120 - }
1.121 -
1.122 - if (arr[i].equals(item)) {
1.123 - // already there
1.124 - if (i != newIndex) {
1.125 - // change in index
1.126 - changed.add(item);
1.127 -
1.128 - return false;
1.129 - } else {
1.130 - // no change
1.131 - return false;
1.132 - }
1.133 - }
1.134 - }
1.135 -
1.136 - // if not found in the original array
1.137 - changed.add(item);
1.138 -
1.139 - return true;
1.140 - }
1.141 - }
1.142 -
1.143 - /** Removes an item.
1.144 - */
1.145 - public void remove(AbstractLookup.Pair item, Transaction changed) {
1.146 - Object[] arr = changed.current;
1.147 - if (arr == null) {
1.148 - return;
1.149 - }
1.150 -
1.151 - int found = -1;
1.152 -
1.153 - for (int i = 0; i < arr.length;) {
1.154 - if (arr[i] == null) {
1.155 - // end of task
1.156 - return;
1.157 - }
1.158 -
1.159 - if ((found == -1) && arr[i].equals(item)) {
1.160 - // already there
1.161 - Pair<?> p = (Pair<?>)arr[i];
1.162 - p.setIndex(null, -1);
1.163 - changed.add(p);
1.164 - found = i;
1.165 - }
1.166 -
1.167 - i++;
1.168 -
1.169 - if (found != -1) {
1.170 - if (i < arr.length && !(arr[i] instanceof Integer)) {
1.171 - // moving the array
1.172 - arr[i - 1] = arr[i];
1.173 - } else {
1.174 - arr[i - 1] = null;
1.175 - }
1.176 - }
1.177 - }
1.178 - }
1.179 -
1.180 - /** Removes all items that are not present in the provided collection.
1.181 - * @param retain Pair -> AbstractLookup.Info map
1.182 - * @param notify set of Classes that has possibly changed
1.183 - */
1.184 - public void retainAll(Map retain, Transaction changed) {
1.185 - Object[] arr = changed.current;
1.186 -
1.187 - for (int from = 0; from < arr.length; from++) {
1.188 - if (!(arr[from] instanceof AbstractLookup.Pair)) {
1.189 - // end of content
1.190 - break;
1.191 - }
1.192 -
1.193 - AbstractLookup.Pair p = (AbstractLookup.Pair) arr[from];
1.194 -
1.195 - AbstractLookup.Info info = (AbstractLookup.Info) retain.get(p);
1.196 -
1.197 - if (info == null) {
1.198 - // was removed
1.199 -
1.200 - /*
1.201 - if (info != null) {
1.202 - if (info.index < arr.length) {
1.203 - newArr[info.index] = p;
1.204 - }
1.205 -
1.206 - if (p.getIndex() != info.index) {
1.207 - p.setIndex (null, info.index);
1.208 - changed.add (p);
1.209 - }
1.210 - } else {
1.211 - // removed
1.212 - */
1.213 - changed.add(p);
1.214 - }
1.215 - }
1.216 - }
1.217 -
1.218 - /** Queries for instances of given class.
1.219 - * @param clazz the class to check
1.220 - * @return enumeration of Item
1.221 - * @see #unsorted
1.222 - */
1.223 - public <T> Enumeration<Pair<T>> lookup(final Class<T> clazz) {
1.224 - if (content instanceof Object[]) {
1.225 - final Enumeration<Object> all = InheritanceTree.arrayEn((Object[]) content);
1.226 - class JustPairs implements Enumeration<Pair<T>> {
1.227 - private Pair<T> next;
1.228 -
1.229 - @SuppressWarnings("unchecked")
1.230 - private Pair<T> findNext() {
1.231 - for (;;) {
1.232 - if (next != null) {
1.233 - return next;
1.234 - }
1.235 - if (!all.hasMoreElements()) {
1.236 - return null;
1.237 - }
1.238 - Object o = all.nextElement();
1.239 - boolean ok;
1.240 - if (o instanceof AbstractLookup.Pair) {
1.241 - ok = (clazz == null) || ((AbstractLookup.Pair<?>) o).instanceOf(clazz);
1.242 - } else {
1.243 - ok = false;
1.244 - }
1.245 -
1.246 - next = ok ? (Pair<T>) o : null;
1.247 - }
1.248 - }
1.249 -
1.250 - public boolean hasMoreElements() {
1.251 - return findNext() != null;
1.252 - }
1.253 -
1.254 - public Pair<T> nextElement() {
1.255 - Pair<T> r = findNext();
1.256 - if (r == null) {
1.257 - throw new NoSuchElementException();
1.258 - }
1.259 - next = null;
1.260 - return r;
1.261 - }
1.262 - } // end of JustPairs
1.263 - return new JustPairs();
1.264 - } else {
1.265 - return InheritanceTree.emptyEn();
1.266 - }
1.267 - }
1.268 -
1.269 - /** Associates another result with this storage.
1.270 - */
1.271 - public AbstractLookup.ReferenceToResult registerReferenceToResult(AbstractLookup.ReferenceToResult<?> newRef) {
1.272 - AbstractLookup.ReferenceToResult prev = this.results;
1.273 - this.results = newRef;
1.274 -
1.275 - return prev;
1.276 - }
1.277 -
1.278 - /** Cleanup the references
1.279 - */
1.280 - public AbstractLookup.ReferenceToResult cleanUpResult(Lookup.Template<?> templ) {
1.281 - AbstractLookup.ReferenceIterator it = new AbstractLookup.ReferenceIterator(this.results);
1.282 -
1.283 - while (it.next()) {
1.284 - // empty
1.285 - }
1.286 -
1.287 - return this.results = it.first();
1.288 - }
1.289 -
1.290 - /** We use a hash set of all modified Pair to handle the transaction */
1.291 - public Transaction beginTransaction(int ensure) {
1.292 - return new Transaction(ensure, content);
1.293 - }
1.294 -
1.295 - /** Extract all results.
1.296 - */
1.297 - public void endTransaction(Transaction changed, Set<AbstractLookup.R> modified) {
1.298 - AbstractLookup.ReferenceIterator it = new AbstractLookup.ReferenceIterator(this.results);
1.299 -
1.300 - if (changed.arr == null) {
1.301 - // either add or remove, only check the content of check HashSet
1.302 - while (it.next()) {
1.303 - AbstractLookup.ReferenceToResult ref = it.current();
1.304 - Iterator<Pair<?>> pairs = changed.iterator();
1.305 -
1.306 - while (pairs.hasNext()) {
1.307 - AbstractLookup.Pair p = (AbstractLookup.Pair) pairs.next();
1.308 -
1.309 - if (AbstractLookup.matches(ref.template, p, true)) {
1.310 - modified.add(ref.getResult());
1.311 - }
1.312 - }
1.313 - }
1.314 - } else {
1.315 - // do full check of changes
1.316 - while (it.next()) {
1.317 - AbstractLookup.ReferenceToResult ref = it.current();
1.318 -
1.319 - int oldIndex = -1;
1.320 - int newIndex = -1;
1.321 -
1.322 - for (;;) {
1.323 - oldIndex = findMatching(ref.template, changed.current, oldIndex);
1.324 - newIndex = findMatching(ref.template, changed.arr, newIndex);
1.325 -
1.326 - if ((oldIndex == -1) && (newIndex == -1)) {
1.327 - break;
1.328 - }
1.329 -
1.330 - if (
1.331 - (oldIndex == -1) || (newIndex == -1) ||
1.332 - !changed.current[oldIndex].equals(changed.arr[newIndex])
1.333 - ) {
1.334 - modified.add(ref.getResult());
1.335 -
1.336 - break;
1.337 - }
1.338 - }
1.339 - }
1.340 - }
1.341 -
1.342 - this.results = it.first();
1.343 - this.content = changed.newContent(this.content);
1.344 - }
1.345 -
1.346 - private static int findMatching(Lookup.Template t, Object[] arr, int from) {
1.347 - while (++from < arr.length) {
1.348 - if (arr[from] instanceof AbstractLookup.Pair) {
1.349 - if (AbstractLookup.matches(t, (AbstractLookup.Pair) arr[from], true)) {
1.350 - return from;
1.351 - }
1.352 - }
1.353 - }
1.354 -
1.355 - return -1;
1.356 - }
1.357 -
1.358 - /** HashSet with additional field for new array which is callocated
1.359 - * in case we are doing replace to hold all new items.
1.360 - */
1.361 - static final class Transaction extends HashSet<Pair<?>> {
1.362 - /** array with current objects */
1.363 - public final Object[] current;
1.364 -
1.365 - /** array with new objects */
1.366 - public final Object[] arr;
1.367 -
1.368 - /** number of objects in the array */
1.369 - private int cnt;
1.370 -
1.371 - public Transaction(int ensure, Object currentContent) {
1.372 - Integer trashold;
1.373 - Object[] _arr;
1.374 -
1.375 - if (currentContent instanceof Integer) {
1.376 - trashold = (Integer) currentContent;
1.377 - _arr = null;
1.378 - } else {
1.379 - _arr = (Object[]) currentContent;
1.380 -
1.381 - if (_arr[_arr.length - 1] instanceof Integer) {
1.382 - trashold = (Integer) _arr[_arr.length - 1];
1.383 - } else {
1.384 - // nowhere to grow we have reached the limit
1.385 - trashold = null;
1.386 - }
1.387 - }
1.388 -
1.389 - int maxSize = (trashold == null) ? _arr.length : trashold.intValue();
1.390 -
1.391 - if (ensure > maxSize) {
1.392 - throw new UnsupportedOperationException();
1.393 - }
1.394 -
1.395 - if (ensure == -1) {
1.396 - // remove => it is ok
1.397 - this.current = currentContent instanceof Integer ? null : (Object[]) currentContent;
1.398 - this.arr = null;
1.399 -
1.400 - return;
1.401 - }
1.402 -
1.403 - if (ensure == -2) {
1.404 - // adding one
1.405 - if (_arr == null) {
1.406 - // first time add, let's allocate the array
1.407 - _arr = new Object[2];
1.408 - _arr[1] = trashold;
1.409 - } else {
1.410 - if (_arr[_arr.length - 1] instanceof AbstractLookup.Pair) {
1.411 - // we are full
1.412 - throw new UnsupportedOperationException();
1.413 - } else {
1.414 - // ensure we have allocated enough space
1.415 - if (_arr.length < 2 || _arr[_arr.length - 2] != null) {
1.416 - // double the array
1.417 - int newSize = (_arr.length - 1) * 2;
1.418 -
1.419 - if (newSize <= 1) {
1.420 - newSize = 2;
1.421 - }
1.422 -
1.423 - if (newSize > maxSize) {
1.424 - newSize = maxSize;
1.425 -
1.426 - if (newSize <= _arr.length) {
1.427 - // no space to get in
1.428 - throw new UnsupportedOperationException();
1.429 - }
1.430 -
1.431 - _arr = new Object[newSize];
1.432 - } else {
1.433 - // still a lot of space
1.434 - _arr = new Object[newSize + 1];
1.435 - _arr[newSize] = trashold;
1.436 - }
1.437 -
1.438 - // copy content of original array without the last Integer into
1.439 - // the new one
1.440 - System.arraycopy(currentContent, 0, _arr, 0, ((Object[]) currentContent).length - 1);
1.441 - }
1.442 - }
1.443 - }
1.444 -
1.445 - this.current = _arr;
1.446 - this.arr = null;
1.447 - } else {
1.448 - // allocate array for complete replacement
1.449 - if (ensure == maxSize) {
1.450 - this.arr = new Object[ensure];
1.451 - } else {
1.452 - this.arr = new Object[ensure + 1];
1.453 - this.arr[ensure] = trashold;
1.454 - }
1.455 -
1.456 - this.current = (currentContent instanceof Object[]) ? (Object[]) currentContent : new Object[0];
1.457 - }
1.458 - }
1.459 -
1.460 - public int addPair(AbstractLookup.Pair<?> p) {
1.461 - p.setIndex(null, cnt);
1.462 - arr[cnt++] = p;
1.463 -
1.464 - return p.getIndex();
1.465 - }
1.466 -
1.467 - public Object newContent(Object prev) {
1.468 - if (arr == null) {
1.469 - if (current == null) {
1.470 - return prev;
1.471 - } else {
1.472 - return current;
1.473 - }
1.474 - } else {
1.475 - return arr;
1.476 - }
1.477 - }
1.478 - }
1.479 - // end of Transaction
1.480 -}