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#ifndef _ANDROID_GRAPHICS_REFLIST_H
13#define _ANDROID_GRAPHICS_REFLIST_H
14
15#include <inttypes.h>
16
17#include "android/utils/compiler.h"
18#include <android/utils/system.h>
19
20ANDROID_BEGIN_HEADER
21
22/* Definitions for a smart list of references to generic objects.
23 * supports safe deletion and addition while they are being iterated
24 * with AREFLIST_FOREACH() macro.
25 *
26 * note that you cannot add NULL to an ARefList.
27 */
28
29/* Clients should ignore these implementation details, which
30 * we're going to explain there:
31 *   - 'count' is the number of items in the list
32 *   - 'size' is the number of slots in the list's array. It is
33 *     always >= 'count'. Some slots correspond to deleted items
34 *     and will hold a NULL value.
35 *   - 'max' is the size of the slots array
36 *   - 'u.item0' is used when 'max' is 1
37 *   - 'u.items' is the slot array if 'max > 1'
38 *   - 'u.next' is only used for free-list storage.
39 */
40typedef struct ARefList {
41    /* XXX: should we use uint32_t instead ? */
42    uint16_t   count, size, max;
43    uint16_t   iteration;
44    union {
45        void*   item0;
46        void**  items;
47    } u;
48} ARefList;
49
50/* Initialize an empty ARefList */
51AINLINED void
52areflist_init(ARefList*  l)
53{
54    l->count     = 0;
55    l->size      = 0;
56    l->max       = 1;
57    l->iteration = 0;
58}
59
60/* Return the number of items in a list */
61AINLINED int
62areflist_getCount(const ARefList*  l)
63{
64    return l->count;
65}
66
67/* Clear an ARefList */
68void  areflist_setEmpty(ARefList*  l);
69
70/* Finalize, i.e. clear, an ARefList */
71AINLINED void
72areflist_done(ARefList*  l)
73{
74    areflist_setEmpty(l);
75}
76
77/* Return TRUE iff an ARefList has no item */
78AINLINED ABool
79areflist_isEmpty(const ARefList*  l)
80{
81    return (areflist_getCount(l) == 0);
82}
83
84/* Return the index of 'item' in the ARefList, or -1.
85 * This returns -1 if 'item' is NULL.
86 */
87int    areflist_indexOf(const ARefList*  l, void*  item);
88
89/* Return TRUE iff an ARefList contains 'item' */
90AINLINED ABool
91areflist_has(const ARefList*  l, void*  item)
92{
93    return areflist_indexOf(l, item) >= 0;
94}
95
96/* Append 'item' to a list. An item can be added several
97 * times to the same list. Do nothing if 'item' is NULL. */
98void    areflist_add(ARefList*  l, void*  item);
99
100/* Remove first instance of 'item' from an ARefList.
101 * Returns TRUE iff the item was found in the list. */
102ABool   areflist_delFirst(ARefList*  l, void*  item);
103
104/* Remove all instances of 'item' from an ARefList.
105 * returns TRUE iff the item was found in the list */
106ABool   areflist_delAll(ARefList*  l, void*  item);
107
108/* Same as areflist_add() */
109AINLINED void
110areflist_push(ARefList*  l, void*  item)
111{
112    areflist_add(l, item);
113}
114
115/* Remove last item from an ARefList and return it.
116 * NULL is returned if the list is empty */
117void*  areflist_popLast(ARefList*  l);
118
119/* Return the n-th array entry, or NULL in case of invalid index */
120void*   areflist_get(const ARefList*  l, int  n);
121
122AINLINED int
123areflist_count(ARefList*  l)
124{
125    return l->count;
126}
127
128void  areflist_append(ARefList*  l, const ARefList*  src);
129
130/* used internally */
131void    _areflist_remove_deferred(ARefList*  l);
132
133void**  _areflist_at(const ARefList*  l, int  n);
134
135#define  AREFLIST_LOOP(list_,itemvar_) \
136    do { \
137        ARefList*  _reflist_loop   = (list_); \
138        int        _reflist_loop_i = 0; \
139        int        _reflist_loop_n = _reflist_loop->size; \
140        _reflist_loop->iteration += 2; \
141        for ( ; _reflist_loop_i < _reflist_loop_n; _reflist_loop_i++ ) { \
142            void** _reflist_loop_at = _areflist_at(_reflist_loop, _reflist_loop_i); \
143            (itemvar_) = *(_reflist_loop_at); \
144            if ((itemvar_) != NULL) {
145
146#define  AREFLIST_LOOP_END \
147            } \
148        } \
149        if (_reflist_loop->iteration & 1) \
150            _areflist_remove_deferred(_reflist_loop); \
151    } while (0);
152
153#define  AREFLIST_LOOP_CONST(list_,itemvar_) \
154    do { \
155        const ARefList*  _reflist_loop   = (list_); \
156        int              _reflist_loop_i = 0; \
157        int              _reflist_loop_n = _reflist_loop->size; \
158        for ( ; _reflist_loop_i < _reflist_loop_n; _reflist_loop_i++ ) { \
159            void** _reflist_loop_at = _areflist_at(_reflist_loop, _reflist_loop_i); \
160            (itemvar_) = *(_reflist_loop_at); \
161            if ((itemvar_) != NULL) {
162
163#define  AREFLIST_LOOP_DEL() \
164    (_reflist_loop->iteration |= 1, *_reflist_loop_at = NULL)
165
166#define  AREFLIST_LOOP_SET(val) \
167    (_reflist_loop->iteration |= 1, *_reflist_loop_at = (val))
168
169
170#define  AREFLIST_FOREACH(list_,item_,statement_) \
171    ({ ARefList*  _reflist   = (list_); \
172       int        _reflist_i = 0; \
173       int        _reflist_n = _reflist->size; \
174       _reflist->iteration += 2; \
175       for ( ; _reflist_i < _reflist_n; _reflist_i++ ) { \
176           void**  __reflist_at   = _areflist_at(_reflist, _reflist_i); \
177           void*  item_ = *__reflist_at; \
178           if (item_ != NULL) { \
179               statement_; \
180           } \
181       } \
182       _reflist->iteration -= 2; \
183       if (_reflist->iteration == 1) \
184           _areflist_remove_deferred(_reflist); \
185    })
186
187#define  AREFLIST_FOREACH_CONST(list_,item_,statement_) \
188    ({ const ARefList*  _reflist = (list_); \
189       int        _reflist_i = 0; \
190       int        _reflist_n = _reflist->size; \
191       for ( ; _reflist_i < _reflist_n; _reflist_i++ ) { \
192           void**  __reflist_at = _areflist_at(_reflist, _reflist_i); \
193           void*  item_ = *__reflist_at; \
194           if (item_ != NULL) { \
195               statement_; \
196           } \
197       } \
198    })
199
200/* use this to delete the currently iterated element */
201#define  AREFLIST_DEL_ITERATED()  \
202    ({ *__reflist_at = NULL; \
203       _reflist->iteration |= 1; })
204
205/* use this to replace the currently iterated element */
206#define  AREFLIST_SET_ITERATED(item) \
207    ({ *__reflist_at = (item); \
208       if (item == NULL) _reflist->iteration |= 1; })
209
210void  areflist_copy(ARefList*  dst, const ARefList*  src);
211
212ANDROID_END_HEADER
213
214#endif /* _ANDROID_GRAPHICS_REFLIST_H */
215