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