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 18static 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 26static 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 36void 37areflist_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 53int 54areflist_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 68static void 69areflist_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 98void 99areflist_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 114void 115areflist_append(ARefList* l, const ARefList* l2) 116{ 117 AREFLIST_FOREACH_CONST(l2, item, { 118 areflist_add(l, item); 119 }); 120} 121 122void* 123areflist_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 139FOUND_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 151ABool 152areflist_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 184ABool 185areflist_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 204COPY_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 224void 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 242void 243areflist_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 266void* 267areflist_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 278void** 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