runtime/ObjC/Framework/HashMap.m

//
//  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