1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
// SPDX-FileCopyrightText: 2022 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT
#pragma once
#include "./cref_wrapper.hpp"
#include <string_view>
#include <unordered_map>
namespace mdds {
namespace ssmap {
namespace detail {
template<typename ValueT>
struct map_entry
{
std::string_view key;
ValueT value;
};
} // namespace detail
/**
* Function object that iterates through the key-value entries linearly until
* it finds one that contains the target value.
*/
template<typename ValueT>
class linear_key_finder
{
using value_type = ValueT;
using size_type = typename std::string_view::size_type;
using entry_type = detail::map_entry<ValueT>;
const entry_type* m_entries;
const entry_type* m_entries_end;
public:
linear_key_finder(const entry_type* entries, const entry_type* entries_end) noexcept;
std::string_view operator()(const value_type& v) const;
};
/**
* Function object that builds a hash map of values to keys during its
* construction, and uses it during the lookup of the keys.
*/
template<typename ValueT>
class hash_key_finder
{
using value_type = ValueT;
using size_type = typename std::string_view::size_type;
using entry_type = detail::map_entry<ValueT>;
using keystore_type = std::unordered_map<
mdds::detail::cref_wrapper<value_type>, size_type, typename mdds::detail::cref_wrapper<value_type>::hash>;
const entry_type* m_entries;
keystore_type m_keys;
public:
hash_key_finder(const entry_type* entries, const entry_type* entries_end);
std::string_view operator()(const value_type& v) const;
};
} // namespace ssmap
/**
* sorted_string_map is an immutable associative container that provides an
* efficient way to map string keys to values of a user-specified type.
* The keys must be known at compile time and must be sorted in ascending
* order.
*
* Besides the minimal amount of memory required to store the size and memory
* address of the caller-provided key-value entries and a few extra data,
* it does not allocate any additional memory; it simply re-uses the
* caller-provided key-value entries in all of its operations.
*
* @tparam ValueT Type of the values associated with the string keys.
* This type must be either movable or copyable.
* @tparam KeyFinderT Function object type for performing reverse-lookup of
* keys from values. This is used in the find_key() method.
*/
template<typename ValueT, template<typename> class KeyFinderT = ssmap::linear_key_finder>
class sorted_string_map
{
using func_find_key_type = KeyFinderT<ValueT>;
public:
using value_type = ValueT;
using size_type = typename std::string_view::size_type;
/**
* Single key-value entry type. Caller must provide at compile time a
* static array of these entries.
*/
using entry_type = ssmap::detail::map_entry<ValueT>;
/**
* Constructor.
*
* @param entries pointer to the array of key-value entries.
* @param entry_size size of the key-value entry array.
* @param null_value null value to return when the find method fails to
* find a matching entry.
*/
sorted_string_map(const entry_type* entries, size_type entry_size, value_type null_value);
/**
* Find a value associated with a specified string key.
*
* @param input pointer to a C-style string whose value represents the key
* to match.
* @param len length of the matching string value.
*
* @return value associated with the key, or the null value in case the
* key is not found.
*/
const value_type& find(const char* input, size_type len) const;
/**
* Find a value associated with a specified string key.
*
* @param input string key to match.
*
* @return value associated with the key, or the null value in case the
* key is not found.
*/
const value_type& find(std::string_view input) const;
/**
* Find a key associated with a specified value.
*
* @warning When multiple keys are associated with one value, this method
* only returns one of the keys. Which key gets returned for that
* value is undefined.
*
* @param v Value to find the associated key of.
*
* @return Key associated with the value, or an empty string if no key is
* found.
*/
std::string_view find_key(const value_type& v) const;
/**
* Return the number of entries in the map. Since the number of entries
* is statically defined at compile time, this method always returns the
* same value.
*
* @return the number of entries in the map.
*/
size_type size() const;
private:
const entry_type* m_entries;
const value_type m_null_value;
const size_type m_entry_size;
const entry_type* m_entries_end;
func_find_key_type m_func_find_key;
};
} // namespace mdds
#include "sorted_string_map_def.inl"
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
