blob: 55ec055ff8222d00dcc5f77e40899a98d83345a6 [file] [log] [blame]
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -08001/*
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>
The Android Open Source Projecte037fd72009-03-13 13:04:37 -070021#include <limits.h>
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080022
23#define INITIAL_CAPACITY (4)
The Android Open Source Projecte037fd72009-03-13 13:04:37 -070024#define MAX_CAPACITY ((int)(UINT_MAX/sizeof(void*)))
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080025
26struct Array {
27 void** contents;
28 int size;
29 int capacity;
30};
31
32Array* arrayCreate() {
33 return calloc(1, sizeof(struct Array));
34}
35
36void 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.. */
47static int ensureCapacity(Array* array, int capacity) {
48 int oldCapacity = array->capacity;
49 if (capacity > oldCapacity) {
The Android Open Source Projecte037fd72009-03-13 13:04:37 -070050 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.
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080057 while (newCapacity < capacity) {
The Android Open Source Projecte037fd72009-03-13 13:04:37 -070058 int newCap = newCapacity*2;
59 // Handle integer overflows
60 if (newCap < newCapacity || newCap > MAX_CAPACITY) {
61 newCap = MAX_CAPACITY;
62 }
63 newCapacity = newCap;
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080064 }
The Android Open Source Projecte037fd72009-03-13 13:04:37 -070065
66 // Should not happen, but better be safe than sorry
67 if (newCapacity < 0 || newCapacity > MAX_CAPACITY)
68 return -1;
69
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -080070 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
92int 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
104static inline void checkBounds(Array* array, int index) {
105 assert(array != NULL);
106 assert(index < array->size);
107 assert(index >= 0);
108}
109
110void* arrayGet(Array* array, int index) {
111 checkBounds(array, index);
112 return array->contents[index];
113}
114
115void* 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
133void* 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
140int 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
163int arraySize(Array* array) {
164 assert(array != NULL);
165 return array->size;
166}
167
168const void** arrayUnwrap(Array* array) {
The Android Open Source Projecte037fd72009-03-13 13:04:37 -0700169 return (const void**)array->contents;
The Android Open Source Projectdd7bc332009-03-03 19:32:55 -0800170}