From 14d2085e35bbc3e5c73c018e5c70e8093003820f Mon Sep 17 00:00:00 2001 From: Tycho Bickerstaff Date: Sat, 21 Dec 2013 14:43:32 +0000 Subject: basic threadsafe queue interface --- src/OSSupport/Queue.h | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) create mode 100644 src/OSSupport/Queue.h (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h new file mode 100644 index 000000000..838a101e0 --- /dev/null +++ b/src/OSSupport/Queue.h @@ -0,0 +1,30 @@ +#pragma once + +template +class cDeleter +{ + public: + static void Delete(T) {}; +} + +template +class cQueue +{ +public: + cQueue(int warnsize); + cQueue(cQueue& queue); + ~cQueue(); + + void EnqueueItem(T item); + bool TryDequeueItem(T& item); + T DequeueItem(); + void BlockTillEmpty(cEvent CancelationEvent); + void Clear(); + int Size(); + +private: + int warnsize; +} + +//template classes must be implemented in the header +#include "Queue.inc" -- cgit v1.2.3 From f3736b1eb7bf698518cdb853ee29ee96b9c24a52 Mon Sep 17 00:00:00 2001 From: Tycho Bickerstaff Date: Tue, 31 Dec 2013 15:48:57 +0000 Subject: refactored chunk Queue to seperate class --- src/OSSupport/Queue.h | 110 +++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 92 insertions(+), 18 deletions(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index 838a101e0..eb323b067 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -1,30 +1,104 @@ + #pragma once +#include + +#include "../OSSupport/Promise.h" + +//this empty struct allows function inlining template -class cDeleter +struct cQueueFuncs { public: static void Delete(T) {}; -} + static void Combine(T&, const T) {}; +}; -template +template > class cQueue { + +typedef typename std::list ListType; +//magic typedef to persuade clang that the iterator is a type +typedef typename ListType::iterator iterator; public: - cQueue(int warnsize); - cQueue(cQueue& queue); - ~cQueue(); - - void EnqueueItem(T item); - bool TryDequeueItem(T& item); - T DequeueItem(); - void BlockTillEmpty(cEvent CancelationEvent); - void Clear(); - int Size(); - + cQueue() {} + ~cQueue() {} + + void EnqueueItem(ItemType a_item) + { + cCSLock Lock(m_CS); + m_contents.push_back(a_item); + m_evtAdded.Set(); + } + void EnqueueItemIfNotPresent(ItemType a_item) + { + cCSLock Lock(m_CS); + + for (iterator itr = m_contents.begin(); itr != m_contents.end(); ++itr) + { + if((*itr) == a_item) { + Funcs funcTable; + funcTable.Combine(*itr,a_item); + return; + } + } + m_contents.push_back(a_item); + m_evtAdded.Set(); + } + bool TryDequeueItem(ItemType& item) + { + cCSLock Lock(m_CS); + if (m_contents.size() == 0) return false; + item = m_contents.front(); + m_contents.pop_front(); + return true; + } + ItemType DequeueItem() + { + cCSLock Lock(m_CS); + while (m_contents.size() == 0) + { + cCSUnlock Unlock(m_CS); + m_evtAdded.Wait(); + } + return m_contents.pop_front(); + } + cPromise* BlockTillEmpty() { + return new cEmptyQueuePromise(this); + } + //can all be inlined when delete is a noop + void Clear() + { + cCSLock Lock(m_CS); + Funcs funcTable; + while (!m_contents.empty()) + { + funcTable.Delete(m_contents.front()); + m_contents.pop_front(); + } + } + size_t Size() + { + cCSLock Lock(m_CS); + return m_contents.size(); + } + bool Remove(ItemType item) + { + cCSLock Lock(m_CS); + m_contents.remove(item); + } + private: - int warnsize; -} + ListType m_contents; + cCriticalSection m_CS; + cEvent m_evtAdded; -//template classes must be implemented in the header -#include "Queue.inc" + class cEmptyQueuePromise : public cPromise { + public: + cEmptyQueuePromise(cQueue* a_Queue) : cPromise(), m_Queue(a_Queue) {} + virtual bool IsCompleted() {return m_Queue->Size() != 0;} + private: + cQueue* m_Queue; + }; +}; -- cgit v1.2.3 From 042b72bc172e7eb4e9ef7668ae28be6e7a3b4036 Mon Sep 17 00:00:00 2001 From: Tycho Bickerstaff Date: Thu, 2 Jan 2014 12:32:55 +0000 Subject: rewrote queue not to use promises for waits --- src/OSSupport/Queue.h | 24 +++++++++++------------- 1 file changed, 11 insertions(+), 13 deletions(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index eb323b067..153e201c1 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -3,8 +3,6 @@ #include -#include "../OSSupport/Promise.h" - //this empty struct allows function inlining template struct cQueueFuncs @@ -52,6 +50,7 @@ public: if (m_contents.size() == 0) return false; item = m_contents.front(); m_contents.pop_front(); + m_evtRemoved.Set(); return true; } ItemType DequeueItem() @@ -62,10 +61,15 @@ public: cCSUnlock Unlock(m_CS); m_evtAdded.Wait(); } - return m_contents.pop_front(); + ItemType item = m_contents.front(); + m_contents.pop_front(); + m_evtRemoved.Set(); + return item; } - cPromise* BlockTillEmpty() { - return new cEmptyQueuePromise(this); + void BlockTillEmpty() { + //There is a very slight race condition here if the load completes between the check + //and the wait. + while(!(Size() == 0)){m_evtRemoved.Wait();} } //can all be inlined when delete is a noop void Clear() @@ -87,18 +91,12 @@ public: { cCSLock Lock(m_CS); m_contents.remove(item); + m_evtRemoved.Set(); } private: ListType m_contents; cCriticalSection m_CS; cEvent m_evtAdded; - - class cEmptyQueuePromise : public cPromise { - public: - cEmptyQueuePromise(cQueue* a_Queue) : cPromise(), m_Queue(a_Queue) {} - virtual bool IsCompleted() {return m_Queue->Size() != 0;} - private: - cQueue* m_Queue; - }; + cEvent m_evtRemoved; }; -- cgit v1.2.3 From d522619ce2ac05831febedea675d121445dcbdbe Mon Sep 17 00:00:00 2001 From: Tycho Bickerstaff Date: Thu, 2 Jan 2014 17:43:57 +0000 Subject: added documentation --- src/OSSupport/Queue.h | 52 ++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 45 insertions(+), 7 deletions(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index 153e201c1..1f0c19f40 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -1,34 +1,55 @@ +// Queue.h + +// Implements the cQueue class representing a thread safe queue + #pragma once #include -//this empty struct allows function inlining +/* +Usage: +To use the callback functions Delete and Combine create a class with the two +methods and pass it as a second template parameter to cQueue. The class does +not need to inherit cQueueFuncs but you do so to document the classes purpose. +The second template parmeter is optional if not overriding the callback +functions +*/ + +// this empty struct allows for the callback functions to be inlined template struct cQueueFuncs { public: + // Called when an Item is deleted form the queue without being returned static void Delete(T) {}; - static void Combine(T&, const T) {}; + // Called when an Item is inserted with EnqueueItemIfNotPresent and + // there is another equal value already inserted + static void Combine(T& a_existing, const T a_new) {}; }; template > class cQueue { - +// internal typedef for a List of Items typedef typename std::list ListType; -//magic typedef to persuade clang that the iterator is a type +// magic typedef to persuade clang that the iterator is a type typedef typename ListType::iterator iterator; public: cQueue() {} ~cQueue() {} + // Enqueues an item to the queue, may block if other threads are accessing + // the queue. void EnqueueItem(ItemType a_item) { cCSLock Lock(m_CS); m_contents.push_back(a_item); m_evtAdded.Set(); } + + // Enqueues an item to the queue if not already present as determined with + // operator ==. Will block other threads from accessing the queue. void EnqueueItemIfNotPresent(ItemType a_item) { cCSLock Lock(m_CS); @@ -44,6 +65,11 @@ public: m_contents.push_back(a_item); m_evtAdded.Set(); } + + // Dequeues an Item from the queue if any are present, provides no + // guarantees about success if the list is empty but an item is enqueued at + // the same time. Returns true if successful. Value of item is undefined if + // Dequeuing was unsuccessful. bool TryDequeueItem(ItemType& item) { cCSLock Lock(m_CS); @@ -53,6 +79,8 @@ public: m_evtRemoved.Set(); return true; } + + // Dequeues an Item from the Queue, blocking until an Item is Available. ItemType DequeueItem() { cCSLock Lock(m_CS); @@ -66,12 +94,17 @@ public: m_evtRemoved.Set(); return item; } + + // Blocks Until the queue is Empty, Has a slight race condition which may + // cause it to miss the queue being empty. void BlockTillEmpty() { - //There is a very slight race condition here if the load completes between the check - //and the wait. + // There is a very slight race condition here if the load completes between the check + // and the wait. while(!(Size() == 0)){m_evtRemoved.Wait();} } - //can all be inlined when delete is a noop + + // Removes all Items from the Queue, calling Delete on each of them. + // can all be inlined when delete is a noop void Clear() { cCSLock Lock(m_CS); @@ -82,11 +115,16 @@ public: m_contents.pop_front(); } } + + // Returns the Size at time of being called + // Do not use to detirmine weather to call DequeueItem, use TryDequeue instead size_t Size() { cCSLock Lock(m_CS); return m_contents.size(); } + + // Removes an Item from the queue bool Remove(ItemType item) { cCSLock Lock(m_CS); -- cgit v1.2.3 From 6f3c5b806eb59e2610f8bac9ad3fff24994609c9 Mon Sep 17 00:00:00 2001 From: Tycho Bickerstaff Date: Fri, 3 Jan 2014 11:22:01 +0000 Subject: implement xsofts recommendations --- src/OSSupport/Queue.h | 24 +++++++++++++++--------- 1 file changed, 15 insertions(+), 9 deletions(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index 1f0c19f40..65f9bd258 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -5,15 +5,18 @@ #pragma once -#include - /* +Items can be added multiple times to a queue, there are two functions for +adding, EnqueueItem() and EnqueueItemIfNotPresent(). The first one always +enqueues the specified item, the second one checks if the item is already +present and only queues it if it isn't. + Usage: -To use the callback functions Delete and Combine create a class with the two -methods and pass it as a second template parameter to cQueue. The class does -not need to inherit cQueueFuncs but you do so to document the classes purpose. -The second template parmeter is optional if not overriding the callback -functions +To create a queue of type T, instantiate a cQueue object. You can also +modify the behavior of the queue when deleting items and when adding items +that are already in the queue by providing a second parameter, a class that +implements the functions Delete() and Combine(). An example is given in +cQueueFuncs and is used as the default behavior. */ // this empty struct allows for the callback functions to be inlined @@ -25,7 +28,7 @@ struct cQueueFuncs static void Delete(T) {}; // Called when an Item is inserted with EnqueueItemIfNotPresent and // there is another equal value already inserted - static void Combine(T& a_existing, const T a_new) {}; + static void Combine(T& a_existing, const T& a_new) {}; }; template > @@ -73,7 +76,10 @@ public: bool TryDequeueItem(ItemType& item) { cCSLock Lock(m_CS); - if (m_contents.size() == 0) return false; + if (m_contents.size() == 0) + { + return false; + } item = m_contents.front(); m_contents.pop_front(); m_evtRemoved.Set(); -- cgit v1.2.3 From 0e8bb3bf415e4c0fe6c8bd0aa06dc2d9af2823c4 Mon Sep 17 00:00:00 2001 From: Tycho Date: Fri, 3 Jan 2014 08:34:41 -0800 Subject: fixed failure to return a value from Remove --- src/OSSupport/Queue.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index 65f9bd258..bf6d7e451 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -134,8 +134,8 @@ public: bool Remove(ItemType item) { cCSLock Lock(m_CS); - m_contents.remove(item); m_evtRemoved.Set(); + return m_contents.remove(item); } private: -- cgit v1.2.3 From 14ec68d8d309d3fdf8e0af47196b1cf8609d017d Mon Sep 17 00:00:00 2001 From: Tycho Date: Fri, 3 Jan 2014 08:49:14 -0800 Subject: actual fix --- src/OSSupport/Queue.h | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index bf6d7e451..fc942b3e1 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -134,8 +134,15 @@ public: bool Remove(ItemType item) { cCSLock Lock(m_CS); - m_evtRemoved.Set(); - return m_contents.remove(item); + for (iterator itr = m_contents.begin(); itr != m_contents.end(); ++itr) + { + if((*itr) == a_item) { + m_contents.erase(itr); + m_evtRemoved.Set(); + return true; + } + } + return false; } private: -- cgit v1.2.3 From 13bbb3d99dee8041d47279cae3484c3083491f18 Mon Sep 17 00:00:00 2001 From: Tycho Date: Fri, 3 Jan 2014 08:56:20 -0800 Subject: derp --- src/OSSupport/Queue.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index fc942b3e1..ab42c871e 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -131,7 +131,7 @@ public: } // Removes an Item from the queue - bool Remove(ItemType item) + bool Remove(ItemType a_item) { cCSLock Lock(m_CS); for (iterator itr = m_contents.begin(); itr != m_contents.end(); ++itr) -- cgit v1.2.3 From d26c0e3815a8e3c38447eeb65b052a5d7c43da73 Mon Sep 17 00:00:00 2001 From: Tycho Date: Fri, 3 Jan 2014 09:42:35 -0800 Subject: Fixed Documentation --- src/OSSupport/Queue.h | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'src/OSSupport/Queue.h') diff --git a/src/OSSupport/Queue.h b/src/OSSupport/Queue.h index ab42c871e..cde26e415 100644 --- a/src/OSSupport/Queue.h +++ b/src/OSSupport/Queue.h @@ -69,10 +69,8 @@ public: m_evtAdded.Set(); } - // Dequeues an Item from the queue if any are present, provides no - // guarantees about success if the list is empty but an item is enqueued at - // the same time. Returns true if successful. Value of item is undefined if - // Dequeuing was unsuccessful. + // Dequeues an Item from the queue if any are present. Returns true if + // successful. Value of item is undefined if Dequeuing was unsuccessful. bool TryDequeueItem(ItemType& item) { cCSLock Lock(m_CS); -- cgit v1.2.3