import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Load a node stored in the created list from fsimage.
 * @param createdNodeName The name of the created node.
 * @param parent The directory that the created list belongs to.
 * @return The created node.
 */
public static INode loadCreated(byte[] createdNodeName,
    INodeDirectory parent) throws IOException {
  // the INode in the created list should be a reference to another INode
  // in posterior SnapshotDiffs or one of the current children
  for (DirectoryDiff postDiff : parent.getDiffs()) {
    final INode d = postDiff.getChildrenDiff().search(ListType.DELETED,
        createdNodeName);
    if (d != null) {
      return d;
    } // else go to the next SnapshotDiff
  } 
  // use the current child
  INode currentChild = parent.getChild(createdNodeName,
      Snapshot.CURRENT_STATE_ID);
  if (currentChild == null) {
    throw new IOException("Cannot find an INode associated with the INode "
        + DFSUtil.bytes2String(createdNodeName)
        + " in created list while loading FSImage.");
  }
  return currentChild;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** clear the created list */
private QuotaCounts destroyCreatedList(
    final BlockStoragePolicySuite bsps,
    final INodeDirectory currentINode,
    final BlocksMapUpdateInfo collectedBlocks,
    final List<INode> removedINodes) {
  QuotaCounts counts = new QuotaCounts.Builder().build();
  final List<INode> createdList = getList(ListType.CREATED);
  for (INode c : createdList) {
    c.computeQuotaUsage(bsps, counts, true);
    c.destroyAndCollectBlocks(bsps, collectedBlocks, removedINodes);
    // c should be contained in the children list, remove it
    currentINode.removeChild(c);
  }
  createdList.clear();
  return counts;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Undo the rename operation for the dst tree, i.e., if the rename operation
 * (with OVERWRITE option) removes a file/dir from the dst tree, add it back
 * and delete possible record in the deleted list.  
 */
public void undoRename4DstParent(final BlockStoragePolicySuite bsps,
    final INode deletedChild,
    int latestSnapshotId) throws QuotaExceededException {
  DirectoryWithSnapshotFeature sf = getDirectoryWithSnapshotFeature();
  Preconditions.checkState(sf != null,
      "Directory does not have snapshot feature");
  boolean removeDeletedChild = sf.getDiffs().removeChild(ListType.DELETED,
      deletedChild);
  int sid = removeDeletedChild ? Snapshot.CURRENT_STATE_ID : latestSnapshotId;
  final boolean added = addChild(deletedChild, true, sid);
  // update quota usage if adding is successfully and the old child has not
  // been stored in deleted list before
  if (added && !removeDeletedChild) {
    final QuotaCounts counts = deletedChild.computeQuotaUsage(bsps);
    addSpaceConsumed(counts, false);

  }
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Undo the rename operation for the dst tree, i.e., if the rename operation
 * (with OVERWRITE option) removes a file/dir from the dst tree, add it back
 * and delete possible record in the deleted list.  
 */
public void undoRename4DstParent(final INode deletedChild,
    int latestSnapshotId) throws QuotaExceededException {
  DirectoryWithSnapshotFeature sf = getDirectoryWithSnapshotFeature();
  Preconditions.checkState(sf != null,
      "Directory does not have snapshot feature");
  boolean removeDeletedChild = sf.getDiffs().removeChild(ListType.DELETED,
      deletedChild);
  int sid = removeDeletedChild ? Snapshot.CURRENT_STATE_ID : latestSnapshotId;
  final boolean added = addChild(deletedChild, true, sid);
  // update quota usage if adding is successfully and the old child has not
  // been stored in deleted list before
  if (added && !removeDeletedChild) {
    final Quota.Counts counts = deletedChild.computeQuotaUsage();
    addSpaceConsumed(counts.get(Quota.NAMESPACE),
        counts.get(Quota.DISKSPACE), false);
  }
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** clear the created list */
private Quota.Counts destroyCreatedList(
    final INodeDirectoryWithSnapshot currentINode,
    final BlocksMapUpdateInfo collectedBlocks,
    final List<INode> removedINodes) {
  Quota.Counts counts = Quota.Counts.newInstance();
  final List<INode> createdList = getList(ListType.CREATED);
  for (INode c : createdList) {
    c.computeQuotaUsage(counts, true);
    c.destroyAndCollectBlocks(collectedBlocks, removedINodes);
    // c should be contained in the children list, remove it
    currentINode.removeChild(c);
  }
  createdList.clear();
  return counts;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Undo the rename operation for the dst tree, i.e., if the rename operation
 * (with OVERWRITE option) removes a file/dir from the dst tree, add it back
 * and delete possible record in the deleted list.  
 */
public void undoRename4DstParent(final INode deletedChild,
    Snapshot latestSnapshot) throws QuotaExceededException {
  boolean removeDeletedChild = diffs.removeChild(ListType.DELETED,
      deletedChild);
  // pass null for inodeMap since the parent node will not get replaced when
  // undoing rename
  final boolean added = addChild(deletedChild, true, removeDeletedChild ? null
      : latestSnapshot, null);
  // update quota usage if adding is successfully and the old child has not
  // been stored in deleted list before
  if (added && !removeDeletedChild) {
    final Quota.Counts counts = deletedChild.computeQuotaUsage();
    addSpaceConsumed(counts.get(Quota.NAMESPACE),
        counts.get(Quota.DISKSPACE), false);
  }
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Load a node stored in the created list from fsimage.
 * @param createdNodeName The name of the created node.
 * @param parent The directory that the created list belongs to.
 * @return The created node.
 */
private static INode loadCreated(byte[] createdNodeName,
    INodeDirectoryWithSnapshot parent) throws IOException {
  // the INode in the created list should be a reference to another INode
  // in posterior SnapshotDiffs or one of the current children
  for (DirectoryDiff postDiff : parent.getDiffs()) {
    final INode d = postDiff.getChildrenDiff().search(ListType.DELETED,
        createdNodeName);
    if (d != null) {
      return d;
    } // else go to the next SnapshotDiff
  } 
  // use the current child
  INode currentChild = parent.getChild(createdNodeName, null);
  if (currentChild == null) {
    throw new IOException("Cannot find an INode associated with the INode "
        + DFSUtil.bytes2String(createdNodeName)
        + " in created list while loading FSImage.");
  }
  return currentChild;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Replace the given child from the created/deleted list.
 * @return true if the child is replaced; false if the child is not found.
 */
private boolean replace(final ListType type,
    final INode oldChild, final INode newChild) {
  final List<INode> list = getList(type);
  final int i = search(list, oldChild.getLocalNameBytes());
  if (i < 0 || list.get(i).getId() != oldChild.getId()) {
    return false;
  }

  final INode removed = list.set(i, newChild);
  Preconditions.checkState(removed == oldChild);
  return true;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
private boolean removeChild(ListType type, final INode child) {
  final List<INode> list = getList(type);
  final int i = searchIndex(type, child.getLocalNameBytes());
  if (i >= 0 && list.get(i) == child) {
    list.remove(i);
    return true;
  }
  return false;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** clear the deleted list */
private QuotaCounts destroyDeletedList(
    final BlockStoragePolicySuite bsps,
    final BlocksMapUpdateInfo collectedBlocks,
    final List<INode> removedINodes) {
  QuotaCounts counts = new QuotaCounts.Builder().build();
  final List<INode> deletedList = getList(ListType.DELETED);
  for (INode d : deletedList) {
    d.computeQuotaUsage(bsps, counts, false);
    d.destroyAndCollectBlocks(bsps, collectedBlocks, removedINodes);
  }
  deletedList.clear();
  return counts;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** Serialize {@link #created} */
private void writeCreated(DataOutput out) throws IOException {
  final List<INode> created = getList(ListType.CREATED);
  out.writeInt(created.size());
  for (INode node : created) {
    // For INode in created list, we only need to record its local name
    byte[] name = node.getLocalNameBytes();
    out.writeShort(name.length);
    out.write(name);
  }
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** Serialize {@link #deleted} */
private void writeDeleted(DataOutput out,
    ReferenceMap referenceMap) throws IOException {
  final List<INode> deleted = getList(ListType.DELETED);
  out.writeInt(deleted.size());
  for (INode node : deleted) {
    FSImageSerialization.saveINode2Image(node, out, true, referenceMap);
  }
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** Get the list of INodeDirectory contained in the deleted list */
private void getDirsInDeleted(List<INodeDirectory> dirList) {
  for (INode node : getList(ListType.DELETED)) {
    if (node.isDirectory()) {
      dirList.add(node.asDirectory());
    }
  }
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** Replace the given child in the created/deleted list, if there is any. */
public boolean replaceChild(final ListType type, final INode oldChild,
    final INode newChild) {
  final List<DirectoryDiff> diffList = asList();
  for(int i = diffList.size() - 1; i >= 0; i--) {
    final ChildrenDiff diff = diffList.get(i).diff;
    if (diff.replace(type, oldChild, newChild)) {
      return true;
    }
  }
  return false;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Find the corresponding snapshot whose deleted list contains the given
 * inode.
 * @return the id of the snapshot. {@link Snapshot#NO_SNAPSHOT_ID} if the
 * given inode is not in any of the snapshot.
 */
public int findSnapshotDeleted(final INode child) {
  final List<DirectoryDiff> diffList = asList();
  for(int i = diffList.size() - 1; i >= 0; i--) {
    final ChildrenDiff diff = diffList.get(i).diff;
    final int d = diff.searchIndex(ListType.DELETED,
        child.getLocalNameBytes());
    if (d >= 0 && diff.getList(ListType.DELETED).get(d) == child) {
      return diffList.get(i).getSnapshotId();
    }
  }
  return Snapshot.NO_SNAPSHOT_ID;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
public QuotaCounts computeQuotaUsage4CurrentDirectory(
    BlockStoragePolicySuite bsps, byte storagePolicyId,
    QuotaCounts counts) {
  for(DirectoryDiff d : diffs) {
    for(INode deleted : d.getChildrenDiff().getList(ListType.DELETED)) {
      final byte childPolicyId = deleted.getStoragePolicyIDForQuota(storagePolicyId);
      deleted.computeQuotaUsage(bsps, childPolicyId, counts, false,
          Snapshot.CURRENT_STATE_ID);
    }
  }
  return counts;
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
public void computeContentSummary4Snapshot(final BlockStoragePolicySuite bsps,
    final ContentCounts counts) {
  // Create a new blank summary context for blocking processing of subtree.
  ContentSummaryComputationContext summary = 
      new ContentSummaryComputationContext(bsps);
  for(DirectoryDiff d : diffs) {
    for(INode deleted : d.getChildrenDiff().getList(ListType.DELETED)) {
      deleted.computeContentSummary(summary);
    }
  }
  // Add the counts from deleted trees.
  counts.addContents(summary.getCounts());
  // Add the deleted directory count.
  counts.addContent(Content.DIRECTORY, diffs.asList().size());
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
private void serializeDirDiffList(INodeDirectory dir,
    final List<INodeReference> refList, OutputStream out)
    throws IOException {
  DirectoryWithSnapshotFeature sf = dir.getDirectoryWithSnapshotFeature();
  if (sf != null) {
    List<DirectoryDiff> diffList = sf.getDiffs().asList();
    SnapshotDiffSection.DiffEntry entry = SnapshotDiffSection.DiffEntry
        .newBuilder().setInodeId(dir.getId()).setType(Type.DIRECTORYDIFF)
        .setNumOfDiff(diffList.size()).build();
    entry.writeDelimitedTo(out);
    for (int i = diffList.size() - 1; i >= 0; i--) { // reverse order!
      DirectoryDiff diff = diffList.get(i);
      SnapshotDiffSection.DirectoryDiff.Builder db = SnapshotDiffSection.
          DirectoryDiff.newBuilder().setSnapshotId(diff.getSnapshotId())
                       .setChildrenSize(diff.getChildrenSize())
                       .setIsSnapshotRoot(diff.isSnapshotRoot());
      INodeDirectoryAttributes copy = diff.snapshotINode;
      if (!diff.isSnapshotRoot() && copy != null) {
        db.setName(ByteString.copyFrom(copy.getLocalNameBytes()))
            .setSnapshotCopy(
                buildINodeDirectory(copy, parent.getSaverContext()));
      }
      // process created list and deleted list
      List<INode> created = diff.getChildrenDiff()
          .getList(ListType.CREATED);
      db.setCreatedListSize(created.size());
      List<INode> deleted = diff.getChildrenDiff().getList(ListType.DELETED);
      for (INode d : deleted) {
        if (d.isReference()) {
          refList.add(d.asReference());
          db.addDeletedINodeRef(refList.size() - 1);
        } else {
          db.addDeletedINode(d.getId());
        }
      }
      db.build().writeDelimitedTo(out);
      saveCreatedList(created, out);
    }
  }
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/** 
 * Replace the given child with a new child. Note that we no longer need to
 * replace an normal INodeDirectory or INodeFile into an
 * INodeDirectoryWithSnapshot or INodeFileUnderConstruction. The only cases
 * for child replacement is for reference nodes.
 */
public void replaceChild(INode oldChild, final INode newChild,
    final INodeMap inodeMap) {
  Preconditions.checkNotNull(children);
  final int i = searchChildren(newChild.getLocalNameBytes());
  Preconditions.checkState(i >= 0);
  Preconditions.checkState(oldChild == children.get(i)
      || oldChild == children.get(i).asReference().getReferredINode()
          .asReference().getReferredINode());
  oldChild = children.get(i);
  
  if (oldChild.isReference() && newChild.isReference()) {
    // both are reference nodes, e.g., DstReference -> WithName
    final INodeReference.WithCount withCount = 
        (WithCount) oldChild.asReference().getReferredINode();
    withCount.removeReference(oldChild.asReference());
  }
  children.set(i, newChild);
  
  // replace the instance in the created list of the diff list
  DirectoryWithSnapshotFeature sf = this.getDirectoryWithSnapshotFeature();
  if (sf != null) {
    sf.getDiffs().replaceChild(ListType.CREATED, oldChild, newChild);
  }
  
  // update the inodeMap
  if (inodeMap != null) {
    inodeMap.put(newChild);
  }    
}
 

import org.apache.hadoop.hdfs.util.Diff.ListType; //导入依赖的package包/类
/**
 * Make sure we clean the whole subtree under a DstReference node after 
 * deleting a snapshot.
 * see HDFS-5476.
 */
@Test
public void testCleanDstReference() throws Exception {
  final Path test = new Path("/test");
  final Path foo = new Path(test, "foo");
  final Path bar = new Path(foo, "bar");
  hdfs.mkdirs(bar);
  SnapshotTestHelper.createSnapshot(hdfs, test, "s0");
  
  // create file after s0 so that the file should not be included in s0
  final Path fileInBar = new Path(bar, "file");
  DFSTestUtil.createFile(hdfs, fileInBar, BLOCKSIZE, REPL, SEED);
  // rename foo --> foo2
  final Path foo2 = new Path(test, "foo2");
  hdfs.rename(foo, foo2);
  // create snapshot s1, note the file is included in s1
  hdfs.createSnapshot(test, "s1");
  // delete bar and foo2
  hdfs.delete(new Path(foo2, "bar"), true);
  hdfs.delete(foo2, true);
  
  final Path sfileInBar = SnapshotTestHelper.getSnapshotPath(test, "s1",
      "foo2/bar/file");
  assertTrue(hdfs.exists(sfileInBar));
  
  hdfs.deleteSnapshot(test, "s1");
  assertFalse(hdfs.exists(sfileInBar));
  
  restartClusterAndCheckImage(true);
  // make sure the file under bar is deleted 
  final Path barInS0 = SnapshotTestHelper.getSnapshotPath(test, "s0",
      "foo/bar");
  INodeDirectory barNode = fsdir.getINode(barInS0.toString()).asDirectory();
  assertEquals(0, barNode.getChildrenList(Snapshot.CURRENT_STATE_ID).size());
  List<DirectoryDiff> diffList = barNode.getDiffs().asList();
  assertEquals(1, diffList.size());
  DirectoryDiff diff = diffList.get(0);
  assertEquals(0, diff.getChildrenDiff().getList(ListType.DELETED).size());
  assertEquals(0, diff.getChildrenDiff().getList(ListType.CREATED).size());
}