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 _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
queue_empty(Queue * q)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
queue_shift(Queue * q)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
queue_pop(Queue * q)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
queue_unshift(Queue * q,Id id)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
queue_push(Queue * q,Id id)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
queue_pushunique(Queue * q,Id id)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
queue_push2(Queue * q,Id id1,Id id2)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
queue_truncate(Queue * q,int n)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 *t, Queue *s);
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, 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 */
128