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;         // current elements
  20   int count;            // current number of elements (minimal size for elements pointer)
  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 void
  52 queue_push(Queue *q, Id id)
  53 {
  54   if (!q->left)
  55     queue_alloc_one(q);
  56   q->elements[q->count++] = id;
  57   q->left--;
  58 }
  59
  60 static inline void
  61 queue_pushunique(Queue *q, Id id)
  62 {
  63   int i;
  64   for (i = q->count; i > 0; )
  65     if (q->elements[--i] == id)
  66       return;
  67   queue_push(q, id);
  68 }
  69
  70 extern void queue_clone(Queue *t, Queue *s);
  71 extern void queue_init(Queue *q);
  72 extern void queue_init_buffer(Queue *q, Id *buf, int size);
  73 extern void queue_free(Queue *q);
  74
  75 #endif /* SATSOLVER_QUEUE_H */