Queue / Array in C++

Makefile

all:
	g++ -o QueueArrayTest test.cc -lpthread --debug

QueueArray.h

#ifndef QUEUEARRAY_H
#define QUEUEARRAY_H

/*
 *  The MIT License (MIT)
 *
 *  Copyright (c) 2014, vmolsa <ville.molsa@gmail.com> @ https://github.com/vmolsa
 *
 *  Permission is hereby granted, free of charge, to any person obtaining a copy
 *  of this software and associated documentation files (the "Software"), to deal
 *  in the Software without restriction, including without limitation the rights
 *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *  copies of the Software, and to permit persons to whom the Software is
 *  furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in all
 *  copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 *  SOFTWARE.
 *
 */

#ifdef USE_DEBUG
  #ifndef assert
    #include <assert.h>
  #endif
#else
  #ifndef assert
    #define assert(check)
  #endif
#endif

#ifdef USE_PTHREAD
  #include <pthread.h>
  #define QueueLocker pthread_mutex_t
  #define QueueLockInit(lock) pthread_mutex_init(&lock, 0)
  #define QueueLockDestroy(lock) pthread_mutex_destroy(&lock)
  #define QueueLock(lock) pthread_mutex_lock(&lock)
  #define QueueUnlock(lock) pthread_mutex_unlock(&lock)
#endif

namespace QueueArray {

template <class L> class Queue {
 public:
  inline explicit Queue() :
    This(0),
    parent(this),
    self(this),
    next(this),
    prev(this)
  {
#ifdef QueueLocker
    QueueLockInit(lock);
#endif
  }

  inline Queue(L *ptr) :
    This(ptr),
    parent(this),
    self(this),
    next(this),
    prev(this)
  {
#ifdef QueueLocker
    QueueLockInit(lock);
#endif 
  }
  
#ifdef QueueLocker
  inline ~Queue() {
    QueueLockDestroy(lock);
  }
#endif
  
  inline void Dispose() {
    if (parent == self && next != parent) {
      Pop(next);
      Dispose();
    }
  }
  
  // return 0; => continue
  // return <= -1 || 1 =<; => break
  
  typedef int (*QueueCallback)(Queue<L> *arg, void *payload, Queue<L> **retval);

  inline int forEach(QueueCallback callback) const {
    Queue<L> *retval = NULL;
    return forEach(callback, 0, &retval);
  }

  inline int forEach(QueueCallback callback, Queue<L> **retval) const {
    return forEach(callback, 0, retval);
  }

  inline int forEach(QueueCallback callback, void *payload, Queue<L> **retval) const {
    Queue *cur = parent->next;
    int ret = 0;
    
    while (cur != 0 && cur != self) {
      if ((ret = callback(cur, payload, retval))) {
        return ret;
      }
      
      cur = cur->next;
    }
    
    return 0;
  }

  template <class T> inline int forEach(QueueCallback callback, T *payload) const {
    Queue<L> *retval = NULL;
    return forEach(callback, static_cast<void*>(payload), &retval);
  }
  
  template <class T> inline int forEach(QueueCallback callback, T *payload, Queue<L> **retval) const {
    return forEach(callback, static_cast<void*>(payload), retval);
  }
  
  inline L* operator->() const { return This; }
  inline L* operator*() const { return This; }

  inline Queue *Insert(L *ptr) {
#ifdef QueueLocker
    QueueLock(lock);
#endif
    assert(ptr);
    Queue *cur = parent;
    Queue *entry = new Queue(ptr);

    entry->parent = cur;
    entry->prev = cur;
    entry->next = cur->next;
    entry->prev->next = entry;
    entry->next->prev = entry;   
#ifdef QueueLocker
    QueueUnlock(lock);
#endif

    return entry;
  }

  inline Queue *Append(L *ptr) {
#ifdef QueueLocker
    QueueLock(lock);
#endif
    assert(ptr);
    Queue *cur = parent;
    Queue *entry = new Queue(ptr);

    entry->parent = cur;
    entry->next = cur;
    entry->prev = cur->prev;
    entry->prev->next = entry;
    entry->next->prev = entry; 
#ifdef QueueLocker
    QueueUnlock(lock);
#endif

    return entry;
  }
  
  inline void Unshift(L *ptr) {
    const Queue *ret = Insert(ptr);
    assert(ret);
  }
  
  inline void Push(L *ptr) {
    const Queue *ret = Append(ptr);
    assert(ret);
  }
  
  inline void Pop() {
    if (parent != self) {
      parent->Pop(self);
    }
  }
  
  inline void Pop(L* ptr) const {
    if (parent == self) {
      Queue *cur = parent->next;

      while (cur != 0 && cur != parent) {
        if (**cur == ptr) {
          cur->Pop();
          break;
        }

        cur = cur->next;
      }
    } else {
      parent->Pop(ptr);
    }
  }

 private:
  inline void Pop(Queue<L> *cur) {
    if (parent == self) {
#ifdef QueueLocker
      QueueLock(lock);
#endif
      if (cur != 0) {
        cur->next->prev = cur->prev;
        cur->prev->next = cur->next;
        delete cur;
      }
#ifdef QueueLocker
      QueueUnlock(lock);
#endif
    } else {
      cur->Pop();
    }
  }

 protected:
  L* This;
#ifdef QueueLocker
  QueueLocker lock;
#endif
  Queue *parent;
  Queue *self;
  Queue *next;
  Queue *prev;
};

template <class L> class Array {
 public:  
  inline Array() :
    heap(0),
    length(0)
  { }
  
  ~Array() {
    Dispose();
  }
  
  inline void Dispose() {
    heap.Dispose();
  }
  
  inline int Length() {
    return length;
  }
 
  inline void Unshift(L* ptr) {
    assert(ptr);
    heap.Unshift(ptr);
    length++;
  }
 
  inline void Push(L* ptr) {
    assert(ptr);  
    heap.Push(ptr);
    length++;
  }
 
  inline void Pop(const int index) {
    Queue<L> *entry = 0;
    int i = index;
    
    if (heap.forEach(Array::inQueue, &i, &entry)) {
      entry->Pop();
    }
    
    length--;
  }
  
  inline const L* operator[] (const int index) const {
    Queue<L> *entry = 0;
    int i = index;
    
    if (heap.forEach(Array::inQueue, &i, &entry)) {
      return **entry;
    }
    
    return 0;
  }
  
 private:
  static int inQueue(Queue<L> *arg, void *payload, Queue<L> **retval) {
    int *index = static_cast<int*>(payload);
    
    if (!(*index)) {
      *retval = arg;
      return 1;
    }
    
    (*index)--;
    return 0;
  }
 
  Queue<L> heap;
  int length;
};

}

