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 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 69 ESR_ReturnCode ArrayListCreate(ArrayList** self) 70 { 71 return ArrayListCreateWithCapacity(self, INITIAL_CAPACITY); 72 } 73 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 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 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 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 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 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 162 ESR_ReturnCode ArrayList_RemoveAll(ArrayList* self) 163 { 164 ArrayListImpl* impl = (ArrayListImpl*) self; 165 166 impl->size = 0; 167 return ESR_SUCCESS; 168 } 169 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 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 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 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 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 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
