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: SuballocatedIntVector.java,v 1.10 2004/02/17 04:21:14 minchau Exp $
  18. */
  19. package com.sun.org.apache.xml.internal.utils;
  20. /**
  21. * A very simple table that stores a list of int. Very similar API to our
  22. * IntVector class (same API); different internal storage.
  23. *
  24. * This version uses an array-of-arrays solution. Read/write access is thus
  25. * a bit slower than the simple IntVector, and basic storage is a trifle
  26. * higher due to the top-level array -- but appending is O(1) fast rather
  27. * than O(N**2) slow, which will swamp those costs in situations where
  28. * long vectors are being built up.
  29. *
  30. * Known issues:
  31. *
  32. * Some methods are private because they haven't yet been tested properly.
  33. *
  34. * Retrieval performance is critical, since this is used at the core
  35. * of the DTM model. (Append performance is almost as important.)
  36. * That's pushing me toward just letting reads from unset indices
  37. * throw exceptions or return stale data; safer behavior would have
  38. * performance costs.
  39. * */
  40. public class SuballocatedIntVector
  41. {
  42. /** Size of blocks to allocate */
  43. protected int m_blocksize;
  44. /** Bitwise addressing (much faster than div/remainder */
  45. protected int m_SHIFT, m_MASK;
  46. /** The default number of blocks to (over)allocate by */
  47. protected static final int NUMBLOCKS_DEFAULT = 32;
  48. /** The number of blocks to (over)allocate by */
  49. protected int m_numblocks = NUMBLOCKS_DEFAULT;
  50. /** Array of arrays of ints */
  51. protected int m_map[][];
  52. /** Number of ints in array */
  53. protected int m_firstFree = 0;
  54. /** "Shortcut" handle to m_map[0]. Surprisingly helpful for short vectors. */
  55. protected int m_map0[];
  56. /** "Shortcut" handle to most recently added row of m_map.
  57. * Very helpful during construction.
  58. * @xsl.usage internal
  59. */
  60. protected int m_buildCache[];
  61. protected int m_buildCacheStartIndex;
  62. /**
  63. * Default constructor. Note that the default
  64. * block size is currently 2K, which may be overkill for
  65. * small lists and undershootng for large ones.
  66. */
  67. public SuballocatedIntVector()
  68. {
  69. this(2048);
  70. }
  71. /**
  72. * Construct a IntVector, using the given block size and number
  73. * of blocks. For efficiency, we will round the requested size
  74. * off to a power of two.
  75. *
  76. * @param blocksize Size of block to allocate
  77. * @param numblocks Number of blocks to allocate
  78. * */
  79. public SuballocatedIntVector(int blocksize, int numblocks)
  80. {
  81. //m_blocksize = blocksize;
  82. for(m_SHIFT=0;0!=(blocksize>>>=1);++m_SHIFT)
  83. ;
  84. m_blocksize=1<<m_SHIFT;
  85. m_MASK=m_blocksize-1;
  86. m_numblocks = numblocks;
  87. m_map0=new int[m_blocksize];
  88. m_map = new int[numblocks][];
  89. m_map[0]=m_map0;
  90. m_buildCache = m_map0;
  91. m_buildCacheStartIndex = 0;
  92. }
  93. /** Construct a IntVector, using the given block size and
  94. * the default number of blocks (32).
  95. *
  96. * @param blocksize Size of block to allocate
  97. * */
  98. public SuballocatedIntVector(int blocksize)
  99. {
  100. this(blocksize, NUMBLOCKS_DEFAULT);
  101. }
  102. /**
  103. * Get the length of the list.
  104. *
  105. * @return length of the list
  106. */
  107. public int size()
  108. {
  109. return m_firstFree;
  110. }
  111. /**
  112. * Set the length of the list. This will only work to truncate the list, and
  113. * even then it has not been heavily tested and may not be trustworthy.
  114. *
  115. * @return length of the list
  116. */
  117. public void setSize(int sz)
  118. {
  119. if(m_firstFree>sz) // Whups; had that backward!
  120. m_firstFree = sz;
  121. }
  122. /**
  123. * Append a int onto the vector.
  124. *
  125. * @param value Int to add to the list
  126. */
  127. public void addElement(int value)
  128. {
  129. int indexRelativeToCache = m_firstFree - m_buildCacheStartIndex;
  130. // Is the new index an index into the cache row of m_map?
  131. if(indexRelativeToCache >= 0 && indexRelativeToCache < m_blocksize) {
  132. m_buildCache[indexRelativeToCache]=value;
  133. ++m_firstFree;
  134. } else {
  135. // Growing the outer array should be rare. We initialize to a
  136. // total of m_blocksize squared elements, which at the default
  137. // size is 4M integers... and we grow by at least that much each
  138. // time. However, attempts to microoptimize for this (assume
  139. // long enough and catch exceptions) yield no noticable
  140. // improvement.
  141. int index=m_firstFree>>>m_SHIFT;
  142. int offset=m_firstFree&m_MASK;
  143. if(index>=m_map.length)
  144. {
  145. int newsize=index+m_numblocks;
  146. int[][] newMap=new int[newsize][];
  147. System.arraycopy(m_map, 0, newMap, 0, m_map.length);
  148. m_map=newMap;
  149. }
  150. int[] block=m_map[index];
  151. if(null==block)
  152. block=m_map[index]=new int[m_blocksize];
  153. block[offset]=value;
  154. // Cache the current row of m_map. Next m_blocksize-1
  155. // values added will go to this row.
  156. m_buildCache = block;
  157. m_buildCacheStartIndex = m_firstFree-offset;
  158. ++m_firstFree;
  159. }
  160. }
  161. /**
  162. * Append several int values onto the vector.
  163. *
  164. * @param value Int to add to the list
  165. */
  166. private void addElements(int value, int numberOfElements)
  167. {
  168. if(m_firstFree+numberOfElements<m_blocksize)
  169. for (int i = 0; i < numberOfElements; i++)
  170. {
  171. m_map0[m_firstFree++]=value;
  172. }
  173. else
  174. {
  175. int index=m_firstFree>>>m_SHIFT;
  176. int offset=m_firstFree&m_MASK;
  177. m_firstFree+=numberOfElements;
  178. while( numberOfElements>0)
  179. {
  180. if(index>=m_map.length)
  181. {
  182. int newsize=index+m_numblocks;
  183. int[][] newMap=new int[newsize][];
  184. System.arraycopy(m_map, 0, newMap, 0, m_map.length);
  185. m_map=newMap;
  186. }
  187. int[] block=m_map[index];
  188. if(null==block)
  189. block=m_map[index]=new int[m_blocksize];
  190. int copied=(m_blocksize-offset < numberOfElements)
  191. ? m_blocksize-offset : numberOfElements;
  192. numberOfElements-=copied;
  193. while(copied-- > 0)
  194. block[offset++]=value;
  195. ++index;offset=0;
  196. }
  197. }
  198. }
  199. /**
  200. * Append several slots onto the vector, but do not set the values.
  201. * Note: "Not Set" means the value is unspecified.
  202. *
  203. * @param value Int to add to the list
  204. */
  205. private void addElements(int numberOfElements)
  206. {
  207. int newlen=m_firstFree+numberOfElements;
  208. if(newlen>m_blocksize)
  209. {
  210. int index=m_firstFree>>>m_SHIFT;
  211. int newindex=(m_firstFree+numberOfElements)>>>m_SHIFT;
  212. for(int i=index+1;i<=newindex;++i)
  213. m_map[i]=new int[m_blocksize];
  214. }
  215. m_firstFree=newlen;
  216. }
  217. /**
  218. * Inserts the specified node in this vector at the specified index.
  219. * Each component in this vector with an index greater or equal to
  220. * the specified index is shifted upward to have an index one greater
  221. * than the value it had previously.
  222. *
  223. * Insertion may be an EXPENSIVE operation!
  224. *
  225. * @param value Int to insert
  226. * @param at Index of where to insert
  227. */
  228. private void insertElementAt(int value, int at)
  229. {
  230. if(at==m_firstFree)
  231. addElement(value);
  232. else if (at>m_firstFree)
  233. {
  234. int index=at>>>m_SHIFT;
  235. if(index>=m_map.length)
  236. {
  237. int newsize=index+m_numblocks;
  238. int[][] newMap=new int[newsize][];
  239. System.arraycopy(m_map, 0, newMap, 0, m_map.length);
  240. m_map=newMap;
  241. }
  242. int[] block=m_map[index];
  243. if(null==block)
  244. block=m_map[index]=new int[m_blocksize];
  245. int offset=at&m_MASK;
  246. block[offset]=value;
  247. m_firstFree=offset+1;
  248. }
  249. else
  250. {
  251. int index=at>>>m_SHIFT;
  252. int maxindex=m_firstFree>>>m_SHIFT; // %REVIEW% (m_firstFree+1?)
  253. ++m_firstFree;
  254. int offset=at&m_MASK;
  255. int push;
  256. // ***** Easier to work down from top?
  257. while(index<=maxindex)
  258. {
  259. int copylen=m_blocksize-offset-1;
  260. int[] block=m_map[index];
  261. if(null==block)
  262. {
  263. push=0;
  264. block=m_map[index]=new int[m_blocksize];
  265. }
  266. else
  267. {
  268. push=block[m_blocksize-1];
  269. System.arraycopy(block, offset , block, offset+1, copylen);
  270. }
  271. block[offset]=value;
  272. value=push;
  273. offset=0;
  274. ++index;
  275. }
  276. }
  277. }
  278. /**
  279. * Wipe it out. Currently defined as equivalent to setSize(0).
  280. */
  281. public void removeAllElements()
  282. {
  283. m_firstFree = 0;
  284. m_buildCache = m_map0;
  285. m_buildCacheStartIndex = 0;
  286. }
  287. /**
  288. * Removes the first occurrence of the argument from this vector.
  289. * If the object is found in this vector, each component in the vector
  290. * with an index greater or equal to the object's index is shifted
  291. * downward to have an index one smaller than the value it had
  292. * previously.
  293. *
  294. * @param s Int to remove from array
  295. *
  296. * @return True if the int was removed, false if it was not found
  297. */
  298. private boolean removeElement(int s)
  299. {
  300. int at=indexOf(s,0);
  301. if(at<0)
  302. return false;
  303. removeElementAt(at);
  304. return true;
  305. }
  306. /**
  307. * Deletes the component at the specified index. Each component in
  308. * this vector with an index greater or equal to the specified
  309. * index is shifted downward to have an index one smaller than
  310. * the value it had previously.
  311. *
  312. * @param i index of where to remove and int
  313. */
  314. private void removeElementAt(int at)
  315. {
  316. // No point in removing elements that "don't exist"...
  317. if(at<m_firstFree)
  318. {
  319. int index=at>>>m_SHIFT;
  320. int maxindex=m_firstFree>>>m_SHIFT;
  321. int offset=at&m_MASK;
  322. while(index<=maxindex)
  323. {
  324. int copylen=m_blocksize-offset-1;
  325. int[] block=m_map[index];
  326. if(null==block)
  327. block=m_map[index]=new int[m_blocksize];
  328. else
  329. System.arraycopy(block, offset+1, block, offset, copylen);
  330. if(index<maxindex)
  331. {
  332. int[] next=m_map[index+1];
  333. if(next!=null)
  334. block[m_blocksize-1]=(next!=null) ? next[0] : 0;
  335. }
  336. else
  337. block[m_blocksize-1]=0;
  338. offset=0;
  339. ++index;
  340. }
  341. }
  342. --m_firstFree;
  343. }
  344. /**
  345. * Sets the component at the specified index of this vector to be the
  346. * specified object. The previous component at that position is discarded.
  347. *
  348. * The index must be a value greater than or equal to 0 and less
  349. * than the current size of the vector.
  350. *
  351. * @param node object to set
  352. * @param index Index of where to set the object
  353. */
  354. public void setElementAt(int value, int at)
  355. {
  356. if(at<m_blocksize)
  357. m_map0[at]=value;
  358. else
  359. {
  360. int index=at>>>m_SHIFT;
  361. int offset=at&m_MASK;
  362. if(index>=m_map.length)
  363. {
  364. int newsize=index+m_numblocks;
  365. int[][] newMap=new int[newsize][];
  366. System.arraycopy(m_map, 0, newMap, 0, m_map.length);
  367. m_map=newMap;
  368. }
  369. int[] block=m_map[index];
  370. if(null==block)
  371. block=m_map[index]=new int[m_blocksize];
  372. block[offset]=value;
  373. }
  374. if(at>=m_firstFree)
  375. m_firstFree=at+1;
  376. }
  377. /**
  378. * Get the nth element. This is often at the innermost loop of an
  379. * application, so performance is critical.
  380. *
  381. * @param i index of value to get
  382. *
  383. * @return value at given index. If that value wasn't previously set,
  384. * the result is undefined for performance reasons. It may throw an
  385. * exception (see below), may return zero, or (if setSize has previously
  386. * been used) may return stale data.
  387. *
  388. * @throw ArrayIndexOutOfBoundsException if the index was _clearly_
  389. * unreasonable (negative, or past the highest block).
  390. *
  391. * @throw NullPointerException if the index points to a block that could
  392. * have existed (based on the highest index used) but has never had anything
  393. * set into it.
  394. * %REVIEW% Could add a catch to create the block in that case, or return 0.
  395. * Try/Catch is _supposed_ to be nearly free when not thrown to. Do we
  396. * believe that? Should we have a separate safeElementAt?
  397. */
  398. public int elementAt(int i)
  399. {
  400. // This is actually a significant optimization!
  401. if(i<m_blocksize)
  402. return m_map0[i];
  403. return m_map[i>>>m_SHIFT][i&m_MASK];
  404. }
  405. /**
  406. * Tell if the table contains the given node.
  407. *
  408. * @param s object to look for
  409. *
  410. * @return true if the object is in the list
  411. */
  412. private boolean contains(int s)
  413. {
  414. return (indexOf(s,0) >= 0);
  415. }
  416. /**
  417. * Searches for the first occurence of the given argument,
  418. * beginning the search at index, and testing for equality
  419. * using the equals method.
  420. *
  421. * @param elem object to look for
  422. * @param index Index of where to begin search
  423. * @return the index of the first occurrence of the object
  424. * argument in this vector at position index or later in the
  425. * vector; returns -1 if the object is not found.
  426. */
  427. public int indexOf(int elem, int index)
  428. {
  429. if(index>=m_firstFree)
  430. return -1;
  431. int bindex=index>>>m_SHIFT;
  432. int boffset=index&m_MASK;
  433. int maxindex=m_firstFree>>>m_SHIFT;
  434. int[] block;
  435. for(;bindex<maxindex;++bindex)
  436. {
  437. block=m_map[bindex];
  438. if(block!=null)
  439. for(int offset=boffset;offset<m_blocksize;++offset)
  440. if(block[offset]==elem)
  441. return offset+bindex*m_blocksize;
  442. boffset=0; // after first
  443. }
  444. // Last block may need to stop before end
  445. int maxoffset=m_firstFree&m_MASK;
  446. block=m_map[maxindex];
  447. for(int offset=boffset;offset<maxoffset;++offset)
  448. if(block[offset]==elem)
  449. return offset+maxindex*m_blocksize;
  450. return -1;
  451. }
  452. /**
  453. * Searches for the first occurence of the given argument,
  454. * beginning the search at index, and testing for equality
  455. * using the equals method.
  456. *
  457. * @param elem object to look for
  458. * @return the index of the first occurrence of the object
  459. * argument in this vector at position index or later in the
  460. * vector; returns -1 if the object is not found.
  461. */
  462. public int indexOf(int elem)
  463. {
  464. return indexOf(elem,0);
  465. }
  466. /**
  467. * Searches for the first occurence of the given argument,
  468. * beginning the search at index, and testing for equality
  469. * using the equals method.
  470. *
  471. * @param elem Object to look for
  472. * @return the index of the first occurrence of the object
  473. * argument in this vector at position index or later in the
  474. * vector; returns -1 if the object is not found.
  475. */
  476. private int lastIndexOf(int elem)
  477. {
  478. int boffset=m_firstFree&m_MASK;
  479. for(int index=m_firstFree>>>m_SHIFT;
  480. index>=0;
  481. --index)
  482. {
  483. int[] block=m_map[index];
  484. if(block!=null)
  485. for(int offset=boffset; offset>=0; --offset)
  486. if(block[offset]==elem)
  487. return offset+index*m_blocksize;
  488. boffset=0; // after first
  489. }
  490. return -1;
  491. }
  492. /**
  493. * Return the internal m_map0 array
  494. * @return the m_map0 array
  495. */
  496. public final int[] getMap0()
  497. {
  498. return m_map0;
  499. }
  500. /**
  501. * Return the m_map double array
  502. * @return the internal map of array of arrays
  503. */
  504. public final int[][] getMap()
  505. {
  506. return m_map;
  507. }
  508. }