summaryrefslogtreecommitdiffstats
path: root/mfbt/ArrayUtils.h
blob: 0d55bb1f65466ea06167ca5a204f4fd8b206b1e9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * Implements various helper functions related to arrays.
 */

#ifndef mozilla_ArrayUtils_h
#define mozilla_ArrayUtils_h

#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"

#include <stddef.h>
#include <stdint.h>

#ifdef __cplusplus
#  include <algorithm>
#  include <type_traits>

#  include "mozilla/Alignment.h"

namespace mozilla {

template <typename T, size_t Length>
class Array;
template <typename IndexType, IndexType SizeAsEnumValue, typename ValueType>
class EnumeratedArray;

/*
 * Safely subtract two pointers when it is known that aEnd >= aBegin, yielding a
 * size_t result.
 *
 * Ordinary pointer subtraction yields a ptrdiff_t result, which, being signed,
 * has insufficient range to express the distance between pointers at opposite
 * ends of the address space. Furthermore, most compilers use ptrdiff_t to
 * represent the intermediate byte address distance, before dividing by
 * sizeof(T); if that intermediate result overflows, they'll produce results
 * with the wrong sign even when the correct scaled distance would fit in a
 * ptrdiff_t.
 */
template <class T>
MOZ_ALWAYS_INLINE size_t PointerRangeSize(T* aBegin, T* aEnd) {
  MOZ_ASSERT(aEnd >= aBegin);
  return (size_t(aEnd) - size_t(aBegin)) / sizeof(T);
}

/*
 * Compute the length of an array with constant length.  (Use of this method
 * with a non-array pointer will not compile.)
 *
 * Beware of the implicit trailing '\0' when using this with string constants.
 */
template <typename T, size_t N>
constexpr size_t ArrayLength(T (&aArr)[N]) {
  return N;
}

template <typename T, size_t N>
constexpr size_t ArrayLength(const Array<T, N>& aArr) {
  return N;
}

template <typename E, E N, typename T>
constexpr size_t ArrayLength(const EnumeratedArray<E, N, T>& aArr) {
  return size_t(N);
}

/*
 * Compute the address one past the last element of a constant-length array.
 *
 * Beware of the implicit trailing '\0' when using this with string constants.
 */
template <typename T, size_t N>
constexpr T* ArrayEnd(T (&aArr)[N]) {
  return aArr + ArrayLength(aArr);
}

template <typename T, size_t N>
constexpr T* ArrayEnd(Array<T, N>& aArr) {
  return &aArr[0] + ArrayLength(aArr);
}

template <typename T, size_t N>
constexpr const T* ArrayEnd(const Array<T, N>& aArr) {
  return &aArr[0] + ArrayLength(aArr);
}

/**
 * std::equal has subpar ergonomics.
 */

template <typename T, typename U, size_t N>
bool ArrayEqual(const T (&a)[N], const U (&b)[N]) {
  return std::equal(a, a + N, b);
}

template <typename T, typename U>
bool ArrayEqual(const T* const a, const U* const b, const size_t n) {
  return std::equal(a, a + n, b);
}

namespace detail {

template <typename AlignType, typename Pointee, typename = void>
struct AlignedChecker {
  static void test(const Pointee* aPtr) {
    MOZ_ASSERT((uintptr_t(aPtr) % MOZ_ALIGNOF(AlignType)) == 0,
               "performing a range-check with a misaligned pointer");
  }
};

template <typename AlignType, typename Pointee>
struct AlignedChecker<AlignType, Pointee,
                      std::enable_if_t<std::is_void_v<AlignType>>> {
  static void test(const Pointee* aPtr) {}
};

}  // namespace detail

/**
 * Determines whether |aPtr| points at an object in the range [aBegin, aEnd).
 *
 * |aPtr| must have the same alignment as |aBegin| and |aEnd|.  This usually
 * should be achieved by ensuring |aPtr| points at a |U|, not just that it
 * points at a |T|.
 *
 * It is a usage error for any argument to be misaligned.
 *
 * It's okay for T* to be void*, and if so U* may also be void*.  In the latter
 * case no argument is required to be aligned (obviously, as void* implies no
 * particular alignment).
 */
template <typename T, typename U>
inline std::enable_if_t<std::is_same_v<T, U> || std::is_base_of<T, U>::value ||
                            std::is_void_v<T>,
                        bool>
IsInRange(const T* aPtr, const U* aBegin, const U* aEnd) {
  MOZ_ASSERT(aBegin <= aEnd);
  detail::AlignedChecker<U, T>::test(aPtr);
  detail::AlignedChecker<U, U>::test(aBegin);
  detail::AlignedChecker<U, U>::test(aEnd);
  return aBegin <= reinterpret_cast<const U*>(aPtr) &&
         reinterpret_cast<const U*>(aPtr) < aEnd;
}

/**
 * Convenience version of the above method when the valid range is specified as
 * uintptr_t values.  As above, |aPtr| must be aligned, and |aBegin| and |aEnd|
 * must be aligned with respect to |T|.
 */
template <typename T>
inline bool IsInRange(const T* aPtr, uintptr_t aBegin, uintptr_t aEnd) {
  return IsInRange(aPtr, reinterpret_cast<const T*>(aBegin),
                   reinterpret_cast<const T*>(aEnd));
}

namespace detail {

/*
 * Helper for the MOZ_ARRAY_LENGTH() macro to make the length a typesafe
 * compile-time constant even on compilers lacking constexpr support.
 */
template <typename T, size_t N>
char (&ArrayLengthHelper(T (&array)[N]))[N];

} /* namespace detail */

} /* namespace mozilla */

#endif /* __cplusplus */

/*
 * MOZ_ARRAY_LENGTH() is an alternative to mozilla::ArrayLength() for C files
 * that can't use C++ template functions and for static_assert() calls that
 * can't call ArrayLength() when it is not a C++11 constexpr function.
 */
#ifdef __cplusplus
#  define MOZ_ARRAY_LENGTH(array) \
    sizeof(mozilla::detail::ArrayLengthHelper(array))
#else
#  define MOZ_ARRAY_LENGTH(array) (sizeof(array) / sizeof((array)[0]))
#endif

#endif /* mozilla_ArrayUtils_h */