Line data Source code
1 : /***************************************************************************//**
2 :
3 : @file arraylist.c
4 :
5 : @author Stephen Brennan
6 :
7 : @date Created Friday, 27 September 2013
8 :
9 : @brief Implementation of "libstephen/al.h".
10 :
11 : @copyright Copyright (c) 2013-2016, Stephen Brennan. Released under the
12 : Revised BSD License. See the LICENSE.txt file for details.
13 :
14 : *******************************************************************************/
15 :
16 : #include <stdlib.h> /* memcpy */
17 :
18 : #include "libstephen/al.h"
19 :
20 : /**
21 : @brief The default size that an array list is allocated with, and is added to
22 : the capacity each time it expands.
23 : */
24 : #define SMB_AL_BLOCK_SIZE 20
25 :
26 : /*******************************************************************************
27 :
28 : Private Functions
29 :
30 : *******************************************************************************/
31 :
32 : /**
33 : @brief Expands the smb_al by adding anothur chunk of the default size.
34 :
35 : Note that this is a *private* function, not defined in libstephen.h for a
36 : reason.
37 :
38 : @param list The list to expand.
39 : @param[out] status Status variable.
40 : */
41 24520 : void al_expand(smb_al *list)
42 : {
43 24520 : list->allocated = list->allocated + SMB_AL_BLOCK_SIZE;
44 24520 : list->data = smb_renew(DATA, list->data, list->allocated);
45 24520 : }
46 :
47 : /**
48 : @brief Shifts the elements in the array up one element starting from
49 : from_index.
50 :
51 : Additionally, increments the list->length. Precondition is that from_index
52 : is within range. Since this is a private function, that is reasonable.
53 :
54 : Note that this is a *private* function, not defined in libstephen.h for a
55 : reason.
56 :
57 : @param list The list to operate on.
58 : @param from_index The index to start shifting up from.
59 : @param[out] status Status variable.
60 : */
61 210 : void al_shift_up(smb_al *list, int from_index)
62 : {
63 : // Check if there's space and allocate more if necessary
64 210 : if (list->length >= list->allocated) {
65 10 : al_expand(list);
66 : }
67 :
68 : // Starting at the last element in the array, shift up by one
69 20174 : for (int i = list->length - 1; i >= from_index; i--) {
70 19964 : list->data[i + 1] = list->data[i];
71 : }
72 :
73 210 : list->length++;
74 210 : }
75 :
76 : /**
77 : @brief Shifts the elements of the array down one element.
78 :
79 : The function shifts each element down in the list, until the element at the
80 : given index is eventually overwritten. Decrements the list->length.
81 : Precondition is that to_index is within range.
82 :
83 : Note that this is a *private* function, not defined in libstephen.h for a
84 : reason.
85 :
86 : @param list The list to operate on.
87 : @param to_index The index to shift down to. The element at this index is
88 : eventually overwritten.
89 : */
90 14 : void al_shift_down(smb_al *list, int to_index)
91 : {
92 51 : for (int i = to_index + 1; i < list->length; i++) {
93 37 : list->data[i - 1] = list->data[i];
94 : }
95 :
96 14 : list->length--;
97 14 : }
98 :
99 : /*******************************************************************************
100 :
101 : Public Functions
102 :
103 : *******************************************************************************/
104 :
105 1014 : void al_init(smb_al *list)
106 : {
107 1014 : list->data = smb_new(DATA, SMB_AL_BLOCK_SIZE);
108 1014 : list->length = 0;
109 1014 : list->allocated = SMB_AL_BLOCK_SIZE;
110 1014 : }
111 :
112 1014 : smb_al *al_create()
113 : {
114 1014 : smb_al *list = smb_new(smb_al, 1);
115 1014 : al_init(list);
116 1014 : return list;
117 : }
118 :
119 1014 : void al_destroy(smb_al *list)
120 : {
121 1014 : smb_free(list->data);
122 1014 : }
123 :
124 1014 : void al_delete(smb_al *list)
125 : {
126 1014 : al_destroy(list);
127 1014 : smb_free(list);
128 1014 : }
129 :
130 500817 : void al_append(smb_al *list, DATA newData)
131 : {
132 500817 : if (list->length < list->allocated) {
133 476307 : list->data[list->length++] = newData;
134 : } else {
135 24510 : al_expand(list);
136 24510 : list->data[list->length++] = newData;
137 : }
138 500817 : }
139 :
140 205 : void al_prepend(smb_al *list, DATA newData)
141 : {
142 205 : al_shift_up(list, 0);
143 205 : list->data[0] = newData;
144 205 : }
145 :
146 541863 : DATA al_get(const smb_al *list, int index, smb_status *status)
147 : {
148 541863 : *status = SMB_SUCCESS;
149 541863 : if (index < 0 || index >= list->length) {
150 1005 : *status = SMB_INDEX_ERROR;
151 1005 : DATA mockData = PTR(NULL);
152 1005 : return mockData;
153 : }
154 :
155 540858 : return list->data[index];
156 : }
157 :
158 18 : void al_remove(smb_al *list, int index, smb_status *status)
159 : {
160 18 : *status = SMB_SUCCESS;
161 18 : if (index < 0 || index >= list->length) {
162 4 : *status = SMB_INDEX_ERROR;
163 22 : return;
164 : }
165 :
166 14 : al_shift_down(list, index);
167 : }
168 :
169 5 : void al_insert(smb_al *list, int index, DATA newData)
170 : {
171 5 : if (index < 0) {
172 1 : index = 0;
173 4 : } else if (index > list->length) {
174 1 : index = list->length;
175 : }
176 :
177 5 : al_shift_up(list, index);
178 5 : list->data[index] = newData;
179 5 : }
180 :
181 31 : void al_set(smb_al *list, int index, DATA newData, smb_status *status)
182 : {
183 31 : *status = SMB_SUCCESS;
184 31 : if (index < 0 || index >= list->length) {
185 1 : *status = SMB_INDEX_ERROR;
186 32 : return;
187 : }
188 :
189 30 : list->data[index] = newData;
190 : }
191 :
192 25 : void al_push_back(smb_al *list, DATA newData)
193 : {
194 25 : al_append(list, newData);
195 25 : }
196 :
197 7 : DATA al_pop_back(smb_al *list, smb_status *status)
198 : {
199 : // On failure, returns dummy and sets INDEX_ERROR:
200 7 : DATA toReturn = al_get(list, list->length - 1, status);
201 : // On failure, sets INDEX_ERROR and does nothing:
202 7 : al_remove(list, list->length - 1, status);
203 7 : return toReturn;
204 : }
205 :
206 2 : DATA al_peek_back(smb_al *list, smb_status *status)
207 : {
208 2 : return al_get(list, list->length - 1, status);
209 : }
210 :
211 5 : void al_push_front(smb_al *list, DATA newData)
212 : {
213 5 : al_prepend(list, newData);
214 5 : }
215 :
216 6 : DATA al_pop_front(smb_al *list, smb_status *status)
217 : {
218 : // On failure, returns dummy and sets INDEX_ERROR.
219 6 : DATA toReturn = al_get(list, 0, status);
220 : // On failure, sets INDEX_ERROR and does nothing.
221 6 : al_remove(list, 0, status);
222 6 : return toReturn;
223 : }
224 :
225 2 : DATA al_peek_front(smb_al *list, smb_status *status)
226 : {
227 2 : return al_get(list, 0, status);
228 : }
229 :
230 542620 : int al_length(const smb_al *list)
231 : {
232 542620 : return list->length;
233 : }
234 :
235 22 : int al_index_of(const smb_al *list, DATA d, DATA_COMPARE comp)
236 : {
237 : int i;
238 212 : for (i = 0; i < list->length; i++) {
239 211 : if (comp == NULL) {
240 210 : if (list->data[i].data_llint == d.data_llint) {
241 20 : return i;
242 : }
243 : } else {
244 1 : if (comp(list->data[i], d) == 0) {
245 1 : return i;
246 : }
247 : }
248 : }
249 1 : return -1;
250 : }
251 :
252 : /**
253 : @brief Return the next item in the array list.
254 : @param iter The iterator being used.
255 : @param[out] status Status variable.
256 : @return The next item in the array list.
257 : @exception SMB_STOP_ITERATION If the list has no more elements.
258 : */
259 501500 : DATA al_iter_next(smb_iter *iter, smb_status *status)
260 : {
261 501500 : DATA ret_val = al_get((const smb_al *)iter->ds, iter->index++, status);
262 501500 : if (*status == SMB_INDEX_ERROR) {
263 1000 : *status = SMB_STOP_ITERATION;
264 : }
265 501500 : return ret_val;
266 : }
267 :
268 : /**
269 : @brief Return whether or not the iterator has another item.
270 : @param iter The iterator being used.
271 : @return Whether or not the iterator has another item.
272 : */
273 501502 : bool al_iter_has_next(smb_iter *iter)
274 : {
275 501502 : return iter->index < al_length((const smb_al *)iter->ds);
276 : }
277 :
278 : /**
279 : @brief Free whatever resources are held by the iterator.
280 : @param iter The iterator to clean up.
281 : */
282 1004 : void al_iter_destroy(smb_iter *iter)
283 : {
284 : (void)iter; // unused
285 1004 : }
286 :
287 : /**
288 : @brief Free the iterator and its resources.
289 : @param iter The iterator to free.
290 : */
291 1 : void al_iter_delete(smb_iter *iter)
292 : {
293 1 : iter->destroy(iter);
294 1 : smb_free(iter);
295 1 : }
296 :
297 1004 : smb_iter al_get_iter(const smb_al *list)
298 : {
299 1004 : smb_iter iter = {
300 : // Data values
301 : .ds = list,
302 : .state = (DATA) { .data_ptr = NULL },
303 : .index = 0,
304 :
305 : // Functions
306 : .next = &al_iter_next,
307 : .has_next = &al_iter_has_next,
308 : .destroy = &al_iter_destroy,
309 : .delete = &al_iter_delete
310 : };
311 1004 : return iter;
312 : }
313 :
314 : /*******************************************************************************
315 :
316 : List Adapter Functions
317 :
318 : These guys are used as the function pointers in smb_list. They really don't
319 : need any documentation.
320 :
321 : *******************************************************************************/
322 :
323 271 : void al_append_adapter(smb_list *l, DATA newData)
324 : {
325 271 : smb_al *list = (smb_al*) (l->data);
326 271 : al_append(list, newData);
327 271 : }
328 :
329 200 : void al_prepend_adapter(smb_list *l, DATA newData)
330 : {
331 200 : smb_al *list = (smb_al*) (l->data);
332 200 : al_prepend(list, newData);
333 200 : }
334 :
335 40345 : DATA al_get_adapter(const smb_list *l, int index, smb_status *status)
336 : {
337 40345 : const smb_al *list = (const smb_al*) (l->data);
338 40345 : return al_get(list, index, status);
339 : }
340 :
341 31 : void al_set_adapter(smb_list *l, int index, DATA newData, smb_status *status)
342 : {
343 31 : smb_al *list = (smb_al*) (l->data);
344 31 : al_set(list, index, newData, status);
345 31 : }
346 :
347 5 : void al_remove_adapter(smb_list *l, int index, smb_status *status)
348 : {
349 5 : smb_al *list = (smb_al*) (l->data);
350 5 : al_remove(list, index, status);
351 5 : }
352 :
353 5 : void al_insert_adapter(smb_list *l, int index, DATA newData)
354 : {
355 5 : smb_al *list = (smb_al*) (l->data);
356 5 : al_insert(list, index, newData);
357 5 : }
358 :
359 8 : void al_delete_adapter(smb_list *l)
360 : {
361 8 : smb_al *list = (smb_al*) (l->data);
362 8 : al_delete(list);
363 8 : l->data = NULL;
364 8 : return;
365 : }
366 :
367 41116 : int al_length_adapter(const smb_list *l)
368 : {
369 41116 : const smb_al *list = (const smb_al*) (l->data);
370 41116 : return al_length(list);
371 : }
372 :
373 25 : void al_push_back_adapter(smb_list *l, DATA newData)
374 : {
375 25 : smb_al *list = (smb_al*) (l->data);
376 25 : al_push_back(list, newData);
377 25 : }
378 :
379 7 : DATA al_pop_back_adapter(smb_list *l, smb_status *status)
380 : {
381 7 : smb_al *list = (smb_al*) (l->data);
382 7 : return al_pop_back(list, status);
383 : }
384 :
385 2 : DATA al_peek_back_adapter(smb_list *l, smb_status *status)
386 : {
387 2 : smb_al *list = (smb_al*) (l->data);
388 2 : return al_peek_back(list, status);
389 : }
390 :
391 5 : void al_push_front_adapter(smb_list *l, DATA newData)
392 : {
393 5 : smb_al *list = (smb_al*) (l->data);
394 5 : al_push_front(list, newData);
395 5 : }
396 :
397 6 : DATA al_pop_front_adapter(smb_list *l, smb_status *status)
398 : {
399 6 : smb_al *list = (smb_al*) (l->data);
400 6 : return al_pop_front(list, status);
401 : }
402 :
403 2 : DATA al_peek_front_adapter(smb_list *l, smb_status *status)
404 : {
405 2 : smb_al *list = (smb_al*) (l->data);
406 2 : return al_peek_front(list, status);
407 : }
408 :
409 22 : int al_index_of_adapter(const smb_list *l, DATA d, DATA_COMPARE comp)
410 : {
411 22 : const smb_al *list = (smb_al*) (l->data);
412 22 : return al_index_of(list, d, comp);
413 : }
414 :
415 : /**
416 : @brief Populate generic smb_list with function pointers necessary to use
417 : smb_al with it.
418 :
419 : Note that this is a *private* function, not defined in libstephen.h for a
420 : reason. You shouldn't need the function, as there is library functionality
421 : that provides it for you.
422 :
423 : @param l The list to fill up.
424 : */
425 8 : void al_fill_functions(smb_list *l)
426 : {
427 8 : l->append = al_append_adapter;
428 8 : l->prepend = al_prepend_adapter;
429 8 : l->get = al_get_adapter;
430 8 : l->set = al_set_adapter;
431 8 : l->remove = al_remove_adapter;
432 8 : l->insert = al_insert_adapter;
433 8 : l->delete = al_delete_adapter;
434 8 : l->length = al_length_adapter;
435 8 : l->push_back = al_push_back_adapter;
436 8 : l->pop_back = al_pop_back_adapter;
437 8 : l->peek_back = al_peek_back_adapter;
438 8 : l->push_front = al_push_front_adapter;
439 8 : l->pop_front = al_pop_front_adapter;
440 8 : l->peek_front = al_peek_front_adapter;
441 8 : l->index_of = al_index_of_adapter;
442 8 : }
443 :
444 8 : smb_list al_cast_to_list(smb_al *list)
445 : {
446 : smb_list genericList;
447 8 : genericList.data = list;
448 :
449 8 : al_fill_functions(&genericList);
450 :
451 8 : return genericList;
452 : }
453 :
454 8 : smb_list al_create_list()
455 : {
456 8 : smb_al *list = al_create();
457 8 : return al_cast_to_list(list);
458 : }
|
