v1.1.0
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Modules Pages
array.h
1 /* -*- mode: C; c-basic-offset: 4; intent-tabs-mode: nil -*-
2  *
3  * Sifteo SDK
4  *
5  * Copyright <c> 2012 Sifteo, Inc.
6  *
7  * Permission is hereby granted, free of charge, to any person obtaining a copy
8  * of this software and associated documentation files (the "Software"), to deal
9  * in the Software without restriction, including without limitation the rights
10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11  * copies of the Software, and to permit persons to whom the Software is
12  * furnished to do so, subject to the following conditions:
13  *
14  * The above copyright notice and this permission notice shall be included in
15  * all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23  * THE SOFTWARE.
24  */
25 
26 #pragma once
27 #ifdef NOT_USERSPACE
28 # error This is a userspace-only header, not allowed by the current build.
29 #endif
30 
31 #include <sifteo/memory.h>
32 #include <sifteo/macros.h>
33 
34 namespace Sifteo {
35 
50 template <typename T, unsigned tCapacity, typename sizeT = uint32_t>
51 class Array {
52 public:
53 
54  typedef T* iterator;
55  typedef const T* const_iterator;
56  static const unsigned NOT_FOUND = unsigned(-1);
57 
59  Array() {
60  clear();
61  }
62 
64  static unsigned capacity() {
65  return tCapacity;
66  }
67 
69  unsigned count() const {
70  return numItems;
71  }
72 
80  void setCount(unsigned c) {
81  ASSERT(c <= tCapacity);
82  numItems = c;
83  }
84 
86  bool empty() const {
87  return count() == 0;
88  }
89 
91  const T& operator[](unsigned index) const {
92  ASSERT(index < count());
93  return items[index];
94  }
95 
97  const T& operator[](int index) const {
98  ASSERT(0 <= index && index < (int)count());
99  return items[index];
100  }
101 
103  T& operator[](unsigned index) {
104  ASSERT(index < count());
105  return items[index];
106  }
107 
109  T& operator[](int index) {
110  ASSERT(0 <= index && index < (int)count());
111  return items[index];
112  }
113 
115  T& append(const T &newItem) {
116  return push_back(newItem);
117  }
118 
120  T& append() {
121  return push_back();
122  }
123 
125  T& push_back(const T &newItem) {
126  ASSERT(count() < tCapacity);
127  T &item = items[numItems++];
128  item = newItem;
129  return item;
130  }
131 
133  T& push_back() {
134  ASSERT(count() < tCapacity);
135  return items[numItems++];
136  }
137 
139  T pop_back() {
140  ASSERT(count() > 0);
141  numItems--;
142  return items[numItems];
143  }
144 
146  void pop_back(T* outValue) {
147  ASSERT(outValue != 0);
148  ASSERT(count() > 0);
149  numItems--;
150  *outValue = items[numItems];
151  }
152 
154  void clear() {
155  numItems = 0;
156  }
157 
159  void erase(unsigned index) {
160  // allow a.erase(a.find()) without checking for not-found.
161  if (index == NOT_FOUND)
162  return;
163 
164  erase(items + index);
165  }
166 
168  void erase(iterator item) {
169  ASSERT(item >= begin() && item < end());
170  iterator next = item + 1;
171  memcpy((uint8_t*)item, (uint8_t*)next, (uint8_t*)end() - (uint8_t*)next);
172  numItems--;
173  }
174 
176  void erase_tail() {
177  ASSERT(count() > 0);
178  numItems--;
179  }
180 
182  iterator begin() {
183  return &items[0];
184  }
185 
187  iterator end() {
188  return &items[count()];
189  }
190 
199  unsigned find(T itemToFind)
200  {
201  int index = 0;
202  for (iterator I=begin(), E=end(); I != E; ++I, ++index) {
203  if (*I == itemToFind)
204  return index;
205  }
206  return NOT_FOUND;
207  }
208 
209 private:
210  T items[tCapacity];
211  sizeT numItems;
212 };
213 
214 
230 template <unsigned tSize>
231 class BitArray
232 {
233  static unsigned clz(uint32_t word) {
234  return __builtin_clz(word);
235  }
236 
237  static uint32_t lz(unsigned bit) {
238  return 0x80000000 >> bit;
239  }
240 
241  // Return a range of bits from 'bit' to 31.
242  static uint32_t range(int bit) {
243  if (bit <= 0) return 0xffffffff;
244  if (bit >= 32) return 0;
245  return 0xffffffff >> bit;
246  }
247 
248 public:
249  uint32_t words[(tSize + 31) / 32];
250 
252  static unsigned size() {
253  return tSize;
254  }
255 
257  void mark(unsigned index)
258  {
259  const unsigned NUM_WORDS = (tSize + 31) / 32;
260 
261  ASSERT(index < tSize);
262  if (NUM_WORDS > 1) {
263  unsigned word = index >> 5;
264  unsigned bit = index & 31;
265  words[word] |= lz(bit);
266  } else {
267  words[0] |= lz(index);
268  }
269  }
270 
272  void clear(unsigned index)
273  {
274  const unsigned NUM_WORDS = (tSize + 31) / 32;
275 
276  ASSERT(index < tSize);
277  if (NUM_WORDS > 1) {
278  unsigned word = index >> 5;
279  unsigned bit = index & 31;
280  words[word] &= ~lz(bit);
281  } else {
282  words[0] &= ~lz(index);
283  }
284  }
285 
287  void mark()
288  {
289  const unsigned NUM_WORDS = (tSize + 31) / 32;
290  const unsigned NUM_FULL_WORDS = tSize / 32;
291  const unsigned REMAINDER_BITS = tSize & 31;
292 
293  STATIC_ASSERT(NUM_FULL_WORDS + 1 == NUM_WORDS ||
294  NUM_FULL_WORDS == NUM_WORDS);
295 
296  // Set fully-utilized words only
297  _SYS_memset32(words, -1, NUM_FULL_WORDS);
298 
299  if (NUM_FULL_WORDS != NUM_WORDS) {
300  // Set only bits < tSize in the last word.
301  uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
302  words[NUM_FULL_WORDS] = mask;
303  }
304  }
305 
307  void clear()
308  {
309  const unsigned NUM_WORDS = (tSize + 31) / 32;
310  _SYS_memset32(words, 0, NUM_WORDS);
311  }
312 
314  bool test(unsigned index) const
315  {
316  const unsigned NUM_WORDS = (tSize + 31) / 32;
317 
318  ASSERT(index < tSize);
319  if (NUM_WORDS > 1) {
320  unsigned word = index >> 5;
321  unsigned bit = index & 31;
322  return (words[word] & lz(bit)) != 0;
323  } else {
324  return (words[0] & lz(index)) != 0;
325  }
326  }
327 
329  bool empty() const
330  {
331  const unsigned NUM_WORDS = (tSize + 31) / 32;
332 
333  if (NUM_WORDS > 1) {
334  #pragma clang diagnostic push
335  #pragma clang diagnostic ignored "-Wtautological-compare"
336  for (unsigned w = 0; w < NUM_WORDS; w++)
337  if (words[w])
338  return false;
339  return true;
340  #pragma clang diagnostic pop
341  } else if (NUM_WORDS == 1) {
342  return words[0] == 0;
343  } else {
344  return true;
345  }
346  }
347 
349  unsigned count() const
350  {
351  const unsigned NUM_WORDS = (tSize + 31) / 32;
352 
353  if (NUM_WORDS > 1) {
354  #pragma clang diagnostic push
355  #pragma clang diagnostic ignored "-Wtautological-compare"
356  unsigned c = 0;
357  for (unsigned w = 0; w < NUM_WORDS; w++)
358  c += __builtin_popcount(words[w]);
359  return c;
360  #pragma clang diagnostic pop
361  } else if (NUM_WORDS == 1) {
362  return __builtin_popcount(words[0]);
363  } else {
364  return 0;
365  }
366  }
367 
374  bool findFirst(unsigned &index) const
375  {
376  const unsigned NUM_WORDS = (tSize + 31) / 32;
377 
378  if (NUM_WORDS > 1) {
379  #pragma clang diagnostic push
380  #pragma clang diagnostic ignored "-Wtautological-compare"
381  for (unsigned w = 0; w < NUM_WORDS; w++) {
382  uint32_t v = words[w];
383  if (v) {
384  index = (w << 5) | clz(v);
385  ASSERT(index < tSize);
386  return true;
387  }
388  }
389  #pragma clang diagnostic pop
390  } else if (NUM_WORDS == 1) {
391  uint32_t v = words[0];
392  if (v) {
393  index = clz(v);
394  ASSERT(index < tSize);
395  return true;
396  }
397  }
398  return false;
399  }
400 
416  bool clearFirst(unsigned &index)
417  {
418  const unsigned NUM_WORDS = (tSize + 31) / 32;
419 
420  if (NUM_WORDS > 1) {
421  #pragma clang diagnostic push
422  #pragma clang diagnostic ignored "-Wtautological-compare"
423  for (unsigned w = 0; w < NUM_WORDS; w++) {
424  uint32_t v = words[w];
425  if (v) {
426  unsigned bit = clz(v);
427  words[w] ^= lz(bit);
428  index = (w << 5) | bit;
429  ASSERT(index < tSize);
430  return true;
431  }
432  }
433  #pragma clang diagnostic pop
434  } else if (NUM_WORDS == 1) {
435  uint32_t v = words[0];
436  if (v) {
437  unsigned bit = clz(v);
438  words[0] ^= lz(bit);
439  index = bit;
440  ASSERT(index < tSize);
441  return true;
442  }
443  }
444  return false;
445  }
446 
454  bool clearN(unsigned &index, unsigned n)
455  {
456  for (unsigned i : *this) {
457  if (n--)
458  continue;
459 
460  clear(i);
461  index = i;
462  return true;
463  }
464  return false;
465  }
466 
468  struct iterator {
469  unsigned index;
470  BitArray<tSize> remaining;
471 
472  bool operator == (const iterator& other) const {
473  return index == other.index;
474  }
475 
476  bool operator != (const iterator& other) const {
477  return index != other.index;
478  }
479 
480  unsigned operator* () const {
481  return index;
482  }
483 
484  const iterator& operator++ () {
485  if (!remaining.clearFirst(index))
486  index = unsigned(-1);
487  return *this;
488  }
489  };
490 
492  iterator begin() const {
493  iterator i;
494  i.remaining = *this;
495  return ++i;
496  }
497 
499  iterator end() const {
500  iterator i;
501  i.index = unsigned(-1);
502  return i;
503  }
504 
507  clear();
508  }
509 
511  explicit BitArray(unsigned index) {
512  const unsigned NUM_WORDS = (tSize + 31) / 32;
513 
514  ASSERT(index < tSize);
515  if (NUM_WORDS > 1) {
516  #pragma clang diagnostic push
517  #pragma clang diagnostic ignored "-Wtautological-compare"
518  for (unsigned w = 0; w < NUM_WORDS; w++) {
519  words[w] = (w == (index >> 5)) ? lz(index & 31) : 0;
520  }
521  #pragma clang diagnostic pop
522  } else {
523  words[0] = lz(index);
524  }
525  }
526 
532  explicit BitArray(unsigned begin, unsigned end) {
533  const unsigned NUM_WORDS = (tSize + 31) / 32;
534 
535  ASSERT(begin < tSize);
536  ASSERT(end <= tSize);
537  ASSERT(begin <= end);
538 
539  if (NUM_WORDS > 1) {
540  #pragma clang diagnostic push
541  #pragma clang diagnostic ignored "-Wtautological-compare"
542  for (unsigned w = 0; w < NUM_WORDS; w++) {
543  int offset = w << 5;
544  words[w] = range(begin - offset) & ~range(end - offset);
545  }
546  #pragma clang diagnostic pop
547  } else {
548  words[0] = range(begin) & ~range(end);
549  }
550  }
551 
554  {
555  const unsigned NUM_WORDS = (tSize + 31) / 32;
556  BitArray<tSize> result;
557  #pragma clang diagnostic push
558  #pragma clang diagnostic ignored "-Wtautological-compare"
559  for (unsigned w = 0; w < NUM_WORDS; w++)
560  result.words[w] = words[w] & other.words[w];
561  #pragma clang diagnostic pop
562  return result;
563  }
564 
567  {
568  const unsigned NUM_WORDS = (tSize + 31) / 32;
569  BitArray<tSize> result;
570  #pragma clang diagnostic push
571  #pragma clang diagnostic ignored "-Wtautological-compare"
572  for (unsigned w = 0; w < NUM_WORDS; w++)
573  result.words[w] = words[w] | other.words[w];
574  #pragma clang diagnostic pop
575  return result;
576  }
577 
580  {
581  const unsigned NUM_WORDS = (tSize + 31) / 32;
582  BitArray<tSize> result;
583  #pragma clang diagnostic push
584  #pragma clang diagnostic ignored "-Wtautological-compare"
585  for (unsigned w = 0; w < NUM_WORDS; w++)
586  result.words[w] = words[w] ^ other.words[w];
587  #pragma clang diagnostic pop
588  return result;
589  }
590 
593  {
594  const unsigned NUM_WORDS = (tSize + 31) / 32;
595  const unsigned NUM_FULL_WORDS = tSize / 32;
596  const unsigned REMAINDER_BITS = tSize & 31;
597  BitArray<tSize> result;
598 
599  STATIC_ASSERT(NUM_FULL_WORDS + 1 == NUM_WORDS ||
600  NUM_FULL_WORDS == NUM_WORDS);
601 
602  // Trivial inversion for fully-utilized words
603  #pragma clang diagnostic push
604  #pragma clang diagnostic ignored "-Wtautological-compare"
605  for (unsigned w = 0; w < NUM_FULL_WORDS; w++)
606  result.words[w] = ~words[w];
607  #pragma clang diagnostic pop
608 
609  if (NUM_FULL_WORDS != NUM_WORDS) {
610  // Set only bits < tSize in the last word.
611  uint32_t mask = ((uint32_t)-1) << ((32 - REMAINDER_BITS) & 31);
612  result.words[NUM_FULL_WORDS] = mask & ~words[NUM_FULL_WORDS];
613  }
614 
615  return result;
616  }
617 };
618 
619 
624 }; // namespace Sifteo
void erase(unsigned index)
Remove a specific element, by index, and shift the others down.
Definition: array.h:159
T pop_back()
Deallocate the last element and return a copy of it's value.
Definition: array.h:139
void erase(iterator item)
Remove the element at iterator 'item' and shift the others down.
Definition: array.h:168
static unsigned capacity()
Retrieve the capacity of this array, always constant at compile-time.
Definition: array.h:64
T & append(const T &newItem)
Synonym for push_back()
Definition: array.h:115
BitArray()
Create a new empty BitArray.
Definition: array.h:506
#define ASSERT(_x)
Runtime debug assertion.
Definition: macros.h:205
T & operator[](int index)
Accessor for array elements.
Definition: array.h:109
const T & operator[](int index) const
Accessor for array elements.
Definition: array.h:97
T & push_back()
Allocate the first unused slot in the array, and return an reference to this uninitialized slot...
Definition: array.h:133
iterator end()
Return an iterator pointing just past the last in-use slot in the array.
Definition: array.h:187
Array()
Initialize a new empty array.
Definition: array.h:59
bool findFirst(unsigned &index) const
Find the lowest index where there's a marked (1) bit.
Definition: array.h:374
void mark()
Mark (set to 1) all bits in the array.
Definition: array.h:287
void clear()
Clear (set to 0) all bits in the array.
Definition: array.h:307
unsigned count() const
How many bits are marked in this vector?
Definition: array.h:349
An STL-style iterator for the BitArray.
Definition: array.h:468
void setCount(unsigned c)
Change the number of elements currently in the array.
Definition: array.h:80
void pop_back(T *outValue)
Pop-back, but avoid a potential unnecessary copy.
Definition: array.h:146
iterator begin()
Return an iterator pointing to the first slot in the array.
Definition: array.h:182
T & push_back(const T &newItem)
Copy 'newItem' to the first unused slot in the array, and return a reference to the copy...
Definition: array.h:125
BitArray< tSize > operator^(const BitArray< tSize > &other) const
Bitwise XOR of two BitArrays of the same size.
Definition: array.h:579
const T & operator[](unsigned index) const
Accessor for array elements.
Definition: array.h:91
A statically sized array.
Definition: array.h:51
BitArray(unsigned index)
Create a new BitArray with a single bit marked.
Definition: array.h:511
void erase_tail()
Remove the last element, which involves no shifting.
Definition: array.h:176
void clear(unsigned index)
Clear (set to 0) a single bit.
Definition: array.h:272
Definition: array.h:34
BitArray< tSize > operator~() const
Negate a BitArray, returning a new array in which each bit is inverted.
Definition: array.h:592
BitArray< tSize > operator|(const BitArray< tSize > &other) const
Bitwise OR of two BitArrays of the same size.
Definition: array.h:566
bool test(unsigned index) const
Is a particular bit marked?
Definition: array.h:314
bool empty() const
Is this array empty?
Definition: array.h:86
void mark(unsigned index)
Mark (set to 1) a single bit.
Definition: array.h:257
iterator end() const
Return an STL-style iterator for this array.
Definition: array.h:499
bool clearFirst(unsigned &index)
Find and clear the lowest marked bit.
Definition: array.h:416
#define STATIC_ASSERT(_x)
Definition: macros.h:342
T & operator[](unsigned index)
Accessor for array elements.
Definition: array.h:103
T & append()
Synonym for push_back()
Definition: array.h:120
BitArray< tSize > operator&(const BitArray< tSize > &other) const
Bitwise AND of two BitArrays of the same size.
Definition: array.h:553
bool empty() const
Is every bit in this array set to zero?
Definition: array.h:329
unsigned find(T itemToFind)
Definition: array.h:199
iterator begin() const
Return an STL-style iterator for this array.
Definition: array.h:492
unsigned count() const
How many items does this array currently hold?
Definition: array.h:69
BitArray(unsigned begin, unsigned end)
Create a new BitArray with a range of bits marked.
Definition: array.h:532
bool clearN(unsigned &index, unsigned n)
Find and clear the Nth lowest marked bit.
Definition: array.h:454
static unsigned size()
Retrieve the size of this array in bits, always constant at compile-time.
Definition: array.h:252
void clear()
Equivalent to setCount(0)
Definition: array.h:154
void memcpy(uint8_t *dest, const uint8_t *src, unsigned count)
memcpy(), with an implicit 8-bit data width
Definition: memory.h:94
A fixed-size array of bits, with compact storage and fast iteration.
Definition: array.h:231