Add <android/utils/intmap.h> which implements an integer-keyed map of pointers.
This will be used later to support QEMUD fast pipes.
diff --git a/Makefile.common b/Makefile.common
index e872734..09fa4a1 100644
--- a/Makefile.common
+++ b/Makefile.common
@@ -76,6 +76,7 @@
android/utils/dirscanner.c \
android/utils/filelock.c \
android/utils/ini.c \
+ android/utils/intmap.c \
android/utils/mapfile.c \
android/utils/misc.c \
android/utils/panic.c \
diff --git a/android/utils/intmap.c b/android/utils/intmap.c
new file mode 100644
index 0000000..ecb19f2
--- /dev/null
+++ b/android/utils/intmap.c
@@ -0,0 +1,227 @@
+/* Copyright (C) 2011 The Android Open Source Project
+**
+** This software is licensed under the terms of the GNU General Public
+** License version 2, as published by the Free Software Foundation, and
+** may be copied, distributed, and modified under those terms.
+**
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+** GNU General Public License for more details.
+*/
+
+#include "android/utils/intmap.h"
+#include "android/utils/system.h"
+#include "android/utils/duff.h"
+#include <stddef.h>
+
+/* We implement the map as two parallel arrays.
+ *
+ * One array for the integer keys, and the other one
+ * for the corresponding pointers.
+ *
+ * A more sophisticated implementation will probably be
+ * needed in the case where we would need to store a large
+ * number of items in the map.
+ */
+
+struct AIntMap {
+ int size;
+ int capacity;
+ int* keys;
+ void** values;
+
+#define INIT_CAPACITY 8
+ int keys0[INIT_CAPACITY];
+ void* values0[INIT_CAPACITY];
+};
+
+AIntMap*
+aintMap_new(void)
+{
+ AIntMap* map;
+
+ ANEW0(map);
+ map->size = 0;
+ map->capacity = 4;
+ map->keys = map->keys0;
+ map->values = map->values0;
+
+ return map;
+}
+
+void
+aintMap_free( AIntMap* map )
+{
+ if (map) {
+ if (map->keys != map->keys0)
+ AFREE(map->keys);
+ if (map->values != map->values0)
+ AFREE(map->values);
+
+ map->size = 0;
+ map->capacity = 0;
+ AFREE(map);
+ }
+}
+
+int
+aintMap_getCount( AIntMap* map )
+{
+ return map->size;
+}
+
+void*
+aintMap_get( AIntMap* map, int key )
+{
+ return aintMap_getWithDefault(map, key, NULL);
+}
+
+void*
+aintMap_getWithDefault( AIntMap* map, int key, void* def )
+{
+ int limit = map->size + 1;
+ int index = 0;
+ int* keys = map->keys;
+
+ index = 0;
+ DUFF4(limit,{
+ if (keys[index] == key)
+ return map->values[index];
+ index++;
+ });
+ return def;
+}
+
+static void
+aintMap_grow( AIntMap* map )
+{
+ int oldCapacity = map->capacity;
+ int newCapacity;
+ void* keys = map->keys;
+ void* values = map->values;
+
+ if (keys == map->keys0)
+ keys = NULL;
+
+ if (values == map->values0)
+ values = NULL;
+
+ if (oldCapacity < 256)
+ newCapacity = oldCapacity*2;
+ else
+ newCapacity = oldCapacity + (oldCapacity >> 2);
+
+ AARRAY_RENEW(keys, newCapacity);
+ AARRAY_RENEW(values, newCapacity);
+
+ map->keys = keys;
+ map->values = values;
+ map->capacity = newCapacity;
+}
+
+
+void*
+aintMap_set( AIntMap* map, int key, void* value )
+{
+ int index, limit;
+ int* keys;
+ void* result = NULL;
+
+ /* First, try to find the item in our heap */
+ keys = map->keys;
+ limit = map->size;
+ index = 0;
+ DUFF4(limit,{
+ if (keys[index] == key)
+ goto FOUND;
+ index++;
+ });
+
+ /* Not found, need to add it */
+ if (map->size >= map->capacity)
+ aintMap_grow(map);
+
+ map->keys[limit] = key;
+ map->values[limit] = value;
+ map->size ++;
+ return NULL;
+
+FOUND:
+ result = map->values[index];
+ map->values[index] = value;
+ return result;
+}
+
+
+void*
+aintMap_del( AIntMap* map, int key )
+{
+ int index, limit;
+ int* keys;
+ void* result = NULL;
+
+ keys = map->keys;
+ limit = map->size;
+ index = 0;
+ DUFF4(limit,{
+ if (keys[index] == key);
+ goto FOUND;
+ index++;
+ });
+ return NULL;
+
+FOUND:
+ result = map->values[index];
+ if (index+1 < limit) {
+ /* Move last item to 'index' */
+ --limit;
+ map->keys[index] = map->keys[limit];
+ map->values[index] = map->values[limit];
+ }
+ map->size -= 1;
+ return result;
+}
+
+
+#define ITER_MAGIC ((void*)(ptrdiff_t)0x17e8af1c)
+
+void
+aintMapIterator_init( AIntMapIterator* iter, AIntMap* map )
+{
+ AZERO(iter);
+ iter->magic[0] = ITER_MAGIC;
+ iter->magic[1] = (void*)(ptrdiff_t) 0;
+ iter->magic[2] = map;
+ iter->magic[3] = NULL;
+}
+
+int
+aintMapIterator_next( AIntMapIterator* iter )
+{
+ AIntMap* map;
+ int index;
+
+ if (iter == NULL || iter->magic[0] != ITER_MAGIC)
+ return 0;
+
+ map = iter->magic[2];
+ index = (int)(ptrdiff_t)iter->magic[1];
+ if (index >= map->size) {
+ AZERO(iter);
+ return 0;
+ }
+
+ iter->key = map->keys[index];
+ iter->value = map->values[index];
+
+ index += 1;
+ iter->magic[1] = (void*)(ptrdiff_t)index;
+ return 1;
+}
+
+void
+aintMapIterator_done( AIntMapIterator* iter )
+{
+ AZERO(iter);
+}
diff --git a/android/utils/intmap.h b/android/utils/intmap.h
new file mode 100644
index 0000000..6fd450a
--- /dev/null
+++ b/android/utils/intmap.h
@@ -0,0 +1,106 @@
+/* Copyright (C) 2011 The Android Open Source Project
+**
+** This software is licensed under the terms of the GNU General Public
+** License version 2, as published by the Free Software Foundation, and
+** may be copied, distributed, and modified under those terms.
+**
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+** GNU General Public License for more details.
+*/
+#ifndef _ANDROID_UTILS_INTMAP_H
+#define _ANDROID_UTILS_INTMAP_H
+
+/* A simple container that can hold a simple mapping from integers to
+ * references. I.e. a dictionary where keys are integers, and values
+ * are liberal pointer values (NULL is allowed).
+ */
+
+typedef struct AIntMap AIntMap;
+
+/* Create new integer map */
+AIntMap* aintMap_new(void);
+
+/* Returns the number of keys stored in the map */
+int aintmap_getCount( AIntMap* map );
+
+/* Returns TRUE if the map has a value for the 'key'. Necessary because
+ * NULL is a valid value for the map.
+ */
+int aintmap_has( AIntMap* map, int key );
+
+/* Get the value associated with a 'key', or NULL if not in map */
+void* aintMap_get( AIntMap* map, int key );
+
+/* Get the value associated with a 'key', or 'def' if not in map */
+void* aintMap_getWithDefault( AIntMap* map, int key, void* def );
+
+/* Set the value associated to a 'key', return the old value, if any, or NULL */
+void* aintMap_set( AIntMap* map, int key, void* value );
+
+/* Delete a given value associated to a 'key', return the old value, or NULL */
+void* aintMap_del( AIntMap* map, int key );
+
+/* Destroy a given integer map */
+void aintMap_free( AIntMap* map );
+
+/* Integer map iterator. First call aintMapIterator_init(), then call
+ * aintMapIterator_next() until it returns 0. Then finish with
+ * aintMapIterator_done().
+ *
+ * Example:
+ * AIntMapIterator iter[1];
+ * aintMapIterator_init(iter, map);
+ * while (aintMapIterator_next(iter, &key, &value)) {
+ * // do something
+ * }
+ * aintMapIterator_done(iter);
+ */
+typedef struct AIntMapIterator {
+ int key;
+ void* value;
+ void* magic[4];
+} AIntMapIterator;
+
+/* Initialize iterator. Returns -1 if the map is empty, or 0 otherwise
+ * On success, the first (key,value) pair can be read from the iterator
+ * directly.
+ */
+void aintMapIterator_init( AIntMapIterator* iter, AIntMap* map );
+
+/* Read the next (key,value) pair with an iterator, returns -1 when
+ * there isn't anything more, or 0 otherwise. On success, the key and
+ * value can be read directly from the iterator.
+ */
+int aintMapIterator_next( AIntMapIterator* iter );
+
+/* Finalize an iterator. This only needs to be called if you stop
+ * the iteration before aintMapIterator_init() or aintMapIterator_next()
+ * return -1.
+ */
+void aintMapIterator_done( AIntMapIterator* iter );
+
+#define AINTMAP_FOREACH_KEY(map, keyvarname, stmnt) \
+ do { \
+ AIntMapIterator __aintmap_foreach_iter[1]; \
+ aintMapIterator_init(__aintmap_foreach_iter, (map)); \
+ while (aintMapIterator_next(__aintmap_foreach_iter)) { \
+ int keyvarname = __aintmap_foreach_iter->key; \
+ stmnt; \
+ } \
+ aintMapIterator_done(__aintmap_foreach_iter); \
+ } while (0)
+
+#define AINTMAP_FOREACH_VALUE(map, valvarname, stmnt) \
+ do { \
+ AIntMapIterator __aintmap_foreach_iter[1]; \
+ aintMapIterator_init(__aintmap_foreach_iter, (map)); \
+ while (aintMapIterator_next(__aintmap_foreach_iter)) { \
+ void* valvarname = __aintmap_foreach_iter->value; \
+ stmnt; \
+ } \
+ aintMapIterator_done(__aintmap_foreach_iter); \
+ } while (0)
+
+#endif /* _ANDROID_UTILS_INTMAP_H */