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
_arefSet_hashItem(void * item)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**
_arefSet_lookup(ARefSet * s,void * item)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**
_arefSet_lookupInsert(ARefSet * s,void * item)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
arefSet_has(ARefSet * s,void * item)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
_arefSet_resize(ARefSet * s,unsigned newSize)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
arefSet_add(ARefSet * s,void * item)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
arefSet_del(ARefSet * s,void * item)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
_arefSet_removeDeferred(ARefSet * s)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