ccache_queue.c

harvest是一个下载html网页得机器人

static char rcsid[] = "ccache_queue.c,v 1.11 1995/11/29 00:48:31 duane Exp";
/*
 *  queue.c - FIFO queue routines
 *
 *  David Merkel & Mark Peterson, University of Colorado - Boulder, July 1994  
 *
 *  ----------------------------------------------------------------------
 *  Copyright (c) 1994, 1995.  All rights reserved.
 *  
 *    The Harvest software was developed by the Internet Research Task
 *    Force Research Group on Resource Discovery (IRTF-RD):
 *  
 *          Mic Bowman of Transarc Corporation.
 *          Peter Danzig of the University of Southern California.
 *          Darren R. Hardy of the University of Colorado at Boulder.
 *          Udi Manber of the University of Arizona.
 *          Michael F. Schwartz of the University of Colorado at Boulder.
 *          Duane Wessels of the University of Colorado at Boulder.
 *  
 *    This copyright notice applies to software in the Harvest
 *    ``src/'' directory only.  Users should consult the individual
 *    copyright notices in the ``components/'' subdirectories for
 *    copyright information about other software bundled with the
 *    Harvest source code distribution.
 *  
 *  TERMS OF USE
 *    
 *    The Harvest software may be used and re-distributed without
 *    charge, provided that the software origin and research team are
 *    cited in any use of the system.  Most commonly this is
 *    accomplished by including a link to the Harvest Home Page
 *    (http://harvest.cs.colorado.edu/) from the query page of any
 *    Broker you deploy, as well as in the query result pages.  These
 *    links are generated automatically by the standard Broker
 *    software distribution.
 *    
 *    The Harvest software is provided ``as is'', without express or
 *    implied warranty, and with no support nor obligation to assist
 *    in its use, correction, modification or enhancement.  We assume
 *    no liability with respect to the infringement of copyrights,
 *    trade secrets, or any patents, and are not responsible for
 *    consequential damages.  Proper use of the Harvest software is
 *    entirely the responsibility of the user.
 *  
 *  DERIVATIVE WORKS
 *  
 *    Users may make derivative works from the Harvest software, subject 
 *    to the following constraints:
 *  
 *      - You must include the above copyright notice and these 
 *        accompanying paragraphs in all forms of derivative works, 
 *        and any documentation and other materials related to such 
 *        distribution and use acknowledge that the software was 
 *        developed at the above institutions.
 *  
 *      - You must notify IRTF-RD regarding your distribution of 
 *        the derivative work.
 *  
 *      - You must clearly notify users that your are distributing 
 *        a modified version and not the original Harvest software.
 *  
 *      - Any derivative product is also subject to these copyright 
 *        and use restrictions.
 *  
 *    Note that the Harvest software is NOT in the public domain.  We
 *    retain copyright, as specified above.
 *  
 *  HISTORY OF FREE SOFTWARE STATUS
 *  
 *    Originally we required sites to license the software in cases
 *    where they were going to build commercial products/services
 *    around Harvest.  In June 1995 we changed this policy.  We now
 *    allow people to use the core Harvest software (the code found in
 *    the Harvest ``src/'' directory) for free.  We made this change
 *    in the interest of encouraging the widest possible deployment of
 *    the technology.  The Harvest software is really a reference
 *    implementation of a set of protocols and formats, some of which
 *    we intend to standardize.  We encourage commercial
 *    re-implementations of code complying to this set of standards.  
 *  
 */
#include <stdio.h>
#include <stdlib.h>
#include "ccache.h"
#include "ccache_list.h"
#include "ccache_queue.h"
#include "time_it.h"

/**************************************************************************
**
**	DESCRIPTION
**		Remove a node from the top of the queue.
**
**	FUNCTIONS
**		dequeue()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		Need a queue!
**
**	POSTCONDITIONS
**		Function returns a Boolean operator telling whether or not
**		the function was successful.  
**		Note:  An empty queue returns false.
**************************************************************************/


