src/rt/util/array_list.h

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 #ifndef ARRAY_LIST_H
  12 #define ARRAY_LIST_H
  13
  14 #include <inttypes.h>
  15 #include <stddef.h>
  16 #include <new>
  17
  18 /**
  19  * A simple, resizable array list. Note that this only works with POD types
  20  * (because data is grown via realloc).
  21  */
  22 template<typename T> class array_list {
  23     static const size_t INITIAL_CAPACITY = 8;
  24     size_t _size;
  25     T * _data;
  26     size_t _capacity;
  27 private:
  28     // private and left undefined to disable copying
  29     array_list(const array_list& rhs);
  30     array_list& operator=(const array_list& rhs);
  31 public:
  32     array_list();
  33     ~array_list();
  34     size_t size() const;
  35     int32_t append(T value);
  36     int32_t push(T value);
  37     void pop(T *value);
  38     bool replace(T old_value, T new_value);
  39     int32_t index_of(T value) const;
  40     bool is_empty() const;
  41     T* data();
  42     const T* data() const;
  43     T & operator[](size_t index);
  44     const T & operator[](size_t index) const;
  45 };
  46
  47 template<typename T>
  48 array_list<T>::array_list() {
  49     _size = 0;
  50     _capacity = INITIAL_CAPACITY;
  51     _data = (T *) malloc(sizeof(T) * _capacity);
  52 }
  53
  54 template<typename T>
  55 array_list<T>::~array_list() {
  56     free(_data);
  57 }
  58
  59 template<typename T> size_t
  60 array_list<T>::size() const {
  61     return _size;
  62 }
  63
  64 template<typename T> int32_t
  65 array_list<T>::append(T value) {
  66     return push(value);
  67 }
  68
  69 template<typename T> int32_t
  70 array_list<T>::push(T value) {
  71     if (_size == _capacity) {
  72         size_t new_capacity = _capacity * 2;
  73         void* buffer = realloc(_data, new_capacity * sizeof(T));
  74         if (buffer == NULL) {
  75             fprintf(stderr,
  76                     "array_list::push> "
  77                     "Out of memory allocating %ld bytes",
  78                     (long int) (new_capacity * sizeof(T)));
  79             abort();
  80         }
  81         _data = (T *) buffer;
  82         _capacity = new_capacity;
  83     }
  84     _data[_size ++] = value;
  85     return _size - 1;
  86 }
  87
  88 template<typename T> void
  89 array_list<T>::pop(T *value) {
  90     assert(_size > 0);
  91     if (value != NULL) {
  92         *value = _data[-- _size];
  93     } else {
  94         -- _size;
  95     }
  96 }
  97
  98 /**
  99  * Replaces the old_value in the list with the new_value.
 100  * Returns the true if the replacement succeeded, or false otherwise.
 101  */
 102 template<typename T> bool
 103 array_list<T>::replace(T old_value, T new_value) {
 104     int index = index_of(old_value);
 105     if (index < 0) {
 106         return false;
 107     }
 108     _data[index] = new_value;
 109     return true;
 110 }
 111
 112 template<typename T> int32_t
 113 array_list<T>::index_of(T value) const {
 114     for (size_t i = 0; i < _size; i++) {
 115         if (_data[i] == value) {
 116             return i;
 117         }
 118     }
 119     return -1;
 120 }
 121
 122 template<typename T> T &
 123 array_list<T>::operator[](size_t index) {
 124     assert(index < size());
 125     return _data[index];
 126 }
 127
 128 template<typename T> const T &
 129 array_list<T>::operator[](size_t index) const {
 130     assert(index < size());
 131     return _data[index];
 132 }
 133
 134 template<typename T> bool
 135 array_list<T>::is_empty() const {
 136     return _size == 0;
 137 }
 138
 139 template<typename T> T*
 140 array_list<T>::data() {
 141     return _data;
 142 }
 143
 144 template<typename T> const T*
 145 array_list<T>::data() const {
 146     return _data;
 147 }
 148
 149 #endif /* ARRAY_LIST_H */