Merge lp:~smspillaz/compiz-core/compiz-core.fix_969108.2 into lp:compiz-core

[Sam Spilsbury]

== Problem ==

moveHandleMotionEvent could cause the window geometry to be updated several times a second which would have run-on effects in calling moveNotify a lot in the plugins. This would cause an unnessary performance hit.

== Solution ==

Added a new releasable queue structure, which allows observers to lock the queue and trigger releases at a later point and an accumulator to accumulate values to release in the future. Use this in order to queue up motion on windows and release in synchronization with repaints so that we only update the geometries where it matters.

== Tests ==

Test Suite included.

[Daniel van Vugt (vanvugt)]

Again, I can't endorse a major rewrite of critical functionality this late.

review: Abstain

[Daniel van Vugt (vanvugt)]

Also, this 1000 lines of code seems to be aimed at solving a problem that I planned on solving myself in only a dozen or so lines. Is it really necessary to introduce such vast complexity?

[Sam Spilsbury (smspillaz)]

1) This isn't a rewrite
2) The only functional changes are in the form of

42 if (state & CompAction::StateCancel)
43 - ms->w->move (ms->savedX - ms->w->geometry ().x (),
44 - ms->savedY - ms->w->geometry ().y (), false);
45 + ms->addMovement (MoveWindow::get (ms->w), CompPoint (ms->savedX - ms->w->geometry ().x (),
46 + ms->savedY - ms->w->geometry ().y ()));
47
48 ms->w->syncPosition ();
49
50 @@ -484,8 +486,7 @@
51
52 if (dx || dy)
53 {
54 - w->move (wX + dx - w->geometry ().x (),
55 - wY + dy - w->geometry ().y (), false);
56 + ms->addMovement (MoveWindow::get (w), CompPoint (dx, dy));
62
63 bool
64 +MoveWindow::doRelease (const CompPoint &d)
65 +{
66 + window->move (d.x (), d.y (), false);
67 + return true;
68 +}
69 +
70 +void
71 +MoveScreen::dispatchDamage (compiz::queues::QueueReleaseInterface *releasable)
72 +{
73 + MoveWindow *mw = static_cast <MoveWindow *> (releasable);
74 + mw->cWindow->addDamage ();
75 +}
76 +
77 +bool
78 MoveScreen::registerPaintHandler(compiz::composite::PaintHandler *pHnd)
79 {
80 hasCompositing = true;
81 @@ -677,9 +692,27 @@
82 MoveScreen::unregisterPaintHandler()
83 {
84 hasCompositing = false;
85 + queueLock.reset ();
86 cScreen->unregisterPaintHandler ();
87 }
88
89 +void
90 +MoveScreen::preparePaint (int ms)
91 +{
92 + if (queueLock)
93 + queueLock->unlock ();
94 +
95 + cScreen->preparePaint (ms);
96 + cScreen->preparePaintSetEnabled (this, false);
97 +}
98 +
99 +void
100 +MoveScreen::addMovement (MoveWindow *mw, const CompPoint &d)
101 +{
102 + cScreen->preparePaintSetEnabled (this, true);
103 + pendingMovements->addPending (d, mw);
104 +}
105 +
113 - yConstrained (false)
114 + yConstrained (false),
115 + pendingMovementsStorage (new compiz::queues::impl::AccumulatedMapStorage <CompPoint> ()),
116 + pendingMovements (new compiz::queues::impl::Queue <CompPoint> (boost::shared_static_cast <compiz::queues::QueueStorageInterface <CompPoint> > (pendingMovementsStorage)))
123 CompositeScreenInterface::setHandler (cScreen);
124 + queueLock = pendingMovements->obtainLock (boost::bind (&MoveScreen::dispatchDamage, this, _1));
125 + cScreen->preparePaintSetEnabled (this, false);

That's fairly small

3) The reason the diff is so large is because 100 of 1200 lines are cmake and 600 of the 1200 lines are tests
4) This solution is aimed at making releasable queues more generic
5) Its blocking other work

Plenty of good reasons to merge this before precise.

[Tim Penhey (thumper)]

Making destructors pure virtual is only really necessary if there are no other pure virtual methods and you want to make the class abstract. Other than that they are just a PITA.

[Mikkel Kamstrup Erlandsen (kamstrup)]

I don't know the compiz coding standards, but for abstract code like this I'd expect at the very least 2 comments: 1) In queue.cpp/h explaining what the general idea behind all the interfaces are, 2) in the move.cpp explaining what it is using the clever queues for (ie. why a bog standard list is not good enough)

[Alan Griffiths (alan-griffiths)]

It isn't obvious what contracts the template interfaces QueueStorageInterface, QueueInterface, and QueueLockInterface represent. E.g. I'd expect a lock to have "lock()" and "unlock()" methods or similar. Do they need to be templates?

The pure destructors and NVPI clutter up the code.

In MoveScreen the new variables pendingMovementsStorage, pendingMovements and queueLock could be private. (I suspect others could too - what is it with compiz and public data members?)

I don't see why pendingMovementsStorage is a member variable - it's only use is in initalizing pendingMovements. In any case, it should be of the usage type - shared_ptr<QueueStorageInterface> not the implementation type.

