Home | History | Annotate | Download | only in utils 
      1 /* Copyright (C) 2009 The Android Open Source Project
      2 **
      3 ** This software is licensed under the terms of the GNU General Public
      4 ** License version 2, as published by the Free Software Foundation, and
      5 ** may be copied, distributed, and modified under those terms.
      6 **
      7 ** This program is distributed in the hope that it will be useful,
      8 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
      9 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     10 ** GNU General Public License for more details.
     11 */
     12 #include <android/utils/refset.h>
     13 #include <stddef.h>
     14 
     15 #define  AREFSET_STEP    5
     16 
     17 AINLINED uint32_t
     18 _arefSet_hashItem( void*  item )
     19 {
     20     uint32_t  hash;
     21 
     22     hash = (uint32_t)(ptrdiff_t)item >> 2;
     23     if (sizeof(item) > 4)
     24         hash ^= ((uint64_t)(ptrdiff_t)item >> 32);
     25 
     26     return hash;
     27 }
     28 
     29 static void**
     30 _arefSet_lookup( ARefSet*  s, void*  item)
     31 {
     32     uint32_t  hash = _arefSet_hashItem(item);
     33     unsigned  index = hash & (s->max_buckets-1);
     34 
     35     for (;;) {
     36         void**  pnode = &s->buckets[index];
     37 
     38         if (*pnode == item || *pnode == NULL)
     39             return pnode;
     40 
     41         index += AREFSET_STEP;
     42         if (index >= s->max_buckets)
     43             index -= s->max_buckets;
     44     }
     45 }
     46 
     47 static void**
     48 _arefSet_lookupInsert( ARefSet*  s, void*  item)
     49 {
     50     uint32_t  hash = _arefSet_hashItem(item);
     51     unsigned  index = hash & (s->max_buckets-1);
     52     void**    insert = NULL;
     53 
     54     for (;;) {
     55         void**  pnode = &s->buckets[index];
     56 
     57         if (*pnode == NULL) {
     58             return insert ? insert : pnode;
     59         } else if (*pnode == AREFSET_DELETED) {
     60             if (!insert)
     61                 insert = pnode;
     62         } else if (*pnode == item)
     63             return pnode;
     64 
     65         index = (index + AREFSET_STEP) & (s->max_buckets-1);
     66     }
     67 }
     68 
     69 extern ABool
     70 arefSet_has( ARefSet*  s, void*  item )
     71 {
     72     void**  lookup;
     73 
     74     if (item == NULL || s->max_buckets == 0)
     75         return 0;
     76 
     77     lookup = _arefSet_lookup(s, item);
     78     return (*lookup == item);
     79 }
     80 
     81 /* the code below assumes, in the case of a down-size,
     82  * that there aren't too many items in the set.
     83  */
     84 static void
     85 _arefSet_resize( ARefSet*  s, unsigned  newSize )
     86 {
     87     ARefSet   newSet;
     88     unsigned  nn, count = s->num_buckets;
     89 
     90     AVECTOR_INIT_ALLOC(&newSet,buckets, newSize);
     91 
     92     for (nn = 0; nn < s->max_buckets; nn++) {
     93         void*  item  = s->buckets[nn];
     94         if (item != NULL && item != AREFSET_DELETED) {
     95             void** lookup = _arefSet_lookup(&newSet, item);
     96             *lookup = item;
     97         }
     98     }
     99 
    100     AVECTOR_DONE(s,buckets);
    101     s->buckets     = newSet.buckets;
    102     s->num_buckets = count;
    103     s->max_buckets = newSet.max_buckets;
    104 }
    105 
    106 extern void
    107 arefSet_add( ARefSet*  s, void*  item )
    108 {
    109     void**  lookup;
    110 
    111     if (item == NULL)
    112         return;
    113 
    114     /* You can't add items to a set during iteration! */
    115     AASSERT(s->iteration == 0);
    116 
    117     if (s->max_buckets == 0)
    118         AVECTOR_INIT_ALLOC(s,buckets,4);
    119 
    120     lookup = _arefSet_lookupInsert(s, item);
    121     if (*lookup == item)
    122         return;
    123 
    124     *lookup = item;
    125     s->num_buckets += 1;
    126 
    127     if (s->iteration == 0) {
    128         if (s->num_buckets > s->max_buckets*0.85)
    129             _arefSet_resize(s, s->max_buckets*2);
    130     }
    131 }
    132 
    133 extern void
    134 arefSet_del( ARefSet*  s, void*  item )
    135 {
    136     void**  lookup;
    137 
    138     if (item == NULL || s->max_buckets == 0)
    139         return;
    140 
    141     lookup = _arefSet_lookup(s, item);
    142     if (*lookup != item)
    143         return;
    144 
    145     if (s->iteration == 0) {
    146         /* direct deletion */
    147         *lookup = NULL;
    148         s->num_buckets -= 1;
    149         if (s->num_buckets < s->max_buckets*0.25)
    150             _arefSet_resize(s, s->max_buckets/2);
    151     } else {
    152         /* deferred deletion */
    153         *lookup = AREFSET_DELETED;
    154         s->num_buckets -= 1;
    155         s->iteration   |= 1;
    156     }
    157 }
    158 
    159 void
    160 _arefSet_removeDeferred( ARefSet*  s )
    161 {
    162     unsigned nn, newSize;
    163 
    164     for (nn = 0; nn < s->max_buckets; nn++) {
    165         if (s->buckets[nn] == AREFSET_DELETED) {
    166             s->buckets[nn]  = NULL;
    167         }
    168     }
    169     s->iteration = 0;
    170 
    171     newSize = s->max_buckets;
    172     while (s->num_buckets < newSize*0.25)
    173         newSize /= 2;
    174 
    175     if (newSize != s->max_buckets)
    176         _arefSet_resize(s, newSize);
    177 }
    178 
    179