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 */
36typedef 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 */
47AINLINED void
48areflist_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 */
57AINLINED int
58areflist_getCount(const ARefList*  l)
59{
60    return l->count;
61}
62
63/* Clear an ARefList */
64void  areflist_setEmpty(ARefList*  l);
65
66/* Finalize, i.e. clear, an ARefList */
67AINLINED void
68areflist_done(ARefList*  l)
69{
70    areflist_setEmpty(l);
71}
72
73/* Return TRUE iff an ARefList has no item */
74AINLINED ABool
75areflist_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 */
83int    areflist_indexOf(const ARefList*  l, void*  item);
84
85/* Return TRUE iff an ARefList contains 'item' */
86AINLINED ABool
87areflist_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. */
94void    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. */
98ABool   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 */
102ABool   areflist_delAll(ARefList*  l, void*  item);
103
104/* Same as areflist_add() */
105AINLINED void
106areflist_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 */
113void*  areflist_popLast(ARefList*  l);
114
115/* Return the n-th array entry, or NULL in case of invalid index */
116void*   areflist_get(const ARefList*  l, int  n);
117
118AINLINED int
119areflist_count(ARefList*  l)
120{
121    return l->count;
122}
123
124void  areflist_append(ARefList*  l, const ARefList*  src);
125
126/* used internally */
127void    _areflist_remove_deferred(ARefList*  l);
128
129void**  _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
206void  areflist_copy(ARefList*  dst, const ARefList*  src);
207
208#endif /* _ANDROID_GRAPHICS_REFLIST_H */
209