priority_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 <string.h>
#include <stdio.h>

#include "priority_queue.h"
#include "system_messages.h"

#pragma warning disable = 47

// this (minimum) priority queue module keeps elements sorted based on their key which 
// is 16 bits long. the key's accompanying data is also 16 bits long.
// the key is stored at ( (element value) & 0xFFFF). The accompanying data is 
// stored at ( (element value) & 0xFFFF0000)

// fix the heap from top to bottom
static void heapify(priority_queue_info *a_queue)
{
	int32u *lp_queue_element = a_queue->values ;
	int8u l_non_leafs = (a_queue->size>>1) ; // half of a heap elements are leaves
	int8u l_children_base_index = 1 ;
	int32u l_swap ;

	while (l_non_leafs-- > 0)
	{
        if ( ( (*lp_queue_element) & 0xFFFF) > (*(a_queue->values + l_children_base_index) & 0xFFFF) )
        {
            l_swap = *lp_queue_element ;
            *lp_queue_element = *(a_queue->values + l_children_base_index) ;
            *(a_queue->values + l_children_base_index) = l_swap ;
        }
        
		if ( ( (*lp_queue_element) & 0xFFFF) > (*(a_queue->values + l_children_base_index + 1) & 0xFFFF) )
        {
            l_swap = *lp_queue_element ;
            *lp_queue_element = *(a_queue->values + l_children_base_index + 1) ;
            *(a_queue->values + l_children_base_index + 1) = l_swap ;
        }

		l_children_base_index = l_children_base_index << 1 ;

        ++lp_queue_element ;
	}
}

int16s	priority_queue_init(priority_queue_info *a_queue)
{
	a_queue->size = 0 ;
	memset(a_queue->values, '\0', MAX_QUEUE_ELEMENTS) ;
	
	return NO_ERROR ;
}

// Note: the 16 LSB bits of 'a_key' are the key, the 16 upper bits represent the data to be stored
int16s priority_queue_insert(priority_queue_info *a_queue, int16u a_key, int16u a_data)
{
	int8u l_parent, l_index ;

	if (a_queue->size > MAX_QUEUE_ELEMENTS)
	{
		return ERR_QUEUE_FULL ;
	}

	l_index = (a_queue->size++) ;
	l_parent = l_index>>1 ;

	while ( (l_index > 0) && ( *(a_queue->values + l_parent) & 0xFFFF) > a_key)
	{
		*(a_queue->values + l_index) = *(a_queue->values + l_parent) ;
		
		l_index = l_parent ;
		l_parent = l_index>>1 ;
	}
	
	// store key and data in queue. each occupy 16 bits.
	*(a_queue->values + l_index) = ((int32u)(a_data) << 16) + a_key ;

	return NO_ERROR ;
}

int16s priority_queue_empty(priority_queue_info *a_queue)
{
	a_queue->size = 0 ;

	return NO_ERROR ;
}

int8u priority_queue_is_empty(const priority_queue_info *a_queue)
{
	return (a_queue->size == 0) ;
}

int16s priority_queue_num_elements(const priority_queue_info *a_queue)
{
	return a_queue->size ;
}

// note: this function returns the data stored at the root of the priority queue
int16u priority_queue_minimum_data(const priority_queue_info *a_queue)
{
	return (a_queue->values[0] & 0xFFFF0000)>>16 ;
}

// note: this function returns the data stored at the root of the priority queue
int16u priority_queue_minimum_key(const priority_queue_info *a_queue)
{
	return (a_queue->values[0] & 0xFFFF) ;
}

int16s priority_queue_update_key(priority_queue_info *a_queue, int16u a_key, int16u a_data)
{
	int16s 	l_index ;
	int16u 	l_data ;
	int32u  *lp_value ;

	l_index = a_queue->size - 1 ;

	while (l_index >= 0)
	{
		lp_value = a_queue->values + l_index ;
		l_data = (int16u) ( ((*lp_value) & 0xFFFF0000)>>16) ;
		if (l_data == a_data)
		{
			(*lp_value) &= 0xFFFF0000 ;
			(*lp_value) |= a_key ;
			
			heapify(a_queue) ;
			
			return NO_ERROR ;
		}
		--l_index ;
	}

	return ERR_ITEM_NOT_FOUND ;
}

int16s priority_queue_minimum_data_extract(priority_queue_info *a_queue)
{
	int16s l_minimum ;

	if (a_queue->size == 0)
	{
		return ERR_QUEUE_EMPTY ;
	}

	l_minimum = (int16s)( (a_queue->values[0] & 0xFFFF0000) >> 16) ; // cast to silence the compiler; to accuracy loss here.
	--a_queue->size ;
    a_queue->values[0] = a_queue->values[a_queue->size] ;
	heapify(a_queue) ;

	return l_minimum ;
}

void priority_queue_print(const priority_queue_info *a_queue)
{
	int8u l_index = 0, l_size = a_queue->size ;

	while (l_index < l_size)
	{
		printf("key=%d,data=%d\n", *(a_queue->values + l_index) & 0xFFFF, (*(a_queue->values + l_index) & 0xFFFF0000) >> 16 ) ;

		++l_index ;
	}

	printf("\n") ;
}