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 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 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 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 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 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 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 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* 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 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 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 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 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* 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** 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
