# Stored Types

> SmashTable for C++

`#include <smashtable/shared.hpp>`

`#include <smashtable/row_layout.hpp>`

## mapping

Simple key-value mapping type, cleaner & lighter than `std::pair` used by `std::map`.

```cpp
template <typename key_type_,
          typename mapped_type_>
struct mapping
```

- `key` `key_type`
- `mapped` `mapped_type`

See also: [https://en.cppreference.com/w/cpp/utility/pair.html](https://en.cppreference.com/w/cpp/utility/pair.html)

## has_comparable_particle

Checks if a type has a `comparable_particle` member.

```cpp
template <typename,
          typename = void>
struct has_comparable_particle
```

```
struct with_particle { using comparable_particle = int; };
struct without_particle {};
static_assert(has_comparable_particle::value, "Should have comparable_particle");
static_assert(!has_comparable_particle::value, "Should not have comparable_particle");
```

## mapping_key_type_or_itself

If `can_be_mapping_type_` is a mapping, exposes its [`key_type`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#key_type) as `::type`.

```cpp
template <typename can_be_mapping_type_,
          bool = is_mapping<can_be_mapping_type_>>
struct mapping_key_type_or_itself
```

Otherwise, exposes `can_be_mapping_type_` itself as `::type`.

```
using pair = mapping;
static_assert(std::is_same_v::type, int>, "Must be int");
static_assert(std::is_same_v::type, double>, "Must be double");
```

## mapped_value_type_or_void

If `can_be_mapping_type_` is a mapping, exposes its `mapped_type` as `::type`.

```cpp
template <typename can_be_mapping_type_,
          bool = is_mapping<can_be_mapping_type_>>
struct mapped_value_type_or_void
```

Otherwise, exposes `void` as `::type`.

```
using pair = mapping;
static_assert(std::is_same_v::type, std::string>, "Must be string");
static_assert(std::is_same_v::type, void>, "Must be void");
```

## comparable_particle_of

```cpp
template <typename comparator_type_,
          typename comparable_type_,
          bool = has_comparable_particle<comparator_type_>::value>
struct comparable_particle_of
```

#### Correctness of Comparisons

For `std::set`, `std::map`, or similar containers we only require the keys to provide __strict-weak-ordering__ comparisons. It's enough to simply define a comparator that returns a boolean result for two comparable objects. Since C++ 20, comparisons are better formalized:

- `std::strong_ordering` - equivalent values are fully interchangeable, all are comparable!
- `std::weak_ordering` - equivalent values may be non-interchangeable, but all are comparable!
- `std::partial_ordering` - equivalent values may be non-interchangeable or incomparable!
Assuming that `float` values can be `NaN` and thus incomparable, we shouldn't be able to construct a `std::set<float>` since the ordering is only partial, but GCC still compiles it.

#### Optimization Opportunities

Oftentimes, when dealing with heavy objects as keys (e.g., strings, composite structures), we want to avoid storing many copies of the full object just to perform comparisons and lookups. Instead, we can distill a lightweight "particle" from the heavy object that captures its identity for ordering purposes. Examples may be:

- Non-owning `std::string_view` for `std::string` keys
- Integer identifiers extracted from composite structures
If the `comparator_type_` has a `value_type` member - indicating some form of a unique identifier can be distilled from `comparable_type_` - we expose it via `::type`. Else, if the `comparable_type_` is a [`mapping`](#mapping), we use its [`key_type`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#key_type) as the identifier. Else, we use the `comparable_type_` itself as the identifier.

## owned_value_of

The owned element a core stores, as distinct from the view it hands out.

```cpp
template <typename collection_type_,
          typename = void>
struct owned_value_of
```

A node-based container returns a reference to the element it holds, so the two coincide; an open-addressed table keeps keys and values in separate regions and can only view an entry as a pair of references, which nothing above it can own, copy, or version.

## storage_node_of

The node type a linked storage hands out, or `void` where the storage has no nodes.

```cpp
template <typename collection_type_,
          typename = void>
struct storage_node_of
```

An ordered surface walks nodes directly; an open-addressed table has none to walk, and naming one unconditionally would break the adapter at its own definition rather than at the call.

## key128_t

A 16-byte key as two words, each holding eight bytes read big-endian, so ordering the words orders the bytes as `memcmp` would.

```cpp
struct key128_t
```

An integer identity below 2^64 has a zero `high` and its value in `low`.

- `high` `std::uint64_t`
- `low` `std::uint64_t`

## hash< key128_t >

A 16-byte key, its high word finalized into the low one and the result finalized again.

```cpp
template <>
struct hash< key128_t >
```

## row_format

How a node of `keys_per_row_` keys is stored as words: an integer row is one column of keys, and a 16-byte row is a column of high words followed by a column of low words, so both columns share one medium unit.

```cpp
template <typename key_type_,
          std::size_t keys_per_row_>
struct row_format
```

- `keys_are_split_k` `bool`
- `keys_per_row_k` `std::size_t`
- `words_per_row_k` `std::size_t`
- `bytes_per_row_k` `std::size_t`
- `padding_k` `key_t`: The key unused slots hold, ordering at or after every key, so a count below never includes it.

## copy_to

Builds a `copy_to_fn` over `element`, for a read whose result the caller wants kept.

```cpp
template <typename element_type_>
copy_to_fn<element_type_> copy_to(element_type_ & element) noexcept;
```

## operator==

Whether `result` carries `status:` why it failed, or success when it holds a value.

```cpp
template <typename value_type_>
bool operator==(
    expected<value_type_> const & result,
    status_t status) noexcept;
```

```cpp
template <typename value_type_, typename comparable_type_>
requires (!std::same_as<std::remove_cvref_t<comparable_type_>, status_t>) && requires(value_type_ const &held, comparable_type_ const &other) { { held == other } -> std::convertible_to<bool>; }
bool operator==(
    expected<value_type_> const & result,
    comparable_type_ const & value) noexcept;
```

Whether `result` holds a value equal to `value`.

Saves a ``.status() at the call site, and reads the way the question is asked out loud. C++20 synthesizes the reversed and negated forms, so this one definition covers all four spellings.

Warnings: A failed [`expected`](https://www.unum.cloud/docs/smashtable/cpp/quickstart.md#expected) equals no value, so a `false` answer covers both "held something
    else" and "held nothing at all". Where a test needs those apart, check the result first and compare the value second.

## copy_safely

Copies `object` through its `noexcept` copy constructor, or its [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) method.

```cpp
template <typename object_type_>
expected<object_type_> copy_safely(
    object_type_ const & object) noexcept;
```

Statuses: - Any status the [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) method of `object` returns passes through unchanged.

## move_or_copy_safely

Takes `object` over when it is an rvalue, as a move iterator hands one, and copies it through [`copy_safely`](#copy_safely) otherwise, so a sorted build moves what a caller gave up and copies what it lent.

```cpp
template <typename object_type_>
expected<std::remove_cvref_t<object_type_>> move_or_copy_safely(
    object_type_ && object) noexcept;
```

Statuses: - Any status the [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy) method of `object` returns passes through unchanged.

## copy_identifier

Copies `comparable` into an owned `identifier_type_:` through [`copy_safely`](#copy_safely) where it already is one, and by conversion where it is another type the store compares against.

```cpp
template <typename identifier_type_, typename comparable_type_>
expected<identifier_type_> copy_identifier(
    comparable_type_ const & comparable) noexcept;
```

Converting an identifier into itself would ask for its copy constructor, which a key owning its bytes deletes in favour of [`copy`](https://www.unum.cloud/docs/smashtable/cpp/containers.md#copy).

## mapping_key_or_itself

Helper method to extract mapping key or return the object itself.

```cpp
template <typename can_be_mapping_type_>
mapping_key_type_or_itself<can_be_mapping_type_>::type const & mapping_key_or_itself(
    can_be_mapping_type_ const & can_be_mapping) noexcept;
```

Useful for generic code that works with both mappings and simple keys.

## keys_per_row

How many keys of `key_type_` fill `medium_bytes`, counting both columns of a split 16-byte row.

```cpp
template <typename key_type_>
std::size_t keys_per_row(std::size_t medium_bytes) noexcept;
```

## default_row_bytes_k

The row width the ordered layouts take when a caller names none: a 512-byte block.

```cpp
std::size_t default_row_bytes_k;
```

Sized rather than measured: a cache line is 64 bytes on most cores and 128 on others, and a page is 4096 bytes until an operating system is configured otherwise, so neither is a constant this header could state. A block sits between them and divides evenly by every key width here.

## Overview

A row is the unit every ordered layout here searches: a span of keys wide enough to be worth one vectorized pass. This header says what a key may be and how a row is laid out; `row_search.hpp` says how one is searched, and the layouts above both say what they do with the answer.