mirror of
https://github.com/carbon-language/carbon-lang.git
synced 2026-09-24 11:20:12 +01:00
Chandler Carruthandjosh11b
21a81bc59e
The hash table design is heavily based on Abseil's ["Swiss Tables"][swiss-tables] design. It uses an array of bytes storing metadata about each entry and an array of entries where each is a pair of key and value. The metadata byte consists of 7-bits of hash of the key (distinct from the bits used to index the table), and one bit indicating the presence of a special entry -- either empty or deleted. [swiss-tables]: https://abseil.io/about/design/swisstables There are a large range of optimizations and other nuanced aspects of this hash table design and implementation, a good point to understand that context is `raw_hashtable.h` which has an overview of the design and references to various other files for relevant details. --------- Co-authored-by: josh11b <15258583+josh11b@users.noreply.github.com>
21 lines
567 B
C++
21 lines
567 B
C++
// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
|
|
// Exceptions. See /LICENSE for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
|
|
#include "common/raw_hashtable_metadata_group.h"
|
|
|
|
#include "llvm/ADT/StringExtras.h"
|
|
|
|
namespace Carbon::RawHashtable {
|
|
|
|
auto MetadataGroup::Print(llvm::raw_ostream& out) const -> void {
|
|
out << "[";
|
|
llvm::ListSeparator sep;
|
|
for (uint8_t byte : metadata_bytes) {
|
|
out << sep << llvm::formatv("{0:x2}", byte);
|
|
}
|
|
out << "]";
|
|
}
|
|
|
|
} // namespace Carbon::RawHashtable
|