[libc][BlockStore] Add back, pop_back and empty methods

[sivachandra]

libc/src/__support/CPP/blockstore.h

138

REVERSE_ORDER only controls the iteration. IMO, back and pop_back are independent of that and should work irrespective of the REVERSE_ORDER.

144

I think it might be better have a static assert like this:

static_assert(__has_trivial_contructor(T) && __has_trivial_destructor(T));

157

Please fix.

[sivachandra]

libc/src/__support/CPP/blockstore.h

138

I just realized I pressed submit while I was still thinking about this. Go ahead and submit this patch with one change: Instead of a static_assert in the function body, use a EnableIf for the return type. I have few other thoughts. They would be best expressed as a separate patch, which I will do after you land this.

[abrachet]

Make pop_back and back work regardless of REVERSE_ORDER

[abrachet]

libc/src/__support/CPP/blockstore.h

138

Ah, didn't see this comment while working on it. How does this look? I can revert to revision 1 if you'd like. But I guess this is probably better

144

I'll do this in a follow up patch and add an IsTrivially[Con|De]structible to TypeTraits.h to put the implementation dependent builtins in a more generic place.

[sivachandra]

libc/src/__support/CPP/blockstore.h

138

Still fine. I don't quite like the for loop on line 56, but fine for now.

[abrachet]

clang-format

[abrachet]

libc/src/__support/CPP/blockstore.h

138

Agreed, this is why I initially had it only for REVERSE_ORDER. In any case there are no current users of BlockStore<T, N, false>

libc/src/__support/CPP/blockstore.h

 //===-- A data structure which stores data in blocks  -----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_SUPPORT_CPP_BLOCKSTORE_H
 #define LLVM_LIBC_SUPPORT_CPP_BLOCKSTORE_H
 
 #include <stddef.h>
 #include <stdint.h>
 #include <stdlib.h>
 
+// TODO: fix our assert.h to make it useable
+#define assert(x)                                                              \
+  if (!(x))                                                                    \
+  __builtin_trap()
+
 namespace __llvm_libc {
 namespace cpp {
 
 // The difference between BlockStore a traditional vector types is that,
 // when more capacity is desired, a new block is added instead of allocating
 // a larger sized array and copying over existing items to the new allocation.
 // Also, the initial block does not need heap allocation. Hence, a BlockStore is
 // suitable for global objects as it does not require explicit construction.
struct Block {
     alignas(T) uint8_t data[BLOCK_SIZE * sizeof(T)] = {0};
     Block *next = nullptr;
   };
 
   Block first;
   Block *current = &first;
   size_t fill_count = 0;
 
+  struct Pair {
+    Block *first, *second;
+  };
+  Pair getLastBlocks() {
+    if (REVERSE_ORDER)
+      return {current, current->next};
+    Block *prev = nullptr;
+    Block *curr = &first;
+    for (; curr->next; prev = curr, curr = curr->next)
+      ;
+    assert(curr == current);
+    return {curr, prev};
+  }
+
+  Block *getLastBlock() { return getLastBlocks().first; }
+
 public:
   constexpr BlockStore() = default;
   ~BlockStore() = default;
 
   class iterator {
     Block *block;
     size_t index;
 
T *new_obj() {
     return obj;
   }
 
   void push_back(const T &value) {
     T *ptr = new_obj();
     *ptr = value;
   }
 
+  T &back() {
+    return *reinterpret_cast<T *>(getLastBlock()->data +
+                                  sizeof(T) * (fill_count - 1));
+  }
+
+  void pop_back() {
+    fill_count--;
+    if (fill_count || current == &first)
+      return;
+    auto [last, prev] = getLastBlocks();
+    if (REVERSE_ORDER) {
+      assert(last == current);
+      current = current->next;
+    } else {
+      assert(prev->next == last);
+      current = prev;
+      current->next = nullptr;
+    }
+    if (last != &first)
+      ::free(last);
+    fill_count = BLOCK_SIZE;
+  }
+
+  bool empty() const { return current == &first && !fill_count; }
+
   iterator begin() {
     if (REVERSE_ORDER)
       return iterator(current, fill_count);
     else
       return iterator(&first, 0);
   }
 
   iterator end() {

libc/test/src/__support/CPP/blockstore_test.cpp

for (auto iter = block_store.begin(); iter != end; ++iter, ++i) {
         ASSERT_EQ(e.b, long(i * 2));
         ASSERT_EQ(e.c, unsigned(i * 3));
       }
     }
     ASSERT_EQ(i, int(ELEMENT_COUNT));
     __llvm_libc::cpp::BlockStore<Element, BLOCK_SIZE, REVERSE>::destroy(
         &block_store);
   }
+
+  template <bool REVERSE> void back_test() {
+    using __llvm_libc::cpp::BlockStore;
+    BlockStore<int, 4, REVERSE> block_store;
+    for (int i = 0; i < 20; i++)
+      block_store.push_back(i);
+    for (int i = 19; i >= 0; i--, block_store.pop_back())
+      ASSERT_EQ(block_store.back(), i);
+    block_store.destroy(&block_store);
+  }
+
+  template <bool REVERSE> void empty_test() {
+    using __llvm_libc::cpp::BlockStore;
+    BlockStore<int, 2, REVERSE> block_store;
+
+    ASSERT_TRUE(block_store.empty());
+    block_store.push_back(1);
+    for (int i = 0; i < 10; i++, block_store.push_back(1))
+      ASSERT_FALSE(block_store.empty());
+    block_store.destroy(&block_store);
+  }
 };
 
 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate4) {
   populate_and_iterate<4, 4, false>();
 }
 
 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate8) {
   populate_and_iterate<4, 8, false>();

 
 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse8) {
   populate_and_iterate<4, 8, true>();
 }
 
 TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse10) {
   populate_and_iterate<4, 10, true>();
 }
+
+TEST_F(LlvmLibcBlockStoreTest, Back) {
+  back_test<false>();
+  back_test<true>();
+}
+
+TEST_F(LlvmLibcBlockStoreTest, Empty) {
+  empty_test<false>();
+  empty_test<true>();
+}