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
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) {
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
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) {
169    return (const void**)array->contents;
170}
171