< prev index next >

src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/SparseArrayData.java

Print this page




  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.runtime.arrays;
  27 
  28 import java.util.Arrays;
  29 import java.util.Map;
  30 import java.util.TreeMap;
  31 import jdk.nashorn.internal.codegen.types.Type;
  32 import jdk.nashorn.internal.runtime.JSType;
  33 import jdk.nashorn.internal.runtime.ScriptRuntime;
  34 
  35 /**
  36  * Handle arrays where the index is very large.
  37  */
  38 class SparseArrayData extends ArrayData {

  39     static final int MAX_DENSE_LENGTH = 1024 * 1024;
  40 
  41     /** Underlying array. */
  42     private ArrayData underlying;
  43 
  44     /** Maximum length to be stored in the array. */
  45     private final long maxDenseLength;
  46 
  47     /** Sparse elements. */
  48     private TreeMap<Long, Object> sparseMap;
  49 
  50     SparseArrayData(final ArrayData underlying, final long length) {
  51         this(underlying, length, new TreeMap<>());
  52     }
  53 
  54     SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
  55         super(length);
  56         assert underlying.length() <= length;
  57         this.underlying = underlying;
  58         this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length());
  59         this.sparseMap = sparseMap;
  60     }
  61 
  62     @Override
  63     public ArrayData copy() {
  64         return new SparseArrayData(underlying.copy(), length(), new TreeMap<>(sparseMap));
  65     }
  66 
  67     @Override
  68     public Object[] asObjectArray() {
  69         final int len = (int)Math.min(length(), Integer.MAX_VALUE);
  70         final int underlyingLength = (int)Math.min(len, underlying.length());
  71         final Object[] objArray = new Object[len];
  72 
  73         for (int i = 0; i < underlyingLength; i++) {
  74             objArray[i] = underlying.getObject(i);
  75         }
  76 
  77         Arrays.fill(objArray, underlyingLength, len, ScriptRuntime.UNDEFINED);
  78 
  79         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
  80             final long key = entry.getKey();
  81             if (key < Integer.MAX_VALUE) {
  82                 objArray[(int)key] = entry.getValue();
  83             } else {
  84                 break; // ascending key order
  85             }
  86         }
  87 
  88         return objArray;
  89     }
  90 
  91     @Override
  92     public void shiftLeft(final int by) {
  93         underlying.shiftLeft(by);
  94 
  95         final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
  96 
  97         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
  98             final long newIndex = entry.getKey() - by;

  99             if (newIndex < maxDenseLength) {
 100                 underlying = underlying.set((int) newIndex, entry.getValue(), false);
 101             } else if (newIndex >= 0) {



 102                 newSparseMap.put(newIndex, entry.getValue());
 103             }
 104         }

 105 
 106         sparseMap = newSparseMap;
 107         setLength(Math.max(length() - by, 0));


 108     }
 109 
 110     @Override
 111     public ArrayData shiftRight(final int by) {
 112         final TreeMap<Long, Object> newSparseMap = new TreeMap<>();

 113         final long len = underlying.length();
 114         if (len + by > maxDenseLength) {
 115             for (long i = maxDenseLength - by; i < len; i++) {


 116                 if (underlying.has((int) i)) {
 117                     newSparseMap.put(i + by, underlying.getObject((int) i));
 118                 }
 119             }
 120             underlying = underlying.shrink((int) (maxDenseLength - by));

 121         }
 122 
 123         underlying.shiftRight(by);
 124 
 125         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
 126             final long newIndex = entry.getKey() + by;
 127             newSparseMap.put(newIndex, entry.getValue());
 128         }
 129 
 130         sparseMap = newSparseMap;
 131         setLength(length() + by);
 132 
 133         return this;
 134     }
 135 
 136     @Override
 137     public ArrayData ensure(final long safeIndex) {
 138         // Usually #ensure only needs to be called if safeIndex is greater or equal current length.
 139         // SparseArrayData is an exception as an index smaller than our current length may still
 140         // exceed the underlying ArrayData's capacity. Because of this, SparseArrayData invokes
 141         // its ensure method internally in various places where other ArrayData subclasses don't,
 142         // making it safe for outside uses to only call ensure(safeIndex) if safeIndex >= length.
 143         if (safeIndex < maxDenseLength && underlying.length() <= safeIndex) {
 144             underlying = underlying.ensure(safeIndex);
 145         }
 146         if (safeIndex >= length()) {
 147             setLength(safeIndex + 1);
 148         }
 149         return this;
 150     }
 151 
 152     @Override
 153     public ArrayData shrink(final long newLength) {
 154         if (newLength < underlying.length()) {
 155             underlying = underlying.shrink(newLength);
 156             underlying.setLength(newLength);
 157             sparseMap.clear();
 158             setLength(newLength);
 159         }
 160 
 161         sparseMap.subMap(newLength, Long.MAX_VALUE).clear();
 162         setLength(newLength);
 163         return this;
 164     }
 165 
 166     @Override
 167     public ArrayData set(final int index, final Object value, final boolean strict) {
 168         if (index >= 0 && index < maxDenseLength) {
 169             final long oldLength = underlying.length();
 170             ensure(index);
 171             underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
 172             setLength(Math.max(underlying.length(), length()));
 173         } else {
 174             final Long longIndex = indexToKey(index);
 175             sparseMap.put(longIndex, value);
 176             setLength(Math.max(longIndex + 1, length()));
 177         }
 178 
 179         return this;
 180     }
 181 
 182     @Override
 183     public ArrayData set(final int index, final int value, final boolean strict) {
 184         if (index >= 0 && index < maxDenseLength) {
 185             final long oldLength = underlying.length();
 186             ensure(index);
 187             underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
 188             setLength(Math.max(underlying.length(), length()));
 189         } else {
 190             final Long longIndex = indexToKey(index);
 191             sparseMap.put(longIndex, value);
 192             setLength(Math.max(longIndex + 1, length()));
 193         }
 194         return this;
 195     }
 196 
 197     @Override
 198     public ArrayData set(final int index, final double value, final boolean strict) {
 199         if (index >= 0 && index < maxDenseLength) {
 200             final long oldLength = underlying.length();
 201             ensure(index);
 202             underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
 203             setLength(Math.max(underlying.length(), length()));
 204         } else {
 205             final Long longIndex = indexToKey(index);
 206             sparseMap.put(longIndex, value);
 207             setLength(Math.max(longIndex + 1, length()));
 208         }
 209         return this;
 210     }
 211 
 212     @Override
 213     public ArrayData setEmpty(final int index) {
 214         underlying.setEmpty(index);
 215         return this;
 216     }
 217 
 218     @Override
 219     public ArrayData setEmpty(final long lo, final long hi) {
 220         underlying.setEmpty(lo, hi);
 221         return this;
 222     }




  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.runtime.arrays;
  27 
  28 import java.util.Arrays;
  29 import java.util.Map;
  30 import java.util.TreeMap;
  31 import jdk.nashorn.internal.codegen.types.Type;
  32 import jdk.nashorn.internal.runtime.JSType;
  33 import jdk.nashorn.internal.runtime.ScriptRuntime;
  34 
  35 /**
  36  * Handle arrays where the index is very large.
  37  */
  38 class SparseArrayData extends ArrayData {
  39     /** Maximum size for dense arrays */
  40     static final int MAX_DENSE_LENGTH = 1024 * 1024;
  41 
  42     /** Underlying array. */
  43     private ArrayData underlying;
  44 
  45     /** Maximum length to be stored in the array. */
  46     private final long maxDenseLength;
  47 
  48     /** Sparse elements. */
  49     private TreeMap<Long, Object> sparseMap;
  50 
  51     SparseArrayData(final ArrayData underlying, final long length) {
  52         this(underlying, length, new TreeMap<>());
  53     }
  54 
  55     private SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
  56         super(length);
  57         assert underlying.length() <= length;
  58         this.underlying = underlying;
  59         this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length());
  60         this.sparseMap = sparseMap;
  61     }
  62 
  63     @Override
  64     public ArrayData copy() {
  65         return new SparseArrayData(underlying.copy(), length(), new TreeMap<>(sparseMap));
  66     }
  67 
  68     @Override
  69     public Object[] asObjectArray() {
  70         final int len = (int)Math.min(length(), Integer.MAX_VALUE);
  71         final int underlyingLength = (int)Math.min(len, underlying.length());
  72         final Object[] objArray = new Object[len];
  73 
  74         for (int i = 0; i < underlyingLength; i++) {
  75             objArray[i] = underlying.getObject(i);
  76         }
  77 
  78         Arrays.fill(objArray, underlyingLength, len, ScriptRuntime.UNDEFINED);
  79 
  80         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
  81             final long key = entry.getKey();
  82             if (key < Integer.MAX_VALUE) {
  83                 objArray[(int)key] = entry.getValue();
  84             } else {
  85                 break; // ascending key order
  86             }
  87         }
  88 
  89         return objArray;
  90     }
  91 
  92     @Override
  93     public ArrayData shiftLeft(final int by) {
  94         underlying = underlying.shiftLeft(by);
  95 
  96         final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
  97 
  98         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
  99             final long newIndex = entry.getKey() - by;
 100             if (newIndex >= 0) {
 101                 if (newIndex < maxDenseLength) {
 102                     final long oldLength = underlying.length();
 103                     underlying = underlying.ensure(newIndex)
 104                             .set((int) newIndex, entry.getValue(), false)
 105                             .safeDelete(oldLength, newIndex - 1, false);
 106                 } else {
 107                     newSparseMap.put(newIndex, entry.getValue());
 108                 }
 109             }
 110         }
 111 
 112         sparseMap = newSparseMap;
 113         setLength(Math.max(length() - by, 0));
 114 
 115         return sparseMap.isEmpty() ? underlying : this;
 116     }
 117 
 118     @Override
 119     public ArrayData shiftRight(final int by) {
 120         final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
 121         // Move elements from underlying to sparse map if necessary
 122         final long len = underlying.length();
 123         if (len + by > maxDenseLength) {
 124             // Length of underlying array after shrinking, before right-shifting
 125             final long tempLength = Math.max(0, maxDenseLength - by);
 126             for (long i = tempLength; i < len; i++) {
 127                 if (underlying.has((int) i)) {
 128                     newSparseMap.put(i + by, underlying.getObject((int) i));
 129                 }
 130             }
 131             underlying = underlying.shrink((int) tempLength);
 132             underlying.setLength(tempLength);
 133         }
 134 
 135         underlying = underlying.shiftRight(by);
 136 
 137         for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
 138             final long newIndex = entry.getKey() + by;
 139             newSparseMap.put(newIndex, entry.getValue());
 140         }
 141 
 142         sparseMap = newSparseMap;
 143         setLength(length() + by);
 144 
 145         return this;
 146     }
 147 
 148     @Override
 149     public ArrayData ensure(final long safeIndex) {








 150         if (safeIndex >= length()) {
 151             setLength(safeIndex + 1);
 152         }
 153         return this;
 154     }
 155 
 156     @Override
 157     public ArrayData shrink(final long newLength) {
 158         if (newLength < underlying.length()) {
 159             underlying = underlying.shrink(newLength);
 160             underlying.setLength(newLength);
 161             sparseMap.clear();
 162             setLength(newLength);
 163         }
 164 
 165         sparseMap.subMap(newLength, Long.MAX_VALUE).clear();
 166         setLength(newLength);
 167         return this;
 168     }
 169 
 170     @Override
 171     public ArrayData set(final int index, final Object value, final boolean strict) {
 172         if (index >= 0 && index < maxDenseLength) {
 173             final long oldLength = underlying.length();
 174             underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);

 175             setLength(Math.max(underlying.length(), length()));
 176         } else {
 177             final Long longIndex = indexToKey(index);
 178             sparseMap.put(longIndex, value);
 179             setLength(Math.max(longIndex + 1, length()));
 180         }
 181 
 182         return this;
 183     }
 184 
 185     @Override
 186     public ArrayData set(final int index, final int value, final boolean strict) {
 187         if (index >= 0 && index < maxDenseLength) {
 188             final long oldLength = underlying.length();
 189             underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);

 190             setLength(Math.max(underlying.length(), length()));
 191         } else {
 192             final Long longIndex = indexToKey(index);
 193             sparseMap.put(longIndex, value);
 194             setLength(Math.max(longIndex + 1, length()));
 195         }
 196         return this;
 197     }
 198 
 199     @Override
 200     public ArrayData set(final int index, final double value, final boolean strict) {
 201         if (index >= 0 && index < maxDenseLength) {
 202             final long oldLength = underlying.length();
 203             underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);

 204             setLength(Math.max(underlying.length(), length()));
 205         } else {
 206             final Long longIndex = indexToKey(index);
 207             sparseMap.put(longIndex, value);
 208             setLength(Math.max(longIndex + 1, length()));
 209         }
 210         return this;
 211     }
 212 
 213     @Override
 214     public ArrayData setEmpty(final int index) {
 215         underlying.setEmpty(index);
 216         return this;
 217     }
 218 
 219     @Override
 220     public ArrayData setEmpty(final long lo, final long hi) {
 221         underlying.setEmpty(lo, hi);
 222         return this;
 223     }


< prev index next >