aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2019-01-24 12:26:24 +0100
committerGitHub <[email protected]>2019-01-24 12:26:24 +0100
commita4aeacd28e4e31d3d79b091afcdc528082be2865 (patch)
treedd319be0169c105b44383736e0dd97e3afb19da9 /lib
parentc0f1b4ebb0a532d90a1da18144dff7a645d83220 (diff)
parent429aaac6c25bccfd443e95f1502b680c1cc83a3f (diff)
downloadotp-a4aeacd28e4e31d3d79b091afcdc528082be2865.tar.gz
otp-a4aeacd28e4e31d3d79b091afcdc528082be2865.tar.bz2
otp-a4aeacd28e4e31d3d79b091afcdc528082be2865.zip
Merge PR-2103 from sverker/ets-iteration-doc/OTP-15545
Clarify ETS docs about table iterations
Diffstat (limited to 'lib')
-rw-r--r--lib/stdlib/doc/src/ets.xml121
1 files changed, 87 insertions, 34 deletions
diff --git a/lib/stdlib/doc/src/ets.xml b/lib/stdlib/doc/src/ets.xml
index 70d1aaa74d..ccccf7de88 100644
--- a/lib/stdlib/doc/src/ets.xml
+++ b/lib/stdlib/doc/src/ets.xml
@@ -138,23 +138,56 @@
operation. In database terms the isolation level can be seen as
"serializable", as if all isolated operations are carried out serially,
one after the other in a strict order.</p>
+ </section>
- <p>No other support is available within this module that would guarantee
- consistency between objects. However, function
- <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
- can be used to guarantee that a sequence of
- <seealso marker="#first/1"><c>first/1</c></seealso> and
- <seealso marker="#next/2"><c>next/2</c></seealso> calls traverse the
- table without errors and that each existing object in the table is
- visited exactly once, even if another (or the same) process
- simultaneously deletes or inserts objects into the table.
- Nothing else is guaranteed; in particular objects that are inserted
- or deleted during such a traversal can be visited once or not at all.
- Functions that internally traverse over a table, like
- <seealso marker="#select/1"><c>select</c></seealso> and
- <seealso marker="#match/1"><c>match</c></seealso>,
- give the same guarantee as
- <seealso marker="#safe_fixtable/2"><c>safe_fixtable</c></seealso>.</p>
+ <section><marker id="traversal"></marker>
+ <title>Table traversal</title>
+ <p>There are different ways to traverse through the objects of a table.</p>
+ <list type="bulleted">
+ <item><p><em>Single-step</em> traversal one key at at time, using
+ <seealso marker="#first/1"><c>first/1</c></seealso>,
+ <seealso marker="#next/2"><c>next/2</c></seealso>,
+ <seealso marker="#last/1"><c>last/1</c></seealso> and
+ <seealso marker="#prev/2"><c>prev/2</c></seealso>.</p>
+ </item>
+ <item><p>Search with simple <em>match patterns</em>, using
+ <seealso marker="#match/1"><c>match/1/2/3</c></seealso>,
+ <seealso marker="#match_delete/2"><c>match_delete/2</c></seealso> and
+ <seealso marker="#match_object/1"><c>match_object/1/2/3</c></seealso>.</p>
+ </item>
+ <item><p>Search with more powerful <em>match specifications</em>, using
+ <seealso marker="#select/1"><c>select/1/2/3</c></seealso>,
+ <seealso marker="#select_count/2"><c>select_count/2</c></seealso>,
+ <seealso marker="#select_delete/2"><c>select_delete/2</c></seealso>,
+ <seealso marker="#select_replace/2"><c>select_replace/2</c></seealso> and
+ <seealso marker="#select_reverse/1"><c>select_reverse/1/2/3</c></seealso>.</p>
+ </item>
+ <item><p><em>Table conversions</em>, using
+ <seealso marker="#tab2file/2"><c>tab2file/2/3</c></seealso> and
+ <seealso marker="#tab2list/1"><c>tab2list/1</c></seealso>.</p>
+ </item>
+ </list>
+ <p>None of these ways of table traversal will guarantee a consistent table snapshot
+ if the table is also updated during the traversal. Moreover, traversals not
+ done in a <em>safe</em> way, on tables where keys are inserted or deleted
+ during the traversal, may yield the following undesired effects:</p>
+ <list type="bulleted">
+ <item><p>Any key may be missed.</p></item>
+ <item><p>Any key may be found more than once.</p></item>
+ <item><p>The traversal may fail with <c>badarg</c> exception if keys are deleted.</p>
+ </item>
+ </list>
+ <p>A table traversal is <em>safe</em> if either</p>
+ <list type="bulleted">
+ <item><p>the table is of type <c>ordered_set</c>.</p>
+ </item>
+ <item><p>the entire table traversal is done within one ETS function
+ call.</p>
+ </item>
+ <item><p>function <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+ is used to keep the table fixated during the entire traversal.</p>
+ </item>
+ </list>
</section>
<section>
@@ -871,6 +904,9 @@ ets:is_compiled_ms(Broken).</code>
<seealso marker="#first/1"><c>first/1</c></seealso> and
<seealso marker="#next/2"><c>next/2</c></seealso>.</p>
<p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+ <p>Use <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+ to guarantee <seealso marker="#traversal">safe traversal</seealso>
+ for subsequent calls to <seealso marker="#match/1"><c>match/1</c></seealso>.</p>
</desc>
</func>
@@ -936,6 +972,10 @@ ets:is_compiled_ms(Broken).</code>
<seealso marker="#first/1"><c>first/1</c></seealso> and
<seealso marker="#next/2"><c>next/2</c></seealso>.</p>
<p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+ <p>Use <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+ to guarantee <seealso marker="#traversal">safe traversal</seealso>
+ for subsequent calls to <seealso marker="#match_object/1">
+ <c>match_object/1</c></seealso>.</p>
</desc>
</func>
@@ -1192,12 +1232,13 @@ ets:select(Table, MatchSpec),</code>
<p>To find the first key in the table, use
<seealso marker="#first/1"><c>first/1</c></seealso>.</p>
<p>Unless a table of type <c>set</c>, <c>bag</c>, or
- <c>duplicate_bag</c> is protected using
+ <c>duplicate_bag</c> is fixated using
<seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>,
- a traversal can fail if
- concurrent updates are made to the table. For table
- type <c>ordered_set</c>, the function returns the next key in
- order, even if the object does no longer exist.</p>
+ a call to <c>next/2</c> will fail if <c><anno>Key1</anno></c> no longer
+ exists in the table. For table type <c>ordered_set</c>, the function
+ always returns the next key after <c><anno>Key1</anno></c> in term
+ order, regardless whether <c><anno>Key1</anno></c> ever existed in the
+ table.</p>
</desc>
</func>
@@ -1212,7 +1253,7 @@ ets:select(Table, MatchSpec),</code>
table types, the function is synonymous to
<seealso marker="#next/2"><c>next/2</c></seealso>.
If no previous key exists, <c>'$end_of_table'</c> is returned.</p>
- <p>To find the last key in the table, use
+ <p>To find the last key in an <c>ordered_set</c> table, use
<seealso marker="#last/1"><c>last/1</c></seealso>.</p>
</desc>
</func>
@@ -1287,7 +1328,16 @@ ets:select(ets:repair_continuation(Broken,MS)).</code>
<fsummary>Fix an ETS table for safe traversal.</fsummary>
<desc>
<p>Fixes a table of type <c>set</c>, <c>bag</c>, or
- <c>duplicate_bag</c> for safe traversal.</p>
+ <c>duplicate_bag</c> for <seealso marker="#traversal">
+ safe traversal</seealso> using
+ <seealso marker="#first/1"><c>first/1</c></seealso> &amp;
+ <seealso marker="#next/2"><c>next/2</c></seealso>,
+ <seealso marker="#match/3"><c>match/3</c></seealso> &amp;
+ <seealso marker="#match/1"><c>match/1</c></seealso>,
+ <seealso marker="#match_object/3"><c>match_object/3</c></seealso> &amp;
+ <seealso marker="#match_object/1"><c>match_object/1</c></seealso>, or
+ <seealso marker="#select/3"><c>select/3</c></seealso> &amp;
+ <seealso marker="#select/1"><c>select/1</c></seealso>.</p>
<p>A process fixes a table by calling
<c>safe_fixtable(<anno>Tab</anno>, true)</c>. The table remains
fixed until the process releases it by calling
@@ -1300,11 +1350,11 @@ ets:select(ets:repair_continuation(Broken,MS)).</code>
<p>When a table is fixed, a sequence of
<seealso marker="#first/1"><c>first/1</c></seealso> and
<seealso marker="#next/2"><c>next/2</c></seealso> calls are
- guaranteed to succeed, and each object in
- the table is returned only once, even if objects
- are removed or inserted during the traversal. The keys for new
- objects inserted during the traversal <em>can</em> be returned by
- <c>next/2</c> (it depends on the internal ordering of the keys).</p>
+ guaranteed to succeed even if keys are removed during the
+ traversal. The keys for objects inserted or deleted during a
+ traversal may or may not be returned by <c>next/2</c> depending on
+ the ordering of keys within the table and if the key exists at the time
+ <c>next/2</c> is called.</p>
<p><em>Example:</em></p>
<code type="none">
clean_all_with_value(Tab,X) ->
@@ -1322,7 +1372,7 @@ clean_all_with_value(Tab,X,Key) ->
true
end,
clean_all_with_value(Tab,X,ets:next(Tab,Key)).</code>
- <p>Notice that no deleted objects are removed from a
+ <p>Notice that deleted objects are not freed from a
fixed table until it has been released. If a process fixes a
table but never releases it, the memory used by the deleted
objects is never freed. The performance of operations on
@@ -1332,9 +1382,9 @@ clean_all_with_value(Tab,X,Key) ->
<c>info(Tab, safe_fixed_monotonic_time)</c></seealso>. A system with
many processes fixing tables can need a monitor that sends alarms
when tables have been fixed for too long.</p>
- <p>Notice that for table type <c>ordered_set</c>,
- <c>safe_fixtable/2</c> is not necessary, as calls to
- <c>first/1</c> and <c>next/2</c> always succeed.</p>
+ <p>Notice that <c>safe_fixtable/2</c> is not necessary for table type
+ <c>ordered_set</c> and for traversals done by a single ETS function call,
+ like <seealso marker="#select/2"><c>select/2</c></seealso>.</p>
</desc>
</func>
@@ -1462,7 +1512,10 @@ is_integer(X), is_integer(Y), X + Y < 4711]]></code>
table, which is still faster than traversing the table object by
object using <seealso marker="#first/1"><c>first/1</c></seealso>
and <seealso marker="#next/2"><c>next/2</c></seealso>.</p>
- <p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+ <p>If the table is empty, <c>'$end_of_table'</c> is returned.</p>
+ <p>Use <seealso marker="#safe_fixtable/2"><c>safe_fixtable/2</c></seealso>
+ to guarantee <seealso marker="#traversal">safe traversal</seealso>
+ for subsequent calls to <seealso marker="#select/1"><c>select/1</c></seealso>.</p>
</desc>
</func>
@@ -1519,7 +1572,7 @@ is_integer(X), is_integer(Y), X + Y < 4711]]></code>
the match specification result.</p>
<p>The match-and-replace operation for each individual object is guaranteed to be
<seealso marker="#concurrency">atomic and isolated</seealso>. The
- <c>select_replace</c> table iteration as a whole, like all other select functions,
+ <c>select_replace</c> table traversal as a whole, like all other select functions,
does not give such guarantees.</p>
<p>The match specifiction must be guaranteed to <em>retain the key</em>
of any matched object. If not, <c>select_replace</c> will fail with <c>badarg</c>