err.no Git - sope/blob - sope-core/NGExtensions/NGBitSet.m

   1 /*
   2   Copyright (C) 2000-2005 SKYRIX Software AG
   3
   4   This file is part of SOPE.
   5
   6   SOPE is free software; you can redistribute it and/or modify it under
   7   the terms of the GNU Lesser General Public License as published by the
   8   Free Software Foundation; either version 2, or (at your option) any
   9   later version.
  10
  11   SOPE is distributed in the hope that it will be useful, but WITHOUT ANY
  12   WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14   License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public
  17   License along with SOPE; see the file COPYING.  If not, write to the
  18   Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19   02111-1307, USA.
  20 */
  21
  22 #import "common.h"
  23 #import "NGMemoryAllocation.h"
  24 #import "NGBitSet.h"
  25
  26 #define NGStorageSize   sizeof(NGBitSetStorage)
  27 #define NGBitsPerEntry  (NGStorageSize * 8)
  28 #define NGByteSize      (universe / 8)
  29
  30 #define NGTestBit(_x)   (((storage[ _x / NGBitsPerEntry ] & \
  31                          (1 << (_x % NGBitsPerEntry))) == 0) ? NO : YES)
  32
  33 @interface NGConcreteBitSetEnumerator : NSEnumerator
  34 {
  35 @public
  36   unsigned int    universe;
  37   unsigned int    count;
  38   NGBitSetStorage *storage;
  39
  40   unsigned int position;
  41   unsigned int found;
  42 }
  43
  44 - (id)nextObject;
  45
  46 @end
  47
  48 @implementation NGBitSet
  49
  50 + (id)bitSet {
  51   return [[[self alloc] init] autorelease];
  52 }
  53 + (id)bitSetWithCapacity:(unsigned)_capacity {
  54   return [[[self alloc] initWithCapacity:_capacity] autorelease];
  55 }
  56 + (id)bitSetWithBitSet:(NGBitSet *)_set {
  57   return [[[self alloc] initWithBitSet:_set] autorelease];
  58 }
  59
  60 - (id)initWithCapacity:(unsigned)_capacity {
  61   if ((self = [super init])) {
  62     self->universe = (_capacity / NGBitsPerEntry + 1) * NGBitsPerEntry;
  63     storage  = NGMallocAtomic(NGByteSize);
  64     memset(storage, 0, NGByteSize);
  65     count = 0;
  66   }
  67   return self;
  68 }
  69
  70 - (id)initWithBitSet:(NGBitSet *)_set {
  71   if ((self = [self initWithCapacity:NGBitsPerEntry])) {
  72     NSEnumerator *enumerator = [_set objectEnumerator];
  73     id obj = nil;
  74
  75     while ((obj = [enumerator nextObject]))
  76       [self addMember:[obj unsignedIntValue]];
  77
  78     enumerator = nil;
  79   }
  80   return self;
  81 }
  82 - (id)init {
  83   return [self initWithCapacity:NGBitsPerEntry];
  84 }
  85 - (id)initWithNullTerminatedArray:(unsigned int *)_array {
  86   if ((self = [self initWithCapacity:NGBitsPerEntry])) {
  87     while (*_array) {
  88       [self addMember:*_array];
  89       _array++;
  90     }
  91   }
  92   return self;
  93 }
  94
  95 - (void)dealloc {
  96   if (self->storage) {
  97     NGFree(self->storage);
  98     self->storage = NULL;
  99   }
 100   [super dealloc];
 101 }
 102
 103 /* storage */
 104
 105 - (void)_expandToInclude:(unsigned int)_element {
 106   unsigned int nu = (_element / NGBitsPerEntry + 1) * NGBitsPerEntry;
 107   if (nu > self->universe) {
 108     void *old = storage;
 109     storage = (NGBitSetStorage *)NGMallocAtomic(nu / 8);
 110     memset(storage, 0, nu / 8);
 111     if (old) {
 112       memcpy(storage, old, NGByteSize);
 113       NGFree(old);
 114       old = NULL;
 115     }
 116     self->universe = nu;
 117   }
 118 }
 119
 120 /* accessors */
 121
 122 - (unsigned int)capacity {
 123   return self->universe;
 124 }
 125 - (unsigned int)count {
 126   return count;
 127 }
 128
 129 /* membership */
 130
 131 - (BOOL)isMember:(unsigned int)_element {
 132   return (_element >= self->universe) ? NO : NGTestBit(_element);
 133 }
 134
 135 - (void)addMember:(unsigned int)_element {
 136   register unsigned int subIdxPattern = 1 << (_element % NGBitsPerEntry);
 137
 138   if (_element >= self->universe)
 139     [self _expandToInclude:_element];
 140
 141   if ((storage[ _element / NGBitsPerEntry ] & subIdxPattern) == 0) {
 142     storage[ _element / NGBitsPerEntry ] |= subIdxPattern;
 143     count++;
 144   }
 145 }
 146 - (void)addMembersInRange:(NSRange)_range {
 147   register unsigned int from = _range.location;
 148   register unsigned int to   = from + _range.length - 1;
 149
 150   if (to >= self->universe)
 151     [self _expandToInclude:to];
 152
 153   for (; from <= to; from++) {
 154     register unsigned int subIdxPattern = 1 << (from % NGBitsPerEntry);
 155
 156     if ((storage[ from / NGBitsPerEntry ] & subIdxPattern) == 0) {
 157       storage[ from / NGBitsPerEntry ] |= subIdxPattern;
 158       count++;
 159     }
 160   }
 161 }
 162
 163 - (void)addMembersFromBitSet:(NGBitSet *)_set {
 164   unsigned i;
 165
 166   if ([_set capacity] > self->universe)
 167     [self _expandToInclude:[_set capacity]];
 168
 169   for (i = 0; i < [_set capacity]; i++) {
 170     if ([_set isMember:i]) {
 171       register unsigned int subIdxPattern = 1 << (i % NGBitsPerEntry);
 172
 173       if ((storage[ i / NGBitsPerEntry ] & subIdxPattern) == 0) {
 174         storage[ i / NGBitsPerEntry ] |= subIdxPattern;
 175         count++;
 176       }
 177     }
 178   }
 179 }
 180
 181 - (void)removeMember:(unsigned int)_element {
 182   register unsigned int subIdxPattern = 1 << (_element % NGBitsPerEntry);
 183
 184   if (_element >= self->universe)
 185     return;
 186
 187   if ((storage[ _element / NGBitsPerEntry ] & subIdxPattern) != 0) {
 188     storage[ _element / NGBitsPerEntry ] -= subIdxPattern;
 189     count--;
 190   }
 191 }
 192 - (void)removeMembersInRange:(NSRange)_range {
 193   register unsigned int from = _range.location;
 194   register unsigned int to   = from + _range.length - 1;
 195
 196   if (from >= self->universe)
 197     return;
 198   if (to >= self->universe) to = self->universe - 1;
 199
 200   for (; from <= to; from++) {
 201     register unsigned int subIdxPattern = 1 << (from % NGBitsPerEntry);
 202
 203     if ((storage[ from / NGBitsPerEntry ] & subIdxPattern) != 0) {
 204       storage[ from / NGBitsPerEntry ] -= subIdxPattern;
 205       count--;
 206     }
 207   }
 208 }
 209 - (void)removeAllMembers {
 210   memset(storage, 0, NGByteSize);
 211   count = 0;
 212 }
 213
 214 - (unsigned int)firstMember {
 215   register unsigned int element;
 216
 217   for (element = 0; element < self->universe; element++) {
 218     if (NGTestBit(element))
 219       return element;
 220   }
 221   return NSNotFound;
 222 }
 223
 224 - (unsigned int)lastMember {
 225   register unsigned int element;
 226
 227   for (element = (self->universe - 1); element >= 0; element--) {
 228     if (NGTestBit(element))
 229       return element;
 230   }
 231   return NSNotFound;
 232 }
 233
 234 /* equality */
 235
 236 - (BOOL)isEqual:(id)_object {
 237   if (self == _object) return YES;
 238   if ([self class] != [_object class]) return NO;
 239   return [self isEqualToSet:_object];
 240 }
 241 - (BOOL)isEqualToSet:(NGBitSet *)_set {
 242   if (self == _set) return YES;
 243   if (count != [_set count]) return NO;
 244
 245   {
 246     register unsigned int element;
 247
 248     for (element = 0; element < self->universe; element++) {
 249       if (NGTestBit(element)) {
 250         if (![_set isMember:element])
 251           return NO;
 252       }
 253     }
 254     return YES;
 255   }
 256 }
 257
 258 /* enumerator */
 259
 260 - (NSEnumerator *)objectEnumerator {
 261   if (self->count == 0)
 262     return nil;
 263   else {
 264     NGConcreteBitSetEnumerator *en = [[NGConcreteBitSetEnumerator alloc] init];
 265     en->universe = self->universe;
 266     en->count    = self->count;
 267     en->storage  = self->storage;
 268     return [en autorelease];
 269   }
 270 }
 271
 272 /* NSCopying */
 273
 274 - (id)copy {
 275   return [self copyWithZone:[self zone]];
 276 }
 277 - (id)copyWithZone:(NSZone *)_zone {
 278   return [[NGBitSet alloc] initWithBitSet:self];
 279 }
 280
 281
 282 /* NSCoding */
 283
 284 - (void)encodeWithCoder:(NSCoder *)_coder {
 285   unsigned int element;
 286   register unsigned int found;
 287
 288   [_coder encodeValueOfObjCType:@encode(unsigned int) at:&count];
 289
 290   for (element = 0, found = 0; (element < self->universe) && (found < count); element++) {
 291     if (NGTestBit(element)) {
 292       [_coder encodeValueOfObjCType:@encode(unsigned int) at:&element];
 293       found++;
 294     }
 295   }
 296 }
 297 - (id)initWithCoder:(NSCoder *)_coder {
 298   if ((self = [super init])) {
 299     unsigned int nc;
 300     register unsigned int cnt;
 301
 302     self->universe = NGBitsPerEntry;
 303     storage  = NGMallocAtomic(NGByteSize);
 304     memset(storage, 0, NGByteSize);
 305
 306     [_coder decodeValueOfObjCType:@encode(unsigned int) at:&nc];
 307
 308     for (cnt = 0; cnt < nc; cnt++) {
 309       unsigned int member;
 310       [_coder decodeValueOfObjCType:@encode(unsigned int) at:&member];
 311       [self addMember:member];
 312     }
 313   }
 314   return self;
 315 }
 316
 317 /* description */
 318
 319 - (NSString *)description {
 320   return [NSString stringWithFormat:
 321                      @"<NGBitSet[0x%p]: capacity=%u count=%u content=%@>",
 322                      self, self->universe, self->count,
 323                      [[self toArray] description]];
 324 }
 325
 326 - (NSArray *)toArray {
 327   NSMutableArray *result = [[NSMutableArray alloc] initWithCapacity:count + 1];
 328   register unsigned int element, found;
 329
 330   for (element = 0, found = 0;
 331        (element < self->universe) && (found < self->count); element++) {
 332
 333     if (NGTestBit(element)) {
 334       [result addObject:[NSNumber numberWithUnsignedInt:element]];
 335       found++;
 336     }
 337   }
 338   return [[[result autorelease] copy] autorelease];
 339 }
 340
 341 @end /* NGBitSet */
 342
 343 @implementation NGConcreteBitSetEnumerator
 344
 345 - (id)nextObject {
 346   if (self->found == self->count)
 347     return nil;
 348   if (self->position >= self->universe)
 349     return nil;
 350
 351   while (!NGTestBit(self->position))
 352     self->position++;
 353
 354   self->found++;
 355   self->position++;
 356
 357   return [NSNumber numberWithUnsignedInt:(self->position - 1)];
 358 }
 359
 360 @end /* NGConcreteBitSetEnumerator */
 361
 362 NSString *stringValueForBitset(unsigned int _set, char _setC, char _unsetC,
 363                                short _wide) {
 364   char           buf[_wide + 1];
 365   register short pos;
 366
 367   for (pos = 0; pos < _wide; pos++) {
 368     register unsigned int v = (1 << pos);
 369     buf[(int)pos] = ((v & _set) == v) ? _setC : _unsetC;
 370   }
 371
 372   buf[_wide] = '\0';
 373   return [NSString stringWithCString:buf];
 374 }
 375
 376 void __link_NGExtensions_NGBitSet() {
 377   __link_NGExtensions_NGBitSet();
 378 }