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 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 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 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 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 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 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 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 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