AbstractOpenIntHashMap.java

  1. /*
  2.  * Licensed to the Hipparchus project under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The Hipparchus project licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      https://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.hipparchus.util;

  19. import java.util.Arrays;
  20. import java.util.ConcurrentModificationException;
  21. import java.util.NoSuchElementException;

  23. /** Base class for open addressed map from int.
  24.  * @since 3.1
  25.  */
  26. public abstract class AbstractOpenIntHashMap {

  28.     /** Default starting size.
  29.      * <p>This must be a power of two for bit mask to work properly. </p>
  30.      */
  31.     protected static final int DEFAULT_EXPECTED_SIZE = 16;

  33.     /** Multiplier for size growth when map fills up.
  34.      * <p>This must be a power of two for bit mask to work properly. </p>
  35.      */
  36.     protected static final int RESIZE_MULTIPLIER = 2;

  38.     /** Status indicator for free table entries. */
  39.     private static final byte FREE    = 0;

  41.     /** Status indicator for full table entries. */
  42.     private static final byte FULL    = 1;

  44.     /** Status indicator for removed table entries. */
  45.     private static final byte REMOVED = 2;

  47.     /** Load factor for the map. */
  48.     private static final float LOAD_FACTOR = 0.5f;

  50.     /** Number of bits to perturb the index when probing for collision resolution. */
  51.     private static final int PERTURB_SHIFT = 5;

  53.     /** Keys table. */
  54.     private int[] keys;

  56.     /** States table. */
  57.     private byte[] states;

  59.     /** Current size of the map. */
  60.     private int size;

  62.     /** Bit mask for hash values. */
  63.     private int mask;

  65.     /** Modifications count. */
  66.     private transient int count;

  68.     /** Build an empty map with default size.
  69.      */
  70.     protected AbstractOpenIntHashMap() {
  71.         this(DEFAULT_EXPECTED_SIZE);
  72.     }

  74.     /**
  75.      * Build an empty map with specified size.
  76.      * @param expectedSize expected number of elements in the map
  77.      */
  78.     protected AbstractOpenIntHashMap(final int expectedSize) {
  79.         final int capacity = computeCapacity(expectedSize);
  80.         keys   = new int[capacity];
  81.         states = new byte[capacity];
  82.         mask   = capacity - 1;
  83.         resetCount();
  84.     }

  86.     /**
  87.      * Copy constructor.
  88.      * @param source map to copy
  89.      */
  90.     protected AbstractOpenIntHashMap(final AbstractOpenIntHashMap source) {
  91.         final int length = source.keys.length;
  92.         keys = new int[length];
  93.         System.arraycopy(source.keys, 0, keys, 0, length);
  94.         states = new byte[length];
  95.         System.arraycopy(source.states, 0, states, 0, length);
  96.         size  = source.size;
  97.         mask  = source.mask;
  98.         count = source.count;
  99.     }

  101.     /** Get capacity.
  102.      * @return capacity
  103.      * @since 3.1
  104.      */
  105.     protected int getCapacity() {
  106.         return keys.length;
  107.     }

  109.     /** Get the number of elements stored in the map.
  110.      * @return number of elements stored in the map
  111.      */
  112.     public int getSize() {
  113.         return size;
  114.     }

  116.     /**
  117.      * Compute the capacity needed for a given size.
  118.      * @param expectedSize expected size of the map
  119.      * @return capacity to use for the specified size
  120.      */
  121.     private static int computeCapacity(final int expectedSize) {
  122.         if (expectedSize == 0) {
  123.             return 1;
  124.         }
  125.         final int capacity   = (int) FastMath.ceil(expectedSize / LOAD_FACTOR);
  126.         final int powerOfTwo = Integer.highestOneBit(capacity);
  127.         if (powerOfTwo == capacity) {
  128.             return capacity;
  129.         }
  130.         return nextPowerOfTwo(capacity);
  131.     }

  133.     /** Reset count.
  134.      * @since 3.1
  135.      */
  136.     protected final void resetCount() {
  137.         count = 0;
  138.     }

  140.     /**
  141.      * Find the smallest power of two greater than the input value
  142.      * @param i input value
  143.      * @return smallest power of two greater than the input value
  144.      */
  145.     private static int nextPowerOfTwo(final int i) {
  146.         return Integer.highestOneBit(i) << 1;
  147.     }

  149.     /**
  150.      * Check if a value is associated with a key.
  151.      * @param key key to check
  152.      * @return true if a value is associated with key
  153.      */
  154.     public boolean containsKey(final int key) {

  156.         final int hash  = hashOf(key);
  157.         int index = hash & mask;
  158.         if (containsKey(key, index)) {
  159.             return true;
  160.         }

  162.         if (states[index] == FREE) {
  163.             return false;
  164.         }

  166.         int j = index;
  167.         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
  168.             j = probe(perturb, j);
  169.             index = j & mask;
  170.             if (containsKey(key, index)) {
  171.                 return true;
  172.             }
  173.         }

  175.         return false;

  177.     }

  179.     /**
  180.      * Perturb the hash for starting probing.
  181.      * @param hash initial hash
  182.      * @return perturbed hash
  183.      */
  184.     private static int perturb(final int hash) {
  185.         return hash & 0x7fffffff;
  186.     }

  188.     /**
  189.      * Find the index at which a key should be inserted
  190.      * @param keys keys table
  191.      * @param states states table
  192.      * @param key key to lookup
  193.      * @param mask bit mask for hash values
  194.      * @return index at which key should be inserted
  195.      */
  196.     private static int findInsertionIndex(final int[] keys, final byte[] states,
  197.                                           final int key, final int mask) {
  198.         final int hash = hashOf(key);
  199.         int index = hash & mask;
  200.         if (states[index] == FREE) {
  201.             return index;
  202.         } else if (states[index] == FULL && keys[index] == key) {
  203.             return changeIndexSign(index);
  204.         }

  206.         int perturb = perturb(hash);
  207.         int j = index;
  208.         if (states[index] == FULL) {
  209.             while (true) {
  210.                 j = probe(perturb, j);
  211.                 index = j & mask;
  212.                 perturb >>= PERTURB_SHIFT;

  214.                 if (states[index] != FULL || keys[index] == key) {
  215.                     break;
  216.                 }
  217.             }
  218.         }

  220.         if (states[index] == FREE) {
  221.             return index;
  222.         } else if (states[index] == FULL) {
  223.             // due to the loop exit condition,
  224.             // if (states[index] == FULL) then keys[index] == key
  225.             return changeIndexSign(index);
  226.         }

  228.         final int firstRemoved = index;
  229.         while (true) {
  230.             j = probe(perturb, j);
  231.             index = j & mask;

  233.             if (states[index] == FREE) {
  234.                 return firstRemoved;
  235.             } else if (states[index] == FULL && keys[index] == key) {
  236.                 return changeIndexSign(index);
  237.             }

  239.             perturb >>= PERTURB_SHIFT;

  241.         }

  243.     }

  245.     /**
  246.      * Compute next probe for collision resolution
  247.      * @param perturb perturbed hash
  248.      * @param j previous probe
  249.      * @return next probe
  250.      */
  251.     private static int probe(final int perturb, final int j) {
  252.         return (j << 2) + j + perturb + 1;
  253.     }

  255.     /**
  256.      * Change the index sign
  257.      * @param index initial index
  258.      * @return changed index
  259.      */
  260.     private static int changeIndexSign(final int index) {
  261.         return -index - 1;
  262.     }

  264.     /**
  265.      * Get the number of elements stored in the map.
  266.      * @return number of elements stored in the map
  267.      */
  268.     public int size() {
  269.         return size;
  270.     }

  272.     /**
  273.      * Check if the tables contain an element associated with specified key
  274.      * at specified index.
  275.      * @param key key to check
  276.      * @param index index to check
  277.      * @return true if an element is associated with key at index
  278.      */
  279.     public boolean containsKey(final int key, final int index) {
  280.         return (key != 0 || states[index] == FULL) && keys[index] == key;
  281.     }

  283.     /** Locate the index of value associated with the given key
  284.      * @param key key associated with the data
  285.      * @return index of value associated with the given key or negative
  286.      * if key not present
  287.      */
  288.     protected int locate(final int key) {

  290.         final int hash  = hashOf(key);
  291.         int index = hash & mask;
  292.         if (containsKey(key, index)) {
  293.             return index;
  294.         }

  296.         if (states[index] == FREE) {
  297.             return -1;
  298.         }

  300.         int j = index;
  301.         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
  302.             j = probe(perturb, j);
  303.             index = j & mask;
  304.             if (containsKey(key, index)) {
  305.                 return index;
  306.             }
  307.         }

  309.         return -1;

  311.     }

  313.     /** Remove an element at specified index.
  314.      * @param index index of the element to remove
  315.      */
  316.     protected void doRemove(int index) {
  317.         keys[index]   = 0;
  318.         states[index] = REMOVED;
  319.         --size;
  320.         ++count;
  321.     }

  323.     /** Put a value associated with a key in the map.
  324.      * @param key key to which value is associated
  325.      * @return holder to manage insertion
  326.      */
  327.     protected InsertionHolder put(final int key) {
  328.         int     oldIndex   = findInsertionIndex(keys, states, key, mask);
  329.         int     newIndex   = oldIndex;
  330.         boolean existing   = false;
  331.         boolean newMapping = true;
  332.         if (oldIndex < 0) {
  333.             oldIndex   = changeIndexSign(oldIndex);
  334.             existing   = true;
  335.             newMapping = false;
  336.         }
  337.         keys[oldIndex] = key;
  338.         states[oldIndex] = FULL;
  339.         if (newMapping) {
  340.             ++size;
  341.             if (shouldGrowTable()) {
  342.                 newIndex = growTable(oldIndex);
  343.             }
  344.             ++count;
  345.         }
  346.         return new InsertionHolder(existing ? oldIndex : newIndex, existing);

  348.     }

  350.     /** Grow the tables.
  351.      * @param oldIndex index the entry being inserted should have used
  352.      * @return index the entry being inserted should really use
  353.      */
  354.     protected abstract int growTable(int oldIndex);

  356.     /** Grow the tables.
  357.      * @param oldIndex index the entry being inserted should have used
  358.      * @param valueCopier copier for existing values
  359.      * @return index the entry being inserted should really use
  360.      */
  361.     protected int doGrowTable(final int oldIndex, final ValueCopier valueCopier) {

  363.         int newIndex = oldIndex;
  364.         final int    oldLength = states.length;
  365.         final int[]  oldKeys   = keys;
  366.         final byte[] oldStates = states;

  368.         final int    newLength = RESIZE_MULTIPLIER * oldLength;
  369.         final int[]  newKeys   = new int[newLength];
  370.         final byte[] newStates = new byte[newLength];
  371.         final int newMask = newLength - 1;
  372.         for (int srcIndex = 0; srcIndex < oldLength; ++srcIndex) {
  373.             if (oldStates[srcIndex] == FULL) {
  374.                 final int key   = oldKeys[srcIndex];
  375.                 final int dstIndex = findInsertionIndex(newKeys, newStates, key, newMask);
  376.                 newKeys[dstIndex]  = key;
  377.                 valueCopier.copyValue(srcIndex, dstIndex);
  378.                 if (srcIndex == oldIndex) {
  379.                     newIndex = dstIndex;
  380.                 }
  381.                 newStates[dstIndex] = FULL;
  382.             }
  383.         }

  385.         mask   = newMask;
  386.         keys   = newKeys;
  387.         states = newStates;

  389.         return newIndex;

  391.     }

  393.     /**
  394.      * Check if tables should grow due to increased size.
  395.      * @return true if  tables should grow
  396.      */
  397.     private boolean shouldGrowTable() {
  398.         return size > (mask + 1) * LOAD_FACTOR;
  399.     }

  401.     /**
  402.      * Compute the hash value of a key
  403.      * @param key key to hash
  404.      * @return hash value of the key
  405.      */
  406.     private static int hashOf(final int key) {
  407.         final int h = key ^ ((key >>> 20) ^ (key >>> 12));
  408.         return h ^ (h >>> 7) ^ (h >>> 4);
  409.     }

  411.     /** Check if keys are equals.
  412.      * @param other other map
  413.      * @return true if keys are equals
  414.      */
  415.     protected boolean equalKeys(final AbstractOpenIntHashMap other) {
  416.         return Arrays.equals(keys, other.keys);
  417.     }

  419.     /** Check if states are equals.
  420.      * @param other other map
  421.      * @return true if states are equals
  422.      */
  423.     protected boolean equalStates(final AbstractOpenIntHashMap other) {
  424.         return Arrays.equals(states, other.states);
  425.     }

  427.     /** Compute partial hashcode on keys and states.
  428.      * @return partial hashcode on keys and states
  429.      */
  430.     protected int keysStatesHashCode() {
  431.         return  53 * Arrays.hashCode(keys) + 31 * Arrays.hashCode(states);
  432.     }

  434.     /** Iterator class for the map. */
  435.     protected class BaseIterator {

  437.         /** Reference modification count. */
  438.         private final int referenceCount;

  440.         /** Index of current element. */
  441.         private int current;

  443.         /** Index of next element. */
  444.         private int next;

  446.         /**
  447.          * Simple constructor.
  448.          */
  449.         protected BaseIterator() {

  451.             // preserve the modification count of the map to detect concurrent modifications later
  452.             referenceCount = count;

  454.             // initialize current index
  455.             next = -1;
  456.             try {
  457.                 advance();
  458.             } catch (NoSuchElementException nsee) { // NOPMD
  459.                 // ignored
  460.             }

  462.         }

  464.         /**
  465.          * Check if there is a next element in the map.
  466.          * @return true if there is a next element
  467.          */
  468.         public boolean hasNext() {
  469.             return next >= 0;
  470.         }

  472.         /** Get index of current entry.
  473.          * @return key of current entry
  474.          * @since 3.1
  475.          */
  476.         protected int getCurrent() {
  477.             return current;
  478.         }

  480.         /**
  481.          * Get the key of current entry.
  482.          * @return key of current entry
  483.          * @exception ConcurrentModificationException if the map is modified during iteration
  484.          * @exception NoSuchElementException if there is no element left in the map
  485.          */
  486.         public int key() throws ConcurrentModificationException, NoSuchElementException {
  487.             return keys[getCurrent()];
  488.         }

  490.         /**
  491.          * Advance iterator one step further.
  492.          * @exception ConcurrentModificationException if the map is modified during iteration
  493.          * @exception NoSuchElementException if there is no element left in the map
  494.          */
  495.         public void advance()
  496.             throws ConcurrentModificationException, NoSuchElementException {

  498.             if (referenceCount != count) {
  499.                 throw new ConcurrentModificationException();
  500.             }

  502.             // advance on step
  503.             current = next;

  505.             // prepare next step
  506.             try {
  507.                 while (states[++next] != FULL) { // NOPMD
  508.                     // nothing to do
  509.                 }
  510.             } catch (ArrayIndexOutOfBoundsException e) {
  511.                 next = -2;
  512.                 if (current < 0) {
  513.                     throw new NoSuchElementException(); // NOPMD
  514.                 }
  515.             }

  517.         }

  519.     }

  521.     /** Holder for handling values insertion.
  522.      * @since 3.1
  523.      */
  524.     protected static class InsertionHolder {

  526.         /** Index at which new value should be put. */
  527.         private final int index;

  529.         /** Indicator for value already present before insertion. */
  530.         private final boolean existing;

  532.         /** Simple constructor.
  533.          * @param index index at which new value should be put
  534.          * @param existing indicator for value already present before insertion
  535.          */
  536.         InsertionHolder(final int index, final boolean existing) {
  537.             this.index    = index;
  538.             this.existing = existing;
  539.         }

  541.         /** Get index at which new value should be put.
  542.          * @return index at which new value should be put
  543.          */
  544.         public int getIndex() {
  545.             return index;
  546.         }

  548.         /** Get indicator for value already present before insertion.
  549.          * @return indicator for value already present before insertion
  550.          */
  551.         public boolean isExisting() {
  552.             return existing;
  553.         }
  554.     }

  556.     /** Interface for copying values.
  557.      * @since 3.1
  558.      */
  559.     @FunctionalInterface
  560.     protected interface ValueCopier {
  561.         /** Copy a value.
  562.          * @param src source index
  563.          * @param dest destination index
  564.          */
  565.         void copyValue(int src, int dest);
  566.     }

  568. }
Created with JaCoCo 0.8.12.202403310830