Generic Gap Buffer data structure

base/gap_buffer.h

Index: base/gap_buffer.h
diff --git a/base/gap_buffer.h b/base/gap_buffer.h
new file mode 100644
index 0000000000000000000000000000000000000000..b1829065706298fa1e1e24214efe4ea30c7a87fa
--- /dev/null
+++ b/base/gap_buffer.h
@@ -0,0 +1,218 @@
+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_GAP_BUFFER_H_
+#define BASE_GAP_BUFFER_H_
+#pragma once
+
+#include <stdio.h>

[tfarina, 2010/11/18 12:03:23]

Hum? Why do you need this here? If it is for memmove you can include string.h
instead.

[varunjain, 2010/11/18 17:53:44]

removed

+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/logging.h"

[tfarina, 2010/11/18 12:03:23]

Do you this include here?

[varunjain, 2010/11/18 17:53:44]

I had NOTIMPLEMENTED() in one of the methods which I need this for. It somehow
got lost... but its back now.

+#include "base/scoped_ptr.h"
+
+namespace base {
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// This class implements a standard GapBuffer

[rjkroege, 2010/11/18 19:34:28]

I don't understand the "why" of your API.

I think that a gap buffer needs:
* MoveGapBy(int) where the int can be positive (forward) or negative (back)
* SetGapTo(unsigned) where the unsigned is a position into the contained string
* GetString which needs to be aligned with the downstream consumer's needs
(DrawStringInt) so ought to be a wstring perhaps.
* InsertRune (where rune has its plan9 meaning) and is a natural cast from
character code that you get from the event.
* A constructor taking a string.

I was (and remain) slightly doubtful that we need this to be templated and claim
that it would be easier to write without them. (Despite talking about how
important it is to learn template-fu yesterday. :-)

Please also be explicit about how you intend to handle UTF-blah because the user
of this class will want to operate in terms of character position. Based on the
wstring downstream, UTF-16 might be appropriate.

How will you manage the storage of metrics?

+// (http://en.wikipedia.org/wiki/Gap_buffer)
+//

[sky, 2010/11/18 18:26:07]

You need some description of this class rather than a pointer to a wikipedia
article. At least describe the core concepts you refer to in descriptions like
buffer and gap.

+////////////////////////////////////////////////////////////////////////////////
+template<class T>

[sky, 2010/11/18 18:26:07]

We've trying to move all strings to string16. Could this be written only in
terms of string16?

+class GapBuffer {
+ public:
+  // Constructor. The initial size of the buffer can be specified in the

[tfarina, 2010/11/18 12:03:23]

Please, can you move the implementation of all these method to the source file?
With this is more easy to read the API of GapBuffer.

[varunjain, 2010/11/18 17:53:44]

This is a template.. if I move the implementation to a source file linker will
not be able to generate the specific source

+  // argument (defaults to 10).
+  explicit GapBuffer(int size) {

[sky, 2010/11/18 18:26:07]

Is anyone really going to want to specify the initial buffer size? Should this
instead take no args?

+    if (size < kMinResizeAmount) {
+      size = kMinResizeAmount;
+    }
+
+    buffer_.reset(new T[size]);
+    buffer_size_ = size;
+    gap_start_ = 0;
+    gap_end_ = buffer_size_;
+  }
+
+  // Constructor. Initializes the gap buffer with values from the input buffer.
+  GapBuffer(const T* buffer, int buffer_size) {

[sky, 2010/11/18 18:26:07]

Use member initialize list for setting all fields.

+    buffer_size_ = buffer_size + kMinResizeAmount;
+    buffer_.reset(new T[buffer_size_]);
+    gap_start_ = buffer_size;
+    gap_end_ = buffer_size_;
+    memmove(buffer_.get(), buffer, sizeof(T) * buffer_size);
+  }
+
+  // Moves the Gap left by "count" positions (until it hits the start of the

[sky, 2010/11/18 18:26:07]

Gap -> gap

[rjkroege, 2010/11/18 19:34:28]

you can refactor move-left and move-right  into 1

+  // buffer). The gap size remains constant. Contents from the start of the gap
+  // are moved to the end.
+  void MoveGapLeft(int count) {

[sky, 2010/11/18 18:26:07]

Why do we have the move left/right. Can't it just be SetGapPosition() and
internally you do whatever you need to do?

+    if (buffer_.get() && gap_start_ > 0) {

[sky, 2010/11/18 18:26:07]

Why do you check buffer_.get() here?

+      int new_gap_start = (gap_start_ >= count)? gap_start_ - count : 0;
+      int num_elements = gap_start_ - new_gap_start;
+      memmove(buffer_.get() + gap_end_ - num_elements,
+          buffer_.get() + new_gap_start, sizeof(T) * num_elements);
+      gap_start_ = new_gap_start;
+      gap_end_ -= num_elements;
+    }
+  }
+
+  // Moves the Gap right by "count" positions (until it hits the end of the
+  // buffer). The gap size remains constant. Contents from the end of the gap
+  // are moved to the start.
+  void MoveGapRight(int count) {
+    if (gap_end_ < buffer_size_) {
+      int new_gap_end = (gap_end_ + count > buffer_size_)? buffer_size_
+          : gap_end_ + count;
+      int num_elements = new_gap_end - gap_end_;
+      memmove(buffer_.get() + gap_start_, buffer_.get() + gap_end_,
+          sizeof(T) * num_elements);
+      gap_start_ += num_elements;
+      gap_end_ = new_gap_end;
+    }
+  }
+
+  // Moves the Gap to the left until its just after the first occurrence of
+  // "object". If object is not found it moves the gap all the way to the
+  // beginning of the buffer.
+  void MoveGapLeftTo(T object) {

[sky, 2010/11/18 18:26:07]

Why is this and MoveGapRightTo needed?

+    for (; gap_start_ > 0 && buffer_[gap_start_ - 1] != object;) {
+      MoveGapLeftByOne();
+    }
+  }
+
+  // Moves the Gap to the right until its just after the first occurrence of
+  // "object". If object is not found it moves the gap all the way to the end
+  // of the buffer.
+  void MoveGapRightTo(T object) {
+    for (; gap_end_ < buffer_size_ && buffer_[gap_end_] != object;) {
+      MoveGapRightByOne();
+    }
+    // Move one more space to get after the occurrence on "object".
+    MoveGapRight(1);
+  }
+
+  // Inserts one element in the gap at the beginning. Gap size decreases by one.
+  // If gap is full, it resizes the buffer_ to create gap and then inserts.
+  void InsertAtGapStart(T object) {
+    if (gap_start_ < gap_end_) {
+      buffer_[gap_start_] = object;
+      gap_start_++;
+    } else {
+      ResizeBuffer();
+      InsertAtGapStart(object);
+    }
+  }
+
+  // Removes an element from the beginning of the gap increasing the gap size
+  // by one (unless the gap is already at the beginning of the buffer). Returns
+  // a pointer to the element removed.
+  const T* RemoveFromGapStart() {
+    if (gap_start_ > 0) {
+      gap_start_--;
+      return buffer_.get() + gap_start_;
+    } else {
+      return NULL;
+    }
+  }
+
+  // Removes an element from the end of the gap increasing the gap size
+  // by one (unless the gap is already at the end of the buffer). Returns a
+  // pointer to the element removed.
+  const T* RemoveFromGapEnd() {
+    if (gap_end_ < buffer_size_) {
+      gap_end_++;
+      return buffer_.get() + gap_end_ - 1;
+    } else {
+      return NULL;
+    }
+  }
+
+  // Replaces the part of the buffer from "start" (inclusive) upto "end" with
+  // "replacement". Resizes the gap appropriately. <start-end> should not
+  // overlap with the gap.
+  // FIXME: implement this.
+  void Replace(int start, int end, T replacement) { }
+
+  // Gets the contents of the buffer (removing the gap) in vector "contents".
+  void GetContents(std::vector<T>* contents) {

[rjkroege, 2010/11/18 19:34:28]

ultimately, we'll want strings right? not a vector?

+    contents->clear();
+    int size = GetCurrentSize();
+    if (size) {
+      int i, j;
+      for (i = 0; i < gap_start_; i++) {
+        (*contents).push_back(buffer_[i]);
+      }
+      for (j = gap_end_; j < buffer_size_; j++, i++) {
+        (*contents).push_back(buffer_[j]);
+      }
+    }
+  }
+
+  // Gets the current number of elements in the buffer.
+  int GetCurrentSize() {
+    return buffer_size_ - (gap_end_ - gap_start_);
+  }
+
+  // Gets the size of the underlying buffer.
+  int GetBufferSize() {
+    return buffer_size_;
+  }
+
+  // Gets the gap_start_ index (essentially the current cursor position).
+  int GetGapStart() {
+    return gap_start_;
+  }
+
+ private:
+  // Increases the size of the buffer by 10% of current size. Unsafe.. assumes
+  // that the buffer is already allocated. Should not be invoked for

[rjkroege, 2010/11/18 19:34:28]

you should assert that the buffer has been initialized yes?

+  // un-initialized buffer.
+  // FIXME: explore more efficient resizing.

[rjkroege, 2010/11/18 19:34:28]

Given that this is a buffer that is backing the omnibox, I would recommend
growing it in 4kB increments.

+  void ResizeBuffer() {
+    int size_increment = (buffer_size_ / 10.0 < kMinResizeAmount)?
+        kMinResizeAmount : buffer_size_ / 10.0;
+    int new_size = buffer_size_ + size_increment;
+    T* new_buffer = new T[new_size];
+    memmove(new_buffer, buffer_.get(), sizeof(T) * gap_start_);
+    memmove(new_buffer + gap_start_ + new_size, buffer_.get() + gap_end_,
+        sizeof(T) * (buffer_size_ - gap_end_));
+    gap_end_ = new_size - (buffer_size_ - gap_end_);
+    buffer_size_ = new_size;
+    buffer_.reset(new_buffer);
+  }
+
+  // Internal helper function. Should not be used on its own as it doesnot do
+  // any sanity checks. Use MoveGapLeft() or MoveGapLeftTo() instead.
+  void MoveGapLeftByOne() {
+    gap_start_--;
+    gap_end_--;
+    buffer_[gap_end_] = buffer_[gap_start_];
+  }
+
+  // Internal helper function. Should not be used on its own as it doesnot do
+  // any sanity checks. Use MoveGapRight() or MoveGapRightTo() instead.
+  void MoveGapRightByOne() {
+    buffer_[gap_start_] = buffer_[gap_end_];
+    gap_start_++;
+    gap_end_++;
+  }
+
+  scoped_array<T> buffer_;
+  int buffer_size_;
+  int gap_start_;
+  int gap_end_;
+
+  // In case of resizing the buffer, we will increase the length at least by
+  // kMinResizeAmount to avoid frequent resizing.
+  static const int kMinResizeAmount = 10;
+
+  DISALLOW_COPY_AND_ASSIGN(GapBuffer);
+};
+
+}  // namespace

[tfarina, 2010/11/18 12:03:23]

// namespace base

[varunjain, 2010/11/18 17:53:44]

Done.

+
+#endif  // BASE_GAP_BUFFER_H_