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