src/int/queue.c

   1 #include "depend.h"
   2 #include "genint.h"
   3 #include "int.h"
   4 #include "process.h"
   5 #include "intproto.h"
   6
   7
   8 /**
   9  * @file
  10  */
  11 /* Queue management */
  12 /* Single linked circular lists with queue represented as pointer to rear */
  13
  14 /**
  15  * Initialize empty queue
  16  */
  17 queue qinit()
  18 {
  19         return NULL;
  20 }
  21
  22 /**
  23  * Insert element into the queue
  24  */
  25 stack push(stack q, selem e)
  26 {
  27         stack p;
  28
  29         p = (stack) ballocate(sizeof(struct queuelem));
  30         if (p == NULL)
  31                 errsignal(RTEMEMOV);
  32         p->elem = e;
  33         /* the lonely element of the queue */
  34         if (q == NULL) {
  35                 p->next = p;
  36                 q = p;
  37         } else {/* insert at rear */
  38                 p->next = q->next;
  39                 q->next = p;
  40         }
  41         return q;
  42 }
  43
  44 /**
  45  * Get first element of the queue
  46  */
  47 qelem qfront(queue q)
  48 {
  49         if (qempty(q)){
  50                 fprintf(stderr, "getting first element from empty queue\n");
  51                 errsignal(RTESYSER);
  52         }
  53         return q->next->elem;
  54 }
  55
  56 /**
  57  * Remove front element from the queue
  58  */
  59 queue qremove(queue q)
  60 {
  61         queue p;
  62
  63         if (qempty(q)){
  64                 fprintf(stderr, "removing first element from empty queue\n");
  65                 errsignal(RTESYSER);
  66         }
  67         p = q->next;
  68         q->next = q->next->next;
  69         /* removing last element of the queue */
  70         if (p == q)
  71                 q = NULL;
  72         free(p);
  73         return q;
  74 }
  75
  76 /**
  77  * Delete arbitrary element
  78  */
  79 queue qdelete(queue q, qelem e)
  80 {
  81         queue p;
  82         queue r;
  83         queue s;
  84
  85         if (qempty(q))
  86                 return q;
  87         r = q;
  88         p = r->next;
  89         while (p->elem != e) {
  90                 if (p == q)
  91                         return q;
  92                 r = p;
  93                 p = p->next;
  94         }
  95         r->next = p->next;
  96         if (r == p)
  97                 s = NULL;
  98         else if (p == q)
  99                 s = r;
 100         else
 101                 s = q;
 102         free(p);
 103         return s;
 104 }
 105
 106 /**
 107  * Remove front and insert at rear
 108  */
 109 queue qrotate(queue q)
 110 {
 111         if (qempty(q)){
 112                 fprintf(stderr, "rotating empty queue\n");
 113                 errsignal(RTESYSER);
 114         }
 115         return q->next;
 116 }
 117
 118
 119 /**
 120  *
 121  */
 122 void qfree(queue q)
 123 {
 124         while (!qempty(q)) {
 125                 free(qfront(q));
 126                 q = qremove(q);
 127         }
 128 }