Allow safe deletion during iteration of an ARefSet.

+ make AREFSET_FOREACH take the name of an existing type variable
  which avoids an annoying type-cast in each statement.

Change-Id: Icf9d886601a9876fa29c15eb0e60a9bf6c8ec163

2 files changed, 51 insertions, 11 deletions

diff --git a/android/utils/refset.c b/android/utils/refset.c
index bb9a7f1..11399b4 100644
--- a/android/utils/refset.c
+++ b/android/utils/refset.c
@@ -62,9 +62,7 @@ _arefSet_lookupInsert( ARefSet*  s, void*  item)
         } else if (*pnode == item)
             return pnode;
 
-        index += AREFSET_STEP;
-        if (index >= s->max_buckets)
-            index -= s->max_buckets;
+        index = (index + AREFSET_STEP) & (s->max_buckets-1);
     }
 }
 
@@ -87,7 +85,7 @@ static void
 _arefSet_resize( ARefSet*  s, unsigned  newSize )
 {
     ARefSet   newSet;
-    unsigned  nn;
+    unsigned  nn, count = s->num_buckets;
 
     AVECTOR_INIT_ALLOC(&newSet,buckets, newSize);
 
@@ -101,6 +99,7 @@ _arefSet_resize( ARefSet*  s, unsigned  newSize )
 
     AVECTOR_DONE(s,buckets);
     s->buckets     = newSet.buckets;
+    s->num_buckets = count;
     s->max_buckets = newSet.max_buckets;
 }
 
@@ -112,6 +111,9 @@ arefSet_add( ARefSet*  s, void*  item )
     if (item == NULL)
         return;
 
+    /* You can't add items to a set during iteration! */
+    AASSERT(s->iteration == 0);
+
     if (s->max_buckets == 0)
         AVECTOR_INIT_ALLOC(s,buckets,4);
 
@@ -122,8 +124,10 @@ arefSet_add( ARefSet*  s, void*  item )
     *lookup = item;
     s->num_buckets += 1;
 
-    if (s->num_buckets > s->max_buckets*0.85)
-        _arefSet_resize(s, s->max_buckets*2);
+    if (s->iteration == 0) {
+        if (s->num_buckets > s->max_buckets*0.85)
+            _arefSet_resize(s, s->max_buckets*2);
+    }
 }
 
 extern void
@@ -138,9 +142,37 @@ arefSet_del( ARefSet*  s, void*  item )
     if (*lookup != item)
         return;
 
-    *lookup = AREFSET_DELETED;
-    s->num_buckets -= 1;
+    if (s->iteration == 0) {
+        /* direct deletion */
+        *lookup = NULL;
+        s->num_buckets -= 1;
+        if (s->num_buckets < s->max_buckets*0.25)
+            _arefSet_resize(s, s->max_buckets/2);
+    } else {
+        /* deferred deletion */
+        *lookup = AREFSET_DELETED;
+        s->num_buckets -= 1;
+        s->iteration   |= 1;
+    }
+}
 
-    if (s->num_buckets < s->max_buckets*0.25)
-        _arefSet_resize(s, s->max_buckets/2);
+void
+_arefSet_removeDeferred( ARefSet*  s )
+{
+    unsigned nn, newSize;
+
+    for (nn = 0; nn < s->max_buckets; nn++) {
+        if (s->buckets[nn] == AREFSET_DELETED) {
+            s->buckets[nn]  = NULL;
+        }
+    }
+    s->iteration = 0;
+
+    newSize = s->max_buckets;
+    while (s->num_buckets < newSize*0.25)
+        newSize /= 2;
+
+    if (newSize != s->max_buckets)
+        _arefSet_resize(s, newSize);
 }
+
diff --git a/android/utils/refset.h b/android/utils/refset.h
index d734999..4db9b2b 100644
--- a/android/utils/refset.h
+++ b/android/utils/refset.h
@@ -20,6 +20,7 @@
 
 typedef struct {
     AVECTOR_DECL(void*,buckets);
+    int iteration;
 } ARefSet;
 
 AINLINED void
@@ -38,6 +39,7 @@ AINLINED void
 arefSet_clear( ARefSet*  s )
 {
     AVECTOR_CLEAR(s,buckets);
+    s->iteration = 0;
 }
 
 AINLINED int
@@ -50,19 +52,25 @@ extern ABool  arefSet_has( ARefSet*  s, void*  item );
 extern void   arefSet_add( ARefSet*  s, void*  item );
 extern void   arefSet_del( ARefSet*  s, void*  item );
 
+extern void   _arefSet_removeDeferred( ARefSet* s );
+
 #define  AREFSET_DELETED ((void*)~(size_t)0)
 
 #define  AREFSET_FOREACH(_set,_item,_statement) \
     do { \
         int  __refset_nn = 0; \
         int  __refset_max = (_set)->max_buckets; \
+        (_set)->iteration += 2; \
         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; \
+            _item = __refset_item; \
             _statement; \
         } \
+        (_set)->iteration -= 2; \
+        if ((_set)->iteration == 1) \
+            _arefSet_removeDeferred(_set); \
     } while (0)
 
 #endif /* _ANDROID_UTILS_REFSET_H */