1/*****************************************************************************/
2/* */
3/* coll.c */
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#include <stdlib.h>
37#include <string.h>
38
39/* common */
40#include "check.h"
41#include "xmalloc.h"
42
43/* cc65 */
44#include "coll.h"
45
46
47
48/*****************************************************************************/
49/* Data */
50/*****************************************************************************/
51
52
53
54/* An empty collection */
55const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER;
56
57
58
59/*****************************************************************************/
60/* Code */
61/*****************************************************************************/
62
63
64
65Collection* InitCollection (Collection* C)
66/* Initialize a collection and return it. */
67{
68 /* Intialize the fields. */
69 C->Count = 0;
70 C->Size = 0;
71 C->Items = 0;
72
73 /* Return the new struct */
74 return C;
75}
76
77
78
79void DoneCollection (Collection* C)
80/* Free the data for a collection. This will not free the data contained in
81** the collection.
82*/
83{
84 /* Free the pointer array */
85 xfree (C->Items);
86}
87
88
89
90Collection* NewCollection (void)
91/* Create and return a new collection with the given initial size */
92{
93 /* Allocate memory, intialize the collection and return it */
94 return InitCollection (xmalloc (sizeof (Collection)));
95}
96
97
98
99void FreeCollection (Collection* C)
100/* Free a collection */
101{
102 /* Free the data */
103 DoneCollection (C);
104
105 /* Free the structure itself */
106 xfree (C);
107}
108
109
110
111void 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.
115*/
116{
117 void** NewItems;
118
119 /* Ignore the call if the collection is already large enough */
120 if (Size <= C->Size) {
121 return;
122 }
123
124 /* Grow the collection */
125 C->Size = Size;
126 NewItems = xmalloc (C->Size * sizeof (void*));
127 memcpy (NewItems, C->Items, C->Count * sizeof (void*));
128 xfree (C->Items);
129 C->Items = NewItems;
130}
131
132
133
134void CollInsert (Collection* C, void* Item, unsigned Index)
135/* Insert the data at the given position in the collection */
136{
137 /* Check for invalid indices */
138 PRECONDITION (Index <= C->Count);
139
140 /* Grow the array if necessary */
141 if (C->Count >= C->Size) {
142 /* Must grow */
143 CollGrow (C, (C->Size == 0)? 4 : C->Size * 2);
144 }
145
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*));
149 }
150 ++C->Count;
151
152 /* Store the new item */
153 C->Items[Index] = Item;
154}
155
156
157
158#if !defined(HAVE_INLINE)
159void CollAppend (Collection* C, void* Item)
160/* Append an item to the end of the collection */
161{
162 /* Insert the item at the end of the current list */
163 CollInsert (C, Item, C->Count);
164}
165#endif
166
167
168
169#if !defined(HAVE_INLINE)
170void* CollAt (const Collection* C, unsigned Index)
171/* Return the item at the given index */
172{
173 /* Check the index */
174 PRECONDITION (Index < C->Count);
175
176 /* Return the element */
177 return C->Items[Index];
178}
179#endif
180
181
182
183#if !defined(HAVE_INLINE)
184const void* CollConstAt (const Collection* C, unsigned Index)
185/* Return the item at the given index */
186{
187 /* Check the index */
188 PRECONDITION (Index < C->Count);
189
190 /* Return the element */
191 return C->Items[Index];
192}
193#endif
194
195
196
197#if !defined(HAVE_INLINE)
198void* CollLast (Collection* C)
199/* Return the last item in a collection */
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-1];
206}
207#endif
208
209
210
211#if !defined(HAVE_INLINE)
212const void* CollConstLast (const Collection* C)
213/* Return the last item in a collection */
214{
215 /* We must have at least one entry */
216 PRECONDITION (C->Count > 0);
217
218 /* Return the element */
219 return C->Items[C->Count-1];
220}
221#endif
222
223
224
225#if !defined(HAVE_INLINE)
226void* CollPop (Collection* C)
227/* Remove the last segment from the stack and return it. Calls FAIL if the
228** collection is empty.
229*/
230{
231 /* We must have at least one entry */
232 PRECONDITION (C->Count > 0);
233
234 /* Return the element */
235 return C->Items[--C->Count];
236}
237#endif
238
239
240
241int 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.
244*/
245{
246 /* Linear search */
247 unsigned I;
248 for (I = 0; I < C->Count; ++I) {
249 if (Item == C->Items[I]) {
250 /* Found */
251 return (int)I;
252 }
253 }
254
255 /* Not found */
256 return -1;
257}
258
259
260
261void 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.
265*/
266{
267 /* Check the index */
268 PRECONDITION (Index < C->Count);
269
270 /* Remove the item pointer */
271 --C->Count;
272 memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
273}
274
275
276
277void 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.
280*/
281{
282 /* Get the index of the entry */
283 int Index = CollIndex (C, Item);
284 CHECK (Index >= 0);
285
286 /* Delete the item with this index */
287 --C->Count;
288 memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
289}
290
291
292
293#if !defined(HAVE_INLINE)
294void 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.
297*/
298{
299 /* Check the index */
300 PRECONDITION (Index < C->Count);
301
302 /* Replace the item pointer */
303 C->Items[Index] = Item;
304}
305#endif
306
307
308
309void CollReplaceExpand (Collection* C, void* Item, unsigned Index)
310/* If Index is a valid index for the collection, replace the item at this
311** position by the one passed. If the collection is too small, expand it,
312** filling unused pointers with NULL, then add the new item at the given
313** position.
314*/
315{
316 if (Index < C->Count) {
317 /* Collection is already large enough */
318 C->Items[Index] = Item;
319 } else {
320 /* Must expand the collection */
321 unsigned Size = C->Size;
322 if (Size == 0) {
323 Size = 4;
324 }
325 while (Index >= Size) {
326 Size *= 2;
327 }
328 CollGrow (C, Size);
329
330 /* Fill up unused slots with NULL */
331 while (C->Count < Index) {
332 C->Items[C->Count++] = 0;
333 }
334
335 /* Fill in the item */
336 C->Items[C->Count++] = Item;
337 }
338}
339
340
341
342void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex)
343/* Move an item from one position in the collection to another. OldIndex
344** is the current position of the item, NewIndex is the new index before
345** the function has done it's work. Existing entries with indices NewIndex
346** and up might be moved one position upwards.
347*/
348{
349 /* Get the item; and, remove it from the collection */
350 void* Item = CollAt (C, OldIndex);
351
352 CollDelete (C, OldIndex);
353
354 /* Correct NewIndex if needed */
355 if (NewIndex > OldIndex) {
356 /* Position has changed with removal */
357 --NewIndex;
358 }
359
360 /* Now, insert it at the new position */
361 CollInsert (C, Item, NewIndex);
362}
363
364
365
366void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target)
367/* Move a range of items from one position to another. Start is the index
368** of the first item to move, Count is the number of items and Target is
369** the index of the target item. The item with the index Start will later
370** have the index Target. All items with indices Target and above are moved
371** to higher indices.
372*/
373{
374 void** TmpItems;
375 unsigned Bytes;
376
377 /* Check the range */
378 PRECONDITION (Start < C->Count && Start + Count <= C->Count && Target <= C->Count);
379
380 /* Check for trivial parameters */
381 if (Count == 0 || Start == Target) {
382 return;
383 }
384
385 /* Calculate the raw memory space used by the items to move */
386 Bytes = Count * sizeof (void*);
387
388 /* Allocate temporary storage for the items */
389 TmpItems = xmalloc (Bytes);
390
391 /* Copy the items we have to move to the temporary storage */
392 memcpy (TmpItems, C->Items + Start, Bytes);
393
394 /* Check if the range has to be moved upwards or downwards. Move the
395 ** existing items to their final location, so that the space needed
396 ** for the items now in temporary storage is unoccupied.
397 */
398 if (Target < Start) {
399
400 /* Move downwards */
401 unsigned BytesToMove = (Start - Target) * sizeof (void*);
402 memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
403
404 } else if (Target < Start + Count) {
405
406 /* Target is inside range */
407 FAIL ("Not supported");
408
409 } else {
410
411 /* Move upwards */
412 unsigned ItemsToMove = (Target - Start - Count);
413 unsigned BytesToMove = ItemsToMove * sizeof (void*);
414 memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
415
416 /* Adjust the target index */
417 Target -= Count;
418 }
419
420 /* Move the old items to their final location */
421 memcpy (C->Items + Target, TmpItems, Bytes);
422
423 /* Delete the temporary item space */
424 xfree (TmpItems);
425}
426
427
428
429static void QuickSort (Collection* C, int Lo, int Hi,
430 int (*Compare) (void*, const void*, const void*),
431 void* Data)
432/* Internal recursive sort function. */
433{
434 /* Get a pointer to the items */
435 void** Items = C->Items;
436
437 /* Quicksort */
438 while (Hi > Lo) {
439 int I = Lo + 1;
440 int J = Hi;
441 while (I <= J) {
442 while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
443 ++I;
444 }
445 while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
446 --J;
447 }
448 if (I <= J) {
449 /* Swap I and J */
450 void* Tmp = Items[I];
451 Items[I] = Items[J];
452 Items[J] = Tmp;
453 ++I;
454 --J;
455 }
456 }
457 if (J != Lo) {
458 /* Swap J and Lo */
459 void* Tmp = Items[J];
460 Items[J] = Items[Lo];
461 Items[Lo] = Tmp;
462 }
463 if (J > (Hi + Lo) / 2) {
464 QuickSort (C, J + 1, Hi, Compare, Data);
465 Hi = J - 1;
466 } else {
467 QuickSort (C, Lo, J - 1, Compare, Data);
468 Lo = J + 1;
469 }
470 }
471}
472
473
474
475void CollTransfer (Collection* Dest, const Collection* Source)
476/* Transfer all items from Source to Dest. Anything already in Dest is left
477** untouched. The items in Source are not changed and are therefore in both
478** Collections on return.
479*/
480{
481 /* Be sure there's enough room in Dest */
482 CollGrow (Dest, Dest->Count + Source->Count);
483
484 /* Copy the items */
485 memcpy (Dest->Items + Dest->Count,
486 Source->Items,
487 Source->Count * sizeof (Source->Items[0]));
488
489 /* Bump the counter */
490 Dest->Count += Source->Count;
491}
492
493
494
495void CollSort (Collection* C,
496 int (*Compare) (void*, const void*, const void*),
497 void* Data)
498/* Sort the collection using the given compare function. The data pointer is
499** passed as *first* element to the compare function, it's not used by the
500** sort function itself. The other two pointer passed to the Compare function
501** are pointers to objects.
502*/
503{
504 if (C->Count > 1) {
505 QuickSort (C, 0, C->Count-1, Compare, Data);
506 }
507}
508