crashpad/client/simple_string_dictionary.h
Mark Mentovai 6278690abe Update copyright boilerplate, 2022 edition (Crashpad)
sed -i '' -E -e 's/Copyright (.+) The Crashpad Authors\. All rights reserved\.$/Copyright \1 The Crashpad Authors/' $(git grep -El 'Copyright (.+) The Crashpad Authors\. All rights reserved\.$')

Bug: chromium:1098010
Change-Id: I8d6138469ddbe3d281a5d83f64cf918ec2491611
Reviewed-on: https://chromium-review.googlesource.com/c/crashpad/crashpad/+/3878262
Reviewed-by: Joshua Peraza <jperaza@chromium.org>
Commit-Queue: Mark Mentovai <mark@chromium.org>
2022-09-06 23:54:07 +00:00

289 lines
8.5 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

// Copyright 2014 The Crashpad Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_
#define CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_
#include <string.h>
#include <sys/types.h>
#include <algorithm>
#include <type_traits>
#include "base/check_op.h"
#include "base/strings/string_piece.h"
#include "util/misc/implicit_cast.h"
namespace crashpad {
//! \brief A map/dictionary collection implementation using a fixed amount of
//! storage, so that it does not perform any dynamic allocations for its
//! operations.
//!
//! The actual map storage (TSimpleStringDictionary::Entry) is guaranteed to be
//! POD, so that it can be transmitted over various IPC mechanisms.
//!
//! The template parameters control the amount of storage used for the key,
//! value, and map. The \a KeySize and \a ValueSize are measured in bytes, not
//! glyphs, and include space for a trailing `NUL` byte. This gives space for
//! `KeySize - 1` and `ValueSize - 1` characters in an entry. \a NumEntries is
//! the total number of entries that will fit in the map.
template <size_t KeySize = 256, size_t ValueSize = 256, size_t NumEntries = 64>
class TSimpleStringDictionary {
public:
//! \brief Constant and publicly accessible versions of the template
//! parameters.
//! \{
static const size_t key_size = KeySize;
static const size_t value_size = ValueSize;
static const size_t num_entries = NumEntries;
//! \}
//! \brief A single entry in the map.
struct Entry {
//! \brief The entrys key.
//!
//! This string is always `NUL`-terminated. If this is a 0-length
//! `NUL`-terminated string, the entry is inactive.
char key[KeySize];
//! \brief The entrys value.
//!
//! This string is always `NUL`-terminated.
char value[ValueSize];
//! \brief Returns the validity of the entry.
//!
//! If #key is an empty string, the entry is considered inactive, and this
//! method returns `false`. Otherwise, returns `true`.
bool is_active() const {
return key[0] != '\0';
}
};
//! \brief An iterator to traverse all of the active entries in a
//! TSimpleStringDictionary.
class Iterator {
public:
explicit Iterator(const TSimpleStringDictionary& map)
: map_(map),
current_(0) {
}
Iterator(const Iterator&) = delete;
Iterator& operator=(const Iterator&) = delete;
//! \brief Returns the next entry in the map, or `nullptr` if at the end of
//! the collection.
const Entry* Next() {
while (current_ < map_.num_entries) {
const Entry* entry = &map_.entries_[current_++];
if (entry->is_active()) {
return entry;
}
}
return nullptr;
}
private:
const TSimpleStringDictionary& map_;
size_t current_;
};
TSimpleStringDictionary()
: entries_() {
}
TSimpleStringDictionary(const TSimpleStringDictionary& other) {
*this = other;
}
TSimpleStringDictionary& operator=(const TSimpleStringDictionary& other) {
memcpy(entries_, other.entries_, sizeof(entries_));
return *this;
}
//! \brief Returns the number of active key/value pairs. The upper limit for
//! this is \a NumEntries.
size_t GetCount() const {
size_t count = 0;
for (size_t i = 0; i < num_entries; ++i) {
if (entries_[i].is_active()) {
++count;
}
}
return count;
}
//! \brief Given \a key, returns its corresponding value.
//!
//! \param[in] key The key to look up. This must not be `nullptr`, nor an
//! empty string. It must not contain embedded `NUL`s.
//!
//! \return The corresponding value for \a key, or if \a key is not found,
//! `nullptr`.
const char* GetValueForKey(base::StringPiece key) const {
DCHECK(key.data());
DCHECK(key.size());
DCHECK_EQ(key.find('\0', 0), base::StringPiece::npos);
if (!key.data() || !key.size()) {
return nullptr;
}
const Entry* entry = GetConstEntryForKey(key);
if (!entry) {
return nullptr;
}
return entry->value;
}
//! \brief Stores \a value into \a key, replacing the existing value if \a key
//! is already present.
//!
//! If \a key is not yet in the map and the map is already full (containing
//! \a NumEntries active entries), this operation silently fails.
//!
//! \param[in] key The key to store. This must not be `nullptr`, nor an empty
//! string. It must not contain embedded `NUL`s.
//! \param[in] value The value to store. If `nullptr`, \a key is removed from
//! the map. Must not contain embedded `NUL`s.
void SetKeyValue(base::StringPiece key, base::StringPiece value) {
if (!value.data()) {
RemoveKey(key);
return;
}
DCHECK(key.data());
DCHECK(key.size());
DCHECK_EQ(key.find('\0', 0), base::StringPiece::npos);
if (!key.data() || !key.size()) {
return;
}
// |key| must not be an empty string.
DCHECK_NE(key[0], '\0');
if (key[0] == '\0') {
return;
}
// |value| must not contain embedded NULs.
DCHECK_EQ(value.find('\0', 0), base::StringPiece::npos);
Entry* entry = GetEntryForKey(key);
// If it does not yet exist, attempt to insert it.
if (!entry) {
for (size_t i = 0; i < num_entries; ++i) {
if (!entries_[i].is_active()) {
entry = &entries_[i];
SetFromStringPiece(key, entry->key, key_size);
break;
}
}
}
// If the map is out of space, |entry| will be nullptr.
if (!entry) {
return;
}
#ifndef NDEBUG
// Sanity check that the key only appears once.
int count = 0;
for (size_t i = 0; i < num_entries; ++i) {
if (EntryKeyEquals(key, entries_[i])) {
++count;
}
}
DCHECK_EQ(count, 1);
#endif
SetFromStringPiece(value, entry->value, value_size);
}
//! \brief Removes \a key from the map.
//!
//! If \a key is not found, this is a no-op.
//!
//! \param[in] key The key of the entry to remove. This must not be `nullptr`,
//! nor an empty string. It must not contain embedded `NUL`s.
void RemoveKey(base::StringPiece key) {
DCHECK(key.data());
DCHECK(key.size());
DCHECK_EQ(key.find('\0', 0), base::StringPiece::npos);
if (!key.data() || !key.size()) {
return;
}
Entry* entry = GetEntryForKey(key);
if (entry) {
entry->key[0] = '\0';
entry->value[0] = '\0';
}
DCHECK_EQ(GetEntryForKey(key), implicit_cast<Entry*>(nullptr));
}
private:
static void SetFromStringPiece(base::StringPiece src,
char* dst,
size_t dst_size) {
size_t copy_len = std::min(dst_size - 1, src.size());
src.copy(dst, copy_len);
dst[copy_len] = '\0';
}
static bool EntryKeyEquals(base::StringPiece key, const Entry& entry) {
if (key.size() >= KeySize)
return false;
// Test for a NUL terminator and early out if it's absent.
if (entry.key[key.size()] != '\0')
return false;
// As there's a NUL terminator at the right position in the entries
// string, strncmp can do the rest.
return strncmp(key.data(), entry.key, key.size()) == 0;
}
const Entry* GetConstEntryForKey(base::StringPiece key) const {
for (size_t i = 0; i < num_entries; ++i) {
if (EntryKeyEquals(key, entries_[i])) {
return &entries_[i];
}
}
return nullptr;
}
Entry* GetEntryForKey(base::StringPiece key) {
return const_cast<Entry*>(GetConstEntryForKey(key));
}
Entry entries_[NumEntries];
};
//! \brief A TSimpleStringDictionary with default template parameters.
//!
//! For historical reasons this specialized version is available with the same
//! size factors as a previous implementation.
using SimpleStringDictionary = TSimpleStringDictionary<256, 256, 64>;
static_assert(std::is_standard_layout<SimpleStringDictionary>::value,
"SimpleStringDictionary must be standard layout");
} // namespace crashpad
#endif // CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_