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