llvm/ADT/TrieHashIndexGenerator.h

0001 //===- TrieHashIndexGenerator.h ---------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_TRIEHASHINDEXGENERATOR_H
0010 #define LLVM_ADT_TRIEHASHINDEXGENERATOR_H
0011
0012 #include "llvm/ADT/ArrayRef.h"
0013 #include <optional>
0014
0015 namespace llvm {
0016
0017 /// The utility class that helps computing the index of the object inside trie
0018 /// from its hash. The generator can be configured with the number of bits
0019 /// used for each level of trie structure with \c NumRootsBits and \c
0020 /// NumSubtrieBits.
0021 /// For example, try computing indexes for a 16-bit hash 0x1234 with 8-bit root
0022 /// and 4-bit sub-trie:
0023 ///
0024 ///   IndexGenerator IndexGen{8, 4, Hash};
0025 ///   size_t index1 = IndexGen.next(); // index 18 in root node.
0026 ///   size_t index2 = IndexGen.next(); // index 3 in sub-trie level 1.
0027 ///   size_t index3 = IndexGen.next(); // index 4 in sub-tire level 2.
0028 ///
0029 /// This is used by different trie implementation to figure out where to
0030 /// insert/find the object in the data structure.
0031 struct TrieHashIndexGenerator {
0032   size_t NumRootBits;
0033   size_t NumSubtrieBits;
0034   ArrayRef<uint8_t> Bytes;
0035   std::optional<size_t> StartBit = std::nullopt;
0036
0037   // Get the number of bits used to generate current index.
0038   size_t getNumBits() const {
0039     assert(StartBit);
0040     size_t TotalNumBits = Bytes.size() * 8;
0041     assert(*StartBit <= TotalNumBits);
0042     return std::min(*StartBit ? NumSubtrieBits : NumRootBits,
0043                     TotalNumBits - *StartBit);
0044   }
0045
0046   // Get the index of the object in the next level of trie.
0047   size_t next() {
0048     if (!StartBit) {
0049       // Compute index for root when StartBit is not set.
0050       StartBit = 0;
0051       return getIndex(Bytes, *StartBit, NumRootBits);
0052     }
0053     if (*StartBit < Bytes.size() * 8) {
0054       // Compute index for sub-trie.
0055       *StartBit += *StartBit ? NumSubtrieBits : NumRootBits;
0056       assert((*StartBit - NumRootBits) % NumSubtrieBits == 0);
0057       return getIndex(Bytes, *StartBit, NumSubtrieBits);
0058     }
0059     // All the bits are consumed.
0060     return end();
0061   }
0062
0063   // Provide a hint to speed up the index generation by providing the
0064   // information of the hash in current level. For example, if the object is
0065   // known to have \c Index on a level that already consumes first n \c Bits of
0066   // the hash, it can start index generation from this level by calling \c hint
0067   // function.
0068   size_t hint(unsigned Index, unsigned Bit) {
0069     assert(Bit < Bytes.size() * 8);
0070     assert(Bit == 0 || (Bit - NumRootBits) % NumSubtrieBits == 0);
0071     StartBit = Bit;
0072     return Index;
0073   }
0074
0075   // Utility function for looking up the index in the trie for an object that
0076   // has colliding hash bits in the front as the hash of the object that is
0077   // currently being computed.
0078   size_t getCollidingBits(ArrayRef<uint8_t> CollidingBits) const {
0079     assert(StartBit);
0080     return getIndex(CollidingBits, *StartBit, NumSubtrieBits);
0081   }
0082
0083   size_t end() const { return SIZE_MAX; }
0084
0085   // Compute the index for the object from its hash, current start bits, and
0086   // the number of bits used for current level.
0087   static size_t getIndex(ArrayRef<uint8_t> Bytes, size_t StartBit,
0088                          size_t NumBits) {
0089     assert(StartBit < Bytes.size() * 8);
0090     // Drop all the bits before StartBit.
0091     Bytes = Bytes.drop_front(StartBit / 8u);
0092     StartBit %= 8u;
0093     size_t Index = 0;
0094     // Compute the index using the bits in range [StartBit, StartBit + NumBits),
0095     // note the range can spread across few `uint8_t` in the array.
0096     for (uint8_t Byte : Bytes) {
0097       size_t ByteStart = 0, ByteEnd = 8;
0098       if (StartBit) {
0099         ByteStart = StartBit;
0100         Byte &= (1u << (8 - StartBit)) - 1u;
0101         StartBit = 0;
0102       }
0103       size_t CurrentNumBits = ByteEnd - ByteStart;
0104       if (CurrentNumBits > NumBits) {
0105         Byte >>= CurrentNumBits - NumBits;
0106         CurrentNumBits = NumBits;
0107       }
0108       Index <<= CurrentNumBits;
0109       Index |= Byte & ((1u << CurrentNumBits) - 1u);
0110
0111       assert(NumBits >= CurrentNumBits);
0112       NumBits -= CurrentNumBits;
0113       if (!NumBits)
0114         break;
0115     }
0116     return Index;
0117   }
0118 };
0119
0120 } // namespace llvm
0121
0122 #endif // LLVM_ADT_TRIEHASHINDEXGENERATOR_H