Foundation/NSArray/NSMutableArray_concrete.m

   1 /* Copyright (c) 2006-2007 Christopher J. W. Lloyd
   2
   3 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
   4
   5 The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
   6
   7 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
   8
   9 #import <Foundation/NSMutableArray_concrete.h>
  10 #import <Foundation/NSRaise.h>
  11 #import <Foundation/NSCoder.h>
  12 #import <Foundation/NSRaiseException.h>
  13
  14 @implementation NSMutableArray_concrete
  15
  16 static inline NSUInteger roundCapacityUp(NSUInteger capacity){
  17    return (capacity<1)?1:capacity;
  18 }
  19
  20
  21 NSMutableArray_concrete *NSMutableArray_concreteInit(NSMutableArray_concrete *self, id *objects, NSUInteger count, NSZone *zone)
  22 {
  23     NSUInteger i;
  24
  25     self->_count = count;
  26     self->_capacity = roundCapacityUp(count);
  27     self->_objects = NSZoneMalloc(zone, sizeof(id) * self->_capacity);
  28     for (i = 0; i < count; i++) {
  29         self->_objects[i] = [objects[i] retain];
  30     }
  31
  32     return self;
  33 }
  34
  35
  36 NSMutableArray_concrete *NSMutableArray_concreteInitWithCapacity(NSMutableArray_concrete *self, NSUInteger capacity, NSZone *zone)
  37 {
  38     self->_count = 0;
  39     self->_capacity = roundCapacityUp(capacity);
  40     self->_objects = NSZoneMalloc(zone, sizeof(id) * self->_capacity);
  41
  42     return self;
  43 }
  44
  45
  46 NSArray *NSMutableArray_concreteNew(NSZone *zone,id *objects,NSUInteger count) {
  47    NSMutableArray_concrete *self=NSAllocateObject([NSMutableArray_concrete class],0,zone);
  48     if (self) {
  49         self = NSMutableArray_concreteInit(self,objects,count,zone);
  50     }
  51    return self;
  52 }
  53
  54 NSArray *NSMutableArray_concreteNewWithCapacity(NSZone *zone,NSUInteger capacity) {
  55    NSMutableArray_concrete *self=NSAllocateObject([NSMutableArray_concrete class],0,zone);
  56     if (self) {
  57         self = NSMutableArray_concreteInitWithCapacity(self,capacity,zone);
  58     }
  59     return self;
  60 }
  61
  62 -init {
  63    return NSMutableArray_concreteInitWithCapacity(self,0,
  64      NSZoneFromPointer(self));
  65 }
  66
  67 -initWithArray:(NSArray *)array {
  68    NSUInteger i,count=[array count];
  69
  70    NSMutableArray_concreteInitWithCapacity(self,count,NSZoneFromPointer(self));
  71    self->_count=count;
  72    [array getObjects:_objects];
  73    for(i=0;i<count;i++)
  74     [_objects[i] retain];
  75
  76    return self;
  77 }
  78
  79 -initWithContentsOfFile:(NSString *)path {
  80    NSUnimplementedMethod();
  81    return self;
  82 }
  83
  84 -initWithObjects:(id *)objects count:(NSUInteger)count {
  85    return NSMutableArray_concreteInit(self,objects,count,
  86      NSZoneFromPointer(self));
  87 }
  88
  89 -initWithObjects:object,... {
  90    va_list  arguments;
  91    NSUInteger i,count;
  92    id      *objects;
  93
  94    va_start(arguments,object);
  95    count=1;
  96    while(va_arg(arguments,id)!=nil)
  97     count++;
  98    va_end(arguments);
  99
 100    objects=__builtin_alloca(sizeof(id)*count);
 101
 102    va_start(arguments,object);
 103    objects[0]=object;
 104    for(i=1;i<count;i++)
 105     objects[i]=va_arg(arguments,id);
 106    va_end(arguments);
 107
 108    return NSMutableArray_concreteInit(self,objects,count,NSZoneFromPointer(self));
 109 }
 110
 111 -initWithCapacity:(NSUInteger)capacity {
 112    return NSMutableArray_concreteInitWithCapacity(self,capacity,
 113      NSZoneFromPointer(self));
 114 }
 115
 116 -(void)dealloc {
 117    NSInteger count=_count;
 118
 119    while(--count>=0)
 120     [_objects[count] release];
 121
 122    NSZoneFree(NSZoneFromPointer(_objects),_objects);
 123    NSDeallocateObject(self);
 124    return;
 125    [super dealloc];
 126 }
 127
 128 -(NSUInteger)count {
 129    return _count;
 130 }
 131
 132 -objectAtIndex:(NSUInteger)index {
 133    if(index>=_count){
 134     NSRaiseException(NSRangeException,self,_cmd,@"index %d beyond count %d",index,[self count]);
 135     return nil;
 136    }
 137
 138    return _objects[index];
 139 }
 140
 141 -(void)addObject:object {
 142    if(object==nil){
 143     NSRaiseException(NSInvalidArgumentException,self,_cmd,@"nil object");
 144     return;
 145    }
 146
 147    [object retain];
 148
 149    _count++;
 150    if(_count>_capacity){
 151     _capacity=_count*2;
 152     _objects=NSZoneRealloc(NSZoneFromPointer(_objects),_objects,sizeof(id)*_capacity);
 153    }
 154    _objects[_count-1]=object;
 155 }
 156
 157 -(void)replaceObjectAtIndex:(NSUInteger)index withObject:object {
 158    if(object==nil){
 159     NSRaiseException(NSInvalidArgumentException,self,_cmd,@"nil object");
 160     return;
 161    }
 162
 163    if(index>=_count){
 164     NSRaiseException(NSRangeException,self,_cmd,@"index %d beyond count %d",index,[self count]);
 165     return;
 166    }
 167
 168    [object retain];
 169    [_objects[index] release];
 170    _objects[index]=object;
 171 }
 172
 173 -lastObject {
 174    if(_count==0)
 175     return nil;
 176
 177    return _objects[_count-1];
 178 }
 179
 180 -(void)insertObject:object atIndex:(NSUInteger)index {
 181    NSInteger c;
 182
 183    if(object==nil){
 184     NSRaiseException(NSInvalidArgumentException,self,_cmd,@"nil object");
 185     return;
 186    }
 187
 188    if(index>_count){
 189     NSRaiseException(NSRangeException,self,_cmd,@"index %d beyond count %d",index,[self count]);
 190     return;
 191    }
 192
 193    _count++;
 194    if(_count>_capacity){
 195     _capacity=_count*2;
 196     _objects=NSZoneRealloc(NSZoneFromPointer(_objects),
 197       _objects,sizeof(id)*_capacity);
 198    }
 199
 200    if(_count>1)
 201     for(c=_count-1;c>index && c>0;c--)
 202      _objects[c]=_objects[c-1];
 203
 204    _objects[index]=[object retain];
 205 }
 206
 207 static void removeObjectAtIndex(NSMutableArray_concrete *self,NSUInteger index) {
 208    NSUInteger i;
 209    id object;
 210
 211    object=self->_objects[index];
 212    self->_count--;
 213    for(i=index;i<self->_count;i++)
 214     self->_objects[i]=self->_objects[i+1];
 215
 216    [object release];
 217
 218    if(self->_capacity>self->_count*2){
 219     self->_capacity=self->_count;
 220     self->_objects=NSZoneRealloc(NSZoneFromPointer(self->_objects),self->_objects,sizeof(id)*self->_capacity);
 221    }
 222 }
 223
 224 -(void)removeObjectAtIndex:(NSUInteger)index {
 225    if(index>=_count){
 226     NSRaiseException(NSRangeException,self,_cmd,@"index %d beyond count %d",index,[self count]);
 227    }
 228
 229   removeObjectAtIndex(self,index);
 230 }
 231
 232 -(void)removeLastObject {
 233    if(_count==0){
 234     NSRaiseException(NSRangeException,self,_cmd,@"index %d beyond count %d",1,[self count]);
 235     return;
 236    }
 237
 238    removeObjectAtIndex(self,_count-1);
 239 }
 240
 241 -(void)removeAllObjects {
 242    NSUInteger i;
 243
 244    for(i=0;i<_count;i++)
 245     [_objects[i] release];
 246
 247    _count=0;
 248    if(self->_capacity>8){
 249     self->_capacity=8;
 250     self->_objects=NSZoneRealloc(NSZoneFromPointer(self->_objects),self->_objects,sizeof(id)*self->_capacity);
 251    }
 252 }
 253
 254 -(void)getObjects:(id *)objects {
 255    NSUInteger i;
 256
 257    for(i=0;i<_count;i++)
 258     objects[i]=_objects[i];
 259 }
 260
 261 -(NSUInteger)indexOfObjectIdenticalTo:object {
 262    NSInteger i;
 263
 264    for(i=0;i<self->_count;i++)
 265     if(self->_objects[i]==object)
 266      return i;
 267
 268    return NSNotFound;
 269 }
 270
 271 static inline NSUInteger indexOfObject(NSMutableArray_concrete *self,id object){
 272    NSUInteger i;
 273
 274    for(i=0;i<self->_count;i++)
 275     if([self->_objects[i] isEqual:object])
 276      return i;
 277
 278    return NSNotFound;
 279 }
 280
 281 -(NSUInteger)indexOfObject:object {
 282    return indexOfObject(self,object);
 283 }
 284
 285 -(BOOL)containsObject:object {
 286    return (indexOfObject(self,object)!=NSNotFound)?YES:NO;
 287 }
 288
 289 -(void)makeObjectsPerformSelector:(SEL)selector {
 290         NSInteger i, count = [self count];
 291
 292         for (i = 0; i < count; i++)
 293                 [_objects[i] performSelector:selector];
 294 }
 295
 296 // Bottom up merge
 297
 298 -(void)mergeUsingFunction:(NSInteger (*)(id, id, void *))compare context:(void *)context A: (id *)A left:(NSInteger)iLeft right:(NSInteger)iRight end:(NSInteger)iEnd B: (id *)B
 299 {
 300     NSInteger i0 = iLeft;
 301     NSInteger i1 = iRight;
 302     NSInteger j;
 303
 304     /* While there are elements in the left or right lists */
 305     for (j = iLeft; j < iEnd; j++)
 306     {
 307         /* If left list head exists and is <= existing right list head */
 308         if (i0 < iRight && (i1 >= iEnd || compare(A[i0], A[i1], context) != NSOrderedDescending))
 309         {
 310             B[j] = A[i0++];
 311         }
 312         else
 313         {
 314             B[j] = A[i1++];
 315         }
 316     }
 317 }
 318
 319 // iterative bottom up mergesort based on http://en.wikipedia.org/wiki/Merge_sort
 320 -(void)sortUsingFunction:(NSInteger (*)(id, id, void *))compare context:(void *)context {
 321   NSInteger n = _count;
 322
 323   /* array A[] has the items to sort; array B[] is a work array */
 324   id *A = _objects;
 325   id *B = NSZoneMalloc(NULL,(n+1)* sizeof(id));
 326
 327   /* Each 1-element run in A is already "sorted". */
 328
 329   /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. */
 330   for (int width = 1; width < n; width = 2 * width)
 331   {
 332       /* Array A is full of runs of length width. */
 333       for (int i = 0; i < n; i = i + 2 * width)
 334       {
 335           /* Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
 336           /* or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
 337           [self mergeUsingFunction: compare context: context A: A left: i right: MIN(i+width, n) end: MIN(i+2*width, n) B: B];
 338       }
 339       /* Now work array B is full of runs of length 2*width. */
 340       /* Copy array B to array A for next iteration. */
 341       memcpy(A, B, n * sizeof(id));
 342   }
 343
 344   free(B);
 345 }
 346
 347 -(NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)length;
 348 {
 349    if(state->state>=_count)
 350     return 0;
 351
 352    state->itemsPtr=_objects;
 353    state->state=_count;
 354
 355    state->mutationsPtr=(unsigned long*)self;
 356
 357    return _count;
 358 }
 359
 360 @end