Update android/utils/ with misc. new features.
This introduces a few new features to android/utils/ that will
be used in later patches.
+ <android/utils/assert.h> to handle assertions
+ <android/utils/vector.h> to handle dynamic arrays
+ <android/utils/reflist.h> slightly updated (more docs)
+ <android/utils/refset.h> implements a set of pointers
Change-Id: Iebc14cfefd1c0e8aaecda9958a980d40f0be610a
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 @@
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 @@
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);
+ void** items = _areflist_items(l);
+ int nn;
- 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;
- }
- }
+ 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 (item == NULL)
+ return 0;
- 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;
+ 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 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 @@
}
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 @@
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 @@
_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 @@
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 @@
#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 */