2 Copyright (C) 2000-2005 SKYRIX Software AG
4 This file is part of SOPE.
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
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.
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
23 #import "NGMemoryAllocation.h"
26 #define NGStorageSize sizeof(NGBitSetStorage)
27 #define NGBitsPerEntry (NGStorageSize * 8)
28 #define NGByteSize (universe / 8)
30 #define NGTestBit(_x) (((storage[ _x / NGBitsPerEntry ] & \
31 (1 << (_x % NGBitsPerEntry))) == 0) ? NO : YES)
33 @interface NGConcreteBitSetEnumerator : NSEnumerator
36 unsigned int universe;
38 NGBitSetStorage *storage;
40 unsigned int position;
48 @implementation NGBitSet
51 return [[[self alloc] init] autorelease];
53 + (id)bitSetWithCapacity:(unsigned)_capacity {
54 return [[[self alloc] initWithCapacity:_capacity] autorelease];
56 + (id)bitSetWithBitSet:(NGBitSet *)_set {
57 return [[[self alloc] initWithBitSet:_set] autorelease];
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);
70 - (id)initWithBitSet:(NGBitSet *)_set {
71 if ((self = [self initWithCapacity:NGBitsPerEntry])) {
72 NSEnumerator *enumerator = [_set objectEnumerator];
75 while ((obj = [enumerator nextObject]))
76 [self addMember:[obj unsignedIntValue]];
83 return [self initWithCapacity:NGBitsPerEntry];
85 - (id)initWithNullTerminatedArray:(unsigned int *)_array {
86 if ((self = [self initWithCapacity:NGBitsPerEntry])) {
88 [self addMember:*_array];
97 NGFree(self->storage);
105 - (void)_expandToInclude:(unsigned int)_element {
106 unsigned int nu = (_element / NGBitsPerEntry + 1) * NGBitsPerEntry;
107 if (nu > self->universe) {
109 storage = (NGBitSetStorage *)NGMallocAtomic(nu / 8);
110 memset(storage, 0, nu / 8);
112 memcpy(storage, old, NGByteSize);
122 - (unsigned int)capacity {
123 return self->universe;
125 - (unsigned int)count {
131 - (BOOL)isMember:(unsigned int)_element {
132 return (_element >= self->universe) ? NO : NGTestBit(_element);
135 - (void)addMember:(unsigned int)_element {
136 register unsigned int subIdxPattern = 1 << (_element % NGBitsPerEntry);
138 if (_element >= self->universe)
139 [self _expandToInclude:_element];
141 if ((storage[ _element / NGBitsPerEntry ] & subIdxPattern) == 0) {
142 storage[ _element / NGBitsPerEntry ] |= subIdxPattern;
146 - (void)addMembersInRange:(NSRange)_range {
147 register unsigned int from = _range.location;
148 register unsigned int to = from + _range.length - 1;
150 if (to >= self->universe)
151 [self _expandToInclude:to];
153 for (; from <= to; from++) {
154 register unsigned int subIdxPattern = 1 << (from % NGBitsPerEntry);
156 if ((storage[ from / NGBitsPerEntry ] & subIdxPattern) == 0) {
157 storage[ from / NGBitsPerEntry ] |= subIdxPattern;
163 - (void)addMembersFromBitSet:(NGBitSet *)_set {
166 if ([_set capacity] > self->universe)
167 [self _expandToInclude:[_set capacity]];
169 for (i = 0; i < [_set capacity]; i++) {
170 if ([_set isMember:i]) {
171 register unsigned int subIdxPattern = 1 << (i % NGBitsPerEntry);
173 if ((storage[ i / NGBitsPerEntry ] & subIdxPattern) == 0) {
174 storage[ i / NGBitsPerEntry ] |= subIdxPattern;
181 - (void)removeMember:(unsigned int)_element {
182 register unsigned int subIdxPattern = 1 << (_element % NGBitsPerEntry);
184 if (_element >= self->universe)
187 if ((storage[ _element / NGBitsPerEntry ] & subIdxPattern) != 0) {
188 storage[ _element / NGBitsPerEntry ] -= subIdxPattern;
192 - (void)removeMembersInRange:(NSRange)_range {
193 register unsigned int from = _range.location;
194 register unsigned int to = from + _range.length - 1;
196 if (from >= self->universe)
198 if (to >= self->universe) to = self->universe - 1;
200 for (; from <= to; from++) {
201 register unsigned int subIdxPattern = 1 << (from % NGBitsPerEntry);
203 if ((storage[ from / NGBitsPerEntry ] & subIdxPattern) != 0) {
204 storage[ from / NGBitsPerEntry ] -= subIdxPattern;
209 - (void)removeAllMembers {
210 memset(storage, 0, NGByteSize);
214 - (unsigned int)firstMember {
215 register unsigned int element;
217 for (element = 0; element < self->universe; element++) {
218 if (NGTestBit(element))
224 - (unsigned int)lastMember {
225 register unsigned int element;
227 for (element = (self->universe - 1); element >= 0; element--) {
228 if (NGTestBit(element))
236 - (BOOL)isEqual:(id)_object {
237 if (self == _object) return YES;
238 if ([self class] != [_object class]) return NO;
239 return [self isEqualToSet:_object];
241 - (BOOL)isEqualToSet:(NGBitSet *)_set {
242 if (self == _set) return YES;
243 if (count != [_set count]) return NO;
246 register unsigned int element;
248 for (element = 0; element < self->universe; element++) {
249 if (NGTestBit(element)) {
250 if (![_set isMember:element])
260 - (NSEnumerator *)objectEnumerator {
261 if (self->count == 0)
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];
275 return [self copyWithZone:[self zone]];
277 - (id)copyWithZone:(NSZone *)_zone {
278 return [[NGBitSet alloc] initWithBitSet:self];
284 - (void)encodeWithCoder:(NSCoder *)_coder {
285 unsigned int element;
286 register unsigned int found;
288 [_coder encodeValueOfObjCType:@encode(unsigned int) at:&count];
290 for (element = 0, found = 0; (element < self->universe) && (found < count); element++) {
291 if (NGTestBit(element)) {
292 [_coder encodeValueOfObjCType:@encode(unsigned int) at:&element];
297 - (id)initWithCoder:(NSCoder *)_coder {
298 if ((self = [super init])) {
300 register unsigned int cnt;
302 self->universe = NGBitsPerEntry;
303 storage = NGMallocAtomic(NGByteSize);
304 memset(storage, 0, NGByteSize);
306 [_coder decodeValueOfObjCType:@encode(unsigned int) at:&nc];
308 for (cnt = 0; cnt < nc; cnt++) {
310 [_coder decodeValueOfObjCType:@encode(unsigned int) at:&member];
311 [self addMember:member];
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]];
326 - (NSArray *)toArray {
327 NSMutableArray *result = [[NSMutableArray alloc] initWithCapacity:count + 1];
328 register unsigned int element, found;
330 for (element = 0, found = 0;
331 (element < self->universe) && (found < self->count); element++) {
333 if (NGTestBit(element)) {
334 [result addObject:[NSNumber numberWithUnsignedInt:element]];
338 return [[[result autorelease] copy] autorelease];
343 @implementation NGConcreteBitSetEnumerator
346 if (self->found == self->count)
348 if (self->position >= self->universe)
351 while (!NGTestBit(self->position))
357 return [NSNumber numberWithUnsignedInt:(self->position - 1)];
360 @end /* NGConcreteBitSetEnumerator */
362 NSString *stringValueForBitset(unsigned int _set, char _setC, char _unsetC,
367 for (pos = 0; pos < _wide; pos++) {
368 register unsigned int v = (1 << pos);
369 buf[(int)pos] = ((v & _set) == v) ? _setC : _unsetC;
373 return [NSString stringWithCString:buf];
376 void __link_NGExtensions_NGBitSet() {
377 __link_NGExtensions_NGBitSet();