src/queue.h

   1 /*
   2  * Copyright (c) 2007, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * queue.h
  10  *
  11  */
  12
  13 #ifndef SATSOLVER_QUEUE_H
  14 #define SATSOLVER_QUEUE_H
  15
  16 #include "pooltypes.h"
  17
  18 typedef struct _Queue {
  19   Id *elements;         /* pointer to elements */
  20   int count;            /* current number of elements in queue */
  21   Id *alloc;            /* this is whats actually allocated, elements > alloc if shifted */
  22   int left;             /* space left in alloc *after* elements+count */
  23 } Queue;
  24
  25
  26 extern void queue_alloc_one(Queue *q);
  27
  28 /* clear queue */
  29 static inline void
  30 queue_empty(Queue *q)
  31 {
  32   if (q->alloc)
  33     {
  34       q->left += (q->elements - q->alloc) + q->count;
  35       q->elements = q->alloc;
  36     }
  37   else
  38     q->left += q->count;
  39   q->count = 0;
  40 }
  41
  42 static inline Id
  43 queue_shift(Queue *q)
  44 {
  45   if (!q->count)
  46     return 0;
  47   q->count--;
  48   return *q->elements++;
  49 }
  50
  51 static inline Id
  52 queue_pop(Queue *q)
  53 {
  54   if (!q->count)
  55     return 0;
  56   q->left++;
  57   return q->elements[--q->count];
  58 }
  59
  60 static inline void
  61 queue_unshift(Queue *q, Id id)
  62 {
  63   if (q->alloc && q->alloc != q->elements)
  64     {
  65       *--q->elements = id;
  66       q->count++;
  67       return;
  68     }
  69   if (!q->left)
  70     queue_alloc_one(q);
  71   if (q->count)
  72     memmove(q->elements + 1, q->elements, sizeof(Id) * q->count);
  73   q->count++;
  74   q->elements[0] = id;
  75   q->left--;
  76 }
  77
  78 static inline void
  79 queue_push(Queue *q, Id id)
  80 {
  81   if (!q->left)
  82     queue_alloc_one(q);
  83   q->elements[q->count++] = id;
  84   q->left--;
  85 }
  86
  87 static inline void
  88 queue_pushunique(Queue *q, Id id)
  89 {
  90   int i;
  91   for (i = q->count; i > 0; )
  92     if (q->elements[--i] == id)
  93       return;
  94   queue_push(q, id);
  95 }
  96
  97 static inline void
  98 queue_push2(Queue *q, Id id1, Id id2)
  99 {
 100   queue_push(q, id1);
 101   queue_push(q, id2);
 102 }
 103
 104 extern void queue_init(Queue *q);
 105 extern void queue_init_buffer(Queue *q, Id *buf, int size);
 106 extern void queue_init_clone(Queue *t, Queue *s);
 107 extern void queue_free(Queue *q);
 108
 109 extern void queue_insert(Queue *q, int pos, Id id);
 110 extern void queue_insert2(Queue *q, int pos, Id id1, Id id2);
 111 extern void queue_delete(Queue *q, int pos);
 112 extern void queue_delete2(Queue *q, int pos);
 113
 114 #endif /* SATSOLVER_QUEUE_H */