FileDocCategorySizeDatePackage
SuballocatedByteVector.javaAPI DocJava SE 5 API13705Fri Aug 26 14:56:04 BST 2005com.sun.org.apache.xml.internal.utils

SuballocatedByteVector

public class SuballocatedByteVector extends Object
A very simple table that stores a list of byte. Very similar API to our IntVector class (same API); different internal storage. This version uses an array-of-arrays solution. Read/write access is thus a bit slower than the simple IntVector, and basic storage is a trifle higher due to the top-level array -- but appending is O(1) fast rather than O(N**2) slow, which will swamp those costs in situations where long vectors are being built up. Known issues: Some methods are private because they haven't yet been tested properly. If an element has not been set (because we skipped it), its value will initially be 0. Shortening the vector does not clear old storage; if you then skip values and setElementAt a higher index again, you may see old data reappear in the truncated-and-restored section. Doing anything else would have performance costs.
xsl.usage
internal

Fields Summary
protected int
m_blocksize
Size of blocks to allocate
protected int
m_numblocks
Number of blocks to (over)allocate by
protected byte[]
m_map
Array of arrays of bytes
protected int
m_firstFree
Number of bytes in array
protected byte[]
m_map0
"Shortcut" handle to m_map[0]
Constructors Summary
public SuballocatedByteVector()
Default constructor. Note that the default block size is very small, for small lists.


                    
   
  
    this(2048);
public SuballocatedByteVector(int blocksize)
Construct a ByteVector, using the given block size.

param
blocksize Size of block to allocate

    m_blocksize = blocksize;
    m_map0=new byte[blocksize];
    m_map = new byte[m_numblocks][];
    m_map[0]=m_map0;
public SuballocatedByteVector(int blocksize, int increaseSize)
Construct a ByteVector, using the given block size.

param
blocksize Size of block to allocate

    // increaseSize not currently used.
    this(blocksize);
Methods Summary
public voidaddElement(byte value)
Append a byte onto the vector.

param
value Byte to add to the list

    if(m_firstFree<m_blocksize)
      m_map0[m_firstFree++]=value;
    else
    {
      int index=m_firstFree/m_blocksize;
      int offset=m_firstFree%m_blocksize;
      ++m_firstFree;

      if(index>=m_map.length)
      {
        int newsize=index+m_numblocks;
        byte[][] newMap=new byte[newsize][];
        System.arraycopy(m_map, 0, newMap, 0, m_map.length);
        m_map=newMap;
      }
      byte[] block=m_map[index];
      if(null==block)
        block=m_map[index]=new byte[m_blocksize];
      block[offset]=value;
    }
private voidaddElements(byte value, int numberOfElements)
Append several byte values onto the vector.

param
value Byte 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_blocksize;
      int offset=m_firstFree%m_blocksize;
      m_firstFree+=numberOfElements;
      while( numberOfElements>0)
      {
        if(index>=m_map.length)
        {
          int newsize=index+m_numblocks;
          byte[][] newMap=new byte[newsize][];
          System.arraycopy(m_map, 0, newMap, 0, m_map.length);
          m_map=newMap;
        }
        byte[] block=m_map[index];
        if(null==block)
          block=m_map[index]=new byte[m_blocksize];
        int copied=(m_blocksize-offset < numberOfElements)
          ? m_blocksize-offset : numberOfElements;
        numberOfElements-=copied;
        while(copied-- > 0)
          block[offset++]=value;

        ++index;offset=0;
      }
    }
private voidaddElements(int numberOfElements)
Append several slots onto the vector, but do not set the values. Note: "Not Set" means the value is unspecified.

param
value Byte to add to the list

    int newlen=m_firstFree+numberOfElements;
    if(newlen>m_blocksize)
    {
      int index=m_firstFree%m_blocksize;
      int newindex=(m_firstFree+numberOfElements)%m_blocksize;
      for(int i=index+1;i<=newindex;++i)
        m_map[i]=new byte[m_blocksize];
    }
    m_firstFree=newlen;
private booleancontains(byte 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 byteelementAt(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?

    // %OPT% Does this really buy us anything? Test versus division for small,
    // test _plus_ division for big docs.
    if(i<m_blocksize)
      return m_map0[i];

    return m_map[i/m_blocksize][i%m_blocksize];
public intindexOf(byte 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_blocksize;
    int boffset=index%m_blocksize;
    int maxindex=m_firstFree/m_blocksize;
    byte[] 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_blocksize;
    block=m_map[maxindex];
    for(int offset=boffset;offset<maxoffset;++offset)
      if(block[offset]==elem)
        return offset+maxindex*m_blocksize;

    return -1;
public intindexOf(byte 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 voidinsertElementAt(byte 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 Byte to insert
param
at Index of where to insert

    if(at==m_firstFree)
      addElement(value);
    else if (at>m_firstFree)
    {
      int index=at/m_blocksize;
      if(index>=m_map.length)
      {
        int newsize=index+m_numblocks;
        byte[][] newMap=new byte[newsize][];
        System.arraycopy(m_map, 0, newMap, 0, m_map.length);
        m_map=newMap;
      }
      byte[] block=m_map[index];
      if(null==block)
        block=m_map[index]=new byte[m_blocksize];
      int offset=at%m_blocksize;
      block[offset]=value;
      m_firstFree=offset+1;
    }
    else
    {
      int index=at/m_blocksize;
      int maxindex=m_firstFree+1/m_blocksize;
      ++m_firstFree;
      int offset=at%m_blocksize;
      byte push;
      
      // ***** Easier to work down from top?
      while(index<=maxindex)
      {
        int copylen=m_blocksize-offset-1;
        byte[] block=m_map[index];
        if(null==block)
        {
          push=0;
          block=m_map[index]=new byte[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 intlastIndexOf(byte 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_blocksize;
    for(int index=m_firstFree/m_blocksize;
        index>=0;
        --index)
    {
      byte[] 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 voidremoveAllElements()
Wipe it out.

    m_firstFree = 0;
private booleanremoveElement(byte 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 Byte to remove from array
return
True if the byte was removed, false if it was not found

    int at=indexOf(s,0);
    if(at<0)
      return false;
    removeElementAt(at);
    return true;
private voidremoveElementAt(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
at index of where to remove a byte

    // No point in removing elements that "don't exist"...  
    if(at<m_firstFree)
    {
      int index=at/m_blocksize;
      int maxindex=m_firstFree/m_blocksize;
      int offset=at%m_blocksize;
      
      while(index<=maxindex)
      {
        int copylen=m_blocksize-offset-1;
        byte[] block=m_map[index];
        if(null==block)
          block=m_map[index]=new byte[m_blocksize];
        else
          System.arraycopy(block, offset+1, block, offset, copylen);
        if(index<maxindex)
        {
          byte[] 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 voidsetElementAt(byte 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;
      return;
    }

    int index=at/m_blocksize;
    int offset=at%m_blocksize;
        
    if(index>=m_map.length)
    {
      int newsize=index+m_numblocks;
      byte[][] newMap=new byte[newsize][];
      System.arraycopy(m_map, 0, newMap, 0, m_map.length);
      m_map=newMap;
    }

    byte[] block=m_map[index];
    if(null==block)
      block=m_map[index]=new byte[m_blocksize];
    block[offset]=value;

    if(at>=m_firstFree)
      m_firstFree=at+1;
private voidsetSize(int sz)
Set the length of the list.

return
length of the list

    if(m_firstFree<sz)
      m_firstFree = sz;
public intsize()
Get the length of the list.

return
length of the list

    return m_firstFree;