Google Git
Sign in
apache / hadoop-site / 952d547359cafef280f0a0324055741b2ed55be1 / . / content / docs / r3.3.1 / hadoop-project-dist / hadoop-hdfs / build / source / hadoop-hdfs-project / hadoop-hdfs / target / api / org / apache / hadoop / hdfs / server / namenode / snapshot / DiffListBySkipList.html
blob: bf58e0041d948de2a1d9c99d49a40622be8840cc [file] [log] [blame]
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html lang="en">
<head>
<!-- Generated by javadoc (1.8.0_292) on Tue Jun 15 06:06:55 GMT 2021 -->
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>DiffListBySkipList (Apache Hadoop HDFS 3.3.1 API)</title>
<meta name="date" content="2021-06-15">
<link rel="stylesheet" type="text/css" href="../../../../../../../stylesheet.css" title="Style">
<script type="text/javascript" src="../../../../../../../script.js"></script>
</head>
<body>
<script type="text/javascript"><!--
try {
if (location.href.indexOf('is-external=true') == -1) {
parent.document.title="DiffListBySkipList (Apache Hadoop HDFS 3.3.1 API)";
}
}
catch(err) {
}
//-->
var methods = {"i0":10,"i1":10,"i2":10,"i3":10,"i4":10,"i5":10,"i6":10,"i7":10,"i8":10,"i9":10};
var tabs = {65535:["t0","All Methods"],2:["t2","Instance Methods"],8:["t4","Concrete Methods"]};
var altColor = "altColor";
var rowColor = "rowColor";
var tableTab = "tableTab";
var activeTableTab = "activeTableTab";
</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar.top">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.top" title="Skip navigation links">Skip navigation links</a></div>
<a name="navbar.top.firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../../../../../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="class-use/DiffListBySkipList.html">Use</a></li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../../../../../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../../../../../../index-all.html">Index</a></li>
<li><a href="../../../../../../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListByArrayList.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot"><span class="typeNameLink">Prev&nbsp;Class</span></a></li>
<li><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryDiffListFactory.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot"><span class="typeNameLink">Next&nbsp;Class</span></a></li>
</ul>
<ul class="navList">
<li><a href="../../../../../../../index.html?org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html" target="_top">Frames</a></li>
<li><a href="DiffListBySkipList.html" target="_top">No&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="../../../../../../../allclasses-noframe.html">All&nbsp;Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_top");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li><a href="#field.summary">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li><a href="#field.detail">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.detail">Method</a></li>
</ul>
</div>
<a name="skip.navbar.top">
<!-- -->
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<!-- ======== START OF CLASS DATA ======== -->
<div class="header">
<div class="subTitle">org.apache.hadoop.hdfs.server.namenode.snapshot</div>
<h2 title="Class DiffListBySkipList" class="title">Class DiffListBySkipList</h2>
</div>
<div class="contentContainer">
<ul class="inheritance">
<li><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">java.lang.Object</a></li>
<li>
<ul class="inheritance">
<li>org.apache.hadoop.hdfs.server.namenode.snapshot.DiffListBySkipList</li>
</ul>
</li>
</ul>
<div class="description">
<ul class="blockList">
<li class="blockList">
<dl>
<dt>All Implemented Interfaces:</dt>
<dd><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html?is-external=true" title="class or interface in java.lang">Iterable</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;, <a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</dd>
</dl>
<hr>
<br>
<pre>public class <span class="typeNameLabel">DiffListBySkipList</span>
extends <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</a>
implements <a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</pre>
<div class="block">SkipList is an implementation of a data structure for storing a sorted list
of Directory Diff elements, using a hierarchy of linked lists that connect
increasingly sparse subsequences(defined by skip interval here) of the diffs.
The elements contained in the tree must be mutually comparable.
<p>
Consider a case where we have 10 snapshots for a directory starting from s0
to s9 each associated with certain change records in terms of inodes deleted
and created after a particular snapshot and before the next snapshot. The
sequence will look like this:
<p>
s0-&gt;s1-&gt;s2-&gt;s3-&gt;s4-&gt;s5-&gt;s6-&gt;s7-&gt;s8-&gt;s9.
<p>
Assuming a skip interval of 3, which means a new diff will be added at a
level higher than the current level after we have ore than 3 snapshots.
Next level promotion happens after 9 snapshots and so on.
<p>
level 2: s08-------------------------------&gt;s9
level 1: S02-------&gt;s35--------&gt;s68--------&gt;s9
level 0: s0-&gt;s1-&gt;s2-&gt;s3-&gt;s4-&gt;s5-&gt;s6-&gt;s7-&gt;s8-&gt;s9
<p>
s02 will be created by combining diffs for s0, s1, s2 once s3 gets created.
Similarly, s08 will be created by combining s02, s35 and s68 once s9 gets
created.So, for constructing the children list fot s0, we have to combine
s08, s9 and reverse apply to the live fs.
<p>
Similarly, for constructing the children list for s2, s2, s35, s68 and s9
need to get combined(or added) and reverse applied to current fs.
<p>
This approach will improve the snapshot deletion and snapshot diff
calculation.
<p>
Once a snapshot gets deleted, the list needs to be balanced.</div>
</li>
</ul>
</div>
<div class="summary">
<ul class="blockList">
<li class="blockList">
<!-- =========== FIELD SUMMARY =========== -->
<ul class="blockList">
<li class="blockList"><a name="field.summary">
<!-- -->
</a>
<h3>Field Summary</h3>
<table class="memberSummary" border="0" cellpadding="3" cellspacing="0" summary="Field Summary table, listing fields, and an explanation">
<caption><span>Fields</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colFirst" scope="col">Modifier and Type</th>
<th class="colLast" scope="col">Field and Description</th>
</tr>
<tr class="altColor">
<td class="colFirst"><code>static org.slf4j.Logger</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#LOG">LOG</a></span></code>&nbsp;</td>
</tr>
</table>
<ul class="blockList">
<li class="blockList"><a name="fields.inherited.from.class.org.apache.hadoop.hdfs.server.namenode.snapshot.DiffList">
<!-- -->
</a>
<h3>Fields inherited from interface&nbsp;org.apache.hadoop.hdfs.server.namenode.snapshot.<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a></h3>
<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#EMPTY_LIST">EMPTY_LIST</a></code></li>
</ul>
</li>
</ul>
<!-- ======== CONSTRUCTOR SUMMARY ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor.summary">
<!-- -->
</a>
<h3>Constructor Summary</h3>
<table class="memberSummary" border="0" cellpadding="3" cellspacing="0" summary="Constructor Summary table, listing constructors, and an explanation">
<caption><span>Constructors</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colOne" scope="col">Constructor and Description</th>
</tr>
<tr class="altColor">
<td class="colOne"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#DiffListBySkipList-int-">DiffListBySkipList</a></span>(int&nbsp;capacity)</code>
<div class="block">Constructs a new, empty instance of SkipList.</div>
</td>
</tr>
</table>
</li>
</ul>
<!-- ========== METHOD SUMMARY =========== -->
<ul class="blockList">
<li class="blockList"><a name="method.summary">
<!-- -->
</a>
<h3>Method Summary</h3>
<table class="memberSummary" border="0" cellpadding="3" cellspacing="0" summary="Method Summary table, listing methods, and an explanation">
<caption><span id="t0" class="activeTableTab"><span>All Methods</span><span class="tabEnd">&nbsp;</span></span><span id="t2" class="tableTab"><span><a href="javascript:show(2);">Instance Methods</a></span><span class="tabEnd">&nbsp;</span></span><span id="t4" class="tableTab"><span><a href="javascript:show(8);">Concrete Methods</a></span><span class="tabEnd">&nbsp;</span></span></caption>
<tr>
<th class="colFirst" scope="col">Modifier and Type</th>
<th class="colLast" scope="col">Method and Description</th>
</tr>
<tr id="i0" class="altColor">
<td class="colFirst"><code>void</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#addFirst-org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.DirectoryDiff-">addFirst</a></span>(<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&nbsp;diff)</code>
<div class="block">Adds the specified data element to the beginning of the SkipList,
if the element is not already present.</div>
</td>
</tr>
<tr id="i1" class="rowColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#addLast-org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.DirectoryDiff-">addLast</a></span>(<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&nbsp;diff)</code>
<div class="block">Adds the specified data element to the end of the SkipList,
if the element is not already present.</div>
</td>
</tr>
<tr id="i2" class="altColor">
<td class="colFirst"><code>int</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#binarySearch-int-">binarySearch</a></span>(int&nbsp;key)</code>
<div class="block">Searches the list for the specified object using the binary
search algorithm.</div>
</td>
</tr>
<tr id="i3" class="rowColor">
<td class="colFirst"><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a></code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#get-int-">get</a></span>(int&nbsp;index)</code>
<div class="block">Returns the data element at the specified index in this SkipList.</div>
</td>
</tr>
<tr id="i4" class="altColor">
<td class="colFirst"><code><a href="https://docs.oracle.com/javase/8/docs/api/java/util/List.html?is-external=true" title="class or interface in java.util">List</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#getMinListForRange-int-int-org.apache.hadoop.hdfs.server.namenode.INodeDirectory-">getMinListForRange</a></span>(int&nbsp;fromIndex,
int&nbsp;toIndex,
<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/INodeDirectory.html" title="class in org.apache.hadoop.hdfs.server.namenode">INodeDirectory</a>&nbsp;dir)</code>
<div class="block">This function returns the minimal set of diffs required to combine in
order to generate all the changes occurred between fromIndex and
toIndex.</div>
</td>
</tr>
<tr id="i5" class="rowColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#isEmpty--">isEmpty</a></span>()</code>
<div class="block">Returns true if this SkipList contains no data elements.</div>
</td>
</tr>
<tr id="i6" class="altColor">
<td class="colFirst"><code><a href="https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html?is-external=true" title="class or interface in java.util">Iterator</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#iterator--">iterator</a></span>()</code>
<div class="block">Iterator is an iterator over the SkipList.</div>
</td>
</tr>
<tr id="i7" class="rowColor">
<td class="colFirst"><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a></code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#remove-int-">remove</a></span>(int&nbsp;index)</code>
<div class="block">Removes the element at the specified position in this list.</div>
</td>
</tr>
<tr id="i8" class="altColor">
<td class="colFirst"><code>int</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#size--">size</a></span>()</code>
<div class="block">Returns the number of data elements in this SkipList.</div>
</td>
</tr>
<tr id="i9" class="rowColor">
<td class="colFirst"><code><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/String.html?is-external=true" title="class or interface in java.lang">String</a></code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html#toString--">toString</a></span>()</code>&nbsp;</td>
</tr>
</table>
<ul class="blockList">
<li class="blockList"><a name="methods.inherited.from.class.java.lang.Object">
<!-- -->
</a>
<h3>Methods inherited from class&nbsp;java.lang.<a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</a></h3>
<code><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#clone--" title="class or interface in java.lang">clone</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#equals-java.lang.Object-" title="class or interface in java.lang">equals</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#finalize--" title="class or interface in java.lang">finalize</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#getClass--" title="class or interface in java.lang">getClass</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#hashCode--" title="class or interface in java.lang">hashCode</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#notify--" title="class or interface in java.lang">notify</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#notifyAll--" title="class or interface in java.lang">notifyAll</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#wait--" title="class or interface in java.lang">wait</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#wait-long-" title="class or interface in java.lang">wait</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#wait-long-int-" title="class or interface in java.lang">wait</a></code></li>
</ul>
<ul class="blockList">
<li class="blockList"><a name="methods.inherited.from.class.org.apache.hadoop.hdfs.server.namenode.snapshot.DiffList">
<!-- -->
</a>
<h3>Methods inherited from interface&nbsp;org.apache.hadoop.hdfs.server.namenode.snapshot.<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a></h3>
<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#emptyList--">emptyList</a>, <a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#unmodifiableList-org.apache.hadoop.hdfs.server.namenode.snapshot.DiffList-">unmodifiableList</a></code></li>
</ul>
<ul class="blockList">
<li class="blockList"><a name="methods.inherited.from.class.java.lang.Iterable">
<!-- -->
</a>
<h3>Methods inherited from interface&nbsp;java.lang.<a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html?is-external=true" title="class or interface in java.lang">Iterable</a></h3>
<code><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html?is-external=true#forEach-java.util.function.Consumer-" title="class or interface in java.lang">forEach</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html?is-external=true#spliterator--" title="class or interface in java.lang">spliterator</a></code></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
<div class="details">
<ul class="blockList">
<li class="blockList">
<!-- ============ FIELD DETAIL =========== -->
<ul class="blockList">
<li class="blockList"><a name="field.detail">
<!-- -->
</a>
<h3>Field Detail</h3>
<a name="LOG">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>LOG</h4>
<pre>public static final&nbsp;org.slf4j.Logger LOG</pre>
</li>
</ul>
</li>
</ul>
<!-- ========= CONSTRUCTOR DETAIL ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor.detail">
<!-- -->
</a>
<h3>Constructor Detail</h3>
<a name="DiffListBySkipList-int-">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>DiffListBySkipList</h4>
<pre>public&nbsp;DiffListBySkipList(int&nbsp;capacity)</pre>
<div class="block">Constructs a new, empty instance of SkipList.</div>
</li>
</ul>
</li>
</ul>
<!-- ============ METHOD DETAIL ========== -->
<ul class="blockList">
<li class="blockList"><a name="method.detail">
<!-- -->
</a>
<h3>Method Detail</h3>
<a name="addFirst-org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.DirectoryDiff-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>addFirst</h4>
<pre>public&nbsp;void&nbsp;addFirst(<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&nbsp;diff)</pre>
<div class="block">Adds the specified data element to the beginning of the SkipList,
if the element is not already present.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#addFirst-T-">addFirst</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>diff</code> - the element to be inserted</dd>
</dl>
</li>
</ul>
<a name="addLast-org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.DirectoryDiff-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>addLast</h4>
<pre>public&nbsp;boolean&nbsp;addLast(<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&nbsp;diff)</pre>
<div class="block">Adds the specified data element to the end of the SkipList,
if the element is not already present.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#addLast-T-">addLast</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>diff</code> - the element to be inserted</dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>true, if insertion is successful</dd>
</dl>
</li>
</ul>
<a name="get-int-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>get</h4>
<pre>public&nbsp;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&nbsp;get(int&nbsp;index)</pre>
<div class="block">Returns the data element at the specified index in this SkipList.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#get-int-">get</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>index</code> - The index of the element to be returned.</dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>The element at the specified index in this SkipList.</dd>
</dl>
</li>
</ul>
<a name="remove-int-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>remove</h4>
<pre>public&nbsp;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&nbsp;remove(int&nbsp;index)</pre>
<div class="block">Removes the element at the specified position in this list.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#remove-int-">remove</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>index</code> - the index of the element to be removed</dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>the removed DirectoryDiff</dd>
</dl>
</li>
</ul>
<a name="isEmpty--">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>isEmpty</h4>
<pre>public&nbsp;boolean&nbsp;isEmpty()</pre>
<div class="block">Returns true if this SkipList contains no data elements. In other words,
returns true if the size of this SkipList is zero.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#isEmpty--">isEmpty</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>True if this SkipList contains no elements.</dd>
</dl>
</li>
</ul>
<a name="size--">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>size</h4>
<pre>public&nbsp;int&nbsp;size()</pre>
<div class="block">Returns the number of data elements in this SkipList.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#size--">size</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>The number of elements in this SkipList.</dd>
</dl>
</li>
</ul>
<a name="iterator--">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>iterator</h4>
<pre>public&nbsp;<a href="https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html?is-external=true" title="class or interface in java.util">Iterator</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;&nbsp;iterator()</pre>
<div class="block">Iterator is an iterator over the SkipList. This should
always provide a linear view of the list.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html?is-external=true#iterator--" title="class or interface in java.lang">iterator</a></code>&nbsp;in interface&nbsp;<code><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html?is-external=true" title="class or interface in java.lang">Iterable</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
</dl>
</li>
</ul>
<a name="binarySearch-int-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>binarySearch</h4>
<pre>public&nbsp;int&nbsp;binarySearch(int&nbsp;key)</pre>
<div class="block"><span class="descfrmTypeLabel">Description copied from interface:&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#binarySearch-int-">DiffList</a></code></span></div>
<div class="block">Searches the list for the specified object using the binary
search algorithm.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#binarySearch-int-">binarySearch</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>key</code> - key to be searched for</dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>the index of the search key, if it is contained in the list
otherwise, (-insertion point - 1).</dd>
</dl>
</li>
</ul>
<a name="getMinListForRange-int-int-org.apache.hadoop.hdfs.server.namenode.INodeDirectory-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>getMinListForRange</h4>
<pre>public&nbsp;<a href="https://docs.oracle.com/javase/8/docs/api/java/util/List.html?is-external=true" title="class or interface in java.util">List</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;&nbsp;getMinListForRange(int&nbsp;fromIndex,
int&nbsp;toIndex,
<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/INodeDirectory.html" title="class in org.apache.hadoop.hdfs.server.namenode">INodeDirectory</a>&nbsp;dir)</pre>
<div class="block">This function returns the minimal set of diffs required to combine in
order to generate all the changes occurred between fromIndex and
toIndex.</div>
<dl>
<dt><span class="overrideSpecifyLabel">Specified by:</span></dt>
<dd><code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html#getMinListForRange-int-int-org.apache.hadoop.hdfs.server.namenode.INodeDirectory-">getMinListForRange</a></code>&nbsp;in interface&nbsp;<code><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffList.html" title="interface in org.apache.hadoop.hdfs.server.namenode.snapshot">DiffList</a>&lt;<a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryWithSnapshotFeature.DirectoryDiff.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot">DirectoryWithSnapshotFeature.DirectoryDiff</a>&gt;</code></dd>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>fromIndex</code> - index from where the summation has to start(inclusive)</dd>
<dd><code>toIndex</code> - index till where the summation has to end(exclusive)</dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>list of Directory Diff</dd>
</dl>
</li>
</ul>
<a name="toString--">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>toString</h4>
<pre>public&nbsp;<a href="https://docs.oracle.com/javase/8/docs/api/java/lang/String.html?is-external=true" title="class or interface in java.lang">String</a>&nbsp;toString()</pre>
<dl>
<dt><span class="overrideSpecifyLabel">Overrides:</span></dt>
<dd><code><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#toString--" title="class or interface in java.lang">toString</a></code>&nbsp;in class&nbsp;<code><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</a></code></dd>
</dl>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<!-- ========= END OF CLASS DATA ========= -->
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar.bottom">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.bottom" title="Skip navigation links">Skip navigation links</a></div>
<a name="navbar.bottom.firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../../../../../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="class-use/DiffListBySkipList.html">Use</a></li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../../../../../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../../../../../../index-all.html">Index</a></li>
<li><a href="../../../../../../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListByArrayList.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot"><span class="typeNameLink">Prev&nbsp;Class</span></a></li>
<li><a href="../../../../../../../org/apache/hadoop/hdfs/server/namenode/snapshot/DirectoryDiffListFactory.html" title="class in org.apache.hadoop.hdfs.server.namenode.snapshot"><span class="typeNameLink">Next&nbsp;Class</span></a></li>
</ul>
<ul class="navList">
<li><a href="../../../../../../../index.html?org/apache/hadoop/hdfs/server/namenode/snapshot/DiffListBySkipList.html" target="_top">Frames</a></li>
<li><a href="DiffListBySkipList.html" target="_top">No&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="../../../../../../../allclasses-noframe.html">All&nbsp;Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_bottom");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li><a href="#field.summary">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li><a href="#field.detail">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.detail">Method</a></li>
</ul>
</div>
<a name="skip.navbar.bottom">
<!-- -->
</a></div>
<!-- ======== END OF BOTTOM NAVBAR ======= -->
<p class="legalCopy"><small>Copyright &#169; 2008&#x2013;2021 <a href="https://www.apache.org">Apache Software Foundation</a>. All rights reserved.</small></p>
</body>
</html>