queue.c

一个用在mips体系结构中的操作系统

/*
 * Copyright (C) 1996-1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * 
 * This file is part of the SimOS distribution. 
 * See LICENSE file for terms of the license. 
 *
 */

/* @TITLE "queue.c: queue data structure"*/
/* 
 * queue: this is a normal FIFO queue module, with a fixed maximum capacity.

 * David Kotz 1994
 */

/* $Id: queue.c,v 1.4 1998/02/10 00:36:48 bosch Exp $ */

#ifdef DFK
# include "dmcache.h"		/* the overall include file */
#else
# include "modularize.h"      /* the overall include file */
#endif
#include "queue.h"

/* debugging */
/* 
#define DEBUG_QUEUE(x) {CYCLE_COUNTING_OFF; printf x; CYCLE_COUNTING_ON;}
 */
#define DEBUG_QUEUE(x) {}

/* The queue data structure */
/* typedef struct queue_noncyc_s NCQUEUE; */ /* in queue.h */
struct queue_noncyc_s {
    char *debugname;	      /* name for debugging purposes */
    int length;		      /* length (max items+1) of queue */
    int first, last;	      /* begin and end of queue */
    Qitem *entries;	      /* array[length] of entries */
};

/* how many slots of the queue are used (either for items or for threads)? */
#define SLOTS_USED(q) (((q)->last + (q)->length - (q)->first) % (q)->length)
#define IS_EMPTY(q) ((q)->first == (q)->last)

/* @SUBTITLE "MakeQueue_noncyc: allocate a new queue" */
NCQUEUE *			      /* NULL if no space */
MakeQueue_noncyc(int size, char *debugname)
{
    NCQUEUE *q;

    size++;		      /* make room for dummy space in entries[] */

    q = (NCQUEUE *)malloc(sizeof(NCQUEUE));

    if (q == NULL)
      return(NULL);

    q->entries = (Qitem *)malloc(size * sizeof(Qitem));
    if (q->entries == NULL) {
	free(q);
	return(NULL);
    }

    q->debugname = debugname;
    q->length = size;
    q->first = q->last = 0;
 
    DEBUG_QUEUE(("MakeQueue_noncyc: %s queue 0x%lx  for %d elements\n", 
		 debugname, (ulong)q, size-1));
    
    return(q);
}

/* @SUBTITLE "FreeQueue_noncyc: free a queue" */
void
FreeQueue_noncyc(NCQUEUE *q)
{
    DEBUG_QUEUE(("FreeQueue_noncyc: queue %s\n", q->debugname));

    if (q != NULL) {
	if (q->entries != NULL)
	  free(q->entries);
	free(q);
    }
}

/* @SUBTITLE "InQueue: how many items in the queue?" */
int
InQueue_noncyc(NCQUEUE *qp)
{
    register NCQUEUE *q = qp;
    return(SLOTS_USED(q));
}

/* @SUBTITLE "EmptyQueue_noncyc: is the queue empty?" */
boolean			      /* TRUE if queue is empty */
EmptyQueue_noncyc(NCQUEUE *qp)
{
    register NCQUEUE *q = qp;
    return(IS_EMPTY(q));
}

/* @SUBTITLE "Enqueue_noncyc: add an item to the queue" */
void
Enqueue_noncyc(NCQUEUE *qp, Qitem item)
{
    register NCQUEUE *q = qp;

    /* check for overflow */
    INVARIANT4(!((q->last + 1) % q->length == q->first),
	       "NCqueue 0x%lx overflowed its limit of %d items\n",
	       (unsigned long) q, q->length-1);
    
    q->entries[q->last] = (item);
    q->last = (q->last + 1) % q->length;

    DEBUG_QUEUE(("Enqueue_noncyc: queue %s <- item 0x%lx\n", 
		 q->debugname, (ulong)item));
}

/* @SUBTITLE "Dequeue_noncyc: take an item from the queue" */
void
Dequeue_noncyc(NCQUEUE *qp, Qitem *itemp)
{
    register NCQUEUE *q = qp;

    INVARIANT3(!IS_EMPTY(q), "Dequeue_noncyc: Queue 0x%lx is empty\n",
	       (ulong)q);
    
    *itemp = q->entries[q->first];
    q->first = (q->first + 1) % q->length;

    DEBUG_QUEUE(("Dequeue_noncyc: queue %s -> item 0x%lx\n", 
		 q->debugname, (ulong)(*itemp)));
}