Array of Chars as Queue in C

Question

I'm coding a piece of code for AVR. I want to build a queue that can push and pop, and this queue is an array of chars (string). So when I push 'a':
['b', 'c', 'd', 'e', 'f']
becomes:
['a','b', 'c', 'd', 'e', 'f']
and when I pop, f comes out. I've written this code, but it only pushes 1 char to the queue, as if it removes the whole queue. Here's my code for the queue:

char queue[50] = "";
char* queue_tail = &queue[0];
char* queue_head = &queue[0];

void queue_push(char l_item)
{
    if(queue_head != &queue[strlen(queue) - 1]) //if queue is not full, do the job
    {
        //Push all elements one step further
        char* traveler = queue_head;
        for(; traveler != queue_tail; --traveler)
        {
            *(traveler+1) = *traveler;
            *traveler = '';
        }
        ++queue_head;
        *queue_tail = l_item;
    }
}

char queue_pop()
{
    char temp = *queue_head;
    *queue_head = '';
    --queue_head;
    return temp;
}

This is my main function:

#include <mega32.h>
#include <alcd.h>
#include <delay.h>
#include <string.h>

void main(void)
{

const char text[] = "Hello world!";
int col_counter = 0;
char* p_head = '';

lcd_init(32);
p_head = &text[12];

while(1)
{
    lcd_clear();

    if(col_counter + strlen(text) > 32)
    {
        queue_push(*p_head);
        --p_head;
    }

    lcd_gotoxy(col_counter, 0);
    lcd_puts(text);
    lcd_gotoxy(0,0);
    lcd_puts(queue);
    delay_ms(200);
    ++col_counter;

}
}

Any help would be appreciated. Thanks in advance.

strlen(queue) may be 0, then queue[strlen(queue) - 1] is out-of-range. — MikeCAT
– MikeCAT, Commented Mar 5, 2016 at 8:46
I changed queue[strlen(queue) - 1] to queue[49], still the same issue. — Reza Hajianpour
– Reza Hajianpour, Commented Mar 5, 2016 at 9:05
For efficiency, you may consider a circular buffer which avoids copying the queue's data again and again. — JimmyB
– JimmyB, Commented Mar 7, 2016 at 12:32

MikeCAT · Accepted Answer · 2016-03-05 09:26:31Z

I changed the meaning of queue_head from the last element to one past the last element in the queue, and adjusted the code.

Here is a corrected code (main() in this code is a test code for usual PC):

#include <stdio.h>

char queue[50] = "";
char* queue_tail = &queue[0];
char* queue_head = &queue[0];

void queue_push(char l_item)
{
    if(queue_head != queue + sizeof(queue)/sizeof(*queue)) //if queue is not full, do the job
    {
        //Push all elements one step further
        char* traveler = queue_head;
        for(; traveler != queue_tail; --traveler)
        {
            *traveler = *(traveler - 1);
        }
        ++queue_head;
        *queue_tail = l_item;
    }
}

char queue_pop(void)
{
    char temp;
    if (queue_head == queue_tail) return '\0'; // the queue is empty
    --queue_head;
    temp = *queue_head;
    *queue_head = '\0';
    return temp;
}

int main(void) {
    queue_push(100);
    queue_push(110);
    printf("%d\n",queue_pop());
    printf("%d\n",queue_pop());
    return 0;
}

JimmyB · Accepted Answer · 2016-03-07 14:51:39Z

Proposal for a circular buffer implementation (obviating the need to copy the buffer's content to and fro):

char queue[50] = "";
char* queue_tail = &queue[0];
char* queue_head = &queue[0];

#define END_OF_QUEUE (&queue[sizeof(queue)/sizeof(*queue)]) // The first element _after_ the buffer.

#define QUEUE_NOT_FULL   0
#define QUEUE_IS_FULL    1

uint8_t queueState;

void queue_push(const char l_item)
{
    // 0) Addition is always modulus buffer size (50)
    // 1) head points to the next empty location which can store an incoming byte
    // 2) tail points to the next location from where a byte may be read
    // 3) Queue is empty iff tail == head && queueState == QUEUE_NOT_FULL
    // 4) Queue is full iff tail == head && queueState == QUEUE_IS_FULL

    if ( queueState == QUEUE_NOT_FULL ) {

        // Store item to the current head:
        *queue_head = l_item;

        // Advance head by one:
        queue_head++;

        if ( queue_head == END_OF_QUEUE ) {
            // head passed the end of buffer -> continue at the start:
            queue_head = &queue[0];
        }

        // If head meets tail after appending the new element, the buffer is now full.
        if ( queue_head == queue_tail ) {
            queueState = QUEUE_IS_FULL;
        }

    } else {
        // Buffer overflow! - Options: Ignore new data, overwrite old data, wait until not full, signal an error somehow.
    }

}

char queue_pop()
{

    if ( (queue_tail == queue_head) && (queueState == QUEUE_NOT_FULL) ) {
        // Queue is empty. "Buffer underflow." - Options: Return dummy value, wait until data available, signal an error somehow.
        return '\0';
    } else {
        const char result = *queue_tail;
        queue_tail++;

        if ( queue_tail == END_OF_QUEUE ) {
            // tail passed the end of buffer -> continue at the start:
            queue_tail = &queue[0];        
        }

        // We just removed an element from the queue, so the queue cannot be full now even if it was full a moment ago.
        queueState = QUEUE_NOT_FULL;

        return result;
    }

}

(Note that, without further synchronization elements, this code will not work correctly when running concurrently, i.e. when accessing the buffer (read or write) from within an ISR.)

Collectives™ on Stack Overflow

Array of Chars as Queue in C

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related