WIP linked list shared strings

4 files changed, 62 insertions, 33 deletions

diff --git a/src/buffer.cc b/src/buffer.cc
index f0205c54..0b943207 100644
--- a/src/buffer.cc
+++ b/src/buffer.cc
@@ -20,6 +20,23 @@
 namespace Kakoune
 {
 
+void fix_links(BufferLines& lines, StringData* sentinel)
+{
+    StringData* prev = nullptr;
+    for (auto& ptr : lines)
+    {
+        ptr->prev = prev;
+        if (prev)
+            prev->next = ptr.get();
+        prev = ptr.get();
+    }
+    if (prev)
+    {
+        prev->next = sentinel;
+        sentinel->prev = prev;
+    }
+}
+
 Buffer::HistoryNode::HistoryNode(HistoryId parent)
     : parent{parent}, committed{Clock::now()}
 {}
@@ -42,6 +59,7 @@ Buffer::Buffer(String name, Flags flags, BufferLines lines,
                    line->data()[line->length-1] == '\n');
     #endif
     static_cast<BufferLines&>(m_lines) = std::move(lines);
+    fix_links(m_lines, m_sentinel.get());
 
     m_changes.push_back({ Change::Insert, {0,0}, line_count() });
 
@@ -271,6 +289,7 @@ void Buffer::reload(BufferLines lines, ByteOrderMark bom, EolFormat eolformat, F
         m_lines.erase(write_it, m_lines.end());
     }
 
+    fix_links(m_lines, m_sentinel.get());
     commit_undo_group();
 
     options().get_local_option("eolformat").set(eolformat);
@@ -452,6 +471,7 @@ BufferRange Buffer::do_insert(BufferCoord pos, StringView content)
     const auto end = at_end ? line_count()
                             : BufferCoord{ last_line, m_lines[last_line].length() - suffix.length() };
 
+    fix_links(m_lines, m_sentinel.get());
     m_changes.push_back({ Change::Insert, pos, end });
     return {pos, end};
 }
@@ -473,6 +493,7 @@ BufferCoord Buffer::do_erase(BufferCoord begin, BufferCoord end)
     if (new_line)
         m_lines.get_storage(begin.line) = std::move(new_line);
 
+    fix_links(m_lines, m_sentinel.get());
     return begin;
 }
 
diff --git a/src/buffer.hh b/src/buffer.hh
index 50423502..df899f44 100644
--- a/src/buffer.hh
+++ b/src/buffer.hh
@@ -66,17 +66,17 @@ public:
 
     BufferIterator() = default;
     BufferIterator(const Buffer& buffer, BufferCoord coord) noexcept;
-    BufferIterator(const StringDataPtr* lines, LineCount line_count, BufferCoord coord) noexcept;
+    BufferIterator(const StringData* line, BufferCoord coord) noexcept;
 
     bool operator== (const BufferIterator& iterator) const noexcept;
     auto operator<=>(const BufferIterator& iterator) const noexcept;
     bool operator== (const BufferCoord& coord) const noexcept;
 
-    const char& operator* () const noexcept;
+    const char& operator*() const noexcept;
     const char& operator[](size_t n) const noexcept;
     size_t operator- (const BufferIterator& iterator) const;
 
-    explicit operator bool() const { return m_lines; }
+    explicit operator bool() const { return m_line; }
 
     BufferIterator operator+ (ByteCount size) const;
     BufferIterator operator- (ByteCount size) const;
@@ -95,9 +95,7 @@ public:
     using Sentinel = BufferCoord;
 
 private:
-    const StringDataPtr* m_lines;
-    [[no_unique_address]] StringView m_line;
-    [[no_unique_address]] LineCount m_line_count;
+    const StringData* m_line;
     BufferCoord m_coord;
 };
 
@@ -188,7 +186,7 @@ public:
     { return m_lines[line]; }
 
     const StringDataPtr& line_storage(LineCount line) const
-    { return m_lines.get_storage(line); }
+    { return line == line_count() ? m_sentinel : m_lines.get_storage(line); }
 
     // returns an iterator at given coordinates. clamp line_and_column
     BufferIterator iterator_at(BufferCoord coord) const;
@@ -289,6 +287,7 @@ private:
         StringView back() const { return BufferLines::back()->strview(); }
     };
     LineList m_lines;
+    StringDataPtr m_sentinel = StringData::create("");
 
     String m_name;
     String m_display_name;
diff --git a/src/buffer.inl.hh b/src/buffer.inl.hh
index 890a5cbd..e55cae05 100644
--- a/src/buffer.inl.hh
+++ b/src/buffer.inl.hh
@@ -60,7 +60,7 @@ inline BufferIterator Buffer::begin() const
 
 inline BufferIterator Buffer::end() const
 {
-    return {*this, end_coord()};
+    return {m_sentinel.get(), end_coord()};
 }
 
 [[gnu::always_inline]]
@@ -99,23 +99,19 @@ inline BufferCoord Buffer::end_coord() const
 }
 
 inline BufferIterator::BufferIterator(const Buffer& buffer, BufferCoord coord) noexcept
