/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You 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.
 */

/**
 * @author Pavel A. Ozhdikhin
 */

#ifndef _QUEUE_H_
#define _QUEUE_H_

#include "MemoryManager.h"
#include "Dlink.h"

namespace Jitrino {

class queueImpl
{ 
public:
    queueImpl(MemoryManager& m) : mm(m) {}
    void* pop() {
        if (isEmpty()) return NULL;
        queueElem* e = workList.next();
        free(e); // put it back to freeList
        return e->elem;
    }
    void  push(void *elem) {
        queueElem* se = getFreeQueueElem();
        if (se == NULL)
            se = new (mm) queueElem();
        se->elem = elem;
        se->insertBefore(&workList);
    };
    // if stack is empty, NULL is returned
    void* top() {return workList.next()->elem;}
    // returns true if empty
    bool  isEmpty() {return workList.next() == &workList;}
private:
    class queueElem : public Dlink 
    {
    public:
        void     *elem;

        queueElem() : elem(NULL) {}
        queueElem* next() {return (queueElem*)_next;}
        queueElem* prev() {return (queueElem*)_prev;}
    };

    MemoryManager& mm;
    queueElem freeList;
    queueElem workList; 

    void  free(queueElem* n) {
        n->unlink();
        n->insertBefore(&freeList); 
    }
    queueElem* getFreeQueueElem() {
        queueElem *n = freeList.next();
        if (n != &freeList) // there is a free node
        {
            n->unlink();
            n->elem = NULL;
            return n;
        }
        return NULL;
    }
};

template <class T>
class Queue : public queueImpl {
public:
    Queue(MemoryManager& m) : queueImpl(m) {}
    T*    pop()         {return (T*)queueImpl::pop();}
    void  push(T* elem) {queueImpl::push(elem);}
    T*    top()         {return (T*)queueImpl::top();}
};

} //namespace Jitrino 

#endif // _QUEUE_H_