1 /*---------------------------------------------------------------------------*
2 * ArrayListImpl.c *
3 * *
4 * Copyright 2007, 2008 Nuance Communciations, Inc. *
5 * *
6 * Licensed under the Apache License, Version 2.0 (the 'License'); *
7 * you may not use this file except in compliance with the License. *
8 * *
9 * You may obtain a copy of the License at *
10 * http://www.apache.org/licenses/LICENSE-2.0 *
11 * *
12 * Unless required by applicable law or agreed to in writing, software *
13 * distributed under the License is distributed on an 'AS IS' BASIS, *
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
15 * See the License for the specific language governing permissions and *
16 * limitations under the License. *
17 * *
18 *---------------------------------------------------------------------------*/
19
20
21
22 #include "ArrayList.h"
23 #include "ArrayListImpl.h"
24 #include "pmemory.h"
25
26 #define MTAG NULL
27 #define INITIAL_CAPACITY 16
28
ArrayListCreateWithCapacity(ArrayList ** self,size_t minCapacity)29 ESR_ReturnCode ArrayListCreateWithCapacity(ArrayList **self, size_t minCapacity)
30 {
31 ArrayListImpl* impl;
32
33 if (self == NULL)
34 return ESR_INVALID_ARGUMENT;
35
36 impl = NEW(ArrayListImpl, MTAG);
37
38 if (impl == NULL)
39 return ESR_OUT_OF_MEMORY;
40
41 impl->Interface.add = &ArrayList_Add;
42 impl->Interface.insertAt = &ArrayList_InsertAt;
43 impl->Interface.contains = &ArrayList_Contains;
44 impl->Interface.destroy = &ArrayList_Destroy;
45 impl->Interface.get = &ArrayList_Get;
46 impl->Interface.getSize = &ArrayList_GetSize;
47 impl->Interface.remove = &ArrayList_Remove;
48 impl->Interface.removeAtIndex = &ArrayList_RemoveAtIndex;
49 impl->Interface.removeAll = &ArrayList_RemoveAll;
50 impl->Interface.set = &ArrayList_Set;
51 impl->Interface.toStaticArray = NULL; /* Not implemented */
52 impl->Interface.clone = &ArrayList_Clone;
53
54 impl->contents = MALLOC(minCapacity * sizeof(void*), MTAG);
55 if (impl->contents == NULL)
56 {
57 FREE(impl);
58 return ESR_OUT_OF_MEMORY;
59 }
60 impl->capacity = minCapacity;
61 impl->minCapacity = minCapacity;
62 impl->size = 0;
63
64 *self = (ArrayList*) impl;
65 return ESR_SUCCESS;
66 }
67
68
ArrayListCreate(ArrayList ** self)69 ESR_ReturnCode ArrayListCreate(ArrayList** self)
70 {
71 return ArrayListCreateWithCapacity(self, INITIAL_CAPACITY);
72 }
73
ArrayList_Insert_Internal(ArrayListImpl * impl,size_t index,void * element)74 static ESR_ReturnCode ArrayList_Insert_Internal(ArrayListImpl *impl, size_t index, void *element)
75 {
76 size_t i;
77
78 if (impl->size >= impl->capacity)
79 {
80 /* enlarge buffer */
81 size_t newCapacity = impl->capacity * 2;
82 void** temp = REALLOC(impl->contents, newCapacity * sizeof(void*));
83 if (temp == NULL)
84 return ESR_OUT_OF_MEMORY;
85 impl->contents = temp;
86 impl->capacity = newCapacity;
87 }
88
89 for (i = impl->size; i > index; --i)
90 impl->contents[i] = impl->contents[i - 1];
91 ++impl->size;
92 impl->contents[index] = element;
93 return ESR_SUCCESS;
94 }
95
ArrayList_Add(ArrayList * self,void * element)96 ESR_ReturnCode ArrayList_Add(ArrayList* self, void* element)
97 {
98 ArrayListImpl *impl = (ArrayListImpl *) self;
99
100 return ArrayList_Insert_Internal(impl, impl->size, element);
101 }
102
ArrayList_InsertAt(ArrayList * self,size_t index,void * element)103 ESR_ReturnCode ArrayList_InsertAt(ArrayList *self, size_t index, void *element)
104 {
105 ArrayListImpl *impl = (ArrayListImpl *) self;
106
107 if (index > impl->size)
108 return ESR_ARGUMENT_OUT_OF_BOUNDS;
109
110 return ArrayList_Insert_Internal(impl, index, element);
111 }
112
ArrayList_Remove_Internal(ArrayListImpl * impl,size_t i)113 static ESR_ReturnCode ArrayList_Remove_Internal(ArrayListImpl *impl, size_t i)
114 {
115 --impl->size;
116 while (i < impl->size)
117 {
118 impl->contents[i] = impl->contents[i+1];
119 ++i;
120 }
121
122 if (impl->capacity > impl->minCapacity &&
123 impl->size <= impl->capacity / 4)
124 {
125 void** temp;
126 size_t newCapacity = impl->capacity / 2;
127
128 /* shrink buffer */
129 if ((temp = REALLOC(impl->contents, newCapacity * sizeof(void*))) == NULL)
130 return ESR_OUT_OF_MEMORY;
131 impl->contents = temp;
132 impl->capacity = newCapacity;
133 }
134 return ESR_SUCCESS;
135 }
136
ArrayList_Remove(ArrayList * self,const void * element)137 ESR_ReturnCode ArrayList_Remove(ArrayList* self, const void* element)
138 {
139 ArrayListImpl* impl = (ArrayListImpl*) self;
140 size_t i;
141
142 /* Remove element */
143 for (i = 0; i < impl->size; ++i)
144 {
145 if (impl->contents[i] == element)
146 return ArrayList_Remove_Internal(impl, i);
147 }
148
149 return ESR_NO_MATCH_ERROR;
150 }
151
ArrayList_RemoveAtIndex(ArrayList * self,size_t index)152 ESR_ReturnCode ArrayList_RemoveAtIndex(ArrayList* self, size_t index)
153 {
154 ArrayListImpl* impl = (ArrayListImpl*) self;
155
156 if (index >= impl->size)
157 return ESR_ARGUMENT_OUT_OF_BOUNDS;
158
159 return ArrayList_Remove_Internal(impl, index);
160 }
161
ArrayList_RemoveAll(ArrayList * self)162 ESR_ReturnCode ArrayList_RemoveAll(ArrayList* self)
163 {
164 ArrayListImpl* impl = (ArrayListImpl*) self;
165
166 impl->size = 0;
167 return ESR_SUCCESS;
168 }
169
ArrayList_Contains(ArrayList * self,const void * element,ESR_BOOL * exists)170 ESR_ReturnCode ArrayList_Contains(ArrayList* self, const void* element,
171 ESR_BOOL* exists)
172 {
173 ArrayListImpl* impl = (ArrayListImpl*) self;
174 size_t i;
175
176 for (i = 0; i < impl->size; ++i)
177 {
178 if (impl->contents[i] == element)
179 {
180 *exists = ESR_TRUE;
181 return ESR_SUCCESS;
182 }
183 }
184 *exists = ESR_FALSE;
185 return ESR_SUCCESS;
186 }
187
ArrayList_Get(ArrayList * self,size_t index,void ** element)188 ESR_ReturnCode ArrayList_Get(ArrayList* self, size_t index, void** element)
189 {
190 ArrayListImpl* impl = (ArrayListImpl*) self;
191
192 if (index >= impl->size)
193 return ESR_ARGUMENT_OUT_OF_BOUNDS;
194 *element = impl->contents[index];
195 return ESR_SUCCESS;
196 }
197
ArrayList_Set(ArrayList * self,size_t index,void * element)198 ESR_ReturnCode ArrayList_Set(ArrayList* self, size_t index, void* element)
199 {
200 ArrayListImpl* impl = (ArrayListImpl*) self;
201
202 if (index >= impl->size)
203 return ESR_ARGUMENT_OUT_OF_BOUNDS;
204 impl->contents[index] = element;
205 return ESR_SUCCESS;
206 }
207
ArrayList_GetSize(ArrayList * self,size_t * size)208 ESR_ReturnCode ArrayList_GetSize(ArrayList* self, size_t* size)
209 {
210 ArrayListImpl* impl = (ArrayListImpl*) self;
211
212 *size = impl->size;
213 return ESR_SUCCESS;
214 }
215
ArrayList_Clone(ArrayList * self,ArrayList * clone)216 ESR_ReturnCode ArrayList_Clone(ArrayList* self, ArrayList* clone)
217 {
218 size_t size, i;
219 void* element;
220 ESR_ReturnCode rc;
221
222 CHK(rc, clone->removeAll(clone));
223 CHK(rc, self->getSize(self, &size));
224 for (i = 0; i < size; ++i)
225 {
226 CHK(rc, self->get(self, i, &element));
227 CHK(rc, clone->add(clone, element));
228 }
229 return ESR_SUCCESS;
230 CLEANUP:
231 return rc;
232 }
233
ArrayList_Destroy(ArrayList * self)234 ESR_ReturnCode ArrayList_Destroy(ArrayList* self)
235 {
236 ArrayListImpl* impl = (ArrayListImpl*) self;
237
238 FREE(impl->contents);
239 FREE(self);
240 return ESR_SUCCESS;
241 }
242