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 */
55 const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER;
56
57
58
59 /*****************************************************************************/
60 /* Code */
61 /*****************************************************************************/
62
63
64
InitCollection(Collection * C)65 Collection* 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
DoneCollection(Collection * C)79 void 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
NewCollection(void)90 Collection* 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
FreeCollection(Collection * C)99 void 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
CollGrow(Collection * C,unsigned Size)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.
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
CollInsert(Collection * C,void * Item,unsigned Index)134 void 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)
CollAppend(Collection * C,void * Item)159 void 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)
CollAt(const Collection * C,unsigned Index)170 void* 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)
CollConstAt(const Collection * C,unsigned Index)184 const 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)
CollLast(Collection * C)198 void* 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)
CollConstLast(const Collection * C)212 const 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)
CollPop(Collection * C)226 void* 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
CollIndex(Collection * C,const void * Item)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.
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
CollDelete(Collection * C,unsigned Index)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.
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
CollDeleteItem(Collection * C,const void * Item)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.
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)
CollReplace(Collection * C,void * Item,unsigned Index)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.
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
CollReplaceExpand(Collection * C,void * Item,unsigned Index)309 void 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
CollMove(Collection * C,unsigned OldIndex,unsigned NewIndex)342 void 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
CollMoveMultiple(Collection * C,unsigned Start,unsigned Count,unsigned Target)366 void 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
QuickSort(Collection * C,int Lo,int Hi,int (* Compare)(void *,const void *,const void *),void * Data)429 static 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
CollTransfer(Collection * Dest,const Collection * Source)475 void 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
CollSort(Collection * C,int (* Compare)(void *,const void *,const void *),void * Data)495 void 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