// queue.h -- interface for a queue
|
#ifndef SQUEUE_H_
|
#define SQUEUE_H_
|
#include "common.h"
|
#include "mm.h"
|
#include "pcsem.h"
|
|
template <typename T>
|
class Node {
|
public:
|
T item;
|
Node<T> * next;
|
void *operator new(size_t size){
|
return mm_malloc(size);
|
}
|
|
void operator delete(void *p) {
|
return mm_free(p);
|
}
|
};
|
|
template <typename T>
|
class SQueue
|
{
|
private:
|
// class scope definitions
|
// Node is a nested structure definition local to this class
|
void *shmp;
|
int first;
|
|
enum {Q_SIZE = 10};
|
|
int slots;
|
int items;
|
// private class members
|
Node<T> * front; // pointer to front of Queue
|
Node<T> * rear; // pointer to rear of Queue
|
size_t count; // current number of size in Queue
|
const size_t qsize; // maximum number of size in Queue
|
// preemptive definitions to prevent public copying
|
SQueue(const SQueue & q) : qsize(0) { }
|
SQueue & operator=(const SQueue & q) { return *this;}
|
bool _enqueue(const T &item); // add item to end
|
bool _dequeue(T &item); // remove item from front
|
public:
|
SQueue(size_t qs = Q_SIZE); // create queue with a qs limit
|
~SQueue();
|
bool isempty() const;
|
bool isfull() const;
|
int size() const;
|
bool enqueue(const T &item); // add item to end
|
bool enqueue_nowait(const T &item);
|
bool enqueue_timeout(const T &item, struct timespec *timeout);
|
bool dequeue(T &item);
|
bool dequeue_nowait(T &item);
|
bool dequeue_timeout(T &item, struct timespec * timeout);
|
|
|
|
T& operator[](int i);
|
};
|
|
|
|
|
// Queue methods
|
template <typename T>
|
SQueue<T>::SQueue(size_t qs) : qsize(qs)
|
{
|
front = rear = NULL; // or nullptr
|
count = 0;
|
|
//std::cout << "=====qsize ==" << qsize << std::endl;
|
slots = pcsem::init(145, qsize);
|
items = pcsem::init(146, 0);
|
|
}
|
|
template <typename T>
|
SQueue<T>::~SQueue()
|
{
|
std::cout << "squeue destory" << std::endl;
|
pcsem::remove(slots);
|
pcsem::remove(items);
|
Node<T> * temp;
|
while (front != NULL) // while queue is not yet empty
|
{
|
temp = front; // save address of front item
|
front = front->next;// reset pointer to next item
|
delete temp; // delete former front
|
}
|
|
}
|
|
template <typename T>
|
bool SQueue<T>::isempty() const
|
{
|
return count == 0;
|
}
|
|
template <typename T>
|
bool SQueue<T>::isfull() const
|
{
|
return count == qsize;
|
}
|
|
template <typename T>
|
int SQueue<T>::size() const
|
{
|
return count;
|
}
|
|
// Add item to queue
|
template <typename T>
|
bool SQueue<T>::_enqueue(const T & item)
|
{
|
if (isfull())
|
return false;
|
|
Node<T> * add = new Node<T>; // create node
|
|
// on failure, new throws std::bad_alloc exception
|
add->item = item; // set node pointers
|
add->next = NULL; // or nullptr;
|
count++;
|
if (front == NULL) // if queue is empty,
|
front = add; // place item at front
|
else
|
rear->next = add; // else place at rear
|
rear = add;
|
|
return true;
|
}
|
|
template <typename T>
|
bool SQueue<T>::enqueue(const T & item)
|
{
|
if (pcsem::dec(slots) == -1) {
|
err_exit(errno, "enqueue");
|
}
|
|
if (SQueue<T>::_enqueue(item)) {
|
pcsem::inc(items);
|
return true;
|
}
|
return false;
|
|
}
|
|
template <typename T>
|
bool SQueue<T>::enqueue_nowait(const T & item)
|
{
|
if (pcsem::dec_nowait(slots) == -1) {
|
if (errno == EAGAIN)
|
return false;
|
else
|
err_exit(errno, "enqueue_nowait");
|
}
|
|
if (SQueue<T>::_enqueue(item)) {
|
pcsem::inc(items);
|
return true;
|
}
|
return false;
|
|
}
|
|
template <typename T>
|
bool SQueue<T>::enqueue_timeout(const T & item, struct timespec * timeout)
|
{
|
if (pcsem::dec_timeout(slots, timeout) == -1) {
|
if (errno == EAGAIN)
|
return false;
|
else
|
err_exit(errno, "enqueue_timeout");
|
}
|
|
if (SQueue<T>::_enqueue(item)){
|
pcsem::inc(items);
|
return true;
|
}
|
return false;
|
|
}
|
|
|
// Place front item into item variable and remove from queue
|
template <typename T>
|
bool SQueue<T>::_dequeue(T & item)
|
{
|
if (isempty())
|
return false;
|
item = front->item; // set item to first item in queue
|
count--;
|
Node<T> * temp = front; // save location of first item
|
front = front->next; // reset front to next item
|
delete temp; // delete former first item
|
if (count == 0)
|
rear = NULL;
|
|
return true;
|
}
|
|
template <typename T>
|
bool SQueue<T>::dequeue(T & item)
|
{
|
if (pcsem::dec(items) == -1) {
|
err_exit(errno, "dequeue");
|
}
|
|
if (SQueue<T>::_dequeue(item)) {
|
pcsem::inc(slots);
|
return true;
|
}
|
return false;
|
|
}
|
|
template <typename T>
|
bool SQueue<T>::dequeue_nowait(T & item)
|
{
|
if (pcsem::dec_nowait(items) == -1) {
|
if (errno == EAGAIN)
|
return false;
|
else
|
err_exit(errno, "dequeue_nowait");
|
}
|
|
if (SQueue<T>::_dequeue(item)) {
|
pcsem::inc(slots);
|
return true;
|
}
|
return false;
|
|
}
|
|
template <typename T>
|
bool SQueue<T>::dequeue_timeout(T & item, struct timespec * timeout)
|
{
|
if (pcsem::dec_timeout(items, timeout) == -1) {
|
if (errno == EAGAIN)
|
return false;
|
else
|
err_exit(errno, "dequeue_timeout");
|
}
|
|
if (SQueue<T>::_dequeue(item)) {
|
pcsem::inc(slots);
|
return true;
|
}
|
return false;
|
|
}
|
|
|
template <class T>
|
T& SQueue<T>::operator[](int i)
|
{
|
if (i < 0 || i >= count)
|
{
|
std::cerr << "Error in array limits: " << i << " is out of range\n";
|
std::exit(EXIT_FAILURE);
|
}
|
|
Node<T> * temp = front;
|
while(i-->0) {
|
temp = temp->next;
|
}
|
return temp->item;
|
}
|
|
|
#endif
|
