| // |
| // HashMap.m |
| // ANTLR |
| // |
| // Copyright (c) 2010 Alan Condit |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions |
| // are met: |
| // 1. Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // 2. Redistributions in binary form must reproduce the above copyright |
| // notice, this list of conditions and the following disclaimer in the |
| // documentation and/or other materials provided with the distribution. |
| // 3. The name of the author may not be used to endorse or promote products |
| // derived from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #define SUCCESS (0) |
| #define FAILURE (-1) |
| |
| #import "HashMap.h" |
| #import "AMutableArray.h" |
| #import "RuntimeException.h" |
| |
| extern NSInteger max(NSInteger a, NSInteger b); |
| |
| static NSInteger itIndex; |
| |
| @implementation HMEntry |
| |
| @synthesize next; |
| @synthesize hash; |
| @synthesize key; |
| @synthesize value; |
| |
| /** |
| * Creates new entry. |
| */ |
| + (HMEntry *)newEntry:(NSInteger)h key:(NSString *)k value:(id)v next:(HMEntry *) n |
| { |
| return [[HMEntry alloc] init:h key:k value:v next:n]; |
| } |
| |
| - (id) init:(NSInteger)h key:(NSString *)k value:(id)v next:(HMEntry *)n |
| { |
| self = [super init]; |
| if ( self ) { |
| value = v; |
| next = n; |
| key = k; |
| hash = h; |
| } |
| return self; |
| } |
| |
| - (void) setValue:(id)newValue |
| { |
| value = newValue; |
| // return oldValue; |
| } |
| |
| - (BOOL) isEqualTo:(id)o |
| { |
| /* |
| if (!([o conformsToProtocol:@protocol(HMEntry)])) |
| return NO; |
| */ |
| HMEntry *e = (HMEntry *)o; |
| NSString *k1 = [self key]; |
| NSString *k2 = [e key]; |
| if (k1 == k2 || (k1 != nil && [k1 isEqualTo:k2])) { |
| id v1 = [self value]; |
| id v2 = [e value]; |
| if (v1 == v2 || (v1 != nil && [v1 isEqualTo:v2])) |
| return YES; |
| } |
| return NO; |
| } |
| |
| - (NSInteger) hashCode |
| { |
| return (key == nil ? 0 : [key hash]) ^ (value == nil ? 0 : [value hash]); |
| } |
| |
| - (NSString *) description |
| { |
| return [NSString stringWithFormat:@"%@ = %@",[key description], [value description]]; |
| } |
| |
| |
| /** |
| * This method is invoked whenever the value in an entry is |
| * overwritten by an invocation of put(k,v) for a key k that's already |
| * in the HashMap. |
| */ |
| - (void) recordAccess:(HashMap *)m |
| { |
| } |
| |
| |
| /** |
| * This method is invoked whenever the entry is |
| * removed from the table. |
| */ |
| - (void) recordRemoval:(HashMap *)m |
| { |
| } |
| |
| - (void) dealloc |
| { |
| [key release]; |
| [value release]; |
| [next release]; |
| [super dealloc]; |
| } |
| |
| @end |
| |
| @implementation HashIterator |
| |
| + (HashIterator *)newIterator:(HashMap *)aHM |
| { |
| return [[HashIterator alloc] init:aHM]; |
| } |
| |
| - (id) init:(HashMap *)aHM |
| { |
| self = [super init]; |
| if ( self ) { |
| hm = aHM; |
| expectedModCount = hm.modCount; |
| if (count > 0) { |
| while ( idx < [hm.buffer length] ) { |
| next = (HMEntry *)hm.ptrBuffer[idx++]; |
| if ( next == nil ) |
| break; |
| } |
| } |
| } |
| return self; |
| } |
| |
| - (BOOL) hasNext |
| { |
| return next != nil; |
| } |
| |
| - (HMEntry *) next |
| { |
| // if (hm.modCount != expectedModCount) |
| // @throw [[ConcurrentModificationException alloc] init]; |
| HMEntry *e = next; |
| if (e == nil) |
| @throw [[NoSuchElementException alloc] init]; |
| if ((next = e.next) == nil) { |
| while ( idx < [hm.buffer length] ) { |
| next = [anArray objectAtIndex:idx++]; |
| if ( next == nil ) |
| break; |
| } |
| } |
| current = e; |
| return e; |
| } |
| |
| - (void) remove |
| { |
| if (current == nil) |
| @throw [[IllegalStateException alloc] init]; |
| // if (modCount != expectedModCount) |
| // @throw [[ConcurrentModificationException alloc] init]; |
| NSString *k = current.key; |
| current = nil; |
| [hm removeEntryForKey:k]; |
| expectedModCount = hm.modCount; |
| } |
| |
| - (void) dealloc |
| { |
| [next release]; |
| [current release]; |
| [super dealloc]; |
| } |
| |
| @end |
| |
| @implementation HMValueIterator |
| |
| + (HMValueIterator *)newIterator:(HashMap *)aHM |
| { |
| return [[HMValueIterator alloc] init:aHM]; |
| } |
| |
| - (id) init:(HashMap *)aHM |
| { |
| self = [super init:aHM]; |
| if ( self ) { |
| } |
| return self; |
| } |
| |
| - (id) next |
| { |
| return [super next].value; |
| } |
| |
| @end |
| |
| @implementation HMKeyIterator |
| |
| + (HMKeyIterator *)newIterator:(HashMap *)aHM |
| { |
| return [[HMKeyIterator alloc] init:aHM]; |
| } |
| |
| - (id) init:(HashMap *)aHM |
| { |
| self = [super init:aHM]; |
| if ( self ) { |
| } |
| return self; |
| } |
| |
| - (NSString *) next |
| { |
| return [super next].key; |
| } |
| |
| @end |
| |
| @implementation HMEntryIterator |
| |
| + (HMEntryIterator *)newIterator:(HashMap *)aHM |
| { |
| return [[HMEntryIterator alloc] init:aHM]; |
| } |
| |
| - (id) init:(HashMap *)aHM |
| { |
| self = [super init:aHM]; |
| if ( self ) { |
| } |
| return self; |
| } |
| |
| - (HMEntry *) next |
| { |
| return [super next]; |
| } |
| |
| @end |
| |
| @implementation HMKeySet |
| |
| @synthesize hm; |
| @synthesize anArray; |
| |
| + (HMKeySet *)newKeySet:(HashMap *)aHM |
| { |
| return [[HMKeySet alloc] init:(HashMap *)aHM]; |
| } |
| |
| - (id) init:(HashMap *)aHM |
| { |
| self = [super init]; |
| if ( self ) { |
| hm = aHM; |
| anArray = [[AMutableArray arrayWithCapacity:16] retain]; |
| HMKeyIterator *it = [hm newKeyIterator]; |
| while ( [it hasNext] ) { |
| NSString *aKey = [it next]; |
| [anArray addObject:aKey]; |
| } |
| } |
| return self; |
| } |
| |
| - (HashIterator *) iterator |
| { |
| return [HMKeyIterator newIterator:hm]; |
| } |
| |
| - (NSUInteger) count |
| { |
| return hm.count; |
| } |
| |
| - (BOOL) contains:(id)o |
| { |
| return [hm containsKey:o]; |
| } |
| |
| - (BOOL) remove:(id)o |
| { |
| return [hm removeEntryForKey:o] != nil; |
| } |
| |
| - (void) clear { |
| [hm clear]; |
| } |
| |
| - (AMutableArray *)toArray |
| { |
| return anArray; |
| } |
| |
| @end |
| |
| @implementation Values |
| |
| @synthesize hm; |
| @synthesize anArray; |
| |
| + (Values *)newValueSet:(HashMap *)aHM |
| { |
| return [[Values alloc] init:aHM]; |
| } |
| |
| - (id) init:(HashMap *)aHM |
| { |
| self = [super init]; |
| if ( self ) { |
| hm = aHM; |
| anArray = [[AMutableArray arrayWithCapacity:16] retain]; |
| HMValueIterator *it = [hm newValueIterator]; |
| while ( [it hasNext] ) { |
| id aValue = [it next]; |
| [anArray addObject:aValue]; |
| } |
| } |
| return self; |
| } |
| |
| - (ArrayIterator *) iterator |
| { |
| return [HMValueIterator newIterator:hm]; |
| } |
| |
| - (NSUInteger) count |
| { |
| return hm.count; |
| } |
| |
| - (BOOL) contains:(id)o |
| { |
| return [hm containsValue:o]; |
| } |
| |
| - (void) clear { |
| [hm clear]; |
| } |
| |
| - (AMutableArray *)toArray |
| { |
| return anArray; |
| } |
| |
| @end |
| |
| @implementation HMEntrySet |
| |
| @synthesize hm; |
| @synthesize anArray; |
| |
| + (HMEntrySet *)newEntrySet:(HashMap *)aHM |
| { |
| return [[HMEntrySet alloc] init:aHM]; |
| } |
| |
| - (id) init:(HashMap *)aHM |
| { |
| self = [super init]; |
| if ( self ) { |
| hm = aHM; |
| anArray = [[AMutableArray arrayWithCapacity:16] retain]; |
| HMEntryIterator *it = [hm newEntryIterator]; |
| while ( [it hasNext] ) { |
| HMEntry *entry = [it next]; |
| [anArray addObject:entry]; |
| } |
| } |
| return self; |
| } |
| |
| - (HashIterator *) iterator |
| { |
| return [HMEntryIterator newIterator:hm]; |
| } |
| |
| - (BOOL) contains:(id)o |
| { |
| /* |
| if (!([o conformsToProtocol:@protocol(HMEntry)])) |
| return NO; |
| */ |
| HMEntry *e = (HMEntry *)o; |
| HMEntry *candidate = [hm getEntry:e.key]; |
| return candidate != nil && [candidate isEqualTo:e]; |
| } |
| |
| - (BOOL) remove:(id)o |
| { |
| return [hm removeMapping:o] != nil; |
| } |
| |
| - (NSUInteger) count |
| { |
| return hm.count; |
| } |
| |
| - (void) clear |
| { |
| [hm clear]; |
| } |
| |
| - (NSArray *)toArray |
| { |
| return anArray; |
| } |
| |
| @end |
| |
| /** |
| * The default initial capacity - MUST be a power of two. |
| */ |
| NSInteger const DEFAULT_INITIAL_CAPACITY = 16; |
| |
| /** |
| * The maximum capacity, used if a higher value is implicitly specified |
| * by either of the constructors with arguments. |
| * MUST be a power of two <= 1<<30. |
| */ |
| NSInteger const MAXIMUM_CAPACITY = 1 << 30; |
| |
| /** |
| * The load factor used when none specified in constructor. |
| */ |
| float const DEFAULT_LOAD_FACTOR = 0.75f; |
| //long const serialVersionUID = 362498820763181265L; |
| |
| /* |
| * Start of HashMap |
| */ |
| @implementation HashMap |
| |
| @synthesize Scope; |
| @synthesize LastHash; |
| @synthesize BuffSize; |
| @synthesize Capacity; |
| @synthesize count; |
| @synthesize ptr; |
| @synthesize ptrBuffer; |
| @synthesize buffer; |
| @synthesize threshold; |
| @synthesize loadFactor; |
| @synthesize modCount; |
| @synthesize entrySet; |
| @synthesize empty; |
| @synthesize keySet; |
| @synthesize values; |
| |
| +(id)newHashMap |
| { |
| return [[HashMap alloc] init]; |
| } |
| |
| +(id)newHashMapWithLen:(NSInteger)aBuffSize |
| { |
| return [[HashMap alloc] initWithLen:aBuffSize]; |
| } |
| |
| + (id) newHashMap:(NSInteger)initialCapacity |
| { |
| return [[HashMap alloc] init:initialCapacity loadFactor:DEFAULT_LOAD_FACTOR]; |
| } |
| |
| + (id) newHashMap:(NSInteger)initialCapacity loadFactor:(float)aLoadFactor |
| { |
| return [[HashMap alloc] init:initialCapacity loadFactor:aLoadFactor]; |
| } |
| |
| /** |
| * Constructs an empty <tt>HashMap</tt> with the default initial capacity |
| * (16) and the default load factor (0.75). |
| */ |
| - (id) init |
| { |
| NSInteger idx; |
| |
| self = [super init]; |
| if ( self ) { |
| entrySet = nil; |
| loadFactor = DEFAULT_LOAD_FACTOR; |
| threshold = (NSInteger)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); |
| count = 0; |
| BuffSize = HASHSIZE; |
| NSInteger capacity = 1; |
| |
| while (capacity < BuffSize) |
| capacity <<= 1; |
| |
| BuffSize = capacity; |
| fNext = nil; |
| Scope = 0; |
| ptr = 0; |
| buffer = [[NSMutableData dataWithLength:(NSUInteger)BuffSize * sizeof(id)] retain]; |
| ptrBuffer = (MapElement **) [buffer mutableBytes]; |
| if ( fNext != nil ) { |
| Scope = ((HashMap *)fNext)->Scope+1; |
| for( idx = 0; idx < BuffSize; idx++ ) { |
| ptrBuffer[idx] = ((HashMap *)fNext)->ptrBuffer[idx]; |
| } |
| } |
| mode = 0; |
| keySet = nil; |
| values = nil; |
| } |
| return self; |
| } |
| |
| -(id)initWithLen:(NSInteger)aBuffSize |
| { |
| NSInteger idx; |
| |
| self = [super init]; |
| if ( self ) { |
| fNext = nil; |
| entrySet = nil; |
| loadFactor = DEFAULT_LOAD_FACTOR; |
| threshold = (NSInteger)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); |
| count = 0; |
| BuffSize = aBuffSize; |
| NSInteger capacity = 1; |
| |
| while (capacity < BuffSize) |
| capacity <<= 1; |
| |
| BuffSize = capacity * sizeof(id); |
| Capacity = capacity; |
| Scope = 0; |
| ptr = 0; |
| buffer = [[NSMutableData dataWithLength:(NSUInteger)BuffSize] retain]; |
| ptrBuffer = (MapElement **) [buffer mutableBytes]; |
| if ( fNext != nil ) { |
| Scope = ((HashMap *)fNext)->Scope+1; |
| for( idx = 0; idx < Capacity; idx++ ) { |
| ptrBuffer[idx] = ((HashMap *)fNext)->ptrBuffer[idx]; |
| } |
| } |
| mode = 0; |
| keySet = nil; |
| values = nil; |
| } |
| return( self ); |
| } |
| |
| /** |
| * Constructs an empty <tt>HashMap</tt> with the specified initial |
| * capacity and load factor. |
| * |
| * @param initialCapacity the initial capacity |
| * @param loadFactor the load factor |
| * @throws IllegalArgumentException if the initial capacity is negative |
| * or the load factor is nonpositive |
| */ |
| - (id) init:(NSInteger)initialCapacity loadFactor:(float)aLoadFactor |
| { |
| self = [super init]; |
| if ( self ) { |
| entrySet = nil; |
| if (initialCapacity < 0) |
| @throw [[IllegalArgumentException alloc] init:[NSString stringWithFormat:@"Illegal initial capacity: %d", initialCapacity]]; |
| if (initialCapacity > MAXIMUM_CAPACITY) |
| initialCapacity = MAXIMUM_CAPACITY; |
| if (aLoadFactor <= 0 /* || [Float isNaN:loadFactor] */) |
| @throw [[IllegalArgumentException alloc] init:[NSString stringWithFormat:@"Illegal load factor:%d ", aLoadFactor]]; |
| NSInteger capacity = 1; |
| |
| while (capacity < initialCapacity) |
| capacity <<= 1; |
| |
| count = 0; |
| BuffSize = capacity * sizeof(id); |
| Capacity = capacity; |
| loadFactor = aLoadFactor; |
| threshold = (NSInteger)(capacity * loadFactor); |
| // ptrBuffer = [AMutableArray arrayWithCapacity:initialCapacity]; |
| // [self init]; |
| keySet = nil; |
| values = nil; |
| Scope = 0; |
| ptr = 0; |
| buffer = [[NSMutableData dataWithLength:(NSUInteger)BuffSize] retain]; |
| ptrBuffer = (MapElement **) [buffer mutableBytes]; |
| } |
| return self; |
| } |
| |
| |
| /** |
| * Constructs an empty <tt>HashMap</tt> with the specified initial |
| * capacity and the default load factor (0.75). |
| * |
| * @param initialCapacity the initial capacity. |
| * @throws IllegalArgumentException if the initial capacity is negative. |
| */ |
| - (id) init:(NSInteger)anInitialCapacity |
| { |
| self = [super init]; |
| if ( self ) { |
| entrySet = nil; |
| NSInteger initialCapacity = anInitialCapacity; |
| if (initialCapacity > MAXIMUM_CAPACITY) |
| initialCapacity = MAXIMUM_CAPACITY; |
| NSInteger capacity = 1; |
| while (capacity < initialCapacity) |
| capacity <<= 1; |
| count = 0; |
| BuffSize = capacity; |
| loadFactor = DEFAULT_LOAD_FACTOR; |
| threshold = (NSInteger)(capacity * loadFactor); |
| keySet = nil; |
| values = nil; |
| Scope = 0; |
| ptr = 0; |
| buffer = [[NSMutableData dataWithLength:(NSUInteger)BuffSize] retain]; |
| ptrBuffer = (MapElement **) [buffer mutableBytes]; |
| } |
| return self; |
| } |
| |
| /** |
| * Constructs a new <tt>HashMap</tt> with the same mappings as the |
| * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with |
| * default load factor (0.75) and an initial capacity sufficient to |
| * hold the mappings in the specified <tt>Map</tt>. |
| * |
| * @param m the map whose mappings are to be placed in this map |
| * @throws NullPointerException if the specified map is null |
| */ |
| - (id) initWithM:(HashMap *)m |
| { |
| self = [super init]; |
| self = [self init:(NSInteger)max((([m count] / DEFAULT_LOAD_FACTOR) + 1), DEFAULT_INITIAL_CAPACITY) loadFactor:DEFAULT_LOAD_FACTOR]; |
| if ( self ) { |
| entrySet = nil; |
| NSInteger initialCapacity = max((([m count] / DEFAULT_LOAD_FACTOR) + 1), DEFAULT_INITIAL_CAPACITY); |
| if (initialCapacity > MAXIMUM_CAPACITY) |
| initialCapacity = MAXIMUM_CAPACITY; |
| NSInteger capacity = 1; |
| while (capacity < initialCapacity) |
| capacity <<= 1; |
| count = 0; |
| BuffSize = capacity * sizeof(id); |
| Capacity = capacity; |
| loadFactor = DEFAULT_LOAD_FACTOR; |
| threshold = (NSInteger)(capacity * loadFactor); |
| keySet = nil; |
| values = nil; |
| Scope = 0; |
| ptr = 0; |
| buffer = [[NSMutableData dataWithLength:(NSUInteger)BuffSize] retain]; |
| ptrBuffer = (MapElement **) [buffer mutableBytes]; |
| [self putAllForCreate:m]; |
| } |
| return self; |
| } |
| |
| -(void)dealloc |
| { |
| #ifdef DEBUG_DEALLOC |
| NSLog( @"called dealloc in HashMap" ); |
| #endif |
| MapElement *tmp, *rtmp; |
| NSInteger idx; |
| |
| if ( self.fNext != nil ) { |
| for( idx = 0; idx < Capacity; idx++ ) { |
| tmp = ptrBuffer[idx]; |
| while ( tmp && tmp != [((HashMap *)fNext) getptrBufferEntry:idx] ) { |
| rtmp = tmp; |
| // tmp = [tmp getfNext]; |
| tmp = (MapElement *)tmp.fNext; |
| [rtmp release]; |
| } |
| } |
| } |
| if ( buffer ) [buffer release]; |
| #ifdef DONTUSEYET |
| [ptrBuffer release]; |
| [entrySet release]; |
| #endif |
| if ( keySet ) [keySet release]; |
| if ( values ) [values release]; |
| [super dealloc]; |
| } |
| |
| - (NSUInteger)count |
| { |
| /* |
| NSUInteger aCnt = 0; |
| |
| for (NSUInteger i = 0; i < Capacity; i++) { |
| if ( ptrBuffer[i] != nil ) { |
| aCnt++; |
| } |
| } |
| return aCnt; |
| */ |
| return count; |
| } |
| |
| - (NSInteger) size |
| { |
| NSInteger aSize = 0; |
| |
| for (NSInteger i = 0; i < Capacity; i++) { |
| if ( ptrBuffer[i] != nil ) { |
| aSize += sizeof(id); |
| } |
| } |
| return aSize; |
| } |
| |
| |
| -(void)deleteHashMap:(MapElement *)np |
| { |
| MapElement *tmp, *rtmp; |
| NSInteger idx; |
| |
| if ( self.fNext != nil ) { |
| for( idx = 0; idx < Capacity; idx++ ) { |
| tmp = ptrBuffer[idx]; |
| while ( tmp && tmp != (LinkBase *)[((HashMap *)fNext) getptrBufferEntry:idx] ) { |
| rtmp = tmp; |
| tmp = [tmp getfNext]; |
| [rtmp release]; |
| } |
| } |
| } |
| } |
| |
| -(HashMap *)PushScope:(HashMap **)map |
| { |
| NSInteger idx; |
| HashMap *htmp; |
| |
| htmp = [HashMap newHashMap]; |
| if ( *map != nil ) { |
| ((HashMap *)htmp)->fNext = *map; |
| [htmp setScope:[((HashMap *)htmp->fNext) getScope]+1]; |
| for( idx = 0; idx < Capacity; idx++ ) { |
| htmp->ptrBuffer[idx] = ((HashMap *)htmp->fNext)->ptrBuffer[idx]; |
| } |
| } |
| // gScopeLevel++; |
| *map = htmp; |
| return( htmp ); |
| } |
| |
| -(HashMap *)PopScope:(HashMap **)map |
| { |
| NSInteger idx; |
| MapElement *tmp; |
| HashMap *htmp; |
| |
| htmp = *map; |
| if ( (*map)->fNext != nil ) { |
| *map = (HashMap *)htmp->fNext; |
| for( idx = 0; idx < Capacity; idx++ ) { |
| if ( htmp->ptrBuffer[idx] == nil || |
| htmp->ptrBuffer[idx] == (*map)->ptrBuffer[idx] ) { |
| break; |
| } |
| tmp = htmp->ptrBuffer[idx]; |
| /* |
| * must deal with parms, locals and labels at some point |
| * can not forget the debuggers |
| */ |
| htmp->ptrBuffer[idx] = [tmp getfNext]; |
| [tmp release]; |
| } |
| *map = (HashMap *)htmp->fNext; |
| // gScopeLevel--; |
| } |
| return( htmp ); |
| } |
| |
| #ifdef USERDOC |
| /* |
| * HASH hash entry to get idx to table |
| * NSInteger hash( HashMap *self, char *s ); |
| * |
| * Inputs: char *s string to find |
| * |
| * Returns: NSInteger hashed value |
| * |
| * Last Revision 9/03/90 |
| */ |
| #endif |
| -(NSInteger)hash:(NSString *)s /* form hash value for string s */ |
| { |
| NSInteger hashval; |
| const char *tmp; |
| |
| tmp = [s cStringUsingEncoding:NSASCIIStringEncoding]; |
| for( hashval = 0; *tmp != '\0'; ) |
| hashval += *tmp++; |
| self->LastHash = hashval % Capacity; |
| return( self->LastHash ); |
| } |
| |
| /** |
| * Applies a supplemental hash function to a given hashCode, which |
| * defends against poor quality hash functions. This is critical |
| * because HashMap uses power-of-two length hash tables, that |
| * otherwise encounter collisions for hashCodes that do not differ |
| * in lower bits. Note: Null keys always map to hash 0, thus idx 0. |
| */ |
| - (NSInteger) hashInt:(NSInteger) h |
| { |
| // This function ensures that hashCodes that differ only by |
| // constant multiples at each bit position have a bounded |
| // number of collisions (approximately 8 at default load factor). |
| h ^= (h >> 20) ^ (h >> 12); |
| return h ^ (h >> 7) ^ (h >> 4); |
| } |
| |
| /** |
| * Returns idx for hash code h. |
| */ |
| - (NSInteger) indexFor:(NSInteger)h length:(NSInteger)length |
| { |
| return h & (length - 1); |
| } |
| |
| #ifdef USERDOC |
| /* |
| * FINDSCOPE search hashed list for entry |
| * HashMap *findscope( HashMap *self, NSInteger scope ); |
| * |
| * Inputs: NSInteger scope -- scope level to find |
| * |
| * Returns: HashMap pointer to ptrBuffer of proper scope level |
| * |
| * Last Revision 9/03/90 |
| */ |
| #endif |
| -(HashMap *)findscope:(NSInteger)scope |
| { |
| if ( self->Scope == scope ) { |
| return( self ); |
| } |
| else if ( fNext ) { |
| return( [((HashMap *)fNext) findscope:scope] ); |
| } |
| return( nil ); /* not found */ |
| } |
| |
| #ifdef USERDOC |
| /* |
| * LOOKUP search hashed list for entry |
| * MapElement *lookup( HashMap *self, char *s, NSInteger scope ); |
| * |
| * Inputs: char *s string to find |
| * |
| * Returns: MapElement * pointer to entry |
| * |
| * Last Revision 9/03/90 |
| */ |
| #endif |
| -(id)lookup:(NSString *)s Scope:(NSInteger)scope |
| { |
| MapElement *np; |
| |
| for( np = self->ptrBuffer[[self hash:s]]; np != nil; np = [np getfNext] ) { |
| if ( [s isEqualToString:[np getName]] ) { |
| return( np ); /* found it */ |
| } |
| } |
| return( nil ); /* not found */ |
| } |
| |
| #ifdef USERDOC |
| /* |
| * INSTALL search hashed list for entry |
| * NSInteger install( HashMap *self, MapElement *sym, NSInteger scope ); |
| * |
| * Inputs: MapElement *sym -- symbol ptr to install |
| * NSInteger scope -- level to find |
| * |
| * Returns: Boolean TRUE if installed |
| * FALSE if already in table |
| * |
| * Last Revision 9/03/90 |
| */ |
| #endif |
| -(MapElement *)install:(MapElement *)sym Scope:(NSInteger)scope |
| { |
| MapElement *np; |
| |
| np = [self lookup:[sym getName] Scope:scope ]; |
| if ( np == nil ) { |
| [sym retain]; |
| [sym setFNext:self->ptrBuffer[ self->LastHash ]]; |
| self->ptrBuffer[ self->LastHash ] = sym; |
| return( self->ptrBuffer[ self->LastHash ] ); |
| } |
| return( nil ); /* not found */ |
| } |
| |
| #ifdef USERDOC |
| /* |
| * RemoveSym search hashed list for entry |
| * NSInteger RemoveSym( HashMap *self, char *s ); |
| * |
| * Inputs: char *s string to find |
| * |
| * Returns: NSInteger indicator of SUCCESS OR FAILURE |
| * |
| * Last Revision 9/03/90 |
| */ |
| #endif |
| -(NSInteger)RemoveSym:(NSString *)s |
| { |
| MapElement *np, *tmp; |
| NSInteger idx; |
| |
| idx = [self hash:s]; |
| for ( tmp = self->ptrBuffer[idx], np = self->ptrBuffer[idx]; np != nil; np = [np getfNext] ) { |
| if ( [s isEqualToString:[np getName]] ) { |
| tmp = [np getfNext]; /* get the next link */ |
| [np release]; |
| return( SUCCESS ); /* report SUCCESS */ |
| } |
| tmp = [np getfNext]; // BAD!!!!!! |
| } |
| return( FAILURE ); /* not found */ |
| } |
| |
| -(void)delete_chain:(MapElement *)np |
| { |
| if ( [np getfNext] != nil ) |
| [self delete_chain:[np getfNext]]; |
| [np dealloc]; |
| } |
| |
| #ifdef DONTUSEYET |
| -(NSInteger)bld_symtab:(KW_TABLE *)toknams |
| { |
| NSInteger i; |
| MapElement *np; |
| |
| for( i = 0; *(toknams[i].name) != '\0'; i++ ) { |
| // install symbol in ptrBuffer |
| np = [MapElement newMapElement:[NSString stringWithFormat:@"%s", toknams[i].name]]; |
| // np->fType = toknams[i].toknum; |
| [self install:np Scope:0]; |
| } |
| return( SUCCESS ); |
| } |
| #endif |
| |
| -(MapElement *)getptrBufferEntry:(NSInteger)idx |
| { |
| return( ptrBuffer[idx] ); |
| } |
| |
| -(MapElement **)getptrBuffer |
| { |
| return( ptrBuffer ); |
| } |
| |
| -(void)setptrBuffer:(MapElement *)np Index:(NSInteger)idx |
| { |
| if ( idx < Capacity ) { |
| [np retain]; |
| ptrBuffer[idx] = np; |
| } |
| } |
| |
| -(NSInteger)getScope |
| { |
| return( Scope ); |
| } |
| |
| -(void)setScopeScope:(NSInteger)i |
| { |
| Scope = i; |
| } |
| |
| - (MapElement *)getTType:(NSString *)name |
| { |
| return [self lookup:name Scope:0]; |
| } |
| |
| /* |
| * works only for maplist indexed not by name but by TokenNumber |
| */ |
| - (MapElement *)getNameInList:(NSInteger)ttype |
| { |
| MapElement *np; |
| NSInteger aTType; |
| |
| aTType = ttype % Capacity; |
| for( np = self->ptrBuffer[aTType]; np != nil; np = [np getfNext] ) { |
| if ( [(ACNumber *)np.node integerValue] == ttype ) { |
| return( np ); /* found it */ |
| } |
| } |
| return( nil ); /* not found */ |
| } |
| |
| - (LinkBase *)getName:(NSString *)name |
| { |
| return [self lookup:name Scope:0]; /* nil if not found */ |
| } |
| |
| - (void)putNode:(NSString *)name TokenType:(NSInteger)ttype |
| { |
| MapElement *np; |
| |
| // install symbol in ptrBuffer |
| np = [MapElement newMapElementWithName:[NSString stringWithString:name] Type:ttype]; |
| // np->fType = toknams[i].toknum; |
| [self install:np Scope:0]; |
| } |
| |
| - (NSInteger)getMode |
| { |
| return mode; |
| } |
| |
| - (void)setMode:(NSInteger)aMode |
| { |
| mode = aMode; |
| } |
| |
| - (void) addObject:(id)aRule |
| { |
| NSInteger idx; |
| |
| idx = [self count]; |
| if ( idx >= Capacity ) { |
| idx %= Capacity; |
| } |
| ptrBuffer[idx] = aRule; |
| } |
| |
| /* this may have to handle linking into the chain |
| */ |
| - (void) insertObject:(id)aRule atIndex:(NSInteger)idx |
| { |
| if ( idx >= Capacity ) { |
| idx %= Capacity; |
| } |
| if ( aRule != ptrBuffer[idx] ) { |
| if ( ptrBuffer[idx] ) [ptrBuffer[idx] release]; |
| [aRule retain]; |
| } |
| ptrBuffer[idx] = aRule; |
| } |
| |
| - (id)objectAtIndex:(NSInteger)idx |
| { |
| if ( idx >= Capacity ) { |
| idx %= Capacity; |
| } |
| return ptrBuffer[idx]; |
| } |
| |
| /** |
| * Returns <tt>true</tt> if this map contains no key-value mappings. |
| * |
| * @return <tt>true</tt> if this map contains no key-value mappings |
| */ |
| - (BOOL) empty |
| { |
| return count == 0; |
| } |
| |
| /** |
| * Offloaded version of get() to look up null keys. Null keys map |
| * to idx 0. This null case is split out into separate methods |
| * for the sake of performance in the two most commonly used |
| * operations (get and put), but incorporated with conditionals in |
| * others. |
| */ |
| - (id) getForNullKey |
| { |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[0]; e != nil; e = e.next) { |
| if (e.key == nil) |
| return e.value; |
| } |
| |
| return nil; |
| } |
| |
| /** |
| * Returns the value to which the specified key is mapped, |
| * or {@code null} if this map contains no mapping for the key. |
| * |
| * <p>More formally, if this map contains a mapping from a key |
| * {@code k} to a value {@code v} such that {@code (key==null ? k==null : |
| * key.equals(k))}, then this method returns {@code v}; otherwise |
| * it returns {@code null}. (There can be at most one such mapping.) |
| * |
| * <p>A return value of {@code null} does not <i>necessarily</i> |
| * indicate that the map contains no mapping for the key; it's also |
| * possible that the map explicitly maps the key to {@code null}. |
| * The {@link #containsKey containsKey} operation may be used to |
| * distinguish these two cases. |
| * |
| * @see #put(Object, Object) |
| */ |
| - (id) get:(NSString *)key |
| { |
| if (key == nil) |
| return [self getForNullKey]; |
| // NSInteger hash = [self hashInt:[self hash:key]]; |
| NSInteger hash = [self hashInt:[key hash]]; |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[[self indexFor:hash length:[self capacity]]]; e != nil; e = e.next) { |
| NSString *k; |
| if (e.hash == hash && ((k = e.key) == key || [key isEqualTo:k])) |
| return e.value; |
| } |
| |
| return nil; |
| } |
| |
| |
| /** |
| * Returns <tt>true</tt> if this map contains a mapping for the |
| * specified key. |
| * |
| * @param key The key whose presence in this map is to be tested |
| * @return <tt>true</tt> if this map contains a mapping for the specified |
| * key. |
| */ |
| - (BOOL) containsKey:(NSString *)key |
| { |
| return [self getEntry:key] != nil; |
| } |
| |
| /** |
| * Returns the entry associated with the specified key in the |
| * HashMap. Returns null if the HashMap contains no mapping |
| * for the key. |
| */ |
| - (HMEntry *) getEntry:(NSString *)key |
| { |
| // NSInteger hash = (key == nil) ? 0 : [self hashInt:[self hash:key]]; |
| NSInteger hash = (key == nil) ? 0 : [self hashInt:[key hash]]; |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[[self indexFor:hash length:Capacity]]; e != nil; e = e.next) { |
| NSString *k; |
| if (e.hash == hash && ((k = e.key) == key || (key != nil && [key isEqualTo:k]))) |
| return e; |
| } |
| |
| return nil; |
| } |
| |
| |
| /** |
| * Associates the specified value with the specified key in this map. |
| * If the map previously contained a mapping for the key, the old |
| * value is replaced. |
| * |
| * @param key key with which the specified value is to be associated |
| * @param value value to be associated with the specified key |
| * @return the previous value associated with <tt>key</tt>, or |
| * <tt>null</tt> if there was no mapping for <tt>key</tt>. |
| * (A <tt>null</tt> return can also indicate that the map |
| * previously associated <tt>null</tt> with <tt>key</tt>.) |
| */ |
| - (id) put:(NSString *)key value:(id)value |
| { |
| if (key == nil) |
| return [self putForNullKey:value]; |
| // NSInteger hash = [self hashInt:[self hash:key]]; |
| NSInteger hash = [self hashInt:[key hash]]; |
| NSInteger i = [self indexFor:hash length:[self capacity]]; |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[i]; e != nil; e = e.next) { |
| NSString *k; |
| if (e.hash == hash && ((k = e.key) == key || [key isEqualTo:k])) { |
| id oldValue = e.value; |
| e.value = value; |
| [e recordAccess:self]; |
| return oldValue; |
| } |
| } |
| |
| modCount++; |
| [self addEntry:hash key:key value:value bucketIndex:i]; |
| return nil; |
| } |
| |
| |
| /** |
| * Offloaded version of put for null keys |
| */ |
| - (id) putForNullKey:(id)value |
| { |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[0]; e != nil; e = e.next) { |
| if (e.key == nil) { |
| id oldValue = e.value; |
| e.value = value; |
| [e recordAccess:self]; |
| return oldValue; |
| } |
| } |
| |
| modCount++; |
| [self addEntry:0 key:nil value:value bucketIndex:0]; |
| return nil; |
| } |
| |
| /** |
| * This method is used instead of put by constructors and |
| * pseudoconstructors (clone, readObject). It does not resize the table, |
| * check for comodification, etc. It calls createEntry rather than |
| * addEntry. |
| */ |
| - (void) putForCreate:(NSString *)key value:(id)value |
| { |
| NSInteger hash = (key == nil) ? 0 : [self hashInt:[self hash:key]]; |
| NSInteger i = [self indexFor:hash length:[self capacity]]; |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[i]; e != nil; e = e.next) { |
| NSString *k; |
| if (e.hash == hash && ((k = e.key) == key || (key != nil && [key isEqualTo:k]))) { |
| e.value = value; |
| return; |
| } |
| } |
| |
| [self createEntry:hash key:key value:value bucketIndex:i]; |
| } |
| |
| - (void) putAllForCreate:(HashMap *)m |
| { |
| |
| for (HMEntry *e in [m entrySet]) |
| [self putForCreate:[e key] value:[e value]]; |
| |
| } |
| |
| /** |
| * Rehashes the contents of this map into a new array with a |
| * larger capacity. This method is called automatically when the |
| * number of keys in this map reaches its threshold. |
| * |
| * If current capacity is MAXIMUM_CAPACITY, this method does not |
| * resize the map, but sets threshold to Integer.MAX_VALUE. |
| * This has the effect of preventing future calls. |
| * |
| * @param newCapacity the new capacity, MUST be a power of two; |
| * must be greater than current capacity unless current |
| * capacity is MAXIMUM_CAPACITY (in which case value |
| * is irrelevant). |
| */ |
| - (void) resize:(NSInteger)newCapacity |
| { |
| // NSArray * oldTable = ptrBuffer; |
| NSInteger oldCapacity = Capacity; |
| if (oldCapacity == MAXIMUM_CAPACITY) { |
| threshold = NSIntegerMax; |
| return; |
| } |
| // NSArray * newTable = [NSArray array]; |
| // [self transfer:newTable]; |
| BuffSize = newCapacity * sizeof(id); |
| Capacity = newCapacity; |
| [buffer setLength:BuffSize]; |
| ptrBuffer = [buffer mutableBytes]; |
| threshold = (NSInteger)(newCapacity * loadFactor); |
| } |
| |
| |
| /** |
| * Transfers all entries from current table to newTable. |
| */ |
| - (void) transfer:(AMutableArray *)newTable |
| { |
| NSInteger newCapacity = [newTable count]; |
| |
| for (NSInteger j = 0; j < [self capacity]; j++) { |
| HMEntry *e = (HMEntry *)ptrBuffer[j]; |
| if (e != nil) { |
| ptrBuffer[j] = nil; |
| |
| do { |
| HMEntry *next = e.next; |
| NSInteger i = [self indexFor:e.hash length:newCapacity]; |
| e.next = [newTable objectAtIndex:i]; |
| [newTable replaceObjectAtIndex:i withObject:e]; |
| e = next; |
| } |
| while (e != nil); |
| } |
| } |
| |
| } |
| |
| |
| /** |
| * Copies all of the mappings from the specified map to this map. |
| * These mappings will replace any mappings that this map had for |
| * any of the keys currently in the specified map. |
| * |
| * @param m mappings to be stored in this map |
| * @throws NullPointerException if the specified map is null |
| */ |
| - (void) putAll:(HashMap *)m |
| { |
| NSInteger numKeysToBeAdded = [m count]; |
| if (numKeysToBeAdded == 0) |
| return; |
| if (numKeysToBeAdded > threshold) { |
| NSInteger targetCapacity = (NSInteger)(numKeysToBeAdded / loadFactor + 1); |
| if (targetCapacity > MAXIMUM_CAPACITY) |
| targetCapacity = MAXIMUM_CAPACITY; |
| NSInteger newCapacity = Capacity; |
| |
| while (newCapacity < targetCapacity) |
| newCapacity <<= 1; |
| |
| if (newCapacity > Capacity) |
| [self resize:newCapacity]; |
| } |
| |
| for (HMEntry *e in [m entrySet]) |
| [self put:[e key] value:[e value]]; |
| |
| } |
| |
| /** |
| * Removes the mapping for the specified key from this map if present. |
| * |
| * @param key key whose mapping is to be removed from the map |
| * @return the previous value associated with <tt>key</tt>, or |
| * <tt>null</tt> if there was no mapping for <tt>key</tt>. |
| * (A <tt>null</tt> return can also indicate that the map |
| * previously associated <tt>null</tt> with <tt>key</tt>.) |
| */ |
| - (id) remove:(NSString *)key |
| { |
| HMEntry *e = [self removeEntryForKey:key]; |
| return (e == nil ? nil : e.value); |
| } |
| |
| |
| /** |
| * Removes and returns the entry associated with the specified key |
| * in the HashMap. Returns null if the HashMap contains no mapping |
| * for this key. |
| */ |
| - (HMEntry *) removeEntryForKey:(NSString *)key |
| { |
| NSInteger hash = (key == nil) ? 0 : [self hashInt:[self hash:key]]; |
| NSInteger i = [self indexFor:hash length:Capacity]; |
| HMEntry *prev = (HMEntry *)ptrBuffer[i]; |
| HMEntry *e = prev; |
| |
| while (e != nil) { |
| HMEntry *next = e.next; |
| NSString *k; |
| if (e.hash == hash && ((k = e.key) == key || (key != nil && [key isEqualTo:k]))) { |
| modCount++; |
| count--; |
| if (prev == e) |
| ptrBuffer[i] = (id) next; |
| else |
| prev.next = next; |
| [e recordRemoval:self]; |
| return e; |
| } |
| prev = e; |
| e = next; |
| } |
| |
| return e; |
| } |
| |
| /** |
| * Special version of remove for EntrySet. |
| */ |
| - (HMEntry *) removeMapping:(id)o |
| { |
| // if (!([o conformsToProtocol:@protocol(HMEntry)])) |
| // return nil; |
| HMEntry *entry = (HMEntry *)o; |
| NSString *key = entry.key; |
| NSInteger hash = (key == nil) ? 0 : [self hashInt:[self hash:key]]; |
| NSInteger i = [self indexFor:hash length:Capacity]; |
| HMEntry *prev = (HMEntry *)ptrBuffer[i]; |
| HMEntry *e = prev; |
| |
| while (e != nil) { |
| HMEntry *next = e.next; |
| if (e.hash == hash && [e isEqualTo:entry]) { |
| modCount++; |
| count--; |
| if (prev == e) |
| ptrBuffer[i] = (id)next; |
| else |
| prev.next = next; |
| [e recordRemoval:self]; |
| return e; |
| } |
| prev = e; |
| e = next; |
| } |
| |
| return e; |
| } |
| |
| /** |
| * Removes all of the mappings from this map. |
| * The map will be empty after this call returns. |
| */ |
| - (void) clear |
| { |
| modCount++; |
| id tmp; |
| |
| for (NSInteger i = 0; i < Capacity; i++) { |
| tmp = ptrBuffer[i]; |
| if ( tmp ) { |
| [tmp release]; |
| } |
| ptrBuffer[i] = nil; |
| } |
| count = 0; |
| } |
| |
| |
| /** |
| * Special-case code for containsValue with null argument |
| */ |
| - (BOOL) containsNullValue |
| { |
| for (NSInteger i = 0; i < Capacity; i++) |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[i]; e != nil; e = e.next) |
| if (e.value == nil) |
| return YES; |
| return NO; |
| } |
| |
| /** |
| * Returns <tt>true</tt> if this map maps one or more keys to the |
| * specified value. |
| * |
| * @param value value whose presence in this map is to be tested |
| * @return <tt>true</tt> if this map maps one or more keys to the |
| * specified value |
| */ |
| - (BOOL) containsValue:(id)value |
| { |
| if (value == nil) |
| return [self containsNullValue]; |
| |
| for (NSInteger i = 0; i < Capacity; i++) |
| |
| for (HMEntry *e = (HMEntry *)ptrBuffer[i]; e != nil; e = e.next) |
| if ([value isEqualTo:e.value]) |
| return YES; |
| |
| |
| return NO; |
| } |
| |
| /** |
| * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and |
| * values themselves are not cloned. |
| * |
| * @return a shallow copy of this map |
| */ |
| - (id) copyWithZone:(NSZone *)zone |
| { |
| HashMap *result = nil; |
| |
| // @try { |
| result = [HashMap allocWithZone:zone]; |
| // result = (HashMap *)[super copyWithZone:zone]; |
| // } |
| // @catch (CloneNotSupportedException * e) { |
| // } |
| result.ptrBuffer = ptrBuffer; |
| result.entrySet = nil; |
| // result.modCount = 0; |
| // result.count = 0; |
| // [result init]; |
| [result putAllForCreate:self]; |
| result.count = count; |
| result.threshold = threshold; |
| result.loadFactor = loadFactor; |
| result.modCount = modCount; |
| result.entrySet = entrySet; |
| return result; |
| } |
| |
| |
| /** |
| * Returns a string representation of this map. The string representation |
| * consists of a list of key-value mappings in the order returned by the |
| * map's <tt>entrySet</tt> view's iterator, enclosed in braces |
| * (<tt>"{}"</tt>). Adjacent mappings are separated by the characters |
| * <tt>", "</tt> (comma and space). Each key-value mapping is rendered as |
| * the key followed by an equals sign (<tt>"="</tt>) followed by the |
| * associated value. Keys and values are converted to strings as by |
| * {@link String#valueOf(Object)}. |
| * |
| * @return a string representation of this map |
| */ |
| - (NSString *)description |
| { |
| HashIterator *it = [[self entrySet] iterator]; |
| if (![it hasNext]) |
| return @"{}"; |
| |
| NSMutableString *sb = [NSMutableString stringWithCapacity:40]; |
| [sb appendString:@"{"]; |
| while ( YES ) { |
| HMEntry *e = [it next]; |
| NSString *key = e.key; |
| id value = e.value; |
| [sb appendFormat:@"%@=%@", (key == self ? @"[self Map]" : key), (value == self ? @"[self Map]" : value)]; |
| if ( ![it hasNext] ) { |
| [sb appendString:@"}"]; |
| return sb; |
| } |
| [sb appendString:@", "]; |
| } |
| } |
| |
| /** |
| * Adds a new entry with the specified key, value and hash code to |
| * the specified bucket. It is the responsibility of this |
| * method to resize the table if appropriate. |
| * |
| * Subclass overrides this to alter the behavior of put method. |
| */ |
| - (void) addEntry:(NSInteger)hash key:(NSString *)key value:(id)value bucketIndex:(NSInteger)bucketIndex |
| { |
| HMEntry *e = (HMEntry *)ptrBuffer[bucketIndex]; |
| ptrBuffer[bucketIndex] = [[HMEntry alloc] init:hash key:key value:value next:e]; |
| if (count++ >= threshold) |
| [self resize:2 * BuffSize]; |
| } |
| |
| /** |
| * Like addEntry except that this version is used when creating entries |
| * as part of Map construction or "pseudo-construction" (cloning, |
| * deserialization). This version needn't worry about resizing the table. |
| * |
| * Subclass overrides this to alter the behavior of HashMap(Map), |
| * clone, and readObject. |
| */ |
| - (void) createEntry:(NSInteger)hash key:(NSString *)key value:(id)value bucketIndex:(NSInteger)bucketIndex |
| { |
| HMEntry *e = (HMEntry *)ptrBuffer[bucketIndex]; |
| ptrBuffer[bucketIndex] = [[HMEntry alloc] init:hash key:key value:value next:e]; |
| count++; |
| } |
| |
| - (HMKeyIterator *) newKeyIterator |
| { |
| return [HMKeyIterator newIterator:self]; |
| } |
| |
| - (HMValueIterator *) newValueIterator |
| { |
| return [HMValueIterator newIterator:self]; |
| } |
| |
| - (HMEntryIterator *) newEntryIterator |
| { |
| return [HMEntryIterator newIterator:self]; |
| } |
| |
| |
| /** |
| * Returns a {@link Set} view of the keys contained in this map. |
| * The set is backed by the map, so changes to the map are |
| * reflected in the set, and vice-versa. If the map is modified |
| * while an iteration over the set is in progress (except through |
| * the iterator's own <tt>remove</tt> operation), the results of |
| * the iteration are undefined. The set supports element removal, |
| * which removes the corresponding mapping from the map, via the |
| * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, |
| * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> |
| * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> |
| * operations. |
| */ |
| - (HMKeySet *) keySet |
| { |
| HMKeySet *ks = keySet; |
| return (ks != nil ? ks : (keySet = [HMKeySet newKeySet:self])); |
| } |
| |
| |
| /** |
| * Returns a {@link Collection} view of the values contained in this map. |
| * The collection is backed by the map, so changes to the map are |
| * reflected in the collection, and vice-versa. If the map is |
| * modified while an iteration over the collection is in progress |
| * (except through the iterator's own <tt>remove</tt> operation), |
| * the results of the iteration are undefined. The collection |
| * supports element removal, which removes the corresponding |
| * mapping from the map, via the <tt>Iterator.remove</tt>, |
| * <tt>Collection.remove</tt>, <tt>removeAll</tt>, |
| * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not |
| * support the <tt>add</tt> or <tt>addAll</tt> operations. |
| */ |
| - (Values *) values |
| { |
| Values *vs = values; |
| return (vs != nil ? vs : (values = [Values newValueSet:self])); |
| } |
| |
| |
| /** |
| * Returns a {@link Set} view of the mappings contained in this map. |
| * The set is backed by the map, so changes to the map are |
| * reflected in the set, and vice-versa. If the map is modified |
| * while an iteration over the set is in progress (except through |
| * the iterator's own <tt>remove</tt> operation, or through the |
| * <tt>setValue</tt> operation on a map entry returned by the |
| * iterator) the results of the iteration are undefined. The set |
| * supports element removal, which removes the corresponding |
| * mapping from the map, via the <tt>Iterator.remove</tt>, |
| * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and |
| * <tt>clear</tt> operations. It does not support the |
| * <tt>add</tt> or <tt>addAll</tt> operations. |
| * |
| * @return a set view of the mappings contained in this map |
| */ |
| - (HMEntrySet *) entrySet0 |
| { |
| HMEntrySet *es = entrySet; |
| return es != nil ? es : (entrySet = [HMEntrySet newEntrySet:self]); |
| } |
| |
| - (HMEntrySet *) entrySet |
| { |
| return [self entrySet0]; |
| } |
| |
| |
| /** |
| * Save the state of the <tt>HashMap</tt> instance to a stream (i.e., |
| * serialize it). |
| * |
| * @serialData The <i>capacity</i> of the HashMap (the length of the |
| * bucket array) is emitted (NSInteger), followed by the |
| * <i>count</i> (an NSInteger, the number of key-value |
| * mappings), followed by the key (Object) and value (Object) |
| * for each key-value mapping. The key-value mappings are |
| * emitted in no particular order. |
| */ |
| - (void) writeObject:(NSOutputStream *)s |
| { |
| /* |
| NSEnumerator * i = (count > 0) ? [[self entrySet0] iterator] : nil; |
| [s defaultWriteObject]; |
| [s writeInt:[buffer length]]; |
| [s writeInt:count]; |
| if (i != nil) { |
| while ([i hasNext]) { |
| HMEntry *e = [i nextObject]; |
| [s writeObject:[e key]]; |
| [s writeObject:[e value]]; |
| } |
| |
| } |
| */ |
| } |
| |
| |
| /** |
| * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e., |
| * deserialize it). |
| */ |
| - (void) readObject:(NSInputStream *)s |
| { |
| /* |
| [s defaultReadObject]; |
| NSInteger numBuckets = [s readInt]; |
| ptrBuffer = [NSArray array]; |
| [self init]; |
| NSInteger count = [s readInt]; |
| |
| for (NSInteger i = 0; i < count; i++) { |
| NSString * key = (NSString *)[s readObject]; |
| id value = (id)[s readObject]; |
| [self putForCreate:key value:value]; |
| } |
| */ |
| } |
| |
| - (NSInteger) capacity |
| { |
| return Capacity; |
| } |
| |
| - (float) loadFactor |
| { |
| return loadFactor; |
| } |
| |
| /* this will never link into the chain |
| */ |
| - (void) setObject:(id)aRule atIndex:(NSInteger)idx |
| { |
| if ( idx >= Capacity ) { |
| idx %= Capacity; |
| } |
| if ( aRule != ptrBuffer[idx] ) { |
| if ( ptrBuffer[idx] ) [ptrBuffer[idx] release]; |
| [aRule retain]; |
| } |
| ptrBuffer[idx] = aRule; |
| } |
| |
| - (void)putName:(NSString *)name Node:(id)aNode |
| { |
| MapElement *np; |
| |
| np = [self lookup:name Scope:0 ]; |
| if ( np == nil ) { |
| np = [MapElement newMapElementWithName:name Node:aNode]; |
| if ( ptrBuffer[LastHash] ) |
| [ptrBuffer[LastHash] release]; |
| [np retain]; |
| np.fNext = ptrBuffer[ LastHash ]; |
| ptrBuffer[ LastHash ] = np; |
| } |
| return; |
| } |
| |
| - (NSEnumerator *)objectEnumerator |
| { |
| #pragma mark fix this its broken |
| NSEnumerator *anEnumerator; |
| |
| itIndex = 0; |
| return anEnumerator; |
| } |
| |
| - (BOOL)hasNext |
| { |
| if (self && [self count] < Capacity-1) { |
| return YES; |
| } |
| return NO; |
| } |
| |
| - (MapElement *)nextObject |
| { |
| if (self && itIndex < Capacity-1) { |
| return ptrBuffer[itIndex]; |
| } |
| return nil; |
| } |
| |
| @end |
| |