tsIntegerSet.cpp

Public Defines

SETUPTO(upto) ( ((1<<(upto&31))-1)*2+1 )

Public Defines

SETUPTO(upto) ( ((1<<(upto&31))-1)*2+1 )

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#include "ts/tsIntegerSet.h"
 25#include "platform/platform.h"
 26#include "core/stream/stream.h"
 27
 28#define SETUPTO(upto) ( ((1<<(upto&31))-1)*2+1 ) // careful not to shift more than 31 times
 29
 30void TSIntegerSet::clearAll(S32 upto)
 31{
 32   AssertFatal(upto<=<a href="/coding/file/tsintegerset_8h/#tsintegerset_8h_1a5a8722ddd7f9fdf72c5f65063d7de677">MAX_TS_SET_SIZE</a>,"TSIntegerSet::clearAll: out of range");
 33
 34   dMemset(bits,0,(upto>>5)*4);
 35   if (upto&31)
 36      bits[upto>>5] &= ~<a href="/coding/file/tsintegerset_8cpp/#tsintegerset_8cpp_1a6d97dbe632e9b92b1719325a9088eed4">SETUPTO</a>(upto);
 37}
 38
 39void TSIntegerSet::setAll(S32 upto)
 40{
 41   AssertFatal(upto<=<a href="/coding/file/tsintegerset_8h/#tsintegerset_8h_1a5a8722ddd7f9fdf72c5f65063d7de677">MAX_TS_SET_SIZE</a>,"TSIntegerSet::setAll: out of range");
 42
 43   dMemset(bits,0xFFFFFFFF,(upto>>5)*4);
 44   if (upto&31)
 45      bits[upto>>5] |= SETUPTO(upto);
 46}
 47
 48bool TSIntegerSet::testAll(S32 upto) const
 49{
 50   AssertFatal(upto<=<a href="/coding/file/tsintegerset_8h/#tsintegerset_8h_1a5a8722ddd7f9fdf72c5f65063d7de677">MAX_TS_SET_SIZE</a>,"TSIntegerSet::testAll: out of range");
 51   S32 i;
 52   for (i=0; i<(upto>>5); i++)
 53      if (bits[i])
 54         return true;
 55   if (upto&31)
 56      return (bits[upto>>5] & SETUPTO(upto)) != 0;
 57   return false;
 58}
 59
 60S32 TSIntegerSet::count(S32 upto) const
 61{
 62   AssertFatal(upto<=<a href="/coding/file/tsintegerset_8h/#tsintegerset_8h_1a5a8722ddd7f9fdf72c5f65063d7de677">MAX_TS_SET_SIZE</a>,"TSIntegerSet::count: out of range");
 63
 64   S32 count = 0;
 65   U32 dword = bits[0];
 66   for (S32 i = 0; i < upto; i++)
 67   {
 68      // get next word
 69      if (!(i & 0x1F))
 70         dword = bits[i>>5];
 71      // test bits in word
 72      if (dword & (1 << (i & 0x1F)))
 73         count++;
 74   }
 75   return count;
 76}
 77
 78void TSIntegerSet::intersect(const TSIntegerSet & otherSet)
 79{
 80   for (S32 i=0; i<MAX_TS_SET_DWORDS; i++)
 81      bits[i] &= otherSet.bits[i];
 82}
 83
 84void TSIntegerSet::overlap(const TSIntegerSet & otherSet)
 85{
 86   for (S32 i=0; i<MAX_TS_SET_DWORDS; i++)
 87      bits[i] |= otherSet.bits[i];
 88}
 89
 90void TSIntegerSet::difference(const TSIntegerSet & otherSet)
 91{
 92   for (S32 i=0; i<MAX_TS_SET_DWORDS; i++)
 93      bits[i] = (bits[i] | otherSet.bits[i]) & ~(bits[i] & otherSet.bits[i]);
 94}
 95
 96void TSIntegerSet::takeAway(const TSIntegerSet & otherSet)
 97{
 98   for (S32 i=0; i<MAX_TS_SET_DWORDS; i++)
 99      bits[i] &= ~otherSet.bits[i];
100}
101
102S32 TSIntegerSet::start() const
103{
104   for (S32 i=0; i<MAX_TS_SET_DWORDS; i++)
105   {
106      // search for set bit one dword at a time
107      U32 dword = bits[i];
108      if (dword!=0)
109      {
110         // got dword, now search one byte at a time
111         S32 j = 0;
112         U32 mask = 0xFF;
113         do
114         {
115            if (dword&mask)
116            {
117               // got byte, now search one bit at a time
118               U32 bit = mask & ~(mask<<1); // grabs the smallest bit
119               do
120               {
121                  if (dword&bit)
122                     return (i<<5)+j;
123                  j++;
124                  bit <<= 1;
125               } while (1);
126            }
127            mask <<= 8;
128            j += 8;
129         } while (1);
130      }
131   }
132
133   return MAX_TS_SET_SIZE;
134}
135
136S32 TSIntegerSet::end() const
137{
138   for (S32 i=<a href="/coding/file/tsintegerset_8h/#tsintegerset_8h_1ad39475d294477a208f1c0c594dde7d5f">MAX_TS_SET_DWORDS</a>-1; i>=0; i--)
139   {
140      // search for set bit one dword at a time
141      U32 dword = bits[i];
142      if (bits[i])
143      {
144         // got dword, now search one byte at a time
145         S32 j = 31;
146         U32 mask = 0xFF000000;
147         do
148         {
149            if (dword&mask)
150            {
151               // got byte, now one bit at a time
152               U32 bit = mask & ~(mask>>1); // grabs the highest bit
153               do
154               {
155                  if (dword&bit)
156                     return (i<<5)+j+1;
157                  j--;
158                  bit >>= 1;
159               } while (1);
160            }
161            mask >>= 8;
162            j -= 8;
163         } while (1);
164      }
165   }
166
167   return 0;
168}
169
170void TSIntegerSet::next(S32 & i) const
171{
172   i++;
173   U32 idx = i>>5;
174   U32 bit = 1 << (i&31);
175   U32 dword = bits[idx] & ~(bit-1);
176   while (dword==0)
177   {
178      i = (i+32) & ~31;
179      if (i>=<a href="/coding/file/tsintegerset_8h/#tsintegerset_8h_1a5a8722ddd7f9fdf72c5f65063d7de677">MAX_TS_SET_SIZE</a>)
180         return;
181      dword=bits[++idx];
182      bit = 1;
183   }
184   dword = bits[idx];
185   while ( (bit & dword) == 0)
186   {
187      bit <<= 1;
188      i++;
189   }
190}
191
192/* Or would one byte at a time be better...
193void TSIntegerSet::next(S32 & i)
194{
195   U32 idx = i>>3;
196   U8 bit = 1 << (i&7);
197   U8 byte = ((U8*)bits)[idx] & ~(bit*2-1);
198   while (byte==0)
199   {
200      i = (i+8) & ~7;
201      if (i>=MAX_TS_SET_SIZE)
202         return;
203      byte=((U8*)bits)[++idx];
204      bit = 1;
205   }
206   byte = ((U8*)bits)[idx];
207   while (bit & byte == 0)
208   {
209      bit <<= 1;
210      i++;
211   }
212}
213*/
214
215void TSIntegerSet::copy(const TSIntegerSet & otherSet)
216{
217   dMemcpy(bits,otherSet.bits,MAX_TS_SET_DWORDS*4);
218}
219
220void TSIntegerSet::insert(S32 index, bool value)
221{
222   AssertFatal(index<MAX_TS_SET_SIZE,"TSIntegerSet::insert: out of range");
223
224   // shift bits in words after the insertion point
225   U32 endWord = (end() >> 5) + 1;
226   if (endWord >= MAX_TS_SET_DWORDS)
227      endWord = MAX_TS_SET_DWORDS-1;
228
229   for (S32 i = endWord; i > (index >> 5); i--)
230   {
231      bits[i] = bits[i] << 1;
232      if (bits[i-1] & 0x80000000)
233         bits[i] |= 0x1;
234   }
235
236   // shift to create space in target word
237   U32 lowMask = (1 << (index & 0x1f)) - 1;              // bits below the insert point
238   U32 highMask = ~(lowMask | (1 << (index & 0x1f)));    // bits above the insert point
239
240   S32 word = index >> 5;
241   bits[word] = ((bits[word] << 1) & highMask) | (bits[word] & lowMask);
242
243   // insert new value
244   if (value)
245      set(index);
246}
247
248void TSIntegerSet::erase(S32 index)
249{
250   AssertFatal(index<MAX_TS_SET_SIZE,"TSIntegerSet::erase: out of range");
251
252   // shift to erase bit in target word
253   S32 word = index >> 5;
254   U32 lowMask = (1 << (index & 0x1f)) - 1;              // bits below the erase point
255
256   bits[word] = ((bits[word] >> 1) & ~lowMask) | (bits[word] & lowMask);
257
258   // shift bits in words after the erase point
259   U32 endWord = (end() >> 5) + 1;
260   if (endWord >= MAX_TS_SET_DWORDS)
261      endWord = MAX_TS_SET_DWORDS-1;
262
263   for (S32 i = (index >> 5) + 1; i <= endWord; i++)
264   {
265      if (bits[i] & 0x1)
266         bits[i-1] |= 0x80000000;
267      bits[i] = bits[i] >> 1;
268   }
269}
270
271TSIntegerSet::TSIntegerSet()
272{
273   clearAll();
274}
275
276TSIntegerSet::TSIntegerSet(const TSIntegerSet & otherSet)
277{
278   copy(otherSet);
279}
280
281void TSIntegerSet::read(Stream * s)
282{
283   clearAll();
284
285   S32 numInts;
286   s->read(&numInts); // don't care about this
287
288   S32 sz;
289   s->read(&sz);
290   AssertFatal(sz<=<a href="/coding/file/tsintegerset_8h/#tsintegerset_8h_1ad39475d294477a208f1c0c594dde7d5f">MAX_TS_SET_DWORDS</a>,"TSIntegerSet::  set too large...increase max set size and re-compile");
291
292   for (S32 i=0; i<sz; i++) // now mirrors the write code...
293      s->read(&(bits[i]));
294}
295
296void TSIntegerSet::write(Stream * s) const
297{
298   s->write((S32)0); // don't do this anymore, keep in to avoid versioning
299   S32 i,sz=0;
300   for (i=0; i<MAX_TS_SET_DWORDS; i++)
301      if (bits[i]!=0)
302         sz=<a href="/coding/file/cmdgram_8cpp/#cmdgram_8cpp_1aa42a9a9cb6e2b93d7f825c395af871bf">i</a>+1;
303   s->write(sz);
304   for (i=0; i<sz; i++)
305      s->write(bits[i]);
306}
307
308