#endif

test.cc

//#define USE_DEGUG
//#define USE_PTHREAD

#include <iostream>
#include "QueueArray.h"

int inQueue(QueueArray::Queue<const char> *arg, void *payload, QueueArray::Queue<const char> **retval) {
  std::cout << "inQueue(" << **arg << ")" << std::endl;
  
  *retval = arg;

  return 0;
}

int main() {
  const char *p1 = "Hello";
  const char *p2 = "World";
  const char *p3 = "cat";
  const char *p4 = "dog";

  int i;
  QueueArray::Array<const char> list;

  list.Unshift(p1);
  list.Unshift(p2);
  list.Unshift(p3);
  list.Push(p4);

  std::cout << "Length: " << list.Length() << std::endl;
    
  for (i = 0; i < list.Length(); i++) {
    std::cout << list[i] << std::endl;
  }
  
  list.Pop(3);
  list.Pop(2);
  
  for (i = 0; i < list.Length(); i++) {
    std::cout << list[i] << std::endl;
  }
  
  list.Dispose();
  QueueArray::Queue<const char> q;
  
  q.Unshift(p1);
  q.Unshift(p2);
  q.Unshift(p3);
  q.Push(p4);
  
  QueueArray::Queue<const char> *last = NULL;
  q.forEach(inQueue, &last);
  
  if (last) {
    std::cout << "Last Entry: " << **last << std::endl;
    last->Pop();
  }
  
  q.Pop(p2);
  q.Pop(p3);
  
  q.forEach(inQueue);
  q.Dispose();

  return 0;
}