src/mem_list.hpp


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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

/*
 * Copyright (c) 2015 Andrew Kelley
 *
 * This file is part of zig, which is MIT licensed.
 * See http://opensource.org/licenses/MIT
 */

#ifndef ZIG_MEM_LIST_HPP
#define ZIG_MEM_LIST_HPP

#include "mem.hpp"

namespace mem {

template<typename T>
struct List {
    void deinit(Allocator *allocator) {
        allocator->deallocate<T>(items, capacity);
        items = nullptr;
        length = 0;
        capacity = 0;
    }

    void append(Allocator *allocator, const T& item) {
        ensure_capacity(allocator, length + 1);
        items[length++] = item;
    }

    // remember that the pointer to this item is invalid after you
    // modify the length of the list
    const T & at(size_t index) const {
        assert(index != SIZE_MAX);
        assert(index < length);
        return items[index];
    }

    T & at(size_t index) {
        assert(index != SIZE_MAX);
        assert(index < length);
        return items[index];
    }

    T pop() {
        assert(length >= 1);
        return items[--length];
    }

    T *add_one() {
        resize(length + 1);
        return &last();
    }

    const T & last() const {
        assert(length >= 1);
        return items[length - 1];
    }

    T & last() {
        assert(length >= 1);
        return items[length - 1];
    }

    void resize(Allocator *allocator, size_t new_length) {
        assert(new_length != SIZE_MAX);
        ensure_capacity(allocator, new_length);
        length = new_length;
    }

    void clear() {
        length = 0;
    }

    void ensure_capacity(Allocator *allocator, size_t new_capacity) {
        if (capacity >= new_capacity)
            return;

        size_t better_capacity = capacity;
        do {
            better_capacity = better_capacity * 5 / 2 + 8;
        } while (better_capacity < new_capacity);

        items = allocator->reallocate_nonzero<T>(items, capacity, better_capacity);
        capacity = better_capacity;
    }

    T swap_remove(size_t index) {
        if (length - 1 == index) return pop();

        assert(index != SIZE_MAX);
        assert(index < length);

        T old_item = items[index];
        items[index] = pop();
        return old_item;
    }

    T *items{nullptr};
    size_t length{0};
    size_t capacity{0};
};

} // namespace mem

#endif