Home | History | Annotate | Download | only in libcutils 
      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 
     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) {
     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 
     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) {
    169     return (const void**)array->contents;
    170 }
    171