• Tweet

• Tweet

Problem statement :

FIFO Queues In Fixed Memory
------------------------------------------------------------------------------

Solution Requirements
---------------------
Your solution should compile and be capable of managing a variable number of
FIFO byte queues, each with variable length, in a small, fixed amount of
memory.

You should provide implementations of the five functions within
QueueManager.cpp.

!! DO NOT MODIFY QueueManager.h !!

You can define additioanl functions within QueueManger.cpp as necessary,
but do not change the QueueManager interface.

Memory Restrictions
-------------------
- No memory dynamically allocated during program execution (new, malloc, etc.).
- All queues must share a single storage space of MAX_DATA_SIZE for their data.
- You may statically allocate as much additional memory as you choose, but
  remember that efficiency is important and that any tradeoffs associated
  with allocating additional storage should be explained.
- You should statically allocate whatever memory you're going to use within
  the QueueManager namespace in QueueManager.cpp.

Common Cases
------------
On average while your system is running, there will be a dozen or so queues
with an average of 100 or so bytes in each queue. Your functions may be asked
to create a larger number of queues with fewer bytes in each. Your functions
may be asked to create a smaller number of queues with more bytes in each.
There may be spikes in the number of queues allocated, or in the size of an
individual queue.  The performance of your code in each of these situations
will be taken into account.  Be sure to explain any tradeoffs you've made to
handle a given case.

Error Handling
--------------
If you are unable to satisfy a request due to lack of memory your code should
call a provided failure function (which will not return):

namespace QueueManager
{
  void onOutOfMemory();
}
 
If the caller makes any illegal request your code should call a provided 
failure function (which will not return):

namespace QueueManager
{
  void onIllegalOperation(const char* fmt = 0, ... );
}

Compilation and Sample Output
-----------------------------
Please compile your implementation of QueueManager.cpp against the provided 
QueueManager.h and main.cpp.

The output of the provided main() should be:

0 1
2 5
3 4 6

Additional Documentation Requirements
-------------------------------------
Please include a description of your implementation.  You should outline areas
in which you feel your solution could be improved given additional time and/or
resources.  

main.cpp

Code:

#include <iostream>
#include <list>
#include <vector>
#include <queue>
#include<set>
#include <algorithm>
#include <map>
#include <cstring>
#include <climits>
#include <stack>
#include <fstream>
#include <assert.h>
#include <memory>

#include "QueueManager.h"

using namespace std;

int main() {
    QueueManager::initializeQueueManager();
    QueueManager::QueueHandle qH =QueueManager::createQueue();
    QueueManager::QueueHandle qH1 =QueueManager::createQueue();
    QueueManager::QueueHandle qH2 =QueueManager::createQueue();
    QueueManager::enQueue(qH,'0');
    QueueManager::enQueue(qH,'1');
    QueueManager::enQueue(qH1,'2');
    QueueManager::enQueue(qH1,'5');
    QueueManager::enQueue(qH2,'3');
    QueueManager::enQueue(qH2,'4');
    QueueManager::enQueue(qH2,'6');

    cout << QueueManager::deQueue(qH) << "\t";
    cout << QueueManager::deQueue(qH) <<endl;

    cout << QueueManager::deQueue(qH1) << "\t";
    cout << QueueManager::deQueue(qH1) <<endl;

    cout << QueueManager::deQueue(qH2) << "\t";
    cout << QueueManager::deQueue(qH2) << "\t";
    cout << QueueManager::deQueue(qH2) <<endl;

    //unsigned  char ch2=QueueManager::deQueue(qH);
    QueueManager::destroyQueue(qH);

//    0 1
//    2 5
//    3 4 6

 return 0;

}

QueueManager.h

//

#define MAX_QUEUES    64
#define MAX_DATA_SIZE 2048

const int QUEUE_HEADER_SIZE = 4;
const int QUEUE_HEADER_STORAGE = 1; // offset at which the Q headers are stored
const int QUEUE_STORAGE_OFFSET = QUEUE_HEADER_STORAGE + QUEUE_HEADER_SIZE*MAX_QUEUES;

const int USABLE_BLOCK_BYTES = 15;

namespace QueueManager
{
    // Queue handles are a single byte.  Do not change the typedef!
    typedef unsigned char QueueHandle;

