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 Development
008: * and Distribution License("CDDL") (collectively, the "License"). You
009: * may not use this file except in compliance with the License. You can obtain
010: * a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
011: * or glassfish/bootstrap/legal/LICENSE.txt. See the License for the specific
012: * language governing permissions and limitations under the License.
013: *
014: * When distributing the software, include this License Header Notice in each
015: * file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
016: * Sun designates this particular file as subject to the "Classpath" exception
017: * as provided by Sun in the GPL Version 2 section of the License file that
018: * accompanied this code. If applicable, add the following below the License
019: * Header, with the fields enclosed by brackets [] replaced by your own
020: * identifying information: "Portions Copyrighted [year]
021: * [name of copyright owner]"
022: *
023: * Contributor(s):
024: *
025: * If you wish your version of this file to be governed by only the CDDL or
026: * only the GPL Version 2, indicate your decision by adding "[Contributor]
027: * elects to include this software in this distribution under the [CDDL or GPL
028: * Version 2] license." If you don't indicate a single choice of license, a
029: * recipient has the option to distribute your version of this file under
030: * either the CDDL, the GPL Version 2 or to extend the choice of license to
031: * its licensees as provided above. However, if you add GPL Version 2 code
032: * and therefore, elected the GPL Version 2 license, then the option applies
033: * only if the new code is made subject to such option by the copyright
034: * holder.
035: */
036:
037: package com.sun.xml.bind.v2.util;
038:
039: import java.util.AbstractList;
040: import java.util.Arrays;
041: import java.util.List;
042: import java.util.Stack;
043:
044: /**
045: * {@link Stack}-like data structure that allows the following efficient operations:
046: *
047: * <ol>
048: * <li>Push/pop operation.
049: * <li>Duplicate check. When an object that's already in the stack is pushed,
050: * this class will tell you so.
051: * </ol>
052: *
053: * <p>
054: * Object equality is their identity equality.
055: *
056: * <p>
057: * This class implements {@link List} for accessing items in the stack,
058: * but {@link List} methods that alter the stack is not supported.
059: *
060: * @author Kohsuke Kawaguchi
061: */
062: public final class CollisionCheckStack<E> extends AbstractList<E> {
063: private Object[] data;
064: private int[] next;
065: private int size = 0;
066:
067: /**
068: * True if the check shall be done by using the object identity.
069: * False if the check shall be done with the equals method.
070: */
071: private boolean useIdentity = true;
072:
073: // for our purpose, there isn't much point in resizing this as we don't expect
074: // the stack to grow that much.
075: private final int[] initialHash;
076:
077: public CollisionCheckStack() {
078: initialHash = new int[17];
079: data = new Object[16];
080: next = new int[16];
081: }
082:
083: /**
084: * Set to false to use {@link Object#equals(Object)} to detect cycles.
085: * This method can be only used when the stack is empty.
086: */
087: public void setUseIdentity(boolean useIdentity) {
088: this .useIdentity = useIdentity;
089: }
090:
091: public boolean getUseIdentity() {
092: return useIdentity;
093: }
094:
095: /**
096: * Pushes a new object to the stack.
097: *
098: * @return
099: * true if this object has already been pushed
100: */
101: public boolean push(E o) {
102: if (data.length == size)
103: expandCapacity();
104:
105: data[size] = o;
106: int hash = hash(o);
107: boolean r = findDuplicate(o, hash);
108: next[size] = initialHash[hash];
109: initialHash[hash] = size + 1;
110: size++;
111: return r;
112: }
113:
114: /**
115: * Pushes a new object to the stack without making it participate
116: * with the collision check.
117: */
118: public void pushNocheck(E o) {
119: if (data.length == size)
120: expandCapacity();
121: data[size] = o;
122: next[size] = -1;
123: size++;
124: }
125:
126: @Override
127: public E get(int index) {
128: return (E) data[index];
129: }
130:
131: @Override
132: public int size() {
133: return size;
134: }
135:
136: private int hash(Object o) {
137: return ((useIdentity ? System.identityHashCode(o) : o
138: .hashCode()) & 0x7FFFFFFF)
139: % initialHash.length;
140: }
141:
142: /**
143: * Pops an object from the stack
144: */
145: public E pop() {
146: size--;
147: Object o = data[size];
148: data[size] = null; // keeping references too long == memory leak
149: int n = next[size];
150: if (n < 0) {
151: // pushed by nocheck. no need to update hash
152: } else {
153: int hash = hash(o);
154: assert initialHash[hash] == size + 1;
155: initialHash[hash] = n;
156: }
157: return (E) o;
158: }
159:
160: /**
161: * Returns the top of the stack.
162: */
163: public E peek() {
164: return (E) data[size - 1];
165: }
166:
167: private boolean findDuplicate(E o, int hash) {
168: int p = initialHash[hash];
169: while (p != 0) {
170: p--;
171: Object existing = data[p];
172: if (useIdentity) {
173: if (existing == o)
174: return true;
175: } else {
176: if (o.equals(existing))
177: return true;
178: }
179: p = next[p];
180: }
181: return false;
182: }
183:
184: private void expandCapacity() {
185: int oldSize = data.length;
186: int newSize = oldSize * 2;
187: Object[] d = new Object[newSize];
188: int[] n = new int[newSize];
189:
190: System.arraycopy(data, 0, d, 0, oldSize);
191: System.arraycopy(next, 0, n, 0, oldSize);
192:
193: data = d;
194: next = n;
195: }
196:
197: /**
198: * Clears all the contents in the stack.
199: */
200: public void reset() {
201: if (size > 0) {
202: size = 0;
203: Arrays.fill(initialHash, 0);
204: }
205: }
206:
207: /**
208: * String that represents the cycle.
209: */
210: public String getCycleString() {
211: StringBuilder sb = new StringBuilder();
212: int i = size() - 1;
213: E obj = get(i);
214: sb.append(obj);
215: Object x;
216: do {
217: sb.append(" -> ");
218: x = get(--i);
219: sb.append(x);
220: } while (obj != x);
221:
222: return sb.toString();
223: }
224: }
|