hphp/util/ptr-map.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   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    +----------------------------------------------------------------------+
  15 */
  16
  17 #pragma once
  18
  19 #include <algorithm>
  20 #include <vector>
  21 #include "hphp/util/assertions.h"
  22 #include "hphp/util/portability.h"
  23
  24 namespace HPHP {
  25 ///////////////////////////////////////////////////////////////////////////////
  26
  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>;
  30
  31   void insert(T h, size_t size) {
  32     sorted_ &= regions_.empty() || h > regions_.back().first;
  33     regions_.emplace_back(h, size);
  34   }
  35
  36   const Region* region(const void* p) const {
  37     assert(sorted_);
  38     if (uintptr_t(p) - uintptr_t(span_.first) >= span_.second) {
  39       return nullptr;
  40     }
  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;
  45       });
  46     // If it == first region, p is before any region, which we already
  47     // checked above.
  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 :
  52            nullptr;
  53   }
  54
  55   T start(const void* p) const {
  56     auto r = region(p);
  57     return r ? r->first : nullptr;
  58   }
  59
  60   bool isStart(const void* p) const {
  61     auto h = start(p);
  62     return h && h == p;
  63   }
  64
  65   size_t index(const Region* r) const {
  66     return r - &regions_[0];
  67   }
  68
  69   // where does this region start sit in the regions_ vector?
  70   size_t index(T h) const {
  71     assert(start(h));
  72     return region(h) - &regions_[0];
  73   }
  74
  75   void prepare() {
  76     if (!sorted_) {
  77       std::sort(regions_.begin(), regions_.end());
  78       sorted_ = true;
  79     }
  80     if (!regions_.empty()) {
  81       auto& front = regions_.front();
  82       auto& back = regions_.back();
  83       span_ = Region{
  84         front.first,
  85         (const char*)back.first + back.second - (const char*)front.first
  86       };
  87     }
  88     assert(sanityCheck());
  89   }
  90
  91   size_t size() const {
  92     return regions_.size();
  93   }
  94
  95   template<class Fn> void iterate(Fn fn) const {
  96     for (auto& r : regions_) {
  97       fn(r.first, r.second);
  98     }
  99   }
 100
 101   Region span() const {
 102     return span_;
 103   }
 104
 105 private:
 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);
 112     }
 113     return true;
 114   }
 115
 116   Region span_{nullptr, 0};
 117   std::vector<Region> regions_;
 118   bool sorted_{true};
 119 };
 120
 121 ///////////////////////////////////////////////////////////////////////////////
 122 }