satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2007, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 /* 00009 * queue.h 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; /* pointer to elements */ 00020 int count; /* current number of elements in queue */ 00021 Id *alloc; /* this is whats actually allocated, elements > alloc if shifted */ 00022 int left; /* space left in alloc *after* elements+count */ 00023 } Queue; 00024 00025 00026 extern void queue_alloc_one(Queue *q); /* internal */ 00027 extern void queue_alloc_one_head(Queue *q); /* internal */ 00028 00029 /* clear queue */ 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 /* SATSOLVER_QUEUE_H */