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_BITMAP_H_
6#define RUNTIME_VM_BITMAP_H_
7
8#include "vm/allocation.h"
9#include "vm/growable_array.h"
10#include "vm/thread_state.h"
11#include "vm/zone.h"
12
13namespace dart {
14
15// BitmapBuilder is used to build a bitmap. The implementation is optimized
16// for a dense set of small bit maps without a fixed upper bound (e.g: a
17// pointer map description of a stack).
18class BitmapBuilder : public ZoneAllocated {
19 public:
20 BitmapBuilder()
21 : length_(0),
22 data_size_in_bytes_(kInitialSizeInBytes),
23 data_(ThreadState::Current()->zone()->Alloc<uint8_t>(
24 kInitialSizeInBytes)) {
25 memset(data_, 0, kInitialSizeInBytes);
26 }
27
28 intptr_t Length() const { return length_; }
29 void SetLength(intptr_t length);
30
31 // Get/Set individual bits in the bitmap, setting bits beyond the bitmap's
32 // length increases the length and expands the underlying bitmap if
33 // needed.
34 bool Get(intptr_t bit_offset) const;
35 void Set(intptr_t bit_offset, bool value);
36
37 // Return the bit offset of the highest bit set.
38 intptr_t Maximum() const;
39
40 // Return the bit offset of the lowest bit set.
41 intptr_t Minimum() const;
42
43 // Sets min..max (inclusive) to value.
44 void SetRange(intptr_t min, intptr_t max, bool value);
45
46 void Print() const;
47 void AppendAsBytesTo(GrowableArray<uint8_t>* bytes) const;
48
49 private:
50 static const intptr_t kInitialSizeInBytes = 16;
51 static const intptr_t kIncrementSizeInBytes = 16;
52
53 bool InRange(intptr_t offset) const {
54 if (offset < 0) {
55 FATAL1(
56 "Fatal error in BitmapBuilder::InRange :"
57 " invalid bit_offset, %" Pd "\n",
58 offset);
59 }
60 return (offset < length_);
61 }
62
63 // Get/Set a bit that is known to be covered by the backing store.
64 bool GetBit(intptr_t bit_offset) const;
65 void SetBit(intptr_t bit_offset, bool value);
66
67 intptr_t length_;
68
69 // Backing store for the bitmap. Reading bits beyond the backing store
70 // (up to length_) is allowed and they are assumed to be false.
71 intptr_t data_size_in_bytes_;
72 uint8_t* data_;
73
74 DISALLOW_COPY_AND_ASSIGN(BitmapBuilder);
75};
76
77} // namespace dart
78
79#endif // RUNTIME_VM_BITMAP_H_
80