queue.c

嵌入式操作系统EOS（Embedded OperatingSystem）是一种用途广泛的系统软件

/*
** Copyright (C) 2006 Tamir Michael
**  
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
** 
** This program 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 General Public License for more details.
** 
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software 
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/

#include "queue.h"
#include "system_messages.h"
#include "rtos_services.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int16s	queue_init(queue_info *a_queue)
{
	a_queue->head = a_queue->tail = a_queue->size = 0 ;
	memset(a_queue->values, '\0', MAX_QUEUE_ELEMENTS) ;

	return NO_ERROR ;
}

int16s	queue_enqueue(queue_info *a_queue, int32s a_element)
{
	int8u l_head = a_queue->head ; // for speed

	if ( (l_head == a_queue->tail) && (a_queue->size > 0) )
	{
		return ERR_QUEUE_FULL ;
	}

	a_queue->values[l_head] = a_element ;
	a_queue->head = ( (++l_head) > (MAX_QUEUE_ELEMENTS - 1) ? 0 : l_head) ;
	a_queue->size++ ;

	return NO_ERROR ;
}

int32s	queue_dequeue(queue_info *a_queue)
{
	int32s l_element ;
	int8u l_tail = a_queue->tail ; // for speed

	if (a_queue->size > 0)
	{
		l_element = a_queue->values[l_tail] ;
		a_queue->tail = ( (++l_tail) > (MAX_QUEUE_ELEMENTS - 1) ? 0 : l_tail) ;
		a_queue->size-- ;
	}
	else
	{
		return ERR_QUEUE_EMPTY ;
	}

	return l_element ;
}

int16s	queue_empty(queue_info *a_queue)
{
	a_queue->head = a_queue->tail ;
	a_queue->size = 0 ;

	return NO_ERROR ;
}

int8u queue_is_empty(const queue_info *a_queue)
{
	return (a_queue->size == 0) ;
}

int16s   queue_num_elements(const queue_info *a_queue)
{
	return a_queue->size ;
}

// returns the location in the queue 'q' (relative to the tail) if 'e' is in it. otherwise, returns -1.
int16s	queue_search(const queue_info *a_queue, int32s a_element)
{
	int8u l_tail = a_queue->tail ;
	int8u l_head = a_queue->head ;

	while (1)
	{
		if (l_tail == l_head)
		{
			break ;
		}

		if (a_queue->values[l_tail] == a_element)
		{
			return l_tail ;
		}

		l_tail = ( (++l_tail) > (MAX_QUEUE_ELEMENTS - 1) ? 0 : l_tail) ;
	}
	
	return ERR_ITEM_NOT_FOUND ;
}

// moves (unique)item from queue 's' to queue 't'
int16s	queue_move(queue_info *a_source_queue, queue_info *a_target_queue, int32s a_element)
{
	int16s l_tail1, l_tail2 ;
	int16s l_index = queue_search(a_source_queue, a_element) ;

	if (l_index == ERR_ITEM_NOT_FOUND)
	{
		return ERR_ITEM_NOT_FOUND ;
	}

	// to do: improve effecienby by allowing shifting to the right if index<(s->size/2)
	l_tail1 = l_index ;
	l_tail2 = ( (l_index + 1) > (MAX_QUEUE_ELEMENTS - 1) ? 0 : (l_index + 1) ) ;

	while (l_tail2 != a_source_queue->head)
	{
		a_source_queue->values[l_tail1] = a_source_queue->values[l_tail2] ;
		l_tail1 = ( (++l_tail1) > (MAX_QUEUE_ELEMENTS - 1) ? 0 : l_tail1) ;
		l_tail2 = ( (++l_tail2) > (MAX_QUEUE_ELEMENTS - 1) ? 0 : l_tail2) ;
	}

	if (a_source_queue->head == 0)
	{
		a_source_queue->head = MAX_QUEUE_ELEMENTS - 1;
	}
	else
	{
		a_source_queue->head-- ;
	}

	a_source_queue->size-- ;
	queue_enqueue(a_target_queue, a_element) ;

	return NO_ERROR ;
}

void queue_print(const queue_info *a_queue)
{
	int8u l_tail = a_queue->tail ;
	int8u l_head = a_queue->head ;

	printf("\nqueue: ") ;
	
	while (1 )
	{
		if (l_tail == l_head )
		{
			break ;
		}

		printf("%d ", a_queue->values[l_tail]) ;
		l_tail = ( (++l_tail) > (MAX_QUEUE_ELEMENTS - 1) ? 0 : l_tail) ;
	}
}