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