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 +}
