Desktop/xinu_mips-1.0.2.tar/xinu_mips-1.0.2/include/queue.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	qentry
Defines
#define	NSEM   100
#define	NQENT
#define	queuehead(q)   (((q) >> 16) & 0xFFFF)
#define	queuetail(q)   ((q) & 0xFFFF)
#define	isbadqueue(x)   (queuehead(x)<0 || (queuehead(x) != (queuetail(x) - 1)) || queuetail(x)>=NQENT)
#define	isempty(q)   (queuetab[queuehead(q)].next >= NPROC)
#define	nonempty(q)   (queuetab[queuehead(q)].next < NPROC)
#define	firstkey(q)   (queuetab[queuetab[queuehead(q)].next].key)
#define	lastkey(q)   (queuetab[queuetab[queuetail(q)].prev].key)
#define	firstid(q)   (queuetab[queuehead(q)].next)
Typedefs
typedef unsigned long	queue
Functions
short	enqueue (short, queue)
short	insert (short, queue, short)
short	insertd (short, queue, short)
short	remove (short)
short	dequeue (queue)
queue	newqueue (void)
Variables
struct qentry	queuetab []
queue	readylist

---

Detailed Description

firstid, firstkey, isempty, lastkey, nonempty

The process queue system allows a statically-allocated array to model sorted process queueing before more complex operating system services, like dynamic memory allocation, are up and running.

These process queues assume several important invariants: 1) A fixed number of process queues in the system, known at compile time, 2) A process queue can contain only processes and their associated key values, and thus queue length is at most NPROC, the total number of processes, and 3) A process can be in at most one queue at a time.

Ordering of processes within a given queue depends upon the sorting functions called when maintaining that particular system queue.

Id

queue.h 240 2007-07-13 21:43:45Z brylow

Definition in file queue.h.

---

Define Documentation

#define firstid

(

q

)

(queuetab[queuehead(q)].next)

Definition at line 67 of file queue.h.

#define firstkey

(

q

)

(queuetab[queuetab[queuehead(q)].next].key)

Definition at line 65 of file queue.h.

Referenced by clockintr(), test_deltaQueue(), test_procQueue(), and wakeup().

#define isbadqueue

(

x

)

(queuehead(x)<0 || (queuehead(x) != (queuetail(x) - 1)) || queuetail(x)>=NQENT)

Check for invalid process ids. Note that interrupts must be disabled for the condition to hold true between statements.

Definition at line 61 of file queue.h.

Referenced by dequeue(), enqueue(), insert(), and insertd().

#define isempty

(

q

)

(queuetab[queuehead(q)].next >= NPROC)

Definition at line 63 of file queue.h.

#define lastkey

(

q

)

(queuetab[queuetab[queuetail(q)].prev].key)

Definition at line 66 of file queue.h.

#define nonempty

(

q

)

(queuetab[queuehead(q)].next < NPROC)

Definition at line 64 of file queue.h.

Referenced by clockintr(), freesem(), nulluser(), and wakeup().

#define NQENT

Value:

NPROC    \
          + 2            \
          + 2            \
          + NSEM + NSEM

plus two for each semaphore

Definition at line 34 of file queue.h.

#define NSEM   100

number of semaphores, if not defined

Definition at line 30 of file queue.h.

#define queuehead

(

q

)

(((q) >> 16) & 0xFFFF)

Definition at line 54 of file queue.h.

Referenced by dequeue(), insert(), and insertd().

#define queuetail

(

q

)

((q) & 0xFFFF)

Definition at line 55 of file queue.h.

Referenced by enqueue(), insert(), and insertd().

---

Typedef Documentation

typedef unsigned long queue

Definition at line 40 of file queue.h.

---

Function Documentation

short dequeue

(

queue

q

)

Remove and return the first process on a list

Parameters:

q

queue from which process should be removed

Returns:

process id of removed process, or EMPTY

Definition at line 57 of file queue.c.

References EMPTY, isbadqueue, qentry::next, NPROC, qentry::prev, queuehead, queuetab, and SYSERR.

Referenced by freesem(), resched(), signal(), signaln(), test_deltaQueue(), test_procQueue(), and wakeup().

short enqueue	(	short	pid,
		queue	q
	)

Insert a process at the tail of a queue

Parameters:

	pid	process ID to enqueue
	q	queue to which the process should be added

Returns:

process id of enqueued process

Definition at line 21 of file queue.c.

References isbadpid, isbadqueue, qentry::next, qentry::prev, queuetab, queuetail, and SYSERR.

Referenced by wait().

short insert	(	short	pid,
		queue	q,
		short	key
	)

Insert a process into a queue in descending key order.

Parameters:

	pid	process id to insert
	q	queue in which process should be inserted
	key	sorting key (priority, for example)

Returns:

OK

Definition at line 20 of file insert.c.

References isbadpid, isbadqueue, qentry::key, qentry::next, memblock::next, OK, qentry::prev, queuehead, queuetab, queuetail, and SYSERR.

Referenced by ready(), resched(), and test_procQueue().

short insertd	(	short	pid,
		queue	q,
		short	key
	)

Insert a process in delta queue in ascending order

Parameters:

	pid	process id to insert
	q	queue in which process should be inserted
	key	delta key

Returns:

OK

Definition at line 20 of file insertd.c.

References isbadpid, isbadqueue, qentry::key, qentry::next, memblock::next, OK, qentry::prev, queuehead, queuetab, queuetail, and SYSERR.

Referenced by sleep(), and test_deltaQueue().

queue newqueue

(

void

)

Initialize a new queue in the global process queue table

Returns:

newly allocated

Definition at line 79 of file queue.c.

References EMPTY, qentry::next, nextqueue, qentry::prev, and queuetab.

Referenced by sysinit().

short remove

(

short

pid

)

Remove a process from anywhere in a queue

Parameters:

pid

process ID to remove

Returns:

process id of removed process

Definition at line 43 of file queue.c.

References isbadpid, qentry::next, qentry::prev, queuetab, and SYSERR.

---

Variable Documentation

struct qentry queuetab[]

global queue table

Definition at line 12 of file queue.c.

Referenced by dequeue(), enqueue(), insert(), insertd(), newqueue(), and remove().

queue readylist

Definition at line 41 of file initialize.c.

Referenced by nulluser(), ready(), resched(), and sysinit().