File	Doc	Category	Size	Date	Package
SuballocatedIntVector.java	API Doc	Java SE 5 API	15664	Fri Aug 26 14:56:04 BST 2005	com.sun.org.apache.xml.internal.utils

SuballocatedIntVector

• java.lang.Object

Fields Summary
protected int	m_blocksize Size of blocks to allocate
protected int	m_SHIFT Bitwise addressing (much faster than div/remainder
protected int	m_MASK
protected static final int	NUMBLOCKS_DEFAULT The default number of blocks to (over)allocate by
protected int	m_numblocks The number of blocks to (over)allocate by
protected int[]	m_map Array of arrays of ints
protected int	m_firstFree Number of ints in array
protected int[]	m_map0 "Shortcut" handle to m_map[0]. Surprisingly helpful for short vectors.
protected int[]	m_buildCache "Shortcut" handle to most recently added row of m_map. Very helpful during construction.
protected int	m_buildCacheStartIndex

Constructors Summary
public SuballocatedIntVector() Default constructor. Note that the default block size is currently 2K, which may be overkill for small lists and undershootng for large ones. this(2048);
public SuballocatedIntVector(int blocksize, int numblocks) Construct a IntVector, using the given block size and number of blocks. For efficiency, we will round the requested size off to a power of two. param blocksize Size of block to allocate param numblocks Number of blocks to allocate //m_blocksize = blocksize; for(m_SHIFT=0;0!=(blocksize>>>=1);++m_SHIFT) ; m_blocksize=1<<m_SHIFT; m_MASK=m_blocksize-1; m_numblocks = numblocks; m_map0=new int[m_blocksize]; m_map = new int[numblocks][]; m_map[0]=m_map0; m_buildCache = m_map0; m_buildCacheStartIndex = 0;
public SuballocatedIntVector(int blocksize) Construct a IntVector, using the given block size and the default number of blocks (32). param blocksize Size of block to allocate this(blocksize, NUMBLOCKS_DEFAULT);

Methods Summary
public void	addElement(int value) Append a int onto the vector. param value Int to add to the list int indexRelativeToCache = m_firstFree - m_buildCacheStartIndex; // Is the new index an index into the cache row of m_map? if(indexRelativeToCache >= 0 && indexRelativeToCache < m_blocksize) { m_buildCache[indexRelativeToCache]=value; ++m_firstFree; } else { // Growing the outer array should be rare. We initialize to a // total of m_blocksize squared elements, which at the default // size is 4M integers... and we grow by at least that much each // time. However, attempts to microoptimize for this (assume // long enough and catch exceptions) yield no noticable // improvement. int index=m_firstFree>>>m_SHIFT; int offset=m_firstFree&m_MASK; if(index>=m_map.length) { int newsize=index+m_numblocks; int[][] newMap=new int[newsize][]; System.arraycopy(m_map, 0, newMap, 0, m_map.length); m_map=newMap; } int[] block=m_map[index]; if(null==block) block=m_map[index]=new int[m_blocksize]; block[offset]=value; // Cache the current row of m_map. Next m_blocksize-1 // values added will go to this row. m_buildCache = block; m_buildCacheStartIndex = m_firstFree-offset; ++m_firstFree; }
private void	addElements(int value, int numberOfElements) Append several int values onto the vector. param value Int to add to the list if(m_firstFree+numberOfElements<m_blocksize) for (int i = 0; i < numberOfElements; i++) { m_map0[m_firstFree++]=value; } else { int index=m_firstFree>>>m_SHIFT; int offset=m_firstFree&m_MASK; m_firstFree+=numberOfElements; while( numberOfElements>0) { if(index>=m_map.length) { int newsize=index+m_numblocks; int[][] newMap=new int[newsize][]; System.arraycopy(m_map, 0, newMap, 0, m_map.length); m_map=newMap; } int[] block=m_map[index]; if(null==block) block=m_map[index]=new int[m_blocksize]; int copied=(m_blocksize-offset < numberOfElements) ? m_blocksize-offset : numberOfElements; numberOfElements-=copied; while(copied-- > 0) block[offset++]=value; ++index;offset=0; } }
private void	addElements(int numberOfElements) Append several slots onto the vector, but do not set the values. Note: "Not Set" means the value is unspecified. param value Int to add to the list int newlen=m_firstFree+numberOfElements; if(newlen>m_blocksize) { int index=m_firstFree>>>m_SHIFT; int newindex=(m_firstFree+numberOfElements)>>>m_SHIFT; for(int i=index+1;i<=newindex;++i) m_map[i]=new int[m_blocksize]; } m_firstFree=newlen;
private boolean	contains(int s) Tell if the table contains the given node. param s object to look for return true if the object is in the list return (indexOf(s,0) >= 0);
public int	elementAt(int i) Get the nth element. This is often at the innermost loop of an application, so performance is critical. param i index of value to get return value at given index. If that value wasn't previously set, the result is undefined for performance reasons. It may throw an exception (see below), may return zero, or (if setSize has previously been used) may return stale data. throw ArrayIndexOutOfBoundsException if the index was _clearly_ unreasonable (negative, or past the highest block). throw NullPointerException if the index points to a block that could have existed (based on the highest index used) but has never had anything set into it. %REVIEW% Could add a catch to create the block in that case, or return 0. Try/Catch is _supposed_ to be nearly free when not thrown to. Do we believe that? Should we have a separate safeElementAt? // This is actually a significant optimization! if(i<m_blocksize) return m_map0[i]; return m_map[i>>>m_SHIFT][i&m_MASK];
public final int[][]	getMap() Return the m_map double array return the internal map of array of arrays return m_map;
public final int[]	getMap0() Return the internal m_map0 array return the m_map0 array return m_map0;
public int	indexOf(int elem, int index) Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method. param elem object to look for param index Index of where to begin search return the index of the first occurrence of the object argument in this vector at position index or later in the vector; returns -1 if the object is not found. if(index>=m_firstFree) return -1; int bindex=index>>>m_SHIFT; int boffset=index&m_MASK; int maxindex=m_firstFree>>>m_SHIFT; int[] block; for(;bindex<maxindex;++bindex) { block=m_map[bindex]; if(block!=null) for(int offset=boffset;offset<m_blocksize;++offset) if(block[offset]==elem) return offset+bindex*m_blocksize; boffset=0; // after first } // Last block may need to stop before end int maxoffset=m_firstFree&m_MASK; block=m_map[maxindex]; for(int offset=boffset;offset<maxoffset;++offset) if(block[offset]==elem) return offset+maxindex*m_blocksize; return -1;
public int	indexOf(int elem) Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method. param elem object to look for return the index of the first occurrence of the object argument in this vector at position index or later in the vector; returns -1 if the object is not found. return indexOf(elem,0);
private void	insertElementAt(int value, int at) Inserts the specified node in this vector at the specified index. Each component in this vector with an index greater or equal to the specified index is shifted upward to have an index one greater than the value it had previously. Insertion may be an EXPENSIVE operation! param value Int to insert param at Index of where to insert if(at==m_firstFree) addElement(value); else if (at>m_firstFree) { int index=at>>>m_SHIFT; if(index>=m_map.length) { int newsize=index+m_numblocks; int[][] newMap=new int[newsize][]; System.arraycopy(m_map, 0, newMap, 0, m_map.length); m_map=newMap; } int[] block=m_map[index]; if(null==block) block=m_map[index]=new int[m_blocksize]; int offset=at&m_MASK; block[offset]=value; m_firstFree=offset+1; } else { int index=at>>>m_SHIFT; int maxindex=m_firstFree>>>m_SHIFT; // %REVIEW% (m_firstFree+1?) ++m_firstFree; int offset=at&m_MASK; int push; // ***** Easier to work down from top? while(index<=maxindex) { int copylen=m_blocksize-offset-1; int[] block=m_map[index]; if(null==block) { push=0; block=m_map[index]=new int[m_blocksize]; } else { push=block[m_blocksize-1]; System.arraycopy(block, offset , block, offset+1, copylen); } block[offset]=value; value=push; offset=0; ++index; } }
private int	lastIndexOf(int elem) Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method. param elem Object to look for return the index of the first occurrence of the object argument in this vector at position index or later in the vector; returns -1 if the object is not found. int boffset=m_firstFree&m_MASK; for(int index=m_firstFree>>>m_SHIFT; index>=0; --index) { int[] block=m_map[index]; if(block!=null) for(int offset=boffset; offset>=0; --offset) if(block[offset]==elem) return offset+index*m_blocksize; boffset=0; // after first } return -1;
public void	removeAllElements() Wipe it out. Currently defined as equivalent to setSize(0). m_firstFree = 0; m_buildCache = m_map0; m_buildCacheStartIndex = 0;
private boolean	removeElement(int s) Removes the first occurrence of the argument from this vector. If the object is found in this vector, each component in the vector with an index greater or equal to the object's index is shifted downward to have an index one smaller than the value it had previously. param s Int to remove from array return True if the int was removed, false if it was not found int at=indexOf(s,0); if(at<0) return false; removeElementAt(at); return true;
private void	removeElementAt(int at) Deletes the component at the specified index. Each component in this vector with an index greater or equal to the specified index is shifted downward to have an index one smaller than the value it had previously. param i index of where to remove and int // No point in removing elements that "don't exist"... if(at<m_firstFree) { int index=at>>>m_SHIFT; int maxindex=m_firstFree>>>m_SHIFT; int offset=at&m_MASK; while(index<=maxindex) { int copylen=m_blocksize-offset-1; int[] block=m_map[index]; if(null==block) block=m_map[index]=new int[m_blocksize]; else System.arraycopy(block, offset+1, block, offset, copylen); if(index<maxindex) { int[] next=m_map[index+1]; if(next!=null) block[m_blocksize-1]=(next!=null) ? next[0] : 0; } else block[m_blocksize-1]=0; offset=0; ++index; } } --m_firstFree;
public void	setElementAt(int value, int at) Sets the component at the specified index of this vector to be the specified object. The previous component at that position is discarded. The index must be a value greater than or equal to 0 and less than the current size of the vector. param node object to set param index Index of where to set the object if(at<m_blocksize) m_map0[at]=value; else { int index=at>>>m_SHIFT; int offset=at&m_MASK; if(index>=m_map.length) { int newsize=index+m_numblocks; int[][] newMap=new int[newsize][]; System.arraycopy(m_map, 0, newMap, 0, m_map.length); m_map=newMap; } int[] block=m_map[index]; if(null==block) block=m_map[index]=new int[m_blocksize]; block[offset]=value; } if(at>=m_firstFree) m_firstFree=at+1;
public void	setSize(int sz) Set the length of the list. This will only work to truncate the list, and even then it has not been heavily tested and may not be trustworthy. return length of the list if(m_firstFree>sz) // Whups; had that backward! m_firstFree = sz;
public int	size() Get the length of the list. return length of the list return m_firstFree;