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* 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 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 69 aintMap_getCount( AIntMap* map ) 70 { 71 return map->size; 72 } 73 74 void* 75 aintMap_get( AIntMap* map, int key ) 76 { 77 return aintMap_getWithDefault(map, key, NULL); 78 } 79 80 void* 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 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* 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* 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 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 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 224 aintMapIterator_done( AIntMapIterator* iter ) 225 { 226 AZERO(iter); 227 } 228
