From bbb81047a39e39021b3b10e2d86af146d514bf8c Mon Sep 17 00:00:00 2001 From: David 'Digit' Turner Date: Thu, 17 Mar 2011 14:48:44 +0100 Subject: Add which implements an integer-keyed map of pointers. This will be used later to support QEMUD fast pipes. --- android/utils/intmap.c | 227 +++++++++++++++++++++++++++++++++++++++++++++++++ android/utils/intmap.h | 106 +++++++++++++++++++++++ 2 files changed, 333 insertions(+) create mode 100644 android/utils/intmap.c create mode 100644 android/utils/intmap.h (limited to 'android/utils') 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 + +/* 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 */ -- cgit v1.1