hphp/util/slice.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 Facebook, Inc. (http://www.facebook.com)     |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #ifndef incl_HPHP_UTIL_SLICE_H_
  17 #define incl_HPHP_UTIL_SLICE_H_
  18
  19 #include <cinttypes>
  20 #include <assert.h>
  21
  22 namespace HPHP {
  23
  24 //////////////////////////////////////////////////////////////////////
  25
  26 /*
  27  * A Slice is a compact way to refer to an extent of array elements.
  28  * For hhvm, it's generally string slices.
  29  *
  30  * This type is designed to be passed around by value.  Methods on
  31  * slice are set up to match the Boost RandomAccessRange concept.  If
  32  * T is not const-qualified, it also models WriteableRange.
  33  */
  34 template<class T>
  35 struct Slice {
  36   typedef T* iterator;
  37   typedef T* const_iterator;
  38   typedef uint32_t size_type;
  39
  40   Slice(T* ptr, size_type len) : ptr(ptr), len(len) {}
  41
  42   const_iterator begin() const { return ptr; }
  43   const_iterator end() const { return ptr + len; }
  44   const_iterator cbegin() const { return ptr; }
  45   const_iterator cend() const { return ptr + len; }
  46   iterator begin() { return ptr; }
  47   iterator end() { return ptr + len; }
  48   size_type size() const { return len; }
  49   T& operator[](size_type i);
  50   const T& operator[](size_type i) const;
  51   iterator erase(iterator it);
  52   bool empty() const { return len == 0; }
  53   void clear() { len = 0; }
  54
  55 public:
  56   T* ptr;         // pointer to bytes, not necessarily \0 teriminated
  57   size_type len;  // number of bytes, not counting possible \0
  58 };
  59
  60 typedef Slice<const char> StringSlice;
  61 typedef Slice<char> MutableSlice;
  62
  63 /*
  64  * List extends Slice, with a capacity field, making it growable.
  65  * sizeof(List) == sizeof(Slice) so it should still pass by value in registers.
  66  */
  67 template<class T>
  68 struct List : Slice<T> {
  69   typedef typename Slice<T>::size_type size_type;
  70
  71   List(T* ptr, size_type len, size_type cap)
  72     : Slice<T>(ptr, len), cap(cap) {
  73     assert(len <= cap);
  74     static_assert(sizeof(List<T>) == sizeof(Slice<T>), "");
  75   }
  76
  77   // vector-like api
  78   size_type capacity() const { return cap; }
  79   void push_back(const T& value);
  80
  81 public:
  82   size_type cap;
  83 };
  84
  85 template<class T>
  86 T& Slice<T>::operator[](size_type i) {
  87   assert(i < len);
  88   return ptr[i];
  89 }
  90
  91 template<class T>
  92 const T& Slice<T>::operator[](size_type i) const {
  93   assert(i < len);
  94   return ptr[i];
  95 }
  96
  97 template<class T>
  98 typename Slice<T>::iterator Slice<T>::erase(iterator it) {
  99   assert(it >= begin() && it < end());
 100   auto last = ptr + len - 1;
 101   for (auto p = it; p < last; ++p) p[0] = p[1];
 102   len--;
 103   return it;
 104 }
 105
 106 template<class T>
 107 void List<T>::push_back(const T& value) {
 108   assert(this->len < this->cap); // caller must have reserved space.
 109   this->ptr[this->len++] = value;
 110 }
 111
 112 //////////////////////////////////////////////////////////////////////
 113
 114 }
 115
 116 #endif