1 /*
2 * This file is part of the Yices SMT Solver.
3 * Copyright (C) 2017 SRI International.
4 *
5 * Yices is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * Yices is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with Yices. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 /*
20 * VECTORS OF INTEGERS (RESIZABLE ARRAYS)
21 */
22
23
24 #include "utils/int_array_sort.h"
25 #include "utils/int_vectors.h"
26 #include "utils/memalloc.h"
27
28
29 /*
30 * Integer vectors
31 */
init_ivector(ivector_t * v,uint32_t n)32 void init_ivector(ivector_t *v, uint32_t n) {
33 if (n >= MAX_IVECTOR_SIZE) {
34 out_of_memory();
35 }
36 v->capacity = n;
37 v->size = 0;
38 v->data = NULL;
39 if (n > 0) {
40 v->data = (int32_t *) safe_malloc(n * sizeof(int32_t));
41 }
42 }
43
delete_ivector(ivector_t * v)44 void delete_ivector(ivector_t *v) {
45 safe_free(v->data);
46 v->data = NULL;
47 }
48
extend_ivector(ivector_t * v)49 void extend_ivector(ivector_t *v) {
50 uint32_t n;
51
52 n = v->capacity;
53 if (n == 0) {
54 n = DEF_IVECTOR_SIZE;
55 } else {
56 n ++;
57 n += n >> 1;
58 if (n >= MAX_IVECTOR_SIZE) {
59 out_of_memory();
60 }
61 }
62 v->data = (int32_t *) safe_realloc(v->data, n * sizeof(int32_t));
63 v->capacity = n;
64 }
65
resize_ivector(ivector_t * v,uint32_t n)66 void resize_ivector(ivector_t *v, uint32_t n) {
67 if (n > v->capacity) {
68 if (n >= MAX_IVECTOR_SIZE) {
69 out_of_memory();
70 }
71 v->data = (int32_t *) safe_realloc(v->data, n * sizeof(int32_t));
72 v->capacity = n;
73 }
74 }
75
76 // copy array a into v. n = size of a
ivector_copy(ivector_t * v,const int32_t * a,uint32_t n)77 void ivector_copy(ivector_t *v, const int32_t *a, uint32_t n) {
78 uint32_t i;
79
80 resize_ivector(v, n);
81 for (i=0; i<n; i++) {
82 v->data[i] = a[i];
83 }
84 v->size = n;
85 }
86
87
88 // add array a to v. n = size of a
ivector_add(ivector_t * v,const int32_t * a,uint32_t n)89 void ivector_add(ivector_t *v, const int32_t *a, uint32_t n) {
90 int32_t *b;
91 uint32_t i, m;
92
93 m = v->size;
94 resize_ivector(v, n + m);
95 b = v->data + m;
96 for (i=0; i<n; i++) {
97 b[i] = a[i];
98 }
99 v->size = n + m;
100 }
101
102
103 /*
104 * Swap v1 and v2
105 */
ivector_swap(ivector_t * v1,ivector_t * v2)106 void ivector_swap(ivector_t *v1, ivector_t *v2) {
107 ivector_t aux;
108
109 aux = *v1;
110 *v1 = *v2;
111 *v2 = aux;
112 }
113
114
115 /*
116 * Sort and remove duplicates
117 */
ivector_remove_duplicates(ivector_t * v)118 void ivector_remove_duplicates(ivector_t *v) {
119 uint32_t n, i, j;
120 int32_t x, y, *a;
121
122 n = v->size;
123 if (n >= 2) {
124 a = v->data;
125 int_array_sort(a, n);
126
127 x = a[0];
128 j = 1;
129 for (i=1; i<n; i++) {
130 y = a[i];
131 if (x != y) {
132 a[j] = y;
133 x = y;
134 j ++;
135 }
136 }
137 v->size = j;
138 }
139 }
140
141
142