1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the  "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18/*
19 * $Id: ChunkedIntArray.java 468653 2006-10-28 07:07:05Z minchau $
20 */
21package org.apache.xml.dtm.ref;
22
23import org.apache.xml.res.XMLErrorResources;
24import org.apache.xml.res.XMLMessages;
25
26/**
27 * <code>ChunkedIntArray</code> is an extensible array of blocks of integers.
28 * (I'd consider Vector, but it's unable to handle integers except by
29 * turning them into Objects.)
30
31 * <p>Making this a separate class means some call-and-return overhead. But
32 * doing it all inline tends to be fragile and expensive in coder time,
33 * not to mention driving up code size. If you want to inline it, feel free.
34 * The Java text suggest that private and Final methods may be inlined,
35 * and one can argue that this beast need not be made subclassable...</p>
36 *
37 * <p>%REVIEW% This has strong conceptual overlap with the IntVector class.
38 * It would probably be a good thing to merge the two, when time permits.<p>
39 */
40final class ChunkedIntArray
41{
42  final int slotsize=4; // Locked, MUST be power of two in current code
43  // Debugging tip: Cranking lowbits down to 4 or so is a good
44  // way to pound on the array addressing code.
45  static final int lowbits=10; // How many bits address within chunks
46  static final int chunkalloc=1<<lowbits;
47  static final int lowmask=chunkalloc-1;
48
49  ChunksVector chunks=new ChunksVector();
50  final int fastArray[] = new int[chunkalloc];
51  int lastUsed=0;
52
53  /**
54   * Create a new CIA with specified record size. Currently record size MUST
55   * be a power of two... and in fact is hardcoded to 4.
56   */
57  ChunkedIntArray(int slotsize)
58  {
59    if(this.slotsize<slotsize)
60      throw new ArrayIndexOutOfBoundsException(XMLMessages.createXMLMessage(XMLErrorResources.ER_CHUNKEDINTARRAY_NOT_SUPPORTED, new Object[]{Integer.toString(slotsize)})); //"ChunkedIntArray("+slotsize+") not currently supported");
61    else if (this.slotsize>slotsize)
62      System.out.println("*****WARNING: ChunkedIntArray("+slotsize+") wasting "+(this.slotsize-slotsize)+" words per slot");
63    chunks.addElement(fastArray);
64  }
65  /**
66   * Append a 4-integer record to the CIA, starting with record 1. (Since
67   * arrays are initialized to all-0, 0 has been reserved as the "unknown"
68   * value in DTM.)
69   * @return the index at which this record was inserted.
70   */
71  int appendSlot(int w0, int w1, int w2, int w3)
72  {
73    /*
74    try
75    {
76      int newoffset = (lastUsed+1)*slotsize;
77      fastArray[newoffset] = w0;
78      fastArray[newoffset+1] = w1;
79      fastArray[newoffset+2] = w2;
80      fastArray[newoffset+3] = w3;
81      return ++lastUsed;
82    }
83    catch(ArrayIndexOutOfBoundsException aioobe)
84    */
85    {
86      final int slotsize=4;
87      int newoffset = (lastUsed+1)*slotsize;
88      int chunkpos = newoffset >> lowbits;
89      int slotpos = (newoffset & lowmask);
90
91      // Grow if needed
92      if (chunkpos > chunks.size() - 1)
93        chunks.addElement(new int[chunkalloc]);
94      int[] chunk = chunks.elementAt(chunkpos);
95      chunk[slotpos] = w0;
96      chunk[slotpos+1] = w1;
97      chunk[slotpos+2] = w2;
98      chunk[slotpos+3] = w3;
99
100      return ++lastUsed;
101    }
102  }
103  /**
104   * Retrieve an integer from the CIA by record number and column within
105   * the record, both 0-based (though position 0 is reserved for special
106   * purposes).
107   * @param position int Record number
108   * @param slotpos int Column number
109   */
110  int readEntry(int position, int offset) throws ArrayIndexOutOfBoundsException
111  {
112    /*
113    try
114    {
115      return fastArray[(position*slotsize)+offset];
116    }
117    catch(ArrayIndexOutOfBoundsException aioobe)
118    */
119    {
120      // System.out.println("Using slow read (1)");
121      if (offset>=slotsize)
122        throw new ArrayIndexOutOfBoundsException(XMLMessages.createXMLMessage(XMLErrorResources.ER_OFFSET_BIGGER_THAN_SLOT, null)); //"Offset bigger than slot");
123      position*=slotsize;
124      int chunkpos = position >> lowbits;
125      int slotpos = position & lowmask;
126      int[] chunk = chunks.elementAt(chunkpos);
127      return chunk[slotpos + offset];
128    }
129  }
130
131  // Check that the node at index "position" is not an ancestor
132  // of the node at index "startPos". IF IT IS, DO NOT ACCEPT IT AND
133  // RETURN -1. If position is NOT an ancestor, return position.
134  // Special case: The Document node (position==0) is acceptable.
135  //
136  // This test supports DTM.getNextPreceding.
137  int specialFind(int startPos, int position)
138  {
139          // We have to look all the way up the ancestor chain
140          // to make sure we don't have an ancestor.
141          int ancestor = startPos;
142          while(ancestor > 0)
143          {
144                // Get the node whose index == ancestor
145                ancestor*=slotsize;
146                int chunkpos = ancestor >> lowbits;
147                int slotpos = ancestor & lowmask;
148                int[] chunk = chunks.elementAt(chunkpos);
149
150                // Get that node's parent (Note that this assumes w[1]
151                // is the parent node index. That's really a DTM feature
152                // rather than a ChunkedIntArray feature.)
153                ancestor = chunk[slotpos + 1];
154
155                if(ancestor == position)
156                         break;
157          }
158
159          if (ancestor <= 0)
160          {
161                  return position;
162          }
163          return -1;
164  }
165
166  /**
167   * @return int index of highest-numbered record currently in use
168   */
169  int slotsUsed()
170  {
171    return lastUsed;
172  }
173
174  /** Disard the highest-numbered record. This is used in the string-buffer
175   CIA; when only a single characters() chunk has been recieved, its index
176   is moved into the Text node rather than being referenced by indirection
177   into the text accumulator.
178   */
179  void discardLast()
180  {
181    --lastUsed;
182  }
183
184  /**
185   * Overwrite the integer found at a specific record and column.
186   * Used to back-patch existing records, most often changing their
187   * "next sibling" reference from 0 (unknown) to something meaningful
188   * @param position int Record number
189   * @param offset int Column number
190   * @param value int New contents
191   */
192  void writeEntry(int position, int offset, int value) throws ArrayIndexOutOfBoundsException
193  {
194    /*
195    try
196    {
197      fastArray[( position*slotsize)+offset] = value;
198    }
199    catch(ArrayIndexOutOfBoundsException aioobe)
200    */
201    {
202      if (offset >= slotsize)
203        throw new ArrayIndexOutOfBoundsException(XMLMessages.createXMLMessage(XMLErrorResources.ER_OFFSET_BIGGER_THAN_SLOT, null)); //"Offset bigger than slot");
204      position*=slotsize;
205      int chunkpos = position >> lowbits;
206      int slotpos = position & lowmask;
207      int[] chunk = chunks.elementAt(chunkpos);
208      chunk[slotpos + offset] = value; // ATOMIC!
209    }
210  }
211
212  /**
213   * Overwrite an entire (4-integer) record at the specified index.
214   * Mostly used to create record 0, the Document node.
215   * @param position integer Record number
216   * @param w0 int
217   * @param w1 int
218   * @param w2 int
219   * @param w3 int
220   */
221  void writeSlot(int position, int w0, int w1, int w2, int w3)
222  {
223      position *= slotsize;
224      int chunkpos = position >> lowbits;
225      int slotpos = (position & lowmask);
226
227    // Grow if needed
228    if (chunkpos > chunks.size() - 1)
229      chunks.addElement(new int[chunkalloc]);
230    int[] chunk = chunks.elementAt(chunkpos);
231    chunk[slotpos] = w0;
232    chunk[slotpos + 1] = w1;
233    chunk[slotpos + 2] = w2;
234    chunk[slotpos + 3] = w3;
235  }
236
237  /**
238   * Retrieve the contents of a record into a user-supplied buffer array.
239   * Used to reduce addressing overhead when code will access several
240   * columns of the record.
241   * @param position int Record number
242   * @param buffer int[] Integer array provided by user, must be large enough
243   * to hold a complete record.
244   */
245  void readSlot(int position, int[] buffer)
246  {
247    /*
248    try
249    {
250      System.arraycopy(fastArray, position*slotsize, buffer, 0, slotsize);
251    }
252    catch(ArrayIndexOutOfBoundsException aioobe)
253    */
254    {
255      // System.out.println("Using slow read (2): "+position);
256      position *= slotsize;
257      int chunkpos = position >> lowbits;
258      int slotpos = (position & lowmask);
259
260      // Grow if needed
261      if (chunkpos > chunks.size() - 1)
262        chunks.addElement(new int[chunkalloc]);
263      int[] chunk = chunks.elementAt(chunkpos);
264      System.arraycopy(chunk,slotpos,buffer,0,slotsize);
265    }
266  }
267
268  class ChunksVector
269  {
270    final int BLOCKSIZE = 64;
271    int[] m_map[] = new int[BLOCKSIZE][];
272    int m_mapSize = BLOCKSIZE;
273    int pos = 0;
274
275    ChunksVector()
276    {
277    }
278
279    final int size()
280    {
281      return pos;
282    }
283
284    void addElement(int[] value)
285    {
286      if(pos >= m_mapSize)
287      {
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    {
303      return m_map[pos];
304    }
305  }
306}
307