1 //===--- b_queue.h ----------------------------------------------------------=== 2 // 3 // satoko: Satisfiability solver 4 // 5 // This file is distributed under the BSD 2-Clause License. 6 // See LICENSE for details. 7 // 8 //===------------------------------------------------------------------------=== 9 #ifndef satoko__utils__b_queue_h 10 #define satoko__utils__b_queue_h 11 12 #include "mem.h" 13 14 #include "misc/util/abc_global.h" 15 ABC_NAMESPACE_HEADER_START 16 17 /* Bounded Queue */ 18 typedef struct b_queue_t_ b_queue_t; 19 struct b_queue_t_ { 20 unsigned size; 21 unsigned cap; 22 unsigned i_first; 23 unsigned i_empty; 24 unsigned long sum; 25 unsigned *data; 26 }; 27 28 //===------------------------------------------------------------------------=== 29 // Bounded Queue API 30 //===------------------------------------------------------------------------=== b_queue_alloc(unsigned cap)31static inline b_queue_t *b_queue_alloc(unsigned cap) 32 { 33 b_queue_t *p = satoko_calloc(b_queue_t, 1); 34 p->cap = cap; 35 p->data = satoko_calloc(unsigned, cap); 36 return p; 37 } 38 b_queue_free(b_queue_t * p)39static inline void b_queue_free(b_queue_t *p) 40 { 41 satoko_free(p->data); 42 satoko_free(p); 43 } 44 b_queue_push(b_queue_t * p,unsigned Value)45static inline void b_queue_push(b_queue_t *p, unsigned Value) 46 { 47 if (p->size == p->cap) { 48 assert(p->i_first == p->i_empty); 49 p->sum -= p->data[p->i_first]; 50 p->i_first = (p->i_first + 1) % p->cap; 51 } else 52 p->size++; 53 54 p->sum += Value; 55 p->data[p->i_empty] = Value; 56 if ((++p->i_empty) == p->cap) { 57 p->i_empty = 0; 58 p->i_first = 0; 59 } 60 } 61 b_queue_avg(b_queue_t * p)62static inline unsigned b_queue_avg(b_queue_t *p) 63 { 64 return (unsigned)(p->sum / ((unsigned long) p->size)); 65 } 66 b_queue_is_valid(b_queue_t * p)67static inline unsigned b_queue_is_valid(b_queue_t *p) 68 { 69 return (p->cap == p->size); 70 } 71 b_queue_clean(b_queue_t * p)72static inline void b_queue_clean(b_queue_t *p) 73 { 74 p->i_first = 0; 75 p->i_empty = 0; 76 p->size = 0; 77 p->sum = 0; 78 } 79 80 ABC_NAMESPACE_HEADER_END 81 #endif /* satoko__utils__b_queue_h */ 82