base: add shrink_to_fit to CircularQueue
Allows for reducing the memory usage of CircularQueue: this is important
given the agressive doubling policy used by the queue.
Change-Id: Ica87393ca99c3ac74353c0e35ac52a080ba8e328
diff --git a/include/perfetto/ext/base/circular_queue.h b/include/perfetto/ext/base/circular_queue.h
index d607562..1f69ce5 100644
--- a/include/perfetto/ext/base/circular_queue.h
+++ b/include/perfetto/ext/base/circular_queue.h
@@ -20,6 +20,7 @@
#include <stdint.h>
#include <stdlib.h>
+#include <cstddef>
#include <iterator>
#include "perfetto/base/logging.h"
@@ -234,6 +235,16 @@
void clear() { erase_front(size()); }
+ void shrink_to_fit() {
+ // We only bother shrinking if we can fit in quarter of the capacity we are
+ // currently using. Moreover, don't bother shrinking below 4096 elements as
+ // that will cause a lot of reallocations for little benefit.
+ if (size() > capacity() / 2 || capacity() <= 4096) {
+ return;
+ }
+ ChangeCapacity(capacity() / 2);
+ }
+
T& at(size_t idx) {
PERFETTO_DCHECK(idx < size());
return *Get(begin_ + idx);
@@ -272,6 +283,13 @@
// anything other than crash in this case.
PERFETTO_CHECK(new_capacity > capacity_);
+ ChangeCapacity(new_capacity);
+ }
+
+ void ChangeCapacity(size_t new_capacity) {
+ // We should still have enough space to fit all the elements in the queue.
+ PERFETTO_CHECK(new_capacity >= size());
+
AlignedUniquePtr<T[]> new_vec = AlignedAllocTyped<T[]>(new_capacity);
// Move all elements in the expanded array.
