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