DBString: Dedup strings
MODIFY
src/dbstring.cpp
src/dbstring.cpp
#include "lcf/dbstring.h"
+#include <unordered_map>
+#include <memory>
+#include <iostream>
namespace lcf {
constexpr DBString::size_type DBString::npos;
+alignas(DBString::size_type) constexpr char DBString::_empty_str[sizeof(size_type)];
-static constexpr size_t AllocSize(size_t len) {
- return sizeof(DBString::size_type) + len + 1;
+struct DBStringData {
+ using size_type = DBString::size_type;
+
+ size_type refcnt;
+ size_type size;
+
+ const char* data() const {
+ return reinterpret_cast<const char*>(this + 1);
}
-static char* Alloc(size_t len) {
- return reinterpret_cast<char*>(::operator new(AllocSize(len)));
+ char* data() {
+ return reinterpret_cast<char*>(this + 1);
}
-static char* Dup(const char* other, size_t size) {
- if (size > 0) {
- auto* s = Alloc(size);
- std::memcpy(s, other, AllocSize(size));
- return s;
+ static size_type alloc_size(StringView str) {
+ return sizeof(DBStringData) + str.size() + 1;
}
- return nullptr;
+
+ static DBStringData* from_data(char* s) {
+ return reinterpret_cast<DBStringData*>(s) - 1;
}
+};
+
+struct DBStringDataDeleter {
+ void operator()(DBStringData* p);
+};
+
+using DBStringDataPtr = std::unique_ptr<DBStringData,DBStringDataDeleter>;
+
+class DBStringAllocator {
+ public:
+ using size_type = DBString::size_type;
+
+ static DBStringDataPtr Alloc(StringView str) {
+ auto* raw = ::operator new(DBStringData::alloc_size(str));
+ auto data = DBStringDataPtr(new (raw) DBStringData());
+ data->refcnt = 1;
+ data->size = str.size();
+ std::memcpy(data->data(), str.data(), data->size);
+ data->data()[data->size] = '\0';
-static void Free(void* p) {
- ::operator delete(p);
+ return data;
}
-DBString::DBString(const char* s, size_t len)
-{
- if (len > 0) {
- auto* ptr = Alloc(len);
- _storage = ptr;
+ static void Free(DBStringData* data) {
+ data->~DBStringData();
+ ::operator delete(data);
+ }
- *reinterpret_cast<size_type*>(ptr) = len;
- ptr += sizeof(size_type);
+ const char* Acquire(StringView str) {
+ if (str.empty()) {
+ return DBString::empty_str();
+ }
- std::memcpy(ptr, s, len);
- ptr += len;
+ auto iter = _map.find(str);
+ if (iter != _map.end()) {
+ iter->second->refcnt += 1;
+ } else {
+ auto ptr = Alloc(str);
+ auto sv = StringView(ptr->data(), ptr->size);
+ // FIXME: Double hash lookup because the key changes..
+ iter = _map.insert({ sv, std::move(ptr) }).first;
+ }
+ return iter->second->data();
+ }
- *ptr = '\0';
+ const char* Dup(const char* s) {
+ if (s != DBString::empty_str()) {
+ auto* data = DBStringData::from_data(const_cast<char*>(s));
+ data->refcnt += 1;
}
+ return s;
+ }
+
+ void Release(StringView str) {
+ if (str.empty()) {
+ // This is needed, due to global DBStrings which are initialized to null.
+ // They may be destroyed *after* DBStringAllocator is destroyed!
+ // FIMXE: To fix this, use a hash table with constexpr default constructor.
+ return;
+ }
+ auto iter = _map.find(str);
+ if (iter != _map.end()) {
+ auto& data = iter->second;
+ data->refcnt -= 1;
+ assert(data->refcnt >= 0);
+ if (data->refcnt == 0) {
+ _map.erase(iter);
+ }
+ }
+ }
+
+ static DBStringAllocator& instance() {
+ static DBStringAllocator alloc;
+ return alloc;
+ }
+ private:
+ DBStringAllocator() = default;
+ private:
+ std::unordered_map<StringView,DBStringDataPtr> _map;
+};
+
+void DBStringDataDeleter::operator()(DBStringData* p) {
+ DBStringAllocator::Free(p);
+}
+
+DBString::DBString(StringView s)
+ : _storage(DBStringAllocator::instance().Acquire(s))
+{
}
DBString::DBString(const DBString& o)
- : _storage(Dup(o._storage, o.size()))
-{ }
+ : _storage(DBStringAllocator::instance().Dup(o._storage))
+{
+}
DBString& DBString::operator=(const DBString& o) {
if (this != &o) {
+ // What is strings are the same, skip double lookup?
_reset();
- _storage = Dup(o._storage, o.size());
+ _storage = DBStringAllocator::instance().Dup(o._storage);
}
return *this;
}
-
-
void DBString::_reset() noexcept {
- Free(_storage);
- _storage = nullptr;
+ assert(_storage != nullptr);
+ DBStringAllocator::instance().Release(*this);
}
} // namespace lcf

MODIFY
src/lcf/dbstring.h
src/lcf/dbstring.h
#include "lcf/string_view.h"
-
namespace lcf {
// A read-only string class optimized for database storage.
@@ -36,22 +35,27 @@ class DBString {
static constexpr size_type npos = size_type(-1);
- constexpr DBString() = default;
- explicit DBString(const std::string& s) : DBString(s.c_str(), s.size()) {}
- explicit DBString(StringView s) : DBString(s.data(), s.size()) {}
+ // FIXME: When the allocator constructor is constexpr, this can be also
+ DBString() : DBString(StringView()) {}
+ explicit DBString(StringView s);
+ explicit DBString(const std::string& s) : DBString(StringView(s)) {}
// Explicit construct for general const char*
- explicit DBString(const char* s) : DBString(s, std::strlen(s)) {}
+ explicit DBString(const char* s) : DBString(StringView(s)) {}
// Implicit constructor to capture string literals
template <size_t N>
DBString(const char(&literal)[N]) : DBString(StringView(literal)) {}
- DBString(const char* s, size_t len);
+ DBString(const char* s, size_t len) : DBString(StringView(s, len)) {}
- DBString(const DBString&);
+ DBString(const DBString& o);
DBString& operator=(const DBString&);
DBString(DBString&&) noexcept;
DBString& operator=(DBString&&) noexcept;
+ void swap(DBString& o) noexcept {
+ std::swap(_storage, o._storage);
+ }
+
~DBString() { _reset(); }
explicit operator std::string() const { return std::string(data(), size()); }
@@ -60,7 +64,7 @@ class DBString {
char operator[](size_type i) const { return data()[i]; }
char front() const { return (*this)[0]; }
char back() const { return (*this)[size()-1]; }
- const char* data() const;
+ const char* data() const { return _storage; }
const char* c_str() const { return data(); }
iterator begin() const { return data(); }
@@ -71,10 +75,15 @@ class DBString {
bool empty() const { return size() == 0; }
size_type size() const;
+
+ static constexpr const char* empty_str() {
+ return _empty_str + sizeof(size_type);
+ }
private:
void _reset() noexcept;
private:
- char* _storage = nullptr;
+ alignas(size_type) static constexpr char _empty_str[sizeof(size_type)] = {};
+ const char* _storage = empty_str();
};
// This should be used over the conversion operator, so we can track all dbstr -> str instances
@@ -116,28 +125,24 @@ template <> struct hash<lcf::DBString> {
namespace lcf {
inline DBString::DBString(DBString&& o) noexcept
- : _storage(o._storage)
{
- o._storage = nullptr;
+ std::swap(_storage, o._storage);
}
inline DBString& DBString::operator=(DBString&& o) noexcept {
+ return operator=(o);
if (this != &o) {
- if (_storage) {
+ if (!empty()) {
_reset();
}
_storage = o._storage;
- o._storage = nullptr;
+ o._storage = empty_str();
}
return *this;
}
-inline const char* DBString::data() const {
- return _storage ? _storage + sizeof(size_type) : nullptr;
-}
-
inline DBString::size_type DBString::size() const {
- return _storage ? *reinterpret_cast<const size_type*>(_storage) : 0;
+ return *(reinterpret_cast<const size_type*>(_storage) - 1);
}
} // namespace lcf

DBString: Dedup strings