1 /*****************************************************************************/
5 /* Collection (dynamic array) */
9 /* (C) 2000-2010, 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 empty collection */
55 const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER;
59 /*****************************************************************************/
61 /*****************************************************************************/
65 Collection* InitCollection (Collection* C)
66 /* Initialize a collection and return it. */
68 /* Intialize the fields. */
73 /* Return the new struct */
79 void DoneCollection (Collection* C)
80 /* Free the data for a collection. This will not free the data contained in
84 /* Free the pointer array */
90 Collection* NewCollection (void)
91 /* Create and return a new collection with the given initial size */
93 /* Allocate memory, intialize the collection and return it */
94 return InitCollection (xmalloc (sizeof (Collection)));
99 void FreeCollection (Collection* C)
100 /* Free a collection */
105 /* Free the structure itself */
111 void CollGrow (Collection* C, unsigned Size)
112 /* Grow the collection C so it is able to hold Size items without a resize
113 * being necessary. This can be called for performance reasons if the number
114 * of items to be placed in the collection is known in advance.
119 /* Ignore the call if the collection is already large enough */
120 if (Size <= C->Size) {
124 /* Grow the collection */
126 NewItems = xmalloc (C->Size * sizeof (void*));
127 memcpy (NewItems, C->Items, C->Count * sizeof (void*));
134 void CollInsert (Collection* C, void* Item, unsigned Index)
135 /* Insert the data at the given position in the collection */
137 /* Check for invalid indices */
138 PRECONDITION (Index <= C->Count);
140 /* Grow the array if necessary */
141 if (C->Count >= C->Size) {
143 CollGrow (C, (C->Size == 0)? 8 : C->Size * 2);
146 /* Move the existing elements if needed */
147 if (C->Count != Index) {
148 memmove (C->Items+Index+1, C->Items+Index, (C->Count-Index) * sizeof (void*));
152 /* Store the new item */
153 C->Items[Index] = Item;
158 #if !defined(HAVE_INLINE)
159 void CollAppend (Collection* C, void* Item)
160 /* Append an item to the end of the collection */
162 /* Insert the item at the end of the current list */
163 CollInsert (C, Item, C->Count);
169 #if !defined(HAVE_INLINE)
170 void* CollAt (Collection* C, unsigned Index)
171 /* Return the item at the given index */
173 /* Check the index */
174 PRECONDITION (Index < C->Count);
176 /* Return the element */
177 return C->Items[Index];
183 #if !defined(HAVE_INLINE)
184 const void* CollConstAt (const Collection* C, unsigned Index)
185 /* Return the item at the given index */
187 /* Check the index */
188 PRECONDITION (Index < C->Count);
190 /* Return the element */
191 return C->Items[Index];
197 #if !defined(HAVE_INLINE)
198 void* CollLast (Collection* C)
199 /* Return the last item in a collection */
201 /* We must have at least one entry */
202 PRECONDITION (C->Count > 0);
204 /* Return the element */
205 return C->Items[C->Count-1];
211 #if !defined(HAVE_INLINE)
212 const void* CollConstLast (const Collection* C)
213 /* Return the last item in a collection */
215 /* We must have at least one entry */
216 PRECONDITION (C->Count > 0);
218 /* Return the element */
219 return C->Items[C->Count-1];
225 #if !defined(HAVE_INLINE)
226 void* CollPop (Collection* C)
227 /* Remove the last segment from the stack and return it. Calls FAIL if the
228 * collection is empty.
231 /* We must have at least one entry */
232 PRECONDITION (C->Count > 0);
234 /* Return the element */
235 return C->Items[--C->Count];
241 int CollIndex (Collection* C, const void* Item)
242 /* Return the index of the given item in the collection. Return -1 if the
243 * item was not found in the collection.
248 for (I = 0; I < C->Count; ++I) {
249 if (Item == C->Items[I]) {
261 void CollDelete (Collection* C, unsigned Index)
262 /* Remove the item with the given index from the collection. This will not
263 * free the item itself, just the pointer. All items with higher indices
264 * will get moved to a lower position.
267 /* Check the index */
268 PRECONDITION (Index < C->Count);
270 /* Remove the item pointer */
272 memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
277 void CollDeleteItem (Collection* C, const void* Item)
278 /* Delete the item pointer from the collection. The item must be in the
279 * collection, otherwise FAIL will be called.
282 /* Get the index of the entry */
283 int Index = CollIndex (C, Item);
286 /* Delete the item with this index */
288 memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
293 #if !defined(HAVE_INLINE)
294 void CollReplace (Collection* C, void* Item, unsigned Index)
295 /* Replace the item at the given position. The old item will not be freed,
296 * just the pointer will get replaced.
299 /* Check the index */
300 PRECONDITION (Index < C->Count);
302 /* Replace the item pointer */
303 C->Items[Index] = Item;
309 void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex)
310 /* Move an item from one position in the collection to another. OldIndex
311 * is the current position of the item, NewIndex is the new index after
312 * the function has done it's work. Existing entries with indices NewIndex
313 * and up are moved one position upwards.
316 /* Get the item and remove it from the collection */
317 void* Item = CollAt (C, OldIndex);
318 CollDelete (C, OldIndex);
320 /* Correct NewIndex if needed */
321 if (NewIndex >= OldIndex) {
322 /* Position has changed with removal */
326 /* Now insert it at the new position */
327 CollInsert (C, Item, NewIndex);
332 void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target)
333 /* Move a range of items from one position to another. Start is the index
334 * of the first item to move, Count is the number of items and Target is
335 * the index of the target item. The item with the index Start will later
336 * have the index Target. All items with indices Target and above are moved
343 /* Check the range */
344 PRECONDITION (Start < C->Count && Start + Count <= C->Count && Target <= C->Count);
346 /* Check for trivial parameters */
347 if (Count == 0 || Start == Target) {
351 /* Calculate the raw memory space used by the items to move */
352 Bytes = Count * sizeof (void*);
354 /* Allocate temporary storage for the items */
355 TmpItems = xmalloc (Bytes);
357 /* Copy the items we have to move to the temporary storage */
358 memcpy (TmpItems, C->Items + Start, Bytes);
360 /* Check if the range has to be moved upwards or downwards. Move the
361 * existing items to their final location, so that the space needed
362 * for the items now in temporary storage is unoccupied.
364 if (Target < Start) {
367 unsigned BytesToMove = (Start - Target) * sizeof (void*);
368 memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
370 } else if (Target < Start + Count) {
372 /* Target is inside range */
373 FAIL ("Not supported");
378 unsigned ItemsToMove = (Target - Start - Count);
379 unsigned BytesToMove = ItemsToMove * sizeof (void*);
380 memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
382 /* Adjust the target index */
386 /* Move the old items to their final location */
387 memcpy (C->Items + Target, TmpItems, Bytes);
389 /* Delete the temporary item space */
395 static void QuickSort (Collection* C, int Lo, int Hi,
396 int (*Compare) (void*, const void*, const void*),
398 /* Internal recursive sort function. */
400 /* Get a pointer to the items */
401 void** Items = C->Items;
408 while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
411 while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
416 void* Tmp = Items[I];
425 void* Tmp = Items[J];
426 Items[J] = Items[Lo];
429 if (J > (Hi + Lo) / 2) {
430 QuickSort (C, J + 1, Hi, Compare, Data);
433 QuickSort (C, Lo, J - 1, Compare, Data);
441 void CollSort (Collection* C,
442 int (*Compare) (void*, const void*, const void*),
444 /* Sort the collection using the given compare function. The data pointer is
445 * passed as *first* element to the compare function, it's not used by the
446 * sort function itself. The other two pointer passed to the Compare function
447 * are pointers to objects.
451 QuickSort (C, 0, C->Count-1, Compare, Data);