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 +----------------------------------------------------------------------+
21 #include "hphp/util/assertions.h"
22 #include "hphp/util/portability.h"
25 ///////////////////////////////////////////////////////////////////////////////
27 // information about heap objects, indexed by valid object starts.
28 template<class T
> struct PtrMap
{
29 using Region
= std::pair
<T
, std::size_t>;
31 void insert(T h
, size_t size
) {
32 sorted_
&= regions_
.empty() || h
> regions_
.back().first
;
33 regions_
.emplace_back(h
, size
);
36 const Region
* region(const void* p
) const {
38 if (uintptr_t(p
) - uintptr_t(span_
.first
) >= span_
.second
) {
41 // Find the first region which begins beyond p.
42 auto it
= std::upper_bound(regions_
.begin(), regions_
.end(), p
,
43 [](const void* p
, const Region
& region
) {
44 return p
< region
.first
;
46 // If it == first region, p is before any region, which we already
48 assert(it
!= regions_
.begin());
49 --it
; // backup to the previous region.
50 // p can only potentially point within this previous region, so check that.
51 return uintptr_t(p
) - uintptr_t(it
->first
) < it
->second
? &*it
:
55 T
start(const void* p
) const {
57 return r
? r
->first
: nullptr;
60 bool isStart(const void* p
) const {
65 size_t index(const Region
* r
) const {
66 return r
- ®ions_
[0];
69 // where does this region start sit in the regions_ vector?
70 size_t index(T h
) const {
72 return region(h
) - ®ions_
[0];
77 std::sort(regions_
.begin(), regions_
.end());
80 if (!regions_
.empty()) {
81 auto& front
= regions_
.front();
82 auto& back
= regions_
.back();
85 (const char*)back
.first
+ back
.second
- (const char*)front
.first
88 assert(sanityCheck());
92 return regions_
.size();
95 template<class Fn
> void iterate(Fn fn
) const {
96 for (auto& r
: regions_
) {
97 fn(r
.first
, r
.second
);
101 Region
span() const {
106 bool sanityCheck() const {
107 // Verify that all the regions are in increasing and non-overlapping order.
108 DEBUG_ONLY
void* last
= nullptr;
109 for (const auto& region
: regions_
) {
110 assert(!last
|| last
<= region
.first
);
111 last
= (void*)(uintptr_t(region
.first
) + region
.second
);
116 Region span_
{nullptr, 0};
117 std::vector
<Region
> regions_
;
121 ///////////////////////////////////////////////////////////////////////////////