[Rtk-cvs] rtk/src/core PriorityQueue.cpp,NONE,1.1

[Dejan L. <dlo...@us...>]

Update of /cvsroot/rtk/rtk/src/core
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv25466/src/core

Added Files:
	PriorityQueue.cpp 
Log Message:


--- NEW FILE: PriorityQueue.cpp ---
/**
  *
  * RTK
  * Fast and easy cross-platform GUI ToolKit.
  *
  * Copyright (C) 2001-200x RTK Development Team
  *
  * This library is free software; you can redistribute it and/or modify it
  * under the terms of the slightly modified (see the "EXCEPTION NOTICE" part
  * of RTK Library License) GNU Lesser General Public License as published
  * by the Free Software Foundation; either version 2.1 of the License, or
  * (at your option) any later version.
  *
  * This library 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 Lesser General Public
  * License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public License
  * and along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA .
  *
  * Also you should have received a copy of RTK Library License, if not please
  * write an e-mail to some of RTK authors (listed in file AUTHORS).
  *
  * Bug reports: bu...@rt...
  * Suggestions: rf...@rt...
  ***************************************************************************/

/**
  * PriorityQueue.cpp
  * $description
  * Authors (chronological order):
  *   Dejan Lozanovic, null§rtk.cx
  * Contributors (chronological order):
  *   $fname $lname, $email
  ***************************************************************************/

// includes for this file...

// We don't want precompiled headers in Borland C++ Builder...
#if defined(__BORLANDC__)
#  pragma hdrstop
#endif

#include <rtk/PriorityQueue.h>
#include <stdlib.h>

// package also
#if defined(__BORLANDC__)
#  pragma package(smart_init)
#endif

namespace Rtk {

#define CALL_FREE_DATA(d) if(_free_func) (*_free_func)((d))

bool PriorityQueue::Enqueue(void *data, unsigned char priority )
{
        if(_mutex) _mutex->Lock();
	// Allocate space for new element
	QueueNode* new_element = (QueueNode*)malloc(sizeof(QueueNode));

	PriorityNode* priority_element=_priority_head;
	PriorityNode* old_element=_priority_head;

	if (new_element == (QueueNode*)0) // NULL
	  return false;

	new_element->data = (void *)data;

	if ( _priority_head == (PriorityNode*)0) // Queue is empty
	{
	  _priority_head = (PriorityNode*)malloc(sizeof(PriorityNode));
	  if ( _priority_head == (PriorityNode*)0)// malloc error
	    return false;
	  new_element->next=(QueueNode*)0;
	  _priority_head->element=_head=new_element;
	  _count++;
	  return true;
	}

	// move throught priority list until we find right place to
	// insert element or until we reach the end of priority list(
	// if new element has the lowest priority)
       
	while (((priority_element->priority < priority ) ^ _sort) && 
		 priority_element->next !=(PriorityNode*)0 )
	{
	  // here is the speedup since between
	  // priority_element->element and
	  // priority_element->next->element can be many elements
	  old_element=priority_element;
	  priority_element=priority_element->next;
	}

	if (priority_element->priority == priority) 
	{
	  //inserting new_element into a list
	  new_element->next=priority_element->element->next;
	  priority_element->element->next=new_element;
	  priority_element->element=new_element;
	}  
	else
	{
	  //we need new priority node
	  priority_element=(PriorityNode*)malloc(sizeof(PriorityNode));
	  if ( priority_element == (PriorityNode*)0)// malloc error
	    return false;
	  priority_element->priority=priority;      //seting priority
	  priority_element->element=new_element;    //seting QueueNode

	  //insert node into priority list
	  priority_element->next=old_element->next;
	  old_element->next=priority_element;
	  
	  //insert node into element list
	  new_element->next=old_element->element->next;
	  old_element->element->next=new_element;
	  
	}
	_count++;
	if(_mutex) _mutex->Unlock();
	return true;
} // Push(void *data, int priority)

//---------------------------------------------------------------------------

PriorityQueue::~PriorityQueue()
{
	Clear();
} // ~List()

//---------------------------------------------------------------------------

void PriorityQueue::Clear()
{
	// Remove each element.
	QueueNode* element_node;
	PriorityNode* priority_node;

	if(_mutex) _mutex->Lock();

	element_node = _head;
	while (element_node) 
	{
	  QueueNode* element_next = element_node->next;
	  CALL_FREE_DATA(element_node->data);
	  free(element_node);
	  element_node = element_next;
	}
	while (priority_node)
	{
	  PriorityNode* priority_next = priority_node->next;
	  free(priority_node);
	  priority_node = priority_next;
	}
	_priority_head = 0;
	 _head = 0;
	_count = 0;

	if(_mutex) _mutex->Unlock();
}

//---------------------------------------------------------------------------

void *PriorityQueue::Dequeue()
{

	void *data = NULL; 
	PriorityNode *node;
	QueueNode    *element_node;
	if (_count == 0)
		return data; // We cannot remove element from an EMPTY list object!

	if(_mutex) _mutex->Lock();	
	
	if(_head == _priority_head->element) // last element with same priority
	{
	  node=_priority_head->next;
	  free(_priority_head);
	  _priority_head=node;
	}

	element_node=_head->next;
	data=_head->data;
	free(_head);
	_head=element_node;

	// Adjust the _count of the PriorityQueue
	_count--;
	if(_mutex) _mutex->Unlock();
	// Everything is OK, return data
    return data;
}