satsolver  0.17.2
queue.h
Go to the documentation of this file.
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); /* 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 
118 #endif /* SATSOLVER_QUEUE_H */
Generated by   doxygen 1.8.4