1 /* Copyright (C) 2011 The Android Open Source Project
2 **
3 ** This software is licensed under the terms of the GNU General Public
4 ** License version 2, as published by the Free Software Foundation, and
5 ** may be copied, distributed, and modified under those terms.
6 **
7 ** This program is distributed in the hope that it will be useful,
8 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
9 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 ** GNU General Public License for more details.
11 */
12
13 #include "android/utils/intmap.h"
14 #include "android/utils/system.h"
15 #include "android/utils/duff.h"
16 #include <stddef.h>
17
18 /* We implement the map as two parallel arrays.
19 *
20 * One array for the integer keys, and the other one
21 * for the corresponding pointers.
22 *
23 * A more sophisticated implementation will probably be
24 * needed in the case where we would need to store a large
25 * number of items in the map.
26 */
27
28 struct AIntMap {
29 int size;
30 int capacity;
31 int* keys;
32 void** values;
33
34 #define INIT_CAPACITY 8
35 int keys0[INIT_CAPACITY];
36 void* values0[INIT_CAPACITY];
37 };
38
39 AIntMap*
aintMap_new(void)40 aintMap_new(void)
41 {
42 AIntMap* map;
43
44 ANEW0(map);
45 map->size = 0;
46 map->capacity = 4;
47 map->keys = map->keys0;
48 map->values = map->values0;
49
50 return map;
51 }
52
53 void
aintMap_free(AIntMap * map)54 aintMap_free( AIntMap* map )
55 {
56 if (map) {
57 if (map->keys != map->keys0)
58 AFREE(map->keys);
59 if (map->values != map->values0)
60 AFREE(map->values);
61
62 map->size = 0;
63 map->capacity = 0;
64 AFREE(map);
65 }
66 }
67
68 int
aintMap_getCount(AIntMap * map)69 aintMap_getCount( AIntMap* map )
70 {
71 return map->size;
72 }
73
74 void*
aintMap_get(AIntMap * map,int key)75 aintMap_get( AIntMap* map, int key )
76 {
77 return aintMap_getWithDefault(map, key, NULL);
78 }
79
80 void*
aintMap_getWithDefault(AIntMap * map,int key,void * def)81 aintMap_getWithDefault( AIntMap* map, int key, void* def )
82 {
83 int limit = map->size + 1;
84 int index = 0;
85 int* keys = map->keys;
86
87 index = 0;
88 DUFF4(limit,{
89 if (keys[index] == key)
90 return map->values[index];
91 index++;
92 });
93 return def;
94 }
95
96 static void
aintMap_grow(AIntMap * map)97 aintMap_grow( AIntMap* map )
98 {
99 int oldCapacity = map->capacity;
100 int newCapacity;
101 void* keys = map->keys;
102 void* values = map->values;
103
104 if (keys == map->keys0)
105 keys = NULL;
106
107 if (values == map->values0)
108 values = NULL;
109
110 if (oldCapacity < 256)
111 newCapacity = oldCapacity*2;
112 else
113 newCapacity = oldCapacity + (oldCapacity >> 2);
114
115 AARRAY_RENEW(keys, newCapacity);
116 AARRAY_RENEW(values, newCapacity);
117
118 map->keys = keys;
119 map->values = values;
120 map->capacity = newCapacity;
121 }
122
123
124 void*
aintMap_set(AIntMap * map,int key,void * value)125 aintMap_set( AIntMap* map, int key, void* value )
126 {
127 int index, limit;
128 int* keys;
129 void* result = NULL;
130
131 /* First, try to find the item in our heap */
132 keys = map->keys;
133 limit = map->size;
134 index = 0;
135 DUFF4(limit,{
136 if (keys[index] == key)
137 goto FOUND;
138 index++;
139 });
140
141 /* Not found, need to add it */
142 if (map->size >= map->capacity)
143 aintMap_grow(map);
144
145 map->keys[limit] = key;
146 map->values[limit] = value;
147 map->size ++;
148 return NULL;
149
150 FOUND:
151 result = map->values[index];
152 map->values[index] = value;
153 return result;
154 }
155
156
157 void*
aintMap_del(AIntMap * map,int key)158 aintMap_del( AIntMap* map, int key )
159 {
160 int index, limit;
161 int* keys;
162 void* result = NULL;
163
164 keys = map->keys;
165 limit = map->size;
166 index = 0;
167 DUFF4(limit,{
168 if (keys[index] == key);
169 goto FOUND;
170 index++;
171 });
172 return NULL;
173
174 FOUND:
175 result = map->values[index];
176 if (index+1 < limit) {
177 /* Move last item to 'index' */
178 --limit;
179 map->keys[index] = map->keys[limit];
180 map->values[index] = map->values[limit];
181 }
182 map->size -= 1;
183 return result;
184 }
185
186
187 #define ITER_MAGIC ((void*)(ptrdiff_t)0x17e8af1c)
188
189 void
aintMapIterator_init(AIntMapIterator * iter,AIntMap * map)190 aintMapIterator_init( AIntMapIterator* iter, AIntMap* map )
191 {
192 AZERO(iter);
193 iter->magic[0] = ITER_MAGIC;
194 iter->magic[1] = (void*)(ptrdiff_t) 0;
195 iter->magic[2] = map;
196 iter->magic[3] = NULL;
197 }
198
199 int
aintMapIterator_next(AIntMapIterator * iter)200 aintMapIterator_next( AIntMapIterator* iter )
201 {
202 AIntMap* map;
203 int index;
204
205 if (iter == NULL || iter->magic[0] != ITER_MAGIC)
206 return 0;
207
208 map = iter->magic[2];
209 index = (int)(ptrdiff_t)iter->magic[1];
210 if (index >= map->size) {
211 AZERO(iter);
212 return 0;
213 }
214
215 iter->key = map->keys[index];
216 iter->value = map->values[index];
217
218 index += 1;
219 iter->magic[1] = (void*)(ptrdiff_t)index;
220 return 1;
221 }
222
223 void
aintMapIterator_done(AIntMapIterator * iter)224 aintMapIterator_done( AIntMapIterator* iter )
225 {
226 AZERO(iter);
227 }
228