Back to index...

	/*
	* Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package com.sun.java.util.jar.pack;

	import com.sun.java.util.jar.pack.ConstantPool.Entry;
	import java.util.AbstractCollection;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Iterator;
	import java.util.Objects;

	/**
	* Collection of relocatable constant pool references.
	* It operates with respect to a particular byte array,
	* and stores some of its state in the bytes themselves.
	* <p>
	* As a Collection, it can be iterated over, but it is not a List,
	* since it does not natively support indexed access.
	* <p>
	*
	* @author John Rose
	*/
	final class Fixups extends AbstractCollection<Fixups.Fixup> {
	byte[] bytes; // the subject of the relocations
	int head; // desc locating first reloc
	int tail; // desc locating last reloc
	int size; // number of relocations
	Entry[] entries; // [0..size-1] relocations
	int[] bigDescs; // descs which cannot be stored in the bytes

	// A "desc" (descriptor) is a bit-encoded pair of a location
	// and format. Every fixup occurs at a "desc". Until final
	// patching, bytes addressed by descs may also be used to
	// link this data structure together. If the bytes are missing,
	// or if the "desc" is too large to encode in the bytes,
	// it is kept in the bigDescs array.

	Fixups(byte[] bytes) {
	this.bytes = bytes;
	entries = new Entry[3];
	bigDescs = noBigDescs;
	}
	Fixups() {
	// If there are no bytes, all descs are kept in bigDescs.
	this((byte[])null);
	}
	Fixups(byte[] bytes, Collection<Fixup> fixups) {
	this(bytes);
	addAll(fixups);
	}
	Fixups(Collection<Fixup> fixups) {
	this((byte[])null);
	addAll(fixups);
	}

	private static final int MINBIGSIZE = 1;
	// cleverly share empty bigDescs:
	private static final int[] noBigDescs = {MINBIGSIZE};

	@Override
	public int size() {
	return size;
	}

	public void trimToSize() {
	if (size != entries.length) {
	Entry[] oldEntries = entries;
	entries = new Entry[size];
	System.arraycopy(oldEntries, 0, entries, 0, size);
	}
	int bigSize = bigDescs[BIGSIZE];
	if (bigSize == MINBIGSIZE) {
	bigDescs = noBigDescs;
	} else if (bigSize != bigDescs.length) {
	int[] oldBigDescs = bigDescs;
	bigDescs = new int[bigSize];
	System.arraycopy(oldBigDescs, 0, bigDescs, 0, bigSize);
	}
	}

	public void visitRefs(Collection<Entry> refs) {
	for (int i = 0; i < size; i++) {
	refs.add(entries[i]);
	}
	}

	@Override
	public void clear() {
	if (bytes != null) {
	// Clean the bytes:
	for (Fixup fx : this) {
	//System.out.println("clean "+fx);
	storeIndex(fx.location(), fx.format(), 0);
	}
	}
	size = 0;
	if (bigDescs != noBigDescs)
	bigDescs[BIGSIZE] = MINBIGSIZE;
	// do not trim to size, however
	}

	public byte[] getBytes() {
	return bytes;
	}

	public void setBytes(byte[] newBytes) {
	if (bytes == newBytes) return;
	ArrayList<Fixup> old = null;
	assert((old = new ArrayList<>(this)) != null);
	if (bytes == null \|\| newBytes == null) {
	// One or the other representations is deficient.
	// Construct a checkpoint.
	ArrayList<Fixup> save = new ArrayList<>(this);
	clear();
	bytes = newBytes;
	addAll(save);
	} else {
	// assume newBytes is some sort of bitwise copy of the old bytes
	bytes = newBytes;
	}
	assert(old.equals(new ArrayList<>(this)));
	}

	private static final int LOC_SHIFT = 1;
	private static final int FMT_MASK = 0x1;
	private static final byte UNUSED_BYTE = 0;
	private static final byte OVERFLOW_BYTE = -1;
	// fill pointer of bigDescs array is in element [0]
	private static final int BIGSIZE = 0;

	// Format values:
	private static final int U2_FORMAT = 0;
	private static final int U1_FORMAT = 1;

	// Special values for the static methods.
	private static final int SPECIAL_LOC = 0;
	private static final int SPECIAL_FMT = U2_FORMAT;

	static int fmtLen(int fmt) { return 1+(fmt-U1_FORMAT)/(U2_FORMAT-U1_FORMAT); }
	static int descLoc(int desc) { return desc >>> LOC_SHIFT; }
	static int descFmt(int desc) { return desc & FMT_MASK; }
	static int descEnd(int desc) { return descLoc(desc) + fmtLen(descFmt(desc)); }
	static int makeDesc(int loc, int fmt) {
	int desc = (loc << LOC_SHIFT) \| fmt;
	assert(descLoc(desc) == loc);
	assert(descFmt(desc) == fmt);
	return desc;
	}
	int fetchDesc(int loc, int fmt) {
	byte b1 = bytes[loc];
	assert(b1 != OVERFLOW_BYTE);
	int value;
	if (fmt == U2_FORMAT) {
	byte b2 = bytes[loc+1];
	value = ((b1 & 0xFF) << 8) + (b2 & 0xFF);
	} else {
	value = (b1 & 0xFF);
	}
	// Stored loc field is difference between its own loc and next loc.
	return value + (loc << LOC_SHIFT);
	}
	boolean storeDesc(int loc, int fmt, int desc) {
	if (bytes == null)
	return false;
	int value = desc - (loc << LOC_SHIFT);
	byte b1, b2;
	switch (fmt) {
	case U2_FORMAT:
	assert(bytes[loc+0] == UNUSED_BYTE);
	assert(bytes[loc+1] == UNUSED_BYTE);
	b1 = (byte)(value >> 8);
	b2 = (byte)(value >> 0);
	if (value == (value & 0xFFFF) && b1 != OVERFLOW_BYTE) {
	bytes[loc+0] = b1;
	bytes[loc+1] = b2;
	assert(fetchDesc(loc, fmt) == desc);
	return true;
	}
	break;
	case U1_FORMAT:
	assert(bytes[loc] == UNUSED_BYTE);
	b1 = (byte)value;
	if (value == (value & 0xFF) && b1 != OVERFLOW_BYTE) {
	bytes[loc] = b1;
	assert(fetchDesc(loc, fmt) == desc);
	return true;
	}
	break;
	default: assert(false);
	}
	// Failure. Caller must allocate a bigDesc.
	bytes[loc] = OVERFLOW_BYTE;
	assert(fmt==U1_FORMAT \|\| (bytes[loc+1]=(byte)bigDescs[BIGSIZE])!=999);
	return false;
	}
	void storeIndex(int loc, int fmt, int value) {
	storeIndex(bytes, loc, fmt, value);
	}
	static
	void storeIndex(byte[] bytes, int loc, int fmt, int value) {
	switch (fmt) {
	case U2_FORMAT:
	assert(value == (value & 0xFFFF)) : (value);
	bytes[loc+0] = (byte)(value >> 8);
	bytes[loc+1] = (byte)(value >> 0);
	break;
	case U1_FORMAT:
	assert(value == (value & 0xFF)) : (value);
	bytes[loc] = (byte)value;
	break;
	default: assert(false);
	}
	}

	void addU1(int pc, Entry ref) {
	add(pc, U1_FORMAT, ref);
	}

	void addU2(int pc, Entry ref) {
	add(pc, U2_FORMAT, ref);
	}

	/** Simple and necessary tuple to present each fixup. */
	public static
	class Fixup implements Comparable<Fixup> {
	int desc; // location and format of reloc
	Entry entry; // which entry to plug into the bytes
	Fixup(int desc, Entry entry) {
	this.desc = desc;
	this.entry = entry;
	}
	public Fixup(int loc, int fmt, Entry entry) {
	this.desc = makeDesc(loc, fmt);
	this.entry = entry;
	}
	public int location() { return descLoc(desc); }
	public int format() { return descFmt(desc); }
	public Entry entry() { return entry; }
	@Override
	public int compareTo(Fixup that) {
	// Ordering depends only on location.
	return this.location() - that.location();
	}
	@Override
	public boolean equals(Object x) {
	if (!(x instanceof Fixup)) return false;
	Fixup that = (Fixup) x;
	return this.desc == that.desc && this.entry == that.entry;
	}
	@Override
	public int hashCode() {
	int hash = 7;
	hash = 59 * hash + this.desc;
	hash = 59 * hash + Objects.hashCode(this.entry);
	return hash;
	}
	@Override
	public String toString() {
	return "@"+location()+(format()==U1_FORMAT?".1":"")+"="+entry;
	}
	}

	private
	class Itr implements Iterator<Fixup> {
	int index = 0; // index into entries
	int bigIndex = BIGSIZE+1; // index into bigDescs
	int next = head; // desc pointing to next fixup
	@Override
	public boolean hasNext() { return index < size; }
	@Override
	public void remove() { throw new UnsupportedOperationException(); }
	@Override
	public Fixup next() {
	int thisIndex = index;
	return new Fixup(nextDesc(), entries[thisIndex]);
	}
	int nextDesc() {
	index++;
	int thisDesc = next;
	if (index < size) {
	// Fetch next desc eagerly, in case this fixup gets finalized.
	int loc = descLoc(thisDesc);
	int fmt = descFmt(thisDesc);
	if (bytes != null && bytes[loc] != OVERFLOW_BYTE) {
	next = fetchDesc(loc, fmt);
	} else {
	// The unused extra byte is "asserted" to be equal to BI.
	// This helps keep the overflow descs in sync.
	assert(fmt==U1_FORMAT \|\| bytes == null \|\| bytes[loc+1]==(byte)bigIndex);
	next = bigDescs[bigIndex++];
	}
	}
	return thisDesc;
	}
	}

	@Override
	public Iterator<Fixup> iterator() {
	return new Itr();
	}
	public void add(int location, int format, Entry entry) {
	addDesc(makeDesc(location, format), entry);
	}
	@Override
	public boolean add(Fixup f) {
	addDesc(f.desc, f.entry);
	return true;
	}

	@Override
	public boolean addAll(Collection<? extends Fixup> c) {
	if (c instanceof Fixups) {
	// Use knowledge of Itr structure to avoid building little structs.
	Fixups that = (Fixups) c;
	if (that.size == 0) return false;
	if (this.size == 0 && entries.length < that.size)
	growEntries(that.size); // presize exactly
	Entry[] thatEntries = that.entries;
	for (Itr i = that.new Itr(); i.hasNext(); ) {
	int ni = i.index;
	addDesc(i.nextDesc(), thatEntries[ni]);
	}
	return true;
	} else {
	return super.addAll(c);
	}
	}
	// Here is how things get added:
	private void addDesc(int thisDesc, Entry entry) {
	if (entries.length == size)
	growEntries(size * 2);
	entries[size] = entry;
	if (size == 0) {
	head = tail = thisDesc;
	} else {
	int prevDesc = tail;
	// Store new desc in previous tail.
	int prevLoc = descLoc(prevDesc);
	int prevFmt = descFmt(prevDesc);
	int prevLen = fmtLen(prevFmt);
	int thisLoc = descLoc(thisDesc);
	// The collection must go in ascending order, and not overlap.
	if (thisLoc < prevLoc + prevLen)
	badOverlap(thisLoc);
	tail = thisDesc;
	if (!storeDesc(prevLoc, prevFmt, thisDesc)) {
	// overflow
	int bigSize = bigDescs[BIGSIZE];
	if (bigDescs.length == bigSize)
	growBigDescs();
	//System.out.println("bigDescs["+bigSize+"] = "+thisDesc);
	bigDescs[bigSize++] = thisDesc;
	bigDescs[BIGSIZE] = bigSize;
	}
	}
	size += 1;
	}
	private void badOverlap(int thisLoc) {
	throw new IllegalArgumentException("locs must be ascending and must not overlap: "+thisLoc+" >> "+this);
	}

	private void growEntries(int newSize) {
	Entry[] oldEntries = entries;
	entries = new Entry[Math.max(3, newSize)];
	System.arraycopy(oldEntries, 0, entries, 0, oldEntries.length);
	}
	private void growBigDescs() {
	int[] oldBigDescs = bigDescs;
	bigDescs = new int[oldBigDescs.length * 2];
	System.arraycopy(oldBigDescs, 0, bigDescs, 0, oldBigDescs.length);
	}

	/// Static methods that optimize the use of this class.
	static Object addRefWithBytes(Object f, byte[] bytes, Entry e) {
	return add(f, bytes, 0, U2_FORMAT, e);
	}
	static Object addRefWithLoc(Object f, int loc, Entry entry) {
	return add(f, null, loc, U2_FORMAT, entry);
	}
	private static
	Object add(Object prevFixups,
	byte[] bytes, int loc, int fmt,
	Entry e) {
	Fixups f;
	if (prevFixups == null) {
	if (loc == SPECIAL_LOC && fmt == SPECIAL_FMT) {
	// Special convention: If the attribute has a
	// U2 relocation at position zero, store the Entry
	// rather than building a Fixups structure.
	return e;
	}
	f = new Fixups(bytes);
	} else if (!(prevFixups instanceof Fixups)) {
	// Recognize the special convention:
	Entry firstEntry = (Entry) prevFixups;
	f = new Fixups(bytes);
	f.add(SPECIAL_LOC, SPECIAL_FMT, firstEntry);
	} else {
	f = (Fixups) prevFixups;
	assert(f.bytes == bytes);
	}
	f.add(loc, fmt, e);
	return f;
	}

	public static
	void setBytes(Object fixups, byte[] bytes) {
	if (fixups instanceof Fixups) {
	Fixups f = (Fixups) fixups;
	f.setBytes(bytes);
	}
	}

	public static
	Object trimToSize(Object fixups) {
	if (fixups instanceof Fixups) {
	Fixups f = (Fixups) fixups;
	f.trimToSize();
	if (f.size() == 0)
	fixups = null;
	}
	return fixups;
	}

	// Iterate over all the references in this set of fixups.
	public static
	void visitRefs(Object fixups, Collection<Entry> refs) {
	if (fixups == null) {
	} else if (!(fixups instanceof Fixups)) {
	// Special convention; see above.
	refs.add((Entry) fixups);
	} else {
	Fixups f = (Fixups) fixups;
	f.visitRefs(refs);
	}
	}

	// Clear out this set of fixups by replacing each reference
	// by a hardcoded coding of its reference, drawn from ix.
	public static
	void finishRefs(Object fixups, byte[] bytes, ConstantPool.Index ix) {
	if (fixups == null)
	return;
	if (!(fixups instanceof Fixups)) {
	// Special convention; see above.
	int index = ix.indexOf((Entry) fixups);
	storeIndex(bytes, SPECIAL_LOC, SPECIAL_FMT, index);
	return;
	}
	Fixups f = (Fixups) fixups;
	assert(f.bytes == bytes);
	f.finishRefs(ix);
	}

	void finishRefs(ConstantPool.Index ix) {
	if (isEmpty())
	return;
	for (Fixup fx : this) {
	int index = ix.indexOf(fx.entry);
	//System.out.println("finish "+fx+" = "+index);
	// Note that the iterator has already fetched the
	// bytes we are about to overwrite.
	storeIndex(fx.location(), fx.format(), index);
	}
	// Further iterations should do nothing:
	bytes = null; // do not clean them
	clear();
	}

	/*
	/// Testing.
	public static void main(String[] av) {
	byte[] bytes = new byte[1 << 20];
	ConstantPool cp = new ConstantPool();
	Fixups f = new Fixups(bytes);
	boolean isU1 = false;
	int span = 3;
	int nextLoc = 0;
	int[] locs = new int[100];
	final int[] indexes = new int[100];
	int iptr = 1;
	for (int loc = 0; loc < bytes.length; loc++) {
	if (loc == nextLoc && loc+1 < bytes.length) {
	int fmt = (isU1 ? U1_FORMAT : U2_FORMAT);
	Entry e = ConstantPool.getUtf8Entry("L"+loc);
	f.add(loc, fmt, e);
	isU1 ^= true;
	if (iptr < 10) {
	// Make it close in.
	nextLoc += fmtLen(fmt) + (iptr < 5 ? 0 : 1);
	} else {
	nextLoc += span;
	span = (int)(span * 1.77);
	}
	// Here are the bytes that would have gone here:
	locs[iptr] = loc;
	if (fmt == U1_FORMAT) {
	indexes[iptr++] = (loc & 0xFF);
	} else {
	indexes[iptr++] = ((loc & 0xFF) << 8) \| ((loc+1) & 0xFF);
	++loc; // skip a byte
	}
	continue;
	}
	bytes[loc] = (byte)loc;
	}
	System.out.println("size="+f.size()
	+" overflow="+(f.bigDescs[BIGSIZE]-1));
	System.out.println("Fixups: "+f);
	// Test collection contents.
	assert(iptr == 1+f.size());
	List l = new ArrayList(f);
	Collections.sort(l); // should not change the order
	if (!l.equals(new ArrayList(f))) System.out.println("** disordered");
	f.setBytes(null);
	if (!l.equals(new ArrayList(f))) System.out.println("** bad set 1");
	f.setBytes(bytes);
	if (!l.equals(new ArrayList(f))) System.out.println("** bad set 2");
	Fixups f3 = new Fixups(f);
	if (!l.equals(new ArrayList(f3))) System.out.println("** bad set 3");
	Iterator fi = f.iterator();
	for (int i = 1; i < iptr; i++) {
	Fixup fx = (Fixup) fi.next();
	if (fx.location() != locs[i]) {
	System.out.println("** "+fx+" != "+locs[i]);
	}
	if (fx.format() == U1_FORMAT)
	System.out.println(fx+" -> "+bytes[locs[i]]);
	else
	System.out.println(fx+" -> "+bytes[locs[i]]+" "+bytes[locs[i]+1]);
	}
	assert(!fi.hasNext());
	indexes[0] = 1; // like iptr
	Index ix = new Index("ix") {
	public int indexOf(Entry e) {
	return indexes[indexes[0]++];
	}
	};
	f.finishRefs(ix);
	for (int loc = 0; loc < bytes.length; loc++) {
	if (bytes[loc] != (byte)loc) {
	System.out.println("** ["+loc+"] = "+bytes[loc]+" != "+(byte)loc);
	}
	}
	}
	//*/
	}

Back to index...