Vector.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef KERNEL_UTILITIES_VECTOR_H
#define KERNEL_UTILITIES_VECTOR_H
 
#include "pedigree/kernel/compiler.h"
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/utility.h"
 
template <class T>
class EXPORTED_PUBLIC Vector {
 public:
  typedef T* Iterator;
  typedef T const* ConstIterator;
  template <class T_>
  struct ReverseIteratorContainer {
    T_ value;
 
    ReverseIteratorContainer<T_>& operator++() {
      --value;
      return *this;
    }
    ReverseIteratorContainer<T_>& operator--() {
      ++value;
      return *this;
    }
 
    ReverseIteratorContainer<T_> operator++(int) {
      T_ origValue = value;
      --value;
      return ReverseIteratorContainer<T_>{.value = origValue};
    }
    ReverseIteratorContainer<T_> operator--(int) {
      T_ origValue = value;
      ++value;
      return ReverseIteratorContainer<T_>{.value = origValue};
    }
 
    operator T_() const {
      return value;
    }
 
    typename pedigree_std::remove_pointer<T_>::type operator*() const {
      return *value;
    }
 
    bool operator==(const ReverseIteratorContainer<T_>& other) {
      return value == other.value;
    }
  };
  typedef ReverseIteratorContainer<T*> ReverseIterator;
  typedef ReverseIteratorContainer<const T*> ConstReverseIterator;
 
  Vector();
  explicit Vector(size_t size);
  Vector(const Vector& x);
  ~Vector();
 
  Vector& operator=(const Vector& x);
  T& operator[](size_t index);
  const T& operator[](size_t index) const;
 
  size_t size() const;
  size_t count() const;
  void pushBack(const T& value);
  template <class... Args>
  void createBack(Args&&... args) {
    reserve(m_Count + 1, true);
 
    // If we've hit the end of the reserved space we can use, we need to move
    // the existing entries (rather than this happening in each reserve).
    if ((m_Start + m_Count + 1) > m_Size) {
      pedigree_std::copy(m_Data, m_Data + m_Start, m_Count);
      m_Start = 0;
    }
 
    m_Data[m_Start + m_Count++] = T(pedigree_std::forward<Args>(args)...);
  }
  void pushBack(T&& value);
  T popBack();
  void pushFront(const T& value);
  void pushFront(T&& value);
  T popFront();
  void setAt(size_t idx, const T& value);
  void swap(Iterator a, Iterator b);
  void swap(Vector& other) noexcept;
  void insert(size_t index, const T& value);
 
  void clear(bool freeMem = false);
  void erase(size_t index);
  Iterator erase(Iterator iter);
  ReverseIterator erase(ReverseIterator iter);
 
  Iterator begin() {
    return m_Data + m_Start;
  }
  ConstIterator begin() const {
    return m_Data + m_Start;
  }
  Iterator end() {
    return m_Data + m_Start + m_Count;
  }
  ConstIterator end() const {
    return m_Data + m_Start + m_Count;
  }
 
  ReverseIterator rbegin() {
    return ReverseIterator{.value = m_Data + m_Start + m_Count - 1};
  }
  ConstReverseIterator rbegin() const {
    return ConstReverseIterator{.value = m_Data + m_Start + m_Count - 1};
  }
  ReverseIterator rend() {
    return ReverseIterator{.value = m_Data + m_Start - 1};
  }
  ConstReverseIterator rend() const {
    return ConstReverseIterator{.value = m_Data + m_Start - 1};
  }
  void assign(const Vector& x);
  void reserve(size_t size, bool copy);
  bool tryReserve(size_t size, bool copy = true);
 
 private:
  void reserve(size_t size, bool copy, bool free);
  size_t m_Size;
  size_t m_Count;
  size_t m_Start;
  T* m_Data;
  static const int m_ReserveFactor = 2;
};
 
template <class T>
Vector<T>::Vector() : m_Size(0), m_Count(0), m_Start(0), m_Data(0) {}
 
template <class T>
Vector<T>::Vector(size_t size) : m_Size(0), m_Count(0), m_Start(0), m_Data(0) {
  reserve(size, false);
}
 
