summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to 'libcutils/array.c')
-rw-r--r--libcutils/array.c155
1 files changed, 155 insertions, 0 deletions
diff --git a/libcutils/array.c b/libcutils/array.c
new file mode 100644
index 000000000..ff2c8ff12
--- /dev/null
+++ b/libcutils/array.c
@@ -0,0 +1,155 @@
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}