|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. |
|
5 * |
|
6 * Redistribution and use in source and binary forms, with or without |
|
7 * modification, are permitted provided that the following conditions are met: |
|
8 * |
|
9 * 1. Redistributions of source code must retain the above copyright |
|
10 * notice, this list of conditions and the following disclaimer. |
|
11 * |
|
12 * 2. Redistributions in binary form must reproduce the above copyright |
|
13 * notice, this list of conditions and the following disclaimer in the |
|
14 * documentation and/or other materials provided with the distribution. |
|
15 * |
|
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
26 * POSSIBILITY OF SUCH DAMAGE. |
|
27 */ |
|
28 |
|
29 #include "cx/iterator.h" |
|
30 |
|
31 #include <string.h> |
|
32 |
|
33 static bool cx_iter_valid(void const *it) { |
|
34 struct cx_iterator_s const *iter = it; |
|
35 return iter->index < iter->elem_count; |
|
36 } |
|
37 |
|
38 static void *cx_iter_current(void const *it) { |
|
39 struct cx_iterator_s const *iter = it; |
|
40 return iter->elem_handle; |
|
41 } |
|
42 |
|
43 static void cx_iter_next_fast(void *it) { |
|
44 struct cx_iterator_base_s *itbase = it; |
|
45 if (itbase->remove) { |
|
46 struct cx_mut_iterator_s *iter = it; |
|
47 itbase->remove = false; |
|
48 iter->elem_count--; |
|
49 // only move the last element when we are not currently aiming |
|
50 // at the last element already |
|
51 if (iter->index < iter->elem_count) { |
|
52 void *last = ((char *) iter->src_handle) |
|
53 + iter->elem_count * iter->elem_size; |
|
54 memcpy(iter->elem_handle, last, iter->elem_size); |
|
55 } |
|
56 } else { |
|
57 struct cx_iterator_s *iter = it; |
|
58 iter->index++; |
|
59 iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; |
|
60 } |
|
61 } |
|
62 |
|
63 static void cx_iter_next_slow(void *it) { |
|
64 struct cx_iterator_base_s *itbase = it; |
|
65 if (itbase->remove) { |
|
66 struct cx_mut_iterator_s *iter = it; |
|
67 itbase->remove = false; |
|
68 iter->elem_count--; |
|
69 |
|
70 // number of elements to move |
|
71 size_t remaining = iter->elem_count - iter->index; |
|
72 if (remaining > 0) { |
|
73 memmove( |
|
74 iter->elem_handle, |
|
75 ((char *) iter->elem_handle) + iter->elem_size, |
|
76 remaining * iter->elem_size |
|
77 ); |
|
78 } |
|
79 } else { |
|
80 struct cx_iterator_s *iter = it; |
|
81 iter->index++; |
|
82 iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; |
|
83 } |
|
84 } |
|
85 |
|
86 CxMutIterator cxIterator( |
|
87 void *array, |
|
88 size_t elem_size, |
|
89 size_t elem_count, |
|
90 bool remove_keeps_order |
|
91 ) { |
|
92 CxMutIterator iter; |
|
93 |
|
94 iter.index = 0; |
|
95 iter.src_handle = array; |
|
96 iter.elem_handle = array; |
|
97 iter.elem_size = elem_size; |
|
98 iter.elem_count = array == NULL ? 0 : elem_count; |
|
99 iter.base.valid = cx_iter_valid; |
|
100 iter.base.current = cx_iter_current; |
|
101 iter.base.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast; |
|
102 iter.base.remove = false; |
|
103 iter.base.mutating = true; |
|
104 |
|
105 return iter; |
|
106 } |