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 com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.nio.file.attribute.FileTime;
import java.util.Iterator;
import org.checkerframework.checker.nullness.qual.Nullable;
/**
* 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 and creation time. */
public static Directory create(int id, FileTime creationTime) {
return new Directory(id, creationTime);
}
/** Creates a new root directory with the given ID, creation time, and name. */
public static Directory createRoot(int id, FileTime creationTime, Name name) {
return new Directory(id, creationTime, name);
}
private Directory(int id, FileTime creationTime) {
super(id, creationTime);
put(new DirectoryEntry(this, Name.SELF, this));
}
private Directory(int id, FileTime creationTime, Name rootName) {
this(id, creationTime);
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, FileTime creationTime) {
return Directory.create(id, creationTime);
}
/**
* 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. */
public @Nullable 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
*/
@CanIgnoreReturnValue
@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;
@Nullable 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();
}
};
}
}