1//
2//  ANTLRHashMap.m
3//  ANTLR
4//
5// Copyright (c) 2010 Alan Condit
6// All rights reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions
10// are met:
11// 1. Redistributions of source code must retain the above copyright
12//    notice, this list of conditions and the following disclaimer.
13// 2. Redistributions in binary form must reproduce the above copyright
14//    notice, this list of conditions and the following disclaimer in the
15//    documentation and/or other materials provided with the distribution.
16// 3. The name of the author may not be used to endorse or promote products
17//    derived from this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30#define SUCCESS (0)
31#define FAILURE (-1)
32
33#import "ANTLRHashMap.h"
34
35static NSInteger itIndex;
36
37/*
38 * Start of ANTLRHashMap
39 */
40@implementation ANTLRHashMap
41
42@synthesize Scope;
43@synthesize LastHash;
44
45+(id)newANTLRHashMap
46{
47    ANTLRHashMap *aNewANTLRHashMap;
48    
49    aNewANTLRHashMap = [[ANTLRHashMap alloc] init];
50	return( aNewANTLRHashMap );
51}
52
53+(id)newANTLRHashMapWithLen:(NSInteger)aBuffSize
54{
55    ANTLRHashMap *aNewANTLRHashMap;
56    
57    aNewANTLRHashMap = [[ANTLRHashMap alloc] initWithLen:aBuffSize];
58	return( aNewANTLRHashMap );
59}
60
61-(id)init
62{
63    NSInteger idx;
64    
65	if ((self = [super init]) != nil) {
66		fNext = nil;
67        BuffSize = HASHSIZE;
68		Scope = 0;
69		if ( fNext != nil ) {
70			Scope = ((ANTLRHashMap *)fNext)->Scope+1;
71			for( idx = 0; idx < BuffSize; idx++ ) {
72				ptrBuffer[idx] = ((ANTLRHashMap *)fNext)->ptrBuffer[idx];
73			}
74		}
75        mode = 0;
76	}
77    return( self );
78}
79
80-(id)initWithLen:(NSInteger)aBuffSize
81{
82    NSInteger idx;
83    
84	if ((self = [super init]) != nil) {
85		fNext = nil;
86        BuffSize = aBuffSize;
87		Scope = 0;
88		if ( fNext != nil ) {
89			Scope = ((ANTLRHashMap *)fNext)->Scope+1;
90			for( idx = 0; idx < BuffSize; idx++ ) {
91				ptrBuffer[idx] = ((ANTLRHashMap *)fNext)->ptrBuffer[idx];
92			}
93		}
94        mode = 0;
95	}
96    return( self );
97}
98
99-(void)dealloc
100{
101    ANTLRMapElement *tmp, *rtmp;
102    NSInteger idx;
103	
104    if ( self.fNext != nil ) {
105        for( idx = 0; idx < BuffSize; idx++ ) {
106            tmp = ptrBuffer[idx];
107            while ( tmp && tmp != [((ANTLRHashMap *)fNext) getptrBufferEntry:idx] ) {
108                rtmp = tmp;
109                // tmp = [tmp getfNext];
110                tmp = (ANTLRMapElement *)tmp.fNext;
111                [rtmp dealloc];
112            }
113        }
114    }
115	[super dealloc];
116}
117
118- (NSInteger)count
119{
120    id anElement;
121    NSInteger aCnt = 0;
122    
123    for (NSInteger i = 0; i < BuffSize; i++) {
124        if ((anElement = ptrBuffer[i]) != nil) {
125            aCnt++;
126        }
127    }
128    return aCnt;
129}
130                          
131- (NSInteger) size
132{
133    id anElement;
134    NSInteger aSize = 0;
135    
136    for (NSInteger i = 0; i < BuffSize; i++) {
137        if ((anElement = ptrBuffer[i]) != nil) {
138            aSize += sizeof(id);
139        }
140    }
141    return aSize;
142}
143                                  
144                                  
145-(void)deleteANTLRHashMap:(ANTLRMapElement *)np
146{
147    ANTLRMapElement *tmp, *rtmp;
148    NSInteger idx;
149    
150    if ( self.fNext != nil ) {
151        for( idx = 0; idx < BuffSize; idx++ ) {
152            tmp = ptrBuffer[idx];
153            while ( tmp && tmp != (ANTLRLinkBase *)[((ANTLRHashMap *)fNext) getptrBufferEntry:idx] ) {
154                rtmp = tmp;
155                tmp = [tmp getfNext];
156                [rtmp dealloc];
157            }
158        }
159    }
160}
161
162-(ANTLRHashMap *)PushScope:(ANTLRHashMap **)map
163{
164    NSInteger idx;
165    ANTLRHashMap *htmp;
166    
167    htmp = [ANTLRHashMap newANTLRHashMap];
168    if ( *map != nil ) {
169        ((ANTLRHashMap *)htmp)->fNext = *map;
170        [htmp setScope:[((ANTLRHashMap *)htmp->fNext) getScope]+1];
171        for( idx = 0; idx < BuffSize; idx++ ) {
172            htmp->ptrBuffer[idx] = ((ANTLRHashMap *)htmp->fNext)->ptrBuffer[idx];
173        }
174    }
175    //    gScopeLevel++;
176    *map = htmp;
177    return( htmp );
178}
179
180-(ANTLRHashMap *)PopScope:(ANTLRHashMap **)map
181{
182    NSInteger idx;
183    ANTLRMapElement *tmp;
184	ANTLRHashMap *htmp;
185    
186    htmp = *map;
187    if ( (*map)->fNext != nil ) {
188        *map = (ANTLRHashMap *)htmp->fNext;
189        for( idx = 0; idx < BuffSize; idx++ ) {
190            if ( htmp->ptrBuffer[idx] == nil ||
191                htmp->ptrBuffer[idx] == (*map)->ptrBuffer[idx] ) {
192                break;
193            }
194            tmp = htmp->ptrBuffer[idx];
195            /*
196             * must deal with parms, locals and labels at some point
197             * can not forget the debuggers
198             */
199            htmp->ptrBuffer[idx] = [tmp getfNext];
200            [ tmp dealloc];
201        }
202        *map = (ANTLRHashMap *)htmp->fNext;
203        //        gScopeLevel--;
204    }
205    return( htmp );
206}
207
208#ifdef USERDOC
209/*
210 *  HASH        hash entry to get index to table
211 *  NSInteger hash( ANTLRHashMap *self, char *s );
212 *
213 *     Inputs:  char *s             string to find
214 *
215 *     Returns: NSInteger                 hashed value
216 *
217 *  Last Revision 9/03/90
218 */
219#endif
220-(NSInteger)hash:(NSString *)s       /*    form hash value for string s */
221{
222	NSInteger hashval;
223	const char *tmp;
224    
225	tmp = [s cStringUsingEncoding:NSASCIIStringEncoding];
226	for( hashval = 0; *tmp != '\0'; )
227        hashval += *tmp++;
228	self->LastHash = hashval % BuffSize;
229	return( self->LastHash );
230}
231
232#ifdef USERDOC
233/*
234 *  FINDSCOPE  search hashed list for entry
235 *  ANTLRHashMap *findscope( ANTLRHashMap *self, NSInteger scope );
236 *
237 *     Inputs:  NSInteger       scope -- scope level to find
238 *
239 *     Returns: ANTLRHashMap   pointer to ptrBuffer of proper scope level
240 *
241 *  Last Revision 9/03/90
242 */
243#endif
244-(ANTLRHashMap *)findscope:(NSInteger)scope
245{
246    if ( self->Scope == scope ) {
247        return( self );
248    }
249    else if ( fNext ) {
250        return( [((ANTLRHashMap *)fNext) findscope:scope] );
251    }
252    return( nil );              /*   not found      */
253}
254
255#ifdef USERDOC
256/*
257 *  LOOKUP  search hashed list for entry
258 *  ANTLRMapElement *lookup( ANTLRHashMap *self, char *s, NSInteger scope );
259 *
260 *     Inputs:  char     *s          string to find
261 *
262 *     Returns: ANTLRMapElement  *           pointer to entry
263 *
264 *  Last Revision 9/03/90
265 */
266#endif
267-(id)lookup:(NSString *)s Scope:(NSInteger)scope
268{
269    ANTLRMapElement *np;
270    
271    for( np = self->ptrBuffer[[self hash:s]]; np != nil; np = [np getfNext] ) {
272        if ( [s isEqualToString:[np getName]] ) {
273            return( np );        /*   found it       */
274        }
275    }
276    return( nil );              /*   not found      */
277}
278
279#ifdef USERDOC
280/*
281 *  INSTALL search hashed list for entry
282 *  NSInteger install( ANTLRHashMap *self, ANTLRMapElement *sym, NSInteger scope );
283 *
284 *     Inputs:  ANTLRMapElement    *sym   -- symbol ptr to install
285 *              NSInteger         scope -- level to find
286 *
287 *     Returns: Boolean     TRUE   if installed
288 *                          FALSE  if already in table
289 *
290 *  Last Revision 9/03/90
291 */
292#endif
293-(ANTLRMapElement *)install:(ANTLRMapElement *)sym Scope:(NSInteger)scope
294{
295    ANTLRMapElement *np;
296    
297    np = [self lookup:[sym getName] Scope:scope ];
298    if ( np == nil ) {
299        [sym retain];
300        [sym setFNext:self->ptrBuffer[ self->LastHash ]];
301        self->ptrBuffer[ self->LastHash ] = sym;
302        return( self->ptrBuffer[ self->LastHash ] );
303    }
304    return( nil );            /*   not found      */
305}
306
307#ifdef USERDOC
308/*
309 *  RemoveSym  search hashed list for entry
310 *  NSInteger RemoveSym( ANTLRHashMap *self, char *s );
311 *
312 *     Inputs:  char     *s          string to find
313 *
314 *     Returns: NSInteger      indicator of SUCCESS OR FAILURE
315 *
316 *  Last Revision 9/03/90
317 */
318#endif
319-(NSInteger)RemoveSym:(NSString *)s
320{
321    ANTLRMapElement *np, *tmp;
322    NSInteger idx;
323    
324    idx = [self hash:s];
325    for ( tmp = self->ptrBuffer[idx], np = self->ptrBuffer[idx]; np != nil; np = [np getfNext] ) {
326        if ( [s isEqualToString:[np getName]] ) {
327            tmp = [np getfNext];             /* get the next link  */
328            [np dealloc];
329            return( SUCCESS );            /* report SUCCESS     */
330        }
331        tmp = [np getfNext];              //  BAD!!!!!!
332    }
333    return( FAILURE );                    /*   not found      */
334}
335
336-(void)delete_chain:(ANTLRMapElement *)np
337{
338    if ( [np getfNext] != nil )
339		[self delete_chain:[np getfNext]];
340	[np dealloc];
341}
342
343#ifdef DONTUSEYET
344-(NSInteger)bld_symtab:(KW_TABLE *)toknams
345{
346    NSInteger i;
347    ANTLRMapElement *np;
348    
349    for( i = 0; *(toknams[i].name) != '\0'; i++ ) {
350        // install symbol in ptrBuffer
351        np = [ANTLRMapElement newANTLRMapElement:[NSString stringWithFormat:@"%s", toknams[i].name]];
352        //        np->fType = toknams[i].toknum;
353        [self install:np Scope:0];
354    }
355    return( SUCCESS );
356}
357#endif
358
359-(ANTLRMapElement *)getptrBufferEntry:(NSInteger)idx
360{
361	return( ptrBuffer[idx] );
362}
363
364-(ANTLRMapElement **)getptrBuffer
365{
366	return( ptrBuffer );
367}
368
369-(void)setptrBuffer:(ANTLRMapElement *)np Index:(NSInteger)idx
370{
371	if ( idx < BuffSize ) {
372        [np retain];
373		ptrBuffer[idx] = np;
374    }
375}
376
377-(NSInteger)getScope
378{
379	return( Scope );
380}
381
382-(void)setScopeScope:(NSInteger)i
383{
384	Scope = i;
385}
386
387- (ANTLRMapElement *)getTType:(NSString *)name
388{
389    return [self lookup:name Scope:0];
390}
391
392/*
393 * works only for maplist indexed not by name but by TokenNumber
394 */
395- (ANTLRMapElement *)getNameInList:(NSInteger)ttype
396{
397    ANTLRMapElement *np;
398    NSInteger aTType;
399
400    aTType = ttype % BuffSize;
401    for( np = self->ptrBuffer[ttype]; np != nil; np = [np getfNext] ) {
402        if ( [np.index integerValue] == ttype ) {
403            return( np );        /*   found it       */
404        }
405    }
406    return( nil );              /*   not found      */
407}
408
409- (ANTLRLinkBase *)getName:(NSString *)name
410{
411    return [self lookup:name Scope:0]; /*  nil if not found      */    
412}
413
414- (void)putNode:(NSString *)name TokenType:(NSInteger)ttype
415{
416    ANTLRMapElement *np;
417    
418    // install symbol in ptrBuffer
419    np = [ANTLRMapElement newANTLRMapElementWithName:[NSString stringWithString:name] Type:ttype];
420    //        np->fType = toknams[i].toknum;
421    [self install:np Scope:0];
422}
423
424- (NSInteger)getMode
425{
426    return mode;
427}
428
429- (void)setMode:(NSInteger)aMode
430{
431    mode = aMode;
432}
433
434- (void) addObject:(id)aRule
435{
436    NSInteger idx;
437
438    idx = [self count];
439    if ( idx >= BuffSize ) {
440        idx %= BuffSize;
441    }
442    ptrBuffer[idx] = aRule;
443}
444
445/* this may have to handle linking into the chain
446 */
447- (void) insertObject:(id)aRule atIndex:(NSInteger)idx
448{
449    if ( idx >= BuffSize ) {
450        idx %= BuffSize;
451    }
452    if (aRule != ptrBuffer[idx]) {
453        if (ptrBuffer[idx] != nil) [ptrBuffer[idx] release];
454        [aRule retain];
455    }
456    ptrBuffer[idx] = aRule;
457}
458
459- (id)objectAtIndex:(NSInteger)idx
460{
461    if ( idx >= BuffSize ) {
462        idx %= BuffSize;
463    }
464    return ptrBuffer[idx];
465}
466
467/* this will never link into the chain
468 */
469- (void) setObject:(id)aRule atIndex:(NSInteger)idx
470{
471    if ( idx >= BuffSize ) {
472        idx %= BuffSize;
473    }
474    if (aRule != ptrBuffer[idx]) {
475        if (ptrBuffer[idx] != nil) [ptrBuffer[idx] release];
476        [aRule retain];
477    }
478    ptrBuffer[idx] = aRule;
479}
480
481- (void)putName:(NSString *)name Node:(id)aNode
482{
483    ANTLRMapElement *np;
484    
485    np = [self lookup:name Scope:0 ];
486    if ( np == nil ) {
487        np = [ANTLRMapElement newANTLRMapElementWithName:name Node:aNode];
488        if (ptrBuffer[LastHash] != nil)
489            [ptrBuffer[LastHash] release];
490        [np retain];
491        np.fNext = ptrBuffer[ LastHash ];
492        ptrBuffer[ LastHash ] = np;
493    }
494    return;    
495}
496
497- (NSEnumerator *)objectEnumerator
498{
499    NSEnumerator *anEnumerator;
500
501    itIndex = 0;
502    return anEnumerator;
503}
504
505- (BOOL)hasNext
506{
507    if (self && [self count] < BuffSize-1) {
508        return YES;
509    }
510    return NO;
511}
512
513- (ANTLRMapElement *)nextObject
514{
515    if (self && itIndex < BuffSize-1) {
516        return ptrBuffer[itIndex];
517    }
518    return nil;
519}
520
521@end
522