diff options
Diffstat (limited to 'libcutils/array.c')
-rw-r--r-- | libcutils/array.c | 155 |
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 | |||
24 | struct Array { | ||
25 | void** contents; | ||
26 | int size; | ||
27 | int capacity; | ||
28 | }; | ||
29 | |||
30 | Array* arrayCreate() { | ||
31 | return calloc(1, sizeof(struct Array)); | ||
32 | } | ||
33 | |||
34 | void 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.. */ | ||
45 | static 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 | |||
77 | int 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 | |||
89 | static inline void checkBounds(Array* array, int index) { | ||
90 | assert(array != NULL); | ||
91 | assert(index < array->size); | ||
92 | assert(index >= 0); | ||
93 | } | ||
94 | |||
95 | void* arrayGet(Array* array, int index) { | ||
96 | checkBounds(array, index); | ||
97 | return array->contents[index]; | ||
98 | } | ||
99 | |||
100 | void* 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 | |||
118 | void* 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 | |||
125 | int 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 | |||
148 | int arraySize(Array* array) { | ||
149 | assert(array != NULL); | ||
150 | return array->size; | ||
151 | } | ||
152 | |||
153 | const void** arrayUnwrap(Array* array) { | ||
154 | return array->contents; | ||
155 | } | ||