diff options
author | David 'Digit' Turner <digit@android.com> | 2010-11-19 05:44:38 -0800 |
---|---|---|
committer | Android Code Review <code-review@android.com> | 2010-11-19 05:44:38 -0800 |
commit | 3aa86ac4b79c71e443d3010a84bed1da27f48880 (patch) | |
tree | 564b5c21a757454895b89b9dc74fcb0bf320da66 | |
parent | a20ae2d2f20ccbb16b58e6e45955d4f97c4dbd50 (diff) | |
parent | 347753be1d6bb07249641c84c3c582113af81941 (diff) | |
download | external_qemu-3aa86ac4b79c71e443d3010a84bed1da27f48880.zip external_qemu-3aa86ac4b79c71e443d3010a84bed1da27f48880.tar.gz external_qemu-3aa86ac4b79c71e443d3010a84bed1da27f48880.tar.bz2 |
Merge "Allow safe deletion during iteration of an ARefSet."
-rw-r--r-- | android/looper-generic.c | 8 | ||||
-rw-r--r-- | android/utils/refset.c | 52 | ||||
-rw-r--r-- | android/utils/refset.h | 10 |
3 files changed, 55 insertions, 15 deletions
diff --git a/android/looper-generic.c b/android/looper-generic.c index 38d8ab5..b471c50 100644 --- a/android/looper-generic.c +++ b/android/looper-generic.c @@ -363,10 +363,10 @@ glooper_run(Looper* ll) } if (ret > 0) { unsigned ready; + GLoopIo* io; /* Add io waiters to the pending list */ - AREFSET_FOREACH(looper->ios, io_, { - GLoopIo* io = io_; + AREFSET_FOREACH(looper->ios, io, { if (io->wanted == 0) continue; @@ -419,8 +419,8 @@ glooper_run(Looper* ll) /* Now fire the pending ios */ { - AREFSET_FOREACH(looper->pendingIos,io_,{ - GLoopIo* io = io_; + GLoopIo* io; + AREFSET_FOREACH(looper->pendingIos,io,{ io->callback(io->opaque,io->fd,io->ready); }); arefSet_clear(looper->pendingIos); 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 */ |