Line data    Source code

       1           0 : /*
       2             : OOShipGroup.m
       3             : 
       4             : IMPLEMENTATION NOTE:
       5             : This is implemented as a dynamic array rather than a hash table for the
       6             : following reasons:
       7             :  *      Ship groups are generally quite small, not motivating a more complex
       8             :         implementation.
       9             :  *      The code ship groups replace was all array-based and not a significant
      10             :         bottleneck.
      11             :  *      Ship groups are compacted (i.e., dead weak references removed) as a side
      12             :         effect of iteration.
      13             :  *      Many uses of ship groups involve iterating over the whole group anyway.
      14             : 
      15             : 
      16             : Oolite
      17             : Copyright (C) 2004-2013 Giles C Williams and contributors
      18             : 
      19             : This program is free software; you can redistribute it and/or
      20             : modify it under the terms of the GNU General Public License
      21             : as published by the Free Software Foundation; either version 2
      22             : of the License, or (at your option) any later version.
      23             : 
      24             : This program is distributed in the hope that it will be useful,
      25             : but WITHOUT ANY WARRANTY; without even the implied warranty of
      26             : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      27             : GNU General Public License for more details.
      28             : 
      29             : You should have received a copy of the GNU General Public License
      30             : along with this program; if not, write to the Free Software
      31             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
      32             : MA 02110-1301, USA.
      33             : 
      34             : */
      35             : 
      36             : #import "ShipEntity.h"
      37             : #import "OOShipGroup.h"
      38             : #import "OOMaths.h"
      39             : 
      40             : 
      41           0 : enum
      42             : {
      43             :         kMinSize                                = 4,
      44             :         kMaxFreeSpace                   = 128
      45             : };
      46             : 
      47             : 
      48           0 : @interface OOShipGroupEnumerator: NSEnumerator
      49             : {
      50             :         // ivars are public so ShipGroupIterate() can peek at both these and OOShipGroup's. Naughty!
      51             : @public
      52           0 :         OOShipGroup                             *_group;
      53           0 :         NSUInteger                              _index, _updateCount;
      54           0 :         BOOL                                    _considerCleanup, _cleanupNeeded;
      55             : }
      56             : 
      57           0 : - (id) initWithShipGroup:(OOShipGroup *)group;
      58             : 
      59           0 : - (NSUInteger) index;
      60           0 : - (void) setPerformCleanup:(BOOL)flag;
      61             : 
      62             : @end
      63             : 
      64             : 
      65             : @interface OOShipGroup (Private)
      66             : 
      67           0 : - (BOOL) resizeTo:(NSUInteger)newCapacity;
      68           0 : - (void) cleanUp;
      69             : 
      70           0 : - (NSUInteger) updateCount;
      71             : 
      72             : @end
      73             : 
      74             : 
      75           0 : static id ShipGroupIterate(OOShipGroupEnumerator *enumerator);
      76             : 
      77             : 
      78             : @implementation OOShipGroup
      79             : 
      80             : - (id) init
      81             : {
      82             :         return [self initWithName:nil];
      83             : }
      84             : 
      85             : 
      86             : - (id) initWithName:(NSString *)name
      87             : {
      88             :         if ((self = [super init]))
      89             :         {
      90             :                 _capacity = kMinSize;
      91             :                 _members = malloc(sizeof *_members * _capacity);
      92             :                 if (_members == NULL)
      93             :                 {
      94             :                         [self release];
      95             :                         return nil;
      96             :                 }
      97             :                 
      98             :                 [self setName:name];
      99             :         }
     100             :         
     101             :         return self;
     102             : }
     103             : 
     104             : 
     105             : + (instancetype) groupWithName:(NSString *)name
     106             : {
     107             :         return [[[self alloc] initWithName:name] autorelease];
     108             : }
     109             : 
     110             : 
     111             : + (instancetype) groupWithName:(NSString *)name leader:(ShipEntity *)leader
     112             : {
     113             :         OOShipGroup *result = [self groupWithName:name];
     114             :         [result setLeader:leader];
     115             :         return result;
     116             : }
     117             : 
     118             : 
     119           0 : - (void) dealloc
     120             : {
     121             :         NSUInteger i;
     122             :         
     123             :         for (i = 0; i < _count; i++)
     124             :         {
     125             :                 [_members[i] release];
     126             :         }
     127             :         free(_members);
     128             :         [_name release];
     129             :         
     130             :         [super dealloc];
     131             : }
     132             : 
     133             : 
     134           0 : - (NSString *) descriptionComponents
     135             : {
     136             :         NSString *desc = [NSString stringWithFormat:@"%llu ships", (unsigned long long)_count];
     137             :         if ([self name] != nil)
     138             :         {
     139             :                 desc = [NSString stringWithFormat:@"\"%@\", %@", [self name], desc];
     140             :         }
     141             :         if ([self leader] != nil)
     142             :         {
     143             :                 desc = [NSString stringWithFormat:@"%@, leader: %@", desc, [[self leader] shortDescription]];
     144             :         }
     145             :         return desc;
     146             : }
     147             : 
     148             : 
     149             : - (NSString *) name
     150             : {
     151             :         return _name;
     152             : }
     153             : 
     154             : 
     155             : - (void) setName:(NSString *)name
     156             : {
     157             :         _updateCount++;
     158             :         
     159             :         if (_name != name)
     160             :         {
     161             :                 [_name release];
     162             :                 _name = [name retain];
     163             :         }
     164             : }
     165             : 
     166             : 
     167             : - (ShipEntity *) leader
     168             : {
     169             :         ShipEntity *result = [_leader weakRefUnderlyingObject];
     170             :         
     171             :         // If reference is stale, delete weakref object.
     172             :         if (result == nil && _leader != nil)
     173             :         {
     174             :                 [_leader release];
     175             :                 _leader = nil;
     176             :         }
     177             :         
     178             :         return result;
     179             : }
     180             : 
     181             : 
     182             : - (void) setLeader:(ShipEntity *)leader
     183             : {
     184             :         _updateCount++;
     185             :         
     186             :         if (leader != [self leader])
     187             :         {
     188             :                 [_leader release];
     189             :                 [self addShip:leader];
     190             :                 _leader = [leader weakRetain];
     191             :         }
     192             : }
     193             : 
     194             : 
     195             : - (NSEnumerator *) objectEnumerator
     196             : {
     197             :         return [[[OOShipGroupEnumerator alloc] initWithShipGroup:self] autorelease];
     198             : }
     199             : 
     200             : 
     201             : - (NSEnumerator *) mutationSafeEnumerator
     202             : {
     203             :         return [[self memberArray] objectEnumerator];
     204             : }
     205             : 
     206             : 
     207             : - (NSSet *) members
     208             : {
     209             :         return [NSSet setWithArray:[self memberArray]];
     210             : }
     211             : 
     212             : 
     213             : - (NSSet *) membersExcludingLeader
     214             : {
     215             :         return [NSSet setWithArray:[self memberArrayExcludingLeader]];
     216             : }
     217             : 
     218             : 
     219             : #if OOLITE_FAST_ENUMERATION
     220             : - (NSArray *) memberArray
     221             : {
     222             :         id                                              *objects = NULL;
     223             :         NSUInteger                              count = 0;
     224             :         NSArray                                 *result = nil;
     225             :         
     226             :         if (_count == 0)  return [NSArray array];
     227             :         
     228             :         objects = malloc(sizeof *objects * _count);
     229             :         for (id ship in self)
     230             :         {
     231             :                 objects[count++] = ship;
     232             :         }
     233             :         
     234             :         result = [NSArray arrayWithObjects:objects count:count];
     235             :         free(objects);
     236             :         
     237             :         return result;
     238             : }
     239             : 
     240             : 
     241             : - (NSArray *) memberArrayExcludingLeader
     242             : {
     243             :         id                                              *objects = NULL;
     244             :         NSUInteger                              count = 0;
     245             :         NSArray                                 *result = nil;
     246             :         ShipEntity                              *leader = nil;
     247             :         
     248             :         if (_count == 0)  return [NSArray array];
     249             :         leader = self.leader;
     250             :         
     251             :         objects = malloc(sizeof *objects * _count);
     252             :         for (id ship in self)
     253             :         {
     254             :                 if (ship != leader)
     255             :                 {
     256             :                         objects[count++] = ship;
     257             :                 }
     258             :         }
     259             :         
     260             :         result = [NSArray arrayWithObjects:objects count:count];
     261             :         free(objects);
     262             :         
     263             :         return result;
     264             : }
     265             : 
     266             : 
     267             : - (BOOL) containsShip:(ShipEntity *)ship
     268             : {
     269             :         ShipEntity                              *containedShip = nil;
     270             :         
     271             :         for (containedShip in self)
     272             :         {
     273             :                 if ([ship isEqual:containedShip])
     274             :                 {
     275             :                         return YES;
     276             :                 }
     277             :         }
     278             :         
     279             :         return NO;
     280             : }
     281             : #else
     282             : - (NSArray *) memberArray
     283             : {
     284             :         return [[self objectEnumerator] allObjects];
     285             : }
     286             : 
     287             : 
     288             : - (NSArray *) memberArrayExcludingLeader
     289             : {
     290             :         id                                              *objects = NULL;
     291             :         NSUInteger                              count = 0;
     292             :         NSArray                                 *result = nil;
     293             :         NSEnumerator                    *shipEnum = nil;
     294             :         ShipEntity                              *ship = nil;
     295             :         ShipEntity                              *leader = nil;
     296             :         
     297             :         if (_count == 0)  return [NSArray array];
     298             :         leader = [self leader];
     299             :         if (leader == nil)  return [self memberArray];
     300             :         
     301             :         objects = malloc(sizeof *objects * _count);
     302             :         for (shipEnum = [self objectEnumerator]; (ship = [shipEnum nextObject]); )
     303             :         {
     304             :                 if (ship != leader)
     305             :                 {
     306             :                         objects[count++] = ship;
     307             :                 }
     308             :         }
     309             :         
     310             :         result = [NSArray arrayWithObjects:objects count:count];
     311             :         free(objects);
     312             :         
     313             :         return result;
     314             : }
     315             : 
     316             : 
     317             : - (BOOL) containsShip:(ShipEntity *)ship
     318             : {
     319             :         OOShipGroupEnumerator   *shipEnum = nil;
     320             :         ShipEntity                              *containedShip = nil;
     321             :         BOOL                                    result = NO;
     322             :         
     323             :         shipEnum = (OOShipGroupEnumerator *)[self objectEnumerator];
     324             :         [shipEnum setPerformCleanup:NO];
     325             :         while ((containedShip = [shipEnum nextObject]))
     326             :         {
     327             :                 if ([ship isEqual:containedShip])
     328             :                 {
     329             :                         result = YES;
     330             :                         break;
     331             :                 }
     332             :         }
     333             :         
     334             :         // Clean up
     335             :         [self cleanUp];
     336             :         
     337             :         return result;
     338             : }
     339             : #endif
     340             : 
     341             : 
     342             : - (BOOL) addShip:(ShipEntity *)ship
     343             : {
     344             :         _updateCount++;
     345             :         
     346             :         if ([self containsShip:ship])  return YES;      // it's in the group already, result!
     347             :         
     348             :         // Ensure there's space.
     349             :         if (_count == _capacity)
     350             :         {
     351             :                 if (![self resizeTo:(_capacity > kMaxFreeSpace) ? (_capacity + kMaxFreeSpace) : (_capacity * 2)])
     352             :                 {
     353             :                         if (![self resizeTo:_capacity + 1])
     354             :                         {
     355             :                                 // Out of memory?
     356             :                                 return NO;
     357             :                         }
     358             :                 }
     359             :         }
     360             :         
     361             :         _members[_count++] = [ship weakRetain];
     362             :         return YES;
     363             : }
     364             : 
     365             : 
     366             : - (BOOL) removeShip:(ShipEntity *)ship
     367             : {
     368             :         OOShipGroupEnumerator   *shipEnum = nil;
     369             :         ShipEntity                              *containedShip = nil;
     370             :         NSUInteger                              index;
     371             :         BOOL                                    foundIt = NO;
     372             :         
     373             :         _updateCount++;
     374             :         
     375             :         if (ship == [self leader])  [self setLeader:nil];
     376             :         
     377             :         shipEnum = (OOShipGroupEnumerator *)[self objectEnumerator];
     378             :         [shipEnum setPerformCleanup:NO];
     379             :         while ((containedShip = [shipEnum nextObject]))
     380             :         {
     381             :                 if ([ship isEqual:containedShip])
     382             :                 {
     383             :                         index = [shipEnum index] - 1;
     384             :                         _members[index] = _members[--_count];
     385             :                         foundIt = YES;
     386             :                         
     387             :                         // Clean up
     388             :                         [ship setGroup:nil];
     389             :                         [ship setOwner:ship];
     390             :                         [self cleanUp];
     391             :                         break;
     392             :                 }
     393             :         }
     394             :         return foundIt;
     395             : }
     396             : 
     397             : /* TODO post-1.78: profiling indicates this is a noticeable
     398             :  * contributor to ShipEntity::update time. Consider optimisation: may
     399             :  * be possible to return _count if invalidation of weakref and group
     400             :  * removal in ShipEntity::dealloc keeps the data consistent anyway -
     401             :  * CIM */
     402             : 
     403             : - (NSUInteger) count
     404             : {
     405             :         NSEnumerator            *memberEnum = nil;
     406             :         NSUInteger                      result = 0;
     407             :         
     408             :         if (_count != 0)
     409             :         {
     410             :                 memberEnum = [self objectEnumerator];
     411             :                 while ([memberEnum nextObject] != nil)  result++;
     412             :         }
     413             :         
     414             :         assert(result == _count);
     415             :         
     416             :         return result;
     417             : }
     418             : 
     419             : 
     420             : - (BOOL) isEmpty
     421             : {
     422             :         if (_count == 0)  return YES;
     423             :         
     424             :         return [[self objectEnumerator] nextObject] == nil;
     425             : }
     426             : 
     427             : 
     428           0 : - (BOOL) resizeTo:(NSUInteger)newCapacity
     429             : {
     430             :         OOWeakReference                 **temp = NULL;
     431             :         
     432             :         if (newCapacity < _count)  return NO;
     433             :         
     434             :         temp = realloc(_members, newCapacity * sizeof *_members);
     435             :         if (temp == NULL)  return NO;
     436             :         
     437             :         _members = temp;
     438             :         _capacity = newCapacity;
     439             :         return YES;
     440             : }
     441             : 
     442             : 
     443           0 : - (void) cleanUp
     444             : {
     445             :         NSUInteger                              newCapacity = _capacity;
     446             :         
     447             :         if (_count >= kMaxFreeSpace)
     448             :         {
     449             :                 if (_capacity > _count + kMaxFreeSpace)
     450             :                 {
     451             :                         newCapacity = _count + 1;       // +1 keeps us at powers of two + multiples of kMaxFreespace.
     452             :                 }
     453             :         }
     454             :         else
     455             :         {
     456             :                 if (_capacity > _count * 2)
     457             :                 {
     458             :                         newCapacity = OORoundUpToPowerOf2_NS(_count);
     459             :                         if (newCapacity < kMinSize) newCapacity = kMinSize;
     460             :                 }
     461             :         }
     462             :         
     463             :         if (newCapacity != _capacity)  [self resizeTo:newCapacity];
     464             : }
     465             : 
     466             : 
     467           0 : - (NSUInteger) updateCount
     468             : {
     469             :         return _updateCount;
     470             : }
     471             : 
     472             : 
     473           0 : static id ShipGroupIterate(OOShipGroupEnumerator *enumerator)
     474             : {
     475             :         // The work is done here so that we can have access to both OOShipGroup's and OOShipGroupEnumerator's ivars.
     476             :         
     477             :         OOShipGroup                             *group = enumerator->_group;
     478             :         ShipEntity                              *result = nil;
     479             :         BOOL                                    cleanupNeeded = NO;
     480             :         
     481             :         if (enumerator->_updateCount != group->_updateCount)
     482             :         {
     483             :                 [NSException raise:NSGenericException format:@"Collection <OOShipGroup: %p> was mutated while being enumerated.", group];
     484             :         }
     485             :         
     486             :         while (enumerator->_index < group->_count)
     487             :         {
     488             :                 result = [group->_members[enumerator->_index] weakRefUnderlyingObject];
     489             :                 if (result != nil)
     490             :                 {
     491             :                         enumerator->_index++;
     492             :                         break;
     493             :                 }
     494             :                 
     495             :                 // If we got here, the group contains a stale reference to a dead ship.
     496             :                 group->_members[enumerator->_index] = group->_members[--group->_count];
     497             :                 cleanupNeeded = YES;
     498             :         }
     499             :         
     500             :         // Clean-up handling. Only perform actual clean-up at end of iteration.
     501             :         if (enumerator->_considerCleanup)
     502             :         {
     503             :                 enumerator->_cleanupNeeded = enumerator->_cleanupNeeded && cleanupNeeded;
     504             :                 if (enumerator->_cleanupNeeded && result == nil)
     505             :                 {
     506             :                         [group cleanUp];
     507             :                 }
     508             :         }
     509             :         
     510             :         return result;
     511             : }
     512             : 
     513             : 
     514             : #if OOLITE_FAST_ENUMERATION
     515           0 : - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len
     516             : {
     517             :         NSUInteger                              srcIndex, dstIndex = 0;
     518             :         ShipEntity                              *item = nil;
     519             :         BOOL                                    cleanupNeeded = NO;
     520             :         
     521             :         srcIndex = state->state;
     522             :         while (srcIndex < _count && dstIndex < len)
     523             :         {
     524             :                 item = [_members[srcIndex] weakRefUnderlyingObject];
     525             :                 if (item != nil)
     526             :                 {
     527             :                         stackbuf[dstIndex++] = item;
     528             :                         srcIndex++;
     529             :                 }
     530             :                 else
     531             :                 {
     532             :                         _members[srcIndex] = _members[--_count];
     533             :                         cleanupNeeded = YES;
     534             :                 }
     535             :         }
     536             :         
     537             :         if (cleanupNeeded)  [self cleanUp];
     538             :         
     539             :         state->state = srcIndex;
     540             :         state->itemsPtr = stackbuf;
     541             :         state->mutationsPtr = &_updateCount;
     542             :         
     543             :         return dstIndex;
     544             : }
     545             : #endif
     546             : 
     547             : 
     548             : /*      This method exists purely to suppress Clang static analyzer warnings that
     549             :         this ivar is unused (but may be used by categories, which they are).
     550             :         FIXME: there must be a feature macro we can use to avoid actually building
     551             :         this into the app, but I can't find it in docs.
     552             : */
     553           0 : - (BOOL) suppressClangStuff
     554             : {
     555             :         return !_jsSelf;
     556             : }
     557             : 
     558             : @end
     559             : 
     560             : 
     561             : @implementation OOShipGroupEnumerator
     562             : 
     563             : - (id) initWithShipGroup:(OOShipGroup *)group
     564             : {
     565             :         assert(group != nil);
     566             :         
     567             :         if ((self = [super init]))
     568             :         {
     569             :                 _group = [group retain];
     570             :                 _considerCleanup = YES;
     571             :                 _updateCount = [_group updateCount];
     572             :         }
     573             :         
     574             :         return self;
     575             : }
     576             : 
     577             : 
     578           0 : - (void) dealloc
     579             : {
     580             :         DESTROY(_group);
     581             :         
     582             :         [super dealloc];
     583             : }
     584             : 
     585             : 
     586           0 : - (id) nextObject
     587             : {
     588             :         return ShipGroupIterate(self);
     589             : }
     590             : 
     591             : 
     592             : - (NSUInteger) index
     593             : {
     594             :         return _index;
     595             : }
     596             : 
     597             : 
     598             : - (void) setPerformCleanup:(BOOL)flag
     599             : {
     600             :         _considerCleanup = flag;
     601             : }
     602             : 
     603             : @end