1  /** @file


2  * IPRT / NoCRT  Minimal C++ std::vector.


3  */


4 


5  /*


6  * Copyright (C) 2023 Oracle and/or its affiliates.


7  *


8  * This file is part of VirtualBox base platform packages, as


9  * available from https://www.virtualbox.org.


10  *


11  * This program is free software; you can redistribute it and/or


12  * modify it under the terms of the GNU General Public License


13  * as published by the Free Software Foundation, in version 3 of the


14  * License.


15  *


16  * This program is distributed in the hope that it will be useful, but


17  * WITHOUT ANY WARRANTY; without even the implied warranty of


18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU


19  * General Public License for more details.


20  *


21  * You should have received a copy of the GNU General Public License


22  * along with this program; if not, see <https://www.gnu.org/licenses>.


23  *


24  * The contents of this file may alternatively be used under the terms


25  * of the Common Development and Distribution License Version 1.0


26  * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included


27  * in the VirtualBox distribution, in which case the provisions of the


28  * CDDL are applicable instead of those of the GPL.


29  *


30  * You may elect to license modified versions of this file under the


31  * terms and conditions of either the GPL or the CDDL or both.


32  *


33  * SPDXLicenseIdentifier: GPL3.0only OR CDDL1.0


34  */


35 


36  #ifndef VBOX_INCLUDED_SRC_nocrt_vector


37  #define VBOX_INCLUDED_SRC_nocrt_vector


38  #ifndef RT_WITHOUT_PRAGMA_ONCE


39  # pragma once


40  #endif


41 


42  #include <iprt/nocrt/memory>


43 


44  namespace std


