1 /* Copyright (C) 2007-2008 The Android Open Source Project
2 **
3 ** This software is licensed under the terms of the GNU General Public
4 ** License version 2, as published by the Free Software Foundation, and
5 ** may be copied, distributed, and modified under those terms.
6 **
7 ** This program is distributed in the hope that it will be useful,
8 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
9 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 ** GNU General Public License for more details.
11 */
12 #include "android/utils/reflist.h"
13 #include "android/utils/system.h"
14 #include "android/utils/assert.h"
15 #include <stdlib.h>
16 #include <string.h>
17
_areflist_items(const ARefList * l)18 static void** _areflist_items(const ARefList* l)
19 {
20 if (l->max == 1)
21 return (void**)&l->u.item0;
22 else
23 return l->u.items;
24 }
25
26 static void
_areflist_checkSize0(ARefList * l)27 _areflist_checkSize0(ARefList* l)
28 {
29 if (l->size == 0 && l->max > 1) {
30 AFREE(l->u.items);
31 l->max = 1;
32 l->u.item0 = NULL;
33 }
34 }
35
36 void
areflist_setEmpty(ARefList * l)37 areflist_setEmpty(ARefList* l)
38 {
39 if (l->iteration > 0) {
40 /* deferred empty, set all items to NULL
41 * to stop iterations */
42 void** items = _areflist_items(l);
43 AARRAY_ZERO(items, l->count);
44 l->iteration |= 1;
45 } else {
46 /* direct empty */
47 l->size = 0;
48 _areflist_checkSize0(l);
49 }
50 l->count = 0;
51 }
52
53 int
areflist_indexOf(const ARefList * l,void * item)54 areflist_indexOf(const ARefList* l, void* item)
55 {
56 if (item) {
57 void** items = _areflist_items(l);
58 void** end = items + l->count;
59 void** ii = items;
60
61 for ( ; ii < end; ii += 1 )
62 if (*ii == item)
63 return (ii - items);
64 }
65 return -1;
66 }
67
68 static void
areflist_grow(ARefList * l,int count)69 areflist_grow(ARefList* l, int count)
70 {
71 int newcount = l->size + count;
72 if (newcount > l->max) {
73 int oldmax = l->max;
74 int newmax;
75 void** items;
76
77 if (oldmax == 1) {
78 oldmax = 0;
79 items = NULL;
80 } else {
81 items = l->u.items;
82 }
83 newmax = oldmax;
84 while (newmax < newcount)
85 newmax += (newmax >> 1) + 4;
86
87 AARRAY_RENEW(items, newmax);
88
89 if (l->max == 1)
90 items[0] = l->u.item0;
91
92 l->u.items = items;
93 l->max = (uint16_t) newmax;
94 }
95 }
96
97
98 void
areflist_add(ARefList * l,void * item)99 areflist_add(ARefList* l, void* item)
100 {
101 if (item) {
102 void** items;
103
104 if (l->size >= l->max) {
105 areflist_grow(l, 1);
106 }
107 items = _areflist_items(l);
108 items[l->size] = item;
109 l->size += 1;
110 l->count += 1;
111 }
112 }
113
114 void
areflist_append(ARefList * l,const ARefList * l2)115 areflist_append(ARefList* l, const ARefList* l2)
116 {
117 AREFLIST_FOREACH_CONST(l2, item, {
118 areflist_add(l, item);
119 });
120 }
121
122 void*
areflist_popLast(ARefList * l)123 areflist_popLast(ARefList* l)
124 {
125 void* item = NULL;
126 void** items = _areflist_items(l);
127 int nn;
128
129 if (l->count == 0)
130 return NULL;
131
132 for (nn = l->size; nn > 0; nn--) {
133 item = items[nn-1];
134 if (item != NULL)
135 goto FOUND_LAST;
136 }
137 return NULL;
138
139 FOUND_LAST:
140 /* we found the last non-NULL item in the array */
141 l->count -= 1;
142 items[nn-1] = NULL;
143
144 if (l->iteration == 0) {
145 l->size = nn;
146 _areflist_checkSize0(l);
147 }
148 return item;
149 }
150
151 ABool
areflist_delFirst(ARefList * l,void * item)152 areflist_delFirst(ARefList* l, void* item)
153 {
154 if (item == NULL)
155 return 0;
156
157 int index = areflist_indexOf(l, item);
158 if (index < 0)
159 return 0;
160
161 void** items = _areflist_items(l);
162
163 if (l->iteration > 0) {
164 /* deferred deletion */
165 items[index] = NULL;
166 l->iteration |= 1;
167 l->count -= 1;
168 } else {
169 /* direct deletion */
170 if (l->max > 1) {
171 AARRAY_MOVE(items + index, items + index + 1, l->size - index - 1);
172 l->size -= 1;
173 l->count -= 1;
174 _areflist_checkSize0(l);
175 } else {
176 l->u.item0 = NULL;
177 l->size = 0;
178 l->count = 0;
179 }
180 }
181 return 1;
182 }
183
184 ABool
areflist_delAll(ARefList * l,void * item)185 areflist_delAll(ARefList* l, void* item)
186 {
187 ABool result = 0;
188
189 if (item == NULL)
190 return 0;
191
192 void** items = _areflist_items(l);
193 int readPos = 0;
194 int writePos = 0;
195
196 /* don't modify the list until we find the item
197 * or an EMPTY slot */
198 for ( ; readPos < l->size; readPos++ ) {
199 if (items[readPos] == NULL || items[readPos] == item)
200 goto COPY_LIST;
201 }
202 return 0;
203
204 COPY_LIST:
205 writePos = readPos;
206 for ( ; readPos < l->size; readPos++ ) {
207 if (items[readPos] == NULL) {
208 continue;
209 }
210 if (items[readPos] == item) {
211 result = 1;
212 continue;
213 }
214 items[writePos] = items[readPos];
215 writePos++;
216 }
217 l->count = l->size = (uint16_t) writePos;
218 _areflist_checkSize0(l);
219
220 return result;
221 }
222
223
224 void
_areflist_remove_deferred(ARefList * l)225 _areflist_remove_deferred(ARefList* l)
226 {
227 if (l->iteration & 1) {
228 /* remove all NULL elements from the array */
229 void** items = _areflist_items(l);
230 int rr = 0;
231 int ww = 0;
232 for ( ; rr < l->size; rr++ ) {
233 if (items[rr] != NULL)
234 items[ww++] = items[rr];
235 }
236 l->count = l->size = (uint16_t) ww;
237 _areflist_checkSize0(l);
238 }
239 l->iteration = 0;
240 }
241
242 void
areflist_copy(ARefList * dst,const ARefList * src)243 areflist_copy(ARefList* dst, const ARefList* src)
244 {
245 dst[0] = src[0];
246
247 if (src->max > 1) {
248 dst->max = dst->count;
249 AARRAY_NEW(dst->u.items, dst->max);
250
251 void** ritems = src->u.items;
252 void** witems = _areflist_items(dst);
253 int rr = 0;
254 int ww = 0;
255 for ( ; rr < src->size; rr++ ) {
256 if (ritems[rr] != NULL) {
257 witems[ww++] = ritems[rr];
258 }
259 }
260 dst->size = ww;
261 AASSERT_TRUE(ww == dst->count);
262 _areflist_checkSize0(dst);
263 }
264 }
265
266 void*
areflist_get(const ARefList * l,int n)267 areflist_get(const ARefList* l, int n)
268 {
269 if ((unsigned)n >= (unsigned)l->count)
270 return NULL;
271
272 if (l->max == 1)
273 return l->u.item0;
274
275 return l->u.items[n];
276 }
277
278 void**
_areflist_at(const ARefList * l,int n)279 _areflist_at(const ARefList* l, int n)
280 {
281 void** items;
282
283 if ((unsigned)n >= (unsigned)l->size)
284 return NULL;
285
286 items = _areflist_items(l);
287 return items + n;
288 }
289