diff options
| -rw-r--r-- | Makefile.android | 8 | ||||
| -rw-r--r-- | android/skin/composer.c | 4 | ||||
| -rw-r--r-- | android/utils/assert.c | 68 | ||||
| -rw-r--r-- | android/utils/assert.h | 120 | ||||
| -rw-r--r-- | android/utils/panic.c | 46 | ||||
| -rw-r--r-- | android/utils/panic.h | 33 | ||||
| -rw-r--r-- | android/utils/reflist.c | 253 | ||||
| -rw-r--r-- | android/utils/reflist.h | 155 | ||||
| -rw-r--r-- | android/utils/refset.c | 146 | ||||
| -rw-r--r-- | android/utils/refset.h | 62 | ||||
| -rw-r--r-- | android/utils/system.c | 42 | ||||
| -rw-r--r-- | android/utils/system.h | 13 | ||||
| -rw-r--r-- | android/utils/vector.c | 33 | ||||
| -rw-r--r-- | android/utils/vector.h | 80 |
14 files changed, 933 insertions, 130 deletions
diff --git a/Makefile.android b/Makefile.android index 97bfafb..870d01e 100644 --- a/Makefile.android +++ b/Makefile.android @@ -754,18 +754,22 @@ UI_AND_CORE_SOURCES = \ sockets.c \ android/keycode-array.c \ android/charmap.c \ + android/utils/assert.c \ android/utils/bufprint.c \ android/utils/debug.c \ - android/utils/path.c \ android/utils/dirscanner.c \ android/utils/filelock.c \ + android/utils/mapfile.c \ android/utils/misc.c \ + android/utils/panic.c \ + android/utils/path.c \ android/utils/reflist.c \ + android/utils/refset.c \ android/utils/stralloc.c \ android/utils/system.c \ android/utils/tempfile.c \ android/utils/timezone.c \ - android/utils/mapfile.c \ + android/utils/vector.c \ android/avd/hw-config.c \ android/avd/info.c \ android/utils/ini.c \ diff --git a/android/skin/composer.c b/android/skin/composer.c index 6076449..ca0f123 100644 --- a/android/skin/composer.c +++ b/android/skin/composer.c @@ -254,7 +254,7 @@ skin_plate_free( SkinPlate* p ) skin_region_reset( p->any.region ); if (p->any.parent) { - areflist_del( p->any.parent->group.children, p ); + areflist_delFirst( p->any.parent->group.children, p ); } } @@ -362,7 +362,7 @@ skin_viewport_free( SkinViewport* v ) { SkinPlate* space = v->space; if (space != NULL) { - areflist_del( space->space.viewports, v ); + areflist_delFirst( space->space.viewports, v ); v->space = NULL; } skin_region_reset( v->update ); diff --git a/android/utils/assert.c b/android/utils/assert.c new file mode 100644 index 0000000..74b2c9a --- /dev/null +++ b/android/utils/assert.c @@ -0,0 +1,68 @@ +/* Copyright (C) 2009 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/assert.h" +#include "android/utils/panic.h" +#include <stdio.h> + +typedef struct { + const char* file; + long lineno; + const char* function; +} AssertLoc; + +AssertLoc* +_get_assert_loc(void) +{ + /* XXX: Use thread-local storage instead ? */ + static AssertLoc loc[1]; + return loc; +} + +void +_android_assert_loc( const char* fileName, + long fileLineno, + const char* functionName ) +{ + AssertLoc* loc = _get_assert_loc(); + + loc->file = fileName; + loc->lineno = fileLineno; + loc->function = functionName; +} + +static void +_android_assert_log_default( const char* fmt, va_list args ) +{ + vfprintf(stderr, fmt, args); +} + +static AAssertLogFunc _assert_log = _android_assert_log_default; + +void android_assert_fail(const char* messageFmt, ...) +{ + AssertLoc* loc = _get_assert_loc(); + va_list args; + + va_start(args, messageFmt); + _assert_log(messageFmt, args); + va_end(args); + + android_panic("ASSERTION FAILURE (%s:%d) in %s\n", loc->file, loc->lineno, loc->function); +} + +void android_assert_registerLog( AAssertLogFunc logger ) +{ + if (logger == NULL) + android_panic("Passing NULL to %s\n", __FUNCTION__); + + _assert_log = logger; +} diff --git a/android/utils/assert.h b/android/utils/assert.h new file mode 100644 index 0000000..320ead5 --- /dev/null +++ b/android/utils/assert.h @@ -0,0 +1,120 @@ +/* Copyright (C) 2009 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_ASSERT_H +#define ANDROID_UTILS_ASSERT_H + +#include <stdarg.h> + +#ifdef ACONFIG_USE_ASSERT + +void _android_assert_loc(const char* fileName, + long fileLineno, + const char* functionName); + +#define AASSERT_LOC() \ + _android_assert_loc(__FILE__,__LINE__,__FUNCTION__) + +# define AASSERT_FAIL(...) \ + android_assert_fail(__VA_ARGS__) + +void __attribute__((noreturn)) android_assert_fail(const char* messageFmt, ...); + +/* Assert we never reach some code point */ +# define AASSERT_UNREACHED(...) \ + do { \ + AASSERT_LOC(); \ + android_assert_fail("Unreachable code"); \ + } while (0); + + +/* Generic assertion, must be followed by formatted string parameters */ +# define AASSERT(cond,...) \ + do { \ + if (!(cond)) { \ + AASSERT_LOC(); \ + android_assert_fail(__VA_ARGS__); \ + } \ + } while (0) + +/* Assert a condition evaluates to a given boolean */ +# define AASSERT_BOOL(cond_,expected_) \ + do { \ + int cond_result_ = !!(cond_); \ + int cond_expected_ = !!(expected_); \ + if (cond_result_ != cond_expected_) { \ + AASSERT_LOC(); \ + android_assert_fail("%s is %s instead of %s\n",\ + #cond_, \ + cond_result_ ? "TRUE" : "FALSE", \ + cond_expected_ ? "TRUE" : "FALSE" ); \ + } \ + } while (0) + +/* Assert a condition evaluates to a given integer */ +# define AASSERT_INT(cond_,expected_) \ + do { \ + int cond_result_ = (cond_); \ + int cond_expected_ = (expected_); \ + if (cond_result_ != cond_expected_) { \ + AASSERT_LOC(); \ + android_assert_fail("%s is %d instead of %d\n", \ + #cond_ , cond_result_, cond_expected_); \ + } \ + } while (0) + +# define AASSERT_PTR(cond_,expected_) \ + do { \ + void* cond_result_ = (cond_); \ + void* cond_expected_ = (void*)(expected_); \ + if (cond_result_ != cond_expected_) { \ + AASSERT_LOC(); \ + android_assert_fail("%s is %p instead of %p\n", \ + #cond_ , cond_result_, cond_expected_); \ + } \ + } while (0) + +# define ANEVER_NULL(ptr_) \ + do { \ + void* never_ptr_ = (ptr_); \ + if (never_ptr_ == NULL) { \ + AASSERT_LOC(); \ + android_assert_fail("%s is NULL\n", #ptr_); \ + } \ + } while (0) + +#else /* !ACONFIG_USE_ASSERT */ + +# define AASSERT_LOC() ((void)0) +# define AASSERT_FAIL(...) ((void)0) +# define AASSERT_UNREACHED(...) ((void)0) + +/* for side-effects */ +# define AASSERT(cond,...) ((void)(cond), (void)0) +# define AASSERT_BOOL(cond,val) ((void)(cond), (void)0) +# define AASSERT_INT(cond,val) AASSERT_BOOL(cond,val) +# define AASSERT_PTR(cond,val) AASSERT_BOOL(cond,val) +# define ANEVER_NULL(ptr) ((void)(ptr), (void)0) + +#endif /* !ACONFIG_USE_ASSERT */ + +# define AASSERT_TRUE(cond_) AASSERT_BOOL(cond_,1) +# define AASSERT_FALSE(cond_) AASSERT_BOOL(cond_,0) + + +/* this can be used to redirect the assertion log to something + * other than stderr. Note that android_assert_fail also calls + * android_vpanic. + */ +typedef void (*AAssertLogFunc)( const char* fmt, va_list args ); +void android_assert_registerLog( AAssertLogFunc logger ); + +#endif /* ANDROID_UTILS_ASSERT_H */ diff --git a/android/utils/panic.c b/android/utils/panic.c new file mode 100644 index 0000000..5f64133 --- /dev/null +++ b/android/utils/panic.c @@ -0,0 +1,46 @@ +/* Copyright (C) 2008 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/panic.h" +#include <stdio.h> +#include <stdlib.h> + +static void __attribute__((noreturn)) +_android_panic_defaultHandler( const char* fmt, va_list args ) +{ + fprintf(stderr, "PANIC: "); + vfprintf(stderr, fmt, args); + exit(1); +} + +static APanicHandlerFunc _panicHandler = _android_panic_defaultHandler; + +void android_panic( const char* fmt, ... ) +{ + va_list args; + va_start(args, fmt); + android_vpanic(fmt, args); + va_end(args); +} + +/* Variant of android_vpanic which take va_list formating arguments */ +void android_vpanic( const char* fmt, va_list args ) +{ + _panicHandler(fmt, args); +} + +void android_panic_registerHandler( APanicHandlerFunc handler ) +{ + if (handler == NULL) + android_panic("Passing NULL to %s", __FUNCTION__); + + _panicHandler = handler; +} diff --git a/android/utils/panic.h b/android/utils/panic.h new file mode 100644 index 0000000..e141ef1 --- /dev/null +++ b/android/utils/panic.h @@ -0,0 +1,33 @@ +/* Copyright (C) 2008 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_PANIC_H +#define ANDROID_UTILS_PANIC_H + +#include <stdarg.h> + +/* Print formatted panic message and halts the process */ +void __attribute__((noreturn)) android_panic ( const char* fmt, ... ); + +/* Variant of android_vpanic which take va_list formating arguments */ +void __attribute__((noreturn)) android_vpanic( const char* fmt, va_list args ); + +/* Convenience macro */ +#define APANIC(...) android_panic(__VA_ARGS__) + +typedef void (*APanicHandlerFunc)(const char*, va_list) __attribute__((noreturn)); + +#ifdef ACONFIG_UNIT_TEST +/* Register a new panic handler. This should only be used for unit-testing */ +void android_panic_registerHandler( APanicHandlerFunc handler ); +#endif /* ACONFIG_UNIT_TEST */ + +#endif /* ANDROID_UTILS_PANIC_H */ diff --git a/android/utils/reflist.c b/android/utils/reflist.c index bc604cd..f439974 100644 --- a/android/utils/reflist.c +++ b/android/utils/reflist.c @@ -10,33 +10,51 @@ ** GNU General Public License for more details. */ #include "android/utils/reflist.h" +#include "android/utils/system.h" +#include "android/utils/assert.h" #include <stdlib.h> #include <string.h> +static void** _areflist_items(const ARefList* l) +{ + if (l->max == 1) + return (void**)&l->u.item0; + else + return l->u.items; +} + +static void +_areflist_checkSize0(ARefList* l) +{ + if (l->size == 0 && l->max > 1) { + AFREE(l->u.items); + l->max = 1; + l->u.item0 = NULL; + } +} + void areflist_setEmpty(ARefList* l) { if (l->iteration > 0) { /* deferred empty, set all items to NULL * to stop iterations */ - void** items = areflist_items(l); - memset(items, 0, l->count*sizeof(items[0])); + void** items = _areflist_items(l); + AARRAY_ZERO(items, l->count); l->iteration |= 1; } else { /* direct empty */ - if (l->max > 1) { - free(l->u.items); - l->max = 1; - } + l->size = 0; + _areflist_checkSize0(l); } l->count = 0; } int -areflist_indexOf(ARefList* l, void* item) +areflist_indexOf(const ARefList* l, void* item) { if (item) { - void** items = (l->max == 1) ? &l->u.item0 : l->u.items; + void** items = _areflist_items(l); void** end = items + l->count; void** ii = items; @@ -50,19 +68,28 @@ areflist_indexOf(ARefList* l, void* item) static void areflist_grow(ARefList* l, int count) { - int newcount = l->count + count; + int newcount = l->size + count; if (newcount > l->max) { - int oldmax = l->max == 1 ? 0 : l->max; - int newmax = oldmax; - void** olditems = l->max == 1 ? NULL : l->u.items; - void** newitems; + int oldmax = l->max; + int newmax; + void** items; - while (oldmax < newcount) - oldmax += (oldmax >> 1) + 4; + if (oldmax == 1) { + oldmax = 0; + items = NULL; + } else { + items = l->u.items; + } + newmax = oldmax; + while (newmax < newcount) + newmax += (newmax >> 1) + 4; - newitems = realloc(olditems, newmax*sizeof(newitems[0])); + AARRAY_RENEW(items, newmax); - l->u.items = newitems; + if (l->max == 1) + items[0] = l->u.item0; + + l->u.items = items; l->max = (uint16_t) newmax; } } @@ -74,111 +101,170 @@ areflist_add(ARefList* l, void* item) if (item) { void** items; - if (l->count >= l->max) { + if (l->size >= l->max) { areflist_grow(l, 1); } - items = areflist_items(l); - items[l->count] = item; + items = _areflist_items(l); + items[l->size] = item; + l->size += 1; l->count += 1; } } +void +areflist_append(ARefList* l, const ARefList* l2) +{ + AREFLIST_FOREACH_CONST(l2, item, { + areflist_add(l, item); + }); +} + void* -areflist_pop(ARefList* l) +areflist_popLast(ARefList* l) { void* item = NULL; - void** items = areflist_items(l); - - if (l->count > 0) { - if (l->iteration > 0) { - /* deferred deletion */ - int nn; - for (nn = l->count-1; nn > 0; nn--) { - item = items[nn]; - if (item != NULL) { - l->count -= 1; - return item; - } - } - } else { - /* normal pop */ - item = items[--l->count]; - if (l->count <= 0 && l->max > 1) { - free(l->u.items); - l->max = 1; - } - } + void** items = _areflist_items(l); + int nn; + + if (l->count == 0) + return NULL; + + for (nn = l->size; nn > 0; nn--) { + item = items[nn-1]; + if (item != NULL) + goto FOUND_LAST; + } + return NULL; + +FOUND_LAST: + /* we found the last non-NULL item in the array */ + l->count -= 1; + items[nn-1] = NULL; + + if (l->iteration == 0) { + l->size = nn; + _areflist_checkSize0(l); } return item; } ABool -areflist_del(ARefList* l, void* item) +areflist_delFirst(ARefList* l, void* item) { - if (item) { - int index = areflist_indexOf(l, item); - if (index >= 0) { - void** items = areflist_items(l); - - if (l->iteration > 0) { - /* deferred deletion */ - items[index] = NULL; - l->iteration |= 1; - } else { - /* direct deletion */ - if (l->max > 1) { - memmove(items + index, items + index + 1, l->count - index - 1); - if (--l->count == 0) { - free(l->u.items); - l->max = 1; - } - } else { - l->u.item0 = NULL; - l->count = 0; - } - } - return 1; + if (item == NULL) + return 0; + + int index = areflist_indexOf(l, item); + if (index < 0) + return 0; + + void** items = _areflist_items(l); + + if (l->iteration > 0) { + /* deferred deletion */ + items[index] = NULL; + l->iteration |= 1; + l->count -= 1; + } else { + /* direct deletion */ + if (l->max > 1) { + AARRAY_MOVE(items + index, items + index + 1, l->size - index - 1); + l->size -= 1; + l->count -= 1; + _areflist_checkSize0(l); + } else { + l->u.item0 = NULL; + l->size = 0; + l->count = 0; } } + return 1; +} + +ABool +areflist_delAll(ARefList* l, void* item) +{ + ABool result = 0; + + if (item == NULL) + return 0; + + void** items = _areflist_items(l); + int readPos = 0; + int writePos = 0; + + /* don't modify the list until we find the item + * or an EMPTY slot */ + for ( ; readPos < l->size; readPos++ ) { + if (items[readPos] == NULL || items[readPos] == item) + goto COPY_LIST; + } return 0; + +COPY_LIST: + writePos = readPos; + for ( ; readPos < l->size; readPos++ ) { + if (items[readPos] == NULL) { + continue; + } + if (items[readPos] == item) { + result = 1; + continue; + } + items[writePos] = items[readPos]; + writePos++; + } + l->count = l->size = (uint16_t) writePos; + _areflist_checkSize0(l); + + return result; } + void _areflist_remove_deferred(ARefList* l) { if (l->iteration & 1) { /* remove all NULL elements from the array */ - void** items = areflist_items(l); + void** items = _areflist_items(l); int rr = 0; int ww = 0; - for ( ; rr < l->count; rr++ ) { + for ( ; rr < l->size; rr++ ) { if (items[rr] != NULL) items[ww++] = items[rr]; } - l->count = (int16_t) ww; - - /* if the list is empty, release its array */ - if (l->count == 0 && l->max > 1) { - free(l->u.items); - l->max = 1; - } + l->count = l->size = (uint16_t) ww; + _areflist_checkSize0(l); } l->iteration = 0; } -void -areflist_copy(ARefList* dst, ARefList* src) +void +areflist_copy(ARefList* dst, const ARefList* src) { dst[0] = src[0]; if (src->max > 1) { - dst->u.items = malloc( dst->count*sizeof(void*) ); - dst->max = dst->count; + dst->max = dst->count; + AARRAY_NEW(dst->u.items, dst->max); + + void** ritems = src->u.items; + void** witems = _areflist_items(dst); + int rr = 0; + int ww = 0; + for ( ; rr < src->size; rr++ ) { + if (ritems[rr] != NULL) { + witems[ww++] = ritems[rr]; + } + } + dst->size = ww; + AASSERT_TRUE(ww == dst->count); + _areflist_checkSize0(dst); } } void* -areflist_get(ARefList* l, int n) +areflist_get(const ARefList* l, int n) { if ((unsigned)n >= (unsigned)l->count) return NULL; @@ -190,14 +276,13 @@ areflist_get(ARefList* l, int n) } void** -areflist_at(ARefList* l, int n) +_areflist_at(const ARefList* l, int n) { void** items; - if ((unsigned)n >= (unsigned)l->count) + if ((unsigned)n >= (unsigned)l->size) return NULL; - items = (l->max == 1) ? &l->u.item0 : l->u.items; - + items = _areflist_items(l); return items + n; } diff --git a/android/utils/reflist.h b/android/utils/reflist.h index dffaef8..7275f54 100644 --- a/android/utils/reflist.h +++ b/android/utils/reflist.h @@ -9,77 +9,111 @@ ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** GNU General Public License for more details. */ -#ifndef _ANDROID_UTILS_REFLIST_H -#define _ANDROID_UTILS_REFLIST_H +#ifndef _ANDROID_GRAPHICS_REFLIST_H +#define _ANDROID_GRAPHICS_REFLIST_H -#include "android/utils/system.h" +#include <inttypes.h> +#include <android/utils/system.h> -/* definitions for a smart list of references to generic objects. +/* Definitions for a smart list of references to generic objects. * supports safe deletion and addition while they are being iterated - * with AREFLIST_FOREACH() macro + * with AREFLIST_FOREACH() macro. + * + * note that you cannot add NULL to an ARefList. */ +/* Clients should ignore these implementation details, which + * we're going to explain there: + * - 'count' is the number of items in the list + * - 'size' is the number of slots in the list's array. It is + * always >= 'count'. Some slots correspond to deleted items + * and will hold a NULL value. + * - 'max' is the size of the slots array + * - 'u.item0' is used when 'max' is 1 + * - 'u.items' is the slot array if 'max > 1' + * - 'u.next' is only used for free-list storage. + */ typedef struct ARefList { - uint16_t count, max; + /* XXX: should we use uint32_t instead ? */ + uint16_t count, size, max; uint16_t iteration; union { - struct ARefList* next; - void* item0; - void** items; + void* item0; + void** items; } u; } ARefList; -AINLINED void +/* Initialize an empty ARefList */ +AINLINED void areflist_init(ARefList* l) { l->count = 0; + l->size = 0; l->max = 1; l->iteration = 0; } +/* Return the number of items in a list */ +AINLINED int +areflist_getCount(const ARefList* l) +{ + return l->count; +} + +/* Clear an ARefList */ void areflist_setEmpty(ARefList* l); +/* Finalize, i.e. clear, an ARefList */ AINLINED void areflist_done(ARefList* l) { areflist_setEmpty(l); } +/* Return TRUE iff an ARefList has no item */ AINLINED ABool -areflist_isEmpty(ARefList* l) +areflist_isEmpty(const ARefList* l) { - return (l->count == 0); + return (areflist_getCount(l) == 0); } -int areflist_indexOf(ARefList* l, void* item); +/* Return the index of 'item' in the ARefList, or -1. + * This returns -1 if 'item' is NULL. + */ +int areflist_indexOf(const ARefList* l, void* item); -AINLINED ABool -areflist_has(ARefList* l, void* item) +/* Return TRUE iff an ARefList contains 'item' */ +AINLINED ABool +areflist_has(const ARefList* l, void* item) { return areflist_indexOf(l, item) >= 0; } -/* if 'item' is not NULL, append it to the list. An item - * can be added several times to a list */ +/* Append 'item' to a list. An item can be added several + * times to the same list. Do nothing if 'item' is NULL. */ void areflist_add(ARefList* l, void* item); -/* if 'item' is not NULL, try to remove it from the list */ -/* returns TRUE iff the item was found in the list */ -ABool areflist_del(ARefList* l, void* item); +/* Remove first instance of 'item' from an ARefList. + * Returns TRUE iff the item was found in the list. */ +ABool areflist_delFirst(ARefList* l, void* item); +/* Remove all instances of 'item' from an ARefList. + * returns TRUE iff the item was found in the list */ +ABool areflist_delAll(ARefList* l, void* item); + +/* Same as areflist_add() */ AINLINED void areflist_push(ARefList* l, void* item) { areflist_add(l, item); } -void* areflist_pop(ARefList* l); +/* Remove last item from an ARefList and return it. + * NULL is returned if the list is empty */ +void* areflist_popLast(ARefList* l); -AINLINED void** -areflist_items(ARefList* l) -{ - return (l->max == 1) ? &l->u.item0 : l->u.items; -} +/* Return the n-th array entry, or NULL in case of invalid index */ +void* areflist_get(const ARefList* l, int n); AINLINED int areflist_count(ARefList* l) @@ -87,23 +121,55 @@ areflist_count(ARefList* l) return l->count; } -/* return a pointer to the n-th list array entry, - or NULL in case of invalid index */ -void** areflist_at(ARefList* l, int n); - -/* return the n-th array entry, or NULL in case of invalid index */ -void* areflist_get(ARefList* l, int n); +void areflist_append(ARefList* l, const ARefList* src); /* used internally */ void _areflist_remove_deferred(ARefList* l); +void** _areflist_at(const ARefList* l, int n); + +#define AREFLIST_LOOP(list_,itemvar_) \ + do { \ + ARefList* _reflist_loop = (list_); \ + int _reflist_loop_i = 0; \ + int _reflist_loop_n = _reflist_loop->size; \ + _reflist_loop->iteration += 2; \ + for ( ; _reflist_loop_i < _reflist_loop_n; _reflist_loop_i++ ) { \ + void** _reflist_loop_at = _areflist_at(_reflist_loop, _reflist_loop_i); \ + (itemvar_) = *(_reflist_loop_at); \ + if ((itemvar_) != NULL) { + +#define AREFLIST_LOOP_END \ + } \ + } \ + if (_reflist_loop->iteration & 1) \ + _areflist_remove_deferred(_reflist_loop); \ + } while (0); + +#define AREFLIST_LOOP_CONST(list_,itemvar_) \ + do { \ + const ARefList* _reflist_loop = (list_); \ + int _reflist_loop_i = 0; \ + int _reflist_loop_n = _reflist_loop->size; \ + for ( ; _reflist_loop_i < _reflist_loop_n; _reflist_loop_i++ ) { \ + void** _reflist_loop_at = _areflist_at(_reflist_loop, _reflist_loop_i); \ + (itemvar_) = *(_reflist_loop_at); \ + if ((itemvar_) != NULL) { + +#define AREFLIST_LOOP_DEL() \ + (_reflist_loop->iteration |= 1, *_reflist_loop_at = NULL) + +#define AREFLIST_LOOP_SET(val) \ + (_reflist_loop->iteration |= 1, *_reflist_loop_at = (val)) + + #define AREFLIST_FOREACH(list_,item_,statement_) \ ({ ARefList* _reflist = (list_); \ int _reflist_i = 0; \ - int _reflist_n = _reflist->count; \ + int _reflist_n = _reflist->size; \ _reflist->iteration += 2; \ for ( ; _reflist_i < _reflist_n; _reflist_i++ ) { \ - void** __reflist_at = areflist_at(_reflist, _reflist_i); \ + void** __reflist_at = _areflist_at(_reflist, _reflist_i); \ void* item_ = *__reflist_at; \ if (item_ != NULL) { \ statement_; \ @@ -114,16 +180,29 @@ void _areflist_remove_deferred(ARefList* l); _areflist_remove_deferred(_reflist); \ }) +#define AREFLIST_FOREACH_CONST(list_,item_,statement_) \ + ({ const ARefList* _reflist = (list_); \ + int _reflist_i = 0; \ + int _reflist_n = _reflist->size; \ + for ( ; _reflist_i < _reflist_n; _reflist_i++ ) { \ + void** __reflist_at = _areflist_at(_reflist, _reflist_i); \ + void* item_ = *__reflist_at; \ + if (item_ != NULL) { \ + statement_; \ + } \ + } \ + }) + /* use this to delete the currently iterated element */ #define AREFLIST_DEL_ITERATED() \ - ({ *_reflist_at = NULL; \ + ({ *__reflist_at = NULL; \ _reflist->iteration |= 1; }) /* use this to replace the currently iterated element */ #define AREFLIST_SET_ITERATED(item) \ - ({ *_reflist_at = (item); \ + ({ *__reflist_at = (item); \ if (item == NULL) _reflist->iteration |= 1; }) -void areflist_copy(ARefList* dst, ARefList* src); +void areflist_copy(ARefList* dst, const ARefList* src); -#endif /* _ANDROID_UTILS_REFLIST_H */ +#endif /* _ANDROID_GRAPHICS_REFLIST_H */ diff --git a/android/utils/refset.c b/android/utils/refset.c new file mode 100644 index 0000000..bb9a7f1 --- /dev/null +++ b/android/utils/refset.c @@ -0,0 +1,146 @@ +/* Copyright (C) 2009 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/refset.h> +#include <stddef.h> + +#define AREFSET_STEP 5 + +AINLINED uint32_t +_arefSet_hashItem( void* item ) +{ + uint32_t hash; + + hash = (uint32_t)(ptrdiff_t)item >> 2; + if (sizeof(item) > 4) + hash ^= ((uint64_t)(ptrdiff_t)item >> 32); + + return hash; +} + +static void** +_arefSet_lookup( ARefSet* s, void* item) +{ + uint32_t hash = _arefSet_hashItem(item); + unsigned index = hash & (s->max_buckets-1); + + for (;;) { + void** pnode = &s->buckets[index]; + + if (*pnode == item || *pnode == NULL) + return pnode; + + index += AREFSET_STEP; + if (index >= s->max_buckets) + index -= s->max_buckets; + } +} + +static void** +_arefSet_lookupInsert( ARefSet* s, void* item) +{ + uint32_t hash = _arefSet_hashItem(item); + unsigned index = hash & (s->max_buckets-1); + void** insert = NULL; + + for (;;) { + void** pnode = &s->buckets[index]; + + if (*pnode == NULL) { + return insert ? insert : pnode; + } else if (*pnode == AREFSET_DELETED) { + if (!insert) + insert = pnode; + } else if (*pnode == item) + return pnode; + + index += AREFSET_STEP; + if (index >= s->max_buckets) + index -= s->max_buckets; + } +} + +extern ABool +arefSet_has( ARefSet* s, void* item ) +{ + void** lookup; + + if (item == NULL || s->max_buckets == 0) + return 0; + + lookup = _arefSet_lookup(s, item); + return (*lookup == item); +} + +/* the code below assumes, in the case of a down-size, + * that there aren't too many items in the set. + */ +static void +_arefSet_resize( ARefSet* s, unsigned newSize ) +{ + ARefSet newSet; + unsigned nn; + + AVECTOR_INIT_ALLOC(&newSet,buckets, newSize); + + for (nn = 0; nn < s->max_buckets; nn++) { + void* item = s->buckets[nn]; + if (item != NULL && item != AREFSET_DELETED) { + void** lookup = _arefSet_lookup(&newSet, item); + *lookup = item; + } + } + + AVECTOR_DONE(s,buckets); + s->buckets = newSet.buckets; + s->max_buckets = newSet.max_buckets; +} + +extern void +arefSet_add( ARefSet* s, void* item ) +{ + void** lookup; + + if (item == NULL) + return; + + if (s->max_buckets == 0) + AVECTOR_INIT_ALLOC(s,buckets,4); + + lookup = _arefSet_lookupInsert(s, item); + if (*lookup == item) + return; + + *lookup = item; + s->num_buckets += 1; + + if (s->num_buckets > s->max_buckets*0.85) + _arefSet_resize(s, s->max_buckets*2); +} + +extern void +arefSet_del( ARefSet* s, void* item ) +{ + void** lookup; + + if (item == NULL || s->max_buckets == 0) + return; + + lookup = _arefSet_lookup(s, item); + if (*lookup != item) + return; + + *lookup = AREFSET_DELETED; + s->num_buckets -= 1; + + if (s->num_buckets < s->max_buckets*0.25) + _arefSet_resize(s, s->max_buckets/2); +} diff --git a/android/utils/refset.h b/android/utils/refset.h new file mode 100644 index 0000000..12cc240 --- /dev/null +++ b/android/utils/refset.h @@ -0,0 +1,62 @@ +/* Copyright (C) 2009 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_REFSET_H +#define _ANDROID_UTILS_REFSET_H + +#include <android/utils/vector.h> + +/* this implements a set of addresses in memory. + * NULL cannot be stored in the set. + */ + +typedef struct { + AVECTOR_DECL(void*,buckets); +} ARefSet; + +AINLINED void +arefSet_init( ARefSet* s ) +{ + AVECTOR_INIT(s,buckets); +} + +AINLINED void +arefSet_done( ARefSet* s ) +{ + AVECTOR_DONE(s,buckets); +} + +AINLINED int +arefSet_count( ARefSet* s ) +{ + return (int) AVECTOR_SIZE(s,buckets); +} + +extern ABool arefSet_has( ARefSet* s, void* item ); +extern void arefSet_add( ARefSet* s, void* item ); +extern void arefSet_del( ARefSet* s, void* item ); + +#define AREFSET_DELETED ((void*)~(size_t)0) + +#define AREFSET_FOREACH(_set,_item,_statement) \ + do { \ + int __refset_nn = 0; \ + int __refset_max = (_set)->max_buckets; \ + for ( ; __refset_nn < __refset_max; __refset_nn++ ) { \ + void* __refset_item = (_set)->buckets[__refset_nn]; \ + if (__refset_item == NULL || __refset_item == AREFSET_DELETED) \ + continue; \ + void* _item = __refset_item; \ + _statement; \ + } \ + } while (0) + +#endif /* _ANDROID_UTILS_REFSET_H */ diff --git a/android/utils/system.c b/android/utils/system.c index 5b20b4b..e65c602 100644 --- a/android/utils/system.c +++ b/android/utils/system.c @@ -10,6 +10,7 @@ ** GNU General Public License for more details. */ #include "android/utils/system.h" +#include "android/utils/assert.h" #include <stdlib.h> #include <stdio.h> #ifdef _WIN32 @@ -78,6 +79,47 @@ android_free( void* block ) free(block); } +void* +_android_array_alloc( size_t itemSize, size_t count ) +{ +#if ACONFIG_USE_ASSERT + size_t maxSize; + + if (itemSize == 0) + AASSERT_FAIL("item size is 0\n"); + + maxSize = (~(size_t)0) / itemSize; + if (count > maxSize) + AASSERT_FAIL("allocation too large (%d > %d)\n", count, maxSize); +#endif + return android_alloc(itemSize * count); +} + +void* +_android_array_alloc0( size_t itemSize, size_t count ) +{ + void* block = _android_array_alloc(itemSize, count); + memset(block, 0, itemSize*count); + return block; +} + +void* +_android_array_realloc( void* block, size_t itemSize, size_t count ) +{ +#if ACONFIG_USE_ASSERT + size_t maxSize; + + if (itemSize == 0) + AASSERT_FAIL("item size is 0\n"); + + maxSize = (~(size_t)0) / itemSize; + if (count > maxSize) + AASSERT_FAIL("reallocation of %d-bytes array too large (%d > %d)\n", + itemSize, count, maxSize); +#endif + return android_realloc(block, itemSize*count); +} + char* android_strdup( const char* str ) { diff --git a/android/utils/system.h b/android/utils/system.h index 804aa7d..5053786 100644 --- a/android/utils/system.h +++ b/android/utils/system.h @@ -14,6 +14,12 @@ #include <string.h> #include <stdint.h> +#include "android/utils/assert.h" + +/* internal helpers */ +void* _android_array_alloc( size_t itemSize, size_t count ); +void* _android_array_alloc0( size_t itemSize, size_t count ); +void* _android_array_realloc( void* block, size_t itemSize, size_t count ); /* the following functions perform 'checked allocations', i.e. * they abort if there is not enough memory. @@ -42,10 +48,9 @@ void android_free( void* block ); #define AMEM_COPY(dst,src,size) memcpy((char*)(dst),(const char*)(src),(size_t)(size)) #define AMEM_MOVE(dst,src,size) memmove((char*)(dst),(const char*)(src),(size_t)(size)) -#define AARRAY_NEW(p,count) ((p) = android_alloc(sizeof(*p)*(count))) -#define AARRAY_NEW0(p,count) ((p) = android_alloc0(sizeof(*p)*(count))) - -#define AARRAY_RENEW(p,count) ((p) = android_realloc((p),sizeof(*(p))*(count))) +#define AARRAY_NEW(p,count) (AASSERT_LOC(), (p) = _android_array_alloc(sizeof(*p),(count))) +#define AARRAY_NEW0(p,count) (AASSERT_LOC(), (p) = _android_array_alloc0(sizeof(*p),(count))) +#define AARRAY_RENEW(p,count) (AASSERT_LOC(), (p) = _android_array_realloc((p),sizeof(*(p)),(count))) #define AARRAY_COPY(dst,src,count) AMEM_COPY(dst,src,(count)*sizeof((dst)[0])) #define AARRAY_MOVE(dst,src,count) AMEM_MOVE(dst,src,(count)*sizeof((dst)[0])) diff --git a/android/utils/vector.c b/android/utils/vector.c new file mode 100644 index 0000000..9029d05 --- /dev/null +++ b/android/utils/vector.c @@ -0,0 +1,33 @@ +#include <android/utils/vector.h> +#include <limits.h> + +extern void +_avector_ensure( void** items, size_t itemSize, unsigned* pMaxItems, unsigned newCount ) +{ + unsigned oldMax = *pMaxItems; + + if (newCount > oldMax) { + unsigned newMax = oldMax; + unsigned bigMax = UINT_MAX / itemSize; + + if (itemSize == 0) { + AASSERT_FAIL("trying to reallocate array of 0-size items (count=%d)\n", newCount); + } + + if (newCount > bigMax) { + AASSERT_FAIL("trying to reallocate over-sized array of %d-bytes items (%d > %d)\n", + itemSize, newCount, bigMax); + } + + while (newMax < newCount) { + unsigned newMax2 = newMax + (newMax >> 1) + 4; + if (newMax2 < newMax || newMax2 > bigMax) + newMax2 = bigMax; + newMax = newMax2; + } + + *items = _android_array_realloc( *items, itemSize, newMax ); + *pMaxItems = newMax; + } +} + diff --git a/android/utils/vector.h b/android/utils/vector.h new file mode 100644 index 0000000..e591055 --- /dev/null +++ b/android/utils/vector.h @@ -0,0 +1,80 @@ +/* Copyright (C) 2009 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_VECTOR_H +#define _ANDROID_UTILS_VECTOR_H + +#include "android/utils/system.h" +#include "android/utils/assert.h" + +#define AVECTOR_DECL(ctype,name) \ + ctype* name; \ + unsigned num_##name; \ + unsigned max_##name \ + +#define AVECTOR_SIZE(obj,name) \ + (obj)->num_##name + +#define AVECTOR_INIT(obj,name) \ + do { \ + (obj)->name = NULL; \ + (obj)->num_##name = 0; \ + (obj)->max_##name = 0; \ + } while (0) + +#define AVECTOR_INIT_ALLOC(obj,name,count) \ + do { \ + AARRAY_NEW0( (obj)->name, (count) ); \ + (obj)->num_##name = 0; \ + (obj)->max_##name = (count); \ + } while (0) + +#define AVECTOR_DONE(obj,name) \ + do { \ + AFREE((obj)->name); \ + (obj)->num_##name = 0; \ + (obj)->max_##name = 0; \ + } while (0) + +#define AVECTOR_AT(obj,name,index) \ + (&(obj)->name[(index)]) + +#define AVECTOR_REALLOC(obj,name,newMax) \ + do { \ + AARRAY_RENEW((obj)->name,newMax); \ + (obj)->max_##name = (newMax); \ + } while(0) + +#define AVECTOR_ENSURE(obj,name,newCount) \ + do { \ + unsigned _newCount = (newCount); \ + if (_newCount > (obj)->max_##name) \ + AASSERT_LOC(); \ + _avector_ensure( (void**)&(obj)->name, sizeof((obj)->name[0]), \ + &(obj)->max_##name, _newCount ); \ + } while (0); + +extern void _avector_ensure( void** items, size_t itemSize, + unsigned* pMaxItems, unsigned newCount ); + +#define AVECTOR_FOREACH(obj,name,itemptr,statement) \ + do { \ + unsigned __vector_nn = 0; \ + unsigned __vector_max = (obj)->num_##name; \ + for ( ; __vector_nn < __vector_max; __vector_nn++ ) { \ + itemptr = &(obj)->name[__vector_nn]; \ + statement; \ + } \ + } while (0); + +/* */ + +#endif /* _ANDROID_UTILS_VECTOR_H */ |