There is no need for pendingMovements to be allocated on the heap instead of being a member variable. (The same change for pendingMovementsStorage which would require a signature change for compiz::queues::impl::Queue::Queue - but that's minor.)

[Sam Spilsbury (smspillaz)]

> It isn't obvious what contracts the template interfaces QueueStorageInterface,
> QueueInterface, and QueueLockInterface represent. E.g. I'd expect a lock to
> have "lock()" and "unlock()" methods or similar. Do they need to be
> templates?

QueueReleaseInterface, QueueInterface and QueueStorageInterface need to know the type that is being stored. As such, they are templates.

QueueLockInterface takes a lock on a QueueUnlockableInterface on construction. Eg, the very act of constructing a QueueLockInterface means that it will receive callbacks and block dispatching of the queue items until the client calls unlock () on it, at which point will call a method in QueueUnlockableInterface to decrement the lock count.

QueueStorageInterface is the abstraction of how queued items are stored.

QueueInterface is the interface to the Queue itself, eg, pushing data into the queue.

>
> The pure destructors and NVPI clutter up the code.
>
> In MoveScreen the new variables pendingMovementsStorage, pendingMovements and
> queueLock could be private. (I suspect others could too - what is it with
> compiz and public data members?)

Ack, although I believe we're using this from MoveWindow.

>
> I don't see why pendingMovementsStorage is a member variable - it's only use
> is in initalizing pendingMovements. In any case, it should be of the usage
> type - shared_ptr<QueueStorageInterface> not the implementation type.

You are correct.

I believe the reason I made it a member was merely for convenience, without that, this line

pendingMovements (new compiz::queues::impl::Queue <CompPoint> (boost::shared_static_cast <compiz::queues::QueueStorageInterface <CompPoint> > (pendingMovementsStorage)))

would look something like

pendingMovements (new compiz::queues::impl::Queue <CompPoint> (boost::shared_static_cast <compiz::queues::QueueStorageInterface <CompPoint> > (compiz::queues::impl::AccumulatedMapStorage <CompPoint>::Ptr ((new compiz::queues::impl::AccumulatedMapStorage <CompPoint> ()))))

(which is a bit of a monstrosity :( )

>
> There is no need for pendingMovements to be allocated on the heap instead of
> being a member variable. (The same change for pendingMovementsStorage which
> would require a signature change for compiz::queues::impl::Queue::Queue - but
> that's minor.)

I think the reason why I had it on the heap was because if it was on the stack then this would mean we'd pass QueueStorageInterface by const reference and we'd have to copy the temporary into the member variable inside of ::Queue . That would mean adding copying semantics to something which shouldn't really be copied anyways (QueueStorageInterface describes /how/ the queue data should be stored, it isn't a value type in itself).

pendingMovements on the other hand could be on the stack.

[Sam Spilsbury (smspillaz)]

> I don't know the compiz coding standards, but for abstract code like this I'd
> expect at the very least 2 comments: 1) In queue.cpp/h explaining what the
> general idea behind all the interfaces are, 2) in the move.cpp explaining what
> it is using the clever queues for (ie. why a bog standard list is not good
> enough)

Yes, I will add such comments. Thanks Mikkel

[Sam Spilsbury (smspillaz)]

> Making destructors pure virtual is only really necessary if there are no other
> pure virtual methods and you want to make the class abstract. Other than that
> they are just a PITA.

Ack

[Alan Griffiths (alan-griffiths)]

> > It isn't obvious what contracts the template interfaces
> QueueStorageInterface,
> > QueueInterface, and QueueLockInterface represent. E.g. I'd expect a lock to
> > have "lock()" and "unlock()" methods or similar. Do they need to be
> > templates?
>
> QueueReleaseInterface, QueueInterface and QueueStorageInterface need to know
> the type that is being stored. As such, they are templates.

Yes, but they are only instantiated on one type in real code. (And another in the tests.)

> >
> > The pure destructors and NVPI clutter up the code.
> >
> > In MoveScreen the new variables pendingMovementsStorage, pendingMovements
> and
> > queueLock could be private. (I suspect others could too - what is it with
> > compiz and public data members?)
>
> Ack, although I believe we're using this from MoveWindow.

Not in the code I see.

> > I don't see why pendingMovementsStorage is a member variable - it's only use
> > is in initalizing pendingMovements. In any case, it should be of the usage
> > type - shared_ptr<QueueStorageInterface> not the implementation type.
>
> You are correct.
>
> I believe the reason I made it a member was merely for convenience, without
> that, this line
>
> pendingMovements (new compiz::queues::impl::Queue <CompPoint>
> (boost::shared_static_cast <compiz::queues::QueueStorageInterface <CompPoint>
> > (pendingMovementsStorage)))
>
> would look something like
>
> pendingMovements (new compiz::queues::impl::Queue <CompPoint>
> (boost::shared_static_cast <compiz::queues::QueueStorageInterface <CompPoint>
> > (compiz::queues::impl::AccumulatedMapStorage <CompPoint>::Ptr ((new
> compiz::queues::impl::AccumulatedMapStorage <CompPoint> ()))))

Or without the pointless cast...

pendingMovements (new compiz::queues::impl::Queue <CompPoint> (compiz::queues::impl::QueueStorageInterface <CompPoint>::Ptr ((new compiz::queues::impl::AccumulatedMapStorage <CompPoint> ())))

And if you don't repeat compiz::queues::impl:: all the time.

pendingMovements (new cqi::Queue <CompPoint> (cqi::QueueStorageInterface <CompPoint>::Ptr ((new cqi::AccumulatedMapStorage <CompPoint> ())))

> > There is no need for pendingMovements to be allocated on the heap instead of
> > being a member variable. (The same change for pendingMovementsStorage which
> > would require a signature change for compiz::queues::impl::Queue::Queue -
> but
> > that's minor.)
>
> I think the reason why I had it on the heap was because if it was on the stack
> then this would mean we'd pass QueueStorageInterface by const reference and
> we'd have to copy the temporary into the member variable inside of ::Queue .
> That would mean adding copying semantics to something which shouldn't really
> be copied anyways (QueueStorageInterface describes /how/ the queue data should
> be stored, it isn't a value type in itself).

I think there's a misunderstanding. But that's moot in view of the above discussion.

> pendingMovements on the other hand could be on the stack.

A data member. Then the "monsterous" line becomes:

pendingMovements (cqi::QueueStorageInterface <CompPoint>::Ptr ((new cqi::AccumulatedMapStorage <CompPoint> ()))

[Sam Spilsbury (smspillaz)]

Code cleaned up. Resubmitted ... though it looks like I have more to do. Fun.

[Sam Spilsbury (smspillaz)]

> QueueReleaseInterface, QueueInterface and QueueStorageInterface need to know
> the type that is being stored. As such, they are templates.

> Yes, but they are only instantiated on one type in real code. (And another in the tests.)

I plan to use this in other parts of the code. It was almost generic as it was, and is quite useful as a separate mechanism IMO

Will use namespace aliases as recommended

[Sam Spilsbury (smspillaz)]

Code cleaned up and resubmitted again

[Alan Griffiths (alan-griffiths)]

Seems to work. And the functionality seems a good idea.

But, now we can read what they do, the names of the queues classes seem a bit awkward...

"QueueInterface" does only a small subset of what I'd expect a queue to do and adding "Interface" to the name seems verbose (not that I like Microsoft's "I" prefix either). "Appender" may be better?

"QueueLockInterface" this doesn't behave as I expect from a lock. It is a pre-release callback to request permission to release the queue.

(I find the other names problematic too - but don't want to go on too much.)

On the design side, I don't like the fact that downcasts are required by the code using these classes. As a general principle templates should allow this to be avoided by propagating type information.

[Sam Spilsbury (smspillaz)]

> Seems to work. And the functionality seems a good idea.
>
> But, now we can read what they do, the names of the queues classes seem a bit
> awkward...
>
> "QueueInterface" does only a small subset of what I'd expect a queue to do and
> adding "Interface" to the name seems verbose (not that I like Microsoft's "I"
> prefix either). "Appender" may be better?

The I/Interface/Whatever discussion needs to be had somewhere else.

>
> "QueueLockInterface" this doesn't behave as I expect from a lock. It is a
> pre-release callback to request permission to release the queue.

QueueHoldInterface ?

>
> (I find the other names problematic too - but don't want to go on too much.)
>
> On the design side, I don't like the fact that downcasts are required by the
> code using these classes. As a general principle templates should allow this
> to be avoided by propagating type information.

550 + mItems[static_cast <QueueReleaseInterface *> (i)] += t;
551 +
552 + return true;
553 + }
554 +
555 + void doRelease ()
556 + {
557 + typename std::map <QueueReleaseInterface *, T>::iterator it = mItems.begin ();
558 +
559 + for (; it != mItems.end (); it++)
560 + {
561 + QueueReleasableInterface <T> *releasable = static_cast <QueueReleasableInterface <T> *> (it->first);

These two are avoidable. I'll try something else. As for the downcast to MoveWindow, it should be possible to avoid that one by changing the boost::function to another interface like a QueueItemReadyCallback or perhaps adding an notifyItemReady (); to QueueReleaseInterface

[lp:~smspillaz/compiz-core/compiz-core.fix_969108.2]

3086. By Sam Spilsbury on 2012-04-03

Also notify interested data receivers they have data pending

3087. By Sam Spilsbury on 2012-04-03

Remove downcasts where possible

3088. By Sam Spilsbury on 2012-04-04

Actually hook up to itemPending

Unmerged revisions

3088. By Sam Spilsbury on 2012-04-04

Actually hook up to itemPending

3087. By Sam Spilsbury on 2012-04-03

Remove downcasts where possible

3086. By Sam Spilsbury on 2012-04-03

Also notify interested data receivers they have data pending

3085. By Sam Spilsbury on 2012-04-02

Remove the shared static cast

3084. By Sam Spilsbury on 2012-04-02

Namespace alias

3083. By Sam Spilsbury on 2012-04-02

Removed AccumulatedMapStorage member

3082. By Sam Spilsbury on 2012-04-02

Made pendingMovements not a shared ptr

3081. By Sam Spilsbury on 2012-04-02

Made pendingMovements private

3080. By Sam Spilsbury on 2012-04-02

Removed virtual destructors

3079. By Sam Spilsbury on 2012-04-02

Added documentation for the contract provided by queues

=== added directory 'build'
=== added directory 'build/src'
=== modified file 'include/core/screen.h'
--- include/core/screen.h	2012-03-12 12:35:52 +0000
+++ include/core/screen.h	2012-04-02 15:10:24 +0000
@@ -39,6 +39,7 @@
 #include <core/valueholder.h>
 
 #include <boost/scoped_ptr.hpp>
+#include <boost/shared_ptr.hpp>
 
 class CompScreenImpl;
 class PrivateScreen;

=== modified file 'plugins/CMakeLists.txt'
--- plugins/CMakeLists.txt	2012-01-20 09:46:31 +0000
+++ plugins/CMakeLists.txt	2012-04-02 15:10:24 +0000
@@ -16,6 +16,7 @@
   ${CMAKE_CURRENT_SOURCE_DIR}/../src/pluginclasshandler/include
   ${CMAKE_CURRENT_SOURCE_DIR}/../src/point/include
   ${CMAKE_CURRENT_SOURCE_DIR}/../src/rect/include
+  ${CMAKE_CURRENT_SOURCE_DIR}/../src/queues/include
   ${CMAKE_CURRENT_SOURCE_DIR}/../src/window/geometry/include
   ${CMAKE_CURRENT_SOURCE_DIR}/../src/window/geometry-saver/include
   ${CMAKE_CURRENT_SOURCE_DIR}/../src/window/extents/include

=== modified file 'plugins/move/src/move.cpp'
--- plugins/move/src/move.cpp	2012-02-16 05:31:28 +0000
+++ plugins/move/src/move.cpp	2012-04-02 15:10:24 +0000
@@ -27,6 +27,8 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include <boost/cast.hpp>
+
 #include <X11/cursorfont.h>
 
 #include <core/atoms.h>
@@ -169,8 +171,8 @@
     if (ms->w)
     {
 	if (state & CompAction::StateCancel)
-	    ms->w->move (ms->savedX - ms->w->geometry ().x (),
-			 ms->savedY - ms->w->geometry ().y (), false);
+	    ms->addMovement (MoveWindow::get (ms->w), CompPoint (ms->savedX - ms->w->geometry ().x (),
+								 ms->savedY - ms->w->geometry ().y ()));
 
 	ms->w->syncPosition ();
 
@@ -484,8 +486,7 @@
 
 	if (dx || dy)
 	{
-	    w->move (wX + dx - w->geometry ().x (),
-		     wY + dy - w->geometry ().y (), false);
+	    ms->addMovement (MoveWindow::get (w), CompPoint (dx, dy));
 
 	    if (!ms->optionGetLazyPositioning ())
 		w->syncPosition ();
@@ -666,6 +667,20 @@
 }
 
 bool
+MoveWindow::doRelease (const CompPoint &d)
+{
+    window->move (d.x (), d.y (), false);
+    return true;
+}
+
+void
+MoveScreen::dispatchDamage (cq::QueueReleaseInterface *releasable)
+{
+    MoveWindow *mw = static_cast <MoveWindow *> (releasable);
+    mw->cWindow->addDamage ();
+}
+
+bool
 MoveScreen::registerPaintHandler(compiz::composite::PaintHandler *pHnd)
 {
     hasCompositing = true;
@@ -677,9 +692,27 @@
 MoveScreen::unregisterPaintHandler()
 {
     hasCompositing = false;
+    queueLock.reset ();
     cScreen->unregisterPaintHandler ();
 }
 
+void
+MoveScreen::preparePaint (int ms)
+{
+    if (queueLock)
+	queueLock->unlock ();
+
+    cScreen->preparePaint (ms);
+    cScreen->preparePaintSetEnabled (this, false);
+}
+
+void
+MoveScreen::addMovement (MoveWindow *mw, const CompPoint &d)
+{
+    cScreen->preparePaintSetEnabled (this, true);
+    pendingMovements.addPending (d, mw);
+}
+
 MoveScreen::MoveScreen (CompScreen *screen) :
     PluginClassHandler<MoveScreen,CompScreen> (screen),
     cScreen (CompositeScreen::get (screen)),
@@ -689,7 +722,8 @@
     releaseButton (0),
     grab (NULL),
     hasCompositing (false),
-    yConstrained (false)
+    yConstrained (false),
+    pendingMovements (cqi::AccumulatedMapStorage<CompPoint>::Ptr (new cqi::AccumulatedMapStorage <CompPoint> ()))
 {
     updateOpacity ();
 
@@ -701,6 +735,8 @@
     if (cScreen)
     {
 	CompositeScreenInterface::setHandler (cScreen);
+	queueLock = pendingMovements.obtainLock (boost::bind (&MoveScreen::dispatchDamage, this, _1));
+	cScreen->preparePaintSetEnabled (this, false);
 	hasCompositing =
 	    cScreen->compositingActive ();
     }

=== modified file 'plugins/move/src/move.h'
--- plugins/move/src/move.h	2012-02-01 17:49:07 +0000
+++ plugins/move/src/move.h	2012-04-02 15:10:24 +0000
@@ -27,10 +27,13 @@
 
 #include <core/screen.h>
 #include <core/pluginclasshandler.h>
+#include <core/queues.h>
 
 #include <composite/composite.h>
 #include <opengl/opengl.h>
 
+namespace cqi = compiz::queues::impl;
+namespace cq = compiz::queues;
 
 #define NUM_KEYS (sizeof (mKeys) / sizeof (mKeys[0]))
 
@@ -50,6 +53,8 @@
     { "Down",   0,  1 }
 };
 
+class MoveWindow;
+
 class MoveScreen :
     public ScreenInterface,
     public CompositeScreenInterface,
@@ -68,6 +73,10 @@
 
 	bool registerPaintHandler (compiz::composite::PaintHandler *pHnd);
 	void unregisterPaintHandler ();
+	void preparePaint (int ms);
+
+	void addMovement (MoveWindow *mw, const CompPoint &d);
+	void dispatchDamage (cq::QueueReleaseInterface *);
 
 	CompWindow *w;
 	int        savedX;
@@ -94,29 +103,49 @@
 	bool hasCompositing;
 
 	bool yConstrained;
+
+    private:
+
+	cqi::Queue <CompPoint> pendingMovements;
+	boost::shared_ptr <cq::QueueLockInterface> queueLock;
 };
 
 class MoveWindow :
     public GLWindowInterface,
-    public PluginClassHandler<MoveWindow,CompWindow>
+    public PluginClassHandler<MoveWindow,CompWindow>,
+    public cq::QueueReleasableInterface <CompPoint>
 {
     public:
 	MoveWindow (CompWindow *window) :
 	    PluginClassHandler<MoveWindow,CompWindow> (window),
 	    window (window),
 	    gWindow (GLWindow::get (window)),
-	    cWindow (CompositeWindow::get (window))
+	    cWindow (CompositeWindow::get (window)),
+	    mRemoveInterface (NULL)
 	{
 	    if (gWindow)
 		GLWindowInterface::setHandler (gWindow, false);
 	};
 
+	~MoveWindow ()
+	{
+	    if (mRemoveInterface)
+		mRemoveInterface->removeReleasable (this);
+	}
+
 	bool glPaint (const GLWindowPaintAttrib &, const GLMatrix &,
 		      const CompRegion &, unsigned int);
 
 	CompWindow      *window;
 	GLWindow        *gWindow;
 	CompositeWindow *cWindow;
+
+    private:
+
+	bool doRelease (const CompPoint &d);
+	void doSetRemoveInterface (cq::QueueReleaseRemoveInterface *removeInterface) { mRemoveInterface = removeInterface; }
+
+	cq::QueueReleaseRemoveInterface *mRemoveInterface;
 };
 
 #define MOVE_SCREEN(s) \

=== modified file 'src/CMakeLists.txt'
--- src/CMakeLists.txt	2012-03-13 10:17:02 +0000
+++ src/CMakeLists.txt	2012-04-02 15:10:24 +0000
@@ -8,6 +8,7 @@
 add_subdirectory( point )
 add_subdirectory( rect )
 add_subdirectory( window )
+add_subdirectory( queues )
 
 IF (COMPIZ_BUILD_TESTING)
 add_subdirectory( privatescreen/tests )
@@ -54,6 +55,9 @@
     ${CMAKE_CURRENT_SOURCE_DIR}/point/include
     ${CMAKE_CURRENT_SOURCE_DIR}/point/src
 
+    ${CMAKE_CURRENT_SOURCE_DIR}/queues/include
+    ${CMAKE_CURRENT_SOURCE_DIR}/queues/src
+
     ${CMAKE_CURRENT_SOURCE_DIR}/rect/include
     ${CMAKE_CURRENT_SOURCE_DIR}/rect/src
 
@@ -159,6 +163,7 @@
     compiz_window_geometry_saver
     compiz_window_extents
     compiz_window_constrainment
+    compiz_queues
     -Wl,-no-whole-archive
 #    ${CORE_MOD_LIBRARIES}
 )

=== added directory 'src/queues'
=== added file 'src/queues/CMakeLists.txt'
--- src/queues/CMakeLists.txt	1970-01-01 00:00:00 +0000
+++ src/queues/CMakeLists.txt	2012-04-02 15:10:24 +0000
@@ -0,0 +1,61 @@
+pkg_check_modules (
+  GLIBMM
+  REQUIRED
+  glibmm-2.4 glib-2.0
+)
+
+INCLUDE_DIRECTORIES (  
+  ${CMAKE_CURRENT_SOURCE_DIR}/include
+  ${CMAKE_CURRENT_SOURCE_DIR}/src
+
+  ${CMAKE_CURRENT_SOURCE_DIR}/queues/include
+  ${CMAKE_CURRENT_SOURCE_DIR}/queues/src
+
+  ${compiz_SOURCE_DIR}/include
+    
+  ${Boost_INCLUDE_DIRS}
+  
+  ${GLIBMM_INCLUDE_DIRS}
+)
+
+LINK_DIRECTORIES (${GLIBMM_LIBRARY_DIRS}) 
+
+SET ( 
+  PUBLIC_HEADERS 
+  ${CMAKE_CURRENT_SOURCE_DIR}/include/core/queues.h
+)
+
+SET ( 
+  PRIVATE_HEADERS 
+)
+
+SET( 
+  SRCS 
+  ${CMAKE_CURRENT_SOURCE_DIR}/src/queues.cpp
+)
+
+ADD_LIBRARY( 
+  compiz_queues STATIC
+  
+  ${SRCS}
+  
+  ${PUBLIC_HEADERS}
+  ${PRIVATE_HEADERS}
+)
+
+IF (COMPIZ_BUILD_TESTING)
+ADD_SUBDIRECTORY( ${CMAKE_CURRENT_SOURCE_DIR}/tests )
+ENDIF (COMPIZ_BUILD_TESTING)
+
+SET_TARGET_PROPERTIES(
+  compiz_queues PROPERTIES
+  PUBLIC_HEADER "${PUBLIC_HEADERS}"
+)
+
+install (FILES ${PUBLIC_HEADERS} DESTINATION ${COMPIZ_CORE_INCLUDE_DIR})
+
+TARGET_LINK_LIBRARIES( 
+  compiz_queues
+  
+  ${GLIBMM_LIBRARIES}
+)

=== added directory 'src/queues/include'
=== added directory 'src/queues/include/core'
=== added file 'src/queues/include/core/queues.h'
--- src/queues/include/core/queues.h	1970-01-01 00:00:00 +0000
+++ src/queues/include/core/queues.h	2012-04-02 15:10:24 +0000
@@ -0,0 +1,360 @@
+/*
+ * Copyright © 2012 Canonical Ltd.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of
+ * Canonical Ltd. not be used in advertising or publicity pertaining to
+ * distribution of the software without specific, written prior permission.
+ * Canonical Ltd. makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express or
+ * implied warranty.
+ *
+ * CANONICAL, LTD. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CANONICAL, LTD. BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
+ * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Authored by: Sam Spilsbury <[e-mail]>
+ */
+
+#ifndef _COMPQUEUES_H
+#define _COMPQUEUES_H
+
+#include <vector>
+#include <map>
+#include <boost/shared_ptr.hpp>
+#include <boost/function.hpp>
+#include <boost/bind.hpp>
+#include <boost/noncopyable.hpp>
+
+namespace compiz
+{
+    namespace queues
+    {
+	class QueueReleaseInterface;
+
+	/**
+	  * A QueueReleaseRemoveInterface describes an interface
+	  * provided to an object inheriting QueueReleaseInterface
+	  * to call back into the queue storage to remove queued items
+	  * relating to a QueueReleaseInterface when the object implementing
+	  * the QueueReleaseInterface is destroyed
+	  */
+	class QueueReleaseRemoveInterface
+	{
+	    public:
+
+		virtual ~QueueReleaseRemoveInterface () {}
+
+		void removeReleasable (QueueReleaseInterface *r) { doRemoveReleasable (r); }
+
+	    protected:
+
+		virtual void doRemoveReleasable (QueueReleaseInterface *) = 0;
+	};
+
+	/**
+	 * A QueueReleaseInterface is implemented by an object interested in some
+	 * data on the object in the future when an object implementing a QueueInterface
+	 * decides it is appropriate to release that data. This class is a base to the
+	 * template QueueReleasableInterface which knows about the data type being released */
+	class QueueReleaseInterface
+	{
+	    public:
+
+		virtual ~QueueReleaseInterface () {}
+
+		void setRemoveInterface (QueueReleaseRemoveInterface *r) { doSetRemoveInterface (r); }
+
+	    protected:
+
+		virtual void doSetRemoveInterface (QueueReleaseRemoveInterface *) = 0;
+	};
+
+	/**
+	 * A QueueReleasableInterface is implemented by an object interested in some
+	 * future data when an object implementing a QueueInterface decides it is appropriate
+	 * to dispatch this data. release () is a callback into the object to inform it that
+	 * new data is ready to be proccessed
+	 */
+	template <class T>
+	class QueueReleasableInterface :
+	    public QueueReleaseInterface
+	{
+	    public:
+
+		virtual ~QueueReleasableInterface () {}
+
+		bool release (const T &t) { return doRelease (t); }
+
+	    protected:
+
+		virtual bool doRelease (const T &t) = 0;
+	};
+
+	/**
+	 * A QueueLockInterface is implemented by an object which wishes to hold a lock
+	 * on a QueueInterface to prevent it from releasing data until the owner of the
+	 * QueueLockInterface decides is appropriate. QueueLockInterfaces provide an unlock ()
+	 * method to indicate that data which is held in the queue is ok by the owner to be
+	 * processed. callback () is invoked by a QueueInterface which wishes to indicate
+	 * that some data on a QueueReleaseInterface is pending processing but not yet
+	 * released (so that the owner may decide whether or not it is appropriate to release
+	 * the lock)
+	 */
+	class QueueLockInterface
+	{
+	    public:
+
+		virtual ~QueueLockInterface () {}
+
+		typedef boost::shared_ptr <QueueLockInterface> Ptr;
+
+		bool unlock () { return doUnlock (); }
+		void callback (QueueReleaseInterface *releasable) { return doCallback (releasable); }
+
+	    private:
+
+		virtual bool doUnlock () = 0;
+		virtual void doCallback (QueueReleaseInterface *releasable) = 0;
+	};
+
+	/**
+	  * A QueueUnlockInterface is implemented by an object which has data to be dispatched
+	  * to other interested owners. QueueUnlockInterface is provided to implementors of
+	  * QueueLockInterface as a means to call-back and decrement the lock count of the queue.
+	  * Locks must also register their existence on the unlock interface
+	  */
+	class QueueUnlockInterface
+	{
+	    public:
+
+		virtual ~QueueUnlockInterface () {}
+
+		void release () { doRelease (); }
+		bool registerLock (QueueLockInterface *lock) { return doRegisterLock (lock); }
+		bool unregisterLock (QueueLockInterface *lock) { return doUnregisterLock (lock); }
+
+	    private:
+
+		virtual void doRelease () = 0;
+		virtual bool doRegisterLock (QueueLockInterface *) = 0;
+		virtual bool doUnregisterLock (QueueLockInterface *) = 0;
+	};
+
+	typedef boost::function <void (QueueReleaseInterface *)> pendingItemsFunc;
+
+	/**
+	 * A QueueLockGeneratorInterface provides an interface to construct a lock - the implementation
+	 * determines what type of lock to construct, and what the lock has control over
+	 */
+	class QueueLockGeneratorInterface
+	{
+	    public:
+
+		virtual ~QueueLockGeneratorInterface () {}
+		boost::shared_ptr <QueueLockInterface> obtainLock (const pendingItemsFunc &func) { return doObtainLock (func); }
+
+	    private:
+
+		virtual boost::shared_ptr <QueueLockInterface> doObtainLock (const pendingItemsFunc &) = 0;
+	};
+
+	/**
+	 * A QueueInterface provides the front-end for adding data to a queue to be dispatched
+	 * on a QueueReleasableInterface at some point in the future.
+	 */
+	template <class T>
+	class QueueInterface
+	{
+	    public:
+
+		virtual ~QueueInterface () {}
+
+		void addPending (const T &t,
+				 QueueReleasableInterface <T> *r) { doAddPending (t, r); }
+
+	    protected:
+
+		virtual void doAddPending (const T &,
+					   QueueReleasableInterface <T> *) = 0;
+	};
+
+	/**
+	 * A QueueStorageInterface is an abstraction as to how data should be stored in a QueueInterface
+	 * and how it should be released when data is ready to be dispatched
+	 */
+	template <class T>
+	class QueueStorageInterface :
+	    public QueueReleaseRemoveInterface
+	{
+	    public:
+
+		virtual ~QueueStorageInterface () {}
+
+		typedef boost::shared_ptr <QueueStorageInterface <T> > Ptr;
+
+		bool store (QueueReleasableInterface<T> *r, const T &t) { return doStore (r, t); }
+		void release () { doRelease (); }
+
+	    protected:
+
+		virtual bool doStore (QueueReleasableInterface<T> *i, const T &) = 0;
+		virtual void doRelease () = 0;
+	};
+
+	namespace impl
+	{
+
+	    typedef boost::function <void ()> notifyReleaseFunc;
+
+	    template <class T>
+	    class AccumulatedMapStorage :
+		public QueueStorageInterface <T>
+	    {
+		public:
+
+		    typedef typename boost::shared_ptr <AccumulatedMapStorage <T> > Ptr;
+
+		private:
+
+		    bool doStore (QueueReleasableInterface<T> *i, const T &t)
+		    {
+			mItems[static_cast <QueueReleaseInterface *> (i)] += t;
+
+			return true;
+		    }
+
+		    void doRelease ()
+		    {
+			typename std::map <QueueReleaseInterface *, T>::iterator it = mItems.begin ();
+
+			for (; it != mItems.end (); it++)
+			{
+			    QueueReleasableInterface <T> *releasable = static_cast <QueueReleasableInterface <T> *> (it->first);
+
+			    releasable->release (it->second);
+			}
+
+			mItems.clear ();
+		    }
+
+		    void doRemoveReleasable (compiz::queues::QueueReleaseInterface *r)
+		    {
+			typename std::map <QueueReleaseInterface *, T>::iterator it = mItems.find (r);
+
+			if (it != mItems.end ())
+			    mItems.erase (it);
+		    }
+
+		    std::map <QueueReleaseInterface *, T> mItems;
+	    };
+
+	    class QueueLock :
+		public QueueLockInterface
+	    {
+		public:
+
+		    QueueLock (QueueUnlockInterface *unlockable, const pendingItemsFunc &f);
+		    ~QueueLock ();
+
+		private:
+
+		    bool doUnlock ();
+		    void doCallback (QueueReleaseInterface *releasable);
+
+		    QueueUnlockInterface *mUnlockable;
+		    pendingItemsFunc mPendingDispatch;
+	    };
+
+	    class QueueImpl :
+		public QueueUnlockInterface,
+		public QueueLockGeneratorInterface
+	    {
+		public:
+
+		    QueueImpl (const notifyReleaseFunc &f) :
+			mNotifyFunc (f)
+		    {
+		    }
+
+		    void reset ();
+		    void notify (compiz::queues::QueueReleaseInterface *);
+
+		private:
+
+		    void doRelease ();
+		    bool doRegisterLock (QueueLockInterface *lock);
+		    bool doUnregisterLock (QueueLockInterface *lock);
+
+		    QueueLockInterface::Ptr doObtainLock (const pendingItemsFunc &);
+
+		    notifyReleaseFunc mNotifyFunc;
+		    std::vector <QueueLockInterface *> mLocks;
+		    unsigned int mLockCount;
+	    };
+
+	    template <class T>
+	    class Queue :
+		boost::noncopyable,
+		public QueueInterface <T>,
+		public QueueLockGeneratorInterface,
+		public QueueUnlockInterface
+
+	    {
+		public:
+
+		    Queue (const typename QueueStorageInterface<T>::Ptr &storage) :
+			mImpl (boost::bind (&QueueStorageInterface<T>::release, storage.get ())),
+			mStorage (storage)
+		    {
+		    }
+
+		private:
+
+		    void doAddPending (const T &t,
+				       QueueReleasableInterface <T> *release)
+		    {
+			release->setRemoveInterface (static_cast <QueueReleaseRemoveInterface *> (mStorage.get ()));
+
+			mStorage->store (release, t);
+			mImpl.reset ();
+			mImpl.notify (release);
+			mImpl.release ();
+		    }
+
+		    boost::shared_ptr <QueueLockInterface> doObtainLock (const pendingItemsFunc &f)
+		    {
+			return mImpl.obtainLock (f);
+		    }
+
+		    void doRelease ()
+		    {
+			return mImpl.release ();
+		    }
+
+		    bool doRegisterLock (QueueLockInterface *lock)
+		    {
+			return mImpl.registerLock (lock);
+		    }
+
+		    bool doUnregisterLock (QueueLockInterface *lock)
+		    {
+			return mImpl.unregisterLock (lock);
+		    }
+
+		    QueueImpl mImpl;
+		    typename compiz::queues::QueueStorageInterface<T>::Ptr mStorage;
+	    };
+	}
+    }
+}
+
+
+#endif

=== added directory 'src/queues/src'
=== added file 'src/queues/src/queues.cpp'
--- src/queues/src/queues.cpp	1970-01-01 00:00:00 +0000
+++ src/queues/src/queues.cpp	2012-04-02 15:10:24 +0000
@@ -0,0 +1,113 @@
+/*
+ * Copyright © 2012 Canonical Ltd.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of
+ * Canonical Ltd. not be used in advertising or publicity pertaining to
+ * distribution of the software without specific, written prior permission.
+ * Canonical Ltd. makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express or
+ * implied warranty.
+ *
+ * CANONICAL, LTD. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CANONICAL, LTD. BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
+ * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Authored by: Sam Spilsbury <[e-mail]>
+ */
+
+#include <core/queues.h>
+#include <cstdio>
+
+using namespace compiz::queues;
+using namespace compiz::queues::impl;
+
+void
+QueueImpl::reset ()
+{
+    mLockCount = mLocks.size () + 1;
+}
+
+void
+QueueImpl::notify (QueueReleaseInterface *releasable)
+{
+    for (std::vector <QueueLockInterface *>::iterator it = mLocks.begin (); it != mLocks.end (); it++)
+	(*it)->callback (releasable);
+}
+
+void
+QueueImpl::doRelease ()
+{
+    if (!mLockCount)
+	return;
+
+    mLockCount--;
+
+    if (mLockCount)
+	return;
+
+    /* Release all queued items */
+    mNotifyFunc ();
+}
+
+bool
+QueueImpl::doRegisterLock (QueueLockInterface *lock)
+{
+    std::vector<QueueLockInterface *>::iterator it = std::find (mLocks.begin (), mLocks.end (), lock);
+
+    if (it != mLocks.end ())
+	return false;
+
+    mLocks.push_back (lock);
+    return true;
+}
+
+bool
+QueueImpl::doUnregisterLock (QueueLockInterface *lock)
+{
+    std::vector<QueueLockInterface *>::iterator it = std::find (mLocks.begin (), mLocks.end (), lock);
+
+    if (it == mLocks.end ())
+	return false;
+
+    mLocks.erase (it);
+    return true;
+}
+
+QueueLockInterface::Ptr
+QueueImpl::doObtainLock (const pendingItemsFunc &f)
+{
+    return QueueLockInterface::Ptr (new QueueLock (this, f));
+}
+
+QueueLock::QueueLock (QueueUnlockInterface *unlockable, const pendingItemsFunc &pending) :
+    mUnlockable (unlockable),
+    mPendingDispatch (pending)
+{
+    mUnlockable->registerLock (this);
+}
+
+QueueLock::~QueueLock ()
+{
+    mUnlockable->unregisterLock (this);
+}
+
+bool
+QueueLock::doUnlock ()
+{
+    mUnlockable->release ();
+    return true;
+}
+
+void
+QueueLock::doCallback (QueueReleaseInterface *releasable)
+{
+    mPendingDispatch (releasable);
+}

=== added directory 'src/queues/tests'
=== added file 'src/queues/tests/CMakeLists.txt'
--- src/queues/tests/CMakeLists.txt	1970-01-01 00:00:00 +0000
+++ src/queues/tests/CMakeLists.txt	2012-04-02 15:10:24 +0000
@@ -0,0 +1,18 @@
+include_directories(${CMAKE_CURRENT_SOURCE_DIR})
+
+add_library (compiz_queues_test
+             ${CMAKE_CURRENT_SOURCE_DIR}/test-queues.cpp)
+
+add_executable (compiz_test_queues
+                ${CMAKE_CURRENT_SOURCE_DIR}/queues/src/test-queues.cpp)
+
+target_link_libraries (compiz_test_queues
+                       compiz_queues_test
+                       compiz_queues 
+                       ${GTEST_BOTH_LIBRARIES}
+		       ${GMOCK_LIBRARY}
+		       ${GMOCK_MAIN_LIBRARY}
+		       ${CMAKE_THREAD_LIBS_INIT} # Link in pthread. 
+                       )
+
+gtest_add_tests (compiz_test_queues "" ${CMAKE_CURRENT_SOURCE_DIR}/queues/src/test-queues.cpp)

=== added directory 'src/queues/tests/queues'
=== added directory 'src/queues/tests/queues/src'
=== added file 'src/queues/tests/queues/src/test-queues.cpp'
--- src/queues/tests/queues/src/test-queues.cpp	1970-01-01 00:00:00 +0000
+++ src/queues/tests/queues/src/test-queues.cpp	2012-04-02 15:10:24 +0000
@@ -0,0 +1,231 @@
+/*
+ * Copyright © 2011 Canonical Ltd.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of
+ * Canonical Ltd. not be used in advertising or publicity pertaining to
+ * distribution of the software without specific, written prior permission.
+ * Canonical Ltd. makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express or
+ * implied warranty.
+ *
+ * CANONICAL, LTD. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CANONICAL, LTD. BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
+ * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Authored by: Sam Spilsbury <[e-mail]>
+ */
+
+#include "test-queues.h"
+#include <boost/cast.hpp>
+
+class CompQueuesTestQueues :
+    public CompQueuesTest
+{
+    public:
+
+	CompQueuesTestQueues ();
+	~CompQueuesTestQueues ();
+
+};
+
+CompQueuesTestQueues::CompQueuesTestQueues ()
+{
+}
+
+CompQueuesTestQueues::~CompQueuesTestQueues ()
+{
+}
+
+TEST_F(CompQueuesTestQueues, TestSetRemoveReleasables)
+{
+    boost::shared_ptr <MockQueueStorage <int> > mockStorage (new MockQueueStorage <int> ());
+    impl::Queue <int> q (boost::shared_static_cast <QueueStorageInterface <int> > (mockStorage));
+
+    MockQueueReleasable <int> releasable;
+
+    releasable.DelegateToFake ();
+
+    EXPECT_CALL (releasable, doSetRemoveInterface (_));
+    EXPECT_CALL (*mockStorage, doStore (_, 7));
+    EXPECT_CALL (*mockStorage, doRelease ());
+    EXPECT_CALL (*mockStorage, doRemoveReleasable (_));
+
+    q.addPending (7, &releasable);
+}
+
+TEST_F(CompQueuesTestQueues, TestReleaseNoLocks)
+{
+    boost::shared_ptr <MockQueueStorage <int> > mockStorage (new MockQueueStorage <int> ());
+    impl::Queue <int> q (boost::shared_static_cast <QueueStorageInterface <int> > (mockStorage));
+
+    MockQueueReleasable <int> releasable;
+
+    releasable.DelegateToFake ();
+
+    EXPECT_CALL (releasable, doSetRemoveInterface (_));
+    EXPECT_CALL (*mockStorage, doStore (_, 7));
+    EXPECT_CALL (*mockStorage, doRelease ());
+    EXPECT_CALL (*mockStorage, doRemoveReleasable (_));
+
+    q.addPending (7, &releasable);
+}
+
+TEST_F(CompQueuesTestQueues, TestReleaseWithLockUnlock)
+{
+    boost::shared_ptr <impl::AccumulatedMapStorage <int> > actualStorage (new impl::AccumulatedMapStorage <int> ());
+    boost::shared_ptr <MockQueueStorage <int> > mockStorage (new MockQueueStorage <int> ());
+
+    mockStorage->Delegate (static_cast <QueueStorageInterface <int> *> (actualStorage.get ()));
+
+    impl::Queue <int> q (boost::shared_static_cast <QueueStorageInterface <int> > (mockStorage));
+    QueueLockGeneratorDelegate <impl::QueueLock> gen (static_cast <QueueUnlockInterface *> (&q));
+    StrictMock <MockPendingItems> pi;
+
+    MockQueue <int> mq;
+
+    mq.Delegate (&q, &gen);
+
+    boost::function <void (QueueReleaseInterface *)> callback (boost::bind (&PendingItemsInterface::pending, static_cast <PendingItemsInterface *> (&pi), _1));
+
+    EXPECT_CALL (mq, doObtainLock (_));
+
+    QueueLockInterface::Ptr lock (mq.obtainLock (callback));
+
+    StrictMock <MockQueueReleasable <int> > releasable;
+
+    releasable.DelegateToFake ();
+
+    EXPECT_CALL (releasable, doSetRemoveInterface (_));
+    EXPECT_CALL (*mockStorage, doStore (_, 7));
+    EXPECT_CALL (*mockStorage, doRemoveReleasable (_));
+    EXPECT_CALL (pi, doPending (_));
+
+    q.addPending (7, &releasable);
+
+    EXPECT_CALL (*mockStorage, doRelease ());
+    EXPECT_CALL (releasable, doRelease (7));
+
+    lock->unlock ();
+}
+
+TEST_F(CompQueuesTestQueues, TestReleaseWithLockNoUnlock)
+{
+    boost::shared_ptr <impl::AccumulatedMapStorage <int> > actualStorage (new impl::AccumulatedMapStorage <int> ());
+    boost::shared_ptr <MockQueueStorage <int> > mockStorage (new MockQueueStorage <int> ());
+
+    mockStorage->Delegate (static_cast <QueueStorageInterface <int> *> (actualStorage.get ()));
+
+    impl::Queue <int> q (boost::shared_static_cast <QueueStorageInterface <int> > (mockStorage));
+    QueueLockGeneratorDelegate <impl::QueueLock> gen (static_cast <QueueUnlockInterface *> (&q));
+    StrictMock <MockPendingItems> pi;
+
+    MockQueue <int> mq;
+
+    mq.Delegate (&q, &gen);
+
+    boost::function <void (QueueReleaseInterface *)> callback (boost::bind (&PendingItemsInterface::pending, static_cast <PendingItemsInterface *> (&pi), _1));
+
+    EXPECT_CALL (mq, doObtainLock (_));
+
+    QueueLockInterface::Ptr lock (mq.obtainLock (callback));
+
+    StrictMock <MockQueueReleasable <int> > releasable;
+
+    releasable.DelegateToFake ();
+
+    EXPECT_CALL (releasable, doSetRemoveInterface (_));
+    EXPECT_CALL (*mockStorage, doStore (_, 7));
+    EXPECT_CALL (*mockStorage, doRemoveReleasable (_));
+    EXPECT_CALL (pi, doPending (_));
+
+    q.addPending (7, &releasable);
+}
+
+TEST_F(CompQueuesTestQueues, TestRemoveReleasableLocked)
+{
+    boost::shared_ptr <impl::AccumulatedMapStorage <int> > actualStorage (new impl::AccumulatedMapStorage <int> ());
+    boost::shared_ptr <MockQueueStorage <int> > mockStorage (new MockQueueStorage <int> ());
+
+    mockStorage->Delegate (static_cast <QueueStorageInterface <int> *> (actualStorage.get ()));
+
+    impl::Queue <int> q (boost::shared_static_cast <QueueStorageInterface <int> > (mockStorage));
+    QueueLockGeneratorDelegate <impl::QueueLock> gen (static_cast <QueueUnlockInterface *> (&q));
+    StrictMock <MockPendingItems> pi;
+
+    MockQueue <int> mq;
+
+    mq.Delegate (&q, &gen);
+
+    boost::function <void (QueueReleaseInterface *)> callback (boost::bind (&PendingItemsInterface::pending, static_cast <PendingItemsInterface *> (&pi), _1));
+
+    EXPECT_CALL (mq, doObtainLock (_));
+
+    QueueLockInterface::Ptr lock (mq.obtainLock (callback));
+
+    boost::shared_ptr <StrictMock <MockQueueReleasable <int> > > releasable (new StrictMock <MockQueueReleasable <int> > ());
+
+    releasable->DelegateToFake ();
+
+    EXPECT_CALL (*releasable, doSetRemoveInterface (_));
+    EXPECT_CALL (*mockStorage, doStore (_, 7));
+    EXPECT_CALL (*mockStorage, doRemoveReleasable (_));
+    EXPECT_CALL (pi, doPending (_));
+
+    q.addPending (7, releasable.get ());
+
+    releasable.reset ();
+
+    EXPECT_CALL (*mockStorage, doRelease ());
+
+    lock->unlock ();
+}
+
+TEST_F(CompQueuesTestQueues, TestAccumulation)
+{
+    boost::shared_ptr <impl::AccumulatedMapStorage <int> > actualStorage (new impl::AccumulatedMapStorage <int> ());
+    boost::shared_ptr <MockQueueStorage <int> > mockStorage (new MockQueueStorage <int> ());
+
+    mockStorage->Delegate (static_cast <QueueStorageInterface <int> *> (actualStorage.get ()));
+
+    impl::Queue <int> q (boost::shared_static_cast <QueueStorageInterface <int> > (mockStorage));
+    QueueLockGeneratorDelegate <impl::QueueLock> gen (static_cast <QueueUnlockInterface *> (&q));
+    StrictMock <MockPendingItems> pi;
+
+    MockQueue <int> mq;
+
+    mq.Delegate (&q, &gen);
+
+    boost::function <void (QueueReleaseInterface *)> callback (boost::bind (&PendingItemsInterface::pending, static_cast <PendingItemsInterface *> (&pi), _1));
+
+    EXPECT_CALL (mq, doObtainLock (_));
+
+    QueueLockInterface::Ptr lock (mq.obtainLock (callback));
+
+    StrictMock <MockQueueReleasable <int> > releasable;
+
+    releasable.DelegateToFake ();
+
+    EXPECT_CALL (releasable, doSetRemoveInterface (_)).Times (3);
+    EXPECT_CALL (*mockStorage, doStore (_, 7));
+    EXPECT_CALL (*mockStorage, doStore (_, 8));
+    EXPECT_CALL (*mockStorage, doStore (_, 9));
+    EXPECT_CALL (*mockStorage, doRemoveReleasable (_));
+    EXPECT_CALL (pi, doPending (_)).Times (3);
+
+    q.addPending (7, &releasable);
+    q.addPending (8, &releasable);
+    q.addPending (9, &releasable);
+
+    EXPECT_CALL (*mockStorage, doRelease ());
+    EXPECT_CALL (releasable, doRelease (24));
+
+    lock->unlock ();
+}

=== added file 'src/queues/tests/test-queues.cpp'
--- src/queues/tests/test-queues.cpp	1970-01-01 00:00:00 +0000
+++ src/queues/tests/test-queues.cpp	2012-04-02 15:10:24 +0000
@@ -0,0 +1,34 @@
+/*
+ * Copyright © 2011 Canonical Ltd.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of
+ * Canonical Ltd. not be used in advertising or publicity pertaining to
+ * distribution of the software without specific, written prior permission.
+ * Canonical Ltd. makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express or
+ * implied warranty.
+ *
+ * CANONICAL, LTD. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CANONICAL, LTD. BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
+ * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Authored by: Sam Spilsbury <[e-mail]>
+ */
+
+#include "test-queues.h"
+
+CompQueuesTest::CompQueuesTest ()
+{
+}
+
+CompQueuesTest::~CompQueuesTest ()
+{
+}

=== added file 'src/queues/tests/test-queues.h'
--- src/queues/tests/test-queues.h	1970-01-01 00:00:00 +0000
+++ src/queues/tests/test-queues.h	2012-04-02 15:10:24 +0000
@@ -0,0 +1,208 @@
+/*
+ * Copyright © 2011 Canonical Ltd.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of
+ * Canonical Ltd. not be used in advertising or publicity pertaining to
+ * distribution of the software without specific, written prior permission.
+ * Canonical Ltd. makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express or
+ * implied warranty.
+ *
+ * CANONICAL, LTD. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL CANONICAL, LTD. BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
+ * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Authored by: Sam Spilsbury <[e-mail]>
+ */
+
+#ifndef _COMPIZ_TEST_QUEUES_H
+#define _COMPIZ_TEST_QUEUES_H
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+#include <core/queues.h>
+#include <iostream>
+#include <boost/bind.hpp>
+
+using ::testing::Invoke;
+using ::testing::_;
+using ::testing::StrictMock;
+using ::testing::AtLeast;
+
+class CompQueuesTest : public ::testing::Test
+{
+public:
+
+    CompQueuesTest ();
+    virtual ~CompQueuesTest ();
+
+};
+
+using namespace compiz::queues;
+
+class MockQueueReleaseRemovable :
+    public QueueReleaseRemoveInterface
+{
+    public:
+
+
+};
+
+class ReleaseRemovableDelegate :
+    public QueueReleaseInterface
+{
+    public:
+
+	ReleaseRemovableDelegate (void *releasable) :
+	    mReleasable (releasable)
+	{
+	}
+
+	~ReleaseRemovableDelegate ()
+	{
+	    if (mInterface)
+		mInterface->removeReleasable (static_cast <QueueReleaseInterface *> (mReleasable));
+	}
+
+	void doSetRemoveInterface (QueueReleaseRemoveInterface *interface)
+	{
+	    mInterface = interface;
+	}
+
+    private:
+
+	QueueReleaseRemoveInterface *mInterface;
+	void                        *mReleasable;
+};
+
+template <class T>
+class MockQueueReleasable :
+    public QueueReleasableInterface <T>
+{
+    public:
+
+	MOCK_METHOD1_T (doSetRemoveInterface, void (QueueReleaseRemoveInterface *));
+	MOCK_METHOD1_T (doRelease, bool (const T &));
+
+	MockQueueReleasable () :
+	    mRemovableDelegate (this)
+	{
+	}
+
+	void DelegateToFake ()
+	{
+	    ON_CALL (*this, doSetRemoveInterface (_)).WillByDefault (Invoke (&mRemovableDelegate, &ReleaseRemovableDelegate::doSetRemoveInterface));
+	}
+
+    private:
+
+	ReleaseRemovableDelegate mRemovableDelegate;
+};
+
+class MockQueueLock :
+    public QueueLockInterface
+{
+    public:
+
+	MOCK_METHOD0 (doUnlock, bool ());
+	MOCK_METHOD0 (doCallback, void ());
+};
+
+class MockQueueUnlockable :
+    public QueueUnlockInterface
+{
+    public:
+
+	MOCK_METHOD0 (doRelease, void ());
+	MOCK_METHOD1 (doRegisterLock, bool (QueueLockInterface *));
+	MOCK_METHOD1 (doUnregisterLock, bool (QueueLockInterface *));
+};
+
+template <class T>
+class QueueLockGeneratorDelegate :
+    public QueueLockGeneratorInterface
+{
+    public:
+
+	QueueLockGeneratorDelegate (QueueUnlockInterface *unlockable) :
+	    mUnlockable (unlockable)
+	{
+	}
+
+	boost::shared_ptr <QueueLockInterface> doObtainLock (const pendingItemsFunc &f)
+	{
+	    return typename boost::shared_ptr <T> (new T (mUnlockable, f));
+	}
+
+    private:
+
+	QueueUnlockInterface *mUnlockable;
+};
+
+class PendingItemsInterface
+{
+    public:
+
+	void pending (QueueReleaseInterface *lock) { doPending (lock); }
+
+    protected:
+
+	virtual void doPending (QueueReleaseInterface *lock) = 0;
+};
+
+class MockPendingItems :
+    public PendingItemsInterface
+{
+    public:
+
+	MOCK_METHOD1 (doPending, void (QueueReleaseInterface *));
+};
+
+template <class T>
+class MockQueue :
+    public QueueInterface <T>,
+    public QueueLockGeneratorInterface
+{
+    public:
+
+	MOCK_METHOD2_T (doAddPending, void (const T &, QueueReleasableInterface <T> *r));
+	MOCK_METHOD1_T (doObtainLock, boost::shared_ptr <QueueLockInterface> (const pendingItemsFunc &));
+
+
+	void Delegate (QueueInterface <T> *queue, QueueLockGeneratorInterface *gen)
+	{
+	    if (queue)
+		ON_CALL (*this, doAddPending (_, _)).WillByDefault (Invoke (static_cast <QueueInterface <T> *> (queue), &QueueInterface <T>::addPending));
+
+	    if (gen)
+		ON_CALL (*this, doObtainLock (_)).WillByDefault (Invoke (static_cast <QueueLockGeneratorInterface *> (gen), &QueueLockGeneratorInterface::obtainLock));
+	}
+};
+
+template <class T>
+class MockQueueStorage :
+    public QueueStorageInterface <T>
+{
+    public:
+
+	MOCK_METHOD1_T (doRemoveReleasable, void (QueueReleaseInterface *));
+	MOCK_METHOD2_T (doStore, bool (QueueReleasableInterface <T> *, const T &));
+	MOCK_METHOD0_T (doRelease, void ());
+
+	void Delegate (QueueStorageInterface <T> *storage)
+	{
+	    ON_CALL (*this, doRemoveReleasable (_)).WillByDefault (Invoke (storage, &QueueStorageInterface<T>::removeReleasable));
+	    ON_CALL (*this, doStore (_, _)).WillByDefault (Invoke (storage, &QueueStorageInterface<T>::store));
+	    ON_CALL (*this, doRelease ()).WillByDefault (Invoke (storage, &QueueStorageInterface<T>::release));
+	}
+};
+
+#endif