    // Performs any necessary initialization of the QueueManager.
    void initializeQueueManager();

    // Creates a FIFO byte queue, returns the handle for the created
    // queue.
    QueueHandle createQueue();

    // Destroy the queue specified by queueHandle.
    void destroyQueue (QueueHandle queueHandle);

    // Adds a new byte to the queue specified by queueHandle.
    void enQueue (QueueHandle queueHandle, unsigned char value);

    // Pops the next byte off the queue specified by queueHandle.
    unsigned char deQueue (QueueHandle queueHandle);

    // If you are unable to satisfy a request due to lack of memory your
    // code should call this provided failure function (which will not return):
    void onOutOfMemory();

    // If the caller makes any illegal request your code should call this
    // provided failure function (which will not return):
    void onIllegalOperation(const char* fmt , ... );
    // eg:
    //   int errorCode;
    //   ...
    //   onIllegalOperation("Error in createQueue: %d", errorCode);
}

QueueManager.cpp

//
//
#include <zconf.h>
#include <pthread.h>
//#include <UInts/semaphore.h>
#include <semaphore.h>
#include <iostream>
#include <cstring>
#include "QueueManager.h"
#include "list"
#include <unordered_map>
#include <cstdarg>
namespace QueueManager
{
    // TODO: statically allocate space for data and queue management.
    QueueHandle data[MAX_DATA_SIZE];
    typedef unsigned int UInt;
    typedef unsigned char StorageHandle;
    struct Q
    {
        UInt inUse       : 1;  // 1 if queue is alloc'd, 0 if not
        UInt headBlock   : 7;  // handle to storage block containing deque head
        UInt headOffset  : 4;  // offset of deque head within storage block
        UInt tailBlock   : 7;  // handle to storage block containing deque tail
        UInt tailOffset  : 4;  // offset of deque tail within storage block
        UInt bdBlock    : 7;  // storage list grows by linking after here,
        //   needed for const time
        UInt unused      : 2;
    };
    unsigned char alpha =
            '!';
    std::unordered_map<unsigned char,Q*> um;
    //Q* q=0;

    struct QStorage
    {
        StorageHandle nextBlock;
        unsigned char storage[USABLE_BLOCK_BYTES];
    };

    const int MAX_NUM_BLOCKS =
            (MAX_DATA_SIZE - QUEUE_HEADER_SIZE*MAX_QUEUES - 1) /
            sizeof(QStorage);

    void onOutOfMemory()
    {
        std::cout << "Sorry , We are out of memory";
    }

    char *convNumToBase(unsigned int num, int base)
    {
        static char rep[]= "0123456789ABCDEF";
        static char buf[50];
        char *ptr;

        ptr = &buf[49];
        *ptr = '\0';

        do
        {
            *--ptr = rep[num%base];
            num /= base;
        }while(num != 0);

        return(ptr);
    }

    void onIllegalOperation(const char* fmt = 0, ... ){
        const char *iter;
        unsigned int i;
        char *s;

        //Module 1: Initializing Myprintf's arguments
        va_list arg;
        va_start(arg, fmt);

        for(iter = fmt; *iter != '\0'; iter++)
        {
            while( *iter != '%' )
            {
                putchar(*iter);
                iter++;
            }

            iter++;

            //Module 2: Fetching and executing arguments
            switch(*iter)
            {
                case 'c' : i = va_arg(arg,int); //Fetch char argument
                    putchar(i);
                    break;

                case 'd' : i = va_arg(arg,int);  //Fetch Decimal/Integer argument
                    if(i<0)
                    {
                        i = -i;
                        putchar('-');
                    }
                    puts(convNumToBase(i,10));
                    break;

                case 'o': i = va_arg(arg,unsigned int); //Fetch Octal rep
                    puts(convNumToBase(i,8));
                    break;

                case 's': s = va_arg(arg,char *);  //Fetch string
                    puts(s);
                    break;

                case 'x': i = va_arg(arg,unsigned int); //Fetch Hexadecimal rep
                    puts(convNumToBase(i,16));
                    break;
            }
        }

        //Module 3: Closing argument list to necessary clean-up
        va_end(arg);
    }

