queue.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef SATSOLVER_QUEUE_H
00014 #define SATSOLVER_QUEUE_H
00015
00016 #include "pooltypes.h"
00017
00018 typedef struct _Queue {
00019 Id *elements;
00020 int count;
00021 Id *alloc;
00022 int left;
00023 } Queue;
00024
00025
00026 extern void queue_alloc_one(Queue *q);
00027 extern void queue_alloc_one_head(Queue *q);
00028
00029
00030 static inline void
00031 queue_empty(Queue *q)
00032 {
00033 if (q->alloc)
00034 {
00035 q->left += (q->elements - q->alloc) + q->count;
00036 q->elements = q->alloc;
00037 }
00038 else
00039 q->left += q->count;
00040 q->count = 0;
00041 }
00042
00043 static inline Id
00044 queue_shift(Queue *q)
00045 {
00046 if (!q->count)
00047 return 0;
00048 q->count--;
00049 return *q->elements++;
00050 }
00051
00052 static inline Id
00053 queue_pop(Queue *q)
00054 {
00055 if (!q->count)
00056 return 0;
00057 q->left++;
00058 return q->elements[--q->count];
00059 }
00060
00061 static inline void
00062 queue_unshift(Queue *q, Id id)
00063 {
00064 if (!q->alloc || q->alloc == q->elements)
00065 queue_alloc_one_head(q);
00066 *--q->elements = id;
00067 q->count++;
00068 }
00069
00070 static inline void
00071 queue_push(Queue *q, Id id)
00072 {
00073 if (!q->left)
00074 queue_alloc_one(q);
00075 q->elements[q->count++] = id;
00076 q->left--;
00077 }
00078
00079 static inline void
00080 queue_pushunique(Queue *q, Id id)
00081 {
00082 int i;
00083 for (i = q->count; i > 0; )
00084 if (q->elements[--i] == id)
00085 return;
00086 queue_push(q, id);
00087 }
00088
00089 static inline void
00090 queue_push2(Queue *q, Id id1, Id id2)
00091 {
00092 queue_push(q, id1);
00093 queue_push(q, id2);
00094 }
00095
00096 static inline void
00097 queue_truncate(Queue *q, int n)
00098 {
00099 if (q->count > n)
00100 {
00101 q->left += q->count - n;
00102 q->count = n;
00103 }
00104 }
00105
00106 extern void queue_init(Queue *q);
00107 extern void queue_init_buffer(Queue *q, Id *buf, int size);
00108 extern void queue_init_clone(Queue *t, Queue *s);
00109 extern void queue_free(Queue *q);
00110
00111 extern void queue_insert(Queue *q, int pos, Id id);
00112 extern void queue_insert2(Queue *q, int pos, Id id1, Id id2);
00113 extern void queue_insertn(Queue *q, int pos, int n);
00114 extern void queue_delete(Queue *q, int pos);
00115 extern void queue_delete2(Queue *q, int pos);
00116 extern void queue_deleten(Queue *q, int pos, int n);
00117
00118 #endif