diff options
Diffstat (limited to 'jimfs/src/main/java/com/google/common/jimfs/Directory.java')
-rw-r--r-- | jimfs/src/main/java/com/google/common/jimfs/Directory.java | 353 |
1 files changed, 353 insertions, 0 deletions
diff --git a/jimfs/src/main/java/com/google/common/jimfs/Directory.java b/jimfs/src/main/java/com/google/common/jimfs/Directory.java new file mode 100644 index 0000000..aaab83b --- /dev/null +++ b/jimfs/src/main/java/com/google/common/jimfs/Directory.java @@ -0,0 +1,353 @@ +/* + * 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(); + } + }; + } +} |