Refactor ring_buffer interface, add a feature and a test.

* Add a RingBuffer typedef.
* Add the ability to force a memcpy by passing a null ptr. In some cases,
  we know we want a memcpy. This allows us to skip a potential
  intermediate memcpy.
* Add a stress test.

Review URL: https://webrtc-codereview.appspot.com/1111004

git-svn-id: http://webrtc.googlecode.com/svn/trunk@3567 4adac7df-926f-26a2-2b94-8c16560cd09d

3 files changed, 197 insertions, 64 deletions

diff --git a/webrtc/modules/audio_processing/utility/ring_buffer.c b/webrtc/modules/audio_processing/utility/ring_buffer.c
index 8b2b43647e..bc21f85c2b 100644
--- a/webrtc/modules/audio_processing/utility/ring_buffer.c
+++ b/webrtc/modules/audio_processing/utility/ring_buffer.c
@@ -13,7 +13,7 @@
 
 #include "ring_buffer.h"
 
-#include <stddef.h> // size_t
+#include <stddef.h>  // size_t
 #include <stdlib.h>
 #include <string.h>
 
@@ -22,21 +22,21 @@ enum Wrap {
   DIFF_WRAP
 };
 
-typedef struct {
+struct RingBuffer {
   size_t read_pos;
   size_t write_pos;
   size_t element_count;
   size_t element_size;
   enum Wrap rw_wrap;
   char* data;
-} buf_t;
+};
 
 // Get address of region(s) from which we can read data.
 // If the region is contiguous, |data_ptr_bytes_2| will be zero.
 // If non-contiguous, |data_ptr_bytes_2| will be the size in bytes of the second
 // region. Returns room available to be read or |element_count|, whichever is
 // smaller.
