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
28struct 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
39AIntMap*
40aintMap_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
53void
54aintMap_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
68int
69aintMap_getCount( AIntMap* map )
70{
71    return map->size;
72}
73
74void*
75aintMap_get( AIntMap*  map, int  key )
76{
77    return aintMap_getWithDefault(map, key, NULL);
78}
79
80void*
81aintMap_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
96static void
97aintMap_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
124void*
125aintMap_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
150FOUND:
151    result = map->values[index];
152    map->values[index] = value;
153    return result;
154}
155
156
157void*
158aintMap_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
174FOUND:
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
189void
190aintMapIterator_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
199int
200aintMapIterator_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
223void
224aintMapIterator_done( AIntMapIterator* iter )
225{
226    AZERO(iter);
227}
228