linkedhashmap.java

this gcc-g++-3.3.1.tar.gz is a source file of gcc, you can learn more about gcc through this codes f

   * Construct a new insertion-ordered LinkedHashMap with a specific
   * inital capacity and default load factor of 0.75.
   *
   * @param initialCapacity the initial capacity of this HashMap (>= 0)
   * @throws IllegalArgumentException if (initialCapacity < 0)
   */
  public LinkedHashMap(int initialCapacity)
  {
    super(initialCapacity);
    accessOrder = false;
  }

  /**
   * Construct a new insertion-orderd LinkedHashMap with a specific
   * inital capacity and load factor.
   *
   * @param initialCapacity the initial capacity (>= 0)
   * @param loadFactor the load factor (> 0, not NaN)
   * @throws IllegalArgumentException if (initialCapacity < 0) ||
   *                                     ! (loadFactor > 0.0)
   */
  public LinkedHashMap(int initialCapacity, float loadFactor)
  {
    super(initialCapacity, loadFactor);
    accessOrder = false;
  }

  /**
   * Construct a new LinkedHashMap with a specific inital capacity, load
   * factor, and ordering mode.
   *
   * @param initialCapacity the initial capacity (>=0)
   * @param loadFactor the load factor (>0, not NaN)
   * @param accessOrder true for access-order, false for insertion-order
   * @throws IllegalArgumentException if (initialCapacity < 0) ||
   *                                     ! (loadFactor > 0.0)
   */
  public LinkedHashMap(int initialCapacity, float loadFactor,
                       boolean accessOrder)
  {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
  }

  /**
   * Clears the Map so it has no keys. This is O(1).
   */
  public void clear()
  {
    super.clear();
    root = null;
  }

  /**
   * Returns <code>true</code> if this HashMap contains a value
   * <code>o</code>, such that <code>o.equals(value)</code>.
   *
   * @param value the value to search for in this HashMap
   * @return <code>true</code> if at least one key maps to the value
   */
  public boolean containsValue(Object value)
  {
    LinkedHashEntry e = root;
    while (e != null)
      {
        if (equals(value, e.value))
          return true;
        e = e.succ;
      }
    return false;
  }

  /**
   * Return the value in this Map associated with the supplied key,
   * or <code>null</code> if the key maps to nothing.  If this is an
   * access-ordered Map and the key is found, this performs structural
   * modification, moving the key to the newest end of the list. NOTE:
   * Since the value could also be null, you must use containsKey to
   * see if this key actually maps to something.
   *
   * @param key the key for which to fetch an associated value
   * @return what the key maps to, if present
   * @see #put(Object, Object)
   * @see #containsKey(Object)
   */
  public Object get(Object key)
  {
    int idx = hash(key);
    HashEntry e = buckets[idx];
    while (e != null)
      {
        if (equals(key, e.key))
          {
            e.access();
            return e.value;
          }
        e = e.next;
      }
    return null;
  }

  /**
   * Returns <code>true</code> if this map should remove the eldest entry.
   * This method is invoked by all calls to <code>put</code> and
   * <code>putAll</code> which place a new entry in the map, providing
   * the implementer an opportunity to remove the eldest entry any time
   * a new one is added.  This can be used to save memory usage of the
   * hashtable, as well as emulating a cache, by deleting stale entries.
   * <p>
   *
   * For example, to keep the Map limited to 100 entries, override as follows:
   * <pre>
   * private static final int MAX_ENTRIES = 100;
   * protected boolean removeEldestEntry(Map.Entry eldest)
   * {
   *   return size() &gt; MAX_ENTRIES;
   * }
   * </pre><p>
   *
   * Typically, this method does not modify the map, but just uses the
   * return value as an indication to <code>put</code> whether to proceed.
   * However, if you override it to modify the map, you must return false
   * (indicating that <code>put</code> should leave the modified map alone),
   * or you face unspecified behavior.  Remember that in access-order mode,
   * even calling <code>get</code> is a structural modification, but using
   * the collections views (such as <code>keySet</code>) is not.
   * <p>
   *
   * This method is called after the eldest entry has been inserted, so
   * if <code>put</code> was called on a previously empty map, the eldest
   * entry is the one you just put in! The default implementation just
   * returns <code>false</code>, so that this map always behaves like
   * a normal one with unbounded growth.
   *
   * @param eldest the eldest element which would be removed if this
   *        returns true. For an access-order map, this is the least
   *        recently accessed; for an insertion-order map, this is the
   *        earliest element inserted.
   * @return true if <code>eldest</code> should be removed
   */
  protected boolean removeEldestEntry(Map.Entry eldest)
  {
    return false;
  }

  /**
   * Helper method called by <code>put</code>, which creates and adds a
   * new Entry, followed by performing bookkeeping (like removeEldestEntry).
   *
   * @param key the key of the new Entry
   * @param value the value
   * @param idx the index in buckets where the new Entry belongs
   * @param callRemove whether to call the removeEldestEntry method
   * @see #put(Object, Object)
   * @see #removeEldestEntry(Map.Entry)
   * @see LinkedHashEntry#LinkedHashEntry(Object, Object)
   */
  void addEntry(Object key, Object value, int idx, boolean callRemove)
  {
    LinkedHashEntry e = new LinkedHashEntry(key, value);
    e.next = buckets[idx];
    buckets[idx] = e;
    if (callRemove && removeEldestEntry(root))
      remove(root);
  }

  /**
   * Helper method, called by clone() to reset the doubly-linked list.
   *
   * @param m the map to add entries from
   * @see #clone()
   */
  void putAllInternal(Map m)
  {
    root = null;
    super.putAllInternal(m);
  }

  /**
   * Generates a parameterized iterator. This allows traversal to follow
   * the doubly-linked list instead of the random bin order of HashMap.
   *
   * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
   * @return the appropriate iterator
   */
  Iterator iterator(final int type)
  {
    return new Iterator()
    {
      /** The current Entry. */
      LinkedHashEntry current = root;

      /** The previous Entry returned by next(). */
      LinkedHashEntry last;

      /** The number of known modifications to the backing Map. */
      int knownMod = modCount;

      /**
       * Returns true if the Iterator has more elements.
       *
       * @return true if there are more elements
       * @throws ConcurrentModificationException if the HashMap was modified
       */
      public boolean hasNext()
      {
        if (knownMod != modCount)
          throw new ConcurrentModificationException();
        return current != null;
      }

      /**
       * Returns the next element in the Iterator's sequential view.
       *
       * @return the next element
       * @throws ConcurrentModificationException if the HashMap was modified
       * @throws NoSuchElementException if there is none
       */
      public Object next()
      {
        if (knownMod != modCount)
          throw new ConcurrentModificationException();
        if (current == null)
          throw new NoSuchElementException();
        last = current;
        current = current.succ;
        return type == VALUES ? last.value : type == KEYS ? last.key : last;
      }
      
      /**
       * Removes from the backing HashMap the last element which was fetched
       * with the <code>next()</code> method.
       *
       * @throws ConcurrentModificationException if the HashMap was modified
       * @throws IllegalStateException if called when there is no last element
       */
      public void remove()
      {
        if (knownMod != modCount)
          throw new ConcurrentModificationException();
        if (last == null)
          throw new IllegalStateException();
        LinkedHashMap.this.remove(last.key);
        last = null;
        knownMod++;
      }
    };
  }
} // class LinkedHashMap