1 /*****************************************************************************
2 ** $Source$
3 **
4 ** $Revision$
5 **
6 ** $Date$
7 **
8 ** More info: http://www.bluemsx.com
9 **
10 ** Copyright (C) 2003-2013 Daniel Vik, Akop Karapetyan
11 **
12 ** This program is free software; you can redistribute it and/or modify
13 ** it under the terms of the GNU General Public License as published by
14 ** the Free Software Foundation; either version 2 of the License, or
15 ** (at your option) any later version.
16 **
17 ** This program is distributed in the hope that it will be useful,
18 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
19 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 ** GNU General Public License for more details.
21 **
22 ** You should have received a copy of the GNU General Public License
23 ** along with this program; if not, write to the Free Software
24 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
25 **
26 ******************************************************************************
27 */
28
29 #include "ArrayList.h"
30
31 #include <stdlib.h>
32
33 struct ArrayListNode
34 {
35 struct ArrayListNode *next;
36 void *object;
37 int managed;
38 };
39
40 typedef struct ArrayListNode ArrayListNode;
41
42 struct ArrayList
43 {
44 ArrayListNode *head;
45 ArrayListNode *tail;
46 int size;
47 };
48
49 struct ArrayListIterator
50 {
51 const ArrayListNode *current;
52 const ArrayList *list;
53 };
54
55 static ArrayListNode *arrayListCreateNode(void *object, int managed);
56 static ArrayListNode *arrayListDestroyNode(ArrayListNode *node);
57 static ArrayListNode *arrayListFindNodeAtIndex(const ArrayList *list, int elementAt);
58
arrayListCreate()59 ArrayList *arrayListCreate()
60 {
61 ArrayList *list = (ArrayList *)malloc(sizeof(ArrayList));
62
63 list->head = NULL;
64 list->tail = NULL;
65 list->size = 0;
66
67 return list;
68 }
69
arrayListDestroy(ArrayList * list)70 void arrayListDestroy(ArrayList *list)
71 {
72 ArrayListNode *node = list->head;
73 while (node)
74 node = arrayListDestroyNode(node);
75
76 free(list);
77 }
78
arrayListFindNodeAtIndex(const ArrayList * list,int elementAt)79 static ArrayListNode *arrayListFindNodeAtIndex(const ArrayList *list, int elementAt)
80 {
81 int index = 0;
82 ArrayListNode *current;
83
84 if (elementAt < 0 || elementAt >= list->size)
85 return NULL;
86
87 for (current = list->head; current; current = current->next, index++)
88 if (index == elementAt)
89 return current;
90
91 return NULL;
92 }
93
arrayListCreateNode(void * object,int managed)94 static ArrayListNode *arrayListCreateNode(void *object, int managed)
95 {
96 ArrayListNode *node = (ArrayListNode *)malloc(sizeof(ArrayListNode));
97
98 if (node)
99 {
100 node->next = NULL;
101 node->object = object;
102 node->managed = managed;
103 }
104
105 return node;
106 }
107
arrayListDestroyNode(ArrayListNode * node)108 static ArrayListNode *arrayListDestroyNode(ArrayListNode *node)
109 {
110 ArrayListNode *next;
111
112 if (!node)
113 return NULL;
114
115 next = node->next;
116 if (node->managed)
117 free(node->object);
118
119 free(node);
120
121 return next; // Return the next node
122 }
123
arrayListInsert(ArrayList * list,int insertAt,void * object,int managed)124 int arrayListInsert(ArrayList *list, int insertAt, void *object, int managed)
125 {
126 ArrayListNode *newNode;
127
128 if (insertAt < 0 || insertAt > list->size)
129 return 0;
130
131 newNode = arrayListCreateNode(object, managed);
132 if (!newNode)
133 return 0;
134
135 if (insertAt == list->size)
136 {
137 // Append
138 if (list->tail)
139 list->tail->next = newNode;
140
141 list->tail = newNode;
142 }
143 else if (insertAt == 0)
144 {
145 // Prepend
146 newNode->next = list->head;
147 list->head = newNode;
148 }
149 else
150 {
151 ArrayListNode *nextNode;
152 ArrayListNode *precedingNode;
153
154 // Find the node previous to the location we're inserting
155 precedingNode = arrayListFindNodeAtIndex(list, insertAt - 1);
156 if (!precedingNode)
157 {
158 arrayListDestroyNode(newNode);
159 return 0;
160 }
161
162 // Get a reference to the current next node
163 nextNode = precedingNode->next;
164
165 // Insert the element
166 precedingNode->next = newNode;
167 newNode->next = nextNode;
168 }
169
170 if (!list->head)
171 list->head = newNode;
172
173 if (!list->tail)
174 list->tail = newNode;
175
176 list->size++;
177
178 return 1;
179 }
180
arrayListPrepend(ArrayList * list,void * object,int managed)181 int arrayListPrepend(ArrayList *list, void *object, int managed)
182 {
183 return arrayListInsert(list, 0, object, managed);
184 }
185
arrayListAppend(ArrayList * list,void * object,int managed)186 int arrayListAppend(ArrayList *list, void *object, int managed)
187 {
188 return arrayListInsert(list, list->size, object, managed);
189 }
190
arrayListRemove(ArrayList * list,int removeAt)191 int arrayListRemove(ArrayList *list, int removeAt)
192 {
193 if (removeAt < 0 || removeAt >= list->size)
194 return 0;
195
196 if (removeAt == 0)
197 {
198 // Remove head
199 ArrayListNode *next = arrayListDestroyNode(list->head);
200
201 if (list->tail == list->head)
202 list->tail = NULL;
203
204 list->head = next;
205 }
206 else
207 {
208 ArrayListNode *nodeToRemove;
209 ArrayListNode *precedingNode;
210
211 // Find the node previous to the one we're removing
212 precedingNode = arrayListFindNodeAtIndex(list, removeAt - 1);
213 if (!precedingNode)
214 return 0;
215
216 nodeToRemove = precedingNode->next;
217 if (!nodeToRemove)
218 return 0;
219
220 precedingNode->next = nodeToRemove->next;
221 if (list->tail == nodeToRemove)
222 list->tail = precedingNode;
223
224 arrayListDestroyNode(nodeToRemove);
225 }
226
227 list->size--;
228
229 return 1;
230 }
231
arrayListGetSize(const ArrayList * list)232 int arrayListGetSize(const ArrayList *list)
233 {
234 return list->size;
235 }
236
arrayListGetObject(const ArrayList * list,int elementAt)237 void *arrayListGetObject(const ArrayList *list, int elementAt)
238 {
239 ArrayListNode *node = arrayListFindNodeAtIndex(list, elementAt);
240 if (!node)
241 return NULL;
242
243 return node->object;
244 }
245
arrayListCreateIterator(const ArrayList * list)246 ArrayListIterator *arrayListCreateIterator(const ArrayList *list)
247 {
248 ArrayListIterator *iterator = (ArrayListIterator *)malloc(sizeof(ArrayListIterator));
249 if (iterator)
250 {
251 iterator->list = list;
252 iterator->current = list->head;
253 }
254
255 return iterator;
256 }
257
arrayListDestroyIterator(ArrayListIterator * iterator)258 void arrayListDestroyIterator(ArrayListIterator *iterator)
259 {
260 free(iterator);
261 }
262
arrayListIterate(ArrayListIterator * iterator)263 void *arrayListIterate(ArrayListIterator *iterator)
264 {
265 void *object;
266
267 if (!iterator->current)
268 return NULL;
269
270 object = iterator->current->object;
271 iterator->current = iterator->current->next;
272
273 return object;
274 }
275
arrayListCanIterate(const ArrayListIterator * iterator)276 int arrayListCanIterate(const ArrayListIterator *iterator)
277 {
278 return (iterator->current != NULL);
279 }