Revert "WIP linked list shared strings"

This got pushed by accident

This reverts commit 2856b99e0914cc7a659977f2b33308cb5b4c9bb7.

4 files changed, 33 insertions, 62 deletions

diff --git a/src/buffer.cc b/src/buffer.cc
index 0b943207..f0205c54 100644
--- a/src/buffer.cc
+++ b/src/buffer.cc
@@ -20,23 +20,6 @@
 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()}
 {}
@@ -59,7 +42,6 @@ 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() });
 
@@ -289,7 +271,6 @@ 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);
@@ -471,7 +452,6 @@ 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};
 }
@@ -493,7 +473,6 @@ 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 df899f44..50423502 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 StringData* line, BufferCoord coord) noexcept;
+    BufferIterator(const StringDataPtr* lines, LineCount line_count, 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_line; }
+    explicit operator bool() const { return m_lines; }
 
     BufferIterator operator+ (ByteCount size) const;
     BufferIterator operator- (ByteCount size) const;
@@ -95,7 +95,9 @@ public:
     using Sentinel = BufferCoord;
 
 private:
-    const StringData* m_line;
+    const StringDataPtr* m_lines;
+    [[no_unique_address]] StringView m_line;
+    [[no_unique_address]] LineCount m_line_count;
     BufferCoord m_coord;
 };
 
@@ -186,7 +188,7 @@ public:
     { return m_lines[line]; }
 
     const StringDataPtr& line_storage(LineCount line) const
-    { return line == line_count() ? m_sentinel : m_lines.get_storage(line); }
+    { return m_lines.get_storage(line); }
 
     // returns an iterator at given coordinates. clamp line_and_column
     BufferIterator iterator_at(BufferCoord coord) const;
@@ -287,7 +289,6 @@ 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 e55cae05..890a5cbd 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 {m_sentinel.get(), end_coord()};
+    return {*this, end_coord()};
 }
 
 [[gnu::always_inline]]
@@ -99,19 +99,23 @@ inline BufferCoord Buffer::end_coord() const
 }
 
 inline BufferIterator::BufferIterator(const Buffer& buffer, BufferCoord coord) noexcept
-    : BufferIterator{buffer.line_storage(coord.line).get(), coord} {}
+    : BufferIterator{buffer.m_lines.data(), buffer.line_count(), coord} {}
 
-inline BufferIterator::BufferIterator(const StringData* line, BufferCoord coord) noexcept
-    : m_line{line},
+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},
       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);
 }
 
@@ -123,62 +127,52 @@ inline bool BufferIterator::operator==(const BufferCoord& coord) const noexcept
 [[gnu::always_inline]]
 inline const char& BufferIterator::operator*() const noexcept
 {
-    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;
+    return m_line[m_coord.column];
 }
 
 inline const char& BufferIterator::operator[](size_t n) const noexcept
 {
-    return *advance(*this, n);
+    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];
 }
 
 inline size_t BufferIterator::operator-(const BufferIterator& iterator) const
 {
-    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;
+    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);
 }
 
 inline BufferIterator BufferIterator::operator+(ByteCount size) const
 {
     kak_assert(*this);
-    return advance(*this, (int)size);
+    return { m_lines, m_line_count, Buffer::advance({m_lines, (size_t)(int)m_line_count}, m_coord, size) };
 }
 
 inline BufferIterator BufferIterator::operator-(ByteCount size) const
 {
-    return advance(*this, -(int)size);
+    return { m_lines, m_line_count, Buffer::advance({m_lines, (size_t)(int)m_line_count}, m_coord, -size) };
 }
 
 inline BufferIterator& BufferIterator::operator+=(ByteCount size)
 {
-    return *this = advance(*this, (int)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;
 }
 
 inline BufferIterator& BufferIterator::operator-=(ByteCount size)
 {
-    return *this = advance(*this, -(int)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;
 }
 
 inline BufferIterator& BufferIterator::operator++()
 {
-    if (++m_coord.column == m_line->length)
+    if (++m_coord.column == m_line.length())
     {
-        m_line = m_line->next;
-        ++m_coord.line;
+        m_line = ((size_t)++m_coord.line < m_line_count) ?
+            m_lines[(size_t)m_coord.line]->strview() : StringView{};
         m_coord.column = 0;
     }
     return *this;
@@ -188,9 +182,8 @@ inline BufferIterator& BufferIterator::operator--()
 {
     if (m_coord.column == 0)
     {
-        m_line = m_line->prev;
-        --m_coord.line;
-        m_coord.column = m_line->length - 1;
+        m_line = m_lines[(size_t)--m_coord.line]->strview();
+        m_coord.column = m_line.length() - 1;
     }
     else
        --m_coord.column;
diff --git a/src/shared_string.hh b/src/shared_string.hh
index 2d39971a..79c34830 100644
--- a/src/shared_string.hh
+++ b/src/shared_string.hh
@@ -15,8 +15,6 @@ 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); }