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

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 */