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
areflist_setEmpty(ARefList * l)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
areflist_indexOf(ARefList * l,void * item)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
areflist_grow(ARefList * l,int count)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
areflist_add(ARefList * l,void * item)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*
areflist_pop(ARefList * l)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
areflist_del(ARefList * l,void * item)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
_areflist_remove_deferred(ARefList * l)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
areflist_copy(ARefList * dst,ARefList * src)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*
areflist_get(ARefList * l,int n)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**
areflist_at(ARefList * l,int n)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