FIFO queues in C

[mmiikkee12]

Any idea how to implement a FIFO queue of chars in C? It doesn't need to be too fancy, just a fixed size (say 256 chars) and can't use any library functions (this is for a hobby OS kernel I'm writing, and there's not a lot of functions available for use). I just tried to make one, then I realized... hey wait, this is an implementation of a stack, not a queue :p (I must say, it worked pretty well for a stack... but I don't need a stack here.)

[WaltP]

One array and two indecies. One index points to the empty position for the next character to be added. Other index points at the character to be removed when needed. When either getst to the end of the array, reset to beginning.

You need to decide when the queue (this is the name of this structure) is full and empty.

[iamthwee]

The implementation of queue is much more difficult than a stack, especially in c.

Have you tried googling for

queue.c

. It should return more than enough examples.

[mmiikkee12]

The implementation of queue is much more difficult than a stack, especially in c.

Really? I didn't know :P (jk)

Have you tried googling for
Code:
queue.c
. It should return more than enough examples.

Hmm, googling for a filename. I need to remember that one ;)

[Dani]

http://www.daniweb.com/code/snippet68.html

[mmiikkee12]

cscgal:

#include <stdlib.h>  // malloc()

Um, I don't have a malloc :P Thanks anyway.

OK, I dug up an old thread about doing it with 2 stacks. Here's what I came up with from that:

// *** fifo.c ***
#include <fifo.h>

void fifo_insert(fifo buffer, char data)
{
	// wait until it's not in use (by an isr or somethign)
	while (buffer.locked);
	buffer.locked = true;

	push(buffer.s1, data);

	buffer.locked = false;
}

char fifo_get(fifo buffer)
{
	// wait until it's not in use (by an isr or somethign)
	while (buffer.locked);
	buffer.locked = true;

	// flip the stack over so we can get the first value there
	while (buffer.s2.length != 0)
		push(buffer.s2, pop(buffer.s1));
	// take that value out
	char rv = pop(buffer.s2);
	// and flip it back
	while (buffer.s2.length != 0)
		push(buffer.s1, pop(buffer.s2));

	buffer.locked = false;
	return rv;
}

// *** fifo.h ***

#ifndef __FIFO_H
#define __FIFO_H

#include <stack.h>
#include <types.h>

typedef struct
{
	boolean locked;
	stack s1;
	stack s2;
} fifo;

#endif

// *** stack.c ***
#include <stack.h>

void push(stack buffer, char key)
{
	buffer.data[buffer.length] = key;
	// Avoid stack overflow by just continuing to put values on the top
	if (buffer.length < 256)
		buffer.length++;
}

// This function should have special significance in Popcorn :-P
char pop(stack buffer)
{
	// if there are no values in the stack, wait until there are
	while(buffer.length == 0);

	// now get one out
	char rv = buffer.data[buffer.length];
	buffer.length--;
	return rv;
}

char pop_nowait(stack buffer)
{
	if (buffer.length == 0) return 0;

	// now get one out
	char rv = buffer.data[buffer.length];
	buffer.length--;
	return rv;
}

// *** stack.h ***
#ifndef __STACK_H
#define __STACK_H


typedef struct
{
	int length;
	char data[256];
} stack;

void push(stack buffer, char key);
char pop(stack buffer);
char pop_nowait(stack buffer);

#endif

And then I use it like this:

// *** keyboard.c ***
void keyboard_handler(regs *r)
{
	unsigned char scancode;

	// Read from the keyboard's data buffer
	scancode = inportb(0x60);

	// If the top bit of the byte we read from the keyboard is
	// set, that means that a key has just been released
	if (scancode & 0x80)
	{
		if (scancode - 0x80 == 42 || scancode - 0x80 == 54)
			shift_pressed = true;

		else if (scancode - 0x80 == 29)
			ctrl_pressed = true;

		else if (scancode - 0x80 == 56)
			alt_pressed = true;
	}

	else
	{
		if (scancode == 42 || scancode == 54)
		{
			shift_pressed = false;
		}
		else if (scancode == 29)
		{
			ctrl_pressed = false;
		}
		else if (scancode == 56)
		{
			alt_pressed = false;
		}
		else if (shift_pressed)
		{
			//putch(kbdus_shift[scancode]);
			keypressed(kbdus_shift[scancode]);
		}
		else
		{
			//putch(kbdus[scancode]);
			keypressed(kbdus[scancode]);
		}
	}
}

#ifndef __KEYBOARD_H
#define __KEYBOARD_H

#include <fifo.h>
#include <misc.h>

boolean shift_pressed;
boolean ctrl_pressed;
boolean alt_pressed;

fifo kb_buffer;

void keyboard_handler(regs *r);
void keyboard_init();

// Separate functions for these would be a bit bloatedish.
#define getkey() fifo_get(kb_buffer)
#define keypressed(k) fifo_insert(kb_buffer, k)

#endif

However, there never seems to be anything in the buffer. It's hanging and not running any code after that. Any ideas?

[mmiikkee12]

Hmm, got it now. Dunno what I was thinking using 2 stacks like that :P

[kiranxxx]

please tell me weather the following algorithm for deletion of an element in a queue from front is right or wrong:
del(int queue[max],item)
1.repeat step 2 to 4 until front==rear
2.item=queue[front];
3.front=front+1
4.print deleted element is item
5.set front=-1,rear=-1
6.print undeflow