The Android Open Source Project | dd7bc33 | 2009-03-03 19:32:55 -0800 | [diff] [blame] | 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> |
The Android Open Source Project | e037fd7 | 2009-03-13 13:04:37 -0700 | [diff] [blame^] | 21 | #include <limits.h> |
The Android Open Source Project | dd7bc33 | 2009-03-03 19:32:55 -0800 | [diff] [blame] | 22 | |
| 23 | #define INITIAL_CAPACITY (4) |
The Android Open Source Project | e037fd7 | 2009-03-13 13:04:37 -0700 | [diff] [blame^] | 24 | #define MAX_CAPACITY ((int)(UINT_MAX/sizeof(void*))) |
The Android Open Source Project | dd7bc33 | 2009-03-03 19:32:55 -0800 | [diff] [blame] | 25 | |
| 26 | struct Array { |
| 27 | void** contents; |
| 28 | int size; |
| 29 | int capacity; |
| 30 | }; |
| 31 | |
| 32 | Array* arrayCreate() { |
| 33 | return calloc(1, sizeof(struct Array)); |
| 34 | } |
| 35 | |
| 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.. */ |
| 47 | static int ensureCapacity(Array* array, int capacity) { |
| 48 | int oldCapacity = array->capacity; |
| 49 | if (capacity > oldCapacity) { |
The Android Open Source Project | e037fd7 | 2009-03-13 13:04:37 -0700 | [diff] [blame^] | 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. |
The Android Open Source Project | dd7bc33 | 2009-03-03 19:32:55 -0800 | [diff] [blame] | 57 | while (newCapacity < capacity) { |
The Android Open Source Project | e037fd7 | 2009-03-13 13:04:37 -0700 | [diff] [blame^] | 58 | 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 Project | dd7bc33 | 2009-03-03 19:32:55 -0800 | [diff] [blame] | 64 | } |
The Android Open Source Project | e037fd7 | 2009-03-13 13:04:37 -0700 | [diff] [blame^] | 65 | |
| 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 Project | dd7bc33 | 2009-03-03 19:32:55 -0800 | [diff] [blame] | 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 | |
| 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 | |
| 104 | static inline void checkBounds(Array* array, int index) { |
| 105 | assert(array != NULL); |
| 106 | assert(index < array->size); |
| 107 | assert(index >= 0); |
| 108 | } |
| 109 | |
| 110 | void* arrayGet(Array* array, int index) { |
| 111 | checkBounds(array, index); |
| 112 | return array->contents[index]; |
| 113 | } |
| 114 | |
| 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 | |
| 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 | |
| 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 | |
| 163 | int arraySize(Array* array) { |
| 164 | assert(array != NULL); |
| 165 | return array->size; |
| 166 | } |
| 167 | |
| 168 | const void** arrayUnwrap(Array* array) { |
The Android Open Source Project | e037fd7 | 2009-03-13 13:04:37 -0700 | [diff] [blame^] | 169 | return (const void**)array->contents; |
The Android Open Source Project | dd7bc33 | 2009-03-03 19:32:55 -0800 | [diff] [blame] | 170 | } |