1 /*
2 Copyright (c) 2013-2018, 2021 Cong Xu
3 All rights reserved.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
7
8 Redistributions of source code must retain the above copyright notice, this
9 list of conditions and the following disclaimer.
10 Redistributions in binary form must reproduce the above copyright notice,
11 this list of conditions and the following disclaimer in the documentation
12 and/or other materials provided with the distribution.
13
14 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
18 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 POSSIBILITY OF SUCH DAMAGE.
25 */
26 #include "c_array.h"
27
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31
32 #include "utils.h"
33
CArrayInit(CArray * a,const size_t elemSize)34 void CArrayInit(CArray *a, const size_t elemSize)
35 {
36 a->data = NULL;
37 a->elemSize = elemSize;
38 a->size = 0;
39 a->capacity = 0;
40 }
CArrayInitFill(CArray * a,const size_t elemSize,const size_t size,const void * value)41 void CArrayInitFill(
42 CArray *a, const size_t elemSize, const size_t size, const void *value)
43 {
44 CArrayInit(a, elemSize);
45 CArrayResize(a, size, value);
46 }
CArrayInitFillZero(CArray * a,const size_t elemSize,const size_t size)47 void CArrayInitFillZero(CArray *a, const size_t elemSize, const size_t size)
48 {
49 CArrayInitFill(a, elemSize, size, NULL);
50 CArrayFillZero(a);
51 }
CArrayReserve(CArray * a,size_t capacity)52 void CArrayReserve(CArray *a, size_t capacity)
53 {
54 if (a->capacity >= capacity)
55 {
56 return;
57 }
58 a->capacity = capacity;
59 const size_t size = a->capacity * a->elemSize;
60 if (size)
61 {
62 CREALLOC(a->data, size);
63 }
64 }
GrowIfFull(CArray * a)65 static void GrowIfFull(CArray *a)
66 {
67 if (a->size == a->capacity)
68 {
69 const size_t capacity = a->capacity == 0 ? 1 : a->capacity * 2;
70 CArrayReserve(a, capacity);
71 }
72 }
CArrayCopy(CArray * dst,const CArray * src)73 void CArrayCopy(CArray *dst, const CArray *src)
74 {
75 if (dst->elemSize > 0)
76 {
77 CArrayTerminate(dst);
78 }
79 CArrayInit(dst, src->elemSize);
80 CArrayResize(dst, src->size, NULL);
81 memcpy(dst->data, src->data, src->size * src->elemSize);
82 }
83
CArrayPushBack(CArray * a,const void * elem)84 void CArrayPushBack(CArray *a, const void *elem)
85 {
86 CASSERT(a->elemSize > 0, "array has not been initialised");
87 GrowIfFull(a);
88 a->size++;
89 memcpy(CArrayGet(a, (int)a->size - 1), elem, a->elemSize);
90 }
CArrayInsert(CArray * a,const size_t idx,const void * elem)91 void CArrayInsert(CArray *a, const size_t idx, const void *elem)
92 {
93 CASSERT(a->elemSize > 0, "array has not been initialised");
94 GrowIfFull(a);
95 a->size++;
96 if (idx + 1 < a->size)
97 {
98 memmove(
99 CArrayGet(a, idx + 1), CArrayGet(a, idx),
100 a->elemSize * (a->size - 1 - idx));
101 }
102 CArraySet(a, idx, elem);
103 }
CArrayDelete(CArray * a,const size_t idx)104 void CArrayDelete(CArray *a, const size_t idx)
105 {
106 CASSERT(a->size != 0, "Cannot delete from empty array");
107 CASSERT(a->elemSize > 0, "array has not been initialised");
108 CASSERT(idx < a->size, "array index out of bounds");
109 if (idx + 1 < a->size)
110 {
111 memmove(
112 CArrayGet(a, idx), CArrayGet(a, idx + 1),
113 a->elemSize * (a->size - 1 - idx));
114 }
115 a->size--;
116 }
CArrayPopBack(CArray * a)117 void CArrayPopBack(CArray *a)
118 {
119 CArrayDelete(a, a->size - 1);
120 }
CArrayResize(CArray * a,const size_t size,const void * value)121 void CArrayResize(CArray *a, const size_t size, const void *value)
122 {
123 CArrayReserve(a, size);
124 if (value != NULL)
125 {
126 while (a->size < size)
127 {
128 CArrayPushBack(a, value);
129 }
130 }
131 a->size = size;
132 }
133
CArrayGet(const CArray * a,const size_t idx)134 void *CArrayGet(const CArray *a, const size_t idx)
135 {
136 CASSERT(a->elemSize > 0, "array has not been initialised");
137 CASSERT(idx < a->size, "array index out of bounds");
138 return &((char *)a->data)[idx * a->elemSize];
139 }
CArraySet(CArray * a,const size_t idx,const void * elem)140 void CArraySet(CArray *a, const size_t idx, const void *elem)
141 {
142 memcpy(CArrayGet(a, idx), elem, a->elemSize);
143 }
144
CArrayClear(CArray * a)145 void CArrayClear(CArray *a)
146 {
147 a->size = 0;
148 }
149
CArrayRemoveIf(CArray * a,bool (* removeIf)(const void *))150 void CArrayRemoveIf(CArray *a, bool (*removeIf)(const void *))
151 {
152 // Note: this is the erase-remove idiom
153 // Check all elements to see if they need to be removed
154 // Move all the elements that don't need to be removed to the head
155 void *dst = a->data;
156 size_t shrunkSize = 0;
157 for (int i = 0; i < (int)a->size; i++)
158 {
159 const void *elem = CArrayGet(a, i);
160 if (!removeIf(elem))
161 {
162 memmove(dst, elem, a->elemSize);
163 dst = (char *)dst + a->elemSize;
164 shrunkSize++;
165 }
166 }
167
168 // Shrink the array to fit
169 a->size = shrunkSize;
170 }
171
172 // Fill all entries with the same element
CArrayFill(CArray * a,const void * elem)173 void CArrayFill(CArray *a, const void *elem)
174 {
175 CA_FOREACH(void, e, *a)
176 memcpy(e, elem, a->elemSize);
177 CA_FOREACH_END()
178 }
179
CArrayFillZero(CArray * a)180 void CArrayFillZero(CArray *a)
181 {
182 memset(a->data, 0, a->size * a->elemSize);
183 }
184
CArrayConcat(CArray * a,const CArray * a2)185 void CArrayConcat(CArray *a, const CArray *a2)
186 {
187 if (a->size == 0)
188 {
189 CArrayInit(a, a2->elemSize);
190 }
191 else
192 {
193 CASSERT(a->elemSize == a2->elemSize, "cannot concat arrays with different sized elements");
194 }
195 CArrayReserve(a, a->size + a2->size);
196 memcpy((char *)a->data + a->size * a->elemSize, a2->data, a2->elemSize * a2->size);
197 a->size += a2->size;
198 }
199
CArrayShuffle(CArray * a)200 void CArrayShuffle(CArray *a)
201 {
202 void *buf;
203 CMALLOC(buf, a->elemSize);
204 CA_FOREACH(void, e, *a)
205 const int j = rand() % (_ca_index + 1);
206 void *je = CArrayGet(a, j);
207 // Swap index and j elements
208 memcpy(buf, e, a->elemSize);
209 memcpy(e, je, a->elemSize);
210 memcpy(je, buf, a->elemSize);
211 CA_FOREACH_END()
212 CFREE(buf);
213 }
214
CArrayUnique(CArray * a,bool (* isEqual)(const void *,const void *))215 void CArrayUnique(CArray *a, bool (*isEqual)(const void *, const void *))
216 {
217 if (a->size == 0)
218 {
219 return;
220 }
221 void *dst = a->data;
222 size_t shrunkSize = 0;
223 CA_FOREACH(void, elem, *a)
224 if (!isEqual(dst, elem))
225 {
226 dst = (char *)dst + a->elemSize;
227 memmove(dst, elem, a->elemSize);
228 shrunkSize++;
229 }
230 CA_FOREACH_END()
231 shrunkSize++;
232
233 // Shrink the array to fit
234 a->size = shrunkSize;
235 }
236
CArrayTerminate(CArray * a)237 void CArrayTerminate(CArray *a)
238 {
239 if (!a)
240 {
241 return;
242 }
243 CFREE(a->data);
244 memset(a, 0, sizeof *a);
245 }
246