174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1
|
/*
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
2
|
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
3
|
*
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
4
|
* Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
5
|
*
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
6
|
* Redistribution and use in source and binary forms, with or without
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
7
|
* modification, are permitted provided that the following conditions are met:
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
8
|
*
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
9
|
* 1. Redistributions of source code must retain the above copyright
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
10
|
* notice, this list of conditions and the following disclaimer.
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
11
|
*
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
12
|
* 2. Redistributions in binary form must reproduce the above copyright
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
13
|
* notice, this list of conditions and the following disclaimer in the
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
14
|
* documentation and/or other materials provided with the distribution.
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
15
|
*
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
16
|
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
17
|
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
18
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
19
|
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
20
|
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
21
|
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
22
|
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
23
|
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
24
|
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
25
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
26
|
* POSSIBILITY OF SUCH DAMAGE.
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
27
|
*/
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
28
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
29
|
#include "cx/array_list.h"
|
253
|
30
|
#include "cx/compare.h"
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
31
|
#include <assert.h>
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
32
|
#include <string.h>
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
33
|
|
253
|
34
|
// Default array reallocator
|
|
35
|
|
|
36
|
static void *cx_array_default_realloc(
|
|
37
|
void *array,
|
|
38
|
size_t capacity,
|
|
39
|
size_t elem_size,
|
|
40
|
__attribute__((__unused__)) struct cx_array_reallocator_s *alloc
|
|
41
|
) {
|
|
42
|
return realloc(array, capacity * elem_size);
|
|
43
|
}
|
|
44
|
|
|
45
|
struct cx_array_reallocator_s cx_array_default_reallocator_impl = {
|
|
46
|
cx_array_default_realloc, NULL, NULL, 0, 0
|
|
47
|
};
|
|
48
|
|
|
49
|
struct cx_array_reallocator_s *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
|
|
50
|
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
51
|
// LOW LEVEL ARRAY LIST FUNCTIONS
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
52
|
|
253
|
53
|
enum cx_array_result cx_array_copy(
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
54
|
void **target,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
55
|
size_t *size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
56
|
size_t *capacity,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
57
|
size_t index,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
58
|
void const *src,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
59
|
size_t elem_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
60
|
size_t elem_count,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
61
|
struct cx_array_reallocator_s *reallocator
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
62
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
63
|
// assert pointers
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
64
|
assert(target != NULL);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
65
|
assert(size != NULL);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
66
|
assert(src != NULL);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
67
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
68
|
// determine capacity
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
69
|
size_t cap = capacity == NULL ? *size : *capacity;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
70
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
71
|
// check if resize is required
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
72
|
size_t minsize = index + elem_count;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
73
|
size_t newsize = *size < minsize ? minsize : *size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
74
|
bool needrealloc = newsize > cap;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
75
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
76
|
// reallocate if possible
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
77
|
if (needrealloc) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
78
|
// a reallocator and a capacity variable must be available
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
79
|
if (reallocator == NULL || capacity == NULL) {
|
253
|
80
|
return CX_ARRAY_REALLOC_NOT_SUPPORTED;
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
81
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
82
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
83
|
// check, if we need to repair the src pointer
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
84
|
uintptr_t targetaddr = (uintptr_t) *target;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
85
|
uintptr_t srcaddr = (uintptr_t) src;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
86
|
bool repairsrc = targetaddr <= srcaddr
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
87
|
&& srcaddr < targetaddr + cap * elem_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
88
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
89
|
// calculate new capacity (next number divisible by 16)
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
90
|
cap = newsize - (newsize % 16) + 16;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
91
|
assert(cap > newsize);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
92
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
93
|
// perform reallocation
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
94
|
void *newmem = reallocator->realloc(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
95
|
*target, cap, elem_size, reallocator
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
96
|
);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
97
|
if (newmem == NULL) {
|
253
|
98
|
return CX_ARRAY_REALLOC_FAILED;
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
99
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
100
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
101
|
// repair src pointer, if necessary
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
102
|
if (repairsrc) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
103
|
src = ((char *) newmem) + (srcaddr - targetaddr);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
104
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
105
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
106
|
// store new pointer and capacity
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
107
|
*target = newmem;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
108
|
*capacity = cap;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
109
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
110
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
111
|
// determine target pointer
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
112
|
char *start = *target;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
113
|
start += index * elem_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
114
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
115
|
// copy elements and set new size
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
116
|
memmove(start, src, elem_count * elem_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
117
|
*size = newsize;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
118
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
119
|
// return successfully
|
253
|
120
|
return CX_ARRAY_SUCCESS;
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
121
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
122
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
123
|
#ifndef CX_ARRAY_SWAP_SBO_SIZE
|
187
|
124
|
#define CX_ARRAY_SWAP_SBO_SIZE 128
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
125
|
#endif
|
253
|
126
|
unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
127
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
128
|
void cx_array_swap(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
129
|
void *arr,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
130
|
size_t elem_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
131
|
size_t idx1,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
132
|
size_t idx2
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
133
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
134
|
assert(arr != NULL);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
135
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
136
|
// short circuit
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
137
|
if (idx1 == idx2) return;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
138
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
139
|
char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
140
|
void *tmp;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
141
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
142
|
// decide if we can use the local buffer
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
143
|
if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
144
|
tmp = malloc(elem_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
145
|
// we don't want to enforce error handling
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
146
|
if (tmp == NULL) abort();
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
147
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
148
|
tmp = sbo_mem;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
149
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
150
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
151
|
// calculate memory locations
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
152
|
char *left = arr, *right = arr;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
153
|
left += idx1 * elem_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
154
|
right += idx2 * elem_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
155
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
156
|
// three-way swap
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
157
|
memcpy(tmp, left, elem_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
158
|
memcpy(left, right, elem_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
159
|
memcpy(right, tmp, elem_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
160
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
161
|
// free dynamic memory, if it was needed
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
162
|
if (tmp != sbo_mem) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
163
|
free(tmp);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
164
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
165
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
166
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
167
|
// HIGH LEVEL ARRAY LIST FUNCTIONS
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
168
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
169
|
typedef struct {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
170
|
struct cx_list_s base;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
171
|
void *data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
172
|
size_t capacity;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
173
|
struct cx_array_reallocator_s reallocator;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
174
|
} cx_array_list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
175
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
176
|
static void *cx_arl_realloc(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
177
|
void *array,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
178
|
size_t capacity,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
179
|
size_t elem_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
180
|
struct cx_array_reallocator_s *alloc
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
181
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
182
|
// retrieve the pointer to the list allocator
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
183
|
CxAllocator const *al = alloc->ptr1;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
184
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
185
|
// use the list allocator to reallocate the memory
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
186
|
return cxRealloc(al, array, capacity * elem_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
187
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
188
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
189
|
static void cx_arl_destructor(struct cx_list_s *list) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
190
|
cx_array_list *arl = (cx_array_list *) list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
191
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
192
|
char *ptr = arl->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
193
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
194
|
if (list->simple_destructor) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
195
|
for (size_t i = 0; i < list->size; i++) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
196
|
cx_invoke_simple_destructor(list, ptr);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
197
|
ptr += list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
198
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
199
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
200
|
if (list->advanced_destructor) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
201
|
for (size_t i = 0; i < list->size; i++) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
202
|
cx_invoke_advanced_destructor(list, ptr);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
203
|
ptr += list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
204
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
205
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
206
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
207
|
cxFree(list->allocator, arl->data);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
208
|
cxFree(list->allocator, list);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
209
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
210
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
211
|
static size_t cx_arl_insert_array(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
212
|
struct cx_list_s *list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
213
|
size_t index,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
214
|
void const *array,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
215
|
size_t n
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
216
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
217
|
// out of bounds and special case check
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
218
|
if (index > list->size || n == 0) return 0;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
219
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
220
|
// get a correctly typed pointer to the list
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
221
|
cx_array_list *arl = (cx_array_list *) list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
222
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
223
|
// do we need to move some elements?
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
224
|
if (index < list->size) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
225
|
char const *first_to_move = (char const *) arl->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
226
|
first_to_move += index * list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
227
|
size_t elems_to_move = list->size - index;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
228
|
size_t start_of_moved = index + n;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
229
|
|
253
|
230
|
if (CX_ARRAY_SUCCESS != cx_array_copy(
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
231
|
&arl->data,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
232
|
&list->size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
233
|
&arl->capacity,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
234
|
start_of_moved,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
235
|
first_to_move,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
236
|
list->item_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
237
|
elems_to_move,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
238
|
&arl->reallocator
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
239
|
)) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
240
|
// if moving existing elems is unsuccessful, abort
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
241
|
return 0;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
242
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
243
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
244
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
245
|
// note that if we had to move the elements, the following operation
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
246
|
// is guaranteed to succeed, because we have the memory already allocated
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
247
|
// therefore, it is impossible to leave this function with an invalid array
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
248
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
249
|
// place the new elements
|
253
|
250
|
if (CX_ARRAY_SUCCESS == cx_array_copy(
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
251
|
&arl->data,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
252
|
&list->size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
253
|
&arl->capacity,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
254
|
index,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
255
|
array,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
256
|
list->item_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
257
|
n,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
258
|
&arl->reallocator
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
259
|
)) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
260
|
return n;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
261
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
262
|
// array list implementation is "all or nothing"
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
263
|
return 0;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
264
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
265
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
266
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
267
|
static int cx_arl_insert_element(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
268
|
struct cx_list_s *list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
269
|
size_t index,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
270
|
void const *element
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
271
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
272
|
return 1 != cx_arl_insert_array(list, index, element, 1);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
273
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
274
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
275
|
static int cx_arl_insert_iter(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
276
|
struct cx_mut_iterator_s *iter,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
277
|
void const *elem,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
278
|
int prepend
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
279
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
280
|
struct cx_list_s *list = iter->src_handle;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
281
|
if (iter->index < list->size) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
282
|
int result = cx_arl_insert_element(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
283
|
list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
284
|
iter->index + 1 - prepend,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
285
|
elem
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
286
|
);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
287
|
if (result == 0 && prepend != 0) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
288
|
iter->index++;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
289
|
iter->elem_handle = ((char *) iter->elem_handle) + list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
290
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
291
|
return result;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
292
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
293
|
int result = cx_arl_insert_element(list, list->size, elem);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
294
|
iter->index = list->size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
295
|
return result;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
296
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
297
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
298
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
299
|
static int cx_arl_remove(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
300
|
struct cx_list_s *list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
301
|
size_t index
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
302
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
303
|
cx_array_list *arl = (cx_array_list *) list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
304
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
305
|
// out-of-bounds check
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
306
|
if (index >= list->size) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
307
|
return 1;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
308
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
309
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
310
|
// content destruction
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
311
|
cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
312
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
313
|
// short-circuit removal of last element
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
314
|
if (index == list->size - 1) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
315
|
list->size--;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
316
|
return 0;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
317
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
318
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
319
|
// just move the elements starting at index to the left
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
320
|
int result = cx_array_copy(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
321
|
&arl->data,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
322
|
&list->size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
323
|
&arl->capacity,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
324
|
index,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
325
|
((char *) arl->data) + (index + 1) * list->item_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
326
|
list->item_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
327
|
list->size - index - 1,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
328
|
&arl->reallocator
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
329
|
);
|
253
|
330
|
|
|
331
|
// cx_array_copy cannot fail, array cannot grow
|
|
332
|
assert(result == 0);
|
|
333
|
|
|
334
|
// decrease the size
|
|
335
|
list->size--;
|
|
336
|
|
|
337
|
return 0;
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
338
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
339
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
340
|
static void cx_arl_clear(struct cx_list_s *list) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
341
|
if (list->size == 0) return;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
342
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
343
|
cx_array_list *arl = (cx_array_list *) list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
344
|
char *ptr = arl->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
345
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
346
|
if (list->simple_destructor) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
347
|
for (size_t i = 0; i < list->size; i++) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
348
|
cx_invoke_simple_destructor(list, ptr);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
349
|
ptr += list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
350
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
351
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
352
|
if (list->advanced_destructor) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
353
|
for (size_t i = 0; i < list->size; i++) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
354
|
cx_invoke_advanced_destructor(list, ptr);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
355
|
ptr += list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
356
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
357
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
358
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
359
|
memset(arl->data, 0, list->size * list->item_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
360
|
list->size = 0;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
361
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
362
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
363
|
static int cx_arl_swap(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
364
|
struct cx_list_s *list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
365
|
size_t i,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
366
|
size_t j
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
367
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
368
|
if (i >= list->size || j >= list->size) return 1;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
369
|
cx_array_list *arl = (cx_array_list *) list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
370
|
cx_array_swap(arl->data, list->item_size, i, j);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
371
|
return 0;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
372
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
373
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
374
|
static void *cx_arl_at(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
375
|
struct cx_list_s const *list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
376
|
size_t index
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
377
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
378
|
if (index < list->size) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
379
|
cx_array_list const *arl = (cx_array_list const *) list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
380
|
char *space = arl->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
381
|
return space + index * list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
382
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
383
|
return NULL;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
384
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
385
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
386
|
|
253
|
387
|
static ssize_t cx_arl_find_remove(
|
|
388
|
struct cx_list_s *list,
|
|
389
|
void const *elem,
|
|
390
|
bool remove
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
391
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
392
|
assert(list->cmpfunc != NULL);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
393
|
assert(list->size < SIZE_MAX / 2);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
394
|
char *cur = ((cx_array_list const *) list)->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
395
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
396
|
for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
397
|
if (0 == list->cmpfunc(elem, cur)) {
|
253
|
398
|
if (remove) {
|
|
399
|
if (0 == cx_arl_remove(list, i)) {
|
|
400
|
return i;
|
|
401
|
} else {
|
|
402
|
return -1;
|
|
403
|
}
|
|
404
|
} else {
|
|
405
|
return i;
|
|
406
|
}
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
407
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
408
|
cur += list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
409
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
410
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
411
|
return -1;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
412
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
413
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
414
|
static void cx_arl_sort(struct cx_list_s *list) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
415
|
assert(list->cmpfunc != NULL);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
416
|
qsort(((cx_array_list *) list)->data,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
417
|
list->size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
418
|
list->item_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
419
|
list->cmpfunc
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
420
|
);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
421
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
422
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
423
|
static int cx_arl_compare(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
424
|
struct cx_list_s const *list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
425
|
struct cx_list_s const *other
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
426
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
427
|
assert(list->cmpfunc != NULL);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
428
|
if (list->size == other->size) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
429
|
char const *left = ((cx_array_list const *) list)->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
430
|
char const *right = ((cx_array_list const *) other)->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
431
|
for (size_t i = 0; i < list->size; i++) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
432
|
int d = list->cmpfunc(left, right);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
433
|
if (d != 0) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
434
|
return d;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
435
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
436
|
left += list->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
437
|
right += other->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
438
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
439
|
return 0;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
440
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
441
|
return list->size < other->size ? -1 : 1;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
442
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
443
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
444
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
445
|
static void cx_arl_reverse(struct cx_list_s *list) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
446
|
if (list->size < 2) return;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
447
|
void *data = ((cx_array_list const *) list)->data;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
448
|
size_t half = list->size / 2;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
449
|
for (size_t i = 0; i < half; i++) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
450
|
cx_array_swap(data, list->item_size, i, list->size - 1 - i);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
451
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
452
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
453
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
454
|
static bool cx_arl_iter_valid(void const *it) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
455
|
struct cx_iterator_s const *iter = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
456
|
struct cx_list_s const *list = iter->src_handle;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
457
|
return iter->index < list->size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
458
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
459
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
460
|
static void *cx_arl_iter_current(void const *it) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
461
|
struct cx_iterator_s const *iter = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
462
|
return iter->elem_handle;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
463
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
464
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
465
|
static void cx_arl_iter_next(void *it) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
466
|
struct cx_iterator_base_s *itbase = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
467
|
if (itbase->remove) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
468
|
struct cx_mut_iterator_s *iter = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
469
|
itbase->remove = false;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
470
|
cx_arl_remove(iter->src_handle, iter->index);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
471
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
472
|
struct cx_iterator_s *iter = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
473
|
iter->index++;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
474
|
iter->elem_handle =
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
475
|
((char *) iter->elem_handle)
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
476
|
+ ((struct cx_list_s const *) iter->src_handle)->item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
477
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
478
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
479
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
480
|
static void cx_arl_iter_prev(void *it) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
481
|
struct cx_iterator_base_s *itbase = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
482
|
struct cx_mut_iterator_s *iter = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
483
|
cx_array_list *const list = iter->src_handle;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
484
|
if (itbase->remove) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
485
|
itbase->remove = false;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
486
|
cx_arl_remove(iter->src_handle, iter->index);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
487
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
488
|
iter->index--;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
489
|
if (iter->index < list->base.size) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
490
|
iter->elem_handle = ((char *) list->data)
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
491
|
+ iter->index * list->base.item_size;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
492
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
493
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
494
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
495
|
static bool cx_arl_iter_flag_rm(void *it) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
496
|
struct cx_iterator_base_s *iter = it;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
497
|
if (iter->mutating) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
498
|
iter->remove = true;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
499
|
return true;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
500
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
501
|
return false;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
502
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
503
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
504
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
505
|
static struct cx_iterator_s cx_arl_iterator(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
506
|
struct cx_list_s const *list,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
507
|
size_t index,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
508
|
bool backwards
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
509
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
510
|
struct cx_iterator_s iter;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
511
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
512
|
iter.index = index;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
513
|
iter.src_handle = list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
514
|
iter.elem_handle = cx_arl_at(list, index);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
515
|
iter.base.valid = cx_arl_iter_valid;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
516
|
iter.base.current = cx_arl_iter_current;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
517
|
iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
518
|
iter.base.flag_removal = cx_arl_iter_flag_rm;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
519
|
iter.base.remove = false;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
520
|
iter.base.mutating = false;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
521
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
522
|
return iter;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
523
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
524
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
525
|
static cx_list_class cx_array_list_class = {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
526
|
cx_arl_destructor,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
527
|
cx_arl_insert_element,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
528
|
cx_arl_insert_array,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
529
|
cx_arl_insert_iter,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
530
|
cx_arl_remove,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
531
|
cx_arl_clear,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
532
|
cx_arl_swap,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
533
|
cx_arl_at,
|
253
|
534
|
cx_arl_find_remove,
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
535
|
cx_arl_sort,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
536
|
cx_arl_compare,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
537
|
cx_arl_reverse,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
538
|
cx_arl_iterator,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
539
|
};
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
540
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
541
|
CxList *cxArrayListCreate(
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
542
|
CxAllocator const *allocator,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
543
|
cx_compare_func comparator,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
544
|
size_t item_size,
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
545
|
size_t initial_capacity
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
546
|
) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
547
|
if (allocator == NULL) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
548
|
allocator = cxDefaultAllocator;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
549
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
550
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
551
|
cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
552
|
if (list == NULL) return NULL;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
553
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
554
|
list->base.cl = &cx_array_list_class;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
555
|
list->base.allocator = allocator;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
556
|
list->capacity = initial_capacity;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
557
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
558
|
if (item_size > 0) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
559
|
list->base.item_size = item_size;
|
253
|
560
|
list->base.cmpfunc = comparator;
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
561
|
} else {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
562
|
item_size = sizeof(void *);
|
253
|
563
|
list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
|
174
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
564
|
cxListStorePointers((CxList *) list);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
565
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
566
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
567
|
// allocate the array after the real item_size is known
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
568
|
list->data = cxCalloc(allocator, initial_capacity, item_size);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
569
|
if (list->data == NULL) {
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
570
|
cxFree(allocator, list);
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
571
|
return NULL;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
572
|
}
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
573
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
574
|
// configure the reallocator
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
575
|
list->reallocator.realloc = cx_arl_realloc;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
576
|
list->reallocator.ptr1 = (void *) allocator;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
577
|
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
578
|
return (CxList *) list;
|
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
579
|
}
|