1 | /*****************************************************************************/ |
2 | /* */ |
3 | /* coll.h */ |
4 | /* */ |
5 | /* Collection (dynamic array) */ |
6 | /* */ |
7 | /* */ |
8 | /* */ |
9 | /* (C) 2000-2011, Ullrich von Bassewitz */ |
10 | /* Roemerstrasse 52 */ |
11 | /* D-70794 Filderstadt */ |
12 | /* EMail: uz@cc65.org */ |
13 | /* */ |
14 | /* */ |
15 | /* This software is provided 'as-is', without any expressed or implied */ |
16 | /* warranty. In no event will the authors be held liable for any damages */ |
17 | /* arising from the use of this software. */ |
18 | /* */ |
19 | /* Permission is granted to anyone to use this software for any purpose, */ |
20 | /* including commercial applications, and to alter it and redistribute it */ |
21 | /* freely, subject to the following restrictions: */ |
22 | /* */ |
23 | /* 1. The origin of this software must not be misrepresented; you must not */ |
24 | /* claim that you wrote the original software. If you use this software */ |
25 | /* in a product, an acknowledgment in the product documentation would be */ |
26 | /* appreciated but is not required. */ |
27 | /* 2. Altered source versions must be plainly marked as such, and must not */ |
28 | /* be misrepresented as being the original software. */ |
29 | /* 3. This notice may not be removed or altered from any source */ |
30 | /* distribution. */ |
31 | /* */ |
32 | /*****************************************************************************/ |
33 | |
34 | |
35 | |
36 | #ifndef COLL_H |
37 | #define COLL_H |
38 | |
39 | |
40 | |
41 | /* common */ |
42 | #include "attrib.h" |
43 | #include "check.h" |
44 | #include "inline.h" |
45 | |
46 | |
47 | |
48 | /*****************************************************************************/ |
49 | /* Data */ |
50 | /*****************************************************************************/ |
51 | |
52 | |
53 | |
54 | /* An array of pointers that grows if needed */ |
55 | typedef struct Collection Collection; |
56 | struct Collection { |
57 | unsigned Count; /* Number of items in the list */ |
58 | unsigned Size; /* Size of allocated array */ |
59 | void** Items; /* Array with dynamic size */ |
60 | }; |
61 | |
62 | /* An empty collection */ |
63 | extern const Collection EmptyCollection; |
64 | |
65 | /* Initializer for static collections */ |
66 | #define STATIC_COLLECTION_INITIALIZER { 0, 0, 0 } |
67 | |
68 | /* Initializer for auto collections */ |
69 | #define AUTO_COLLECTION_INITIALIZER EmptyCollection |
70 | |
71 | |
72 | |
73 | /*****************************************************************************/ |
74 | /* Code */ |
75 | /*****************************************************************************/ |
76 | |
77 | |
78 | |
79 | Collection* InitCollection (Collection* C); |
80 | /* Initialize a collection and return it. */ |
81 | |
82 | void DoneCollection (Collection* C); |
83 | /* Free the data for a collection. This will not free the data contained in |
84 | ** the collection. |
85 | */ |
86 | |
87 | Collection* NewCollection (void); |
88 | /* Create and return a new collection */ |
89 | |
90 | void FreeCollection (Collection* C); |
91 | /* Free a collection */ |
92 | |
93 | void CollGrow (Collection* C, unsigned Size); |
94 | /* Grow the collection C so it is able to hold Size items without a resize |
95 | ** being necessary. This can be called for performance reasons if the number |
96 | ** of items to be placed in the collection is known in advance. |
97 | */ |
98 | |
99 | #if defined(HAVE_INLINE) |
100 | INLINE unsigned CollCount (const Collection* C) |
101 | /* Return the number of items in the collection */ |
102 | { |
103 | return C->Count; |
104 | } |
105 | #else |
106 | # define CollCount(C) (C)->Count |
107 | #endif |
108 | |
109 | void CollInsert (Collection* C, void* Item, unsigned Index); |
110 | /* Insert the data at the given position in the collection */ |
111 | |
112 | #if defined(HAVE_INLINE) |
113 | INLINE void CollAppend (Collection* C, void* Item) |
114 | /* Append an item to the end of the collection */ |
115 | { |
116 | /* Insert the item at the end of the current list */ |
117 | CollInsert (C, Item, C->Count); |
118 | } |
119 | #else |
120 | void CollAppend (Collection* C, void* Item); |
121 | /* Append an item to the end of the collection */ |
122 | #endif |
123 | |
124 | #if defined(HAVE_INLINE) |
125 | INLINE void* CollAt (const Collection* C, unsigned Index) |
126 | /* Return the item at the given index */ |
127 | { |
128 | /* Check the index */ |
129 | PRECONDITION (Index < C->Count); |
130 | |
131 | /* Return the element */ |
132 | return C->Items[Index]; |
133 | } |
134 | #else |
135 | void* CollAt (const Collection* C, unsigned Index); |
136 | /* Return the item at the given index */ |
137 | #endif |
138 | |
139 | #if defined(HAVE_INLINE) |
140 | INLINE void* CollAtUnchecked (const Collection* C, unsigned Index) |
141 | /* Return the item at the given index */ |
142 | { |
143 | /* Return the element */ |
144 | return C->Items[Index]; |
145 | } |
146 | #else |
147 | # define CollAtUnchecked(C, Index) ((C)->Items[(Index)]) |
148 | #endif |
149 | |
150 | #if defined(HAVE_INLINE) |
151 | INLINE const void* CollConstAt (const Collection* C, unsigned Index) |
152 | /* Return the item at the given index */ |
153 | { |
154 | /* Check the index */ |
155 | PRECONDITION (Index < C->Count); |
156 | |
157 | /* Return the element */ |
158 | return C->Items[Index]; |
159 | } |
160 | #else |
161 | const void* CollConstAt (const Collection* C, unsigned Index); |
162 | /* Return the item at the given index */ |
163 | #endif |
164 | |
165 | #if defined(HAVE_INLINE) |
166 | INLINE void* CollLast (Collection* C) |
167 | /* Return the last item in a collection */ |
168 | { |
169 | /* We must have at least one entry */ |
170 | PRECONDITION (C->Count > 0); |
171 | |
172 | /* Return the element */ |
173 | return C->Items[C->Count-1]; |
174 | } |
175 | #else |
176 | void* CollLast (Collection* C); |
177 | /* Return the last item in a collection */ |
178 | #endif |
179 | |
180 | #if defined(HAVE_INLINE) |
181 | INLINE const void* CollConstLast (const Collection* C) |
182 | /* Return the last item in a collection */ |
183 | { |
184 | /* We must have at least one entry */ |
185 | PRECONDITION (C->Count > 0); |
186 | |
187 | /* Return the element */ |
188 | return C->Items[C->Count-1]; |
189 | } |
190 | #else |
191 | const void* CollConstLast (const Collection* C); |
192 | /* Return the last item in a collection */ |
193 | #endif |
194 | |
195 | #if defined(HAVE_INLINE) |
196 | INLINE void* CollPop (Collection* C) |
197 | /* Remove the last segment from the stack and return it. Calls FAIL if the |
198 | ** collection is empty. |
199 | */ |
200 | { |
201 | /* We must have at least one entry */ |
202 | PRECONDITION (C->Count > 0); |
203 | |
204 | /* Return the element */ |
205 | return C->Items[--C->Count]; |
206 | } |
207 | #else |
208 | void* CollPop (Collection* C); |
209 | /* Remove the last segment from the stack and return it. Calls FAIL if the |
210 | ** collection is empty. |
211 | */ |
212 | #endif |
213 | |
214 | int CollIndex (Collection* C, const void* Item); |
215 | /* Return the index of the given item in the collection. Return -1 if the |
216 | ** item was not found in the collection. |
217 | */ |
218 | |
219 | void CollDelete (Collection* C, unsigned Index); |
220 | /* Remove the item with the given index from the collection. This will not |
221 | ** free the item itself, just the pointer. All items with higher indices |
222 | ** will get moved to a lower position. |
223 | */ |
224 | |
225 | void CollDeleteItem (Collection* C, const void* Item); |
226 | /* Delete the item pointer from the collection. The item must be in the |
227 | ** collection, otherwise FAIL will be called. |
228 | */ |
229 | |
230 | #if defined(HAVE_INLINE) |
231 | INLINE void CollDeleteAll (Collection* C) |
232 | /* Delete all items from the given collection. This will not free the items |
233 | ** itself, it will only remove the pointers. |
234 | */ |
235 | { |
236 | /* This one is easy... */ |
237 | C->Count = 0; |
238 | } |
239 | #else |
240 | # define CollDeleteAll(C) ((C)->Count = 0) |
241 | #endif |
242 | |
243 | #if defined(HAVE_INLINE) |
244 | INLINE void CollReplace (Collection* C, void* Item, unsigned Index) |
245 | /* Replace the item at the given position. The old item will not be freed, |
246 | ** just the pointer will get replaced. |
247 | */ |
248 | { |
249 | /* Check the index */ |
250 | PRECONDITION (Index < C->Count); |
251 | |
252 | /* Replace the item pointer */ |
253 | C->Items[Index] = Item; |
254 | } |
255 | #else |
256 | void CollReplace (Collection* C, void* Item, unsigned Index); |
257 | /* Replace the item at the given position. The old item will not be freed, |
258 | ** just the pointer will get replaced. |
259 | */ |
260 | #endif |
261 | |
262 | void CollReplaceExpand (Collection* C, void* Item, unsigned Index); |
263 | /* If Index is a valid index for the collection, replace the item at this |
264 | ** position by the one passed. If the collection is too small, expand it, |
265 | ** filling unused pointers with NULL, then add the new item at the given |
266 | ** position. |
267 | */ |
268 | |
269 | void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex); |
270 | /* Move an item from one position in the collection to another. OldIndex |
271 | ** is the current position of the item, NewIndex is the new index before |
272 | ** the function has done it's work. Existing entries with indices NewIndex |
273 | ** and up might be moved one position upwards. |
274 | */ |
275 | |
276 | void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target); |
277 | /* Move a range of items from one position to another. Start is the index |
278 | ** of the first item to move, Count is the number of items and Target is |
279 | ** the index of the target item. The item with the index Start will later |
280 | ** have the index Target. All items with indices Target and above are moved |
281 | ** to higher indices. |
282 | */ |
283 | |
284 | void CollTransfer (Collection* Dest, const Collection* Source); |
285 | /* Transfer all items from Source to Dest. Anything already in Dest is left |
286 | ** untouched. The items in Source are not changed and are therefore in both |
287 | ** Collections on return. |
288 | */ |
289 | |
290 | void CollSort (Collection* C, |
291 | int (*Compare) (void*, const void*, const void*), |
292 | void* Data); |
293 | /* Sort the collection using the given compare function. The data pointer is |
294 | ** passed as *first* element to the compare function, it's not used by the |
295 | ** sort function itself. The other two pointer passed to the Compare function |
296 | ** are pointers to objects. |
297 | */ |
298 | |
299 | |
300 | |
301 | /* End of coll.h */ |
302 | |
303 | #endif |
304 | |