Datum *dequeue(q)
     Queue *q;
{
	return (list_delete(q, q->first));
	/*All error handling done by list package. */
}
/**************************************************************************
**
**	DESCRIPTION
**		enqueue data at the end of the queue
**
**	FUNCTIONS
**		enqueue()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		There must be a queue!
**
**	POSTCONDITIONS
**		A Boolean operator is returned.  Either TRUE stating the 
**		operation was successful or FALSE stating it was not.
***************************************************************************/

Boolean enqueue(q, data)
     Queue *q;
     Datum *data;

{
	if (list_insert(q, data, list_last(q)) == NULL)
		return (FALSE);
	/*If error in list_insert, return error. */

	return (TRUE);
}
/**************************************************************************
**
**	DESCRIPTION
**		Apply a function to each node in the queue.
**
**	FUNCTIONS
**		queue_apply()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		Need a list and a prewritten function which is applied to 
**		each node's data in the queue.
**
**	POSTCONDITIONS
**		A Boolean operator is returned.  Either TRUE if everything is 
**		successful or FALSE if it is either function crashes.  If the
**		applied function crashes in the middle of the queue, only those
**		nodes to that point are affected.  They will remain as such.
**************************************************************************/

Boolean queue_apply(q, func)
     Queue *q;
Boolean(*func) ();

{
	return (list_apply(func, q));
	/*Call list function.  It handles it all! */
}

/**************************************************************************
**
**	DESCRIPTION
**		Creates a queue header and returns a pointer to it, or to 
**		NULL if it is unsuccessful.
**
**	FUNCTIONS
**		queue_create()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		None
**
**	POSTCONDITIONS
**		A pointer to a new queue header should be returned or a NULL
**		if the operation is unsuccessful.
**************************************************************************/

Boolean compare()
{
	return (TRUE);
}

Queue *queue_create()
{
	return (list_create(compare));	/*Create header node */
}

/**************************************************************************
**
**	DESCRIPTION
**		Frees the queue memory
**
**	FUNCTIONS
**		queue_destroy()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		There must be at least a queue header made using the queue 
**		package.
**
**	POSTCONDITIONS
**		Queue memory is freed.  All data is lost.
***************************************************************************/

void queue_destroy(q)
     Queue *q;
{
	list_destroy(q);
	return;
}
/**************************************************************************
**
**	DESCRIPTION
**		Function to see if queue still contains nodes.
**
**	FUNCTIONS
**		queue_empty()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		Need a queue.
**
**	POSTCONDITIONS
**		Returns a Boolean operator telling whether or not the queue is
**		empty.
**
**	NOTE:  A NULL pointer will return TRUE.
***************************************************************************/

Boolean queue_empty(q)
     Queue *q;
{

	if (q == NULL)
		return (TRUE);
	/*Check to see if there is a Queue. */

	if (q->first == NULL)
		return (TRUE);
	/*Yes, it's empty! */

	return (FALSE);
}
/**************************************************************************
**
**	FILE
**		tdequeue.c
**
**	DESCRIPTION
**		Remove a node from the queue.
**
**	FUNCTIONS
**		tdequeue()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		Need a queue!
**
**	POSTCONDITIONS
**		Function returns a Boolean operator telling whether or not
**		the function was successful.  
**		Note:  An empty queue returns false.
**************************************************************************/

int tdequeue(q, eventnum)
     Queue *q;
     int eventnum;
{
	List_Node *tmp_node;
	Boolean found;

	found = FALSE;
	tmp_node = list_first(q);
	if (tmp_node == NULL)
		return (0);
	do {
		if (eventnum ==
		    ((Time_Node *) (list_getdata(tmp_node)))->eventnum)
			found = TRUE;
		else
			tmp_node = list_next(tmp_node);
	}
	while (!found && tmp_node != list_first(q));
	if (!found)
		return (0);
	if (list_last(q) == tmp_node)
		return (list_delete(q, list_last(q)) != NULL);
	((Time_Node *) (list_getdata(list_next(tmp_node))))->time_in_secs +=
	    ((Time_Node *) (list_getdata(tmp_node)))->time_in_secs;
	if (list_first(q) != tmp_node)
		return (list_delete(q, tmp_node) != NULL);
	if (list_delete(q, tmp_node) != NULL)
		return (-1);
	else
		return (0);
}
/**************************************************************************
**
**	DESCRIPTION
**		enqueue data in the queue
**
**	FUNCTIONS
**		tenqueue()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		There must be a queue!
**
**	POSTCONDITIONS
**		A Boolean operator is returned.  Either TRUE stating the 
**		operation was successful or FALSE stating it was not.
***************************************************************************/

