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
20 ANDROID_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 */
40 typedef 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 */
51 AINLINED void
areflist_init(ARefList * l)52 areflist_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 */
61 AINLINED int
areflist_getCount(const ARefList * l)62 areflist_getCount(const ARefList* l)
63 {
64 return l->count;
65 }
66
67 /* Clear an ARefList */
68 void areflist_setEmpty(ARefList* l);
69
70 /* Finalize, i.e. clear, an ARefList */
71 AINLINED void
areflist_done(ARefList * l)72 areflist_done(ARefList* l)
73 {
74 areflist_setEmpty(l);
75 }
76
77 /* Return TRUE iff an ARefList has no item */
78 AINLINED ABool
areflist_isEmpty(const ARefList * l)79 areflist_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 */
87 int areflist_indexOf(const ARefList* l, void* item);
88
89 /* Return TRUE iff an ARefList contains 'item' */
90 AINLINED ABool
areflist_has(const ARefList * l,void * item)91 areflist_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. */
98 void 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. */
102 ABool 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 */
106 ABool areflist_delAll(ARefList* l, void* item);
107
108 /* Same as areflist_add() */
109 AINLINED void
areflist_push(ARefList * l,void * item)110 areflist_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 */
117 void* areflist_popLast(ARefList* l);
118
119 /* Return the n-th array entry, or NULL in case of invalid index */
120 void* areflist_get(const ARefList* l, int n);
121
122 AINLINED int
areflist_count(ARefList * l)123 areflist_count(ARefList* l)
124 {
125 return l->count;
126 }
127
128 void areflist_append(ARefList* l, const ARefList* src);
129
130 /* used internally */
131 void _areflist_remove_deferred(ARefList* l);
132
133 void** _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
210 void areflist_copy(ARefList* dst, const ARefList* src);
211
212 ANDROID_END_HEADER
213
214 #endif /* _ANDROID_GRAPHICS_REFLIST_H */
215