1 /*---------------------------------------------------------------------------*
2 Project: MEM library
3 File: mem_list.c
4 Programmers: Takano Makoto
5
6 Copyright 2005 Nintendo. All rights reserved.
7
8 These coded instructions, statements, and computer programs contain
9 proprietary information of Nintendo of America Inc. and/or Nintendo
10 Company Ltd., and are protected by Federal copyright law. They may
11 not be disclosed to third parties or copied or duplicated in any form,
12 in whole or in part, without the prior written consent of Nintendo.
13 *---------------------------------------------------------------------------*/
14
15 #include <revolution.h>
16 #include <revolution/mem/list.h>
17
18 #define OBJ_TO_LINK(list,obj) ((MEMLink*)(((u32)(obj))+(list)->offset))
19
20
21 /*---------------------------------------------------------------------------*
22 Name: MEMInitList
23
24 Description: Initializes list structure.
25
26 Arguments: list: Pointer to a list structure.
27 offset: The offset of the Link-type member variable in the structure that you want to connect to the list.
28
29 This is convenient when using the offsetof macro defined in stddef.h.
30
31
32 Returns: None.
33 *---------------------------------------------------------------------------*/
34 void
MEMInitList(MEMList * list,u16 offset)35 MEMInitList( MEMList* list, u16 offset )
36 {
37 ASSERT( list != NULL );
38
39 list->headObject = NULL;
40 list->tailObject = NULL;
41 list->numObjects = 0;
42 list->offset = offset;
43 }
44
45 /*---------------------------------------------------------------------------*
46 Name: SetFirstObject_ [static]
47
48 Description: Adds the first object to the list.
49
50 Arguments: list: pointer to list structure.
51 object: pointer to the object you want to add to the list.
52
53 Returns: None.
54 *---------------------------------------------------------------------------*/
55 static void
SetFirstObject_(MEMList * list,void * object)56 SetFirstObject_( MEMList* list, void* object )
57 {
58 MEMLink* link;
59
60 ASSERT( list != NULL );
61 ASSERT( object != NULL );
62
63 link = OBJ_TO_LINK(list, object);
64
65 link->nextObject = NULL;
66 link->prevObject = NULL;
67 list->headObject = object;
68 list->tailObject = object;
69 list->numObjects++;
70 }
71
72 /*---------------------------------------------------------------------------*
73 Name: MEMAppendListObject
74
75 Description: Adds object to the end of the list.
76
77 Arguments: list: pointer to list structure.
78 object: pointer to the object you want to add to the list.
79
80 Returns: None.
81 *---------------------------------------------------------------------------*/
82 void
MEMAppendListObject(MEMList * list,void * object)83 MEMAppendListObject( MEMList* list, void* object )
84 {
85 ASSERT( list != NULL );
86 ASSERT( object != NULL );
87
88 if (list->headObject == NULL)
89 {
90 // When the list is empty.
91 SetFirstObject_(list, object);
92 }
93 else
94 {
95 MEMLink* link = OBJ_TO_LINK(list, object);
96
97 link->prevObject = list->tailObject;
98 link->nextObject = NULL;
99
100 OBJ_TO_LINK(list, list->tailObject)->nextObject = object;
101 list->tailObject = object;
102 list->numObjects++;
103 }
104 }
105
106 /*---------------------------------------------------------------------------*
107 Name: MEMPrependListObject
108
109 Description: Inserts object at the head of the list.
110
111 Arguments: list: pointer to list structure.
112 object: pointer to the object you want to add to the list.
113
114 Returns: None.
115 *---------------------------------------------------------------------------*/
116 void
MEMPrependListObject(MEMList * list,void * object)117 MEMPrependListObject( MEMList* list, void* object )
118 {
119 ASSERT( list != NULL );
120 ASSERT( object != NULL );
121
122 if (list->headObject == NULL)
123 {
124 // When the list is empty.
125 SetFirstObject_(list, object);
126 }
127 else
128 {
129 MEMLink* link = OBJ_TO_LINK(list, object);
130
131 link->prevObject = NULL;
132 link->nextObject = list->headObject;
133
134 OBJ_TO_LINK(list, list->headObject)->prevObject = object;
135 list->headObject = object;
136 list->numObjects++;
137 }
138 }
139
140 /*---------------------------------------------------------------------------*
141 Name: MEMInsertListObject
142
143 Description: Inserts object in the specified location. The object is inserted in front of the object specified in target.
144 If the target is not specified (when the target is NULL), the object is added to the end of the list.
145
146
147
148 Arguments: list: pointer to list structure.
149 target: pointer to object in the position you want to insert.
150 object: pointer to the object you want to add to the list.
151
152 Returns: None.
153 *---------------------------------------------------------------------------*/
154 void
MEMInsertListObject(MEMList * list,void * target,void * object)155 MEMInsertListObject( MEMList* list, void* target, void* object )
156 {
157 ASSERT( list != NULL );
158 ASSERT( object != NULL );
159
160 if (target == NULL)
161 {
162 // When the target is not specified, same as AppendListObject().
163 MEMAppendListObject(list, object);
164 }
165 else if (target == list->headObject)
166 {
167 // When target is the head of the list, same as PrependListObject().
168 MEMPrependListObject(list, object);
169 }
170 else
171 {
172 MEMLink* link = OBJ_TO_LINK(list, object);
173 void* prevObj = OBJ_TO_LINK(list, target)->prevObject;
174 MEMLink* prevLnk = OBJ_TO_LINK(list, prevObj);
175
176 link->prevObject = prevObj;
177 link->nextObject = target;
178 prevLnk->nextObject = object;
179 OBJ_TO_LINK(list, target)->prevObject = object;
180 list->numObjects++;
181 }
182 }
183
184 /*---------------------------------------------------------------------------*
185 Name: MEMRemoveListObject
186
187 Description: Deletes object from the list.
188
189 Arguments: list: pointer to list structure.
190 object: Pointer to the object you want to delete from the list.
191
192 Returns: None.
193 *---------------------------------------------------------------------------*/
194 void
MEMRemoveListObject(MEMList * list,void * object)195 MEMRemoveListObject( MEMList* list, void* object )
196 {
197 MEMLink* link;
198
199 ASSERT( list != NULL );
200 ASSERT( object != NULL );
201
202 link = OBJ_TO_LINK(list, object);
203
204 if (link->prevObject == NULL)
205 {
206 list->headObject = link->nextObject;
207 }
208 else
209 {
210 OBJ_TO_LINK(list, link->prevObject)->nextObject = link->nextObject;
211 }
212 if (link->nextObject == NULL)
213 {
214 list->tailObject = link->prevObject;
215 }
216 else
217 {
218 OBJ_TO_LINK(list, link->nextObject)->prevObject = link->prevObject;
219 }
220 link->prevObject = NULL;
221 link->nextObject = NULL;
222 list->numObjects--;
223 }
224
225 /*---------------------------------------------------------------------------*
226 Name: MEMGetNextListObject
227
228 Description: The object to be linked next after the object specified by 'object.'
229 If NULL has been specified for the object, the function returns the object linked to the top of the list.
230
231
232 Arguments: list: pointer to list structure.
233 object: Pointer to object in list.
234
235 Returns: Returns a pointer to the next object after the specified object.
236 If there is no next object, returns NULL.
237 *---------------------------------------------------------------------------*/
238 void*
MEMGetNextListObject(MEMList * list,void * object)239 MEMGetNextListObject( MEMList* list, void* object )
240 {
241 ASSERT( list != NULL );
242
243 if (object == NULL)
244 {
245 return list->headObject;
246 }
247 return OBJ_TO_LINK(list, object)->nextObject;
248 }
249
250 /*---------------------------------------------------------------------------*
251 Name: MEMGetPrevListObject
252
253 Description: Returns the object linked in front of the object specified by 'object.'
254 If NULL has been specified for the object, the function returns the object linked to the bottom of the list.
255
256
257 Arguments: list: pointer to list structure.
258 object: Pointer to object in list.
259
260 Returns: Returns a pointer to the previous object before the specified object.
261 If there is no object in front, returns NULL.
262 *---------------------------------------------------------------------------*/
263 void*
MEMGetPrevListObject(MEMList * list,void * object)264 MEMGetPrevListObject( MEMList* list, void* object )
265 {
266 ASSERT( list != NULL );
267
268 if (object == NULL)
269 {
270 return list->tailObject;
271 }
272 return OBJ_TO_LINK(list, object)->prevObject;
273 }
274
275 /*---------------------------------------------------------------------------*
276 Name: MEMGetNthListObject
277
278 Description: Returns a pointer to the object linked Nth on the list.
279 Note that the processing time required is longer the deeper in the list the object being linked appears due to the fact that the list is traversed in order beginning from the top.
280
281
282 Arguments: index: Object index.
283
284 Returns: Returns pointer to object. NULL is returned if there is no object corresponding to the specified index.
285
286 *---------------------------------------------------------------------------*/
287 void*
MEMGetNthListObject(MEMList * list,u16 index)288 MEMGetNthListObject( MEMList* list, u16 index )
289 {
290 int count = 0;
291 MEMLink* object = NULL;
292
293 ASSERT( list != NULL );
294
295 while ((object = (MEMLink*)MEMGetNextListObject(list, object)) != NULL)
296 {
297 if (index == count)
298 {
299 return object;
300 }
301 count++;
302 }
303 return NULL;
304 }
305
306 /*---------------------------------------------------------------------------*
307 Name: MEMCountListNode
308
309 Description: Counts the number of objects on the list. The longer the list, the more time it will require, since the count begins from the head of the list.
310
311
312
313 Arguments: list: pointer to list structure.
314
315 Returns: Number of objects on the list.
316 *---------------------------------------------------------------------------*/
317 #if 0
318 int
319 MEMCountListNode(MEMList* list)
320 {
321 int count = 0;
322 Node* object = NULL;
323
324 ASSERT( list != NULL );
325
326 while ((object = GetNextListObject(list, object)) != NULL)
327 {
328 count++;
329 }
330 return count;
331 }
332 #endif
333
334