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: ChunkedIntArray.java,v 1.7 2004/02/16 23:06:11 minchau Exp $
018: */
019: package org.apache.xml.dtm.ref;
020:
021: import org.apache.xml.res.XMLErrorResources;
022: import org.apache.xml.res.XMLMessages;
023:
024: /**
025: * <code>ChunkedIntArray</code> is an extensible array of blocks of integers.
026: * (I'd consider Vector, but it's unable to handle integers except by
027: * turning them into Objects.)
028:
029: * <p>Making this a separate class means some call-and-return overhead. But
030: * doing it all inline tends to be fragile and expensive in coder time,
031: * not to mention driving up code size. If you want to inline it, feel free.
032: * The Java text suggest that private and Final methods may be inlined,
033: * and one can argue that this beast need not be made subclassable...</p>
034: *
035: * <p>%REVIEW% This has strong conceptual overlap with the IntVector class.
036: * It would probably be a good thing to merge the two, when time permits.<p>
037: */
038: final class ChunkedIntArray {
039: final int slotsize = 4; // Locked, MUST be power of two in current code
040: // Debugging tip: Cranking lowbits down to 4 or so is a good
041: // way to pound on the array addressing code.
042: static final int lowbits = 10; // How many bits address within chunks
043: static final int chunkalloc = 1 << lowbits;
044: static final int lowmask = chunkalloc - 1;
045:
046: ChunksVector chunks = new ChunksVector();
047: final int fastArray[] = new int[chunkalloc];
048: int lastUsed = 0;
049:
050: /**
051: * Create a new CIA with specified record size. Currently record size MUST
052: * be a power of two... and in fact is hardcoded to 4.
053: */
054: ChunkedIntArray(int slotsize) {
055: if (this .slotsize < slotsize)
056: throw new ArrayIndexOutOfBoundsException(
057: XMLMessages
058: .createXMLMessage(
059: XMLErrorResources.ER_CHUNKEDINTARRAY_NOT_SUPPORTED,
060: new Object[] { Integer
061: .toString(slotsize) })); //"ChunkedIntArray("+slotsize+") not currently supported");
062: else if (this .slotsize > slotsize)
063: System.out.println("*****WARNING: ChunkedIntArray("
064: + slotsize + ") wasting "
065: + (this .slotsize - slotsize) + " words per slot");
066: chunks.addElement(fastArray);
067: }
068:
069: /**
070: * Append a 4-integer record to the CIA, starting with record 1. (Since
071: * arrays are initialized to all-0, 0 has been reserved as the "unknown"
072: * value in DTM.)
073: * @return the index at which this record was inserted.
074: */
075: int appendSlot(int w0, int w1, int w2, int w3) {
076: /*
077: try
078: {
079: int newoffset = (lastUsed+1)*slotsize;
080: fastArray[newoffset] = w0;
081: fastArray[newoffset+1] = w1;
082: fastArray[newoffset+2] = w2;
083: fastArray[newoffset+3] = w3;
084: return ++lastUsed;
085: }
086: catch(ArrayIndexOutOfBoundsException aioobe)
087: */
088: {
089: final int slotsize = 4;
090: int newoffset = (lastUsed + 1) * slotsize;
091: int chunkpos = newoffset >> lowbits;
092: int slotpos = (newoffset & lowmask);
093:
094: // Grow if needed
095: if (chunkpos > chunks.size() - 1)
096: chunks.addElement(new int[chunkalloc]);
097: int[] chunk = chunks.elementAt(chunkpos);
098: chunk[slotpos] = w0;
099: chunk[slotpos + 1] = w1;
100: chunk[slotpos + 2] = w2;
101: chunk[slotpos + 3] = w3;
102:
103: return ++lastUsed;
104: }
105: }
106:
107: /**
108: * Retrieve an integer from the CIA by record number and column within
109: * the record, both 0-based (though position 0 is reserved for special
110: * purposes).
111: * @param position int Record number
112: * @param slotpos int Column number
113: */
114: int readEntry(int position, int offset)
115: throws ArrayIndexOutOfBoundsException {
116: /*
117: try
118: {
119: return fastArray[(position*slotsize)+offset];
120: }
121: catch(ArrayIndexOutOfBoundsException aioobe)
122: */
123: {
124: // System.out.println("Using slow read (1)");
125: if (offset >= slotsize)
126: throw new ArrayIndexOutOfBoundsException(
127: XMLMessages
128: .createXMLMessage(
129: XMLErrorResources.ER_OFFSET_BIGGER_THAN_SLOT,
130: null)); //"Offset bigger than slot");
131: position *= slotsize;
132: int chunkpos = position >> lowbits;
133: int slotpos = position & lowmask;
134: int[] chunk = chunks.elementAt(chunkpos);
135: return chunk[slotpos + offset];
136: }
137: }
138:
139: // Check that the node at index "position" is not an ancestor
140: // of the node at index "startPos". IF IT IS, DO NOT ACCEPT IT AND
141: // RETURN -1. If position is NOT an ancestor, return position.
142: // Special case: The Document node (position==0) is acceptable.
143: //
144: // This test supports DTM.getNextPreceding.
145: int specialFind(int startPos, int position) {
146: // We have to look all the way up the ancestor chain
147: // to make sure we don't have an ancestor.
148: int ancestor = startPos;
149: while (ancestor > 0) {
150: // Get the node whose index == ancestor
151: ancestor *= slotsize;
152: int chunkpos = ancestor >> lowbits;
153: int slotpos = ancestor & lowmask;
154: int[] chunk = chunks.elementAt(chunkpos);
155:
156: // Get that node's parent (Note that this assumes w[1]
157: // is the parent node index. That's really a DTM feature
158: // rather than a ChunkedIntArray feature.)
159: ancestor = chunk[slotpos + 1];
160:
161: if (ancestor == position)
162: break;
163: }
164:
165: if (ancestor <= 0) {
166: return position;
167: }
168: return -1;
169: }
170:
171: /**
172: * @return int index of highest-numbered record currently in use
173: */
174: int slotsUsed() {
175: return lastUsed;
176: }
177:
178: /** Disard the highest-numbered record. This is used in the string-buffer
179: CIA; when only a single characters() chunk has been recieved, its index
180: is moved into the Text node rather than being referenced by indirection
181: into the text accumulator.
182: */
183: void discardLast() {
184: --lastUsed;
185: }
186:
187: /**
188: * Overwrite the integer found at a specific record and column.
189: * Used to back-patch existing records, most often changing their
190: * "next sibling" reference from 0 (unknown) to something meaningful
191: * @param position int Record number
192: * @param offset int Column number
193: * @param value int New contents
194: */
195: void writeEntry(int position, int offset, int value)
196: throws ArrayIndexOutOfBoundsException {
197: /*
198: try
199: {
200: fastArray[( position*slotsize)+offset] = value;
201: }
202: catch(ArrayIndexOutOfBoundsException aioobe)
203: */
204: {
205: if (offset >= slotsize)
206: throw new ArrayIndexOutOfBoundsException(
207: XMLMessages
208: .createXMLMessage(
209: XMLErrorResources.ER_OFFSET_BIGGER_THAN_SLOT,
210: null)); //"Offset bigger than slot");
211: position *= slotsize;
212: int chunkpos = position >> lowbits;
213: int slotpos = position & lowmask;
214: int[] chunk = chunks.elementAt(chunkpos);
215: chunk[slotpos + offset] = value; // ATOMIC!
216: }
217: }
218:
219: /**
220: * Overwrite an entire (4-integer) record at the specified index.
221: * Mostly used to create record 0, the Document node.
222: * @param position integer Record number
223: * @param w0 int
224: * @param w1 int
225: * @param w2 int
226: * @param w3 int
227: */
228: void writeSlot(int position, int w0, int w1, int w2, int w3) {
229: position *= slotsize;
230: int chunkpos = position >> lowbits;
231: int slotpos = (position & lowmask);
232:
233: // Grow if needed
234: if (chunkpos > chunks.size() - 1)
235: chunks.addElement(new int[chunkalloc]);
236: int[] chunk = chunks.elementAt(chunkpos);
237: chunk[slotpos] = w0;
238: chunk[slotpos + 1] = w1;
239: chunk[slotpos + 2] = w2;
240: chunk[slotpos + 3] = w3;
241: }
242:
243: /**
244: * Retrieve the contents of a record into a user-supplied buffer array.
245: * Used to reduce addressing overhead when code will access several
246: * columns of the record.
247: * @param position int Record number
248: * @param buffer int[] Integer array provided by user, must be large enough
249: * to hold a complete record.
250: */
251: void readSlot(int position, int[] buffer) {
252: /*
253: try
254: {
255: System.arraycopy(fastArray, position*slotsize, buffer, 0, slotsize);
256: }
257: catch(ArrayIndexOutOfBoundsException aioobe)
258: */
259: {
260: // System.out.println("Using slow read (2): "+position);
261: position *= slotsize;
262: int chunkpos = position >> lowbits;
263: int slotpos = (position & lowmask);
264:
265: // Grow if needed
266: if (chunkpos > chunks.size() - 1)
267: chunks.addElement(new int[chunkalloc]);
268: int[] chunk = chunks.elementAt(chunkpos);
269: System.arraycopy(chunk, slotpos, buffer, 0, slotsize);
270: }
271: }
272:
273: class ChunksVector {
274: final int BLOCKSIZE = 64;
275: int[] m_map[] = new int[BLOCKSIZE][];
276: int m_mapSize = BLOCKSIZE;
277: int pos = 0;
278:
279: ChunksVector() {
280: }
281:
282: final int size() {
283: return pos;
284: }
285:
286: void addElement(int[] value) {
287: if (pos >= m_mapSize) {
288: int orgMapSize = m_mapSize;
289: while (pos >= m_mapSize)
290: m_mapSize += BLOCKSIZE;
291: int[] newMap[] = new int[m_mapSize][];
292: System.arraycopy(m_map, 0, newMap, 0, orgMapSize);
293: m_map = newMap;
294: }
295: // For now, just do a simple append. A sorted insert only
296: // makes sense if we're doing an binary search or some such.
297: m_map[pos] = value;
298: pos++;
299: }
300:
301: final int[] elementAt(int pos) {
302: return m_map[pos];
303: }
304: }
305: }
|