src/rt/util/indexed_list.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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 */