Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 120 lines (102 sloc) 2.364 kB
8f8a9ed @kkaempf current state of 'sat-solver'
kkaempf authored
1 /*
1312779 @mlschroe - add a license
mlschroe authored
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 /*
8f8a9ed @kkaempf current state of 'sat-solver'
kkaempf authored
9 * queue.h
10 *
11 */
12
4cd5d62 @mlschroe rename satsolver -> libsolv
mlschroe authored
13 #ifndef LIBSOLV_QUEUE_H
14 #define LIBSOLV_QUEUE_H
8f8a9ed @kkaempf current state of 'sat-solver'
kkaempf authored
15
16 #include "pooltypes.h"
17
18 typedef struct _Queue {
e38c7e9 @mlschroe - split problem handling from solver.c
mlschroe authored
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 */
8f8a9ed @kkaempf current state of 'sat-solver'
kkaempf authored
23 } Queue;
24
2b4044a @mlschroe - rename queue* to queue_*, inline a bit more
mlschroe authored
25
ac9f5e8 @mlschroe - add queue_insertn, queue_deleten, queue_truncate
mlschroe authored
26 extern void queue_alloc_one(Queue *q); /* internal */
27 extern void queue_alloc_one_head(Queue *q); /* internal */
2b4044a @mlschroe - rename queue* to queue_*, inline a bit more
mlschroe authored
28
e38c7e9 @mlschroe - split problem handling from solver.c
mlschroe authored
29 /* clear queue */
2b4044a @mlschroe - rename queue* to queue_*, inline a bit more
mlschroe authored
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
e38c7e9 @mlschroe - split problem handling from solver.c
mlschroe authored
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 {
ac9f5e8 @mlschroe - add queue_insertn, queue_deleten, queue_truncate
mlschroe authored
64 if (!q->alloc || q->alloc == q->elements)
65 queue_alloc_one_head(q);
66 *--q->elements = id;
e38c7e9 @mlschroe - split problem handling from solver.c
mlschroe authored
67 q->count++;
68 }
69
2b4044a @mlschroe - rename queue* to queue_*, inline a bit more
mlschroe authored
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 }
8f8a9ed @kkaempf current state of 'sat-solver'
kkaempf authored
78
2b4044a @mlschroe - rename queue* to queue_*, inline a bit more
mlschroe authored
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 }
8f8a9ed @kkaempf current state of 'sat-solver'
kkaempf authored
88
e38c7e9 @mlschroe - split problem handling from solver.c
mlschroe authored
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
ac9f5e8 @mlschroe - add queue_insertn, queue_deleten, queue_truncate
mlschroe authored
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
2b4044a @mlschroe - rename queue* to queue_*, inline a bit more
mlschroe authored
106 extern void queue_init(Queue *q);
107 extern void queue_init_buffer(Queue *q, Id *buf, int size);
e38c7e9 @mlschroe - split problem handling from solver.c
mlschroe authored
108 extern void queue_init_clone(Queue *t, Queue *s);
2b4044a @mlschroe - rename queue* to queue_*, inline a bit more
mlschroe authored
109 extern void queue_free(Queue *q);
8f8a9ed @kkaempf current state of 'sat-solver'
kkaempf authored
110
3ef06f9 @mlschroe - update transaction ordering code
mlschroe authored
111 extern void queue_insert(Queue *q, int pos, Id id);
112 extern void queue_insert2(Queue *q, int pos, Id id1, Id id2);
ac9f5e8 @mlschroe - add queue_insertn, queue_deleten, queue_truncate
mlschroe authored
113 extern void queue_insertn(Queue *q, int pos, int n);
3ef06f9 @mlschroe - update transaction ordering code
mlschroe authored
114 extern void queue_delete(Queue *q, int pos);
115 extern void queue_delete2(Queue *q, int pos);
ac9f5e8 @mlschroe - add queue_insertn, queue_deleten, queue_truncate
mlschroe authored
116 extern void queue_deleten(Queue *q, int pos, int n);
8cf2c0a @mlschroe - add map_or and queue_prealloc
mlschroe authored
117 extern void queue_prealloc(Queue *q, int n);
3ef06f9 @mlschroe - update transaction ordering code
mlschroe authored
118
4cd5d62 @mlschroe rename satsolver -> libsolv
mlschroe authored
119 #endif /* LIBSOLV_QUEUE_H */
Something went wrong with that request. Please try again.