1 /*
   2  * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.core.common.util;
  24 
  25 /**
  26  * The {@code ArrayMap} class implements an efficient one-level map which is implemented as an
  27  * array. Note that because of the one-level array inside, this data structure performs best when
  28  * the range of integer keys is small and densely used. Note that the implementation can handle
  29  * arbitrary intervals, including negative numbers, up to intervals of size 2^31 - 1.
  30  */
  31 public class ArrayMap<T> {
  32 
  33     private static final int INITIAL_SIZE = 5; // how big the initial array should be
  34     private static final int EXTRA = 2; // how far on the left or right of a new element to grow
  35 
  36     Object[] map;
  37     int low;
  38 
  39     /**
  40      * Constructs a new {@code ArrayMap} with no initial assumptions.
  41      */
  42     public ArrayMap() {
  43     }
  44 
  45     /**
  46      * Constructs a new {@code ArrayMap} that initially covers the specified interval. Note that
  47      * this map will automatically expand if necessary later.
  48      *
  49      * @param low the low index, inclusive
  50      * @param high the high index, exclusive
  51      */
  52     public ArrayMap(int low, int high) {
  53         this.low = low;
  54         this.map = new Object[high - low + 1];
  55     }
  56 
  57     /**
  58      * Puts a new value in the map at the specified index.
  59      *
  60      * @param i the index at which to store the value
  61      * @param value the value to store at the specified index
  62      */
  63     public void put(int i, T value) {
  64         int index = i - low;
  65         if (map == null) {
  66             // no map yet
  67             map = new Object[INITIAL_SIZE];
  68             low = index - 2;
  69             map[INITIAL_SIZE / 2] = value;
  70         } else if (index < 0) {
  71             // grow backwards
  72             growBackward(i, value);
  73         } else if (index >= map.length) {
  74             // grow forwards
  75             growForward(i, value);
  76         } else {
  77             // no growth necessary
  78             map[index] = value;
  79         }
  80     }
  81 
  82     /**
  83      * Gets the value at the specified index in the map.
  84      *
  85      * @param i the index
  86      * @return the value at the specified index; {@code null} if there is no value at the specified
  87      *         index, or if the index is out of the currently stored range
  88      */
  89     public T get(int i) {
  90         int index = i - low;
  91         if (map == null || index < 0 || index >= map.length) {
  92             return null;
  93         }
  94         Class<T> type = null;
  95         return Util.uncheckedCast(type, map[index]);
  96     }
  97 
  98     public int length() {
  99         return map.length;
 100     }
 101 
 102     private void growBackward(int i, T value) {
 103         int nlow = i - EXTRA;
 104         Object[] nmap = new Object[low - nlow + map.length];
 105         System.arraycopy(map, 0, nmap, low - nlow, map.length);
 106         map = nmap;
 107         low = nlow;
 108         map[i - low] = value;
 109     }
 110 
 111     private void growForward(int i, T value) {
 112         int nlen = i - low + 1 + EXTRA;
 113         Object[] nmap = new Object[nlen];
 114         System.arraycopy(map, 0, nmap, 0, map.length);
 115         map = nmap;
 116         map[i - low] = value;
 117     }
 118 }