001: /*
002: * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package com.sun.xml.internal.bind.v2.util;
027:
028: import java.util.AbstractList;
029: import java.util.Arrays;
030: import java.util.List;
031: import java.util.Stack;
032:
033: /**
034: * {@link Stack}-like data structure that allows the following efficient operations:
035: *
036: * <ol>
037: * <li>Push/pop operation.
038: * <li>Duplicate check. When an object that's already in the stack is pushed,
039: * this class will tell you so.
040: * </ol>
041: *
042: * <p>
043: * Object equality is their identity equality.
044: *
045: * <p>
046: * This class implements {@link List} for accessing items in the stack,
047: * but {@link List} methods that alter the stack is not supported.
048: *
049: * @author Kohsuke Kawaguchi
050: */
051: public final class CollisionCheckStack<E> extends AbstractList<E> {
052: private Object[] data;
053: private int[] next;
054: private int size = 0;
055:
056: // for our purpose, there isn't much point in resizing this as we don't expect
057: // the stack to grow that much.
058: private final int[] initialHash;
059:
060: public CollisionCheckStack() {
061: initialHash = new int[17];
062: data = new Object[16];
063: next = new int[16];
064: }
065:
066: /**
067: * Pushes a new object to the stack.
068: *
069: * @return
070: * true if this object has already been pushed
071: */
072: public boolean push(E o) {
073: if (data.length == size)
074: expandCapacity();
075:
076: data[size] = o;
077: int hash = hash(o);
078: boolean r = findDuplicate(o, hash);
079: next[size] = initialHash[hash];
080: initialHash[hash] = size + 1;
081: size++;
082: return r;
083: }
084:
085: /**
086: * Pushes a new object to the stack without making it participate
087: * with the collision check.
088: */
089: public void pushNocheck(E o) {
090: if (data.length == size)
091: expandCapacity();
092: data[size] = o;
093: next[size] = -1;
094: size++;
095: }
096:
097: @Override
098: public E get(int index) {
099: return (E) data[index];
100: }
101:
102: @Override
103: public int size() {
104: return size;
105: }
106:
107: private int hash(Object o) {
108: return System.identityHashCode(o) % initialHash.length;
109: }
110:
111: /**
112: * Pops an object from the stack
113: */
114: public E pop() {
115: size--;
116: Object o = data[size];
117: data[size] = null; // keeping references too long == memory leak
118: int n = next[size];
119: if (n < 0) {
120: // pushed by nocheck. no need to update hash
121: } else {
122: int hash = hash(o);
123: assert initialHash[hash] == size + 1;
124: initialHash[hash] = n;
125: }
126: return (E) o;
127: }
128:
129: /**
130: * Returns the top of the stack.
131: */
132: public E peek() {
133: return (E) data[size - 1];
134: }
135:
136: private boolean findDuplicate(E o, int hash) {
137: int p = initialHash[hash];
138: while (p != 0) {
139: p--;
140: Object existing = data[p];
141: if (existing == o)
142: return true;
143: p = next[p];
144: }
145: return false;
146: }
147:
148: private void expandCapacity() {
149: int oldSize = data.length;
150: int newSize = oldSize * 2;
151: Object[] d = new Object[newSize];
152: int[] n = new int[newSize];
153:
154: System.arraycopy(data, 0, d, 0, oldSize);
155: System.arraycopy(next, 0, n, 0, oldSize);
156:
157: data = d;
158: next = n;
159: }
160:
161: /**
162: * Clears all the contents in the stack.
163: */
164: public void reset() {
165: if (size > 0) {
166: size = 0;
167: Arrays.fill(initialHash, 0);
168: }
169: }
170: }
|