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