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 #ifdef __cplusplus
  19 extern "C" {
  20 #endif
  21
  22 typedef struct s_Queue {
  23   Id *elements;         /* pointer to elements */
  24   int count;            /* current number of elements in queue */
  25   Id *alloc;            /* this is whats actually allocated, elements > alloc if shifted */
  26   int left;             /* space left in alloc *after* elements+count */
  27 } Queue;
  28
  29
  30 extern void queue_alloc_one(Queue *q);          /* internal */
  31 extern void queue_alloc_one_head(Queue *q);     /* internal */
  32
  33 /* clear queue */
  34 static inline void
  35 queue_empty(Queue *q)
  36 {
  37   if (q->alloc)
  38     {
  39       q->left += (q->elements - q->alloc) + q->count;
  40       q->elements = q->alloc;
  41     }
  42   else
  43     q->left += q->count;
  44   q->count = 0;
  45 }
  46
  47 static inline Id
  48 queue_shift(Queue *q)
  49 {
  50   if (!q->count)
  51     return 0;
  52   q->count--;
  53   return *q->elements++;
  54 }
  55
  56 static inline Id
  57 queue_pop(Queue *q)
  58 {
  59   if (!q->count)
  60     return 0;
  61   q->left++;
  62   return q->elements[--q->count];
  63 }
  64
  65 static inline void
  66 queue_unshift(Queue *q, Id id)
  67 {
  68   if (!q->alloc || q->alloc == q->elements)
  69     queue_alloc_one_head(q);
  70   *--q->elements = id;
  71   q->count++;
  72 }
  73
  74 static inline void
  75 queue_push(Queue *q, Id id)
  76 {
  77   if (!q->left)
  78     queue_alloc_one(q);
  79   q->elements[q->count++] = id;
  80   q->left--;
  81 }
  82
  83 static inline void
  84 queue_pushunique(Queue *q, Id id)
  85 {
  86   int i;
  87   for (i = q->count; i > 0; )
  88     if (q->elements[--i] == id)
  89       return;
  90   queue_push(q, id);
  91 }
  92
  93 static inline void
  94 queue_push2(Queue *q, Id id1, Id id2)
  95 {
  96   queue_push(q, id1);
  97   queue_push(q, id2);
  98 }
  99
 100 static inline void
 101 queue_truncate(Queue *q, int n)
 102 {
 103   if (q->count > n)
 104     {
 105       q->left += q->count - n;
 106       q->count = n;
 107     }
 108 }
 109
 110 extern void queue_init(Queue *q);
 111 extern void queue_init_buffer(Queue *q, Id *buf, int size);
 112 extern void queue_init_clone(Queue *target, const Queue *source);
 113 extern void queue_free(Queue *q);
 114
 115 extern void queue_insert(Queue *q, int pos, Id id);
 116 extern void queue_insert2(Queue *q, int pos, Id id1, Id id2);
 117 extern void queue_insertn(Queue *q, int pos, int n, const Id *elements);
 118 extern void queue_delete(Queue *q, int pos);
 119 extern void queue_delete2(Queue *q, int pos);
 120 extern void queue_deleten(Queue *q, int pos, int n);
 121 extern void queue_prealloc(Queue *q, int n);
 122
 123 #ifdef __cplusplus
 124 }
 125 #endif
 126
 127 #endif /* LIBSOLV_QUEUE_H */