Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2017 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #ifndef ART_RUNTIME_SUBTYPE_CHECK_BITS_H_ |
| 18 | #define ART_RUNTIME_SUBTYPE_CHECK_BITS_H_ |
| 19 | |
| 20 | #include "base/bit_string.h" |
| 21 | #include "base/bit_struct.h" |
| 22 | #include "base/bit_utils.h" |
| 23 | |
| 24 | namespace art { |
| 25 | |
| 26 | /** |
| 27 | * The SubtypeCheckBits memory layout (in bits): |
| 28 | * |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 29 | * 1 bit Variable |
| 30 | * | | |
| 31 | * v v <---- up to 23 bits ----> |
| 32 | * |
| 33 | * +----+-----------+--------+-------------------------+ |
| 34 | * | | Bitstring | |
| 35 | * + +-----------+--------+-------------------------+ |
| 36 | * | OF | (unused) | Next | Path To Root | |
| 37 | * + | |--------+----+----------+----+----+ |
| 38 | * | | (0....0) | | | ... | | | |
| 39 | * +----+-----------+--------+----+----------+----+----+ |
| 40 | * MSB (most significant bit) LSB |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 41 | * |
| 42 | * The bitstring takes up to 23 bits; anything exceeding that is truncated: |
| 43 | * - Path To Root is a list of chars, encoded as a BitString: |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 44 | * starting at the root (in LSB), each character is a sibling index unique to the parent, |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 45 | * Paths longer than BitString::kCapacity are truncated to fit within the BitString. |
| 46 | * - Next is a single BitStringChar (immediatelly following Path To Root) |
| 47 | * When new children are assigned paths, they get allocated the parent's Next value. |
| 48 | * The next value is subsequently incremented. |
| 49 | * |
| 50 | * The exact bit position of (unused) is variable-length: |
| 51 | * In the cases that the "Path To Root" + "Next" does not fill up the entire |
| 52 | * BitString capacity, the remaining bits are (unused) and left as 0s. |
| 53 | * |
| 54 | * There is also an additional "OF" (overflow) field to indicate that the |
| 55 | * PathToRoot has been truncated. |
| 56 | * |
| 57 | * See subtype_check.h and subtype_check_info.h for more details. |
| 58 | */ |
| 59 | BITSTRUCT_DEFINE_START(SubtypeCheckBits, /*size*/ BitString::BitStructSizeOf() + 1u) |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 60 | BitStructField<BitString, /*lsb*/ 0> bitstring_; |
| 61 | BitStructUint</*lsb*/ BitString::BitStructSizeOf(), /*width*/ 1> overflow_; |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 62 | BITSTRUCT_DEFINE_END(SubtypeCheckBits); |
| 63 | |
| 64 | } // namespace art |
| 65 | |
| 66 | #endif // ART_RUNTIME_SUBTYPE_CHECK_BITS_H_ |