Mercurial > hg > ucx / file comparison

comparison: src/array.c

src/array.c

branch
feature/array
changeset 336
6d7aa8a1a3b3
parent 334
bc81faa9afda
child 337
f695ae118460
equal deleted inserted replaced
335:872ae61c8945 336:6d7aa8a1a3b3
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "ucx/array.h" 29 #include "ucx/array.h"
30 30 #include "ucx/utils.h"
31
32 #include <string.h>
31 33
32 UcxArray ucx_array_new(size_t capacity, size_t elemsize) { 34 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
33 return ucx_array_new_a(capacity, elemsize, ucx_default_allocator()); 35 return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
34 } 36 }
35 37
36 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, 38 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,
37 UcxAllocator* allocator) { 39 UcxAllocator* allocator) {
38 UcxArray array; 40 UcxArray array;
39 41
42 array.allocator = allocator;
43 array.elemsize = elemsize;
44 array.size = 0;
45 array.data = alcalloc(allocator, capacity, elemsize);
46
47 if (array.data) {
48 array.capacity = capacity;
49 } else {
50 array.capacity = 0;
51 }
52
40 return array; 53 return array;
41 } 54 }
42 55
43 UcxArray ucx_array_clone(UcxArray array) { 56 UcxArray ucx_array_clone(UcxArray array) {
44 UcxArray clone; 57 UcxArray clone;
45 58
59 clone.allocator = array.allocator;
60 clone.elemsize = array.elemsize;
61 clone.size = array.size;
62 clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);
63
64 if (clone.data) {
65 clone.capacity = array.capacity;
66 memcpy(clone.data, array.data, array.size*array.elemsize);
67 } else {
68 clone.capacity = clone.size = 0;
69 }
70
46 return clone; 71 return clone;
47 } 72 }
48 73
49 int ucx_array_equals(UcxArray array1, UcxArray array2, 74 int ucx_array_equals(UcxArray array1, UcxArray array2,
50 cmp_func cmpfnc, void* data) { 75 cmp_func cmpfnc, void* data) {
51 76
52 return 1; 77 if (array1.size != array2.size || array1.elemsize != array2.elemsize) {
78 return 0;
79 } else {
80 if (array1.size == 0)
81 return 1;
82
83 if (cmpfnc == NULL) {
84 cmpfnc = ucx_cmp_mem;
85 data = &array1.elemsize;
86 }
87
88 for (size_t i = 0 ; i < array1.size ; i++) {
89 int r = cmpfnc(
90 ucx_array_at(array1, i),
91 ucx_array_at(array2, i),
92 data);
93 if (r != 0)
94 return 0;
95 }
96 return 1;
97 }
53 } 98 }
54 99
55 void ucx_array_free(UcxArray *array) { 100 void ucx_array_free(UcxArray *array) {
56 101 alfree(array->allocator, array->data);
102 array->data = NULL;
103 array->capacity = array->size = 0;
57 } 104 }
58 105
59 int ucx_array_append(UcxArray *array, void *data) { 106 int ucx_array_append(UcxArray *array, void *data) {
60 return 1; 107 if (array->size == array->capacity) {
108 if (ucx_array_reserve(array, array->capacity*2)) {
109 return 1;
110 }
111 }
112
113 void* dest = ucx_array_at(*array, array->size++);
114 if (data) {
115 memcpy(dest, data, array->elemsize);
116 } else {
117 memset(dest, 0, array->elemsize);
118 }
119
120 return 0;
61 } 121 }
62 122
63 int ucx_array_prepend(UcxArray *array, void *data) { 123 int ucx_array_prepend(UcxArray *array, void *data) {
64 return 1; 124 if (array->size == array->capacity) {
125 if (ucx_array_reserve(array, array->capacity*2)) {
126 return 1;
127 }
128 }
129
130 array->size++;
131
132 if (array->size > 1) {
133 void *dest = ucx_array_at(*array,1);
134 memmove(dest, array->data, array->elemsize*array->size);
135 }
136
137 if (data) {
138 memcpy(array->data, data, array->elemsize);
139 } else {
140 memset(array->data, 0, array->elemsize);
141 }
142
143 return 0;
65 } 144 }
66 145
67 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) { 146 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
68 return 1; 147
148 if (array1->elemsize != array2->elemsize)
149 return 1;
150
151 size_t capacity = array1->capacity+array2->capacity;
152
153 if (array1->capacity < capacity) {
154 if (ucx_array_reserve(array1, capacity)) {
155 return 1;
156 }
157 }
158
159 void* dest = ucx_array_at(*array1, array1->size);
160 memcpy(dest, array2->data, array2->size*array2->elemsize);
161
162 array1->size += array2->size;
163
164 return 0;
69 } 165 }
70 166
71 void *ucx_array_at(UcxArray array, size_t index) { 167 void *ucx_array_at(UcxArray array, size_t index) {
72 return NULL; 168 char* memory = array.data;
169 char* loc = memory + index*array.elemsize;
170 return loc;
73 } 171 }
74 172
75 size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { 173 size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
76 174
77 return 0; 175 if (cmpfnc == NULL) {
176 cmpfnc = ucx_cmp_mem;
177 data = &array.elemsize;
178 }
179
180 if (array.size > 0) {
181 for (size_t i = 0 ; i < array.size ; i++) {
182 void* ptr = ucx_array_at(array, i);
183 if (cmpfnc(ptr, elem, data) == 0) {
184 return i;
185 }
186 }
187 return array.size;
188 } else {
189 return 0;
190 }
78 } 191 }
79 192
80 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { 193 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
81 return ucx_array_find(array, elem, cmpfnc, data) != array.size; 194 return ucx_array_find(array, elem, cmpfnc, data) != array.size;
82 } 195 }
83 196
84 int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { 197 static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data,
85 return 1; 198 size_t start, size_t mid, size_t end) {
199
200 size_t rightstart = mid + 1;
201
202 if (cmpfnc(ucx_array_at(*array, mid),
203 ucx_array_at(*array, rightstart), data) <= 0) {
204 /* already sorted */
205 return;
206 }
207
208 // we need memory for one element
209 void *value = malloc(array->elemsize);
210
211 while (start <= mid && rightstart <= end) {
212 if (cmpfnc(ucx_array_at(*array, start),
213 ucx_array_at(*array, rightstart), data) <= 0) {
214 start++;
215 } else {
216 // save the value from the right
217 memcpy(value, ucx_array_at(*array, rightstart), array->elemsize);
218
219 // shift all left elements one element to the right
220 size_t shiftcount = rightstart-start;
221 void *startptr = ucx_array_at(*array, start);
222 void *dest = ucx_array_at(*array, start+1);
223 memmove(dest, startptr, shiftcount*array->elemsize);
224
225 // bring the first value from the right to the left
226 memcpy(startptr, value, array->elemsize);
227
228 start++;
229 mid++;
230 rightstart++;
231 }
232 }
233
234 // free the temporary memory
235 free(value);
236 }
237
238 static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data,
239 size_t l, size_t r) {
240 if (l < r) {
241 size_t m = l + (r - l) / 2;
242
243 ucx_array_mergesort(array, cmpfnc, data, l, m);
244 ucx_array_mergesort(array, cmpfnc, data, m + 1, r);
245 ucx_array_merge(array, cmpfnc, data, l, m, r);
246 }
247 }
248
249 void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
250 ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1);
86 } 251 }
87 252
88 void ucx_array_remove(UcxArray *array, size_t index) { 253 void ucx_array_remove(UcxArray *array, size_t index) {
89 254 array->size--;
255 if (index < array->size) {
256 void* dest = ucx_array_at(*array, index);
257 void* src = ucx_array_at(*array, index+1);
258 memmove(dest, src, (array->size - index)*array->elemsize);
259 }
90 } 260 }
91 261
92 void ucx_array_remove_fast(UcxArray *array, size_t index) { 262 void ucx_array_remove_fast(UcxArray *array, size_t index) {
93 263 array->size--;
264 if (index < array->size) {
265 void* dest = ucx_array_at(*array, index);
266 void* src = ucx_array_at(*array, array->size);
267 memcpy(dest, src, array->elemsize);
268 }
94 } 269 }
95 270
96 int ucx_array_shrink(UcxArray* array) { 271 int ucx_array_shrink(UcxArray* array) {
97 return 1; 272 void* newptr = alrealloc(array->allocator, array->data,
273 array->size*array->elemsize);
274 if (newptr) {
275 array->data = newptr;
276 array->capacity = array->size;
277 return 0;
278 } else {
279 return 1;
280 }
98 } 281 }
99 282
100 int ucx_array_resize(UcxArray* array, size_t capacity) { 283 int ucx_array_resize(UcxArray* array, size_t capacity) {
101 return 1; 284 if (array->capacity >= capacity) {
285 void* newptr = alrealloc(array->allocator, array->data,
286 capacity*array->elemsize);
287 if (newptr) {
288 array->data = newptr;
289 array->capacity = capacity;
290 if (array->size > array->capacity) {
291 array->size = array->capacity;
292 }
293 return 0;
294 } else {
295 return 1;
296 }
297 } else {
298 return ucx_array_reserve(array, capacity);
299 }
102 } 300 }
103 301
104 int ucx_array_reserve(UcxArray* array, size_t capacity) { 302 int ucx_array_reserve(UcxArray* array, size_t capacity) {
105 return 1; 303 if (array->capacity > capacity) {
106 } 304 return 0;
107 305 } else {
306 void* newptr = alrealloc(array->allocator, array->data,
307 capacity*array->elemsize);
308 if (newptr) {
309 array->data = newptr;
310 array->capacity = capacity;
311 return 0;
312 } else {
313 return 1;
314 }
315 }
316 }

Mercurial Repository: ucx

mercurial