    StorageHandle& Freelist()
    {
        return data[0];
    }

    QStorage* GetStorageFromHandle(StorageHandle handle)
    {
        if(handle != 0)
        {
            return reinterpret_cast<QStorage*>(
                    data + QUEUE_STORAGE_OFFSET + sizeof(QStorage)*(handle-1)
            );
        }
        else
        {
            return 0;
        }
    }

    void FreeBlock(StorageHandle block)
    {
        // Link the block back onto the front of the freelist
        GetStorageFromHandle(block)->nextBlock = Freelist();
        Freelist() = block;
    }

    StorageHandle AllocBlock()
    {
        // Pull front block off of freelist
        StorageHandle allocated = Freelist();

        if(allocated != 0)
        {
            Freelist() = GetStorageFromHandle(allocated)->nextBlock;
            GetStorageFromHandle(allocated)->nextBlock = 0;
        }
        else
        {
            QueueManager::onOutOfMemory();
        }

        return allocated;
    }

    // Performs any necessary initialization of the QueueManager.
    void initializeQueueManager()
    {
        // TODO: IMPLEMENT ME

        // Freelist handle initially points at storage block 0
        data[0] = 1;  // 0 is reserved for 'null'

        // Q headers initialized to 0
        memset(data + QUEUE_HEADER_STORAGE, 0, QUEUE_HEADER_SIZE*MAX_QUEUES);

        // Build the freelist, a single-linked list of storage blocks
        for(StorageHandle block = 1; block <= MAX_NUM_BLOCKS; ++block)
        {
            GetStorageFromHandle(block)->nextBlock = block + 1;
        }

        // Last block has 'null' handle
        GetStorageFromHandle(MAX_NUM_BLOCKS)->nextBlock = 0;

    }

    QueueHandle createQueue()
    {//konIllegalOperation
        // TODO: IMPLEMENT ME

        Q* q = 0;

        // Search for a queue header not currently in use
        for(int queueIndex = 0; queueIndex < MAX_QUEUES; ++queueIndex)
        {
            Q* queueHeader = reinterpret_cast<Q*>(
                    data + QUEUE_HEADER_STORAGE + queueIndex*QUEUE_HEADER_SIZE
            );
            if(!queueHeader->inUse)
            {
                q = queueHeader;
                break;
            }
        }

        if(q != 0)
        {
            // Mark this queue as 'in use'
            q->inUse = 1;

            // Allocate a block of storage for the queue to start with
            q->headBlock = AllocBlock();
            q->tailBlock = q->headBlock;
            q->bdBlock = q->headBlock;

            GetStorageFromHandle(q->headBlock)->nextBlock =
                    q->headBlock;

            //  the 'head' and 'tail' pointers of our circular buffer
            // are both set to the first element.
            q->headOffset = q->tailOffset = 0;
        }
        else
        {
            // Tried to create more than 64 queues
            const char* err = "Tried to create more than 64 queues";
            int errCode=1;
            QueueManager::onIllegalOperation("Error in createQueue: %d", errCode);
        }
        um[alpha]=q;
        return alpha++;

    }

    // Destroy the queue specified by queueHandle.
    void destroyQueue (QueueHandle queueHandle)
    {
        Q *q=um[queueHandle];
        //q->headBlock=queueHandle;
        // TODO: IMPLEMENT ME
        StorageHandle blockAfterbdBlock =
                GetStorageFromHandle(q->bdBlock)->nextBlock;
        GetStorageFromHandle(q->bdBlock)->nextBlock = Freelist();
        Freelist() = blockAfterbdBlock;

        // Mark this queue as not 'in use'
        q->inUse = 0;

    }

