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