2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present 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 +----------------------------------------------------------------------+
17 #ifndef incl_HPHP_UTIL_PTRMAP_H_
18 #define incl_HPHP_UTIL_PTRMAP_H_
22 #include "hphp/util/assertions.h"
23 #include "hphp/util/portability.h"
26 ///////////////////////////////////////////////////////////////////////////////
28 // information about heap objects, indexed by valid object starts.
29 template<class T
> struct PtrMap
{
30 using Region
= std::pair
<T
, std::size_t>;
32 void insert(T h
, size_t size
) {
33 sorted_
&= regions_
.empty() || h
> regions_
.back().first
;
34 regions_
.emplace_back(h
, size
);
37 const Region
* region(const void* p
) const {
39 if (uintptr_t(p
) - uintptr_t(span_
.first
) >= span_
.second
) {
42 // Find the first region which begins beyond p.
43 auto it
= std::upper_bound(regions_
.begin(), regions_
.end(), p
,
44 [](const void* p
, const Region
& region
) {
45 return p
< region
.first
;
47 // If it == first region, p is before any region, which we already
49 assert(it
!= regions_
.begin());
50 --it
; // backup to the previous region.
51 // p can only potentially point within this previous region, so check that.
52 return uintptr_t(p
) - uintptr_t(it
->first
) < it
->second
? &*it
:
56 T
start(const void* p
) const {
58 return r
? r
->first
: nullptr;
61 bool isStart(const void* p
) const {
66 size_t index(const Region
* r
) const {
67 return r
- ®ions_
[0];
70 // where does this region start sit in the regions_ vector?
71 size_t index(T h
) const {
73 return region(h
) - ®ions_
[0];
78 std::sort(regions_
.begin(), regions_
.end());
81 if (!regions_
.empty()) {
82 auto& front
= regions_
.front();
83 auto& back
= regions_
.back();
86 (const char*)back
.first
+ back
.second
- (const char*)front
.first
89 assert(sanityCheck());
93 return regions_
.size();
96 template<class Fn
> void iterate(Fn fn
) const {
97 for (auto& r
: regions_
) {
98 fn(r
.first
, r
.second
);
102 Region
span() const {
107 bool sanityCheck() const {
108 // Verify that all the regions are in increasing and non-overlapping order.
109 DEBUG_ONLY
void* last
= nullptr;
110 for (const auto& region
: regions_
) {
111 assert(!last
|| last
<= region
.first
);
112 last
= (void*)(uintptr_t(region
.first
) + region
.second
);
117 Region span_
{nullptr, 0};
118 std::vector
<Region
> regions_
;
122 ///////////////////////////////////////////////////////////////////////////////