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
17AINLINED 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
29static 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
47static 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
69extern ABool
70arefSet_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 */
84static 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
106extern void
107arefSet_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
133extern void
134arefSet_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
159void
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