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