1/*
2Copyright (c) 2012, Broadcom Europe Ltd
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * Redistributions in binary form must reproduce the above copyright
10 notice, this list of conditions and the following disclaimer in the
11 documentation and/or other materials provided with the distribution.
12 * Neither the name of the copyright holder nor the
13 names of its contributors may be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
20DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26*/
27
28#include "interface/khronos/common/khrn_client_platform.h"
29#include "interface/khronos/common/khrn_int_generic_map.h"
30#include "interface/khronos/common/khrn_int_util.h"
31
32#ifndef KHRN_GENERIC_MAP_CMP_VALUE
33#define KHRN_GENERIC_MAP_CMP_VALUE(x, y) (x==y)
34#endif
35
36static INLINE uint32_t hash(KHRN_GENERIC_MAP_KEY_T key, uint32_t capacity)
37{
38 return (uint32_t)key & (capacity - 1);
39}
40
41static KHRN_GENERIC_MAP(ENTRY_T) *get_entry(KHRN_GENERIC_MAP(ENTRY_T) *base, uint32_t capacity, KHRN_GENERIC_MAP_KEY_T key)
42{
43 uint32_t h = hash(key, capacity);
44 while (!KHRN_GENERIC_MAP_CMP_VALUE(base[h].value, KHRN_GENERIC_MAP_VALUE_NONE)) {
45 if (base[h].key == key) {
46 return (KHRN_GENERIC_MAP_CMP_VALUE(base[h].value, KHRN_GENERIC_MAP_VALUE_DELETED)) ? NULL : (base + h);
47 }
48 if (++h == capacity) {
49 h = 0;
50 }
51 }
52 return NULL;
53}
54
55static KHRN_GENERIC_MAP(ENTRY_T) *get_free_entry(KHRN_GENERIC_MAP(ENTRY_T) *base, uint32_t capacity, KHRN_GENERIC_MAP_KEY_T key)
56{
57 uint32_t h = hash(key, capacity);
58 while ((!KHRN_GENERIC_MAP_CMP_VALUE(base[h].value, KHRN_GENERIC_MAP_VALUE_DELETED)) && (!KHRN_GENERIC_MAP_CMP_VALUE(base[h].value, KHRN_GENERIC_MAP_VALUE_NONE))) {
59 if (++h == capacity) {
60 h = 0;
61 }
62 }
63 return base + h;
64}
65
66static bool realloc_storage(KHRN_GENERIC_MAP(T) *map, uint32_t new_capacity)
67{
68#ifdef KHRN_GENERIC_MAP_RELOCATABLE
69 MEM_HANDLE_T handle = map->storage;
70 KHRN_GENERIC_MAP(ENTRY_T) *base;
71#else
72 KHRN_GENERIC_MAP(ENTRY_T) *base = map->storage;
73#endif
74 uint32_t capacity = map->capacity;
75 uint32_t i;
76
77 /*
78 new map
79 */
80
81 if (!khrn_generic_map(init)(map, new_capacity)) {
82 /* khrn_generic_map(init) fills in struct only once it is sure to succeed,
83 * so if we get here struct will be unmodified */
84 return false;
85 }
86
87 /*
88 copy entries across to new map and destroy old map
89 */
90
91#ifdef KHRN_GENERIC_MAP_RELOCATABLE
92 base = (KHRN_GENERIC_MAP(ENTRY_T) *)mem_lock(handle);
93#endif
94 for (i = 0; i != capacity; ++i) {
95 if ((!KHRN_GENERIC_MAP_CMP_VALUE(base[i].value, KHRN_GENERIC_MAP_VALUE_DELETED)) && (!KHRN_GENERIC_MAP_CMP_VALUE(base[i].value, KHRN_GENERIC_MAP_VALUE_NONE))) {
96 verify(khrn_generic_map(insert)(map, base[i].key, base[i].value)); /* khrn_generic_map(insert) can only fail if the map is too small */
97#ifdef KHRN_GENERIC_MAP_RELEASE_VALUE
98 KHRN_GENERIC_MAP_RELEASE_VALUE(base[i].value); /* new reference added by khrn_generic_map(insert) */
99#endif
100 }
101 }
102#ifdef KHRN_GENERIC_MAP_RELOCATABLE
103 mem_unlock(handle);
104 mem_release(handle);
105#else
106 KHRN_GENERIC_MAP_FREE(base);
107#endif
108
109 return true;
110}
111
112bool khrn_generic_map(init)(KHRN_GENERIC_MAP(T) *map, uint32_t capacity)
113{
114#ifdef KHRN_GENERIC_MAP_RELOCATABLE
115 MEM_HANDLE_T handle;
116#else
117 KHRN_GENERIC_MAP(ENTRY_T) *base;
118 uint32_t i;
119#endif
120
121 /*
122 we need (capacity - 1) > (capacity / 2) and (capacity - 1) > ((3 * capacity) / 4)
123 to ensure we always have at least 1 unused slot
124
125 the smallest number that satisfies these constraints is 8 (7 > 4, 7 > 6)
126 */
127
128 vcos_assert(capacity >= 8);
129 vcos_assert(is_power_of_2(capacity)); /* hash stuff assumes this */
130
131 /*
132 alloc and clear storage
133 */
134
135 #define STRINGIZE2(X) #X
136 #define STRINGIZE(X) STRINGIZE2(X) /* X will be expanded here */
137#ifdef KHRN_GENERIC_MAP_RELOCATABLE
138 handle = mem_alloc_ex(capacity * sizeof(KHRN_GENERIC_MAP(ENTRY_T)), alignof(KHRN_GENERIC_MAP(ENTRY_T)),
139 MEM_FLAG_INIT, STRINGIZE(KHRN_GENERIC_MAP(T)) ".storage", MEM_COMPACT_DISCARD); /* no term (struct containing KHRN_GENERIC_MAP(T) must call khrn_generic_map(term)()) */
140 if (handle == MEM_INVALID_HANDLE) {
141 return false;
142 }
143 /* all values already initialised to KHRN_GENERIC_MAP_VALUE_NONE */
144#else
145 base = (KHRN_GENERIC_MAP(ENTRY_T) *)KHRN_GENERIC_MAP_ALLOC(capacity * sizeof(KHRN_GENERIC_MAP(ENTRY_T)),
146 STRINGIZE(KHRN_GENERIC_MAP(T)) ".storage");
147 if (!base) {
148 return false;
149 }
150 for (i = 0; i != capacity; ++i) {
151 base[i].value = KHRN_GENERIC_MAP_VALUE_NONE;
152 }
153#endif
154 #undef STRINGIZE
155 #undef STRINGIZE2
156
157 /*
158 fill in struct (do this only once we are sure to succeed --
159 realloc_storage and khrn_generic_map(term) under gl object semantics rely
160 on this behaviour)
161 */
162
163 map->entries = 0;
164 map->deletes = 0;
165#ifdef KHRN_GENERIC_MAP_RELOCATABLE
166 map->storage = handle;
167#else
168 map->storage = base;
169#endif
170 map->capacity = capacity;
171
172 return true;
173}
174
175/*
176 in KHRN_GENERIC_MAP_RELOCATABLE mode, khrn_generic_map(term) may be called:
177 - before init: map->storage will be MEM_INVALID_HANDLE.
178 - after init fails: map is unchanged.
179 - after term: map->storage will have been set back to MEM_INVALID_HANDLE.
180*/
181
182void khrn_generic_map(term)(KHRN_GENERIC_MAP(T) *map)
183{
184#ifdef KHRN_GENERIC_MAP_RELOCATABLE
185 if (map->storage != MEM_INVALID_HANDLE) {
186#endif
187#ifdef KHRN_GENERIC_MAP_RELEASE_VALUE
188#ifdef KHRN_GENERIC_MAP_RELOCATABLE
189 KHRN_GENERIC_MAP(ENTRY_T) *base = (KHRN_GENERIC_MAP(ENTRY_T) *)mem_lock(map->storage);
190#else
191 KHRN_GENERIC_MAP(ENTRY_T) *base = map->storage;
192#endif
193 uint32_t i;
194 for (i = 0; i != map->capacity; ++i) {
195 if ((!KHRN_GENERIC_MAP_CMP_VALUE(base[i].value, KHRN_GENERIC_MAP_VALUE_DELETED)) && (!KHRN_GENERIC_MAP_CMP_VALUE(base[i].value, KHRN_GENERIC_MAP_VALUE_NONE))) {
196 KHRN_GENERIC_MAP_RELEASE_VALUE(base[i].value);
197 }
198 }
199#ifdef KHRN_GENERIC_MAP_RELOCATABLE
200 mem_unlock(map->storage);
201#endif
202#endif
203#ifdef KHRN_GENERIC_MAP_RELOCATABLE
204 mem_release(map->storage);
205 map->storage = MEM_INVALID_HANDLE;
206 }
207#else
208 KHRN_GENERIC_MAP_FREE(map->storage);
209#endif
210}
211
212bool khrn_generic_map(insert)(KHRN_GENERIC_MAP(T) *map, KHRN_GENERIC_MAP_KEY_T key, KHRN_GENERIC_MAP_VALUE_T value)
213{
214 uint32_t capacity = map->capacity;
215 KHRN_GENERIC_MAP(ENTRY_T) *entry;
216
217 vcos_assert(!KHRN_GENERIC_MAP_CMP_VALUE(value, KHRN_GENERIC_MAP_VALUE_DELETED));
218 vcos_assert(!KHRN_GENERIC_MAP_CMP_VALUE(value, KHRN_GENERIC_MAP_VALUE_NONE));
219
220 entry = get_entry(
221#ifdef KHRN_GENERIC_MAP_RELOCATABLE
222 (KHRN_GENERIC_MAP(ENTRY_T) *)mem_lock(map->storage),
223#else
224 map->storage,
225#endif
226 capacity, key);
227 if (entry) {
228#ifdef KHRN_GENERIC_MAP_ACQUIRE_VALUE
229 KHRN_GENERIC_MAP_ACQUIRE_VALUE(value);
230#endif
231#ifdef KHRN_GENERIC_MAP_RELEASE_VALUE
232 KHRN_GENERIC_MAP_RELEASE_VALUE(entry->value);
233#endif
234 entry->value = value;
235#ifdef KHRN_GENERIC_MAP_RELOCATABLE
236 mem_unlock(map->storage);
237#endif
238 } else {
239#ifdef KHRN_GENERIC_MAP_RELOCATABLE
240 mem_unlock(map->storage);
241#endif
242
243 if (map->entries > (capacity / 2)) {
244 capacity *= 2;
245 if (!realloc_storage(map, capacity)) { return false; }
246 } else if ((map->entries + map->deletes) > ((3 * capacity) / 4)) {
247 if (!realloc_storage(map, capacity)) { return false; }
248 }
249
250#ifdef KHRN_GENERIC_MAP_ACQUIRE_VALUE
251 KHRN_GENERIC_MAP_ACQUIRE_VALUE(value);
252#endif
253 entry = get_free_entry(
254#ifdef KHRN_GENERIC_MAP_RELOCATABLE
255 (KHRN_GENERIC_MAP(ENTRY_T) *)mem_lock(map->storage),
256#else
257 map->storage,
258#endif
259 capacity, key);
260 if (KHRN_GENERIC_MAP_CMP_VALUE(entry->value, KHRN_GENERIC_MAP_VALUE_DELETED)) {
261 vcos_assert(map->deletes > 0);
262 --map->deletes;
263 }
264 entry->key = key;
265 entry->value = value;
266 ++map->entries;
267#ifdef KHRN_GENERIC_MAP_RELOCATABLE
268 mem_unlock(map->storage);
269#endif
270 }
271
272 return true;
273}
274
275bool khrn_generic_map(delete)(KHRN_GENERIC_MAP(T) *map, KHRN_GENERIC_MAP_KEY_T key)
276{
277 KHRN_GENERIC_MAP(ENTRY_T) *entry = get_entry(
278#ifdef KHRN_GENERIC_MAP_RELOCATABLE
279 (KHRN_GENERIC_MAP(ENTRY_T) *)mem_lock(map->storage),
280#else
281 map->storage,
282#endif
283 map->capacity, key);
284 if (entry) {
285#ifdef KHRN_GENERIC_MAP_RELEASE_VALUE
286 KHRN_GENERIC_MAP_RELEASE_VALUE(entry->value);
287#endif
288 entry->value = KHRN_GENERIC_MAP_VALUE_DELETED;
289 ++map->deletes;
290 vcos_assert(map->entries > 0);
291 --map->entries;
292 }
293#ifdef KHRN_GENERIC_MAP_RELOCATABLE
294 mem_unlock(map->storage);
295#endif
296 return !!entry;
297}
298
299uint32_t khrn_generic_map(get_count)(KHRN_GENERIC_MAP(T) *map)
300{
301 return map->entries;
302}
303
304KHRN_GENERIC_MAP_VALUE_T khrn_generic_map(lookup)(KHRN_GENERIC_MAP(T) *map, KHRN_GENERIC_MAP_KEY_T key)
305#ifdef KHRN_GENERIC_MAP_RELOCATABLE
306{
307 KHRN_GENERIC_MAP_VALUE_T value = khrn_generic_map(lookup_locked)(map, key, mem_lock(map->storage));
308 mem_unlock(map->storage);
309 return value;
310}
311
312KHRN_GENERIC_MAP_VALUE_T khrn_generic_map(lookup_locked)(KHRN_GENERIC_MAP(T) *map, KHRN_GENERIC_MAP_KEY_T key, void *storage)
313#endif
314{
315 KHRN_GENERIC_MAP(ENTRY_T) *entry = get_entry(
316#ifdef KHRN_GENERIC_MAP_RELOCATABLE
317 (KHRN_GENERIC_MAP(ENTRY_T) *)storage,
318#else
319 map->storage,
320#endif
321 map->capacity, key);
322 return entry ? entry->value : KHRN_GENERIC_MAP_VALUE_NONE;
323}
324
325void khrn_generic_map(iterate)(KHRN_GENERIC_MAP(T) *map, KHRN_GENERIC_MAP(CALLBACK_T) func, void *data)
326{
327#ifdef KHRN_GENERIC_MAP_RELOCATABLE
328 KHRN_GENERIC_MAP(ENTRY_T) *base = (KHRN_GENERIC_MAP(ENTRY_T) *)mem_lock(map->storage);
329#else
330 KHRN_GENERIC_MAP(ENTRY_T) *base = map->storage;
331#endif
332 uint32_t i;
333 for (i = 0; i != map->capacity; ++i) {
334 if ((!KHRN_GENERIC_MAP_CMP_VALUE(base[i].value, KHRN_GENERIC_MAP_VALUE_DELETED)) && (!KHRN_GENERIC_MAP_CMP_VALUE(base[i].value, KHRN_GENERIC_MAP_VALUE_NONE))) {
335 func(map, base[i].key, base[i].value, data);
336 }
337 }
338#ifdef KHRN_GENERIC_MAP_RELOCATABLE
339 mem_unlock(map->storage);
340#endif
341}
342