1 /*****************************************************************************/
5 /* Collection (dynamic array) */
9 /* (C) 2000-2011, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
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. */
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: */
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 */
32 /*****************************************************************************/
48 /*****************************************************************************/
50 /*****************************************************************************/
54 /* An array of pointers that grows if needed */
55 typedef struct Collection Collection;
57 unsigned Count; /* Number of items in the list */
58 unsigned Size; /* Size of allocated array */
59 void** Items; /* Array with dynamic size */
62 /* An empty collection */
63 extern const Collection EmptyCollection;
65 /* Initializer for static collections */
66 #define STATIC_COLLECTION_INITIALIZER { 0, 0, 0 }
68 /* Initializer for auto collections */
69 #define AUTO_COLLECTION_INITIALIZER EmptyCollection
73 /*****************************************************************************/
75 /*****************************************************************************/
79 Collection* InitCollection (Collection* C);
80 /* Initialize a collection and return it. */
82 void DoneCollection (Collection* C);
83 /* Free the data for a collection. This will not free the data contained in
87 Collection* NewCollection (void);
88 /* Create and return a new collection */
90 void FreeCollection (Collection* C);
91 /* Free a collection */
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.
99 #if defined(HAVE_INLINE)
100 INLINE unsigned CollCount (const Collection* C)
101 /* Return the number of items in the collection */
106 # define CollCount(C) (C)->Count
109 void CollInsert (Collection* C, void* Item, unsigned Index);
110 /* Insert the data at the given position in the collection */
112 #if defined(HAVE_INLINE)
113 INLINE void CollAppend (Collection* C, void* Item)
114 /* Append an item to the end of the collection */
116 /* Insert the item at the end of the current list */
117 CollInsert (C, Item, C->Count);
120 void CollAppend (Collection* C, void* Item);
121 /* Append an item to the end of the collection */
124 #if defined(HAVE_INLINE)
125 INLINE void* CollAt (const Collection* C, unsigned Index)
126 /* Return the item at the given index */
128 /* Check the index */
129 PRECONDITION (Index < C->Count);
131 /* Return the element */
132 return C->Items[Index];
135 void* CollAt (const Collection* C, unsigned Index);
136 /* Return the item at the given index */
139 #if defined(HAVE_INLINE)
140 INLINE void* CollAtUnchecked (const Collection* C, unsigned Index)
141 /* Return the item at the given index */
143 /* Return the element */
144 return C->Items[Index];
147 # define CollAtUnchecked(C, Index) ((C)->Items[(Index)])
150 #if defined(HAVE_INLINE)
151 INLINE const void* CollConstAt (const Collection* C, unsigned Index)
152 /* Return the item at the given index */
154 /* Check the index */
155 PRECONDITION (Index < C->Count);
157 /* Return the element */
158 return C->Items[Index];
161 const void* CollConstAt (const Collection* C, unsigned Index);
162 /* Return the item at the given index */
165 #if defined(HAVE_INLINE)
166 INLINE void* CollLast (Collection* C)
167 /* Return the last item in a collection */
169 /* We must have at least one entry */
170 PRECONDITION (C->Count > 0);
172 /* Return the element */
173 return C->Items[C->Count-1];
176 void* CollLast (Collection* C);
177 /* Return the last item in a collection */
180 #if defined(HAVE_INLINE)
181 INLINE const void* CollConstLast (const Collection* C)
182 /* Return the last item in a collection */
184 /* We must have at least one entry */
185 PRECONDITION (C->Count > 0);
187 /* Return the element */
188 return C->Items[C->Count-1];
191 const void* CollConstLast (const Collection* C);
192 /* Return the last item in a collection */
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.
201 /* We must have at least one entry */
202 PRECONDITION (C->Count > 0);
204 /* Return the element */
205 return C->Items[--C->Count];
208 void* CollPop (Collection* C);
209 /* Remove the last segment from the stack and return it. Calls FAIL if the
210 * collection is empty.
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.
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.
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.
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.
236 /* This one is easy... */
240 # define CollDeleteAll(C) ((C)->Count = 0)
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.
249 /* Check the index */
250 PRECONDITION (Index < C->Count);
252 /* Replace the item pointer */
253 C->Items[Index] = Item;
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.
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
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 after
272 * the function has done it's work. Existing entries with indices NewIndex
273 * and up are moved one position upwards.
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
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.
290 void CollSort (Collection* C,
291 int (*Compare) (void*, const void*, const void*),
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.