array.c revision 4f6e8d7a00cbeda1e70cc15be9c4af1018bdad53 
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
22#define INITIAL_CAPACITY (4)
23
24struct Array {
25    void** contents;
26    int size;
27    int capacity;
28};
29
30Array* arrayCreate() {
31    return calloc(1, sizeof(struct Array));
32}
33
34void arrayFree(Array* array) {
35    assert(array != NULL);
36
37    // Free internal array.
38    free(array->contents);
39
40    // Free the Array itself.
41    free(array);
42}
43
44/** Returns 0 if successful, < 0 otherwise.. */
45static int ensureCapacity(Array* array, int capacity) {
46    int oldCapacity = array->capacity;
47    if (capacity > oldCapacity) {
48        int newCapacity = (oldCapacity == 0) ? INITIAL_CAPACITY : oldCapacity * 2;
49
50        // Keep doubling capacity until we surpass necessary capacity.
51        while (newCapacity < capacity) {
52            newCapacity *= 2;
53        }
54
55        void** newContents;
56        if (array->contents == NULL) {
57            // Allocate new array.
58            newContents = malloc(newCapacity * sizeof(void*));
59            if (newContents == NULL) {
60                return -1;
61            }
62        } else {
63            // Expand existing array.
64            newContents = realloc(array->contents, sizeof(void*) * newCapacity);
65            if (newContents == NULL) {
66                return -1;
67            }
68        }
69
70        array->capacity = newCapacity;
71        array->contents = newContents;
72    }
73
74    return 0;
75}
76
77int arrayAdd(Array* array, void* pointer) {
78    assert(array != NULL);
79    int size = array->size;
80    int result = ensureCapacity(array, size + 1);
81    if (result < 0) {
82        return result;
83    }
84    array->contents[size] = pointer;
85    array->size++;
86    return 0;
87}
88
89static inline void checkBounds(Array* array, int index) {
90    assert(array != NULL);
91    assert(index < array->size);
92    assert(index >= 0);
93}
94
95void* arrayGet(Array* array, int index) {
96    checkBounds(array, index);
97    return array->contents[index];
98}
99
100void* arrayRemove(Array* array, int index) {
101    checkBounds(array, index);
102
103    void* pointer = array->contents[index];
104
105    int newSize = array->size - 1;
106
107    // Shift entries left.
108    if (index != newSize) {
109        memmove(array->contents + index, array->contents + index + 1,
110                (sizeof(void*)) * (newSize - index));
111    }
112
113    array->size = newSize;
114
115    return pointer;
116}
117
118void* arraySet(Array* array, int index, void* pointer) {
119    checkBounds(array, index);
120    void* old = array->contents[index];
121    array->contents[index] = pointer;
122    return old;
123}
124
125int arraySetSize(Array* array, int newSize) {
126    assert(array != NULL);
127    assert(newSize >= 0);
128
129    int oldSize = array->size;
130
131    if (newSize > oldSize) {
132        // Expand.
133        int result = ensureCapacity(array, newSize);
134        if (result < 0) {
135            return result;
136        }
137
138        // Zero out new entries.
139        memset(array->contents + sizeof(void*) * oldSize, 0,
140                sizeof(void*) * (newSize - oldSize));
141    }
142
143    array->size = newSize;
144
145    return 0;
146}
147
148int arraySize(Array* array) {
149    assert(array != NULL);
150    return array->size;
151}
152
153const void** arrayUnwrap(Array* array) {
154    return array->contents;
155}
156