-static size_t GetBufferReadRegions(buf_t* buf,
+static size_t GetBufferReadRegions(RingBuffer* buf,
                                    size_t element_count,
                                    void** data_ptr_1,
                                    size_t* data_ptr_bytes_1,
@@ -65,23 +65,25 @@ static size_t GetBufferReadRegions(buf_t* buf,
   return read_elements;
 }
 
-int WebRtc_CreateBuffer(void** handle,
+int WebRtc_CreateBuffer(RingBuffer** handle,
                         size_t element_count,
                         size_t element_size) {
-  buf_t* self = NULL;
-
-  if (handle == NULL) {
+  RingBuffer* self = NULL;
+  if (!handle) {
+    return -1;
+  }
+  if (element_count == 0 || element_size == 0) {
     return -1;
   }
 
-  self = malloc(sizeof(buf_t));
-  if (self == NULL) {
+  self = malloc(sizeof(RingBuffer));
+  if (!self) {
     return -1;
   }
   *handle = self;
 
   self->data = malloc(element_count * element_size);
-  if (self->data == NULL) {
+  if (!self->data) {
     free(self);
     self = NULL;
     return -1;
@@ -93,10 +95,8 @@ int WebRtc_CreateBuffer(void** handle,
   return 0;
 }
 
-int WebRtc_InitBuffer(void* handle) {
-  buf_t* self = (buf_t*) handle;
-
-  if (self == NULL) {
+int WebRtc_InitBuffer(RingBuffer* self) {
+  if (!self) {
     return -1;
   }
 
@@ -110,35 +110,27 @@ int WebRtc_InitBuffer(void* handle) {
   return 0;
 }
 
-int WebRtc_FreeBuffer(void* handle) {
-  buf_t* self = (buf_t*) handle;
-
-  if (self == NULL) {
-    return -1;
+void WebRtc_FreeBuffer(void* handle) {
+  RingBuffer* self = (RingBuffer*)handle;
+  if (!self) {
+    return;
   }
 
   free(self->data);
   free(self);
-
-  return 0;
 }
 
-size_t WebRtc_ReadBuffer(void* handle,
+size_t WebRtc_ReadBuffer(RingBuffer* self,
                          void** data_ptr,
                          void* data,
                          size_t element_count) {
 
-  buf_t* self = (buf_t*) handle;
-
   if (self == NULL) {
     return 0;
   }
   if (data == NULL) {
     return 0;
   }
-  if (data_ptr == NULL) {
-    return 0;
-  }
 
   {
     void* buf_ptr_1 = NULL;
@@ -157,33 +149,35 @@ size_t WebRtc_ReadBuffer(void* handle,
       // |data| and point to it.
       memcpy(data, buf_ptr_1, buf_ptr_bytes_1);
       memcpy(((char*) data) + buf_ptr_bytes_1, buf_ptr_2, buf_ptr_bytes_2);
-      *data_ptr = data;
-    } else {
+      buf_ptr_1 = data;
+    } else if (!data_ptr) {
+      // No wrap, but a memcpy was requested.
+      memcpy(data, buf_ptr_1, buf_ptr_bytes_1);
+    }
+    if (data_ptr) {
+      // |buf_ptr_1| == |data| in the case of a wrap.
       *data_ptr = buf_ptr_1;
     }
 
     // Update read position
-    WebRtc_MoveReadPtr(handle, (int) read_count);
+    WebRtc_MoveReadPtr(self, (int) read_count);
 
     return read_count;
   }
 }
 
-size_t WebRtc_WriteBuffer(void* handle,
+size_t WebRtc_WriteBuffer(RingBuffer* self,
                           const void* data,
                           size_t element_count) {
-
-  buf_t* self = (buf_t*) handle;
-
-  if (self == NULL) {
+  if (!self) {
     return 0;
   }
-  if (data == NULL) {
+  if (!data) {
     return 0;
   }
 
   {
-    const size_t free_elements = WebRtc_available_write(handle);
+    const size_t free_elements = WebRtc_available_write(self);
     const size_t write_elements = (free_elements < element_count ? free_elements
         : element_count);
     size_t n = write_elements;
@@ -206,19 +200,16 @@ size_t WebRtc_WriteBuffer(void* handle,
   }
 }
 
-int WebRtc_MoveReadPtr(void* handle, int element_count) {
-
-  buf_t* self = (buf_t*) handle;
-
-  if (self == NULL) {
+int WebRtc_MoveReadPtr(RingBuffer* self, int element_count) {
+  if (!self) {
     return 0;
   }
 
   {
     // We need to be able to take care of negative changes, hence use "int"
     // instead of "size_t".
-    const int free_elements = (int) WebRtc_available_write(handle);
-    const int readable_elements = (int) WebRtc_available_read(handle);
+    const int free_elements = (int) WebRtc_available_write(self);
+    const int readable_elements = (int) WebRtc_available_read(self);
     int read_pos = (int) self->read_pos;
 
     if (element_count > readable_elements) {
@@ -246,10 +237,8 @@ int WebRtc_MoveReadPtr(void* handle, int element_count) {
   }
 }
 
-size_t WebRtc_available_read(const void* handle) {
-  const buf_t* self = (buf_t*) handle;
-
-  if (self == NULL) {
+size_t WebRtc_available_read(const RingBuffer* self) {
+  if (!self) {
     return 0;
   }
 
@@ -260,12 +249,10 @@ size_t WebRtc_available_read(const void* handle) {
   }
 }
 
-size_t WebRtc_available_write(const void* handle) {
-  const buf_t* self = (buf_t*) handle;
-
-  if (self == NULL) {
+size_t WebRtc_available_write(const RingBuffer* self) {
+  if (!self) {
     return 0;
   }
 
-  return self->element_count - WebRtc_available_read(handle);
+  return self->element_count - WebRtc_available_read(self);
 }
diff --git a/webrtc/modules/audio_processing/utility/ring_buffer.h b/webrtc/modules/audio_processing/utility/ring_buffer.h
index 3c440296dd..ee9a0c6786 100644
--- a/webrtc/modules/audio_processing/utility/ring_buffer.h
+++ b/webrtc/modules/audio_processing/utility/ring_buffer.h
@@ -14,13 +14,15 @@
 #ifndef WEBRTC_MODULES_AUDIO_PROCESSING_UTILITY_RING_BUFFER_H_
 #define WEBRTC_MODULES_AUDIO_PROCESSING_UTILITY_RING_BUFFER_H_
 
-#include <stddef.h> // size_t
+#include <stddef.h>  // size_t
 
-int WebRtc_CreateBuffer(void** handle,
+typedef struct RingBuffer RingBuffer;
+
+int WebRtc_CreateBuffer(RingBuffer** handle,
                         size_t element_count,
                         size_t element_size);
-int WebRtc_InitBuffer(void* handle);
-int WebRtc_FreeBuffer(void* handle);
+int WebRtc_InitBuffer(RingBuffer* handle);
+void WebRtc_FreeBuffer(void* handle);
 
 // Reads data from the buffer. The |data_ptr| will point to the address where
 // it is located. If all |element_count| data are feasible to read without
@@ -28,26 +30,30 @@ int WebRtc_FreeBuffer(void* handle);
 // Otherwise, the data will be copied to |data| (memory allocation done by the
 // user) and |data_ptr| points to the address of |data|. |data_ptr| is only
 // guaranteed to be valid until the next call to WebRtc_WriteBuffer().
+//
+// To force a copying to |data|, pass a NULL |data_ptr|.
+//
 // Returns number of elements read.
-size_t WebRtc_ReadBuffer(void* handle,
+size_t WebRtc_ReadBuffer(RingBuffer* handle,
                          void** data_ptr,
                          void* data,
                          size_t element_count);
 
 // Writes |data| to buffer and returns the number of elements written.
-size_t WebRtc_WriteBuffer(void* handle, const void* data, size_t element_count);
+size_t WebRtc_WriteBuffer(RingBuffer* handle, const void* data,
+                          size_t element_count);
 
 // Moves the buffer read position and returns the number of elements moved.
 // Positive |element_count| moves the read position towards the write position,
 // that is, flushing the buffer. Negative |element_count| moves the read
 // position away from the the write position, that is, stuffing the buffer.
 // Returns number of elements moved.
-int WebRtc_MoveReadPtr(void* handle, int element_count);
+int WebRtc_MoveReadPtr(RingBuffer* handle, int element_count);
 
 // Returns number of available elements to read.
-size_t WebRtc_available_read(const void* handle);
+size_t WebRtc_available_read(const RingBuffer* handle);
 
 // Returns number of available elements for write.
-size_t WebRtc_available_write(const void* handle);
+size_t WebRtc_available_write(const RingBuffer* handle);
 
-#endif // WEBRTC_MODULES_AUDIO_PROCESSING_UTILITY_RING_BUFFER_H_
+#endif  // WEBRTC_MODULES_AUDIO_PROCESSING_UTILITY_RING_BUFFER_H_
diff --git a/webrtc/modules/audio_processing/utility/ring_buffer_unittest.cc b/webrtc/modules/audio_processing/utility/ring_buffer_unittest.cc
new file mode 100644
index 0000000000..eef8b5fbb0
--- /dev/null
+++ b/webrtc/modules/audio_processing/utility/ring_buffer_unittest.cc
@@ -0,0 +1,140 @@
+/*
+ *  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+// TODO(ajm): Make this a comprehensive test.
+
+extern "C" {
+#include "webrtc/modules/audio_processing/utility/ring_buffer.h"
+}
+
+#include <cstdlib>
+#include <ctime>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "webrtc/system_wrappers/interface/scoped_ptr.h"
+
+namespace webrtc {
+
+typedef scoped_ptr_malloc<RingBuffer, WebRtc_FreeBuffer> scoped_ring_buffer;
+
+static void AssertElementEq(int expected, int actual) {
+  ASSERT_EQ(expected, actual);
+}
+
+static int SetIncrementingData(int* data, int num_elements,
+                               int starting_value) {
+  for (int i = 0; i < num_elements; i++) {
+    data[i] = starting_value++;
+  }
+  return starting_value;
+}
+
+static int CheckIncrementingData(int* data, int num_elements,
+                                 int starting_value) {
+  for (int i = 0; i < num_elements; i++) {
+    AssertElementEq(starting_value++, data[i]);
+  }
+  return starting_value;
+}
+
+// We use ASSERTs in this test to avoid obscuring the seed in the case of a
+// failure.
+static void RandomStressTest(int** data_ptr) {
+  const int kNumTests = 100;
+  const int kNumOps = 10000;
+  const int kMaxBufferSize = 1000;
+
+  unsigned int seed = std::time(NULL);
+  printf("seed=%u\n", seed);
+  std::srand(seed);
+  for (int i = 0; i < kNumTests; i++) {
+    const int buffer_size = std::max(rand() % kMaxBufferSize, 1);
+    scoped_array<int> write_data(new int[buffer_size]);
+    scoped_array<int> read_data(new int[buffer_size]);
+    scoped_ring_buffer buffer;
+    ASSERT_EQ(0, WebRtc_CreateBuffer(buffer.accept(), buffer_size,
+                                     sizeof(int)));
+    ASSERT_EQ(0, WebRtc_InitBuffer(buffer.get()));
+    int buffer_consumed = 0;
+    int write_element = 0;
+    int read_element = 0;
+    for (int j = 0; j < kNumOps; j++) {
+      const bool write = rand() % 2 == 0 ? true : false;
+      const int num_elements = rand() % buffer_size;
+      if (write) {
+        const int buffer_available = buffer_size - buffer_consumed;
+        ASSERT_EQ(static_cast<size_t>(buffer_available),
+                  WebRtc_available_write(buffer.get()));
+        const int expected_elements = std::min(num_elements, buffer_available);
+        write_element = SetIncrementingData(write_data.get(), expected_elements,
+                                     write_element);
+        ASSERT_EQ(static_cast<size_t>(expected_elements),
+                  WebRtc_WriteBuffer(buffer.get(), write_data.get(),
+                                     num_elements));
+        buffer_consumed = std::min(buffer_consumed + expected_elements,
+                                   buffer_size);
+      } else {
+        const int expected_elements = std::min(num_elements,
+                                               buffer_consumed);
+        ASSERT_EQ(static_cast<size_t>(buffer_consumed),
+                  WebRtc_available_read(buffer.get()));
+        ASSERT_EQ(static_cast<size_t>(expected_elements),
+                  WebRtc_ReadBuffer(buffer.get(),
+                                    reinterpret_cast<void**>(data_ptr),
+                                    read_data.get(),
+                                    num_elements));
+        int* check_ptr = read_data.get();
+        if (data_ptr) {
+          check_ptr = *data_ptr;
+        }
+        read_element = CheckIncrementingData(check_ptr, expected_elements,
+                                             read_element);
+        buffer_consumed = std::max(buffer_consumed - expected_elements, 0);
+      }
+    }
+  }
+}
+
+TEST(RingBufferTest, RandomStressTest) {
+  int* data_ptr = NULL;
+  RandomStressTest(&data_ptr);
+}
+
+TEST(RingBufferTest, RandomStressTestWithNullPtr) {
+  RandomStressTest(NULL);
+}
+
+TEST(RingBufferTest, PassingNulltoReadBufferForcesMemcpy) {
+  scoped_ring_buffer buffer;
+  const size_t kDataSize = 2;
+  int write_data[kDataSize];
+  int read_data[kDataSize];
+  int* data_ptr;
+
+  ASSERT_EQ(0, WebRtc_CreateBuffer(buffer.accept(), kDataSize, sizeof(int)));
+  ASSERT_EQ(0, WebRtc_InitBuffer(buffer.get()));
+
+  SetIncrementingData(write_data, kDataSize, 0);
+  EXPECT_EQ(kDataSize, WebRtc_WriteBuffer(buffer.get(), write_data, kDataSize));
+  SetIncrementingData(read_data, kDataSize, kDataSize);
+  EXPECT_EQ(kDataSize, WebRtc_ReadBuffer(buffer.get(),
+      reinterpret_cast<void**>(&data_ptr), read_data, kDataSize));
+  // Copying was not necessary, so |read_data| has not been updated.
+  CheckIncrementingData(data_ptr, kDataSize, 0);
+  CheckIncrementingData(read_data, kDataSize, kDataSize);
+
+  EXPECT_EQ(kDataSize, WebRtc_WriteBuffer(buffer.get(), write_data, kDataSize));
+  EXPECT_EQ(kDataSize, WebRtc_ReadBuffer(buffer.get(), NULL, read_data,
+                                         kDataSize));
+  // Passing NULL forces a memcpy, so |read_data| is now updated.
+  CheckIncrementingData(read_data, kDataSize, 0);
+}
+
+}  // namespace webrtc