v1.1.0
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Groups Pages
array.h
1 /* -*- mode: C; c-basic-offset: 4; intent-tabs-mode: nil -*-
2  *
3  * This file is part of the public interface to the Sifteo SDK.
4  * Copyright <c> 2012 Sifteo, Inc. All rights reserved.
5  */
6 
7 #pragma once
8 #ifdef NOT_USERSPACE
9 # error This is a userspace-only header, not allowed by the current build.
10 #endif
11 
12 #include <sifteo/memory.h>
13 #include <sifteo/macros.h>
14 
15 namespace Sifteo {
16 
31 template <typename T, unsigned tCapacity, typename sizeT = uint32_t>
32 class Array {
33 public:
34 
35  typedef T* iterator;
36  typedef const T* const_iterator;
37  static const unsigned NOT_FOUND = unsigned(-1);
38 
40  Array() {
41  clear();
42  }
43 
45  static unsigned capacity() {
46  return tCapacity;
47  }
48 
50  unsigned count() const {
51  return numItems;
52  }
53 
61  void setCount(unsigned c) {
62  ASSERT(c <= tCapacity);
63  numItems = c;
64  }
65 
67  bool empty() const {
68  return count() == 0;
69  }
70 
72  const T& operator[](unsigned index) const {
73  ASSERT(index < count());
74  return items[index];
75  }
76 
78  const T& operator[](int index) const {
79  ASSERT(0 <= index && index < (int)count());
80  return items[index];
81  }
82 
84  T& operator[](unsigned index) {
85  ASSERT(index < count());
86  return items[index];
87  }
88 
90  T& operator[](int index) {
91  ASSERT(0 <= index && index < (int)count());
92  return items[index];
93  }
94 
96  T& append(const T &newItem) {
97  return push_back(newItem);
98  }
99 
101  T& append() {
102  return push_back();
103  }
104 
106  T& push_back(const T &newItem) {
107  ASSERT(count() < tCapacity);
108  T &item = items[numItems++];
109  item = newItem;
110  return item;
111  }
112 
114  T& push_back() {
115  ASSERT(count() < tCapacity);
116  return items[numItems++];
117  }
118 
120  T pop_back() {
121  ASSERT(count() > 0);
122  numItems--;
123  return items[numItems];
124  }
125 
127  void pop_back(T* outValue) {
128  ASSERT(outValue != 0);
129  ASSERT(count() > 0);
130  numItems--;
131  *outValue = items[numItems];
132  }
133 
135  void clear() {
136  numItems = 0;
137  }
138 
140  void erase(unsigned index) {
141  // allow a.erase(a.find()) without checking for not-found.
142  if (index == NOT_FOUND)
143  return;
144 
145  erase(items + index);
146  }
147 
149  void erase(iterator item) {
150  ASSERT(item >= begin() && item < end());
151  iterator next = item + 1;
152  memcpy((uint8_t*)item, (uint8_t*)next, (uint8_t*)end() - (uint8_t*)next);
153  numItems--;
154  }
155 
157  void erase_tail() {
158  ASSERT(count() > 0);
159  numItems--;
160  }
161 
164  return &items[0];
165  }
166 
169  return &items[count()];
170  }
171 
180  unsigned find(T itemToFind)
181  {
182  int index = 0;
183  for (iterator I=begin(), E=end(); I != E; ++I, ++index) {
184  if (*I == itemToFind)
185  return index;
186  }
187  return NOT_FOUND;
188  }
189 
190 private:
191  T items[tCapacity];
192  sizeT numItems;
193 };
194 
195 
211 template <unsigned tSize>
212 class BitArray
213 {
214  static unsigned clz(uint32_t word) {
215  return __builtin_clz(word);
216  }
217 
218  static uint32_t lz(unsigned bit) {
219  return 0x80000000 >> bit;
220  }
221 
222  // Return a range of bits from 'bit' to 31.
223  static uint32_t range(int bit) {
224  if (bit <= 0) return 0xffffffff;
225  if (bit >= 32) return 0;
226  return 0xffffffff >> bit;
227  }
228 
229 public:
230  uint32_t words[(tSize + 31) / 32];
231 
233  static unsigned size() {
234  return tSize;
235  }
236 
238  void mark(unsigned index)
239  {
240  const unsigned NUM_WORDS = (tSize + 31) / 32;
241 
242  ASSERT(index < tSize);
243  if (NUM_WORDS > 1) {
244  unsigned word = index >> 5;
245  unsigned bit = index & 31;
246  words[word] |= lz(bit);
247  } else {
248  words[0] |= lz(index);
249  }
250  }
251 
253  void clear(unsigned index)
254  {
255  const unsigned NUM_WORDS = (tSize + 31) / 32;
256 
257  ASSERT(index < tSize);
258  if (NUM_WORDS > 1) {
259  unsigned word = index >> 5;
260  unsigned bit = index & 31;
261  words[word] &= ~lz(bit);
262  } else {
263  words[0] &= ~lz(index);
264  }
265  }
266 
268  void mark()
269  {
270  const unsigned NUM_WORDS = (tSize + 31) / 32;
271  const unsigned NUM_FULL_WORDS = tSize / 32;
272  const unsigned REMAINDER_BITS = tSize & 31;
273 
274  STATIC_ASSERT(NUM_FULL_WORDS + 1 == NUM_WORDS ||
275  NUM_FULL_WORDS == NUM_WORDS);
276 
277  // Set fully-utilized words only
278  _SYS_memset32(words, -1, NUM_FULL_WORDS);
279 
280  if (NUM_FULL_WORDS != NUM_WORDS) {
281  // Set only bits < tSize in the last word.
282  uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
283  words[NUM_FULL_WORDS] = mask;
284  }
285  }
286 
288  void clear()
289  {
290  const unsigned NUM_WORDS = (tSize + 31) / 32;
291  _SYS_memset32(words, 0, NUM_WORDS);
292  }
293 
295  bool test(unsigned index) const
296  {
297  const unsigned NUM_WORDS = (tSize + 31) / 32;
298 
299  ASSERT(index < tSize);
300  if (NUM_WORDS > 1) {
301  unsigned word = index >> 5;
302  unsigned bit = index & 31;
303  return (words[word] & lz(bit)) != 0;
304  } else {
305  return (words[0] & lz(index)) != 0;
306  }
307  }
308 
310  bool empty() const
311  {
312  const unsigned NUM_WORDS = (tSize + 31) / 32;
313 
314  if (NUM_WORDS > 1) {
315  #pragma clang diagnostic push
316  #pragma clang diagnostic ignored "-Wtautological-compare"
317  for (unsigned w = 0; w < NUM_WORDS; w++)
318  if (words[w])
319  return false;
320  return true;
321  #pragma clang diagnostic pop
322  } else if (NUM_WORDS == 1) {
323  return words[0] == 0;
324  } else {
325  return true;
326  }
327  }
328 
330  unsigned count() const
331  {
332  const unsigned NUM_WORDS = (tSize + 31) / 32;
333 
334  if (NUM_WORDS > 1) {
335  #pragma clang diagnostic push
336  #pragma clang diagnostic ignored "-Wtautological-compare"
337  unsigned c = 0;
338  for (unsigned w = 0; w < NUM_WORDS; w++)
339  c += __builtin_popcount(words[w]);
340  return c;
341  #pragma clang diagnostic pop
342  } else if (NUM_WORDS == 1) {
343  return __builtin_popcount(words[0]);
344  } else {
345  return 0;
346  }
347  }
348 
355  bool findFirst(unsigned &index) const
356  {
357  const unsigned NUM_WORDS = (tSize + 31) / 32;
358 
359  if (NUM_WORDS > 1) {
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];
364  if (v) {
365  index = (w << 5) | clz(v);
366  ASSERT(index < tSize);
367  return true;
368  }
369  }
370  #pragma clang diagnostic pop
371  } else if (NUM_WORDS == 1) {
372  uint32_t v = words[0];
373  if (v) {
374  index = clz(v);
375  ASSERT(index < tSize);
376  return true;
377  }
378  }
379  return false;
380  }
381 
397  bool clearFirst(unsigned &index)
398  {
399  const unsigned NUM_WORDS = (tSize + 31) / 32;
400 
401  if (NUM_WORDS > 1) {
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];
406  if (v) {
407  unsigned bit = clz(v);
408  words[w] ^= lz(bit);
409  index = (w << 5) | bit;
410  ASSERT(index < tSize);
411  return true;
412  }
413  }
414  #pragma clang diagnostic pop
415  } else if (NUM_WORDS == 1) {
416  uint32_t v = words[0];
417  if (v) {
418  unsigned bit = clz(v);
419  words[0] ^= lz(bit);
420  index = bit;
421  ASSERT(index < tSize);
422  return true;
423  }
424  }
425  return false;
426  }
427 
435  bool clearN(unsigned &index, unsigned n)
436  {
437  for (unsigned i : *this) {
438  if (n--)
439  continue;
440 
441  clear(i);
442  index = i;
443  return true;
444  }
445  return false;
446  }
447 
449  struct iterator {
450  unsigned index;
451  BitArray<tSize> remaining;
452 
453  bool operator == (const iterator& other) const {
454  return index == other.index;
455  }
456 
457  bool operator != (const iterator& other) const {
458  return index != other.index;
459  }
460 
461  unsigned operator* () const {
462  return index;
463  }
464 
465  const iterator& operator++ () {
466  if (!remaining.clearFirst(index))
467  index = unsigned(-1);
468  return *this;
469  }
470  };
471 
473  iterator begin() const {
474  iterator i;
475  i.remaining = *this;
476  return ++i;
477  }
478 
480  iterator end() const {
481  iterator i;
482  i.index = unsigned(-1);
483  return i;
484  }
485 
488  clear();
489  }
490 
492  explicit BitArray(unsigned index) {
493  const unsigned NUM_WORDS = (tSize + 31) / 32;
494 
495  ASSERT(index < tSize);
496  if (NUM_WORDS > 1) {
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;
501  }
502  #pragma clang diagnostic pop
503  } else {
504  words[0] = lz(index);
505  }
506  }
507 
513  explicit BitArray(unsigned begin, unsigned end) {
514  const unsigned NUM_WORDS = (tSize + 31) / 32;
515 
516  ASSERT(begin < tSize);
517  ASSERT(end <= tSize);
518  ASSERT(begin <= end);
519 
520  if (NUM_WORDS > 1) {
521  #pragma clang diagnostic push
522  #pragma clang diagnostic ignored "-Wtautological-compare"
523  for (unsigned w = 0; w < NUM_WORDS; w++) {
524  int offset = w << 5;
525  words[w] = range(begin - offset) & ~range(end - offset);
526  }
527  #pragma clang diagnostic pop
528  } else {
529  words[0] = range(begin) & ~range(end);
530  }
531  }
532 
535  {
536  const unsigned NUM_WORDS = (tSize + 31) / 32;
537  BitArray<tSize> result;
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
543  return result;
544  }
545 
548  {
549  const unsigned NUM_WORDS = (tSize + 31) / 32;
550  BitArray<tSize> result;
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
556  return result;
557  }
558 
561  {
562  const unsigned NUM_WORDS = (tSize + 31) / 32;
563  BitArray<tSize> result;
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
569  return result;
570  }
571 
574  {
575  const unsigned NUM_WORDS = (tSize + 31) / 32;
576  const unsigned NUM_FULL_WORDS = tSize / 32;
577  const unsigned REMAINDER_BITS = tSize & 31;
578  BitArray<tSize> result;
579 
580  STATIC_ASSERT(NUM_FULL_WORDS + 1 == NUM_WORDS ||
581  NUM_FULL_WORDS == NUM_WORDS);
582 
583  // Trivial inversion for fully-utilized 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
589 
590  if (NUM_FULL_WORDS != NUM_WORDS) {
591  // Set only bits < tSize in the last word.
592  uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
593  result.words[NUM_FULL_WORDS] = mask & ~words[NUM_FULL_WORDS];
594  }
595 
596  return result;
597  }
598 };
599 
600 
605 }; // namespace Sifteo