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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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) |
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) |
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) |
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) |
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) |
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) |
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 | |
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 | |
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 | |
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) |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |