KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > org > apache > xml > internal > utils > 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 com.sun.org.apache.xml.internal.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
Popular Tags