1 /*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <cutils/array.h>
18 #include <assert.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <limits.h>
22
23 #define INITIAL_CAPACITY (4)
24 #define MAX_CAPACITY ((int)(UINT_MAX/sizeof(void*)))
25
26 struct Array {
27 void** contents;
28 int size;
29 int capacity;
30 };
31
arrayCreate()32 Array* arrayCreate() {
33 return calloc(1, sizeof(struct Array));
34 }
35
arrayFree(Array * array)36 void arrayFree(Array* array) {
37 assert(array != NULL);
38
39 // Free internal array.
40 free(array->contents);
41
42 // Free the Array itself.
43 free(array);
44 }
45
46 /** Returns 0 if successful, < 0 otherwise.. */
ensureCapacity(Array * array,int capacity)47 static int ensureCapacity(Array* array, int capacity) {
48 int oldCapacity = array->capacity;
49 if (capacity > oldCapacity) {
50 int newCapacity = (oldCapacity == 0) ? INITIAL_CAPACITY : oldCapacity;
51
52 // Ensure we're not doing something nasty
53 if (capacity > MAX_CAPACITY)
54 return -1;
55
56 // Keep doubling capacity until we surpass necessary capacity.
57 while (newCapacity < capacity) {
58 int newCap = newCapacity*2;
59 // Handle integer overflows
60 if (newCap < newCapacity || newCap > MAX_CAPACITY) {
61 newCap = MAX_CAPACITY;
62 }
63 newCapacity = newCap;
64 }
65
66 // Should not happen, but better be safe than sorry
67 if (newCapacity < 0 || newCapacity > MAX_CAPACITY)
68 return -1;
69
70 void** newContents;
71 if (array->contents == NULL) {
72 // Allocate new array.
73 newContents = malloc(newCapacity * sizeof(void*));
74 if (newContents == NULL) {
75 return -1;
76 }
77 } else {
78 // Expand existing array.
79 newContents = realloc(array->contents, sizeof(void*) * newCapacity);
80 if (newContents == NULL) {
81 return -1;
82 }
83 }
84
85 array->capacity = newCapacity;
86 array->contents = newContents;
87 }
88
89 return 0;
90 }
91
arrayAdd(Array * array,void * pointer)92 int arrayAdd(Array* array, void* pointer) {
93 assert(array != NULL);
94 int size = array->size;
95 int result = ensureCapacity(array, size + 1);
96 if (result < 0) {
97 return result;
98 }
99 array->contents[size] = pointer;
100 array->size++;
101 return 0;
102 }
103
checkBounds(Array * array,int index)104 static inline void checkBounds(Array* array, int index) {
105 assert(array != NULL);
106 assert(index < array->size);
107 assert(index >= 0);
108 }
109
arrayGet(Array * array,int index)110 void* arrayGet(Array* array, int index) {
111 checkBounds(array, index);
112 return array->contents[index];
113 }
114
arrayRemove(Array * array,int index)115 void* arrayRemove(Array* array, int index) {
116 checkBounds(array, index);
117
118 void* pointer = array->contents[index];
119
120 int newSize = array->size - 1;
121
122 // Shift entries left.
123 if (index != newSize) {
124 memmove(array->contents + index, array->contents + index + 1,
125 (sizeof(void*)) * (newSize - index));
126 }
127
128 array->size = newSize;
129
130 return pointer;
131 }
132
arraySet(Array * array,int index,void * pointer)133 void* arraySet(Array* array, int index, void* pointer) {
134 checkBounds(array, index);
135 void* old = array->contents[index];
136 array->contents[index] = pointer;
137 return old;
138 }
139
arraySetSize(Array * array,int newSize)140 int arraySetSize(Array* array, int newSize) {
141 assert(array != NULL);
142 assert(newSize >= 0);
143
144 int oldSize = array->size;
145
146 if (newSize > oldSize) {
147 // Expand.
148 int result = ensureCapacity(array, newSize);
149 if (result < 0) {
150 return result;
151 }
152
153 // Zero out new entries.
154 memset(array->contents + sizeof(void*) * oldSize, 0,
155 sizeof(void*) * (newSize - oldSize));
156 }
157
158 array->size = newSize;
159
160 return 0;
161 }
162
arraySize(Array * array)163 int arraySize(Array* array) {
164 assert(array != NULL);
165 return array->size;
166 }
167
arrayUnwrap(Array * array)168 const void** arrayUnwrap(Array* array) {
169 return (const void**)array->contents;
170 }
171