9 # error This is a userspace-only header, not allowed by the current build.
12 #include <sifteo/memory.h>
13 #include <sifteo/macros.h>
31 template <
typename T,
unsigned tCapacity,
typename sizeT = u
int32_t>
36 typedef const T* const_iterator;
37 static const unsigned NOT_FOUND = unsigned(-1);
108 T &item = items[numItems++];
116 return items[numItems++];
123 return items[numItems];
131 *outValue = items[numItems];
142 if (index == NOT_FOUND)
145 erase(items + index);
152 memcpy((uint8_t*)item, (uint8_t*)next, (uint8_t*)
end() - (uint8_t*)next);
169 return &items[
count()];
184 if (*I == itemToFind)
211 template <
unsigned tSize>
214 static unsigned clz(uint32_t word) {
215 return __builtin_clz(word);
218 static uint32_t lz(
unsigned bit) {
219 return 0x80000000 >> bit;
223 static uint32_t range(
int bit) {
224 if (bit <= 0)
return 0xffffffff;
225 if (bit >= 32)
return 0;
226 return 0xffffffff >> bit;
230 uint32_t words[(tSize + 31) / 32];
240 const unsigned NUM_WORDS = (tSize + 31) / 32;
244 unsigned word = index >> 5;
245 unsigned bit = index & 31;
246 words[word] |= lz(bit);
248 words[0] |= lz(index);
255 const unsigned NUM_WORDS = (tSize + 31) / 32;
259 unsigned word = index >> 5;
260 unsigned bit = index & 31;
261 words[word] &= ~lz(bit);
263 words[0] &= ~lz(index);
270 const unsigned NUM_WORDS = (tSize + 31) / 32;
271 const unsigned NUM_FULL_WORDS = tSize / 32;
272 const unsigned REMAINDER_BITS = tSize & 31;
275 NUM_FULL_WORDS == NUM_WORDS);
278 _SYS_memset32(words, -1, NUM_FULL_WORDS);
280 if (NUM_FULL_WORDS != NUM_WORDS) {
282 uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
283 words[NUM_FULL_WORDS] = mask;
290 const unsigned NUM_WORDS = (tSize + 31) / 32;
291 _SYS_memset32(words, 0, NUM_WORDS);
295 bool test(
unsigned index)
const
297 const unsigned NUM_WORDS = (tSize + 31) / 32;
301 unsigned word = index >> 5;
302 unsigned bit = index & 31;
303 return (words[word] & lz(bit)) != 0;
305 return (words[0] & lz(index)) != 0;
312 const unsigned NUM_WORDS = (tSize + 31) / 32;
315 #pragma clang diagnostic push
316 #pragma clang diagnostic ignored "-Wtautological-compare"
317 for (
unsigned w = 0; w < NUM_WORDS; w++)
321 #pragma clang diagnostic pop
322 }
else if (NUM_WORDS == 1) {
323 return words[0] == 0;
332 const unsigned NUM_WORDS = (tSize + 31) / 32;
335 #pragma clang diagnostic push
336 #pragma clang diagnostic ignored "-Wtautological-compare"
338 for (
unsigned w = 0; w < NUM_WORDS; w++)
339 c += __builtin_popcount(words[w]);
341 #pragma clang diagnostic pop
342 }
else if (NUM_WORDS == 1) {
343 return __builtin_popcount(words[0]);
357 const unsigned NUM_WORDS = (tSize + 31) / 32;
360 #pragma clang diagnostic push
361 #pragma clang diagnostic ignored "-Wtautological-compare"
362 for (
unsigned w = 0; w < NUM_WORDS; w++) {
363 uint32_t v = words[w];
365 index = (w << 5) | clz(v);
370 #pragma clang diagnostic pop
371 }
else if (NUM_WORDS == 1) {
372 uint32_t v = words[0];
399 const unsigned NUM_WORDS = (tSize + 31) / 32;
402 #pragma clang diagnostic push
403 #pragma clang diagnostic ignored "-Wtautological-compare"
404 for (
unsigned w = 0; w < NUM_WORDS; w++) {
405 uint32_t v = words[w];
407 unsigned bit = clz(v);
409 index = (w << 5) | bit;
414 #pragma clang diagnostic pop
415 }
else if (NUM_WORDS == 1) {
416 uint32_t v = words[0];
418 unsigned bit = clz(v);
437 for (
unsigned i : *
this) {
453 bool operator == (
const iterator& other)
const {
454 return index == other.index;
457 bool operator != (
const iterator& other)
const {
458 return index != other.index;
461 unsigned operator* ()
const {
466 if (!remaining.clearFirst(index))
467 index =
unsigned(-1);
482 i.index = unsigned(-1);
493 const unsigned NUM_WORDS = (tSize + 31) / 32;
497 #pragma clang diagnostic push
498 #pragma clang diagnostic ignored "-Wtautological-compare"
499 for (
unsigned w = 0; w < NUM_WORDS; w++) {
500 words[w] = (w == (index >> 5)) ? lz(index & 31) : 0;
502 #pragma clang diagnostic pop
504 words[0] = lz(index);
514 const unsigned NUM_WORDS = (tSize + 31) / 32;
521 #pragma clang diagnostic push
522 #pragma clang diagnostic ignored "-Wtautological-compare"
523 for (
unsigned w = 0; w < NUM_WORDS; w++) {
525 words[w] = range(begin - offset) & ~range(end - offset);
527 #pragma clang diagnostic pop
529 words[0] = range(begin) & ~range(end);
536 const unsigned NUM_WORDS = (tSize + 31) / 32;
538 #pragma clang diagnostic push
539 #pragma clang diagnostic ignored "-Wtautological-compare"
540 for (
unsigned w = 0; w < NUM_WORDS; w++)
541 result.words[w] = words[w] & other.words[w];
542 #pragma clang diagnostic pop
549 const unsigned NUM_WORDS = (tSize + 31) / 32;
551 #pragma clang diagnostic push
552 #pragma clang diagnostic ignored "-Wtautological-compare"
553 for (
unsigned w = 0; w < NUM_WORDS; w++)
554 result.words[w] = words[w] | other.words[w];
555 #pragma clang diagnostic pop
562 const unsigned NUM_WORDS = (tSize + 31) / 32;
564 #pragma clang diagnostic push
565 #pragma clang diagnostic ignored "-Wtautological-compare"
566 for (
unsigned w = 0; w < NUM_WORDS; w++)
567 result.words[w] = words[w] ^ other.words[w];
568 #pragma clang diagnostic pop
575 const unsigned NUM_WORDS = (tSize + 31) / 32;
576 const unsigned NUM_FULL_WORDS = tSize / 32;
577 const unsigned REMAINDER_BITS = tSize & 31;
581 NUM_FULL_WORDS == NUM_WORDS);
584 #pragma clang diagnostic push
585 #pragma clang diagnostic ignored "-Wtautological-compare"
586 for (
unsigned w = 0; w < NUM_FULL_WORDS; w++)
587 result.words[w] = ~words[w];
588 #pragma clang diagnostic pop
590 if (NUM_FULL_WORDS != NUM_WORDS) {
592 uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
593 result.words[NUM_FULL_WORDS] = mask & ~words[NUM_FULL_WORDS];