summaryrefslogtreecommitdiff
path: root/klm/util/fixed_array.hh
blob: 416b92f4e7abfb3b83f1f0215157696e898014b0 (plain)
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#ifndef UTIL_FIXED_ARRAY_H
#define UTIL_FIXED_ARRAY_H

#include "util/scoped.hh"

#include <cstddef>

#include <assert.h>
#include <stdlib.h>

namespace util {

/**
 * Defines a fixed-size collection.
 *
 * Ever want an array of things by they don't have a default constructor or are
 * non-copyable?  FixedArray allows constructing one at a time.
 */
template <class T> class FixedArray {
  public:
    /** Initialize with a given size bound but do not construct the objects. */
    explicit FixedArray(std::size_t limit) {
      Init(limit);
    }

    /** 
     * Constructs an instance, but does not initialize it.
     *
     * Any objects constructed in this manner must be subsequently @ref FixedArray::Init() "initialized" prior to use.
     *
     * @see FixedArray::Init()
     */
    FixedArray() 
      : newed_end_(NULL) 
#ifndef NDEBUG
      , allocated_end_(NULL) 
#endif
    {}

    /** 
     * Initialize with a given size bound but do not construct the objects. 
     *
     * This method is responsible for allocating memory.
     * Objects stored in this array will be constructed in a location within this allocated memory.
     */
    void Init(std::size_t count) {
      assert(!block_.get());
      block_.reset(malloc(sizeof(T) * count));
      if (!block_.get()) throw std::bad_alloc();
      newed_end_ = begin();
#ifndef NDEBUG
      allocated_end_ = begin() + count;
#endif
    }

    /**
     * Constructs a copy of the provided array.
     *
     * @param from Array whose elements should be copied into this newly-constructed data structure.
     */
    FixedArray(const FixedArray &from) {
      std::size_t size = from.newed_end_ - static_cast<const T*>(from.block_.get());
      Init(size);
      for (std::size_t i = 0; i < size; ++i) {
        push_back(from[i]);
      }
    }

    /**
     * Frees the memory held by this object.
     */
    ~FixedArray() { clear(); }

    /** Gets a pointer to the first object currently stored in this data structure. */
    T *begin() { return static_cast<T*>(block_.get()); }
  
    /** Gets a const pointer to the last object currently stored in this data structure. */
    const T *begin() const { return static_cast<const T*>(block_.get()); }
    
    /** Gets a pointer to the last object currently stored in this data structure. */
    T *end() { return newed_end_; }
  
    /** Gets a const pointer to the last object currently stored in this data structure. */
    const T *end() const { return newed_end_; }

    /** Gets a reference to the last object currently stored in this data structure. */
    T &back() { return *(end() - 1); }
  
    /** Gets a const reference to the last object currently stored in this data structure. */
    const T &back() const { return *(end() - 1); }

    /** Gets the number of objects currently stored in this data structure. */
    std::size_t size() const { return end() - begin(); }
  
    /** Returns true if there are no objects currently stored in this data structure. */
    bool empty() const { return begin() == end(); }

    /** 
     * Gets a reference to the object with index i currently stored in this data structure. 
     *
     * @param i Index of the object to reference
     */
    T &operator[](std::size_t i) { return begin()[i]; }
  
    /** 
     * Gets a const reference to the object with index i currently stored in this data structure. 
     *
     * @param i Index of the object to reference
     */
    const T &operator[](std::size_t i) const { return begin()[i]; }

    /**
     * Constructs a new object using the provided parameter,
     * and stores it in this data structure.
     *
     * The memory backing the constructed object is managed by this data structure.
     */
    template <class C> void push_back(const C &c) {
      new (end()) T(c); // use "placement new" syntax to initalize T in an already-allocated memory location
      Constructed();
    }

    /**
     * Removes all elements from this array.
     */
    void clear() {
      for (T *i = begin(); i != end(); ++i)
        i->~T();
      newed_end_ = begin();
    }

  protected:
    // Always call Constructed after successful completion of new.
    void Constructed() {
      ++newed_end_;
#ifndef NDEBUG
      assert(newed_end_ <= allocated_end_);
#endif
    }

  private:
    util::scoped_malloc block_;

    T *newed_end_;

#ifndef NDEBUG
    T *allocated_end_;
#endif
};

} // namespace util

#endif // UTIL_FIXED_ARRAY_H