]> git.sur5r.net Git - cc65/blob - src/common/coll.c
Line number is now an unsigned
[cc65] / src / common / coll.c
1 /*****************************************************************************/
2 /*                                                                           */
3 /*                                  coll.c                                   */
4 /*                                                                           */
5 /*                        Collection (dynamic array)                         */
6 /*                                                                           */
7 /*                                                                           */
8 /*                                                                           */
9 /* (C) 2000-2010, 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)? 8 : 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 (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 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.
314  */
315 {
316     /* Get the item and remove it from the collection */
317     void* Item = CollAt (C, OldIndex);
318     CollDelete (C, OldIndex);
319
320     /* Correct NewIndex if needed */
321     if (NewIndex >= OldIndex) {
322         /* Position has changed with removal */
323         --NewIndex;
324     }
325
326     /* Now insert it at the new position */
327     CollInsert (C, Item, NewIndex);
328 }
329
330
331
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
337  * to higher indices.
338  */
339 {
340     void** TmpItems;
341     unsigned Bytes;
342
343     /* Check the range */
344     PRECONDITION (Start < C->Count && Start + Count <= C->Count && Target <= C->Count);
345
346     /* Check for trivial parameters */
347     if (Count == 0 || Start == Target) {
348         return;
349     }
350
351     /* Calculate the raw memory space used by the items to move */
352     Bytes = Count * sizeof (void*);
353
354     /* Allocate temporary storage for the items */
355     TmpItems = xmalloc (Bytes);
356
357     /* Copy the items we have to move to the temporary storage */
358     memcpy (TmpItems, C->Items + Start, Bytes);
359
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.
363      */
364     if (Target < Start) {
365
366         /* Move downwards */
367         unsigned BytesToMove = (Start - Target) * sizeof (void*);
368         memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
369
370     } else if (Target < Start + Count) {
371
372         /* Target is inside range */
373         FAIL ("Not supported");
374
375     } else {
376
377         /* Move upwards */
378         unsigned ItemsToMove = (Target - Start - Count);
379         unsigned BytesToMove = ItemsToMove * sizeof (void*);
380         memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
381
382         /* Adjust the target index */
383         Target -= Count;
384     }
385
386     /* Move the old items to their final location */
387     memcpy (C->Items + Target, TmpItems, Bytes);
388
389     /* Delete the temporary item space */
390     xfree (TmpItems);
391 }
392
393
394
395 static void QuickSort (Collection* C, int Lo, int Hi,
396                        int (*Compare) (void*, const void*, const void*),
397                        void* Data)
398 /* Internal recursive sort function. */
399 {
400     /* Get a pointer to the items */
401     void** Items = C->Items;
402
403     /* Quicksort */
404     while (Hi > Lo) {
405         int I = Lo + 1;
406         int J = Hi;
407         while (I <= J) {
408             while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
409                 ++I;
410             }
411             while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
412                 --J;
413             }
414             if (I <= J) {
415                 /* Swap I and J */
416                 void* Tmp = Items[I];
417                 Items[I]  = Items[J];
418                 Items[J]  = Tmp;
419                 ++I;
420                 --J;
421             }
422         }
423         if (J != Lo) {
424             /* Swap J and Lo */
425             void* Tmp = Items[J];
426             Items[J]  = Items[Lo];
427             Items[Lo] = Tmp;
428         }
429         if (J > (Hi + Lo) / 2) {
430             QuickSort (C, J + 1, Hi, Compare, Data);
431             Hi = J - 1;
432         } else {
433             QuickSort (C, Lo, J - 1, Compare, Data);
434             Lo = J + 1;
435         }
436     }
437 }
438
439
440
441 void CollSort (Collection* C,
442                int (*Compare) (void*, const void*, const void*),
443                void* Data)
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.
448  */
449 {
450     if (C->Count > 1) {
451         QuickSort (C, 0, C->Count-1, Compare, Data);
452     }
453 }
454
455
456