queue.c
3.32 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
* 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.1.1.1 2002/05/29 01:09:11 blythe 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)));
}