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)31 static 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)39 static 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)45 static 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)62 static 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)67 static 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)72 static 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