2 files changed, 126 insertions, 0 deletions
diff --git a/src/rt/util/indexed_list.h b/src/rt/util/indexed_list.h
new file mode 100644
index 00000000..d869d43e
--- /dev/null
+++ b/src/rt/util/indexed_list.h
@@ -0,0 +1,70 @@
+#ifndef INDEXED_LIST_H
+#define INDEXED_LIST_H
+
+#include <assert.h>
+#include "array_list.h"
+#include "../memory_region.h"
+
+class indexed_list_object {
+public:
+    int32_t list_index;
+};
+
+/**
+ * An array list of objects that are aware of their position in the list.
+ * Normally, objects in this list should derive from the base class
+ * "indexed_list_object" however because of nasty Rust compiler dependencies
+ * on the layout of runtime objects we cannot always derive from this
+ * base class, so instead we just enforce the informal protocol that any
+ * object inserted in this list must define a "int32_t list_index" member.
+ */
+template<typename T> class indexed_list {
+    memory_region &region;
+    array_list<T*> list;
+public:
+    indexed_list(memory_region &region) : region(region) {}
+    virtual int32_t append(T *value);
+    virtual size_t length() {
+        return list.size();
+    }
+    virtual bool is_empty() {
+        return list.is_empty();
+    }
+    virtual int32_t remove(T* value);
+    virtual T * operator[](int32_t index);
+};
+
+template<typename T> int32_t
+indexed_list<T>::append(T *value) {
+    value->list_index = list.push(value);
+    return value->list_index;
+}
+
+/**
+ * Swap delete the last object in the list with the specified object.
+ */
+template<typename T> int32_t
+indexed_list<T>::remove(T *value) {
+    assert (value->list_index >= 0);
+    assert (value->list_index < (int32_t)list.size());
+    int32_t removeIndex = value->list_index;
+    T *last = list.pop();
+    if (last->list_index == removeIndex) {
+        last->list_index = -1;
+        return removeIndex;
+    } else {
+        value->list_index = -1;
+        list[removeIndex] = last;
+        last->list_index = removeIndex;
+        return removeIndex;
+    }
+}
+
+template <typename T> T *
+indexed_list<T>::operator[](int32_t index) {
+    T *value = list[index];
+    assert(value->list_index == index);
+    return value;
+}
+
+#endif /* INDEXED_LIST_H */
diff --git a/src/rt/util/synchronized_indexed_list.h b/src/rt/util/synchronized_indexed_list.h
new file mode 100644
index 00000000..ca02f6ef
--- /dev/null
+++ b/src/rt/util/synchronized_indexed_list.h
@@ -0,0 +1,56 @@
+#ifndef SYNCHRONIZED_INDEXED_LIST_H
+#define SYNCHRONIZED_INDEXED_LIST_H
+
+#include "indexed_list.h"
+
+template<typename T> class synchronized_indexed_list :
+    public indexed_list<T> {
+    spin_lock _lock;
+public:
+    synchronized_indexed_list(memory_region &region) :
+        indexed_list<T>(region) {
+        // Nop.
+    }
+
+    int32_t append(T *value) {
+        int32_t index = 0;
+        _lock.lock();
+        index = indexed_list<T>::append(value);
+        _lock.unlock();
+        return index;
+    }
+
+    size_t length() {
+       size_t length = 0;
+       _lock.lock();
+       length = indexed_list<T>::length();
+       _lock.unlock();
+       return length;
+    }
+
+    bool is_empty() {
+        bool empty = false;
+        _lock.lock();
+        empty = indexed_list<T>::is_empty();
+        _lock.unlock();
+        return empty;
+    }
+
+    int32_t remove(T* value) {
+        size_t index = 0;
+        _lock.lock();
+        index = indexed_list<T>::remove(value);
+        _lock.unlock();
+        return index;
+    }
+
+    T *operator[](size_t index) {
+        T *value = NULL;
+        _lock.lock();
+        value = indexed_list<T>::operator[](index);
+        _lock.unlock();
+        return value;
+    }
+};
+
+#endif /* SYNCHRONIZED_INDEXED_LIST_H */