[m-rev.] for review: Use a better algorithm for unwinding version_arrays.
Paul Bone
paul at bone.id.au
Tue Jul 29 14:59:53 AEST 2014
Use a better algorithm for unwinding version_arrays.
For review by Peter Wang.
Branches: master, version-14_01-branch.
This is an alternative implementation to something I've recently put on the
release branch. If we beleive that this is better and/or less risky than my
previous change then it could go onto the release branch too.
---
The old version_array rewind code used linear stack space in order to
perform it's updates in the right order (newest to oldest) by following the
structure's next pointers (which are a oldest to newest list). I previously
introduced week prev pointers so that walking over this structure newest to
oldest could be done with constant stack space. However that is less
efficient than the method suggested by Peter Wang.
Peter suggested using a bitmap and traversing oldest-to-newest, marking
each update in the bitmap and checking the bitmap before making any update.
Thus preserving older values over newer ones (which is good, this code
_rewinds_ updates). This patch implements Peter's suggestion and removes
the prev pointers from the structure for C and Java backends.
library/version_array.m:
As above.
runtime/mercury_bitmap.h:
Add some macros for initialising bitmaps and testing, setting and clearing
their bits.
library/bitmap.m:
java/runtime/MercuryBitmap.java:
Move the MercuryBitmap class into the runtime library. This makes it
easier for other standard library modules to use this Java
class.
tests/hard_coded/version_array_test.exp:
tests/hard_coded/version_array_test.m:
Ensure that the test verifies that rolling back updates to a version
array rolls back changes in the correct order: If two updates modify the
same cell, then the older one should be visible in the result.
Use longer arrays so that the bitmap used in the rollback code is more
than one byte in length.
---
java/runtime/MercuryBitmap.java | 83 +++++++++++++
library/bitmap.m | 38 +-----
library/version_array.m | 204 ++++++++++++--------------------
runtime/mercury_bitmap.h | 37 +++++-
tests/hard_coded/version_array_test.exp | 19 +--
tests/hard_coded/version_array_test.m | 48 ++++----
6 files changed, 233 insertions(+), 196 deletions(-)
create mode 100644 java/runtime/MercuryBitmap.java
diff --git a/java/runtime/MercuryBitmap.java b/java/runtime/MercuryBitmap.java
new file mode 100644
index 0000000..5a83023
--- /dev/null
+++ b/java/runtime/MercuryBitmap.java
@@ -0,0 +1,83 @@
+//
+// Copyright (C) 2001-2002, 2004-2007, 2009-2011 The University of Melbourne
+// Copyright (C) 2014 The Mercury Team.
+// This file may only be copied under the terms of the GNU Library General
+// Public License - see the file COPYING.LIB in the Mercury distribution.
+//
+
+package jmercury.runtime;
+
+/**
+ * Simple bitmap implementation.
+ * This bitmap class is mainly used by bitmap.m in the standard library. It
+ * is also used by version_array.m which is why it is part of the
+ * jmercury.runtime package rather than being internal to bitmap.m
+ */
+public class MercuryBitmap implements java.io.Serializable {
+ public static final int BITS_PER_BYTE = 8;
+ public int num_bits;
+ public byte[] elements;
+
+ public MercuryBitmap(int numBits) {
+ this.num_bits = numBits;
+ this.elements = new byte[numBits / 8 + (((numBits % 8) != 0) ? 1 : 0)];
+ }
+
+ public MercuryBitmap(int numBits, byte[] elements) {
+ // This is provided so that foreign code can construct bitmaps from an
+ // existing byte array.
+ this.num_bits = numBits;
+ this.elements = elements;
+ }
+
+ @Override
+ public boolean equals(Object that) {
+ if (this == that) {
+ return true;
+ }
+ if (that instanceof MercuryBitmap) {
+ MercuryBitmap other = (MercuryBitmap)that;
+ return this.num_bits == other.num_bits
+ && java.util.Arrays.equals(this.elements, other.elements);
+ }
+ return false;
+ }
+
+ public byte getByte(int byteno)
+ {
+ return elements[byteno];
+ }
+
+ public boolean getBit(int bit)
+ {
+ return (getByte(byteIndexForBit(bit))
+ & (1 << bitIndexWithinByte(bit))) != 0;
+ }
+
+ public void setBit(int bit)
+ {
+ byte b;
+
+ b = getByte(byteIndexForBit(bit));
+ b |= 1 << bitIndexWithinByte(bit);
+ elements[byteIndexForBit(bit)] = b;
+ }
+
+ public void clearBit(int bit)
+ {
+ byte b;
+
+ b = getByte(byteIndexForBit(bit));
+ b &= ~(1 << bitIndexWithinByte(bit));
+ elements[byteIndexForBit(bit)] = b;
+ }
+
+ public static int byteIndexForBit(int bit) {
+ return bit / BITS_PER_BYTE;
+ }
+
+ public static int bitIndexWithinByte(int bit) {
+ return bit % BITS_PER_BYTE;
+ }
+
+}
diff --git a/library/bitmap.m b/library/bitmap.m
index 24e1379..7ea7aef 100644
--- a/library/bitmap.m
+++ b/library/bitmap.m
@@ -1525,36 +1525,8 @@ combine_hash(X, H0, H) :-
#include ""mercury_type_info.h""
").
-:- pragma foreign_code("Java", "
-public static class MercuryBitmap implements java.io.Serializable {
- public int num_bits;
- public byte[] elements;
-
- public MercuryBitmap(int numBits) {
- this.num_bits = numBits;
- this.elements = new byte[numBits / 8 + (((numBits % 8) != 0) ? 1 : 0)];
- }
-
- public MercuryBitmap(int numBits, byte[] elements) {
- // This is provided so that foreign code can construct bitmaps from an
- // existing byte array.
- this.num_bits = numBits;
- this.elements = elements;
- }
-
- @Override
- public boolean equals(Object that) {
- if (this == that) {
- return true;
- }
- if (that instanceof MercuryBitmap) {
- MercuryBitmap other = (MercuryBitmap)that;
- return this.num_bits == other.num_bits
- && java.util.Arrays.equals(this.elements, other.elements);
- }
- return false;
- }
-}
+:- pragma foreign_decl("Java", "
+import jmercury.runtime.MercuryBitmap;
").
:- pragma foreign_code("C#", "
@@ -1593,7 +1565,7 @@ public class MercuryBitmap {
:- pragma foreign_type("C", bitmap, "MR_BitmapPtr",
[can_pass_as_mercury_type])
where equality is bitmap_equal, comparison is bitmap_compare.
-:- pragma foreign_type("Java", bitmap, "bitmap.MercuryBitmap")
+:- pragma foreign_type("Java", bitmap, "jmercury.runtime.MercuryBitmap")
where equality is bitmap_equal, comparison is bitmap_compare.
:- pragma foreign_type("C#", bitmap, "bitmap.MercuryBitmap")
where equality is bitmap_equal, comparison is bitmap_compare.
@@ -1954,7 +1926,7 @@ _ ^ unsafe_byte(_) = _ :- private_builtin.sorry("bitmap.unsafe_byte").
allocate_bitmap(N::in) = (BM::bitmap_uo),
[will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
"
- BM = new bitmap.MercuryBitmap(N);
+ BM = new MercuryBitmap(N);
").
:- pragma foreign_proc("C#",
@@ -2000,7 +1972,7 @@ resize_bitmap(OldBM, N) =
copy(BM0::in) = (BM::bitmap_uo),
[will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
"
- BM = new bitmap.MercuryBitmap(BM0.num_bits);
+ BM = new MercuryBitmap(BM0.num_bits);
System.arraycopy(BM0.elements, 0, BM.elements, 0, BM0.elements.length);
").
diff --git a/library/version_array.m b/library/version_array.m
index fdfb047..0a418b2 100644
--- a/library/version_array.m
+++ b/library/version_array.m
@@ -600,7 +600,6 @@ cmp_version_array_2(I, Size, VAa, VAb, R) :-
VA->value = (MR_Word) NULL;
VA->rest.array = (MR_ArrayPtr) array;
VA->rest.array->size = 0;
- VA->prev = MR_NULL_WEAK_PTR;
#ifdef MR_THREAD_SAFE
MR_incr_hp_type_msg(VA->lock, MercuryLock, MR_ALLOC_ID, NULL);
@@ -640,7 +639,6 @@ cmp_version_array_2(I, Size, VAa, VAb, R) :-
VA->value = (MR_Word) NULL;
VA->rest.array = (MR_ArrayPtr) array;
VA->rest.array->size = 0;
- VA->prev = MR_NULL_WEAK_PTR;
#ifdef MR_THREAD_SAFE
VA->lock = NULL;
@@ -680,7 +678,6 @@ cmp_version_array_2(I, Size, VAa, VAb, R) :-
VA->value = (MR_Word) NULL;
VA->rest.array = (MR_ArrayPtr) array;
VA->rest.array->size = N;
- VA->prev = MR_NULL_WEAK_PTR;
for (i = 0; i < N; i++) {
VA->rest.array->elements[i] = X;
@@ -727,7 +724,6 @@ unsafe_new(N, X) = unsafe_init(N, X).
VA->value = (MR_Word) NULL;
VA->rest.array = (MR_ArrayPtr) array;
VA->rest.array->size = N;
- VA->prev = MR_NULL_WEAK_PTR;
for (i = 0; i < N; i++) {
VA->rest.array->elements[i] = X;
@@ -927,7 +923,6 @@ struct ML_va {
MR_ArrayPtr array; /* Valid if index == -1 */
ML_va_ptr next; /* Valid if index >= 0 */
} rest;
- MR_weak_ptr prev; /* NULL if this is the oldest */
#ifdef MR_THREAD_SAFE
MercuryLock *lock; /* NULL or lock */
#endif
@@ -979,6 +974,9 @@ ML_va_resize_dolock(ML_va_ptr, MR_Integer, MR_Word, MR_AllocSiteInfoPtr);
:- pragma foreign_decl("C", local, "
+#include ""mercury_types.h""
+#include ""mercury_bitmap.h""
+
/*
** Returns the number of items in a version array.
*/
@@ -1160,7 +1158,6 @@ ML_va_set(ML_va_ptr VA0, MR_Integer I, MR_Word X, ML_va_ptr *VAptr,
VA1->index = -1;
VA1->value = (MR_Word) NULL;
VA1->rest.array = VA0->rest.array;
- MR_new_weak_ptr(&(VA1->prev), VA0);
#ifdef MR_THREAD_SAFE
VA1->lock = VA0->lock;
#endif
@@ -1205,7 +1202,6 @@ ML_va_flat_copy(ML_const_va_ptr VA0, MR_AllocSiteInfoPtr alloc_id)
VA->value = (MR_Word) NULL;
VA->rest.array = (MR_ArrayPtr) array;
VA->rest.array->size = N;
- VA->prev = MR_NULL_WEAK_PTR;
for (i = 0; i < N; i++) {
VA->rest.array->elements[i] = latest->rest.array->elements[i];
@@ -1228,9 +1224,10 @@ ML_va_flat_copy(ML_const_va_ptr VA0, MR_AllocSiteInfoPtr alloc_id)
static void
ML_va_rewind_into(ML_va_ptr VA_dest, ML_const_va_ptr VA_src)
{
- MR_Integer I;
- MR_Word X;
- ML_va_ptr cur;
+ MR_Integer I;
+ MR_Word X;
+ ML_const_va_ptr cur;
+ MR_BitmapPtr bitmap;
if (ML_va_latest_version(VA_src)) {
/* Shortcut */
@@ -1238,29 +1235,23 @@ ML_va_rewind_into(ML_va_ptr VA_dest, ML_const_va_ptr VA_src)
}
/*
- ** Copy elements in the reverse order that they were updated into the
- ** latest array, then return the latest array.
+ ** Rewind elements from the oldest to the newest, undoing their changes.
+ ** So that we undo elements in the correct order we use a bitmap to
+ ** ensure that we never update an array slot twice.
*/
- cur = ML_va_get_latest(VA_src);
- /* start from first 'update' record */
- cur = MR_weak_ptr_read(&(cur->prev));
- while (cur != VA_src) {
+ cur = VA_src;
+ MR_allocate_bitmap_msg(bitmap, VA_dest->rest.array->size, MR_ALLOC_ID);
+ MR_bitmap_zero(bitmap);
+ while (!ML_va_latest_version(cur)) {
I = cur->index;
X = cur->value;
- if (I < VA_dest->rest.array->size) {
+ if (I < VA_dest->rest.array->size && !MR_bitmap_get(bitmap, I)) {
VA_dest->rest.array->elements[I] = X;
+ MR_bitmap_set(bitmap, I);
}
- cur = MR_weak_ptr_read(&(cur->prev));
+ cur = cur->rest.next;
}
-
- /*
- * This loop must be inclusive of the update in VA.
- */
- I = cur->index;
- X = cur->value;
-
- VA_dest->rest.array->elements[I] = X;
}
ML_va_ptr
@@ -1281,10 +1272,11 @@ ML_va_rewind_dolock(ML_va_ptr VA)
static ML_va_ptr
ML_va_rewind(ML_va_ptr VA)
{
- MR_Integer I;
- MR_Word X;
- ML_va_ptr cur;
- ML_va_ptr last_visited;
+ MR_Integer I;
+ MR_Word X;
+ ML_va_ptr cur;
+ MR_ArrayPtr array;
+ MR_BitmapPtr bitmap;
if (ML_va_latest_version(VA)) {
/* Shortcut */
@@ -1292,43 +1284,25 @@ ML_va_rewind(ML_va_ptr VA)
}
/*
- ** last_visited is the last element we interated through, we remember it
- ** because we update it's prev pointer after the loop. This isn't
- ** strictly required as we're already destroying that list.
+ ** Rewind elements from the oldest to the newest, undoing their changes.
+ ** So that we undo elements in the correct order we use a bitmap to
+ ** ensure that we never update an array slot twice.
*/
- last_visited = NULL;
-
- /*
- ** Copy elements in the reverse order that they were updated into the
- ** latest array, then return the latest array.
- */
- cur = ML_va_get_latest(VA);
- VA->rest.array = cur->rest.array;
- /* start from first 'update' record */
- cur = MR_weak_ptr_read(&(cur->prev));
- while (cur != VA) {
+ cur = VA;
+ array = ML_va_get_latest(VA)->rest.array;
+ MR_allocate_bitmap_msg(bitmap, array->size, MR_ALLOC_ID);
+ while (!ML_va_latest_version(cur)) {
I = cur->index;
X = cur->value;
- VA->rest.array->elements[I] = X;
-
- last_visited = cur;
- cur = MR_weak_ptr_read(&(cur->prev));
- }
- /*
- * This loop must be inclusive of the update in VA.
- */
- I = cur->index;
- X = cur->value;
-
- VA->rest.array->elements[I] = X;
+ if (!MR_bitmap_get(bitmap, I)) {
+ array->elements[I] = X;
+ MR_bitmap_set(bitmap, I);
+ }
- /*
- * Clear the prev pointer since we've broken the chain.
- */
- if (NULL != last_visited) {
- last_visited->prev = MR_NULL_WEAK_PTR;
+ cur = cur->rest.next;
}
+ VA->rest.array = array;
/*
* This element is no-longer an update element.
@@ -1380,7 +1354,6 @@ ML_va_resize(ML_va_ptr VA0, MR_Integer N, MR_Word X,
VA->value = (MR_Word) NULL;
VA->rest.array = (MR_ArrayPtr) array;
VA->rest.array->size = N;
- VA->prev = MR_NULL_WEAK_PTR;
for (i = 0; i < min; i++) {
VA->rest.array->elements[i] = latest->rest.array->elements[i];
@@ -1761,7 +1734,7 @@ public class ML_uva : ML_va {
").
:- pragma foreign_decl("Java", local, "
-import java.lang.ref.WeakReference;
+import jmercury.runtime.MercuryBitmap;
").
:- pragma foreign_code("Java", "
@@ -1851,8 +1824,6 @@ public static class ML_uva implements ML_va, java.io.Serializable {
private Object value; /* Valid if index >= 0 */
private Object rest; /* array if index == -1 */
/* next if index >= 0 */
- private WeakReference<ML_uva>
- prev; /* previous array update */
private boolean clone = false;
@@ -1863,7 +1834,6 @@ public static class ML_uva implements ML_va, java.io.Serializable {
va.index = -1;
va.value = null;
va.rest = new Object[0];
- va.prev = null;
return va;
}
@@ -1872,7 +1842,6 @@ public static class ML_uva implements ML_va, java.io.Serializable {
va.index = -1;
va.value = null;
va.rest = new Object[N];
- va.prev = null;
java.util.Arrays.fill(va.array(), X);
return va;
}
@@ -1892,7 +1861,6 @@ public static class ML_uva implements ML_va, java.io.Serializable {
VA.index = -1;
VA.value = null;
VA.rest = new Object[N];
- VA.prev = null;
System.arraycopy(latest.array(), 0, VA.array(), 0, min);
@@ -1957,7 +1925,6 @@ public static class ML_uva implements ML_va, java.io.Serializable {
VA1.index = -1;
VA1.value = null;
VA1.rest = VA0.array();
- VA1.prev = new WeakReference<ML_uva>(VA0);
VA0.index = I;
VA0.value = VA0.array()[I];
@@ -1985,7 +1952,6 @@ public static class ML_uva implements ML_va, java.io.Serializable {
VA.index = -1;
VA.value = null;
VA.rest = latest.array().clone();
- VA.prev = null;
VA.clone = true;
VA0.rewind_into(VA);
@@ -2003,97 +1969,73 @@ public static class ML_uva implements ML_va, java.io.Serializable {
private void rewind_into(ML_uva VA)
{
- int I;
- Object X;
- ML_uva cur;
+ int I;
+ Object X;
+ ML_uva cur;
+ MercuryBitmap bitmap;
if (this.is_latest()) {
return;
}
/*
- ** Copy elements in the reverse order that they were updated into the
- ** latest array, then return the latest array.
+ ** Rewind elements from the oldest to the newest, undoing their changes.
+ ** So that we undo elements in the correct order we use a bitmap to
+ ** ensure that we never update an array slot twice.
*/
- cur = latest();
- /* start from first 'update' record */
- cur = null != cur.prev ? cur.prev.get() : null;
- while (cur != this) {
+ cur = this;
+ bitmap = new MercuryBitmap(cur.size());
+ while (!cur.is_latest()) {
I = cur.index;
X = cur.value;
- if (I < VA.size()) {
+ if (I < VA.size() && !bitmap.getBit(I)) {
VA.array()[I] = X;
+ bitmap.setBit(I);
}
- cur = null != cur.prev ? cur.prev.get() : null;
+ cur = cur.next();
}
-
- /*
- * This loop must be inclusive of the update in VA.
- */
- I = cur.index;
- X = cur.value;
-
- VA.array()[I] = X;
}
public ML_uva rewind()
{
- ML_uva VA = this;
- int I;
- Object X;
- ML_uva cur;
- ML_uva last_visited;
-
- if (VA.is_latest()) {
- return VA;
+ int I;
+ Object X;
+ ML_uva cur;
+ MercuryBitmap bitmap;
+ Object[] array;
+
+ if (is_latest()) {
+ return this;
}
/*
- ** last_visited is the last element we interated through, we remember it
- ** because we update it's prev pointer after the loop. This isn't
- ** strictly required as we're already destroying that list.
- */
- last_visited = null;
-
- /*
- ** Copy elements in the reverse order that they were updated into the
- ** latest array, then return the latest array.
+ ** Rewind elements from the oldest to the newest, undoing their changes.
+ ** So that we undo elements in the correct order we use a bitmap to
+ ** ensure that we never update an array slot twice.
*/
- cur = VA.latest();
- VA.rest = cur.array();
- /* start from first 'update' record */
- cur = null != cur.prev ? cur.prev.get() : null;
- while (cur != VA) {
+ cur = this;
+ array = latest().array();
+ bitmap = new MercuryBitmap(array.length);
+ while (!cur.is_latest()) {
I = cur.index;
X = cur.value;
- VA.array()[I] = X;
-
- last_visited = cur;
- cur = null != cur.prev ? cur.prev.get() : null;
- }
- /*
- * This loop must be inclusive of the update in VA.
- */
- I = cur.index;
- X = cur.value;
-
- VA.array()[I] = X;
+ if (!bitmap.getBit(I)) {
+ array[I] = X;
+ bitmap.setBit(I);
+ }
- /*
- * Clear the prev pointer since we've broken the chain.
- */
- if (null != last_visited) {
- last_visited.prev = null;
+ cur = cur.next();
}
+ rest = array;
/*
* This element is no-longer an update element.
*/
- VA.index = -1;
- VA.value = 0;
- return VA;
+ index = -1;
+ value = 0;
+ return this;
}
}
diff --git a/runtime/mercury_bitmap.h b/runtime/mercury_bitmap.h
index 64427eb..94f5240 100644
--- a/runtime/mercury_bitmap.h
+++ b/runtime/mercury_bitmap.h
@@ -159,9 +159,42 @@ MR_String MR_bitmap_to_quoted_string_saved_hp(MR_ConstBitmapPtr,
#define MR_bitmap_length_in_bytes(bits) \
(((bits) / MR_BITS_PER_BYTE) + (((bits) % MR_BITS_PER_BYTE) != 0))
+#define MR_bitmap_byte_index_for_bit(bit) \
+ ((bit) / MR_BITS_PER_BYTE)
+#define MR_bitmap_bit_index_within_byte(bit) \
+ ((bit) % MR_BITS_PER_BYTE)
+
+#define MR_bitmap_zero(bitmap) \
+ do { \
+ size_t bytes = MR_bitmap_length_in_bytes((bitmap)->num_bits); \
+ memset((bitmap)->elements, 0, bytes); \
+ } while(0);
+
+#define MR_bitmap_get(bitmap, bit) \
+ (!!(((bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)]) & \
+ (1 << MR_bitmap_bit_index_within_byte(bit))))
+
+#define MR_bitmap_set(bitmap, bit) \
+ do { \
+ MR_uint_least8_t byte; \
+ \
+ byte = (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)]; \
+ byte |= 1 << MR_bitmap_bit_index_within_byte(bit); \
+ (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)] = byte; \
+ } while (0);
+
+#define MR_bitmap_clear(bitmap, bit) \
+ do { \
+ MR_uint_least8_t byte; \
+ \
+ byte = (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)]; \
+ byte &= ~(1 << MR_bitmap_bit_index_within_byte(bit)); \
+ (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)] = byte; \
+ } while (0);
+
/*
-** void MR_allocate_bitmap_msg(MR_String ptr, size_t bytes,
-** int bits_in_last_byte, MR_Code *proclabel):
+** void MR_allocate_bitmap_msg(MR_BitmapPtr ptr, size_t bits,
+** MR_Code *proclabel):
** Allocate enough word aligned memory to hold `bytes' bytes. Also
** record for memory profiling purposes the location, proclabel, of the
** allocation if profiling is enabled.
diff --git a/tests/hard_coded/version_array_test.exp b/tests/hard_coded/version_array_test.exp
index 2a7172d..5dbe9b6 100644
--- a/tests/hard_coded/version_array_test.exp
+++ b/tests/hard_coded/version_array_test.exp
@@ -2,17 +2,18 @@ ordering(A1, A0) = '>'
ordering(A0, A1) = '<'
ordering(A1, A2) = '<'
ordering(A2, A1) = '>'
- (size 0)
-0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (size 10)
-9, 8, 7, 6, 5, 4, 3, 2, 1, 0 (size 10)
-0, 1, 6, 3, 12, 5, 18, 7, 24, 9 (size 10)
-0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (size 10)
-7, 7, 7, 7, 7, 7, 7 (size 7)
+A0: [] (size 0)
+A1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] (size 21)
+A2: [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] (size 21)
+A22: [20, 19, 18, 17, 16, 555, 666, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] (size 21)
+A21: [0, 1, 6, 3, 12, 5, 18, 7, 24, 9, 30, 11, 36, 13, 42, 15, 48, 17, 54, 19, 60] (size 21)
+A3: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] (size 21)
+A4: [7, 7, 7, 7, 7, 7, 7] (size 7)
(sum 49)
-7, 7, 7, 7 (size 4)
-7, 7, 7, 7, 9, 9, 9, 9, 9 (size 9)
+A5: [7, 7, 7, 7] (size 4)
+A6: [7, 7, 7, 7, 9, 9, 9, 9, 9] (size 9)
(sum 73)
-7, 7, 7, 7 (size 4)
+A7: [7, 7, 7, 7] (size 4)
Found exception as expected: index_out_of_bounds("version_array.lookup: index -1 not in range [0, 3]")
Found exception as expected: index_out_of_bounds("version_array.set: index -1 not in range [0, 3]")
Found exception as expected: index_out_of_bounds("version_array.set: index -1 not in range [0, 3]")
diff --git a/tests/hard_coded/version_array_test.m b/tests/hard_coded/version_array_test.m
index d45c324..dcbe26f 100644
--- a/tests/hard_coded/version_array_test.m
+++ b/tests/hard_coded/version_array_test.m
@@ -25,10 +25,17 @@
main(!IO) :-
A0 = version_array.empty,
- A1 = version_array(0`..`9),
- A2 = int.fold_up(func(I, A) = ( A ^ elem(I) := 9 - I ), 0, 9, A1),
+ A1 = version_array(0`..`20),
+ % These two updates are overwritten but they're here to help test that
+ % the rollback rolls back to the correct version, that is that changes
+ % are applied in the correct order.
+ version_array.set(3, 333, A1, A10),
+ version_array.set(4, 444, A10, A11),
+ A2 = int.fold_up(func(I, A) = ( A ^ elem(I) := 20 - I ), 0, 20, A11),
+ version_array.set(5, 555, A2, A20),
+ version_array.set(6, 666, A20, A22),
% A21 forces an implicit rollback:
- A21 = int.fold_up(make_a21, 0, 9, A1),
+ A21 = int.fold_up(make_a21, 0, 20, A1),
io.write_string("ordering(A1, A0) = ", !IO),
io.write(ordering(A1, A0), !IO),
io.nl(!IO),
@@ -41,33 +48,25 @@ main(!IO) :-
io.write_string("ordering(A2, A1) = ", !IO),
io.write(ordering(A2, A1), !IO),
io.nl(!IO),
- io.write_list(to_list(A0), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A0))], !IO),
- io.write_list(to_list(A1), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A1))], !IO),
- io.write_list(to_list(A2), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A2))], !IO),
- io.write_list(to_list(A21), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A21))], !IO),
+ write_array("A0", A0, !IO),
+ write_array("A1", A1, !IO),
+ write_array("A2", A2, !IO),
+ write_array("A22", A22, !IO),
+ write_array("A21", A21, !IO),
A3 = unsafe_rewind(A1),
- io.write_list(to_list(A3), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A3))], !IO),
+ write_array("A3", A3, !IO),
A4 = version_array.init(7, 7),
- io.write_list(to_list(A4), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A4))], !IO),
+ write_array("A4", A4, !IO),
S4 = foldl(func(X, A) = X + A, A4, 0),
io.format(" (sum %d)\n", [i(S4)], !IO),
A5 = resize(A4, 4, 4),
- io.write_list(to_list(A5), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A5))], !IO),
+ write_array("A5", A5, !IO),
A6 = resize(A5, 9, 9),
- io.write_list(to_list(A6), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A6))], !IO),
+ write_array("A6", A6, !IO),
S6 = foldl(func(X, A) = X + A, A6, 0),
io.format(" (sum %d)\n", [i(S6)], !IO),
A7 = copy(A5),
- io.write_list(to_list(A7), ", ", io.write_int, !IO),
- io.format(" (size %d)\n", [i(size(A7))], !IO),
+ write_array("A7", A7, !IO),
test_exception(
((pred) is semidet :-
@@ -158,5 +157,12 @@ make_a21(I, A0) = A :-
A = A0
).
+:- pred write_array(string::in, version_array(int)::in, io::di, io::uo) is det.
+
+write_array(Name, Array, !IO) :-
+ Size = size(Array),
+ ArrayStr = string(to_list(Array)),
+ io.format("%s: %s (size %d)\n", [s(Name), s(ArrayStr), i(Size)], !IO).
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
--
2.0.0
More information about the reviews
mailing list