1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_OBJECT_SET_H_
6#define RUNTIME_VM_OBJECT_SET_H_
7
8#include "platform/utils.h"
9#include "vm/bit_vector.h"
10#include "vm/globals.h"
11#include "vm/raw_object.h"
12#include "vm/zone.h"
13
14namespace dart {
15
16class ObjectSetRegion : public ZoneAllocated {
17 public:
18 ObjectSetRegion(Zone* zone, uword start, uword end)
19 : start_(start),
20 end_(end),
21 bit_vector_(zone, (end - start) >> kWordSizeLog2) {}
22
23 bool ContainsAddress(uword address) const {
24 return address >= start_ && address < end_;
25 }
26
27 intptr_t IndexForAddress(uword address) const {
28 ASSERT(Utils::IsAligned(address, kWordSize));
29 return (address - start_) >> kWordSizeLog2;
30 }
31
32 void AddObject(uword address) { bit_vector_.Add(IndexForAddress(address)); }
33
34 bool ContainsObject(uword address) const {
35 return bit_vector_.Contains(IndexForAddress(address));
36 }
37
38 uword start() const { return start_; }
39 uword end() const { return end_; }
40
41 private:
42 uword start_;
43 uword end_;
44 BitVector bit_vector_;
45};
46
47class ObjectSet : public ZoneAllocated {
48 public:
49 explicit ObjectSet(Zone* zone) : zone_(zone), sorted_(true), regions_() {}
50
51 void AddRegion(uword start, uword end) {
52 if (start == end) {
53 return; // Ignore empty regions, such as semispaces in the vm-isolate.
54 }
55 ASSERT(start < end);
56 ObjectSetRegion* region = new (zone_) ObjectSetRegion(zone_, start, end);
57 regions_.Add(region);
58 sorted_ = false;
59 }
60
61 void SortRegions() {
62 regions_.Sort(CompareRegions);
63 sorted_ = true;
64 }
65
66 bool Contains(ObjectPtr raw_obj) const {
67 uword raw_addr = ObjectLayout::ToAddr(raw_obj);
68 ObjectSetRegion* region;
69 if (FindRegion(raw_addr, &region)) {
70 return region->ContainsObject(raw_addr);
71 }
72 return false;
73 }
74
75 void Add(ObjectPtr raw_obj) {
76 uword raw_addr = ObjectLayout::ToAddr(raw_obj);
77 ObjectSetRegion* region;
78 if (FindRegion(raw_addr, &region)) {
79 return region->AddObject(raw_addr);
80 }
81 FATAL("Address not in any heap region");
82 }
83
84 private:
85 static int CompareRegions(ObjectSetRegion* const* a,
86 ObjectSetRegion* const* b) {
87 const uword a_start = (*a)->start();
88 const uword b_start = (*b)->start();
89 if (a_start < b_start) {
90 return -1;
91 } else if (a_start == b_start) {
92 return 0;
93 } else {
94 return 1;
95 }
96 }
97
98 bool FindRegion(uword addr, ObjectSetRegion** region) const {
99 ASSERT(sorted_);
100 intptr_t lo = 0;
101 intptr_t hi = regions_.length() - 1;
102 while (lo <= hi) {
103 const intptr_t mid = (hi - lo + 1) / 2 + lo;
104 ASSERT(mid >= lo);
105 ASSERT(mid <= hi);
106 *region = regions_[mid];
107 if (addr < (*region)->start()) {
108 hi = mid - 1;
109 } else if (addr >= (*region)->end()) {
110 lo = mid + 1;
111 } else {
112 return true;
113 }
114 }
115 return false;
116 }
117
118 Zone* zone_;
119 bool sorted_;
120 GrowableArray<ObjectSetRegion*> regions_;
121};
122
123} // namespace dart
124
125#endif // RUNTIME_VM_OBJECT_SET_H_
126