Author: szetszwo
Date: Thu Nov 15 21:34:54 2012
New Revision: 1410027
URL: http://svn.apache.org/viewvc?rev=1410027&view=rev
Log:
HDFS-4188. Add Snapshot.ID_COMPARATOR for comparing IDs and fix a bug in
ReadOnlyList.Util.binarySearch(..).
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/CHANGES.HDFS-2802.txt
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INode.java
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/INodeDirectoryWithSnapshot.java
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/Snapshot.java
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestINodeDirectoryWithSnapshot.java
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/CHANGES.HDFS-2802.txt
URL:
http://svn.apache.org/viewvc/hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/CHANGES.HDFS-2802.txt?rev=1410027&r1=1410026&r2=1410027&view=diff
==============================================================================
---
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/CHANGES.HDFS-2802.txt
(original)
+++
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/CHANGES.HDFS-2802.txt
Thu Nov 15 21:34:54 2012
@@ -70,3 +70,6 @@ Branch-2802 Snapshot (Unreleased)
HDFS-4148. Disallow write/modify operations on files and directories in a
snapshot. (Brandon Li via suresh)
+
+ HDFS-4188. Add Snapshot.ID_COMPARATOR for comparing IDs and fix a bug in
+ ReadOnlyList.Util.binarySearch(..). (szetszwo)
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INode.java
URL:
http://svn.apache.org/viewvc/hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INode.java?rev=1410027&r1=1410026&r2=1410027&view=diff
==============================================================================
---
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INode.java
(original)
+++
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INode.java
Thu Nov 15 21:34:54 2012
@@ -19,12 +19,9 @@ package org.apache.hadoop.hdfs.server.na
import java.io.PrintWriter;
import java.io.StringWriter;
-import java.util.ArrayList;
import java.util.Arrays;
-import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
-import java.util.List;
import java.util.Map;
import org.apache.hadoop.classification.InterfaceAudience;
@@ -49,10 +46,8 @@ import com.google.common.primitives.Sign
*/
@InterfaceAudience.Private
public abstract class INode implements Comparable<byte[]> {
- static final List<INode> EMPTY_LIST
- = Collections.unmodifiableList(new ArrayList<INode>());
static final ReadOnlyList<INode> EMPTY_READ_ONLY_LIST
- = ReadOnlyList.Util.asReadOnlyList(EMPTY_LIST);
+ = ReadOnlyList.Util.emptyList();
/**
* The inode name is in java UTF8 encoding;
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
URL:
http://svn.apache.org/viewvc/hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java?rev=1410027&r1=1410026&r2=1410027&view=diff
==============================================================================
---
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
(original)
+++
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/INodeDirectory.java
Thu Nov 15 21:34:54 2012
@@ -586,7 +586,7 @@ public class INodeDirectory extends INod
}
private void updateLatestSnapshot(Snapshot s) {
- if (snapshot == null || snapshot.compareTo(s) < 0) {
+ if (Snapshot.ID_COMPARATOR.compare(snapshot, s) < 0) {
snapshot = s;
}
}
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/INodeDirectoryWithSnapshot.java
URL:
http://svn.apache.org/viewvc/hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/INodeDirectoryWithSnapshot.java?rev=1410027&r1=1410026&r2=1410027&view=diff
==============================================================================
---
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/INodeDirectoryWithSnapshot.java
(original)
+++
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/INodeDirectoryWithSnapshot.java
Thu Nov 15 21:34:54 2012
@@ -79,17 +79,11 @@ public class INodeDirectoryWithSnapshot
return inodes == null? -1: Collections.binarySearch(inodes, name);
}
- /** The ID (e.g. snapshot ID) of this object. */
- final int id;
/** c-list: inode(s) created in current. */
private List<INode> created;
/** d-list: inode(s) deleted from current. */
private List<INode> deleted;
- Diff(int id) {
- this.id = id;
- }
-
/**
* Insert the inode to created.
* @param i the insertion point defined
@@ -251,7 +245,7 @@ public class INodeDirectoryWithSnapshot
@Override
public String toString() {
- return getClass().getSimpleName() + "_" + id
+ return getClass().getSimpleName()
+ ":\n created=" + toString(created)
+ "\n deleted=" + toString(deleted);
}
@@ -261,4 +255,4 @@ public class INodeDirectoryWithSnapshot
super(name, dir.getPermissionStatus());
parent = dir;
}
-}
\ No newline at end of file
+}
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/Snapshot.java
URL:
http://svn.apache.org/viewvc/hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/Snapshot.java?rev=1410027&r1=1410026&r2=1410027&view=diff
==============================================================================
---
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/Snapshot.java
(original)
+++
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/Snapshot.java
Thu Nov 15 21:34:54 2012
@@ -17,11 +17,26 @@
*/
package org.apache.hadoop.hdfs.server.namenode.snapshot;
+import java.util.Comparator;
+
import org.apache.hadoop.classification.InterfaceAudience;
/** Snapshot of a sub-tree in the namesystem. */
@InterfaceAudience.Private
public class Snapshot implements Comparable<byte[]> {
+ /** Compare snapshot IDs with null <= s for any snapshot s. */
+ public static final Comparator<Snapshot> ID_COMPARATOR
+ = new Comparator<Snapshot>() {
+ @Override
+ public int compare(Snapshot left, Snapshot right) {
+ if (left == null) {
+ return right == null? 0: -1;
+ } else {
+ return right == null? 1: left.id - right.id;
+ }
+ }
+ };
+
/** Snapshot ID. */
private final int id;
/** The root directory of the snapshot. */
@@ -41,11 +56,6 @@ public class Snapshot implements Compara
public int compareTo(byte[] bytes) {
return root.compareTo(bytes);
}
-
- /** Compare snapshot IDs. */
- public int compareTo(Snapshot s) {
- return id - s.id;
- }
@Override
public String toString() {
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
URL:
http://svn.apache.org/viewvc/hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java?rev=1410027&r1=1410026&r2=1410027&view=diff
==============================================================================
---
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
(original)
+++
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/ReadOnlyList.java
Thu Nov 15 21:34:54 2012
@@ -52,6 +52,11 @@ public interface ReadOnlyList<E> extends
* Utilities for {@link ReadOnlyList}
*/
public static class Util {
+ /** @return an empty list. */
+ public static <E> ReadOnlyList<E> emptyList() {
+ return ReadOnlyList.Util.asReadOnlyList(Collections.<E>emptyList());
+ }
+
/**
* The same as {@link Collections#binarySearch(List, Object)}
* except that the list is a {@link ReadOnlyList}.
@@ -61,7 +66,20 @@ public interface ReadOnlyList<E> extends
*/
public static <K, E extends Comparable<K>> int binarySearch(
final ReadOnlyList<E> list, final K key) {
- return Collections.binarySearch(asList(list), key);
+ int lower = 0;
+ for(int upper = list.size() - 1; lower <= upper; ) {
+ final int mid = (upper + lower) >>> 1;
+
+ final int d = list.get(mid).compareTo(key);
+ if (d == 0) {
+ return mid;
+ } else if (d > 0) {
+ upper = mid - 1;
+ } else {
+ lower = mid + 1;
+ }
+ }
+ return -(lower + 1);
}
/**
Modified:
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestINodeDirectoryWithSnapshot.java
URL:
http://svn.apache.org/viewvc/hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestINodeDirectoryWithSnapshot.java?rev=1410027&r1=1410026&r2=1410027&view=diff
==============================================================================
---
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestINodeDirectoryWithSnapshot.java
(original)
+++
hadoop/common/branches/HDFS-2802/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/hdfs/server/namenode/snapshot/TestINodeDirectoryWithSnapshot.java
Thu Nov 15 21:34:54 2012
@@ -81,7 +81,7 @@ public class TestINodeDirectoryWithSnaps
// make modifications to current and record the diff
final List<INode> current = new ArrayList<INode>(previous);
- final Diff diff = computeDiff? new Diff(0): null;
+ final Diff diff = computeDiff? new Diff(): null;
for(int m = 0; m < numModifications; m++) {
// if current is empty, the next operation must be create;
@@ -228,4 +228,35 @@ public class TestINodeDirectoryWithSnaps
diff.modify(oldinode, newinode);
}
}
+
+ /**
+ * Test {@link Snapshot#ID_COMPARATOR}.
+ */
+ @Test
+ public void testIdCmp() {
+ final INodeDirectory dir = new INodeDirectory("foo", PERM);
+ final INodeDirectorySnapshottable snapshottable
+ = INodeDirectorySnapshottable.newInstance(dir, 100);
+ final Snapshot[] snapshots = {
+ new Snapshot(1, "s1", snapshottable),
+ new Snapshot(1, "s1", snapshottable),
+ new Snapshot(2, "s2", snapshottable),
+ new Snapshot(2, "s2", snapshottable),
+ };
+
+ Assert.assertEquals(0, Snapshot.ID_COMPARATOR.compare(null, null));
+ for(Snapshot s : snapshots) {
+ Assert.assertTrue(Snapshot.ID_COMPARATOR.compare(null, s) < 0);
+ Assert.assertTrue(Snapshot.ID_COMPARATOR.compare(s, null) > 0);
+
+ for(Snapshot t : snapshots) {
+ final int expected = s.getRoot().getLocalName().compareTo(
+ t.getRoot().getLocalName());
+ final int computed = Snapshot.ID_COMPARATOR.compare(s, t);
+ Assert.assertEquals(expected > 0, computed > 0);
+ Assert.assertEquals(expected == 0, computed == 0);
+ Assert.assertEquals(expected < 0, computed < 0);
+ }
+ }
+ }
}
