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