001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: * The Original Software is NetBeans. The Initial Developer of the Original
026: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
027: * Microsystems, Inc. All Rights Reserved.
028: *
029: * If you wish your version of this file to be governed by only the CDDL
030: * or only the GPL Version 2, indicate your decision by adding
031: * "[Contributor] elects to include this software in this distribution
032: * under the [CDDL or GPL Version 2] license." If you do not indicate a
033: * single choice of license, a recipient has the option to distribute
034: * your version of this file under either the CDDL, the GPL Version 2 or
035: * to extend the choice of license to its licensees as provided above.
036: * However, if you add GPL Version 2 code and therefore, elected the GPL
037: * Version 2 license, then the option applies only if the new code is
038: * made subject to such option by the copyright holder.
039: */
040:
041: package org.netbeans.lib.profiler.utils;
042:
043: import java.util.Iterator;
044:
045: /*
046: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
047: *
048: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
049: *
050: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
051: *
052: * The contents of this file are subject to the terms of either the GNU
053: * General Public License Version 2 only ("GPL") or the Common
054: * Development and Distribution License("CDDL") (collectively, the
055: * "License"). You may not use this file except in compliance with the
056: * License. You can obtain a copy of the License at
057: * http://www.netbeans.org/cddl-gplv2.html
058: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
059: * specific language governing permissions and limitations under the
060: * License. When distributing the software, include this License Header
061: * Notice in each file and include the License file at
062: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
063: * particular file as subject to the "Classpath" exception as provided
064: * by Sun in the GPL Version 2 section of the License file that
065: * accompanied this code. If applicable, add the following below the
066: * License Header, with the fields enclosed by brackets [] replaced by
067: * your own identifying information:
068: * "Portions Copyrighted [year] [name of copyright owner]"
069: *
070: * Contributor(s):
071: *
072: * The Original Software is NetBeans. The Initial Developer of the Original
073: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
074: * Microsystems, Inc. All Rights Reserved.
075: *
076: * If you wish your version of this file to be governed by only the CDDL
077: * or only the GPL Version 2, indicate your decision by adding
078: * "[Contributor] elects to include this software in this distribution
079: * under the [CDDL or GPL Version 2] license." If you do not indicate a
080: * single choice of license, a recipient has the option to distribute
081: * your version of this file under either the CDDL, the GPL Version 2 or
082: * to extend the choice of license to its licensees as provided above.
083: * However, if you add GPL Version 2 code and therefore, elected the GPL
084: * Version 2 license, then the option applies only if the new code is
085: * made subject to such option by the copyright holder.
086: */
087:
088: /**
089: *
090: * @author Jaroslav Bachorik
091: */
092: public class ImmutableList implements Iterable {
093: //~ Inner Classes ------------------------------------------------------------------------------------------------------------
094:
095: private class InnerIterator implements Iterator {
096: //~ Instance fields ------------------------------------------------------------------------------------------------------
097:
098: private int counter;
099:
100: //~ Constructors ---------------------------------------------------------------------------------------------------------
101:
102: public InnerIterator() {
103: counter = 0;
104: }
105:
106: //~ Methods --------------------------------------------------------------------------------------------------------------
107:
108: public boolean hasNext() {
109: return counter < size;
110: }
111:
112: public Object next() {
113: return get(counter++);
114: }
115:
116: public void remove() {
117: // do nothing
118: }
119: }
120:
121: private static final class LoadFactor {
122: //~ Static fields/initializers -------------------------------------------------------------------------------------------
123:
124: public static final float DEFAULT_FACTOR = 0.01f;
125:
126: //~ Instance fields ------------------------------------------------------------------------------------------------------
127:
128: public final float factor;
129: public final int upperLimit;
130:
131: //~ Constructors ---------------------------------------------------------------------------------------------------------
132:
133: public LoadFactor(final int upperLimit, final float loadFactor) {
134: this .upperLimit = upperLimit;
135: this .factor = loadFactor;
136: }
137: }
138:
139: //~ Static fields/initializers -----------------------------------------------------------------------------------------------
140:
141: private static final LoadFactor[] distributionMap = new LoadFactor[] {
142: new LoadFactor(2, 3f), new LoadFactor(6, 0.3f),
143: new LoadFactor(10, 0.5f), new LoadFactor(50, 0.1f) };
144:
145: //~ Instance fields ----------------------------------------------------------------------------------------------------------
146:
147: private final Object slotsGuard = new Object();
148:
149: // @GuardedBy slotsGuard
150: private int[] slotLimits;
151:
152: // @GuardedBy slotsGuard
153: private Object[] storageSlots;
154: private float loadFactor;
155:
156: // @GuardedBy slotsGuard
157: private int availableSize;
158:
159: // @GuardedBy slotsGuard
160: private int currentIndex;
161:
162: // @GuardedBy slotsGuard
163: private int currentSlot;
164: private int initialSize;
165: private int size;
166:
167: // @GuardedBy slotsGuard
168: private int slotCount;
169: private int slotInitialSize;
170:
171: //~ Constructors -------------------------------------------------------------------------------------------------------------
172:
173: /** Creates a new instance of DynamicList */
174: public ImmutableList() {
175: initialSize = 1;
176: slotInitialSize = 1;
177: loadFactor = 1.75f;
178:
179: reset();
180: }
181:
182: //~ Methods ------------------------------------------------------------------------------------------------------------------
183:
184: public void add(Object item) {
185: synchronized (slotsGuard) {
186: accomodate(++size);
187: ((Object[]) storageSlots[currentSlot])[currentIndex] = item;
188: }
189: }
190:
191: public void clear() {
192: reset();
193: }
194:
195: public Object get(int index) {
196: synchronized (slotsGuard) {
197: Object[] slot = null;
198: int lowerLimit = 0;
199:
200: for (int i = 0; i < slotCount; i++) {
201: if (slotLimits[i] > index) {
202: slot = (Object[]) storageSlots[i];
203:
204: break;
205: }
206:
207: lowerLimit = slotLimits[i];
208: }
209:
210: if (slot == null) {
211: return null;
212: }
213:
214: return ((Object[]) slot)[index - lowerLimit];
215: }
216: }
217:
218: public Object get(final Object template) {
219: for (Iterator iter = iterator(); iter.hasNext();) {
220: Object obj = iter.next();
221:
222: if (obj.equals(template)) {
223: return obj;
224: }
225: }
226:
227: return null;
228: }
229:
230: public Iterator iterator() {
231: return new InnerIterator();
232: }
233:
234: public static void main(String[] args) {
235: ImmutableList list = new ImmutableList();
236:
237: for (int i = 0; i < 10000; i++) {
238: list.add(Integer.valueOf(i));
239: }
240:
241: System.out.println("ready"); // NOI18N
242:
243: for (int i = 0; i < 10000; i++) {
244: System.out.println(i + " = " + list.get(i)); // NOI18N
245: }
246:
247: list.clear();
248:
249: for (int i = 0; i < 100000; i++) {
250: list.add(Integer.valueOf(i));
251: }
252:
253: System.out.println("ready"); // NOI18N
254:
255: for (int i = 0; i < 100000; i++) {
256: System.out.println(i + " = " + list.get(i)); // NOI18N
257: }
258: }
259:
260: public int size() {
261: return size;
262: }
263:
264: private void accomodate(int newSize) {
265: synchronized (slotsGuard) {
266: if (slotCount == 0) {
267: slotLimits = new int[initialSize];
268: storageSlots = new Object[initialSize];
269: storageSlots[0] = new Object[slotInitialSize];
270: availableSize = slotLimits[0] = slotInitialSize;
271: slotCount = 1;
272: currentSlot = 0;
273: currentIndex = 0;
274:
275: return;
276: }
277:
278: if (newSize > availableSize) {
279: int newSlotSize = (int) (((float) availableSize * findLoadFactor(availableSize)) + 0.5f);
280: newSlotSize = (newSlotSize > 0) ? newSize : 1;
281:
282: Object[] newSlot = new Object[newSlotSize];
283: availableSize += newSlotSize;
284:
285: if (slotCount == storageSlots.length) { // all slots taken
286:
287: int newSlotsSize = (int) (((float) slotCount * loadFactor) + 0.5f);
288: Object[] newStorageSlots = new Object[newSlotsSize];
289: int[] newSlotLimits = new int[newSlotsSize];
290: System.arraycopy(storageSlots, 0, newStorageSlots,
291: 0, storageSlots.length);
292: System.arraycopy(slotLimits, 0, newSlotLimits, 0,
293: slotLimits.length);
294: storageSlots = newStorageSlots;
295: slotLimits = newSlotLimits;
296: }
297:
298: currentSlot = slotCount;
299: currentIndex = 0;
300: storageSlots[slotCount] = newSlot;
301: slotLimits[slotCount] = availableSize;
302:
303: slotCount++;
304:
305: return;
306: }
307:
308: if (slotCount > 1) {
309: currentIndex = newSize - slotLimits[slotCount - 2] - 1; // use the slot size of the previously filled-up slot
310: } else {
311: currentIndex = newSize - 1;
312: }
313: }
314: }
315:
316: private float findLoadFactor(int origSize) {
317: for (int i = 0; i < distributionMap.length; i++) {
318: if (distributionMap[i].upperLimit > origSize) {
319: return distributionMap[i].factor;
320: }
321: }
322:
323: return LoadFactor.DEFAULT_FACTOR;
324: }
325:
326: private void reset() {
327: synchronized (slotsGuard) {
328: storageSlots = null;
329: slotLimits = null;
330:
331: slotCount = 0;
332: size = 0;
333: }
334: }
335: }
|