Boolean tenqueue(q, tdata, ivalue)
     Queue *q;
     Time_Node *tdata;
     int ivalue;
{

	List_Node *tmp_node;
	List_Node *tracer;

	if (!q)
		return (FALSE);
	tmp_node = (List_Node *) malloc(sizeof(List_Node));
	/*allocate memory for new node */

	if (tmp_node == NULL)
		return (FALSE);
	tmp_node->data = (Datum *) tdata;
	tracer = list_first(q);
	if (tracer == NULL)
		/*Empty Queue */
	{
		list_first(q) = tmp_node;
		list_last(q) = tmp_node;
		list_previous(tmp_node) = tmp_node;
		list_next(tmp_node) = tmp_node;
	} else if ((ivalue > (tdata->time_in_secs)) &&
		    (ivalue <= ((Time_Node *)
			    (list_getdata(list_first(q))))->time_in_secs) &&
	    (ivalue > 0))
		/*Change time value of first then insert node. */
	{
		list_previous(tmp_node) = list_last(q);
		list_next(tmp_node) = list_first(q);
		list_previous(list_first(q)) = tmp_node;
		list_next(list_last(q)) = tmp_node;
		list_first(q) = tmp_node;
		((Time_Node *)
		    (list_getdata(list_next(tmp_node))))->time_in_secs =
		    ivalue - (tdata->time_in_secs);
	} else {
		if ((((Time_Node *) (list_getdata(tracer)))->time_in_secs >
			ivalue) && (ivalue > 0)) {
			((Time_Node *)
			    (list_getdata(tracer)))->time_in_secs = ivalue;
		}
		while ((((Time_Node *) (list_getdata(tmp_node)))->time_in_secs) >= (((Time_Node *) (list_getdata(tracer)))->time_in_secs) && (list_last(q) != tracer)) {
			((Time_Node *) (list_getdata(tmp_node)))->time_in_secs -= ((Time_Node *) (list_getdata(tracer)))->time_in_secs;
			tracer = list_next(tracer);
		}
		if (list_last(q) == tracer && (((Time_Node *) (list_getdata(tmp_node)))->time_in_secs >= ((Time_Node *) (list_getdata(tracer)))->time_in_secs)) {
			((Time_Node *) (list_getdata(tmp_node)))->time_in_secs -= ((Time_Node *) (list_getdata(tracer)))->time_in_secs;
			list_next(tmp_node) = list_first(q);
			list_previous(tmp_node) = tracer;
			list_previous(list_first(q)) = tmp_node;
			list_next(tracer) = tmp_node;
			list_last(q) = tmp_node;
		} else {
			list_next(tmp_node) = tracer;
			list_previous(tmp_node) = list_previous(tracer);
			list_previous(tracer) = tmp_node;
			list_next(list_previous(tmp_node)) = tmp_node;
			if (list_first(q) == tracer)
				list_first(q) = tmp_node;
			((Time_Node *) (list_getdata(tracer)))->time_in_secs -= ((Time_Node *) (list_getdata(tmp_node)))->time_in_secs;
		}
	}
	queue_length(q)++;
	return (TRUE);
}
/**************************************************************************
**
**	DESCRIPTION
**		Returns a pointer to the data on the top of the queue.
**
**	FUNCTIONS
**		head()
**
**	DEPENDENCIES
**		"list.h"
**		"queue.h"
**
**	AUTHOR
**		Mark Peterson  9/91	[e-mail]
**
**	PRECONDITIONS
**		We need a list.
**
**	POSTCONDITIONS
**		A data pointer is returned to the first item in the queue.
***************************************************************************/

Datum *head(q)
     Queue *q;
{
	if (q == NULL)
		return (NULL);
	/*See if queue exists. */

	if (!queue_empty(q))
		return (q->first->data);
	/*If queue is not empty return data in first node. */

	return (NULL);
}