ChunkedIntArray


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