hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/LightWeightResizableGSet.java

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.hadoop.util;

import org.apache.hadoop.HadoopIllegalArgumentException;
import org.apache.hadoop.classification.InterfaceAudience;

/**
 * A low memory footprint {@link GSet} implementation,
 * which uses an array for storing the elements
 * and linked lists for collision resolution.
 *
 * If the size of elements exceeds the threshold,
 * the internal array will be resized to double length.
 *
 * This class does not support null element.
 *
 * This class is not thread safe.
 *
 * @param <K> Key type for looking up the elements
 * @param <E> Element type, which must be
 *       (1) a subclass of K, and
 *       (2) implementing {@link LinkedElement} interface.
 */
@InterfaceAudience.Private
public class LightWeightResizableGSet<K, E extends K>
    extends LightWeightGSet<K, E> {

  /**
   * The default initial capacity - MUST be a power of two.
   */
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

  /**
   * The load factor used when none specified in constructor.
   */
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

  /** Size of the entry table. */
  private int capacity;

  /**
   * The load factor for the hash set.
   */
  private final float loadFactor;
  private int threshold;

  public LightWeightResizableGSet(int initCapacity, float loadFactor) {
    if (initCapacity < 0) {
      throw new HadoopIllegalArgumentException("Illegal initial capacity: " +
          initCapacity);
    }
    if (loadFactor <= 0 || loadFactor > 1.0f) {
      throw new HadoopIllegalArgumentException("Illegal load factor: " +
          loadFactor);
    }
    this.capacity = actualArrayLength(initCapacity);
    this.hash_mask = capacity - 1;
    this.loadFactor = loadFactor;
    this.threshold = (int) (capacity * loadFactor);

    entries = new LinkedElement[capacity];
  }

  public LightWeightResizableGSet() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }

  public LightWeightResizableGSet(int initCapacity) {
    this(initCapacity, DEFAULT_LOAD_FACTOR);
  }

  @Override
  public E put(final E element) {
    E existing = super.put(element);
    expandIfNecessary();
    return existing;
  }

  /**
   * Resize the internal table to given capacity.
   */
  @SuppressWarnings("unchecked")
  protected void resize(int cap) {
    int newCapacity = actualArrayLength(cap);
    if (newCapacity == this.capacity) {
      return;
    }
    this.capacity = newCapacity;
    this.threshold = (int) (capacity * loadFactor);
    this.hash_mask = capacity - 1;
    LinkedElement[] oldEntries = entries;
    entries = new LinkedElement[capacity];
    for (int i = 0; i < oldEntries.length; i++) {
      LinkedElement e = oldEntries[i];
      while (e != null) {
        LinkedElement next = e.getNext();
        int index = getIndex((E)e);
        e.setNext(entries[index]);
        entries[index] = e;
        e = next;
      }
    }
  }

  /**
   * Checks if we need to expand, and expands if necessary.
   */
  protected void expandIfNecessary() {
    if (size > this.threshold && capacity < MAX_ARRAY_LENGTH) {
      resize(capacity * 2);
    }
  }
}