45  {


46  template<typename a_Type, class a_Container>


47  class RTCNoCrtVectorIterator


48  {


49  public:


50  typedef a_Type &reference;


51  typedef a_Type *pointer;


52  typedef typename a_Container::difference_type difference_type;


53 


54  protected:


55  a_Type *m_pItem;


56 


57  public:


58  RTCNoCrtVectorIterator() RT_NOEXCEPT


59  : m_pItem(NULL)


60  { }


61 


62  RTCNoCrtVectorIterator(a_Type *a_pItem) RT_NOEXCEPT


63  : m_pItem(a_pItem)


64  { }


65 


66  ~RTCNoCrtVectorIterator()


67  {


68  m_pItem = NULL;


69  }


70 


71  /** @name Moving the iterator.


72  * @{ */


73 


74  RTCNoCrtVectorIterator &operator++() RT_NOEXCEPT


75  {


76  ++m_pItem;


77  return *this;


78  }


79 


80  RTCNoCrtVectorIterator &operator() RT_NOEXCEPT


81  {


82  m_pItem;


83  return *this;


84  }


85 


86  RTCNoCrtVectorIterator operator++(int) RT_NOEXCEPT


87  {


88  return RTCNoCrtVectorIterator(m_pItem++);


89  }


90 


91  RTCNoCrtVectorIterator operator(int) RT_NOEXCEPT


92  {


93  return RTCNoCrtVectorIterator(m_pItem);


94  }


95 


96  RTCNoCrtVectorIterator &operator+=(difference_type cItems) RT_NOEXCEPT


97  {


98  m_pItem += cItems;


99  return *this;


100  }


101 


102  RTCNoCrtVectorIterator &operator=(difference_type cItems) RT_NOEXCEPT


103  {


104  m_pItem = cItems;


105  return *this;


106  }


107 


108  RTCNoCrtVectorIterator operator+(difference_type cItems) const RT_NOEXCEPT


109  {


110  return RTCNoCrtVectorIterator(m_pItem + cItems);


111  }


112 


113  RTCNoCrtVectorIterator operator(difference_type cItems) const RT_NOEXCEPT


114  {


115  return RTCNoCrtVectorIterator(m_pItem  cItems);


116  }


117 


118  /** @} */


119 


120  /** @name Item access


121  * @{ */


122  reference operator*() const RT_NOEXCEPT


123  {


124  return *m_pItem;


125  }


126 


127  pointer operator>() const RT_NOEXCEPT


128  {


129  return m_pItem;


130  }


131 


132  reference operator[](difference_type iItem) const RT_NOEXCEPT


133  {


134  return m_pItem[iItem];


135  }


136 


137  /** @} */


138 


139  /** Helper for const/nonconst iterator comparisons: */


140  inline typename a_Container::const_pointer getConst() const RT_NOEXCEPT


141  {


142  return m_pItem;


143  }


144  };


145 


146  template<typename a_TypeLeft, typename a_TypeRight, class a_Container>


147  inline bool operator==(const RTCNoCrtVectorIterator<a_TypeLeft, a_Container> &a_rLeft,


148  const RTCNoCrtVectorIterator<a_TypeRight, a_Container> &a_rRight) RT_NOEXCEPT


149  {


150  return a_rLeft.getConst() == a_rRight.getConst();


151  }


152 


153  template<typename a_TypeLeft, typename a_TypeRight, class a_Container>


154  inline bool operator!=(const RTCNoCrtVectorIterator<a_TypeLeft, a_Container> &a_rLeft,


155  const RTCNoCrtVectorIterator<a_TypeRight, a_Container> &a_rRight) RT_NOEXCEPT


156  {


157  return a_rLeft.getConst() != a_rRight.getConst();


158  }


159 


160  template<typename a_TypeLeft, typename a_TypeRight, class a_Container>


161  inline bool operator<(const RTCNoCrtVectorIterator<a_TypeLeft, a_Container> &a_rLeft,


162  const RTCNoCrtVectorIterator<a_TypeRight, a_Container> &a_rRight) RT_NOEXCEPT


163  {


164  return (uintptr_t)a_rLeft.getConst() < (uintptr_t)a_rRight.getConst();


165  }


166 


167  template<typename a_TypeLeft, typename a_TypeRight, class a_Container>


168  inline bool operator<=(const RTCNoCrtVectorIterator<a_TypeLeft, a_Container> &a_rLeft,


169  const RTCNoCrtVectorIterator<a_TypeRight, a_Container> &a_rRight) RT_NOEXCEPT


170  {


171  return (uintptr_t)a_rLeft.getConst() <= (uintptr_t)a_rRight.getConst();


172  }


173 


174  template<typename a_TypeLeft, typename a_TypeRight, class a_Container>


175  inline bool operator>(const RTCNoCrtVectorIterator<a_TypeLeft, a_Container> &a_rLeft,


176  const RTCNoCrtVectorIterator<a_TypeRight, a_Container> &a_rRight) RT_NOEXCEPT


177  {


178  return (uintptr_t)a_rLeft.getConst() > (uintptr_t)a_rRight.getConst();


179  }


180 


181  template<typename a_TypeLeft, typename a_TypeRight, class a_Container>


182  inline bool operator>=(const RTCNoCrtVectorIterator<a_TypeLeft, a_Container> &a_rLeft,


183  const RTCNoCrtVectorIterator<a_TypeRight, a_Container> &a_rRight) RT_NOEXCEPT


184  {


185  return (uintptr_t)a_rLeft.getConst() >= (uintptr_t)a_rRight.getConst();


186  }


187 


188 


189 


190  template<class a_Type, class a_Allocator = std::allocator<a_Type> >


191  class vector


192  {


193  public:


194  typedef a_Type value_type;


195  typedef a_Type &reference;


196  typedef a_Type const &const_reference;


197  typedef a_Allocator allocator_type;


198  typedef typename a_Allocator::size_type size_type;


199  typedef typename a_Allocator::difference_type difference_type;


200  typedef typename a_Allocator::pointer pointer;


201  typedef typename a_Allocator::const_pointer const_pointer;


202 


203  typedef RTCNoCrtVectorIterator<a_Type, vector> iterator;


204  typedef RTCNoCrtVectorIterator<const a_Type, vector> const_iterator;


205 


206  protected:


207  pointer m_paItems;


208  size_t m_cItems;


209  size_t m_cAllocated;


210  allocator_type m_Allocator;


211 


212  public:


213  vector() RT_NOEXCEPT


214  : m_paItems(NULL)


215  , m_cItems(0)


216  , m_cAllocated(0)


217  { }


218 


219  vector(size_type a_cAllocate)


220  : m_paItems(NULL)


221  , m_cItems(0)


222  , m_cAllocated(0)


223  {


224  m_paItems = m_Allocator.allocate(a_cAllocate);


225  if (m_paItems)


226  m_cAllocated = a_cAllocate;


227  }


228 


229  ~vector()


230  {


231  clear();


232  }


233 


234  /** @name Iterators


235  * @{ */


236  iterator begin() RT_NOEXCEPT


237  {


238  return iterator(m_paItems);


239  }


240 


241  const_iterator begin() const RT_NOEXCEPT


242  {


243  return const_iterator(m_paItems);


244  }


245 


246  const_iterator cbegin() const RT_NOEXCEPT


247  {


248  return const_iterator(m_paItems);


249  }


250 


251  iterator end() RT_NOEXCEPT


252  {


253  return iterator(m_paItems + m_cItems);


254  }


255 


256  const_iterator end() const RT_NOEXCEPT


257  {


258  return const_iterator(m_paItems + m_cItems);


259  }


260 


261  const_iterator cend() const RT_NOEXCEPT


262  {


263  return const_iterator(m_paItems + m_cItems);


264  }


265  /** @} */


266 


267  /** @name Element access


268  * @{ */


269  reference operator[](size_type iItem) RT_NOEXCEPT


270  {


271  Assert(iItem < m_cAllocated);


272  return m_paItems[iItem];


273  }


274 


275  const_reference operator[](size_type iItem) const RT_NOEXCEPT


276  {


277  Assert(iItem < m_cAllocated);


278  return m_paItems[iItem];


279  }


280 


281  reference at(size_type iItem) RT_NOEXCEPT


282  {


283  Assert(iItem < m_cAllocated);


284  return m_paItems[iItem];


285  }


286 


287  const_reference at(size_type iItem) const RT_NOEXCEPT


288  {


289  Assert(iItem < m_cAllocated);


290  return m_paItems[iItem];


291  }


292 


293  reference front() RT_NOEXCEPT


294  {


295  return m_paItems[0];


296  }


297 


298  const_reference front() const RT_NOEXCEPT


299  {


300  return m_paItems[0];


301  }


302 


303  reference back() RT_NOEXCEPT


304  {


305  return m_paItems[m_cItems  1];


306  }


307 


308  const_reference back() const RT_NOEXCEPT


309  {


310  return m_paItems[m_cItems  1];


311  }


312 


313  pointer data() RT_NOEXCEPT


314  {


315  return m_paItems;


316  }


317 


318  const_pointer data() const RT_NOEXCEPT


319  {


320  return m_paItems;


321  }


322 


323  /** @} */


324 


325  /** @name Capacity


326  * @{ */


327  bool empty() const RT_NOEXCEPT


328  {


329  return m_cItems == 0;


330  }


331 


332  size_type size() const RT_NOEXCEPT


333  {


334  return m_cItems;


335  }


336 


337  size_type max_size() const RT_NOEXCEPT


338  {


339  return m_Allocator.max_size();


340  }


341 


342  void reserve(size_type a_cNewAllocated)


343  {


344  Assert(a_cNewAllocated <= max_size());


345 


346  if (a_cNewAllocated > m_cAllocated)


347  {


348  vector Temp(a_cNewAllocated);


349  if (Temp.m_paItems)


350  {


351  /* Copy over the data: */


352  size_type const cItems = m_cItems;


353  const_pointer paSrc = m_paItems;


354  pointer paDst = Temp.m_paItems;


355  for (size_type i = 0; i < cItems; Temp.m_cItems = ++i)


356  m_Allocator.construct(&paDst[i], paSrc[i]);


357 


358  /* Swap the data. */


359  size_type const cOldAllocated = m_cAllocated;


360  Temp.m_paItems = m_paItems;


361  m_paItems = paDst;


362  m_cAllocated = Temp.m_cAllocated;


363  Temp.m_cAllocated = cOldAllocated;


364  }


365  }


366  }


367 


368  /** @} */


369 


370  /** @name Modifiers


371  * @{ */


372  void push_back(const_reference a_rValue)


373  {


374  if (m_cItems < m_cAllocated)


375  { }


376  else


377  {


378  Assert(m_cItems * 2 >= m_cItems);


379  reserve(m_cItems < 8 ? 8 : m_cItems * 2); /* This might be nonstandard. */


380  AssertReturnVoid(m_cItems < m_cAllocated);


381  }


382  m_paItems[m_cItems] = a_rValue;


383  m_cItems++;


384  }


385 


386  void pop_back() RT_NOEXCEPT


387  {


388  if (m_cItems > 0)


389  m_cItems = 1;


390  }


391 


392  void clear() RT_NOEXCEPT


393  {


394  size_type i = m_cItems;


395  while (i > 0)


396  {


397  m_Allocator.destroy(&m_paItems[i]);


398  m_cItems = i;


399  }


400  m_Allocator.deallocate(m_paItems, m_cAllocated);


401  m_paItems = NULL;


402  m_cAllocated = 0;


403  }


404  /** @} */


405  };


406 


407  }


408 


409  #endif /* !VBOX_INCLUDED_SRC_nocrt_vector */


410 

