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