    // Adds a new byte to the queue specified by queueHandle.
    void enQueue (QueueHandle queueHandle, unsigned char value) {
        // TODO: IMPLEMENT ME
        Q* q =um[queueHandle];
//        q->tailBlock=queueHandle;

        QStorage *tailBlock = GetStorageFromHandle(q->tailBlock);
        tailBlock->storage[q->tailOffset] = value;

        // If the tail wraps to the head block but doesn't collide,
        // move the bud block to where the tail block used to be
        StorageHandle oldTailBlock = q->tailBlock;
        bool updatebdBlock = false;

        unsigned int newOffset = (q->tailOffset + 1) % USABLE_BLOCK_BYTES;
        if (newOffset < q->tailOffset) {
            // Wrap around to head block,
            q->tailBlock = q->headBlock;
            updatebdBlock = true;
        }
            q->tailOffset = newOffset;

            if (q->tailBlock == q->headBlock) {
                if (newOffset == q->headOffset) {
                    // No place to put the next byte, so we need to grow
                    StorageHandle newBlockHandle = AllocBlock();
                    QStorage *newBlock = GetStorageFromHandle(newBlockHandle);

                    // Copy trailing elements, if any, to new block
                    for (unsigned int copyOffset = 0; copyOffset < newOffset; ++copyOffset) {
                        newBlock->storage[copyOffset] =
                                GetStorageFromHandle(q->headBlock)->storage[copyOffset];
                    }

                    // If we just went off the end of a block, that block is the new
                    // bud block
                    if (updatebdBlock) {
                        q->bdBlock = oldTailBlock;
                    }

                    // Link up with new block
                    newBlock->nextBlock = q->headBlock;
                    GetStorageFromHandle(q->bdBlock)->nextBlock = newBlockHandle;
                    q->tailBlock = newBlockHandle;

                    updatebdBlock = false;
                }
            }

            if (updatebdBlock) {
                q->bdBlock = oldTailBlock;
            }
        um[queueHandle]=q;
    }
        // Pops the next byte off the queue specified by queueHandle.
        unsigned char deQueue(QueueHandle queueHandle) {
            // TODO: IMPLEMENT ME
            Q* q =um[queueHandle];
//        q->headBlock=queueHandle;
            if (q->headBlock == q->tailBlock && q->headOffset == q->tailOffset) {
                // Queue is empty!
                const char *err = "Queue is empty!";
                //const char * a = err;
                int errCode=2;
                QueueManager::onIllegalOperation("Error in deQueue: %d", errCode);
                fprintf(stderr, "%s\n", err);
            }
            // We always dequeue at the HEAD
            unsigned char bytePopped =
                    GetStorageFromHandle(q->headBlock)->storage[q->headOffset];

            unsigned int newOffset = (q->headOffset + 1) % USABLE_BLOCK_BYTES;

            if (newOffset < q->headOffset) {
                StorageHandle newHeadBlock =
                        GetStorageFromHandle(q->headBlock)->nextBlock;

                // If the block we just left wasn't the tail block...
                if (q->headBlock != q->tailBlock) {
                    // The block we just left is not being used at all.
                    //  it MUST  be immediately after
                    // the tail block. So we can unlink it, and free it.
                    GetStorageFromHandle(q->tailBlock)->nextBlock = newHeadBlock;
                    FreeBlock(q->headBlock);
                }

                q->headBlock = newHeadBlock;
            }

            q->headOffset = newOffset;

            // For debugging
            //PrintStatus(q);
            um[queueHandle]=q;
            return bytePopped;
        }
};

Further optimizations and execution process:

Implemetation details:
I have created an array based queue.Memory management is handled in the code itself and No memory dynamically allocated during program execution.
These queues are implemented as dequeue with head and tail pointers.Whenever a queue is created , a handle is created and this queue is mappedto that handle.

Both adding and removing a byte only causes a pointer shuffle and thus avoids performance impact.

======================== Compilation Steps:
g++ -c *.cpp -std=c++11
g++ *.o -o Queue.out

./Queue.out

Possible improvements:
I feel my solution could be improved given additional time and/or
resources by extending this system to become highly concurrent. This could be done by thread and event driven
programming where multiple queuing request can be processed in parallel.
Threaded solution can be further improved with a policy based design. This policy based design could be used to
create a generic thread pool based on various thresholds and policies.
Also separate thread pools can be maintained for different queues and load balancing can be introduced based on
pending data in queues and available threads in thread pools.
Further , This solution was asked for only Queues that stores byte , these queues can be extended to queues storing multiple data-types using
templates.
Finally , We could also introduce a Producer -Consumer model to Queue If a particular variant is used in designing sockets where producer is sending data and consumer is waiting for data to arrive and can consume it immediately.