Danilo Bustamante / queue

a simple c queue

queue.c@0:8b473c4a0afc, 2015-02-14 (annotated)

Committer:
danilob
Date:
Sat Feb 14 23:25:22 2015 +0000
Revision:
0:8b473c4a0afc
it has been improved

Who changed what in which revision?

UserRevisionLine numberNew contents of line
danilob 0:8b473c4a0afc 1 /*
danilob 0:8b473c4a0afc 2 * queue.c
danilob 0:8b473c4a0afc 3 *
danilob 0:8b473c4a0afc 4 * Created on: Jan 15, 2015
danilob 0:8b473c4a0afc 5 * Author: danilob
danilob 0:8b473c4a0afc 6 */
danilob 0:8b473c4a0afc 7
danilob 0:8b473c4a0afc 8
danilob 0:8b473c4a0afc 9 #include <stdio.h>
danilob 0:8b473c4a0afc 10 #include <stdlib.h>
danilob 0:8b473c4a0afc 11 #include "queue.h"
danilob 0:8b473c4a0afc 12
danilob 0:8b473c4a0afc 13 //auxiliar function to handle the reset of Index in neede for the queue
danilob 0:8b473c4a0afc 14 queue_index_t incrementIndex(queue_index_t index, queue_size_t size) //functionw ill increment queue index
danilob 0:8b473c4a0afc 15 {
danilob 0:8b473c4a0afc 16 if(index == size-1)
danilob 0:8b473c4a0afc 17 index = 0;
danilob 0:8b473c4a0afc 18 else
danilob 0:8b473c4a0afc 19 index++;
danilob 0:8b473c4a0afc 20 return index;
danilob 0:8b473c4a0afc 21 }
danilob 0:8b473c4a0afc 22
danilob 0:8b473c4a0afc 23 // Standard queue implementation that leaves one spot empty so easier to check for full/empty.
danilob 0:8b473c4a0afc 24 void queue_init(queue_t* q, queue_size_t size) {
danilob 0:8b473c4a0afc 25 q->indexIn = 0;
danilob 0:8b473c4a0afc 26 q->indexOut = 0;
danilob 0:8b473c4a0afc 27 q->elementCount = 0;
danilob 0:8b473c4a0afc 28 q->size = size+1; // Add one additional location for the empty location.
danilob 0:8b473c4a0afc 29 q->data = (queue_data_t *) malloc(q->size * sizeof(queue_data_t));
danilob 0:8b473c4a0afc 30 }
danilob 0:8b473c4a0afc 31
danilob 0:8b473c4a0afc 32 queue_size_t queue_size(queue_t* q);
danilob 0:8b473c4a0afc 33
danilob 0:8b473c4a0afc 34 // Returns true if the queue is full.
danilob 0:8b473c4a0afc 35 bool queueFull(queue_t* q)
danilob 0:8b473c4a0afc 36 {
danilob 0:8b473c4a0afc 37 if(q->elementCount == q->size-1)
danilob 0:8b473c4a0afc 38 return 1;
danilob 0:8b473c4a0afc 39 return 0;
danilob 0:8b473c4a0afc 40 }
danilob 0:8b473c4a0afc 41
danilob 0:8b473c4a0afc 42 // Returns true if the queue is empty.
danilob 0:8b473c4a0afc 43 bool queue_empty(queue_t* q)
danilob 0:8b473c4a0afc 44 {
danilob 0:8b473c4a0afc 45 if(q->elementCount == (queue_size_t)0)
danilob 0:8b473c4a0afc 46 return 1;
danilob 0:8b473c4a0afc 47 return 0;
danilob 0:8b473c4a0afc 48 }
danilob 0:8b473c4a0afc 49
danilob 0:8b473c4a0afc 50 // Pushes a new element into the queue. Reports an error if the queue is full.
danilob 0:8b473c4a0afc 51 void queue_push(queue_t* q, queue_data_t value)
danilob 0:8b473c4a0afc 52 {
danilob 0:8b473c4a0afc 53 if(queueFull(q))
danilob 0:8b473c4a0afc 54 printf("Cannot insert, full queue!\n\r"); // This prints on the console.
danilob 0:8b473c4a0afc 55 else
danilob 0:8b473c4a0afc 56 {
danilob 0:8b473c4a0afc 57 q->data[q->indexIn] = value;
danilob 0:8b473c4a0afc 58 q->elementCount++;
danilob 0:8b473c4a0afc 59 q->indexIn = incrementIndex(q->indexIn, q->size);
danilob 0:8b473c4a0afc 60 }
danilob 0:8b473c4a0afc 61
danilob 0:8b473c4a0afc 62 }
danilob 0:8b473c4a0afc 63
danilob 0:8b473c4a0afc 64 // Removes the oldest element in the queue.
danilob 0:8b473c4a0afc 65 queue_data_t queue_pop(queue_t* q)
danilob 0:8b473c4a0afc 66 {
danilob 0:8b473c4a0afc 67 queue_data_t rdata;
danilob 0:8b473c4a0afc 68 if(queue_empty(q))
danilob 0:8b473c4a0afc 69 printf("Queue is empty\n\r"); // This prints on the console.
danilob 0:8b473c4a0afc 70 else
danilob 0:8b473c4a0afc 71 {
danilob 0:8b473c4a0afc 72 rdata = q->data[q->indexOut];
danilob 0:8b473c4a0afc 73 q->elementCount--;
danilob 0:8b473c4a0afc 74 q->indexOut = incrementIndex(q->indexOut, q->size);
danilob 0:8b473c4a0afc 75 return rdata;
danilob 0:8b473c4a0afc 76 }
danilob 0:8b473c4a0afc 77 return 0;
danilob 0:8b473c4a0afc 78 }
danilob 0:8b473c4a0afc 79
danilob 0:8b473c4a0afc 80 // Pushes a new element into the queue, making room by removing the oldest element.
danilob 0:8b473c4a0afc 81 void queue_overwritePush(queue_t* q, queue_data_t value)
danilob 0:8b473c4a0afc 82 {
danilob 0:8b473c4a0afc 83 if(queueFull(q))
danilob 0:8b473c4a0afc 84 {
danilob 0:8b473c4a0afc 85 printf("warning Queue is being overwritten\n\r"); // This prints on the console.
danilob 0:8b473c4a0afc 86 q->data[q->indexIn] = value;
danilob 0:8b473c4a0afc 87 q->indexIn = incrementIndex(q->indexIn, q->size);
danilob 0:8b473c4a0afc 88 q->indexOut = incrementIndex(q->indexOut, q->size);
danilob 0:8b473c4a0afc 89 }
danilob 0:8b473c4a0afc 90 else
danilob 0:8b473c4a0afc 91 queue_push(q,value);
danilob 0:8b473c4a0afc 92 }
danilob 0:8b473c4a0afc 93
danilob 0:8b473c4a0afc 94 // Provides random-access read capability to the queue.
danilob 0:8b473c4a0afc 95 // Low-valued indexes access older queue elements while higher-value indexes access newer elements
danilob 0:8b473c4a0afc 96 // (according to the order that they were added).
danilob 0:8b473c4a0afc 97 queue_data_t queue_readElementAt(queue_t* q, queue_index_t index)
danilob 0:8b473c4a0afc 98 {
danilob 0:8b473c4a0afc 99 if(queue_empty(q))
danilob 0:8b473c4a0afc 100 printf("Queue is empty\n\r"); // This prints on the console.
danilob 0:8b473c4a0afc 101 else
danilob 0:8b473c4a0afc 102 {
danilob 0:8b473c4a0afc 103 if(index < q->elementCount)
danilob 0:8b473c4a0afc 104 {
danilob 0:8b473c4a0afc 105 if((index + q->indexOut) < q->size-1)
danilob 0:8b473c4a0afc 106 return q->data[index+ q->indexOut];
danilob 0:8b473c4a0afc 107 else
danilob 0:8b473c4a0afc 108 return q->data[q->size - (index+ q->indexOut) -1];
danilob 0:8b473c4a0afc 109 }
danilob 0:8b473c4a0afc 110 else
danilob 0:8b473c4a0afc 111 printf("index out of bounds\n\r");
danilob 0:8b473c4a0afc 112 }
danilob 0:8b473c4a0afc 113 return 0;
danilob 0:8b473c4a0afc 114 }
danilob 0:8b473c4a0afc 115
danilob 0:8b473c4a0afc 116 // Returns a count of the elements currently contained in the queue.
danilob 0:8b473c4a0afc 117 queue_size_t queue_elementCount(queue_t* q)
danilob 0:8b473c4a0afc 118 {
danilob 0:8b473c4a0afc 119 return q->elementCount;
danilob 0:8b473c4a0afc 120 }
danilob 0:8b473c4a0afc 121
danilob 0:8b473c4a0afc 122 // Prints the current contents of the queue. Handy for debugging.
danilob 0:8b473c4a0afc 123 void queue_print(queue_t* q)
danilob 0:8b473c4a0afc 124 {
danilob 0:8b473c4a0afc 125 queue_index_t indexOutTmp;
danilob 0:8b473c4a0afc 126 if(queue_empty(q))
danilob 0:8b473c4a0afc 127 printf("Queue is empty.\n\r");
danilob 0:8b473c4a0afc 128 else
danilob 0:8b473c4a0afc 129 {
danilob 0:8b473c4a0afc 130 for (indexOutTmp = q->indexOut; indexOutTmp != q->indexIn; indexOutTmp = incrementIndex(indexOutTmp, q->size))
danilob 0:8b473c4a0afc 131 printf("%lf\n\r", q->data[indexOutTmp]);
danilob 0:8b473c4a0afc 132 }
danilob 0:8b473c4a0afc 133 }
danilob 0:8b473c4a0afc 134
danilob 0:8b473c4a0afc 135 // Performs a comprehensive test of all queue functions.
danilob 0:8b473c4a0afc 136 int queue_runTest()
danilob 0:8b473c4a0afc 137 {
danilob 0:8b473c4a0afc 138 queue_t q;
danilob 0:8b473c4a0afc 139 queue_init(&q, 3);
danilob 0:8b473c4a0afc 140 queue_pop(&q);
danilob 0:8b473c4a0afc 141
danilob 0:8b473c4a0afc 142 queue_push(&q, 1);
danilob 0:8b473c4a0afc 143 printf("Element count : %lf \n\r",queue_elementCount(&q));
danilob 0:8b473c4a0afc 144 queue_push(&q, 2);
danilob 0:8b473c4a0afc 145 printf("Element count : %lf\n\r",queue_elementCount(&q));
danilob 0:8b473c4a0afc 146 queue_push(&q, 3);
danilob 0:8b473c4a0afc 147 printf("Element count : %lf\n\r",queue_elementCount(&q));
danilob 0:8b473c4a0afc 148 queue_push(&q, 6);
danilob 0:8b473c4a0afc 149
danilob 0:8b473c4a0afc 150 printf("printing contents of queue.\n\r");
danilob 0:8b473c4a0afc 151 queue_print(&q);
danilob 0:8b473c4a0afc 152 printf("done printing contents of queue.\n\r");
danilob 0:8b473c4a0afc 153
danilob 0:8b473c4a0afc 154 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 155 queue_push(&q, 4);
danilob 0:8b473c4a0afc 156 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 157 queue_push(&q, 5);
danilob 0:8b473c4a0afc 158 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 159
danilob 0:8b473c4a0afc 160 printf("printing contents of queue.\n\r");
danilob 0:8b473c4a0afc 161 queue_print(&q);
danilob 0:8b473c4a0afc 162 printf("done printing contents of queue.\n\r");
danilob 0:8b473c4a0afc 163
danilob 0:8b473c4a0afc 164 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 165 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 166 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 167
danilob 0:8b473c4a0afc 168 queue_overwritePush(&q,7);
danilob 0:8b473c4a0afc 169 queue_overwritePush(&q,8);
danilob 0:8b473c4a0afc 170 queue_overwritePush(&q,9);
danilob 0:8b473c4a0afc 171 queue_overwritePush(&q,10);
danilob 0:8b473c4a0afc 172 queue_overwritePush(&q,11);
danilob 0:8b473c4a0afc 173
danilob 0:8b473c4a0afc 174 printf("printing contents of queue.\n\r");
danilob 0:8b473c4a0afc 175 queue_print(&q);
danilob 0:8b473c4a0afc 176 printf("done printing contents of queue.\n\r");
danilob 0:8b473c4a0afc 177
danilob 0:8b473c4a0afc 178 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 179 printf("%lf\n\r",queue_readElementAt(&q, 3));
danilob 0:8b473c4a0afc 180 printf("%lf\n\r",queue_readElementAt(&q, 2));
danilob 0:8b473c4a0afc 181 printf("%lf\n\r",queue_readElementAt(&q, 1));
danilob 0:8b473c4a0afc 182 printf("%lf\n\r",queue_readElementAt(&q, 0));
danilob 0:8b473c4a0afc 183
danilob 0:8b473c4a0afc 184 printf("%lf\n\r", queue_pop(&q));
danilob 0:8b473c4a0afc 185
danilob 0:8b473c4a0afc 186 printf("%lf\n\r",queue_readElementAt(&q, 3));
danilob 0:8b473c4a0afc 187 printf("%lf\n\r",queue_readElementAt(&q, 2));
danilob 0:8b473c4a0afc 188 printf("%lf\n\r",queue_readElementAt(&q, 1));
danilob 0:8b473c4a0afc 189 printf("%lf\n\r",queue_readElementAt(&q, 0));
danilob 0:8b473c4a0afc 190
danilob 0:8b473c4a0afc 191 printf("done testing queue working!.\n\r");
danilob 0:8b473c4a0afc 192 return 1;
danilob 0:8b473c4a0afc 193 }
danilob 0:8b473c4a0afc 194 // Just free the malloc'd storage.
danilob 0:8b473c4a0afc 195 void gueue_garbageCollect(queue_t* q)
danilob 0:8b473c4a0afc 196 {
danilob 0:8b473c4a0afc 197 free(q->data);
danilob 0:8b473c4a0afc 198 }