From 429aaac6c25bccfd443e95f1502b680c1cc83a3f Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 21 Jan 2019 21:02:37 +0100 Subject: stdlib: Clarify ets docs about table iterations --- lib/stdlib/doc/src/ets.xml | 121 ++++++++++++++++++++++++++++++++------------- 1 file changed, 87 insertions(+), 34 deletions(-) (limited to 'lib/stdlib/doc') 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.

+ -

No other support is available within this module that would guarantee - consistency between objects. However, function - safe_fixtable/2 - can be used to guarantee that a sequence of - first/1 and - next/2 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 - select and - match, - give the same guarantee as - safe_fixtable.

+
+ Table traversal +

There are different ways to traverse through the objects of a table.

+ +

Single-step traversal one key at at time, using + first/1, + next/2, + last/1 and + prev/2.

+ +

Search with simple match patterns, using + match/1/2/3, + match_delete/2 and + match_object/1/2/3.

+ +

Search with more powerful match specifications, using + select/1/2/3, + select_count/2, + select_delete/2, + select_replace/2 and + select_reverse/1/2/3.

+ +

Table conversions, using + tab2file/2/3 and + tab2list/1.

+ + +

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 safe way, on tables where keys are inserted or deleted + during the traversal, may yield the following undesired effects:

+ +

Any key may be missed.

 +

Any key may be found more than once.

 +

The traversal may fail with badarg exception if keys are deleted.

+ + +

A table traversal is safe if either

+ +

the table is of type ordered_set.

+ +

the entire table traversal is done within one ETS function + call.

+ +

function safe_fixtable/2 + is used to keep the table fixated during the entire traversal.

+ +
@@ -871,6 +904,9 @@ ets:is_compiled_ms(Broken). first/1 and next/2.

If the table is empty, '$end_of_table' is returned.

+

Use safe_fixtable/2 + to guarantee safe traversal + for subsequent calls to match/1.

@@ -936,6 +972,10 @@ ets:is_compiled_ms(Broken). first/1 and next/2.

If the table is empty, '$end_of_table' is returned.

+

Use safe_fixtable/2 + to guarantee safe traversal + for subsequent calls to + match_object/1.

@@ -1192,12 +1232,13 @@ ets:select(Table, MatchSpec),

To find the first key in the table, use first/1.

Unless a table of type set, bag, or - duplicate_bag is protected using + duplicate_bag is fixated using safe_fixtable/2, - a traversal can fail if - concurrent updates are made to the table. For table - type ordered_set, the function returns the next key in - order, even if the object does no longer exist.

+ a call to next/2 will fail if Key1 no longer + exists in the table. For table type ordered_set, the function + always returns the next key after Key1 in term + order, regardless whether Key1 ever existed in the + table.

@@ -1212,7 +1253,7 @@ ets:select(Table, MatchSpec), table types, the function is synonymous to next/2. If no previous key exists, '$end_of_table' is returned.

-

To find the last key in the table, use +

To find the last key in an ordered_set table, use last/1.

@@ -1287,7 +1328,16 @@ ets:select(ets:repair_continuation(Broken,MS)). Fix an ETS table for safe traversal.

Fixes a table of type set, bag, or - duplicate_bag for safe traversal.

+ duplicate_bag for + safe traversal using + first/1 & + next/2, + match/3 & + match/1, + match_object/3 & + match_object/1, or + select/3 & + select/1.

A process fixes a table by calling safe_fixtable(Tab, true). The table remains fixed until the process releases it by calling @@ -1300,11 +1350,11 @@ ets:select(ets:repair_continuation(Broken,MS)).

When a table is fixed, a sequence of first/1 and next/2 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 can be returned by - next/2 (it depends on the internal ordering of the keys).

+ 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 next/2 depending on + the ordering of keys within the table and if the key exists at the time + next/2 is called.

Example:

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)). -

Notice that no deleted objects are removed from a +

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) -> info(Tab, safe_fixed_monotonic_time). A system with many processes fixing tables can need a monitor that sends alarms when tables have been fixed for too long.

-

Notice that for table type ordered_set, - safe_fixtable/2 is not necessary, as calls to - first/1 and next/2 always succeed.

+

Notice that safe_fixtable/2 is not necessary for table type + ordered_set and for traversals done by a single ETS function call, + like select/2.

 @@ -1462,7 +1512,10 @@ is_integer(X), is_integer(Y), X + Y < 4711]]> table, which is still faster than traversing the table object by object using first/1 and next/2.

-

If the table is empty, '$end_of_table' is returned.

+

If the table is empty, '$end_of_table' is returned.

+

Use safe_fixtable/2 + to guarantee safe traversal + for subsequent calls to select/1.

@@ -1519,7 +1572,7 @@ is_integer(X), is_integer(Y), X + Y < 4711]]> the match specification result.

The match-and-replace operation for each individual object is guaranteed to be atomic and isolated. The - select_replace table iteration as a whole, like all other select functions, + select_replace table traversal as a whole, like all other select functions, does not give such guarantees.

The match specifiction must be guaranteed to retain the key of any matched object. If not, select_replace will fail with badarg -- cgit v1.2.3