001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: SuballocatedByteVector.java 468655 2006-10-28 07:12:06Z minchau $
020 */
021 package org.apache.xml.utils;
022
023 /**
024 * A very simple table that stores a list of byte. Very similar API to our
025 * IntVector class (same API); different internal storage.
026 *
027 * This version uses an array-of-arrays solution. Read/write access is thus
028 * a bit slower than the simple IntVector, and basic storage is a trifle
029 * higher due to the top-level array -- but appending is O(1) fast rather
030 * than O(N**2) slow, which will swamp those costs in situations where
031 * long vectors are being built up.
032 *
033 * Known issues:
034 *
035 * Some methods are private because they haven't yet been tested properly.
036 *
037 * If an element has not been set (because we skipped it), its value will
038 * initially be 0. Shortening the vector does not clear old storage; if you
039 * then skip values and setElementAt a higher index again, you may see old data
040 * reappear in the truncated-and-restored section. Doing anything else would
041 * have performance costs.
042 * @xsl.usage internal
043 */
044 public class SuballocatedByteVector
045 {
046 /** Size of blocks to allocate */
047 protected int m_blocksize;
048
049 /** Number of blocks to (over)allocate by */
050 protected int m_numblocks=32;
051
052 /** Array of arrays of bytes */
053 protected byte m_map[][];
054
055 /** Number of bytes in array */
056 protected int m_firstFree = 0;
057
058 /** "Shortcut" handle to m_map[0] */
059 protected byte m_map0[];
060
061 /**
062 * Default constructor. Note that the default
063 * block size is very small, for small lists.
064 */
065 public SuballocatedByteVector()
066 {
067 this(2048);
068 }
069
070 /**
071 * Construct a ByteVector, using the given block size.
072 *
073 * @param blocksize Size of block to allocate
074 */
075 public SuballocatedByteVector(int blocksize)
076 {
077 m_blocksize = blocksize;
078 m_map0=new byte[blocksize];
079 m_map = new byte[m_numblocks][];
080 m_map[0]=m_map0;
081 }
082
083 /**
084 * Construct a ByteVector, using the given block size.
085 *
086 * @param blocksize Size of block to allocate
087 */
088 public SuballocatedByteVector(int blocksize, int increaseSize)
089 {
090 // increaseSize not currently used.
091 this(blocksize);
092 }
093
094
095 /**
096 * Get the length of the list.
097 *
098 * @return length of the list
099 */
100 public int size()
101 {
102 return m_firstFree;
103 }
104
105 /**
106 * Set the length of the list.
107 *
108 * @return length of the list
109 */
110 private void setSize(int sz)
111 {
112 if(m_firstFree<sz)
113 m_firstFree = sz;
114 }
115
116 /**
117 * Append a byte onto the vector.
118 *
119 * @param value Byte to add to the list
120 */
121 public void addElement(byte value)
122 {
123 if(m_firstFree<m_blocksize)
124 m_map0[m_firstFree++]=value;
125 else
126 {
127 int index=m_firstFree/m_blocksize;
128 int offset=m_firstFree%m_blocksize;
129 ++m_firstFree;
130
131 if(index>=m_map.length)
132 {
133 int newsize=index+m_numblocks;
134 byte[][] newMap=new byte[newsize][];
135 System.arraycopy(m_map, 0, newMap, 0, m_map.length);
136 m_map=newMap;
137 }
138 byte[] block=m_map[index];
139 if(null==block)
140 block=m_map[index]=new byte[m_blocksize];
141 block[offset]=value;
142 }
143 }
144
145 /**
146 * Append several byte values onto the vector.
147 *
148 * @param value Byte to add to the list
149 */
150 private void addElements(byte value, int numberOfElements)
151 {
152 if(m_firstFree+numberOfElements<m_blocksize)
153 for (int i = 0; i < numberOfElements; i++)
154 {
155 m_map0[m_firstFree++]=value;
156 }
157 else
158 {
159 int index=m_firstFree/m_blocksize;
160 int offset=m_firstFree%m_blocksize;
161 m_firstFree+=numberOfElements;
162 while( numberOfElements>0)
163 {
164 if(index>=m_map.length)
165 {
166 int newsize=index+m_numblocks;
167 byte[][] newMap=new byte[newsize][];
168 System.arraycopy(m_map, 0, newMap, 0, m_map.length);
169 m_map=newMap;
170 }
171 byte[] block=m_map[index];
172 if(null==block)
173 block=m_map[index]=new byte[m_blocksize];
174 int copied=(m_blocksize-offset < numberOfElements)
175 ? m_blocksize-offset : numberOfElements;
176 numberOfElements-=copied;
177 while(copied-- > 0)
178 block[offset++]=value;
179
180 ++index;offset=0;
181 }
182 }
183 }
184
185 /**
186 * Append several slots onto the vector, but do not set the values.
187 * Note: "Not Set" means the value is unspecified.
188 *
189 * @param numberOfElements
190 */
191 private void addElements(int numberOfElements)
192 {
193 int newlen=m_firstFree+numberOfElements;
194 if(newlen>m_blocksize)
195 {
196 int index=m_firstFree%m_blocksize;
197 int newindex=(m_firstFree+numberOfElements)%m_blocksize;
198 for(int i=index+1;i<=newindex;++i)
199 m_map[i]=new byte[m_blocksize];
200 }
201 m_firstFree=newlen;
202 }
203
204 /**
205 * Inserts the specified node in this vector at the specified index.
206 * Each component in this vector with an index greater or equal to
207 * the specified index is shifted upward to have an index one greater
208 * than the value it had previously.
209 *
210 * Insertion may be an EXPENSIVE operation!
211 *
212 * @param value Byte to insert
213 * @param at Index of where to insert
214 */
215 private void insertElementAt(byte value, int at)
216 {
217 if(at==m_firstFree)
218 addElement(value);
219 else if (at>m_firstFree)
220 {
221 int index=at/m_blocksize;
222 if(index>=m_map.length)
223 {
224 int newsize=index+m_numblocks;
225 byte[][] newMap=new byte[newsize][];
226 System.arraycopy(m_map, 0, newMap, 0, m_map.length);
227 m_map=newMap;
228 }
229 byte[] block=m_map[index];
230 if(null==block)
231 block=m_map[index]=new byte[m_blocksize];
232 int offset=at%m_blocksize;
233 block[offset]=value;
234 m_firstFree=offset+1;
235 }
236 else
237 {
238 int index=at/m_blocksize;
239 int maxindex=m_firstFree+1/m_blocksize;
240 ++m_firstFree;
241 int offset=at%m_blocksize;
242 byte push;
243
244 // ***** Easier to work down from top?
245 while(index<=maxindex)
246 {
247 int copylen=m_blocksize-offset-1;
248 byte[] block=m_map[index];
249 if(null==block)
250 {
251 push=0;
252 block=m_map[index]=new byte[m_blocksize];
253 }
254 else
255 {
256 push=block[m_blocksize-1];
257 System.arraycopy(block, offset , block, offset+1, copylen);
258 }
259 block[offset]=value;
260 value=push;
261 offset=0;
262 ++index;
263 }
264 }
265 }
266
267 /**
268 * Wipe it out.
269 */
270 public void removeAllElements()
271 {
272 m_firstFree = 0;
273 }
274
275 /**
276 * Removes the first occurrence of the argument from this vector.
277 * If the object is found in this vector, each component in the vector
278 * with an index greater or equal to the object's index is shifted
279 * downward to have an index one smaller than the value it had
280 * previously.
281 *
282 * @param s Byte to remove from array
283 *
284 * @return True if the byte was removed, false if it was not found
285 */
286 private boolean removeElement(byte s)
287 {
288 int at=indexOf(s,0);
289 if(at<0)
290 return false;
291 removeElementAt(at);
292 return true;
293 }
294
295 /**
296 * Deletes the component at the specified index. Each component in
297 * this vector with an index greater or equal to the specified
298 * index is shifted downward to have an index one smaller than
299 * the value it had previously.
300 *
301 * @param at index of where to remove a byte
302 */
303 private void removeElementAt(int at)
304 {
305 // No point in removing elements that "don't exist"...
306 if(at<m_firstFree)
307 {
308 int index=at/m_blocksize;
309 int maxindex=m_firstFree/m_blocksize;
310 int offset=at%m_blocksize;
311
312 while(index<=maxindex)
313 {
314 int copylen=m_blocksize-offset-1;
315 byte[] block=m_map[index];
316 if(null==block)
317 block=m_map[index]=new byte[m_blocksize];
318 else
319 System.arraycopy(block, offset+1, block, offset, copylen);
320 if(index<maxindex)
321 {
322 byte[] next=m_map[index+1];
323 if(next!=null)
324 block[m_blocksize-1]=(next!=null) ? next[0] : 0;
325 }
326 else
327 block[m_blocksize-1]=0;
328 offset=0;
329 ++index;
330 }
331 }
332 --m_firstFree;
333 }
334
335 /**
336 * Sets the component at the specified index of this vector to be the
337 * specified object. The previous component at that position is discarded.
338 *
339 * The index must be a value greater than or equal to 0 and less
340 * than the current size of the vector.
341 *
342 * @param value
343 * @param at Index of where to set the object
344 */
345 public void setElementAt(byte value, int at)
346 {
347 if(at<m_blocksize)
348 {
349 m_map0[at]=value;
350 return;
351 }
352
353 int index=at/m_blocksize;
354 int offset=at%m_blocksize;
355
356 if(index>=m_map.length)
357 {
358 int newsize=index+m_numblocks;
359 byte[][] newMap=new byte[newsize][];
360 System.arraycopy(m_map, 0, newMap, 0, m_map.length);
361 m_map=newMap;
362 }
363
364 byte[] block=m_map[index];
365 if(null==block)
366 block=m_map[index]=new byte[m_blocksize];
367 block[offset]=value;
368
369 if(at>=m_firstFree)
370 m_firstFree=at+1;
371 }
372
373 /**
374 * Get the nth element. This is often at the innermost loop of an
375 * application, so performance is critical.
376 *
377 * @param i index of value to get
378 *
379 * @return value at given index. If that value wasn't previously set,
380 * the result is undefined for performance reasons. It may throw an
381 * exception (see below), may return zero, or (if setSize has previously
382 * been used) may return stale data.
383 *
384 * @throws ArrayIndexOutOfBoundsException if the index was _clearly_
385 * unreasonable (negative, or past the highest block).
386 *
387 * @throws NullPointerException if the index points to a block that could
388 * have existed (based on the highest index used) but has never had anything
389 * set into it.
390 * %REVIEW% Could add a catch to create the block in that case, or return 0.
391 * Try/Catch is _supposed_ to be nearly free when not thrown to. Do we
392 * believe that? Should we have a separate safeElementAt?
393 */
394 public byte elementAt(int i)
395 {
396 // %OPT% Does this really buy us anything? Test versus division for small,
397 // test _plus_ division for big docs.
398 if(i<m_blocksize)
399 return m_map0[i];
400
401 return m_map[i/m_blocksize][i%m_blocksize];
402 }
403
404 /**
405 * Tell if the table contains the given node.
406 *
407 * @param s object to look for
408 *
409 * @return true if the object is in the list
410 */
411 private boolean contains(byte s)
412 {
413 return (indexOf(s,0) >= 0);
414 }
415
416 /**
417 * Searches for the first occurence of the given argument,
418 * beginning the search at index, and testing for equality
419 * using the equals method.
420 *
421 * @param elem object to look for
422 * @param index Index of where to begin search
423 * @return the index of the first occurrence of the object
424 * argument in this vector at position index or later in the
425 * vector; returns -1 if the object is not found.
426 */
427 public int indexOf(byte elem, int index)
428 {
429 if(index>=m_firstFree)
430 return -1;
431
432 int bindex=index/m_blocksize;
433 int boffset=index%m_blocksize;
434 int maxindex=m_firstFree/m_blocksize;
435 byte[] block;
436
437 for(;bindex<maxindex;++bindex)
438 {
439 block=m_map[bindex];
440 if(block!=null)
441 for(int offset=boffset;offset<m_blocksize;++offset)
442 if(block[offset]==elem)
443 return offset+bindex*m_blocksize;
444 boffset=0; // after first
445 }
446 // Last block may need to stop before end
447 int maxoffset=m_firstFree%m_blocksize;
448 block=m_map[maxindex];
449 for(int offset=boffset;offset<maxoffset;++offset)
450 if(block[offset]==elem)
451 return offset+maxindex*m_blocksize;
452
453 return -1;
454 }
455
456 /**
457 * Searches for the first occurence of the given argument,
458 * beginning the search at index, and testing for equality
459 * using the equals method.
460 *
461 * @param elem object to look for
462 * @return the index of the first occurrence of the object
463 * argument in this vector at position index or later in the
464 * vector; returns -1 if the object is not found.
465 */
466 public int indexOf(byte elem)
467 {
468 return indexOf(elem,0);
469 }
470
471 /**
472 * Searches for the first occurence of the given argument,
473 * beginning the search at index, and testing for equality
474 * using the equals method.
475 *
476 * @param elem Object to look for
477 * @return the index of the first occurrence of the object
478 * argument in this vector at position index or later in the
479 * vector; returns -1 if the object is not found.
480 */
481 private int lastIndexOf(byte elem)
482 {
483 int boffset=m_firstFree%m_blocksize;
484 for(int index=m_firstFree/m_blocksize;
485 index>=0;
486 --index)
487 {
488 byte[] block=m_map[index];
489 if(block!=null)
490 for(int offset=boffset; offset>=0; --offset)
491 if(block[offset]==elem)
492 return offset+index*m_blocksize;
493 boffset=0; // after first
494 }
495 return -1;
496 }
497
498 }