template <class T>
Vector<T>::Vector(const Vector& x) : m_Size(0), m_Count(0), m_Start(0), m_Data(0) {
  assign(x);
}
 
template <class T>
Vector<T>::~Vector() {
  if (m_Data != 0)
    delete[] m_Data;
}
 
template <class T>
Vector<T>& Vector<T>::operator=(const Vector& x) {
  assign(x);
  return *this;
}
 
template <class T>
T& Vector<T>::operator[](size_t index) {
  static T outofbounds = T();
  if (index >= m_Count)
    return outofbounds;
  return m_Data[m_Start + index];
}
 
template <class T>
const T& Vector<T>::operator[](size_t index) const {
  static const T outofbounds = T();
  if (index >= m_Count)
    return outofbounds;
  return m_Data[m_Start + index];
}
 
template <class T>
size_t Vector<T>::size() const {
  return m_Size;
}
 
template <class T>
size_t Vector<T>::count() const {
  return m_Count;
}
 
template <class T>
void Vector<T>::pushBack(const T& value) {
  reserve(m_Count + 1, true);
 
  // If we've hit the end of the reserved space we can use, we need to move
  // the existing entries (rather than this happening in each reserve).
  if ((m_Start + m_Count + 1) > m_Size) {
    pedigree_std::copy(m_Data, m_Data + m_Start, m_Count);
    m_Start = 0;
  }
 
  m_Data[m_Start + m_Count++] = value;
}
 
template <class T>
void Vector<T>::pushBack(T&& value) {
  reserve(m_Count + 1, true);
 
  // If we've hit the end of the reserved space we can use, we need to move
  // the existing entries (rather than this happening in each reserve).
  if ((m_Start + m_Count + 1) > m_Size) {
    pedigree_std::copy(m_Data, m_Data + m_Start, m_Count);
    m_Start = 0;
  }
 
  m_Data[m_Start + m_Count++] = pedigree_std::move(value);
}
 
template <class T>
T Vector<T>::popBack() {
  if (!m_Count) {
    return T();
  }
 
  m_Count--;
  return m_Data[m_Start + m_Count];
}
 
template <class T>
void Vector<T>::pushFront(const T& value) {
  const T* oldData = m_Data;
 
  reserve(m_Count + 1, true, false);
 
  if (m_Start && (m_Data == oldData)) {
    m_Start--;
    m_Data[m_Start] = value;
  } else {
    pedigree_std::copy(&m_Data[1], m_Data, m_Count);
    m_Data[0] = value;
  }
 
  m_Count++;
 
  // All finished with the previous buffer now.
  if (m_Data != oldData) {
    delete[] oldData;
  }
}
 
template <class T>
void Vector<T>::pushFront(T&& value) {
  const T* oldData = m_Data;
 
  reserve(m_Count + 1, true, false);
 
  if (m_Start && (m_Data == oldData)) {
    m_Start--;
    m_Data[m_Start] = pedigree_std::move(value);
  } else {
    pedigree_std::copy(&m_Data[1], m_Data, m_Count);
    m_Data[0] = pedigree_std::move(value);
  }
 
  m_Count++;
 
  // All finished with the previous buffer now.
  if (m_Data != oldData) {
    delete[] oldData;
  }
}
 
template <class T>
T Vector<T>::popFront() {
  if (!m_Count) {
    return T();
  }
 
  T ret = m_Data[m_Start];
  m_Count--;
  m_Start++;
  if (!m_Count) {
    m_Start = 0;
  }
  return ret;
}
 
template <class T>
void Vector<T>::setAt(size_t idx, const T& value) {
  if (idx < m_Count)
    m_Data[m_Start + idx] = value;
}
 
template <class T>
void Vector<T>::clear(bool freeMem) {
  m_Count = 0;
  m_Start = 0;
  if (freeMem) {
    m_Size = 0;
    delete[] m_Data;
    m_Data = 0;
  }
}
 
template <class T>
void Vector<T>::erase(size_t index) {
  if (!m_Count) {
    return;
  } else if (index >= m_Count) {
    return;
  }
 
  T* base = m_Data + m_Start;
  pedigree_std::copy(base + index, base + index + 1, m_Count - index - 1);
  m_Count--;
}
 
