mfbt/ArrayUtils.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /*
   8  * Implements various helper functions related to arrays.
   9  */
  10
  11 #ifndef mozilla_ArrayUtils_h
  12 #define mozilla_ArrayUtils_h
  13
  14 #include "mozilla/Assertions.h"
  15 #include "mozilla/Attributes.h"
  16
  17 #include <algorithm>
  18 #include <stddef.h>
  19
  20 #ifdef __cplusplus
  21
  22 #  include "mozilla/Alignment.h"
  23 #  include "mozilla/Array.h"
  24 #  include "mozilla/EnumeratedArray.h"
  25 #  include "mozilla/TypeTraits.h"
  26
  27 namespace mozilla {
  28
  29 /*
  30  * Safely subtract two pointers when it is known that aEnd >= aBegin, yielding a
  31  * size_t result.
  32  *
  33  * Ordinary pointer subtraction yields a ptrdiff_t result, which, being signed,
  34  * has insufficient range to express the distance between pointers at opposite
  35  * ends of the address space. Furthermore, most compilers use ptrdiff_t to
  36  * represent the intermediate byte address distance, before dividing by
  37  * sizeof(T); if that intermediate result overflows, they'll produce results
  38  * with the wrong sign even when the correct scaled distance would fit in a
  39  * ptrdiff_t.
  40  */
  41 template <class T>
  42 MOZ_ALWAYS_INLINE size_t PointerRangeSize(T* aBegin, T* aEnd) {
  43   MOZ_ASSERT(aEnd >= aBegin);
  44   return (size_t(aEnd) - size_t(aBegin)) / sizeof(T);
  45 }
  46
  47 /*
  48  * Compute the length of an array with constant length.  (Use of this method
  49  * with a non-array pointer will not compile.)
  50  *
  51  * Beware of the implicit trailing '\0' when using this with string constants.
  52  */
  53 template <typename T, size_t N>
  54 constexpr size_t ArrayLength(T (&aArr)[N]) {
  55   return N;
  56 }
  57
  58 template <typename T, size_t N>
  59 constexpr size_t ArrayLength(const Array<T, N>& aArr) {
  60   return N;
  61 }
  62
  63 template <typename E, E N, typename T>
  64 constexpr size_t ArrayLength(const EnumeratedArray<E, N, T>& aArr) {
  65   return size_t(N);
  66 }
  67
  68 /*
  69  * Compute the address one past the last element of a constant-length array.
  70  *
  71  * Beware of the implicit trailing '\0' when using this with string constants.
  72  */
  73 template <typename T, size_t N>
  74 constexpr T* ArrayEnd(T (&aArr)[N]) {
  75   return aArr + ArrayLength(aArr);
  76 }
  77
  78 template <typename T, size_t N>
  79 constexpr T* ArrayEnd(Array<T, N>& aArr) {
  80   return &aArr[0] + ArrayLength(aArr);
  81 }
  82
  83 template <typename T, size_t N>
  84 constexpr const T* ArrayEnd(const Array<T, N>& aArr) {
  85   return &aArr[0] + ArrayLength(aArr);
  86 }
  87
  88 /**
  89  * std::equal has subpar ergonomics.
  90  */
  91
  92 template <typename T, typename U, size_t N>
  93 bool ArrayEqual(const T (&a)[N], const U (&b)[N]) {
  94   return std::equal(a, a + N, b);
  95 }
  96
  97 template <typename T, typename U>
  98 bool ArrayEqual(const T* const a, const U* const b, const size_t n) {
  99   return std::equal(a, a + n, b);
 100 }
 101
 102 namespace detail {
 103
 104 template <typename AlignType, typename Pointee,
 105           typename = EnableIf<!IsVoid<AlignType>::value>>
 106 struct AlignedChecker {
 107   static void test(const Pointee* aPtr) {
 108     MOZ_ASSERT((uintptr_t(aPtr) % MOZ_ALIGNOF(AlignType)) == 0,
 109                "performing a range-check with a misaligned pointer");
 110   }
 111 };
 112
 113 template <typename AlignType, typename Pointee>
 114 struct AlignedChecker<AlignType, Pointee> {
 115   static void test(const Pointee* aPtr) {}
 116 };
 117
 118 }  // namespace detail
 119
 120 /**
 121  * Determines whether |aPtr| points at an object in the range [aBegin, aEnd).
 122  *
 123  * |aPtr| must have the same alignment as |aBegin| and |aEnd|.  This usually
 124  * should be achieved by ensuring |aPtr| points at a |U|, not just that it
 125  * points at a |T|.
 126  *
 127  * It is a usage error for any argument to be misaligned.
 128  *
 129  * It's okay for T* to be void*, and if so U* may also be void*.  In the latter
 130  * case no argument is required to be aligned (obviously, as void* implies no
 131  * particular alignment).
 132  */
 133 template <typename T, typename U>
 134 inline typename EnableIf<IsSame<T, U>::value || std::is_base_of<T, U>::value ||
 135                              IsVoid<T>::value,
 136                          bool>::Type
 137 IsInRange(const T* aPtr, const U* aBegin, const U* aEnd) {
 138   MOZ_ASSERT(aBegin <= aEnd);
 139   detail::AlignedChecker<U, T>::test(aPtr);
 140   detail::AlignedChecker<U, U>::test(aBegin);
 141   detail::AlignedChecker<U, U>::test(aEnd);
 142   return aBegin <= reinterpret_cast<const U*>(aPtr) &&
 143          reinterpret_cast<const U*>(aPtr) < aEnd;
 144 }
 145
 146 /**
 147  * Convenience version of the above method when the valid range is specified as
 148  * uintptr_t values.  As above, |aPtr| must be aligned, and |aBegin| and |aEnd|
 149  * must be aligned with respect to |T|.
 150  */
 151 template <typename T>
 152 inline bool IsInRange(const T* aPtr, uintptr_t aBegin, uintptr_t aEnd) {
 153   return IsInRange(aPtr, reinterpret_cast<const T*>(aBegin),
 154                    reinterpret_cast<const T*>(aEnd));
 155 }
 156
 157 namespace detail {
 158
 159 /*
 160  * Helper for the MOZ_ARRAY_LENGTH() macro to make the length a typesafe
 161  * compile-time constant even on compilers lacking constexpr support.
 162  */
 163 template <typename T, size_t N>
 164 char (&ArrayLengthHelper(T (&array)[N]))[N];
 165
 166 } /* namespace detail */
 167
 168 } /* namespace mozilla */
 169
 170 #endif /* __cplusplus */
 171
 172 /*
 173  * MOZ_ARRAY_LENGTH() is an alternative to mozilla::ArrayLength() for C files
 174  * that can't use C++ template functions and for static_assert() calls that
 175  * can't call ArrayLength() when it is not a C++11 constexpr function.
 176  */
 177 #ifdef __cplusplus
 178 #  define MOZ_ARRAY_LENGTH(array) \
 179     sizeof(mozilla::detail::ArrayLengthHelper(array))
 180 #else
 181 #  define MOZ_ARRAY_LENGTH(array) (sizeof(array) / sizeof((array)[0]))
 182 #endif
 183
 184 #endif /* mozilla_ArrayUtils_h */