-    : BufferIterator{buffer.m_lines.data(), buffer.line_count(), coord} {}
+    : BufferIterator{buffer.line_storage(coord.line).get(), coord} {}
 
-inline BufferIterator::BufferIterator(const StringDataPtr* lines, LineCount line_count, BufferCoord coord) noexcept
-    : m_lines{lines},
-      m_line{coord.line < line_count ? m_lines[(size_t)coord.line]->strview() : StringView{}},
-      m_line_count{line_count},
+inline BufferIterator::BufferIterator(const StringData* line, BufferCoord coord) noexcept
+    : m_line{line},
       m_coord{coord} {}
 
 inline bool BufferIterator::operator==(const BufferIterator& iterator) const noexcept
 {
-    kak_assert(m_lines == iterator.m_lines);
     return m_coord == iterator.m_coord;
 }
 
 inline auto BufferIterator::operator<=>(const BufferIterator& iterator) const noexcept
 {
-    kak_assert(m_lines == iterator.m_lines);
     return (m_coord <=> iterator.m_coord);
 }
 
@@ -127,52 +123,62 @@ inline bool BufferIterator::operator==(const BufferCoord& coord) const noexcept
 [[gnu::always_inline]]
 inline const char& BufferIterator::operator*() const noexcept
 {
-    return m_line[m_coord.column];
+    return m_line->data()[(size_t)(int)m_coord.column];
+}
+
+inline BufferIterator advance(BufferIterator iterator, int n)
+{
+    for (; n > 0; --n)
+        ++iterator;
+    for (; n < 0; ++n)
+        --iterator;
+    return iterator;
 }
 
 inline const char& BufferIterator::operator[](size_t n) const noexcept
 {
-    auto coord = Buffer::advance({m_lines, (size_t)(int)m_line_count}, m_coord, n);
-    return m_lines[(size_t)coord.line]->strview()[coord.column];
+    return *advance(*this, n);
 }
 
 inline size_t BufferIterator::operator-(const BufferIterator& iterator) const
 {
-    kak_assert(m_lines == iterator.m_lines);
-    return (size_t)Buffer::distance({m_lines, (size_t)(int)m_line_count}, iterator.m_coord, m_coord);
+    size_t distance = 0;
+    auto* line = iterator.m_line;
+    while (line != m_line)
+    {
+        distance += line->length - (line == iterator.m_line ? (int)iterator.m_coord.column : 0);
+    }
+    distance += (int)(m_coord.column - (line == iterator.m_line ? (int)iterator.m_coord.column : 0));
+    return distance;
 }
 
 inline BufferIterator BufferIterator::operator+(ByteCount size) const
 {
     kak_assert(*this);
-    return { m_lines, m_line_count, Buffer::advance({m_lines, (size_t)(int)m_line_count}, m_coord, size) };
+    return advance(*this, (int)size);
 }
 
 inline BufferIterator BufferIterator::operator-(ByteCount size) const
 {
-    return { m_lines, m_line_count, Buffer::advance({m_lines, (size_t)(int)m_line_count}, m_coord, -size) };
+    return advance(*this, -(int)size);
 }
 
 inline BufferIterator& BufferIterator::operator+=(ByteCount size)
 {
-    m_coord = Buffer::advance({m_lines, (size_t)(int)m_line_count}, m_coord, size);
-    m_line = m_lines[(size_t)m_coord.line]->strview();
-    return *this;
+    return *this = advance(*this, (int)size);
 }
 
 inline BufferIterator& BufferIterator::operator-=(ByteCount size)
 {
-    m_coord = Buffer::advance({m_lines, (size_t)(int)m_line_count}, m_coord, -size);
-    m_line = m_lines[(size_t)m_coord.line]->strview();
-    return *this;
+    return *this = advance(*this, -(int)size);
 }
 
 inline BufferIterator& BufferIterator::operator++()
 {
-    if (++m_coord.column == m_line.length())
+    if (++m_coord.column == m_line->length)
     {
-        m_line = ((size_t)++m_coord.line < m_line_count) ?
-            m_lines[(size_t)m_coord.line]->strview() : StringView{};
+        m_line = m_line->next;
+        ++m_coord.line;
         m_coord.column = 0;
     }
     return *this;
@@ -182,8 +188,9 @@ inline BufferIterator& BufferIterator::operator--()
 {
     if (m_coord.column == 0)
     {
-        m_line = m_lines[(size_t)--m_coord.line]->strview();
-        m_coord.column = m_line.length() - 1;
+        m_line = m_line->prev;
+        --m_coord.line;
+        m_coord.column = m_line->length - 1;
     }
     else
        --m_coord.column;
diff --git a/src/shared_string.hh b/src/shared_string.hh
index 79c34830..2d39971a 100644
--- a/src/shared_string.hh
+++ b/src/shared_string.hh
@@ -15,6 +15,8 @@ struct StringData : UseMemoryDomain<MemoryDomain::SharedString>
 {
     uint32_t refcount;
     const int length;
+    StringData* prev = nullptr;
+    StringData* next = nullptr;
 
     [[gnu::always_inline]]
     const char* data() const { return reinterpret_cast<const char*>(this + 1); }