1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/jaxws_classes/com/sun/xml/internal/bind/v2/util/CollisionCheckStack.java Tue Mar 06 16:09:35 2012 -0800 1.3 @@ -0,0 +1,221 @@ 1.4 +/* 1.5 + * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. Oracle designates this 1.11 + * particular file as subject to the "Classpath" exception as provided 1.12 + * by Oracle in the LICENSE file that accompanied this code. 1.13 + * 1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.17 + * version 2 for more details (a copy is included in the LICENSE file that 1.18 + * accompanied this code). 1.19 + * 1.20 + * You should have received a copy of the GNU General Public License version 1.21 + * 2 along with this work; if not, write to the Free Software Foundation, 1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.23 + * 1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1.25 + * or visit www.oracle.com if you need additional information or have any 1.26 + * questions. 1.27 + */ 1.28 + 1.29 +package com.sun.xml.internal.bind.v2.util; 1.30 + 1.31 +import java.util.AbstractList; 1.32 +import java.util.Arrays; 1.33 +import java.util.List; 1.34 +import java.util.Stack; 1.35 + 1.36 +/** 1.37 + * {@link Stack}-like data structure that allows the following efficient operations: 1.38 + * 1.39 + * <ol> 1.40 + * <li>Push/pop operation. 1.41 + * <li>Duplicate check. When an object that's already in the stack is pushed, 1.42 + * this class will tell you so. 1.43 + * </ol> 1.44 + * 1.45 + * <p> 1.46 + * Object equality is their identity equality. 1.47 + * 1.48 + * <p> 1.49 + * This class implements {@link List} for accessing items in the stack, 1.50 + * but {@link List} methods that alter the stack is not supported. 1.51 + * 1.52 + * @author Kohsuke Kawaguchi 1.53 + */ 1.54 +public final class CollisionCheckStack<E> extends AbstractList<E> { 1.55 + private Object[] data; 1.56 + private int[] next; 1.57 + private int size = 0; 1.58 + 1.59 + private boolean latestPushResult = false; 1.60 + 1.61 + /** 1.62 + * True if the check shall be done by using the object identity. 1.63 + * False if the check shall be done with the equals method. 1.64 + */ 1.65 + private boolean useIdentity = true; 1.66 + 1.67 + // for our purpose, there isn't much point in resizing this as we don't expect 1.68 + // the stack to grow that much. 1.69 + private final int[] initialHash; 1.70 + 1.71 + public CollisionCheckStack() { 1.72 + initialHash = new int[17]; 1.73 + data = new Object[16]; 1.74 + next = new int[16]; 1.75 + } 1.76 + 1.77 + /** 1.78 + * Set to false to use {@link Object#equals(Object)} to detect cycles. 1.79 + * This method can be only used when the stack is empty. 1.80 + */ 1.81 + public void setUseIdentity(boolean useIdentity) { 1.82 + this.useIdentity = useIdentity; 1.83 + } 1.84 + 1.85 + public boolean getUseIdentity() { 1.86 + return useIdentity; 1.87 + } 1.88 + 1.89 + public boolean getLatestPushResult() { 1.90 + return latestPushResult; 1.91 + } 1.92 + 1.93 + /** 1.94 + * Pushes a new object to the stack. 1.95 + * 1.96 + * @return 1.97 + * true if this object has already been pushed 1.98 + */ 1.99 + public boolean push(E o) { 1.100 + if(data.length==size) 1.101 + expandCapacity(); 1.102 + 1.103 + data[size] = o; 1.104 + int hash = hash(o); 1.105 + boolean r = findDuplicate(o, hash); 1.106 + next[size] = initialHash[hash]; 1.107 + initialHash[hash] = size+1; 1.108 + size++; 1.109 + this.latestPushResult = r; 1.110 + return latestPushResult; 1.111 + } 1.112 + 1.113 + /** 1.114 + * Pushes a new object to the stack without making it participate 1.115 + * with the collision check. 1.116 + */ 1.117 + public void pushNocheck(E o) { 1.118 + if(data.length==size) 1.119 + expandCapacity(); 1.120 + data[size] = o; 1.121 + next[size] = -1; 1.122 + size++; 1.123 + } 1.124 + 1.125 + public boolean findDuplicate(E o) { 1.126 + int hash = hash(o); 1.127 + return findDuplicate(o, hash); 1.128 + } 1.129 + 1.130 + @Override 1.131 + public E get(int index) { 1.132 + return (E)data[index]; 1.133 + } 1.134 + 1.135 + @Override 1.136 + public int size() { 1.137 + return size; 1.138 + } 1.139 + 1.140 + private int hash(Object o) { 1.141 + return ((useIdentity?System.identityHashCode(o):o.hashCode())&0x7FFFFFFF) % initialHash.length; 1.142 + } 1.143 + 1.144 + /** 1.145 + * Pops an object from the stack 1.146 + */ 1.147 + public E pop() { 1.148 + size--; 1.149 + Object o = data[size]; 1.150 + data[size] = null; // keeping references too long == memory leak 1.151 + int n = next[size]; 1.152 + if(n<0) { 1.153 + // pushed by nocheck. no need to update hash 1.154 + } else { 1.155 + int hash = hash(o); 1.156 + assert initialHash[hash]==size+1; 1.157 + initialHash[hash] = n; 1.158 + } 1.159 + return (E)o; 1.160 + } 1.161 + 1.162 + /** 1.163 + * Returns the top of the stack. 1.164 + */ 1.165 + public E peek() { 1.166 + return (E)data[size-1]; 1.167 + } 1.168 + 1.169 + private boolean findDuplicate(E o, int hash) { 1.170 + int p = initialHash[hash]; 1.171 + while(p!=0) { 1.172 + p--; 1.173 + Object existing = data[p]; 1.174 + if (useIdentity) { 1.175 + if(existing==o) return true; 1.176 + } else { 1.177 + if (o.equals(existing)) return true; 1.178 + } 1.179 + p = next[p]; 1.180 + } 1.181 + return false; 1.182 + } 1.183 + 1.184 + private void expandCapacity() { 1.185 + int oldSize = data.length; 1.186 + int newSize = oldSize * 2; 1.187 + Object[] d = new Object[newSize]; 1.188 + int[] n = new int[newSize]; 1.189 + 1.190 + System.arraycopy(data,0,d,0,oldSize); 1.191 + System.arraycopy(next,0,n,0,oldSize); 1.192 + 1.193 + data = d; 1.194 + next = n; 1.195 + } 1.196 + 1.197 + /** 1.198 + * Clears all the contents in the stack. 1.199 + */ 1.200 + public void reset() { 1.201 + if(size>0) { 1.202 + size = 0; 1.203 + Arrays.fill(initialHash,0); 1.204 + } 1.205 + } 1.206 + 1.207 + /** 1.208 + * String that represents the cycle. 1.209 + */ 1.210 + public String getCycleString() { 1.211 + StringBuilder sb = new StringBuilder(); 1.212 + int i=size()-1; 1.213 + E obj = get(i); 1.214 + sb.append(obj); 1.215 + Object x; 1.216 + do { 1.217 + sb.append(" -> "); 1.218 + x = get(--i); 1.219 + sb.append(x); 1.220 + } while(obj!=x); 1.221 + 1.222 + return sb.toString(); 1.223 + } 1.224 +}