From f049c157f0d2b5616bd637dd18ba67de261573fc Mon Sep 17 00:00:00 2001 From: Egor Date: Tue, 3 Feb 2026 15:58:56 +0200 Subject: [PATCH] map: reorganize stuff to more directly use FlatSet --- src/admin.cpp | 16 ++-- src/common.hpp | 3 +- src/ircdata.hpp | 8 ++ src/map.hpp | 217 +++++++++++++++++++++++++----------------------- 4 files changed, 129 insertions(+), 115 deletions(-) diff --git a/src/admin.cpp b/src/admin.cpp index 8afd0aa..e78cad6 100644 --- a/src/admin.cpp +++ b/src/admin.cpp @@ -41,22 +41,22 @@ static int map_newindex(lua_State *L) const char *key = luaL_checkstring(L, 2); luaL_checkany(L, 3); if (lua_isnil(L, 3)) { - (void)m->_set(key, 0, 0); + m->_remove(key); return 0; } lua_getiuservalue(L, 1, 1); switch (lua_tointeger(L, -1)) { case MAPTYPE_STRINGSET: - (void)m->_set(key, key, 0); + m->_set(key); break; case MAPTYPE_CLIENT: { void **p = (void **)luaL_checkudata(L, 3, "client"); - (void)m->_set(key, *p, 0); + m->_set(*p); break; } case MAPTYPE_CHANNEL: { void **p = (void **)luaL_checkudata(L, 3, "channel"); - (void)m->_set(key, *p, 0); + m->_set(*p); break; } } @@ -71,16 +71,16 @@ static int map_iter_next(lua_State *L) lua_getiuservalue(L, 1, 1); switch (lua_tointeger(L, -1)) { case MAPTYPE_STRINGSET: - lua_pushstring(L, key); - lua_pushstring(L, key); + lua_pushlstring(L, key.data(), key.size()); + lua_pushlstring(L, key.data(), key.size()); return 2; case MAPTYPE_CLIENT: - lua_pushstring(L, key); + lua_pushlstring(L, key.data(), key.size()); *(Client **)lua_newuserdatauv(L, sizeof(Client *), 0) = (Client *)value; luaL_setmetatable(L, "client"); return 2; case MAPTYPE_CHANNEL: - lua_pushstring(L, key); + lua_pushlstring(L, key.data(), key.size()); *(Channel **)lua_newuserdatauv(L, sizeof(Channel *), 0) = (Channel *)value; luaL_setmetatable(L, "channel"); return 2; diff --git a/src/common.hpp b/src/common.hpp index f7ac225..077a445 100644 --- a/src/common.hpp +++ b/src/common.hpp @@ -1,5 +1,5 @@ // Copyright (c) 2022 Sam Smith -// Copyright (c) 2022-2025 Egor +// Copyright (c) 2022-2026 Egor // SPDX-License-Identifier: GPL-2.0-or-later #ifndef COMMON_H_ #define COMMON_H_ @@ -38,7 +38,6 @@ #include #include #include -#include #include #include using namespace std::string_view_literals; diff --git a/src/ircdata.hpp b/src/ircdata.hpp index 44942fd..02af147 100644 --- a/src/ircdata.hpp +++ b/src/ircdata.hpp @@ -76,6 +76,10 @@ struct Client { Client& operator=(Client&&) = delete; ~Client(); }; +constexpr std::string_view to_key(const Client *v) noexcept { + return v->key; +} + #define DMODE_PERSIST 1 #define DMODE_INVITEONLY 2 #define DMODE_MODERATED 4 @@ -115,6 +119,10 @@ struct Channel { return v.has(client); } }; +constexpr std::string_view to_key(const Channel *v) noexcept { + return v->key; +} + extern clientmap client_map; extern channelmap channel_map; extern Client *clients; diff --git a/src/map.hpp b/src/map.hpp index 32935f6..ff8728b 100644 --- a/src/map.hpp +++ b/src/map.hpp @@ -53,19 +53,26 @@ class FlatSet { KeyContainer m_vec; [[no_unique_address]] Compare cmp; public: - using iterator = KeyContainer::iterator; - auto begin() noexcept { return m_vec.begin(); } - auto end() noexcept { return m_vec.end(); } + using iterator = KeyContainer::const_iterator; + iterator begin() noexcept { return m_vec.cbegin(); } + iterator end() noexcept { return m_vec.cend(); } - auto lower_bound(const Key& key) { + KeyContainer extract() && { + return std::move(m_vec); + } + void replace(KeyContainer&& cont) { + m_vec = std::move(cont); + } + + iterator lower_bound(const Key& key) { return std::partition_point(begin(), end(), [&](const auto &e){ return cmp(e, key); }); } template requires is_transparent - auto lower_bound(const K& key) { + iterator lower_bound(const K& key) { return std::partition_point(begin(), end(), [&](const auto &e){ return cmp(e, key); }); } - auto find(const Key& key) { + iterator find(const Key& key) { auto it = lower_bound(key); if (it != end() && !cmp(key, *it)) return it; @@ -73,7 +80,7 @@ public: return end(); } template requires is_transparent - auto find(const K& key) { + iterator find(const K& key) { auto it = lower_bound(key); if (it != end() && !cmp(key, *it)) return it; @@ -81,7 +88,7 @@ public: return end(); } - auto insert(const Key& key) { + std::pair insert(const Key& key) { auto it = lower_bound(key); if (it != end() && !cmp(key, *it)) { return std::make_pair(it, false); @@ -89,7 +96,7 @@ public: return std::make_pair(m_vec.insert(it, key), true); } } - auto insert(Key&& key) { + std::pair insert(Key&& key) { auto it = lower_bound(key); if (it != end() && !cmp(key, *it)) { return std::make_pair(it, false); @@ -97,8 +104,17 @@ public: return std::make_pair(m_vec.insert(it, std::move(key)), true); } } + template requires is_transparent + std::pair insert(K&& key) { + auto it = lower_bound(key); + if (it != end() && !cmp(key, *it)) { + return std::make_pair(it, false); + } else { + return std::make_pair(m_vec.emplace(it, std::forward(key)), true); + } + } - auto erase(typename KeyContainer::iterator it) { + iterator erase(iterator it) { return m_vec.erase(it); } size_t erase(const Key& key) { @@ -124,7 +140,7 @@ public: void clear() noexcept { m_vec.clear(); } - auto size() noexcept { + size_t size() noexcept { return m_vec.size(); } @@ -141,15 +157,26 @@ public: * A map is created by allocating and zero-initializing an object of type * map_t. All map functions take a pointer to map_t. */ +struct Client; +struct Channel; +constexpr std::string_view to_key(const std::string &v) noexcept { + return v; +} +constexpr std::string_view to_key(const Client *v) noexcept; +constexpr std::string_view to_key(const Channel *v) noexcept; + template struct MapValueLess { using is_transparent = void; - constexpr std::string_view to_key(const T &v) { - return v.key; - } constexpr bool operator()(const T& lhs, const T& rhs) noexcept { return to_key(lhs) < to_key(rhs); } + constexpr bool operator()(const T& lhs, const char *rhs) noexcept { + return to_key(lhs) < rhs; + } + constexpr bool operator()(const char *lhs, const T& rhs) noexcept { + return lhs < to_key(rhs); + } constexpr bool operator()(const T& lhs, std::string_view rhs) noexcept { return to_key(lhs) < rhs; } @@ -167,8 +194,9 @@ struct map_base { map_base& operator=(map_base&&) = delete; virtual ~map_base() = default; virtual void *_get(const char *key) =0; - virtual void _set(const char *key, const void *value, void **oldvalue) =0; - virtual std::pair_next(size_t& index) =0; + virtual void _set(const void *value) =0; + virtual void _remove(const char *key) =0; + virtual std::pair _next(size_t& index) =0; struct iter { map_base *root; size_t index; @@ -178,80 +206,67 @@ struct map_base { }; }; -struct map_base1_5 : map_base { - struct map_value { - char *key; - void *value; - }; - FlatSet> m; +template +struct map_base2 : map_base { + FlatSet> m; - ~map_base1_5() { + ~map_base2() { clear(); } - void *_get(const char *key) final { - auto it = m.find(std::string_view(key)); - return it != m.end() ? it->value : nullptr; +private: + static constexpr T value_to_void(T v) noexcept requires (std::same_as || std::same_as) { + return v; } - void *_iget(const char *key) { - auto it = m.find(LowercasingView(key)); - return it != m.end() ? it->value : nullptr; + static constexpr char *value_to_void(const T& v) noexcept requires std::same_as { + return const_cast(v.data()); } - void _set(const char *key, const void *value, void **oldvalue) final { + using value_to_void_type = decltype(value_to_void(std::declval())); + + constexpr T void_to_value(void *p) noexcept requires (std::same_as || std::same_as) { + return static_cast(p); + } + constexpr std::string_view void_to_value(void *p) noexcept requires std::same_as { + return static_cast(p); + } +public: + void *_get(const char *key) final { + auto it = m.find(key); + return it != m.end() ? value_to_void(*it) : nullptr; + } + void _set(const void *value) final { if (value) { - map_value mv; - mv.key = const_cast(key); - mv.value = const_cast(value); - auto [it, inserted] = m.insert(mv); - if (inserted) { - if (oldvalue) - *oldvalue = nullptr; - it->key = mystrdup(it->key); - } else { - if (oldvalue) - *oldvalue = it->value; - it->value = mv.value; - } - } else { - auto it = m.find(std::string_view(key)); - if (oldvalue) - *oldvalue = it != m.end() ? it->value : nullptr; - if (it != m.end()) { - delete[] it->key; - m.erase(it); - } + auto mv = void_to_value(const_cast(value)); + m.insert(mv); } } - std::pair_next(size_t& index) final { - map_value kv{0, 0}; + void _remove(const char *key) final { + remove(key); + } + std::pair _next(size_t& index) final { auto it = m.begin() + index; if (it < m.end()) { - kv = *it; index++; + return std::make_pair(to_key(*it), static_cast(value_to_void(*it))); } - return std::make_pair(kv.key, kv.value); + return std::make_pair(std::string_view(), nullptr); } void clear() { - for (auto &mv : m) - delete[] mv.key; m.clear(); } -}; -template -struct map_base2 : map_base1_5 { - using value_type = V; + using value_type = T; struct iterator { using iterator_category = std::bidirectional_iterator_tag; - using value_type = V; + using value_type = value_to_void_type; using difference_type = ptrdiff_t; using pointer = void; - using reference = V; + using reference = value_to_void_type; iterator &operator++() { ++ptr; return *this; } iterator operator++(int) { auto it = *this; ++ptr; return it; } iterator &operator--() { --ptr; return *this; } iterator operator--(int) { auto it = *this; --ptr; return it; } bool operator==(const iterator& other) const = default; - reference operator*() const { return T::to_value(&*ptr); } + reference operator*() const { return value_to_void(*ptr); } decltype(m)::iterator ptr; }; static_assert(std::bidirectional_iterator); @@ -269,58 +284,50 @@ struct map_base2 : map_base1_5 { size_t size() { return m.size(); } -protected: - static const char *to_key(V v) { - return v->key; - } - static V to_value(map_value *v) { - return static_cast(v->value); - } public: - bool has(V v) { - return !!_get(T::to_key(v)); - } - bool add(V v) { - void *old; - _set(T::to_key(v), v, &old); - return !old; - } - bool remove(V v) { - void *old; - (void)_set(T::to_key(v), 0, &old); - return !!old; + template + bool has(const K& k) { + return m.find(k) != m.end(); + } + bool add(const T &v) { + return m.insert(v).second; + } + template + bool remove(const K &k) { + if (auto it = m.find(k); it != m.end()) { + m.erase(it); + return true; + } + return false; } - V get(const char *k) { - return static_cast(_get(k)); + template + T get(const K& k) { + auto it = m.find(k); + return it != m.end() ? *it : T(); } - V iget(const char *k) { - return static_cast(_iget(k)); + T iget(const char *k) { + return get(LowercasingView(k)); } }; -struct Client; -struct clientmap : map_base2 { +struct clientmap : map_base2 { void rename(Client *v, const char *newk) { - remove(v); - _set(newk, v, 0); + if (remove(v)) { + auto pos = m.lower_bound(std::string_view(newk)) - m.begin(); + auto vec = std::move(m).extract(); + vec.insert(vec.begin() + pos, v); + // FIXME: this is actually UB. better do some const_casting and std::rotate + m.replace(std::move(vec)); + } } }; -struct Channel; -struct channelmap : map_base2 { +struct channelmap : map_base2 { }; -struct stringset : map_base2 { -protected: - friend map_base2; - static const char *to_key(const char *v) { - return v; - } - static const char *to_value(map_value *v) { - return v->key; - } -public: - const char *get(const char *k) = delete; - const char *iget(const char *k) = delete; +struct stringset : map_base2 { + template + std::string get(const K& k) = delete; + std::string iget(const char *k) = delete; }; #endif -- 2.56.0