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 <stdlib.h> 14 #include <string.h> 15 16 void 17 areflist_setEmpty(ARefList* l) 18 { 19 if (l->iteration > 0) { 20 /* deferred empty, set all items to NULL 21 * to stop iterations */ 22 void** items = areflist_items(l); 23 memset(items, 0, l->count*sizeof(items[0])); 24 l->iteration |= 1; 25 } else { 26 /* direct empty */ 27 if (l->max > 1) { 28 free(l->u.items); 29 l->max = 1; 30 } 31 } 32 l->count = 0; 33 } 34 35 int 36 areflist_indexOf(ARefList* l, void* item) 37 { 38 if (item) { 39 void** items = (l->max == 1) ? &l->u.item0 : l->u.items; 40 void** end = items + l->count; 41 void** ii = items; 42 43 for ( ; ii < end; ii += 1 ) 44 if (*ii == item) 45 return (ii - items); 46 } 47 return -1; 48 } 49 50 static void 51 areflist_grow(ARefList* l, int count) 52 { 53 int newcount = l->count + count; 54 if (newcount > l->max) { 55 int oldmax = l->max == 1 ? 0 : l->max; 56 int newmax = oldmax; 57 void** olditems = l->max == 1 ? NULL : l->u.items; 58 void** newitems; 59 60 while (oldmax < newcount) 61 oldmax += (oldmax >> 1) + 4; 62 63 newitems = realloc(olditems, newmax*sizeof(newitems[0])); 64 65 l->u.items = newitems; 66 l->max = (uint16_t) newmax; 67 } 68 } 69 70 71 void 72 areflist_add(ARefList* l, void* item) 73 { 74 if (item) { 75 void** items; 76 77 if (l->count >= l->max) { 78 areflist_grow(l, 1); 79 } 80 items = areflist_items(l); 81 items[l->count] = item; 82 l->count += 1; 83 } 84 } 85 86 void* 87 areflist_pop(ARefList* l) 88 { 89 void* item = NULL; 90 void** items = areflist_items(l); 91 92 if (l->count > 0) { 93 if (l->iteration > 0) { 94 /* deferred deletion */ 95 int nn; 96 for (nn = l->count-1; nn > 0; nn--) { 97 item = items[nn]; 98 if (item != NULL) { 99 l->count -= 1; 100 return item; 101 } 102 } 103 } else { 104 /* normal pop */ 105 item = items[--l->count]; 106 if (l->count <= 0 && l->max > 1) { 107 free(l->u.items); 108 l->max = 1; 109 } 110 } 111 } 112 return item; 113 } 114 115 ABool 116 areflist_del(ARefList* l, void* item) 117 { 118 if (item) { 119 int index = areflist_indexOf(l, item); 120 if (index >= 0) { 121 void** items = areflist_items(l); 122 123 if (l->iteration > 0) { 124 /* deferred deletion */ 125 items[index] = NULL; 126 l->iteration |= 1; 127 } else { 128 /* direct deletion */ 129 if (l->max > 1) { 130 memmove(items + index, items + index + 1, l->count - index - 1); 131 if (--l->count == 0) { 132 free(l->u.items); 133 l->max = 1; 134 } 135 } else { 136 l->u.item0 = NULL; 137 l->count = 0; 138 } 139 } 140 return 1; 141 } 142 } 143 return 0; 144 } 145 146 void 147 _areflist_remove_deferred(ARefList* l) 148 { 149 if (l->iteration & 1) { 150 /* remove all NULL elements from the array */ 151 void** items = areflist_items(l); 152 int rr = 0; 153 int ww = 0; 154 for ( ; rr < l->count; rr++ ) { 155 if (items[rr] != NULL) 156 items[ww++] = items[rr]; 157 } 158 l->count = (int16_t) ww; 159 160 /* if the list is empty, release its array */ 161 if (l->count == 0 && l->max > 1) { 162 free(l->u.items); 163 l->max = 1; 164 } 165 } 166 l->iteration = 0; 167 } 168 169 void 170 areflist_copy(ARefList* dst, ARefList* src) 171 { 172 dst[0] = src[0]; 173 174 if (src->max > 1) { 175 dst->u.items = malloc( dst->count*sizeof(void*) ); 176 dst->max = dst->count; 177 } 178 } 179 180 void* 181 areflist_get(ARefList* l, int n) 182 { 183 if ((unsigned)n >= (unsigned)l->count) 184 return NULL; 185 186 if (l->max == 1) 187 return l->u.item0; 188 189 return l->u.items[n]; 190 } 191 192 void** 193 areflist_at(ARefList* l, int n) 194 { 195 void** items; 196 197 if ((unsigned)n >= (unsigned)l->count) 198 return NULL; 199 200 items = (l->max == 1) ? &l->u.item0 : l->u.items; 201 202 return items + n; 203 } 204
