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 LIBSOLV_QUEUE_H
  14 #define LIBSOLV_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);          /* internal */
  27 extern void queue_alloc_one_head(Queue *q);     /* internal */
  28
  29 /* clear queue */
  30 static inline void
  31 queue_empty(Queue *q)
  32 {
  33   if (q->alloc)
  34     {
  35       q->left += (q->elements - q->alloc) + q->count;
  36       q->elements = q->alloc;
  37     }
  38   else
  39     q->left += q->count;
  40   q->count = 0;
  41 }
  42
  43 static inline Id
  44 queue_shift(Queue *q)
  45 {
  46   if (!q->count)
  47     return 0;
  48   q->count--;
  49   return *q->elements++;
  50 }
  51
  52 static inline Id
  53 queue_pop(Queue *q)
  54 {
  55   if (!q->count)
  56     return 0;
  57   q->left++;
  58   return q->elements[--q->count];
  59 }
  60
  61 static inline void
  62 queue_unshift(Queue *q, Id id)
  63 {
  64   if (!q->alloc || q->alloc == q->elements)
  65     queue_alloc_one_head(q);
  66   *--q->elements = id;
  67   q->count++;
  68 }
  69
  70 static inline void
  71 queue_push(Queue *q, Id id)
  72 {
  73   if (!q->left)
  74     queue_alloc_one(q);
  75   q->elements[q->count++] = id;
  76   q->left--;
  77 }
  78
  79 static inline void
  80 queue_pushunique(Queue *q, Id id)
  81 {
  82   int i;
  83   for (i = q->count; i > 0; )
  84     if (q->elements[--i] == id)
  85       return;
  86   queue_push(q, id);
  87 }
  88
  89 static inline void
  90 queue_push2(Queue *q, Id id1, Id id2)
  91 {
  92   queue_push(q, id1);
  93   queue_push(q, id2);
  94 }
  95
  96 static inline void
  97 queue_truncate(Queue *q, int n)
  98 {
  99   if (q->count > n)
 100     {
 101       q->left += q->count - n;
 102       q->count = n;
 103     }
 104 }
 105
 106 extern void queue_init(Queue *q);
 107 extern void queue_init_buffer(Queue *q, Id *buf, int size);
 108 extern void queue_init_clone(Queue *t, Queue *s);
 109 extern void queue_free(Queue *q);
 110
 111 extern void queue_insert(Queue *q, int pos, Id id);
 112 extern void queue_insert2(Queue *q, int pos, Id id1, Id id2);
 113 extern void queue_insertn(Queue *q, int pos, int n);
 114 extern void queue_delete(Queue *q, int pos);
 115 extern void queue_delete2(Queue *q, int pos);
 116 extern void queue_deleten(Queue *q, int pos, int n);
 117 extern void queue_prealloc(Queue *q, int n);
 118
 119 #endif /* LIBSOLV_QUEUE_H */