path: root/jimfs/src/main/java/com/google/common/jimfs/Directory.java

/*
 * Copyright 2013 Google Inc.
 *
 * Licensed 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 com.google.common.jimfs;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.AbstractIterator;
import com.google.common.collect.ImmutableSortedSet;
import java.util.Iterator;
import org.checkerframework.checker.nullness.compatqual.NullableDecl;

/**
 * A table of {@linkplain DirectoryEntry directory entries}.
 *
 * @author Colin Decker
 */
final class Directory extends File implements Iterable<DirectoryEntry> {

  /** The entry linking to this directory in its parent directory. */
  private DirectoryEntry entryInParent;

  /** Creates a new normal directory with the given ID. */
  public static Directory create(int id) {
    return new Directory(id);
  }

  /** Creates a new root directory with the given ID and name. */
  public static Directory createRoot(int id, Name name) {
    return new Directory(id, name);
  }

  private Directory(int id) {
    super(id);
    put(new DirectoryEntry(this, Name.SELF, this));
  }

  private Directory(int id, Name rootName) {
    this(id);
    linked(new DirectoryEntry(this, rootName, this));
  }

  /**
   * Creates a copy of this directory. The copy does <i>not</i> contain a copy of the entries in
   * this directory.
   */
  @Override
  Directory copyWithoutContent(int id) {
    return Directory.create(id);
  }

  /**
   * Returns the entry linking to this directory in its parent. If this directory has been deleted,
   * this returns the entry for it in the directory it was in when it was deleted.
   */
  public DirectoryEntry entryInParent() {
    return entryInParent;
  }

  /**
   * Returns the parent of this directory. If this directory has been deleted, this returns the
   * directory it was in when it was deleted.
   */
  public Directory parent() {
    return entryInParent.directory();
  }

  @Override
  void linked(DirectoryEntry entry) {
    File parent = entry.directory(); // handles null check
    this.entryInParent = entry;
    forcePut(new DirectoryEntry(this, Name.PARENT, parent));
  }

  @Override
  void unlinked() {
    // we don't actually remove the parent link when this directory is unlinked, but the parent's
    // link count should go down all the same
    parent().decrementLinkCount();
  }

  /** Returns the number of entries in this directory. */
  @VisibleForTesting
  int entryCount() {
    return entryCount;
  }

  /** Returns true if this directory has no entries other than those to itself and its parent. */
  public boolean isEmpty() {
    return entryCount() == 2;
  }

  /** Returns the entry for the given name in this table or null if no such entry exists. */
  @NullableDecl
  public DirectoryEntry get(Name name) {
    int index = bucketIndex(name, table.length);

    DirectoryEntry entry = table[index];
    while (entry != null) {
      if (name.equals(entry.name())) {
        return entry;
      }

      entry = entry.next;
    }
    return null;
  }

  /**
   * Links the given name to the given file in this directory.
   *
   * @throws IllegalArgumentException if {@code name} is a reserved name such as "." or if an entry
   *     already exists for the name
   */
  public void link(Name name, File file) {
    DirectoryEntry entry = new DirectoryEntry(this, checkNotReserved(name, "link"), file);
    put(entry);
    file.linked(entry);
  }

  /**
   * Unlinks the given name from the file it is linked to.
   *
   * @throws IllegalArgumentException if {@code name} is a reserved name such as "." or no entry
   *     exists for the name
   */
  public void unlink(Name name) {
    DirectoryEntry entry = remove(checkNotReserved(name, "unlink"));
    entry.file().unlinked();
  }

  /**
   * Creates an immutable sorted snapshot of the names this directory contains, excluding "." and
   * "..".
   */
  public ImmutableSortedSet<Name> snapshot() {
    ImmutableSortedSet.Builder<Name> builder =
        new ImmutableSortedSet.Builder<>(Name.displayOrdering());

    for (DirectoryEntry entry : this) {
      if (!isReserved(entry.name())) {
        builder.add(entry.name());
      }
    }

    return builder.build();
  }

  /** Checks that the given name is not "." or "..". Those names cannot be set/removed by users. */
  private static Name checkNotReserved(Name name, String action) {
    if (isReserved(name)) {
      throw new IllegalArgumentException("cannot " + action + ": " + name);
    }
    return name;
  }

  /** Returns true if the given name is "." or "..". */
  private static boolean isReserved(Name name) {
    // all "." and ".." names are canonicalized to the same objects, so we can use identity
    return name == Name.SELF || name == Name.PARENT;
  }

  // Simple hash table code to avoid allocation of Map.Entry objects when DirectoryEntry can
  // serve the same purpose.

