home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume44 / toy_os / part04 / sysqueues.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-05  |  2.9 KB  |  88 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3.  ************************************************************************
  4.  *
  5.  *                  Generic Asynchronous Queue
  6.  *
  7.  * The present file declares classes to handle simple double-linked queues
  8.  * in a multiple access mode. Two semaphores are provided to resolve
  9.  * possible conflicts due to the access to the queue by several concurrently
  10.  * running processes (threads). One semaphore counts the no. of available
  11.  * resources (elements of the queue). A thread requesting the unavailable
  12.  * resource, i.e. wanting to get an element from the empty queue, is to be
  13.  * put down to sleep until somebody else would enqueue smth into the queue.
  14.  * It means, the dequeuing process performs P-operation and the enqueuing 
  15.  * one needs to do V-operation on the count semaphore of the queue. Another
  16.  * semaphor provides for the establishing of the critical section when
  17.  * the process updates control structures of the queue.
  18.  *
  19.  * The queue is double-linked and allows a variety of operations, 
  20.  * inserting an element to the head/tail of the queue, dequeuing an element
  21.  * from the head as well as from arbitrary position of the queue,
  22.  * search on id and key. A queue element (slot) contains, besides
  23.  * linking pointers, two integer fields, id and key, which the user
  24.  * can use in any way he thinks fit. Queue opeartions do not change them,
  25.  * though some functions are provided for searching for the id and the key.
  26.  *
  27.  * The implementation of queues is based on the double-linked list.
  28.  *
  29.  ************************************************************************
  30.  */
  31.  
  32. #ifndef _sysqueues_h
  33. #define _sysqueues_h 1
  34. #pragma interface
  35.  
  36. #include "mult_proc.h"
  37.  
  38. class BasicQueue;
  39.  
  40.                 // This is how an element of the queue
  41.                 // looks like
  42. class QueueLink
  43. {
  44.   friend class BasicQueue;
  45.  
  46.   QueueLink * prev;            // Ptr to the prev element
  47.   QueueLink * next;            // Ptr to the next element
  48.  
  49. public:
  50.   int id;                // Some ID
  51.   int key;                // Arbitrary key
  52.  
  53.   QueueLink(void) : prev(0), next(0) {}
  54.   virtual ~QueueLink(void) {}
  55. };
  56.  
  57. class BasicQueue
  58. {
  59.   int   no_elements;            // No. of occupied slots
  60.   QueueLink * head;            // Ptr to the 1st element in the
  61.                     // queue
  62.   QueueLink * tail;            // Ptr to the last element in the
  63.                     // queue
  64.   Semaphore access_lock;
  65.   Semaphore queue_sema;
  66.  
  67. public:
  68.  
  69.   BasicQueue(void);            // Create a queue of a given capacity
  70.   ~BasicQueue(void) {}
  71.  
  72.                     // Inquires
  73.  
  74.                     // Return TRUE if the queue is empty
  75.   int is_empty() const        { return no_elements == 0; }
  76.  
  77.                     // Return the no. elems in the queue
  78.   int q_no_elems() const    { return no_elements; }
  79.   void dump_ids(void);            // Dump IDs of elements in the queue
  80.  
  81.   QueueLink * get_from_head(void);    // Get and dequeue the top element
  82.   void append(QueueLink& el);        // Add an element to the end of queue
  83.   void dequeue(QueueLink& el);        // Dequeue a given element
  84.   int purge_id(const int id);        // Purge a queue from a given element
  85. };
  86.  
  87. #endif
  88.