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 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 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 68 areflist_done(ARefList* l) 69 { 70 areflist_setEmpty(l); 71 } 72 73 /* Return TRUE iff an ARefList has no item */ 74 AINLINED ABool 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 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 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 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