  private static final int INITIAL_CAPACITY = 16;
  private static final int INITIAL_RESIZE_THRESHOLD = (int) (INITIAL_CAPACITY * 0.75);

  private DirectoryEntry[] table = new DirectoryEntry[INITIAL_CAPACITY];
  private int resizeThreshold = INITIAL_RESIZE_THRESHOLD;

  private int entryCount;

  /** Returns the index of the bucket in the array where an entry for the given name should go. */
  private static int bucketIndex(Name name, int tableLength) {
    return name.hashCode() & (tableLength - 1);
  }

  /**
   * Adds the given entry to the directory.
   *
   * @throws IllegalArgumentException if an entry with the given entry's name already exists in the
   *     directory
   */
  @VisibleForTesting
  void put(DirectoryEntry entry) {
    put(entry, false);
  }

  /**
   * Adds the given entry to the directory. {@code overwriteExisting} determines whether an existing
   * entry with the same name should be overwritten or an exception should be thrown.
   */
  private void put(DirectoryEntry entry, boolean overwriteExisting) {
    int index = bucketIndex(entry.name(), table.length);

    // find the place the new entry should go, ensuring an entry with the same name doesn't already
    // exist along the way
    DirectoryEntry prev = null;
    DirectoryEntry curr = table[index];
    while (curr != null) {
      if (curr.name().equals(entry.name())) {
        if (overwriteExisting) {
          // just replace the existing entry; no need to expand, and entryCount doesn't change
          if (prev != null) {
            prev.next = entry;
          } else {
            table[index] = entry;
          }
          entry.next = curr.next;
          curr.next = null;
          entry.file().incrementLinkCount();
          return;
        } else {
          throw new IllegalArgumentException("entry '" + entry.name() + "' already exists");
        }
      }

      prev = curr;
      curr = curr.next;
    }

    entryCount++;
    if (expandIfNeeded()) {
      // if the table was expanded, the index/entry we found is no longer applicable, so just add
      // the entry normally
      index = bucketIndex(entry.name(), table.length);
      addToBucket(index, table, entry);
    } else {
      // otherwise, we just can use the index/entry we found
      if (prev != null) {
        prev.next = entry;
      } else {
        table[index] = entry;
      }
    }

    entry.file().incrementLinkCount();
  }

  /**
   * Adds the given entry to the directory, overwriting an existing entry with the same name if such
   * an entry exists.
   */
  private void forcePut(DirectoryEntry entry) {
    put(entry, true);
  }

  private boolean expandIfNeeded() {
    if (entryCount <= resizeThreshold) {
      return false;
    }

    DirectoryEntry[] newTable = new DirectoryEntry[table.length << 1];

    // redistribute all current entries in the new table
    for (DirectoryEntry entry : table) {
      while (entry != null) {
        int index = bucketIndex(entry.name(), newTable.length);
        addToBucket(index, newTable, entry);
        DirectoryEntry next = entry.next;
        // set entry.next to null; it's always the last entry in its bucket after being added
        entry.next = null;
        entry = next;
      }
    }

    this.table = newTable;
    resizeThreshold <<= 1;
    return true;
  }

  private static void addToBucket(
      int bucketIndex, DirectoryEntry[] table, DirectoryEntry entryToAdd) {
    DirectoryEntry prev = null;
    DirectoryEntry existing = table[bucketIndex];
    while (existing != null) {
      prev = existing;
      existing = existing.next;
    }

    if (prev != null) {
      prev.next = entryToAdd;
    } else {
      table[bucketIndex] = entryToAdd;
    }
  }

  /**
   * Removes and returns the entry for the given name from the directory.
   *
   * @throws IllegalArgumentException if there is no entry with the given name in the directory
   */
  @VisibleForTesting
  DirectoryEntry remove(Name name) {
    int index = bucketIndex(name, table.length);

    DirectoryEntry prev = null;
    DirectoryEntry entry = table[index];
    while (entry != null) {
      if (name.equals(entry.name())) {
        if (prev != null) {
          prev.next = entry.next;
        } else {
          table[index] = entry.next;
        }

        entry.next = null;
        entryCount--;
        entry.file().decrementLinkCount();
        return entry;
      }

      prev = entry;
      entry = entry.next;
    }

    throw new IllegalArgumentException("no entry matching '" + name + "' in this directory");
  }

  @Override
  public Iterator<DirectoryEntry> iterator() {
    return new AbstractIterator<DirectoryEntry>() {
      int index;
      @NullableDecl DirectoryEntry entry;

      @Override
      protected DirectoryEntry computeNext() {
        if (entry != null) {
          entry = entry.next;
        }

        while (entry == null && index < table.length) {
          entry = table[index++];
        }

        return entry != null ? entry : endOfData();
      }
    };
  }
}