1/*****************************************************************************/
2/* */
3/* coll.h */
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#ifndef COLL_H
37#define COLL_H
38
39
40
41/* common */
42#include "attrib.h"
43#include "check.h"
44#include "inline.h"
45
46
47
48/*****************************************************************************/
49/* Data */
50/*****************************************************************************/
51
52
53
54/* An array of pointers that grows if needed */
55typedef struct Collection Collection;
56struct Collection {
57 unsigned Count; /* Number of items in the list */
58 unsigned Size; /* Size of allocated array */
59 void** Items; /* Array with dynamic size */
60};
61
62/* An empty collection */
63extern const Collection EmptyCollection;
64
65/* Initializer for static collections */
66#define STATIC_COLLECTION_INITIALIZER { 0, 0, 0 }
67
68/* Initializer for auto collections */
69#define AUTO_COLLECTION_INITIALIZER EmptyCollection
70
71
72
73/*****************************************************************************/
74/* Code */
75/*****************************************************************************/
76
77
78
79Collection* InitCollection (Collection* C);
80/* Initialize a collection and return it. */
81
82void DoneCollection (Collection* C);
83/* Free the data for a collection. This will not free the data contained in
84** the collection.
85*/
86
87Collection* NewCollection (void);
88/* Create and return a new collection */
89
90void FreeCollection (Collection* C);
91/* Free a collection */
92
93void CollGrow (Collection* C, unsigned Size);
94/* Grow the collection C so it is able to hold Size items without a resize
95** being necessary. This can be called for performance reasons if the number
96** of items to be placed in the collection is known in advance.
97*/
98
99#if defined(HAVE_INLINE)
100INLINE unsigned CollCount (const Collection* C)
101/* Return the number of items in the collection */
102{
103 return C->Count;
104}
105#else
106# define CollCount(C) (C)->Count
107#endif
108
109void CollInsert (Collection* C, void* Item, unsigned Index);
110/* Insert the data at the given position in the collection */
111
112#if defined(HAVE_INLINE)
113INLINE void CollAppend (Collection* C, void* Item)
114/* Append an item to the end of the collection */
115{
116 /* Insert the item at the end of the current list */
117 CollInsert (C, Item, C->Count);
118}
119#else
120void CollAppend (Collection* C, void* Item);
121/* Append an item to the end of the collection */
122#endif
123
124#if defined(HAVE_INLINE)
125INLINE void* CollAt (const Collection* C, unsigned Index)
126/* Return the item at the given index */
127{
128 /* Check the index */
129 PRECONDITION (Index < C->Count);
130
131 /* Return the element */
132 return C->Items[Index];
133}
134#else
135void* CollAt (const Collection* C, unsigned Index);
136/* Return the item at the given index */
137#endif
138
139#if defined(HAVE_INLINE)
140INLINE void* CollAtUnchecked (const Collection* C, unsigned Index)
141/* Return the item at the given index */
142{
143 /* Return the element */
144 return C->Items[Index];
145}
146#else
147# define CollAtUnchecked(C, Index) ((C)->Items[(Index)])
148#endif
149
150#if defined(HAVE_INLINE)
151INLINE const void* CollConstAt (const Collection* C, unsigned Index)
152/* Return the item at the given index */
153{
154 /* Check the index */
155 PRECONDITION (Index < C->Count);
156
157 /* Return the element */
158 return C->Items[Index];
159}
160#else
161const void* CollConstAt (const Collection* C, unsigned Index);
162/* Return the item at the given index */
163#endif
164
165#if defined(HAVE_INLINE)
166INLINE void* CollLast (Collection* C)
167/* Return the last item in a collection */
168{
169 /* We must have at least one entry */
170 PRECONDITION (C->Count > 0);
171
172 /* Return the element */
173 return C->Items[C->Count-1];
174}
175#else
176void* CollLast (Collection* C);
177/* Return the last item in a collection */
178#endif
179
180#if defined(HAVE_INLINE)
181INLINE const void* CollConstLast (const Collection* C)
182/* Return the last item in a collection */
183{
184 /* We must have at least one entry */
185 PRECONDITION (C->Count > 0);
186
187 /* Return the element */
188 return C->Items[C->Count-1];
189}
190#else
191const void* CollConstLast (const Collection* C);
192/* Return the last item in a collection */
193#endif
194
195#if defined(HAVE_INLINE)
196INLINE void* CollPop (Collection* C)
197/* Remove the last segment from the stack and return it. Calls FAIL if the
198** collection is empty.
199*/
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];
206}
207#else
208void* CollPop (Collection* C);
209/* Remove the last segment from the stack and return it. Calls FAIL if the
210** collection is empty.
211*/
212#endif
213
214int CollIndex (Collection* C, const void* Item);
215/* Return the index of the given item in the collection. Return -1 if the
216** item was not found in the collection.
217*/
218
219void CollDelete (Collection* C, unsigned Index);
220/* Remove the item with the given index from the collection. This will not
221** free the item itself, just the pointer. All items with higher indices
222** will get moved to a lower position.
223*/
224
225void CollDeleteItem (Collection* C, const void* Item);
226/* Delete the item pointer from the collection. The item must be in the
227** collection, otherwise FAIL will be called.
228*/
229
230#if defined(HAVE_INLINE)
231INLINE void CollDeleteAll (Collection* C)
232/* Delete all items from the given collection. This will not free the items
233** itself, it will only remove the pointers.
234*/
235{
236 /* This one is easy... */
237 C->Count = 0;
238}
239#else
240# define CollDeleteAll(C) ((C)->Count = 0)
241#endif
242
243#if defined(HAVE_INLINE)
244INLINE void CollReplace (Collection* C, void* Item, unsigned Index)
245/* Replace the item at the given position. The old item will not be freed,
246** just the pointer will get replaced.
247*/
248{
249 /* Check the index */
250 PRECONDITION (Index < C->Count);
251
252 /* Replace the item pointer */
253 C->Items[Index] = Item;
254}
255#else
256void CollReplace (Collection* C, void* Item, unsigned Index);
257/* Replace the item at the given position. The old item will not be freed,
258** just the pointer will get replaced.
259*/
260#endif
261
262void CollReplaceExpand (Collection* C, void* Item, unsigned Index);
263/* If Index is a valid index for the collection, replace the item at this
264** position by the one passed. If the collection is too small, expand it,
265** filling unused pointers with NULL, then add the new item at the given
266** position.
267*/
268
269void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex);
270/* Move an item from one position in the collection to another. OldIndex
271** is the current position of the item, NewIndex is the new index before
272** the function has done it's work. Existing entries with indices NewIndex
273** and up might be moved one position upwards.
274*/
275
276void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target);
277/* Move a range of items from one position to another. Start is the index
278** of the first item to move, Count is the number of items and Target is
279** the index of the target item. The item with the index Start will later
280** have the index Target. All items with indices Target and above are moved
281** to higher indices.
282*/
283
284void CollTransfer (Collection* Dest, const Collection* Source);
285/* Transfer all items from Source to Dest. Anything already in Dest is left
286** untouched. The items in Source are not changed and are therefore in both
287** Collections on return.
288*/
289
290void CollSort (Collection* C,
291 int (*Compare) (void*, const void*, const void*),
292 void* Data);
293/* Sort the collection using the given compare function. The data pointer is
294** passed as *first* element to the compare function, it's not used by the
295** sort function itself. The other two pointer passed to the Compare function
296** are pointers to objects.
297*/
298
299
300
301/* End of coll.h */
302
303#endif
304