SuballocatedByteVector


1   /*
2    * Copyright 1999-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  /*
17   * $Id: SuballocatedByteVector.java,v 1.6 2004/02/17 04:21:14 minchau Exp $
18   */
19  package org.apache.xml.utils;
20  
21  /**
22   * A very simple table that stores a list of byte. Very similar API to our
23   * IntVector class (same API); different internal storage.
24   * 
25   * This version uses an array-of-arrays solution. Read/write access is thus
26   * a bit slower than the simple IntVector, and basic storage is a trifle
27   * higher due to the top-level array -- but appending is O(1) fast rather
28   * than O(N**2) slow, which will swamp those costs in situations where
29   * long vectors are being built up.
30   * 
31   * Known issues:
32   * 
33   * Some methods are private because they haven't yet been tested properly.
34   * 
35   * If an element has not been set (because we skipped it), its value will
36   * initially be 0. Shortening the vector does not clear old storage; if you
37   * then skip values and setElementAt a higher index again, you may see old data
38   * reappear in the truncated-and-restored section. Doing anything else would
39   * have performance costs.
40   * @xsl.usage internal
41   */
42  public class SuballocatedByteVector
43  {
44    /** Size of blocks to allocate          */
45    protected int m_blocksize;
46    
47    /** Number of blocks to (over)allocate by */
48    protected  int m_numblocks=32;
49    
50    /** Array of arrays of bytes          */
51    protected byte m_map[][];
52  
53    /** Number of bytes in array          */
54    protected int m_firstFree = 0;
55  
56    /** "Shortcut" handle to m_map[0] */
57    protected byte m_map0[];
58  
59    /**
60     * Default constructor.  Note that the default
61     * block size is very small, for small lists.
62     */
63    public SuballocatedByteVector()
64    {
65      this(2048);
66    }
67  
68    /**
69     * Construct a ByteVector, using the given block size.
70     *
71     * @param blocksize Size of block to allocate
72     */
73    public SuballocatedByteVector(int blocksize)
74    {
75      m_blocksize = blocksize;
76      m_map0=new byte[blocksize];
77      m_map = new byte[m_numblocks][];
78      m_map[0]=m_map0;
79    }
80    
81    /**
82     * Construct a ByteVector, using the given block size.
83     *
84     * @param blocksize Size of block to allocate
85     */
86    public SuballocatedByteVector(int blocksize, int increaseSize)
87    {
88      // increaseSize not currently used.
89      this(blocksize);
90    }
91  
92  
93    /**
94     * Get the length of the list.
95     *
96     * @return length of the list
97     */
98    public int size()
99    {
100     return m_firstFree;
101   }
102   
103   /**
104    * Set the length of the list.
105    *
106    * @return length of the list
107    */
108   private  void setSize(int sz)
109   {
110     if(m_firstFree<sz)
111       m_firstFree = sz;
112   }
113 
114   /**
115    * Append a byte onto the vector.
116    *
117    * @param value Byte to add to the list 
118    */
119   public  void addElement(byte value)
120   {
121     if(m_firstFree<m_blocksize)
122       m_map0[m_firstFree++]=value;
123     else
124     {
125       int index=m_firstFree/m_blocksize;
126       int offset=m_firstFree%m_blocksize;
127       ++m_firstFree;
128 
129       if(index>=m_map.length)
130       {
131         int newsize=index+m_numblocks;
132         byte[][] newMap=new byte[newsize][];
133         System.arraycopy(m_map, 0, newMap, 0, m_map.length);
134         m_map=newMap;
135       }
136       byte[] block=m_map[index];
137       if(null==block)
138         block=m_map[index]=new byte[m_blocksize];
139       block[offset]=value;
140     }
141   }
142   
143   /**
144    * Append several byte values onto the vector.
145    *
146    * @param value Byte to add to the list 
147    */
148   private  void addElements(byte value, int numberOfElements)
149   {
150     if(m_firstFree+numberOfElements<m_blocksize)
151       for (int i = 0; i < numberOfElements; i++) 
152       {
153         m_map0[m_firstFree++]=value;
154       }
155     else
156     {
157       int index=m_firstFree/m_blocksize;
158       int offset=m_firstFree%m_blocksize;
159       m_firstFree+=numberOfElements;
160       while( numberOfElements>0)
161       {
162         if(index>=m_map.length)
163         {
164           int newsize=index+m_numblocks;
165           byte[][] newMap=new byte[newsize][];
166           System.arraycopy(m_map, 0, newMap, 0, m_map.length);
167           m_map=newMap;
168         }
169         byte[] block=m_map[index];
170         if(null==block)
171           block=m_map[index]=new byte[m_blocksize];
172         int copied=(m_blocksize-offset < numberOfElements)
173           ? m_blocksize-offset : numberOfElements;
174         numberOfElements-=copied;
175         while(copied-- > 0)
176           block[offset++]=value;
177 
178         ++index;offset=0;
179       }
180     }
181   }
182   
183   /**
184    * Append several slots onto the vector, but do not set the values.
185    * Note: "Not Set" means the value is unspecified.
186    *
187    * @param value Byte to add to the list 
188    */
189   private  void addElements(int numberOfElements)
190   {
191     int newlen=m_firstFree+numberOfElements;
192     if(newlen>m_blocksize)
193     {
194       int index=m_firstFree%m_blocksize;
195       int newindex=(m_firstFree+numberOfElements)%m_blocksize;
196       for(int i=index+1;i<=newindex;++i)
197         m_map[i]=new byte[m_blocksize];
198     }
199     m_firstFree=newlen;
200   }
201   
202   /**
203    * Inserts the specified node in this vector at the specified index.
204    * Each component in this vector with an index greater or equal to
205    * the specified index is shifted upward to have an index one greater
206    * than the value it had previously.
207    *
208    * Insertion may be an EXPENSIVE operation!
209    *
210    * @param value Byte to insert
211    * @param at Index of where to insert 
212    */
213   private  void insertElementAt(byte value, int at)
214   {
215     if(at==m_firstFree)
216       addElement(value);
217     else if (at>m_firstFree)
218     {
219       int index=at/m_blocksize;
220       if(index>=m_map.length)
221       {
222         int newsize=index+m_numblocks;
223         byte[][] newMap=new byte[newsize][];
224         System.arraycopy(m_map, 0, newMap, 0, m_map.length);
225         m_map=newMap;
226       }
227       byte[] block=m_map[index];
228       if(null==block)
229         block=m_map[index]=new byte[m_blocksize];
230       int offset=at%m_blocksize;
231       block[offset]=value;
232       m_firstFree=offset+1;
233     }
234     else
235     {
236       int index=at/m_blocksize;
237       int maxindex=m_firstFree+1/m_blocksize;
238       ++m_firstFree;
239       int offset=at%m_blocksize;
240       byte push;
241       
242       // ***** Easier to work down from top?
243       while(index<=maxindex)
244       {
245         int copylen=m_blocksize-offset-1;
246         byte[] block=m_map[index];
247         if(null==block)
248         {
249           push=0;
250           block=m_map[index]=new byte[m_blocksize];
251         }
252         else
253         {
254           push=block[m_blocksize-1];
255           System.arraycopy(block, offset , block, offset+1, copylen);
256         }
257         block[offset]=value;
258         value=push;
259         offset=0;
260         ++index;
261       }
262     }
263   }
264 
265   /**
266    * Wipe it out. 
267    */
268   public void removeAllElements()
269   {
270     m_firstFree = 0;
271   }
272 
273   /**
274    * Removes the first occurrence of the argument from this vector.
275    * If the object is found in this vector, each component in the vector
276    * with an index greater or equal to the object's index is shifted
277    * downward to have an index one smaller than the value it had
278    * previously.
279    *
280    * @param s Byte to remove from array
281    *
282    * @return True if the byte was removed, false if it was not found
283    */
284   private  boolean removeElement(byte s)
285   {
286     int at=indexOf(s,0);
287     if(at<0)
288       return false;
289     removeElementAt(at);
290     return true;
291   }
292 
293   /**
294    * Deletes the component at the specified index. Each component in
295    * this vector with an index greater or equal to the specified
296    * index is shifted downward to have an index one smaller than
297    * the value it had previously.
298    *
299    * @param at index of where to remove a byte
300    */
301   private  void removeElementAt(int at)
302   {
303     // No point in removing elements that "don't exist"...  
304     if(at<m_firstFree)
305     {
306       int index=at/m_blocksize;
307       int maxindex=m_firstFree/m_blocksize;
308       int offset=at%m_blocksize;
309       
310       while(index<=maxindex)
311       {
312         int copylen=m_blocksize-offset-1;
313         byte[] block=m_map[index];
314         if(null==block)
315           block=m_map[index]=new byte[m_blocksize];
316         else
317           System.arraycopy(block, offset+1, block, offset, copylen);
318         if(index<maxindex)
319         {
320           byte[] next=m_map[index+1];
321           if(next!=null)
322             block[m_blocksize-1]=(next!=null) ? next[0] : 0;
323         }
324         else
325           block[m_blocksize-1]=0;
326         offset=0;
327         ++index;
328       }
329     }
330     --m_firstFree;
331   }
332 
333   /**
334    * Sets the component at the specified index of this vector to be the
335    * specified object. The previous component at that position is discarded.
336    *
337    * The index must be a value greater than or equal to 0 and less
338    * than the current size of the vector.
339    *
340    * @param node object to set
341    * @param index Index of where to set the object
342    */
343   public void setElementAt(byte value, int at)
344   {
345     if(at<m_blocksize)
346     {
347       m_map0[at]=value;
348       return;
349     }
350 
351     int index=at/m_blocksize;
352     int offset=at%m_blocksize;
353         
354     if(index>=m_map.length)
355     {
356       int newsize=index+m_numblocks;
357       byte[][] newMap=new byte[newsize][];
358       System.arraycopy(m_map, 0, newMap, 0, m_map.length);
359       m_map=newMap;
360     }
361 
362     byte[] block=m_map[index];
363     if(null==block)
364       block=m_map[index]=new byte[m_blocksize];
365     block[offset]=value;
366 
367     if(at>=m_firstFree)
368       m_firstFree=at+1;
369   }
370 
371   /**
372    * Get the nth element. This is often at the innermost loop of an
373    * application, so performance is critical.
374    *
375    * @param i index of value to get
376    *
377    * @return value at given index. If that value wasn't previously set,
378    * the result is undefined for performance reasons. It may throw an
379    * exception (see below), may return zero, or (if setSize has previously
380    * been used) may return stale data.
381    *
382    * @throw ArrayIndexOutOfBoundsException if the index was _clearly_
383    * unreasonable (negative, or past the highest block).
384    *
385    * @throw NullPointerException if the index points to a block that could
386    * have existed (based on the highest index used) but has never had anything
387    * set into it.
388    * %REVIEW% Could add a catch to create the block in that case, or return 0.
389    * Try/Catch is _supposed_ to be nearly free when not thrown to. Do we
390    * believe that? Should we have a separate safeElementAt?
391    */
392   public byte elementAt(int i)
393   {
394     // %OPT% Does this really buy us anything? Test versus division for small,
395     // test _plus_ division for big docs.
396     if(i<m_blocksize)
397       return m_map0[i];
398 
399     return m_map[i/m_blocksize][i%m_blocksize];
400   }
401 
402   /**
403    * Tell if the table contains the given node.
404    *
405    * @param s object to look for
406    *
407    * @return true if the object is in the list
408    */
409   private  boolean contains(byte s)
410   {
411     return (indexOf(s,0) >= 0);
412   }
413 
414   /**
415    * Searches for the first occurence of the given argument,
416    * beginning the search at index, and testing for equality
417    * using the equals method.
418    *
419    * @param elem object to look for
420    * @param index Index of where to begin search
421    * @return the index of the first occurrence of the object
422    * argument in this vector at position index or later in the
423    * vector; returns -1 if the object is not found.
424    */
425   public int indexOf(byte elem, int index)
426   {
427     if(index>=m_firstFree)
428       return -1;
429           
430     int bindex=index/m_blocksize;
431     int boffset=index%m_blocksize;
432     int maxindex=m_firstFree/m_blocksize;
433     byte[] block;
434     
435     for(;bindex<maxindex;++bindex)
436     {
437       block=m_map[bindex];
438       if(block!=null)
439         for(int offset=boffset;offset<m_blocksize;++offset)
440           if(block[offset]==elem)
441             return offset+bindex*m_blocksize;
442       boffset=0; // after first
443     }
444     // Last block may need to stop before end
445     int maxoffset=m_firstFree%m_blocksize;
446     block=m_map[maxindex];
447     for(int offset=boffset;offset<maxoffset;++offset)
448       if(block[offset]==elem)
449         return offset+maxindex*m_blocksize;
450 
451     return -1;    
452   }
453 
454   /**
455    * Searches for the first occurence of the given argument,
456    * beginning the search at index, and testing for equality
457    * using the equals method.
458    *
459    * @param elem object to look for
460    * @return the index of the first occurrence of the object
461    * argument in this vector at position index or later in the
462    * vector; returns -1 if the object is not found.
463    */
464   public int indexOf(byte elem)
465   {
466     return indexOf(elem,0);
467   }
468 
469   /**
470    * Searches for the first occurence of the given argument,
471    * beginning the search at index, and testing for equality
472    * using the equals method.
473    *
474    * @param elem Object to look for
475    * @return the index of the first occurrence of the object
476    * argument in this vector at position index or later in the
477    * vector; returns -1 if the object is not found.
478    */
479   private  int lastIndexOf(byte elem)
480   {
481     int boffset=m_firstFree%m_blocksize;
482     for(int index=m_firstFree/m_blocksize;
483         index>=0;
484         --index)
485     {
486       byte[] block=m_map[index];
487       if(block!=null)
488         for(int offset=boffset; offset>=0; --offset)
489           if(block[offset]==elem)
490             return offset+index*m_blocksize;
491       boffset=0; // after first
492     }
493     return -1;
494   }
495 
496 }
497
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags