/* queue.d - implementation of the game studio challenge * Copyright (C) 2012 Paulo Pinto * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307, USA. */ import std.stdio; import std.c.stdlib; import std.c.string; /// Maximum available storage size const int MAX_STORAGE = 2048; /// Bits to shift around const int BIT_SHIFT = 12; /// The set of bits that contain the value of the next pointer const int LOWER_BITS = 0x0FFF; /// storage area byte data[MAX_STORAGE]; /// The queue data type alias void Q; /** * Helper function. Dumps the queue contents in a sequence * of (value, next) elements. * * Params: * q = The queue to dump. Cannot be null. */ void dumpQueue (Q *q) in { assert(q != null); } body { writef ("Printing Queue Debugging Info\n"); int *queue = cast(int*)(q); if (*queue == 0) { writef ("Empty queue!\n"); } int next = *queue & LOWER_BITS; writef ("(%d, %d) ", *queue >> BIT_SHIFT, next); while (next != 0 && next != LOWER_BITS) { queue = cast(int*)(data.ptr + next); next = *queue & LOWER_BITS; writef ("(%d, %d) ", *queue >> BIT_SHIFT, next); } writeln; } void main() { initializeStorage(); Q * q0 = createQueue(); enqueueByte(q0, 0); enqueueByte(q0, 1); Q * q1 = createQueue(); enqueueByte(q1, 3); enqueueByte(q0, 2); enqueueByte(q1, 4); writef("%d ", dequeueByte(q0)); writef("%d\n", dequeueByte(q0)); enqueueByte(q0, 5); enqueueByte(q1, 6); writef("%d ", dequeueByte(q0)); writef("%d\n", dequeueByte(q0)); destroyQueue(q0); writef("%d ", dequeueByte(q1)); writef("%d ", dequeueByte(q1)); writefln("%d", dequeueByte(q1)); destroyQueue(q1); } /** * Called by the queue routines when the storage is * exhausted. It exits to the operating system. * * On a real system, this would be an callback given into this * module. */ void onOutOfMemory() { writef("Not enough memory available. Exiting application\n"); exit(-1); } /** * Called by the queue routines when the an invalid * operation is attempted. It exits to the operating system. * * On a real system, this would be an callback given into this * module. */ void onIllegalOperation() { writef("An invalid queue operation has been requested. Exiting application\n"); exit(-2); } /** * Makes sure all required data structures have * a proper value. */ void initializeStorage() { memset(data.ptr, 0, MAX_STORAGE); int* free_list = cast(int*)(data); *free_list = int.sizeof; // Make the free list point for the first free element } /** * Allocates a fixed block of memory for the queue. * If no memory is available, the function onOutOfMemory is called(). * * Returns: * A new initialized memory block. */ void* allocateStorage() out(result) { assert(result != null); } body { int* free_list = cast(int*)(data); if (*free_list == 0) { onOutOfMemory(); // cannot fullfil request } int *cell = cast(int*)(data.ptr + *free_list); if (*cell == 0) { *free_list += int.sizeof; } else { *free_list = *cell; *cell = 0; } return cell; } /** * Returns the memory block back to the free list. * * Params: * mem = Memory block to return. Cannot be null. */ void releaseStorage(void* mem) in { assert (mem != null); } body { int* free_list = cast(int*)(data); int* cell = cast(int*)(mem); *cell = *free_list; *free_list = cast(int)(cast(byte*)(mem) - data.ptr); } /** * Initializes a new queue * * Return: * A new object representing a queue. */ Q* createQueue() out(result) { assert (result != null); } body { int *queue = cast(int*)(allocateStorage()); *queue = 0; return queue; } /** * Destroys the queue by making its space available * for further operations. * * Params: * q = The queue to dump. Cannot be null. */ void destroyQueue(Q * q) in { assert(q != null); } body { int *queue = cast(int*)(q); int next = *queue & LOWER_BITS; while (next != 0) { byte *mem = data.ptr + next; next = *(cast(int*)(mem)) & LOWER_BITS; releaseStorage(mem); } releaseStorage(q); } /** * Places a byte into the queue. * If the storage is exhausted the function * onOutOfMemory() will be called. * * Params: * q = The queue to dump. Cannot be null. * b = byte to enqueue. */ void enqueueByte(Q * q, byte b) in { assert(q != null); } body { int *queue = cast(int*)(q); if (*queue == 0) { *queue = b << BIT_SHIFT | LOWER_BITS; } else { int next = *queue & LOWER_BITS; int previous = 0; if (next == LOWER_BITS) { previous = 0; } else { while (next != 0) { byte *mem = data.ptr + next; previous = next; next = *(cast(int*)(mem)) & LOWER_BITS; } } int *cell = cast(int*)(allocateStorage()); *cell = b << BIT_SHIFT; int *last_cell; if (previous == 0) { last_cell = queue; } else { last_cell = cast(int*)(data.ptr + previous); } *last_cell = cast(int)((*last_cell & 0xF000) | (cast(byte*)(cell) - data.ptr)); } } /** * Removes a byte from the queue. * If the queue is empty the function * onIllegalOperation() will be called. * * Params: * q = The queue to dump. Cannot be null. * * Return: * The byte at the top of the queue. */ byte dequeueByte(Q * q) in { assert(q != null); } body { int *queue = cast(int*)(q); if (*queue == 0) { onIllegalOperation(); } byte value = cast(byte)(*queue >> BIT_SHIFT); int next = *queue & LOWER_BITS; if (next != 0 && next != LOWER_BITS) { int *cell = cast(int*)(data.ptr + next); *queue = *cell; releaseStorage(cell); } else { *queue = 0; } return value; }