Allow increasing the maximum source limit
[openal-soft.git] / common / uintmap.c
blob98ed319163e32361a21e45b081cc8ee9fa4d88f4
2 #include "config.h"
4 #include "uintmap.h"
6 #include <stdlib.h>
7 #include <string.h>
9 #include "almalloc.h"
12 extern inline void LockUIntMapRead(UIntMap *map);
13 extern inline void UnlockUIntMapRead(UIntMap *map);
14 extern inline void LockUIntMapWrite(UIntMap *map);
15 extern inline void UnlockUIntMapWrite(UIntMap *map);
18 void InitUIntMap(UIntMap *map, ALsizei limit)
20 map->keys = NULL;
21 map->values = NULL;
22 map->size = 0;
23 map->capacity = 0;
24 map->limit = limit;
25 RWLockInit(&map->lock);
28 void ResetUIntMap(UIntMap *map)
30 WriteLock(&map->lock);
31 al_free(map->keys);
32 map->keys = NULL;
33 map->values = NULL;
34 map->size = 0;
35 map->capacity = 0;
36 WriteUnlock(&map->lock);
39 void RelimitUIntMapNoLock(UIntMap *map, ALsizei limit)
41 map->limit = limit;
44 ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
46 ALsizei pos = 0;
48 WriteLock(&map->lock);
49 if(map->size > 0)
51 ALsizei count = map->size;
52 do {
53 ALsizei step = count>>1;
54 ALsizei i = pos+step;
55 if(!(map->keys[i] < key))
56 count = step;
57 else
59 pos = i+1;
60 count -= step+1;
62 } while(count > 0);
65 if(pos == map->size || map->keys[pos] != key)
67 if(map->size >= map->limit)
69 WriteUnlock(&map->lock);
70 return AL_OUT_OF_MEMORY;
73 if(map->size == map->capacity)
75 ALuint *keys = NULL;
76 ALvoid **values;
77 ALsizei newcap, keylen;
79 newcap = (map->capacity ? (map->capacity<<1) : 4);
80 if(map->limit > 0 && newcap > map->limit)
81 newcap = map->limit;
82 if(newcap > map->capacity)
84 /* Round the memory size for keys up to a multiple of the
85 * pointer size.
87 keylen = newcap * sizeof(map->keys[0]);
88 keylen += sizeof(map->values[0]) - 1;
89 keylen -= keylen%sizeof(map->values[0]);
91 keys = al_malloc(16, keylen + newcap*sizeof(map->values[0]));
93 if(!keys)
95 WriteUnlock(&map->lock);
96 return AL_OUT_OF_MEMORY;
98 values = (ALvoid**)((ALbyte*)keys + keylen);
100 if(map->keys)
102 memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
103 memcpy(values, map->values, map->size*sizeof(map->values[0]));
105 al_free(map->keys);
106 map->keys = keys;
107 map->values = values;
108 map->capacity = newcap;
111 if(pos < map->size)
113 memmove(&map->keys[pos+1], &map->keys[pos],
114 (map->size-pos)*sizeof(map->keys[0]));
115 memmove(&map->values[pos+1], &map->values[pos],
116 (map->size-pos)*sizeof(map->values[0]));
118 map->size++;
120 map->keys[pos] = key;
121 map->values[pos] = value;
122 WriteUnlock(&map->lock);
124 return AL_NO_ERROR;
127 ALenum InsertUIntMapEntryNoLock(UIntMap *map, ALuint key, ALvoid *value)
129 ALsizei pos = 0;
131 if(map->size > 0)
133 ALsizei count = map->size;
134 do {
135 ALsizei step = count>>1;
136 ALsizei i = pos+step;
137 if(!(map->keys[i] < key))
138 count = step;
139 else
141 pos = i+1;
142 count -= step+1;
144 } while(count > 0);
147 if(pos == map->size || map->keys[pos] != key)
149 if(map->size >= map->limit)
150 return AL_OUT_OF_MEMORY;
152 if(map->size == map->capacity)
154 ALuint *keys = NULL;
155 ALvoid **values;
156 ALsizei newcap, keylen;
158 newcap = (map->capacity ? (map->capacity<<1) : 4);
159 if(map->limit > 0 && newcap > map->limit)
160 newcap = map->limit;
161 if(newcap > map->capacity)
163 /* Round the memory size for keys up to a multiple of the
164 * pointer size.
166 keylen = newcap * sizeof(map->keys[0]);
167 keylen += sizeof(map->values[0]) - 1;
168 keylen -= keylen%sizeof(map->values[0]);
170 keys = al_malloc(16, keylen + newcap*sizeof(map->values[0]));
172 if(!keys)
173 return AL_OUT_OF_MEMORY;
174 values = (ALvoid**)((ALbyte*)keys + keylen);
176 if(map->keys)
178 memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
179 memcpy(values, map->values, map->size*sizeof(map->values[0]));
181 al_free(map->keys);
182 map->keys = keys;
183 map->values = values;
184 map->capacity = newcap;
187 if(pos < map->size)
189 memmove(&map->keys[pos+1], &map->keys[pos],
190 (map->size-pos)*sizeof(map->keys[0]));
191 memmove(&map->values[pos+1], &map->values[pos],
192 (map->size-pos)*sizeof(map->values[0]));
194 map->size++;
196 map->keys[pos] = key;
197 map->values[pos] = value;
199 return AL_NO_ERROR;
202 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
204 ALvoid *ptr = NULL;
205 WriteLock(&map->lock);
206 if(map->size > 0)
208 ALsizei pos = 0;
209 ALsizei count = map->size;
210 do {
211 ALsizei step = count>>1;
212 ALsizei i = pos+step;
213 if(!(map->keys[i] < key))
214 count = step;
215 else
217 pos = i+1;
218 count -= step+1;
220 } while(count > 0);
221 if(pos < map->size && map->keys[pos] == key)
223 ptr = map->values[pos];
224 if(pos < map->size-1)
226 memmove(&map->keys[pos], &map->keys[pos+1],
227 (map->size-1-pos)*sizeof(map->keys[0]));
228 memmove(&map->values[pos], &map->values[pos+1],
229 (map->size-1-pos)*sizeof(map->values[0]));
231 map->size--;
234 WriteUnlock(&map->lock);
235 return ptr;
238 ALvoid *RemoveUIntMapKeyNoLock(UIntMap *map, ALuint key)
240 ALvoid *ptr = NULL;
241 if(map->size > 0)
243 ALsizei pos = 0;
244 ALsizei count = map->size;
245 do {
246 ALsizei step = count>>1;
247 ALsizei i = pos+step;
248 if(!(map->keys[i] < key))
249 count = step;
250 else
252 pos = i+1;
253 count -= step+1;
255 } while(count > 0);
256 if(pos < map->size && map->keys[pos] == key)
258 ptr = map->values[pos];
259 if(pos < map->size-1)
261 memmove(&map->keys[pos], &map->keys[pos+1],
262 (map->size-1-pos)*sizeof(map->keys[0]));
263 memmove(&map->values[pos], &map->values[pos+1],
264 (map->size-1-pos)*sizeof(map->values[0]));
266 map->size--;
269 return ptr;
272 ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
274 ALvoid *ptr = NULL;
275 ReadLock(&map->lock);
276 if(map->size > 0)
278 ALsizei pos = 0;
279 ALsizei count = map->size;
280 do {
281 ALsizei step = count>>1;
282 ALsizei i = pos+step;
283 if(!(map->keys[i] < key))
284 count = step;
285 else
287 pos = i+1;
288 count -= step+1;
290 } while(count > 0);
291 if(pos < map->size && map->keys[pos] == key)
292 ptr = map->values[pos];
294 ReadUnlock(&map->lock);
295 return ptr;
298 ALvoid *LookupUIntMapKeyNoLock(UIntMap *map, ALuint key)
300 if(map->size > 0)
302 ALsizei pos = 0;
303 ALsizei count = map->size;
304 do {
305 ALsizei step = count>>1;
306 ALsizei i = pos+step;
307 if(!(map->keys[i] < key))
308 count = step;
309 else
311 pos = i+1;
312 count -= step+1;
314 } while(count > 0);
315 if(pos < map->size && map->keys[pos] == key)
316 return map->values[pos];
318 return NULL;