LongMap.java

  1. /*
  2.  * Copyright (C) 2009, Google Inc. and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  10. package org.eclipse.jgit.util;

  11. /**
  12.  * Simple Map<long, Object>.
  13.  *
  14.  * @param <V>
  15.  *            type of the value instance.
  16.  * @since 4.9
  17.  */
  18. public class LongMap<V> {
  19.     private static final float LOAD_FACTOR = 0.75f;

  20.     private Node<V>[] table;

  21.     /** Number of entries currently in the map. */
  22.     private int size;

  23.     /** Next {@link #size} to trigger a {@link #grow()}. */
  24.     private int growAt;

  25.     /**
  26.      * Initialize an empty LongMap.
  27.      */
  28.     public LongMap() {
  29.         table = createArray(64);
  30.         growAt = (int) (table.length * LOAD_FACTOR);
  31.     }

  32.     /**
  33.      * Whether {@code key} is present in the map.
  34.      *
  35.      * @param key
  36.      *            the key to find.
  37.      * @return {@code true} if {@code key} is present in the map.
  38.      */
  39.     public boolean containsKey(long key) {
  40.         return get(key) != null;
  41.     }

  42.     /**
  43.      * Get value for this {@code key}
  44.      *
  45.      * @param key
  46.      *            the key to find.
  47.      * @return stored value for this key, or {@code null}.
  48.      */
  49.     public V get(long key) {
  50.         for (Node<V> n = table[index(key)]; n != null; n = n.next) {
  51.             if (n.key == key)
  52.                 return n.value;
  53.         }
  54.         return null;
  55.     }

  56.     /**
  57.      * Remove an entry from the map
  58.      *
  59.      * @param key
  60.      *            key to remove from the map.
  61.      * @return old value of the key, or {@code null}.
  62.      */
  63.     public V remove(long key) {
  64.         Node<V> n = table[index(key)];
  65.         Node<V> prior = null;
  66.         while (n != null) {
  67.             if (n.key == key) {
  68.                 if (prior == null)
  69.                     table[index(key)] = n.next;
  70.                 else
  71.                     prior.next = n.next;
  72.                 size--;
  73.                 return n.value;
  74.             }
  75.             prior = n;
  76.             n = n.next;
  77.         }
  78.         return null;
  79.     }

  80.     /**
  81.      * Put a new entry into the map
  82.      *
  83.      * @param key
  84.      *            key to store {@code value} under.
  85.      * @param value
  86.      *            new value.
  87.      * @return prior value, or null.
  88.      */
  89.     public V put(long key, V value) {
  90.         for (Node<V> n = table[index(key)]; n != null; n = n.next) {
  91.             if (n.key == key) {
  92.                 final V o = n.value;
  93.                 n.value = value;
  94.                 return o;
  95.             }
  96.         }

  97.         if (++size == growAt)
  98.             grow();
  99.         insert(new Node<>(key, value));
  100.         return null;
  101.     }

  102.     private void insert(Node<V> n) {
  103.         final int idx = index(n.key);
  104.         n.next = table[idx];
  105.         table[idx] = n;
  106.     }

  107.     private void grow() {
  108.         final Node<V>[] oldTable = table;
  109.         final int oldSize = table.length;

  110.         table = createArray(oldSize << 1);
  111.         growAt = (int) (table.length * LOAD_FACTOR);
  112.         for (int i = 0; i < oldSize; i++) {
  113.             Node<V> e = oldTable[i];
  114.             while (e != null) {
  115.                 final Node<V> n = e.next;
  116.                 insert(e);
  117.                 e = n;
  118.             }
  119.         }
  120.     }

  121.     private final int index(long key) {
  122.         int h = ((int) key) >>> 1;
  123.         h ^= (h >>> 20) ^ (h >>> 12);
  124.         return h & (table.length - 1);
  125.     }

  126.     @SuppressWarnings("unchecked")
  127.     private static final <V> Node<V>[] createArray(int sz) {
  128.         return new Node[sz];
  129.     }

  130.     private static class Node<V> {
  131.         final long key;
  132.         V value;
  133.         Node<V> next;

  134.         Node(long k, V v) {
  135.             key = k;
  136.             value = v;
  137.         }
  138.     }
  139. }