From 580752d4f13ee237a795d6a11579bf95ae3a4b63 Mon Sep 17 00:00:00 2001
From: David Steele <david.steele@samsung.com>
Date: Fri, 30 Jun 2017 17:26:19 +0100
Subject: [PATCH] Added a memory efficient Circular Queue to Dali

Added a circular queue that is based on top of Dali::Vector.
It's a FIFO queue that grows to the desired size, then prevents
anything being added to it once full. Elements are pushed to the back
of the queue, and popped from the front of the queue.

Change-Id: I26207d6aca5031e7e35f58adbe2ef1f26298ae2a
Signed-off-by: David Steele <david.steele@samsung.com>
---
 automated-tests/src/dali/CMakeLists.txt            |   1 +
 .../src/dali/utc-Dali-CircularQueue.cpp            | 505 +++++++++++++++++++++
 dali/devel-api/common/circular-queue.h             | 200 ++++++++
 dali/devel-api/file.list                           |   1 +
 dali/public-api/dali-core.h                        |   2 +-
 5 files changed, 708 insertions(+), 1 deletion(-)
 create mode 100644 automated-tests/src/dali/utc-Dali-CircularQueue.cpp
 create mode 100644 dali/devel-api/common/circular-queue.h

diff --git a/automated-tests/src/dali/CMakeLists.txt b/automated-tests/src/dali/CMakeLists.txt
index fb890b3..ad992d5 100644
--- a/automated-tests/src/dali/CMakeLists.txt
+++ b/automated-tests/src/dali/CMakeLists.txt
@@ -14,6 +14,7 @@ SET(TC_SOURCES
         utc-Dali-BaseHandle.cpp
         utc-Dali-BufferImage.cpp
         utc-Dali-CameraActor.cpp
+        utc-Dali-CircularQueue.cpp
         utc-Dali-ConditionalWait.cpp
         utc-Dali-ConnectionTracker.cpp
         utc-Dali-Constrainer.cpp
diff --git a/automated-tests/src/dali/utc-Dali-CircularQueue.cpp b/automated-tests/src/dali/utc-Dali-CircularQueue.cpp
new file mode 100644
index 0000000..6d5110c
--- /dev/null
+++ b/automated-tests/src/dali/utc-Dali-CircularQueue.cpp
@@ -0,0 +1,505 @@
+/*
+ * Copyright (c) 2017 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+#define ENABLE_VECTOR_ASSERTS
+
+#include <iostream>
+#include <stdlib.h>
+#include <dali/public-api/dali-core.h>
+#include <dali/public-api/common/circular-queue.h>
+#include <dali-test-suite-utils.h>
+
+using namespace Dali;
+
+void utc_dali_circular_queue_startup(void)
+{
+  test_return_value = TET_UNDEF;
+}
+
+void utc_dali_circular_queue_cleanup(void)
+{
+  test_return_value = TET_PASS;
+}
+
+
+int UtcDaliCircularQueueNew(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+
+  DALI_TEST_EQUALS( cQ.Count(), 0, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueuePushBack01(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+
+  cQ.PushBack( 1 );
+  DALI_TEST_EQUALS( cQ.Count(), 1, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+
+  DALI_TEST_EQUALS( cQ[0], 1, TEST_LOCATION );
+
+  cQ.PushBack( 2 );
+  DALI_TEST_EQUALS( cQ.Count(), 2, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+
+  DALI_TEST_EQUALS( cQ[0], 1, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ[1], 2, TEST_LOCATION );
+
+  END_TEST;
+}
+
+int UtcDaliCircularQueuePushBack02(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.Count(), i+1, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsFull(), i<19?false:true, TEST_LOCATION );
+  }
+
+  END_TEST;
+}
+
+int UtcDaliCircularQueuePushBack03(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  for( int i=0; i<19; ++i)
+  {
+    cQ.PushBack( i );
+  }
+  cQ.PushBack(19);
+  DALI_TEST_EQUALS( cQ.IsFull(), true, TEST_LOCATION );
+
+  for( int i=0; i<10; ++i )
+  {
+    tet_infoline( "Test that the end marker wraps around");
+    (void)cQ.PopFront();
+    cQ.PushBack(20+i);
+    DALI_TEST_EQUALS( cQ.IsFull(), true, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ[0], 1+i, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ[19], 20+i, TEST_LOCATION );
+  }
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueuePushBack04(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  for( int i=0; i<10; ++i)
+  {
+    cQ.PushBack( i );
+    int v = cQ.PopFront();
+    DALI_TEST_EQUALS( v, i, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.Count(), 0, TEST_LOCATION );
+  }
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+
+  // Queue is empty
+
+  cQ.PushBack(10);
+  DALI_TEST_EQUALS( cQ[0], 10, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.Count(), 1, TEST_LOCATION );
+  (void)cQ.PopFront();
+  DALI_TEST_EQUALS( cQ.Count(), 0, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+
+  // Queue is empty, markers should be in middle
+
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    int v = cQ.PopFront();
+    DALI_TEST_EQUALS( v, i, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.Count(), 0, TEST_LOCATION );
+  }
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueuePushBackN(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.Count(), i+1, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsFull(), i<19?false:true, TEST_LOCATION );
+  }
+
+  try
+  {
+    cQ.PushBack( 20 );
+    DALI_TEST_EQUALS( 0, 1, TEST_LOCATION );// Failure
+  }
+  catch( DaliException e )
+  {
+    DALI_TEST_EQUALS( 1, 1, TEST_LOCATION );
+  }
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueueOperatorIndex01(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.Count(), 1+i, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsFull(), i<19?false:true, TEST_LOCATION );
+  }
+
+  for( int i=0; i<20; ++i)
+  {
+    DALI_TEST_EQUALS( cQ[i], i, TEST_LOCATION );
+  }
+
+  END_TEST;
+}
+
+int UtcDaliCircularQueueOperatorIndexN01(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+
+  try
+  {
+    int v = cQ[0];
+    DALI_TEST_EQUALS(v, 1, TEST_LOCATION);
+  }
+  catch( DaliException e )
+  {
+    DALI_TEST_CHECK(true);
+  }
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueuePopFront01(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.Count(), 1+i, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsFull(), i<19?false:true, TEST_LOCATION );
+  }
+
+  for( int i=0; i<20; ++i)
+  {
+    int v = cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.Count(), 19-i, TEST_LOCATION );
+    DALI_TEST_EQUALS( v, i, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), i<19?false:true, TEST_LOCATION );
+  }
+  END_TEST;
+}
+
+int UtcDaliCircularQueuePopFront02(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  for( int i=0; i<10; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ[i], i, TEST_LOCATION );
+    DALI_TEST_EQUALS( cQ.Count(), i+1, TEST_LOCATION );
+  }
+
+  for( int i=0; i<10; ++i)
+  {
+    DALI_TEST_EQUALS( cQ.PopFront(), i, TEST_LOCATION );
+  }
+  DALI_TEST_EQUALS( cQ.Count(), 0, TEST_LOCATION );
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueuePopFrontN01(void)
+{
+  tet_infoline("Try popping from an empty queue");
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+
+  try
+  {
+    (void)cQ.PopFront();
+    DALI_TEST_CHECK( false );
+  }
+  catch( DaliException e )
+  {
+    DALI_TEST_CHECK( true );
+  }
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueuePopFrontN02(void)
+{
+  tet_infoline("Try popping from an empty queue");
+
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+
+  for( int i=0; i<10; ++i)
+  {
+    cQ.PushBack( i );
+    (void)cQ.PopFront();
+  }
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+
+  try
+  {
+    (void)cQ.PopFront();
+    DALI_TEST_CHECK( false );
+  }
+  catch( DaliException e )
+  {
+    DALI_TEST_CHECK( true );
+  }
+
+  END_TEST;
+}
+
+int UtcDaliCircularQueueCount(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  DALI_TEST_EQUALS( cQ.Count(), 0, TEST_LOCATION );
+
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.Count(), 1+i, TEST_LOCATION );
+  }
+
+  END_TEST;
+}
+
+int UtcDaliCircularQueueIsEmpty(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  }
+
+  // Pop off 19 elements
+  for( int i=0; i<19; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  }
+  // pop off last element
+  (void) cQ.PopFront();
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+
+  tet_infoline( "Add half into queue, then remove");
+
+  for( int i=0; i<10; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  }
+  for( int i=0; i<9; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  }
+  (void) cQ.PopFront();
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+
+  tet_infoline("Markers should now be in the middle of the data structure. Try adding 20 again");
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  }
+
+  for( int i=0; i<19; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  }
+  (void) cQ.PopFront();
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueueIsFull(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+  DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.IsFull(), i<19?false:true, TEST_LOCATION );
+  }
+  DALI_TEST_EQUALS( cQ.IsFull(), true, TEST_LOCATION );
+
+  for( int i=0; i<20; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+  }
+
+  tet_infoline( "Add half into queue, then remove");
+
+  for( int i=0; i<10; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+  }
+  for( int i=0; i<10; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+  }
+
+  tet_infoline("Markers should now be in the middle of the data structure. Try adding 20 again");
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.IsFull(), i<19?false:true, TEST_LOCATION );
+  }
+
+  for( int i=0; i<20; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+  }
+
+  END_TEST;
+}
+
+
+int UtcDaliCircularQueueFront(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.Front(), 0, TEST_LOCATION );
+  }
+
+  for( int i=0; i<19; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.Front(), i+1, TEST_LOCATION );
+  }
+  END_TEST;
+}
+
+int UtcDaliCircularQueueBack(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 20 );
+
+  for( int i=0; i<20; ++i)
+  {
+    cQ.PushBack( i );
+    DALI_TEST_EQUALS( cQ.Back(), i, TEST_LOCATION );
+  }
+
+  for( int i=0; i<19; ++i)
+  {
+    (void) cQ.PopFront();
+    DALI_TEST_EQUALS( cQ.Back(), 19, TEST_LOCATION );
+  }
+  END_TEST;
+}
+
+int UtcDaliCircularQueueSize1(void)
+{
+  CircularQueue<int> cQ = CircularQueue<int>( 1 );
+
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+
+  cQ.PushBack( 5 );
+  DALI_TEST_EQUALS( cQ.IsEmpty(), false, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsFull(), true, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.Front(), 5, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.Back(), 5, TEST_LOCATION );
+
+  DALI_TEST_EQUALS( cQ.PopFront(), 5, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsEmpty(), true, TEST_LOCATION );
+  DALI_TEST_EQUALS( cQ.IsFull(), false, TEST_LOCATION );
+
+  END_TEST;
+}
+
+
+  // pushback
+  //  .  => [O]
+  //  se     se
+
+  // [O] => [O] [O]
+  //  se     s   e
+
+  // [O] [O] [O] [O] [O] [ ]  => [O] [O] [O] [O] [O] [O]
+  //  s               e           s                   e
+
+  // [ ] [O] [O] [O] [O] [O]  => [O] [O] [O] [O] [O] [O]
+  //      s               e       e   s
+
+  // [ ] [ ] [O] [ ] [ ] [ ]  => [ ] [ ] [O] [O] [ ] [ ]
+  //          se                          s   e
+
+  // [ ] [ ] [ ] [ ] [ ] [O]  => [O] [ ] [ ] [ ] [ ] [O]
+  //                      se      e                   s
+
+  // [ ] [ ] [ ] [ ] [ ] [ ]  => [ ] [ ] [O] [ ] [ ] [ ]
+  //          se                          se
+
+  // [ ] [ ] [ ] [ ] [ ] [ ]  => [ ] [ ] [ ] [ ] [ ] [0]
+  //                      se                          se
+  // popfront
+  // [O] [O] [O] [O] [O] [O]  => [ ] [O] [O] [O] [O] [O]
+  //  s                   e           s               e
+
+  // [O] [O] [O] [O] [O] [O]  => [O] [O] [O] [O] [ ] [O]
+  //              e   s                       e       s
+
+  // [O] [O] [O] [O] [O] [O]  => [O] [O] [O] [O] [O] [ ]
+  //                  e   s       s               e
+
+  // [ ] [ ] [O] [O] [ ] [ ]  => [ ] [ ] [ ] [O] [ ] [ ]
+  //          s   e                           se
+
+  // [ ] [ ] [ ] [O] [ ] [ ]  => [ ] [ ] [ ] [ ] [ ] [ ]
+  //              se                          se
diff --git a/dali/devel-api/common/circular-queue.h b/dali/devel-api/common/circular-queue.h
new file mode 100644
index 0000000..589bdaa
--- /dev/null
+++ b/dali/devel-api/common/circular-queue.h
@@ -0,0 +1,200 @@
+#ifndef DALI_CIRCULAR_QUEUE_H
+#define DALI_CIRCULAR_QUEUE_H
+
+/*
+ * Copyright (c) 2017 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <dali/public-api/common/dali-vector.h>
+
+namespace Dali
+{
+
+/**
+ * Class to provide a circular growable queue on top of Dali::Vector
+ * It is designed to occupy a fixed block of memory. It does not allow
+ * addition of elements past the start; i.e. it doesn't overwrite.
+ */
+template <typename ElementType>
+class CircularQueue
+{
+public:
+  typedef Dali::Vector<ElementType> Queue;
+
+  /**
+   * Constructor
+   * @param[in] maximumSize The maximum number of elements that the queue can contain
+   */
+  CircularQueue( int maximumSize )
+  : mMaximumSize(maximumSize),
+    mStartMarker(0),
+    mEndMarker(0),
+    mNumberOfElements(0)
+  {
+    mQueue.Reserve(maximumSize);
+  }
+
+  /**
+   * @brief Index operator.
+   *
+   * @param[in] index The index to lookup.
+   *
+   * @warning This method asserts if the user attempts to read outside the
+   * range of elements.
+   */
+  ElementType& operator[](unsigned int index)
+  {
+    unsigned int actualIndex = (mStartMarker + index) % mMaximumSize;
+    DALI_ASSERT_ALWAYS( actualIndex<mQueue.Count() && "Reading outside queue boundary");
+    return mQueue[actualIndex];
+  }
+
+  const ElementType& operator[](unsigned int index) const
+  {
+    unsigned int actualIndex = (mStartMarker + index) % mMaximumSize;
+    DALI_ASSERT_ALWAYS( actualIndex<mQueue.Count() && "Reading outside queue boundary");
+    return mQueue[actualIndex];
+  }
+
+  /**
+   * @brief Push back an element into the queue.
+   *
+   * @param[in] element The element to push to the back of the queue
+   * @warning This method asserts if the user attempts to push more elements
+   * than the maximum size specified in the constructor
+   */
+  void PushBack( const ElementType& element )
+  {
+    DALI_ASSERT_ALWAYS( !IsFull() && "Adding to full queue");
+
+    // Push back if we need to increase the vector count
+    if( mQueue.Count() == 0 || ( mQueue.Count() < mMaximumSize && ! IsEmpty() ) )
+    {
+      mQueue.PushBack(element);
+      if( !IsEmpty() )
+      {
+        ++mEndMarker;
+      }
+      ++mNumberOfElements;
+    }
+    else if( IsEmpty() )
+    {
+      // Don't advance the end marker or increase the vector count
+      mQueue[mEndMarker] = element;
+      ++mNumberOfElements;
+    }
+    else if( !IsFull() )
+    {
+      // vector is at max and there is space: advance end marker
+      ++mEndMarker;
+      mEndMarker %= mMaximumSize;
+      mQueue[ mEndMarker ] = element;
+      ++mNumberOfElements;
+    }
+  }
+
+  /**
+   * @brief Pops an element off the front of the queue
+   *
+   * @return A copy of the element at the front of the queue
+   * @warning This method asserts if the queue is empty
+   */
+  ElementType PopFront()
+  {
+    DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
+    ElementType element;
+
+    if( mNumberOfElements == 1 )
+    {
+      element = mQueue[mStartMarker];
+      mNumberOfElements = 0;
+    }
+    else if( mNumberOfElements > 1 )
+    {
+      element = mQueue[mStartMarker];
+      ++mStartMarker;
+      mStartMarker %= mMaximumSize;
+      --mNumberOfElements;
+    }
+
+    return element;
+  }
+
+  ElementType& Front()
+  {
+    DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
+    return mQueue[mStartMarker];
+  }
+
+  const ElementType& Front() const
+  {
+    DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
+    return mQueue[mStartMarker];
+  }
+
+  ElementType& Back()
+  {
+    DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
+    return mQueue[mEndMarker];
+  }
+
+  const ElementType& Back() const
+  {
+    DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
+    return mQueue[mEndMarker];
+  }
+
+  /**
+   * @brief Predicate to determine if the queue is empty
+   *
+   * @return true if the queue is empty
+   */
+  bool IsEmpty() const
+  {
+    return mNumberOfElements == 0;
+  }
+
+  /**
+   * @brief Predicate to determine if the queue is full
+   *
+   * @return true if the queue is full
+   */
+  bool IsFull() const
+  {
+    return ( mQueue.Count() == mMaximumSize &&
+             mNumberOfElements > 0 &&
+             (mEndMarker + 1) % mMaximumSize == mStartMarker );
+  }
+
+  /**
+   * @brief Get a count of the elements in the queue
+   *
+   * @return the number of elements in the queue.
+   */
+  std::size_t Count() const
+  {
+    return mNumberOfElements;
+  }
+
+private:
+  Queue       mQueue;            ///< The queue of elements
+  std::size_t mMaximumSize;      ///< maximum size of queue
+  std::size_t mStartMarker;      ///< Index of the first element in the queue
+  std::size_t mEndMarker;        ///< Index of the last element in the queue
+  int         mNumberOfElements; ///< Number of valid elements in the queue
+};
+
+} // Dali
+
+#endif //  DALI_CIRCULAR_QUEUE_H
diff --git a/dali/devel-api/file.list b/dali/devel-api/file.list
index 227ce5c..6fa8e0c 100644
--- a/dali/devel-api/file.list
+++ b/dali/devel-api/file.list
@@ -34,6 +34,7 @@ devel_api_core_animation_header_files = \
   $(devel_api_src_dir)/animation/animation-devel.h
 
 devel_api_core_common_header_files = \
+  $(devel_api_src_dir)/common/circular-queue.h \
   $(devel_api_src_dir)/common/dali-vector-devel.h \
   $(devel_api_src_dir)/common/hash.h \
   $(devel_api_src_dir)/common/map-wrapper.h \
diff --git a/dali/public-api/dali-core.h b/dali/public-api/dali-core.h
index 0ebb644..f0a4516 100644
--- a/dali/public-api/dali-core.h
+++ b/dali/public-api/dali-core.h
@@ -2,7 +2,7 @@
 #define __DALI_CORE_H__
 
 /*
- * Copyright (c) 2016 Samsung Electronics Co., Ltd.
+ * Copyright (c) 2017 Samsung Electronics Co., Ltd.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
-- 
2.7.4