OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * Copyright 2009 The Native Client Authors. All rights reserved. |
| 3 * Use of this source code is governed by a BSD-style license that can |
| 4 * be found in the LICENSE file. |
| 5 * Copyright 2009, Google Inc. |
| 6 */ |
| 7 |
| 8 #ifndef NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_MIPS_ADDRESS_SET_H |
| 9 #define NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_MIPS_ADDRESS_SET_H |
| 10 |
| 11 #include <stdint.h> |
| 12 |
| 13 namespace nacl_mips_val { |
| 14 |
| 15 /* |
| 16 * A set of word addresses, implemented as a dense bitset. |
| 17 * |
| 18 * An AddressSet has a base address and a size, in bytes, of the space to |
| 19 * describe. Describing N bytes costs N/32 bytes here, since we only record |
| 20 * word addresses (4-byte alignment) and pack 8 per byte. |
| 21 * |
| 22 * Thus, an AddressSet covering the entire 256MB code region costs 8MB, plus |
| 23 * a small constant overhead (~16 bytes). |
| 24 */ |
| 25 class AddressSet { |
| 26 public: |
| 27 /* |
| 28 * Creates an AddressSet describing 'size' bytes starting at 'base'. |
| 29 */ |
| 30 AddressSet(uint32_t base, uint32_t size); |
| 31 ~AddressSet(); |
| 32 |
| 33 /* |
| 34 * Adds an address to the set. |
| 35 * - If the address is already in the set, nothing changes. |
| 36 * - If the address is outside of this set's range (delimited by base and size |
| 37 * provided at construction), nothing changes. |
| 38 * - If the address is not 4-byte aligned, the address of the 4-byte word |
| 39 * containing the address is added instead. |
| 40 */ |
| 41 void add(uint32_t address); |
| 42 |
| 43 /* |
| 44 * Checks whether the AddressSet contains an address. If the address is not |
| 45 * 4-byte aligned, the address of the 4-byte word containing the address is |
| 46 * checked instead. |
| 47 */ |
| 48 bool contains(uint32_t address) const; |
| 49 |
| 50 class Iterator { |
| 51 public: |
| 52 Iterator(const AddressSet &, uint32_t index, uint32_t shift); |
| 53 Iterator &operator++(); |
| 54 bool operator!=(const Iterator &) const; |
| 55 uint32_t operator*() const; |
| 56 |
| 57 private: |
| 58 void advance(); |
| 59 |
| 60 const AddressSet &parent_; |
| 61 uint32_t index_; |
| 62 uint32_t shift_; |
| 63 }; |
| 64 |
| 65 Iterator begin() const; |
| 66 Iterator end() const; |
| 67 |
| 68 private: |
| 69 const uint32_t base_; |
| 70 const uint32_t size_; |
| 71 uint32_t * const bits_; |
| 72 |
| 73 // Disallow copies - we don't need them, and don't want to refcount bits_. |
| 74 AddressSet(const AddressSet &); |
| 75 AddressSet &operator=(const AddressSet &); |
| 76 }; |
| 77 |
| 78 } // namespace |
| 79 |
| 80 #endif // NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_MIPS_ADDRESS_SET_H |
OLD | NEW |