1 //===--- vec_uint.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__vec__vec_uint_h
10 #define satoko__utils__vec__vec_uint_h
11
12 #include <assert.h>
13 #include <stdio.h>
14 #include <string.h>
15
16 #include "../mem.h"
17
18 #include "misc/util/abc_global.h"
19 ABC_NAMESPACE_HEADER_START
20
21 typedef struct vec_uint_t_ vec_uint_t;
22 struct vec_uint_t_ {
23 unsigned cap;
24 unsigned size;
25 unsigned* data;
26 };
27
28 //===------------------------------------------------------------------------===
29 // Vector Macros
30 //===------------------------------------------------------------------------===
31 #define vec_uint_foreach(vec, entry, i) \
32 for (i = 0; (i < vec_uint_size(vec)) && (((entry) = vec_uint_at(vec, i)), 1); i++)
33
34 #define vec_uint_foreach_start(vec, entry, i, start) \
35 for (i = start; (i < vec_uint_size(vec)) && (((entry) = vec_uint_at(vec, i)), 1); i++)
36
37 #define vec_uint_foreach_stop(vec, entry, i, stop) \
38 for (i = 0; (i < stop) && (((entry) = vec_uint_at(vec, i)), 1); i++)
39
40 //===------------------------------------------------------------------------===
41 // Vector API
42 //===------------------------------------------------------------------------===
vec_uint_alloc(unsigned cap)43 static inline vec_uint_t * vec_uint_alloc(unsigned cap)
44 {
45 vec_uint_t *p = satoko_alloc(vec_uint_t, 1);
46
47 if (cap > 0 && cap < 16)
48 cap = 16;
49 p->size = 0;
50 p->cap = cap;
51 p->data = p->cap ? satoko_alloc(unsigned, p->cap) : NULL;
52 return p;
53 }
54
vec_uint_alloc_exact(unsigned cap)55 static inline vec_uint_t * vec_uint_alloc_exact(unsigned cap)
56 {
57 vec_uint_t *p = satoko_alloc(vec_uint_t, 1);
58
59 cap = 0;
60 p->size = 0;
61 p->cap = cap;
62 p->data = p->cap ? satoko_alloc(unsigned, p->cap ) : NULL;
63 return p;
64 }
65
vec_uint_init(unsigned size,unsigned value)66 static inline vec_uint_t * vec_uint_init(unsigned size, unsigned value)
67 {
68 vec_uint_t *p = satoko_alloc(vec_uint_t, 1);
69
70 p->cap = size;
71 p->size = size;
72 p->data = p->cap ? satoko_alloc(unsigned, p->cap ) : NULL;
73 memset(p->data, value, sizeof(unsigned) * p->size);
74 return p;
75 }
76
vec_uint_free(vec_uint_t * p)77 static inline void vec_uint_free(vec_uint_t *p)
78 {
79 if (p->data != NULL)
80 satoko_free(p->data);
81 satoko_free(p);
82 }
83
vec_uint_size(vec_uint_t * p)84 static inline unsigned vec_uint_size(vec_uint_t *p)
85 {
86 return p->size;
87 }
88
vec_uint_resize(vec_uint_t * p,unsigned new_size)89 static inline void vec_uint_resize(vec_uint_t *p, unsigned new_size)
90 {
91 p->size = new_size;
92 if (p->cap >= new_size)
93 return;
94 p->data = satoko_realloc(unsigned, p->data, new_size);
95 assert(p->data != NULL);
96 p->cap = new_size;
97 }
98
vec_uint_shrink(vec_uint_t * p,unsigned new_size)99 static inline void vec_uint_shrink(vec_uint_t *p, unsigned new_size)
100 {
101 assert(p->cap >= new_size);
102 p->size = new_size;
103 }
104
vec_uint_reserve(vec_uint_t * p,unsigned new_cap)105 static inline void vec_uint_reserve(vec_uint_t *p, unsigned new_cap)
106 {
107 if (p->cap >= new_cap)
108 return;
109 p->data = satoko_realloc(unsigned, p->data, new_cap);
110 assert(p->data != NULL);
111 p->cap = new_cap;
112 }
113
vec_uint_capacity(vec_uint_t * p)114 static inline unsigned vec_uint_capacity(vec_uint_t *p)
115 {
116 return p->cap;
117 }
118
vec_uint_empty(vec_uint_t * p)119 static inline int vec_uint_empty(vec_uint_t *p)
120 {
121 return p->size ? 0 : 1;
122 }
123
vec_uint_erase(vec_uint_t * p)124 static inline void vec_uint_erase(vec_uint_t *p)
125 {
126 satoko_free(p->data);
127 p->size = 0;
128 p->cap = 0;
129 }
130
vec_uint_at(vec_uint_t * p,unsigned idx)131 static inline unsigned vec_uint_at(vec_uint_t *p, unsigned idx)
132 {
133 assert(idx >= 0 && idx < p->size);
134 return p->data[idx];
135 }
136
vec_uint_at_ptr(vec_uint_t * p,unsigned idx)137 static inline unsigned * vec_uint_at_ptr(vec_uint_t *p, unsigned idx)
138 {
139 assert(idx >= 0 && idx < p->size);
140 return p->data + idx;
141 }
142
vec_uint_find(vec_uint_t * p,unsigned entry)143 static inline unsigned vec_uint_find(vec_uint_t *p, unsigned entry)
144 {
145 unsigned i;
146 for (i = 0; i < p->size; i++)
147 if (p->data[i] == entry)
148 return 1;
149 return 0;
150 }
151
vec_uint_data(vec_uint_t * p)152 static inline unsigned * vec_uint_data(vec_uint_t *p)
153 {
154 assert(p);
155 return p->data;
156 }
157
vec_uint_duplicate(vec_uint_t * dest,const vec_uint_t * src)158 static inline void vec_uint_duplicate(vec_uint_t *dest, const vec_uint_t *src)
159 {
160 assert(dest != NULL && src != NULL);
161 vec_uint_resize(dest, src->cap);
162 memcpy(dest->data, src->data, sizeof(unsigned) * src->cap);
163 dest->size = src->size;
164 }
165
vec_uint_copy(vec_uint_t * dest,const vec_uint_t * src)166 static inline void vec_uint_copy(vec_uint_t *dest, const vec_uint_t *src)
167 {
168 assert(dest != NULL && src != NULL);
169 vec_uint_resize(dest, src->size);
170 memcpy(dest->data, src->data, sizeof(unsigned) * src->size);
171 dest->size = src->size;
172 }
173
vec_uint_push_back(vec_uint_t * p,unsigned value)174 static inline void vec_uint_push_back(vec_uint_t *p, unsigned value)
175 {
176 if (p->size == p->cap) {
177 if (p->cap < 16)
178 vec_uint_reserve(p, 16);
179 else
180 vec_uint_reserve(p, 2 * p->cap);
181 }
182 p->data[p->size] = value;
183 p->size++;
184 }
185
vec_uint_pop_back(vec_uint_t * p)186 static inline unsigned vec_uint_pop_back(vec_uint_t *p)
187 {
188 assert(p && p->size);
189 return p->data[--p->size];
190 }
191
vec_uint_assign(vec_uint_t * p,unsigned idx,unsigned value)192 static inline void vec_uint_assign(vec_uint_t *p, unsigned idx, unsigned value)
193 {
194 assert((idx >= 0) && (idx < vec_uint_size(p)));
195 p->data[idx] = value;
196 }
197
vec_uint_insert(vec_uint_t * p,unsigned idx,unsigned value)198 static inline void vec_uint_insert(vec_uint_t *p, unsigned idx, unsigned value)
199 {
200 assert((idx >= 0) && (idx < vec_uint_size(p)));
201 vec_uint_push_back(p, 0);
202 memmove(p->data + idx + 1, p->data + idx, (p->size - idx - 2) * sizeof(unsigned));
203 p->data[idx] = value;
204 }
205
vec_uint_drop(vec_uint_t * p,unsigned idx)206 static inline void vec_uint_drop(vec_uint_t *p, unsigned idx)
207 {
208 assert((idx >= 0) && (idx < vec_uint_size(p)));
209 memmove(p->data + idx, p->data + idx + 1, (p->size - idx - 1) * sizeof(unsigned));
210 p->size -= 1;
211 }
212
vec_uint_clear(vec_uint_t * p)213 static inline void vec_uint_clear(vec_uint_t *p)
214 {
215 p->size = 0;
216 }
217
vec_uint_asc_compare(const void * p1,const void * p2)218 static inline int vec_uint_asc_compare(const void *p1, const void *p2)
219 {
220 const unsigned *pp1 = (const unsigned *) p1;
221 const unsigned *pp2 = (const unsigned *) p2;
222
223 if ( *pp1 < *pp2 )
224 return -1;
225 if ( *pp1 > *pp2 )
226 return 1;
227 return 0;
228 }
229
vec_uint_desc_compare(const void * p1,const void * p2)230 static inline int vec_uint_desc_compare(const void *p1, const void *p2)
231 {
232 const unsigned *pp1 = (const unsigned *) p1;
233 const unsigned *pp2 = (const unsigned *) p2;
234
235 if ( *pp1 > *pp2 )
236 return -1;
237 if ( *pp1 < *pp2 )
238 return 1;
239 return 0;
240 }
241
vec_uint_sort(vec_uint_t * p,int ascending)242 static inline void vec_uint_sort(vec_uint_t *p, int ascending)
243 {
244 if (ascending)
245 qsort((void *) p->data, (size_t)p->size, sizeof(unsigned),
246 (int (*)(const void *, const void *)) vec_uint_asc_compare);
247 else
248 qsort((void*) p->data, (size_t)p->size, sizeof(unsigned),
249 (int (*)(const void *, const void *)) vec_uint_desc_compare);
250 }
251
vec_uint_memory(vec_uint_t * p)252 static inline long vec_uint_memory(vec_uint_t *p)
253 {
254 return p == NULL ? 0 : sizeof(unsigned) * p->cap + sizeof(vec_uint_t);
255 }
256
vec_uint_print(vec_uint_t * p)257 static inline void vec_uint_print(vec_uint_t* p)
258 {
259 unsigned i;
260 assert(p != NULL);
261 fprintf(stdout, "Vector has %u(%u) entries: {", p->size, p->cap);
262 for (i = 0; i < p->size; i++)
263 fprintf(stdout, " %u", p->data[i]);
264 fprintf(stdout, " }\n");
265 }
266
267 ABC_NAMESPACE_HEADER_END
268 #endif /* satoko__utils__vec__vec_uint_h */
269