template <class T>
typename Vector<T>::Iterator Vector<T>::erase(Iterator iter) {
  erase(static_cast<size_t>(iter - begin()));
  return iter;
}
 
template <class T>
typename Vector<T>::ReverseIterator Vector<T>::erase(ReverseIterator iter) {
  erase(static_cast<size_t>(iter.value - (m_Data + m_Start)));
  return iter;
}
 
template <class T>
void Vector<T>::assign(const Vector& x) {
  if (this == &x) {
    return;
  }
 
  reserve(x.size(), false);
  pedigree_std::copy(m_Data, x.begin(), x.m_Count);
  m_Count = x.count();
  m_Start = 0;
}
 
template <class T>
bool Vector<T>::tryReserve(size_t size, bool copy) {
  if (size <= m_Size) {
    return true;
  }
  const size_t maximum = ~size_t{0} / sizeof(T);
  if (size > maximum) {
    return false;
  }
  if (m_Size <= maximum / m_ReserveFactor && size < m_Size * m_ReserveFactor) {
    size = m_Size * m_ReserveFactor;
  }
  T* replacement = new T[size];
  if (!replacement) {
    return false;
  }
  if (copy && m_Count) {
    pedigree_std::copy(replacement, m_Data + m_Start, m_Count);
  }
  T* old = m_Data;
  m_Data = replacement;
  m_Size = size;
  m_Start = 0;
  delete[] old;
  return true;
}
 
template <class T>
void Vector<T>::reserve(size_t size, bool copy) {
  reserve(size, copy, true);
}
 
template <class T>
void Vector<T>::reserve(size_t size, bool copy, bool free) {
  if (size <= m_Size) {
    return;
  } else if (size < (m_Size * m_ReserveFactor)) {
    // Grow exponentially.
    size = m_Size * m_ReserveFactor;
  }
 
  T* tmp = m_Data;
  m_Data = new T[size];
  if (tmp != 0) {
    if ((copy == true) && m_Count) {
      pedigree_std::copy(m_Data, tmp + m_Start, m_Count);
      m_Start = 0;
    }
    if (free) {
      delete[] tmp;
    }
  }
  m_Size = size;
}
 
template <class T>
void Vector<T>::swap(Iterator a, Iterator b) {
  if (a == b)
    return;
  else if (a < begin() || a >= end())
    return;
  else if (b < begin() || b >= end())
    return;
 
  // Perform the swap.
  T tmp = *a;
  *a = *b;
  *b = tmp;
}
 
template <class T>
void Vector<T>::insert(size_t index, const T& value) {
  if (index >= m_Count) {
    pushBack(value);
    return;
  } else if (index == 0) {
    pushFront(value);
    return;
  }
 
  reserve(m_Count + 1, true);
 
  pedigree_std::copy(m_Data + m_Start + index + 1, m_Data + m_Start + index, m_Count - index);
 
  m_Data[m_Start + index] = value;
  ++m_Count;
}
 
extern template class Vector<void*>;     // IWYU pragma: keep
extern template class Vector<uint64_t>;  // IWYU pragma: keep
extern template class Vector<uint32_t>;  // IWYU pragma: keep
extern template class Vector<uint16_t>;  // IWYU pragma: keep
extern template class Vector<uint8_t>;   // IWYU pragma: keep
extern template class Vector<int64_t>;   // IWYU pragma: keep
extern template class Vector<int32_t>;   // IWYU pragma: keep
extern template class Vector<int16_t>;   // IWYU pragma: keep
extern template class Vector<int8_t>;    // IWYU pragma: keep
 
template <class T>
void Vector<T>::swap(Vector& other) noexcept {
  const size_t size = m_Size, count = m_Count, start = m_Start;
  T* data = m_Data;
  m_Size = other.m_Size;
  m_Count = other.m_Count;
  m_Start = other.m_Start;
  m_Data = other.m_Data;
  other.m_Size = size;
  other.m_Count = count;
  other.m_Start = start;
  other.m_Data = data;
}
 
#endif