err.no Git - sope/blob - sope-core/NGExtensions/NGHashMap.m

   1 /*
   2   Copyright (C) 2000-2005 SKYRIX Software AG
   3
   4   This file is part of SOPE.
   5
   6   SOPE is free software; you can redistribute it and/or modify it under
   7   the terms of the GNU Lesser General Public License as published by the
   8   Free Software Foundation; either version 2, or (at your option) any
   9   later version.
  10
  11   SOPE is distributed in the hope that it will be useful, but WITHOUT ANY
  12   WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14   License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public
  17   License along with SOPE; see the file COPYING.  If not, write to the
  18   Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19   02111-1307, USA.
  20 */
  21
  22 #include "NGHashMap.h"
  23 #include "common.h"
  24
  25 #if !LIB_FOUNDATION_LIBRARY
  26 @interface NSException(SetUI) /* allowed on Jaguar ? */
  27 - (void)setUserInfo:(NSDictionary *)_ui;
  28 @end
  29 #endif
  30
  31 typedef struct _LList {
  32   struct _LList *next;
  33   id            object;
  34   unsigned int  count;
  35 } LList;
  36
  37 static inline void *initLListElement(id _object, LList* _next) {
  38   LList *element  = malloc(sizeof(LList));
  39   _object = [_object retain];
  40   element->object = _object;
  41   element->next   = _next;
  42   element->count  = 0;
  43   return element;
  44 }
  45
  46 static inline void checkForAddErrorMessage(id _self, id _object, id _key) {
  47   NSException  *exc;
  48   NSDictionary *ui;
  49   NSString     *r;
  50
  51   if (_key == nil) {
  52     r = [NSString stringWithFormat:@"nil key to be added in HashMap with object %@",
  53            _object ? _object : @"<nil>"];
  54     ui = [NSDictionary dictionaryWithObjectsAndKeys:
  55                                      _self, @"map",
  56                                      _key ? _key : @"<nil>",
  57                                      @"key",
  58                                      _object ? _object : @"<nil>",
  59                                      @"object",
  60                                      nil];
  61     exc = [NSException exceptionWithName:NSInvalidArgumentException
  62                        reason:r userInfo:ui];
  63     [exc raise];
  64   }
  65   if (_object == nil) {
  66     r = [NSString stringWithFormat:
  67                     @"nil object to be added in HashMap for key %@",
  68                     _key ? _key : @"<nil>"];
  69     ui = [NSDictionary dictionaryWithObjectsAndKeys:
  70                                      _self, @"map",
  71                                      _key ? _key : @"<nil>",
  72                                      @"key",
  73                                      _object ? _object : @"<nil>",
  74                                      @"object",
  75                                      nil];
  76     exc = [NSException exceptionWithName:NSInvalidArgumentException
  77                        reason:r userInfo:ui];
  78     [exc raise];
  79   }
  80 }
  81
  82 static inline void checkForRemoveErrorMessage(id _self, id _object, id _key) {
  83   NSException  *exc;
  84   NSDictionary *ui;
  85   NSString     *r;
  86
  87   if (_object != nil && _key != nil)
  88     return;
  89
  90   r = [NSString stringWithFormat:
  91                   @"nil object to be removed in HashMap for key %@",
  92                   _key ? _key : @"<nil>"];
  93   ui = [NSDictionary dictionaryWithObjectsAndKeys:
  94                                      _self, @"map",
  95                                      _key ? _key : @"<nil>",
  96                                      @"key",
  97                                      _object ? _object : @"<nil>",
  98                                      @"object",
  99                                      nil];
 100   exc = [NSException exceptionWithName:NSInvalidArgumentException
 101                      reason:r userInfo:ui];
 102   [exc raise];
 103 }
 104
 105 static inline void raiseInvalidArgumentExceptionForNilKey(id _self) {
 106   NSException *exc = nil;
 107   exc = [NSException exceptionWithName:NSInvalidArgumentException
 108                      reason:@"key is nil"
 109                      userInfo:[NSDictionary dictionaryWithObject:_self forKey:@"map"]];
 110   [exc raise];
 111 }
 112
 113 @interface _NGHashMapObjectEnumerator : NSEnumerator
 114 {
 115   NSEnumerator *keys;
 116   NSEnumerator *elements;
 117   NGHashMap    *hashMap;
 118 }
 119 - (id)initWithHashMap:(NGHashMap *)_hashMap;
 120 - (id)nextObject;
 121 @end
 122
 123 @interface _NGHashMapObjectForKeyEnumerator : NSEnumerator
 124 {
 125   LList *element;
 126   NGHashMap    *map;
 127 }
 128 - (id)initWithHashMap:(NGHashMap *)_hashMap andKey:(id)_key;
 129 - (id)nextObject;
 130 @end
 131
 132 @interface _NGHashMapKeyEnumerator : NSEnumerator
 133 {
 134   NSMapEnumerator enumerator;
 135   NGHashMap *map;
 136 }
 137 - (id)initWithHashMap:(NGHashMap *)_hashMap;
 138 - (id)nextObject;
 139 @end
 140
 141 // ************************* NGHashMap *************************
 142
 143 @interface NGHashMap(private)
 144 - (LList *)__structForKey:(id)_key;
 145 - (NSMapEnumerator)__keyEnumerator;
 146 - (void)__removeAllObjectsForKey:(id)_key;
 147 - (void)__removeAllObjects;
 148 @end
 149
 150 static Class NSArrayClass = Nil;
 151
 152 @implementation NGHashMap
 153
 154 + (void)initialize {
 155   NSArrayClass = [NSArray class];
 156 }
 157
 158 /* final methods */
 159
 160 static inline void _removeAllObjectsInList(LList *list) {
 161   while (list) {
 162     register LList *element;
 163
 164     [list->object release];
 165     element = list;
 166     list    = list->next;
 167     if (element) free(element);
 168   }
 169 }
 170
 171 static inline LList *__structForKey(NGHashMap *self, id _key) {
 172   if (_key == nil) raiseInvalidArgumentExceptionForNilKey(self);
 173 #if DEBUG
 174   NSCAssert(self->table, @"missing table ..");
 175 #endif
 176   return (LList *)NSMapGet(self->table, (void *)_key);
 177 }
 178
 179 static inline unsigned __countObjectsForKey(NGHashMap *self, id _key) {
 180   LList *list = NULL;
 181   return (list = __structForKey(self, _key)) ? list->count : 0;
 182 }
 183
 184 /* methods */
 185
 186 + (id)hashMap {
 187   return [[[self alloc] init] autorelease];
 188 }
 189 + (id)hashMapWithHashMap:(NGHashMap *)_hashMap {
 190   return [[[self alloc] initWithHashMap:_hashMap] autorelease];
 191 }
 192 + (id)hashMapWithObjects:(NSArray *)_objects forKey:(id)_key {
 193   return [[[self alloc] initWithObjects:_objects forKey:_key] autorelease];
 194 }
 195 + (id)hashMapWithDictionary:(NSDictionary *)_dict {
 196   return [[[self alloc] initWithDictionary:_dict] autorelease];
 197 }
 198
 199 - (id)init {
 200   return [self initWithCapacity:0];
 201 }
 202
 203 - (id)initWithCapacity:(unsigned int)_size {
 204   if ((self = [super init])) {
 205     self->table = NSCreateMapTableWithZone(NSObjectMapKeyCallBacks,
 206                                            NSNonOwnedPointerMapValueCallBacks,
 207                                            _size * 4/3 ,NULL);
 208     NSAssert1(self->table, @"missing table for hashmap of size %d ..", _size);
 209   }
 210   return self;
 211 }
 212
 213 - (id)initWithHashMap:(NGHashMap *)_hashMap {
 214   NSEnumerator *keys    = nil;
 215   id            key     = nil;
 216   LList *list    = NULL;
 217   LList *newList = NULL;
 218   LList *oldList = NULL;
 219
 220   if ((self = [self initWithCapacity:[_hashMap count]])) {
 221     keys  = [_hashMap keyEnumerator];
 222     while ((key = [keys nextObject])) {
 223       list           = [_hashMap __structForKey:key];
 224       newList        = initLListElement(list->object,NULL);
 225       newList->count = list->count;
 226       NSMapInsert(self->table,key,newList);
 227       while (list->next) {
 228         oldList       = newList;
 229         list          = list->next;
 230         newList       = initLListElement(list->object,NULL);
 231         oldList->next = newList;
 232       }
 233     }
 234   }
 235   return self;
 236 }
 237
 238 - (id)initWithObjects:(NSArray *)_objects forKey:(id)_key {
 239   LList *root    = NULL;
 240   LList *element = NULL;
 241   LList *pred    = NULL;
 242   int           count   = 0;
 243   int           i       = 0;
 244
 245   if (( self = [self initWithCapacity:1])) {
 246     count = [_objects count];
 247     if (count == 0)
 248       return self;
 249
 250     root = initLListElement([_objects objectAtIndex:0], NULL);
 251     pred = root;
 252     for (i = 1; i < count; i++) {
 253       element    = initLListElement([_objects objectAtIndex:i], NULL);
 254       pred->next = element;
 255       pred       = element;
 256     }
 257     root->count = i;
 258     NSMapInsert(self->table,_key, root);
 259   }
 260   NSAssert(self->table, @"missing table for hashmap ..");
 261   return self;
 262 }
 263
 264 - (id)initWithDictionary:(NSDictionary *)_dictionary {
 265   if (![self isKindOfClass:[NGMutableHashMap class]]) {
 266     self = [self autorelease];
 267     self = [[NGMutableHashMap allocWithZone:[self zone]]
 268                               initWithCapacity:[_dictionary count]];
 269   }
 270   else
 271     self = [self initWithCapacity:[_dictionary count]];
 272
 273   if (self) {
 274     NSEnumerator *keys;
 275     id key;
 276
 277     keys = [_dictionary keyEnumerator];
 278     while ((key = [keys nextObject])) {
 279       [(NGMutableHashMap *)self
 280                            setObject:[_dictionary objectForKey:key]
 281                            forKey:key];
 282     }
 283   }
 284   NSAssert(self->table, @"missing table for hashmap ..");
 285   return self;
 286 }
 287
 288 - (void)dealloc {
 289   if (self->table) {
 290     NSMapEnumerator mapenum;
 291     id key = nil, value = nil;
 292
 293     mapenum = [self __keyEnumerator];
 294
 295     while (NSNextMapEnumeratorPair(&mapenum, (void **)&key, (void **)&value))
 296       _removeAllObjectsInList((LList *)value);
 297
 298     NSFreeMapTable(self->table);
 299     self->table = NULL;
 300   }
 301   [super dealloc];
 302 }
 303
 304 /* removing */
 305
 306 - (void)__removeAllObjectsForKey:(id)_key {
 307   _removeAllObjectsInList(__structForKey(self, _key));
 308   NSMapRemove(self->table, _key);
 309 }
 310
 311 - (void)__removeAllObjects {
 312   NSEnumerator *keys = nil;
 313   id           key  = nil;
 314
 315   keys = [self keyEnumerator];
 316   while ((key = [keys nextObject]))
 317     _removeAllObjectsInList(__structForKey(self, key));
 318
 319   NSResetMapTable(self->table);
 320 }
 321
 322 /* equality */
 323
 324 - (unsigned int)hash {
 325   return [self count];
 326 }
 327
 328 - (BOOL)isEqual:(id)anObject {
 329   if (self == anObject)
 330     return YES;
 331
 332   if (![anObject isKindOfClass:[NGHashMap class]])
 333     return NO;
 334
 335   return [self isEqualToHashMap:anObject];
 336 }
 337
 338 - (BOOL)isEqualToHashMap:(NGHashMap *)_other {
 339   NSEnumerator *keyEnumerator = nil;
 340   id            key           = nil;
 341   LList *selfList      = NULL;
 342   LList *otherList     = NULL;
 343
 344   if (_other == self)
 345     return YES;
 346
 347   if ([self count] != [_other count])
 348     return NO;
 349
 350   keyEnumerator = [self keyEnumerator];
 351   while ((key = [keyEnumerator nextObject])) {
 352     if (__countObjectsForKey(self, key) != [_other countObjectsForKey:key])
 353       return NO;
 354
 355     selfList  = __structForKey(self, key);
 356     otherList = [_other __structForKey:key];
 357     while (selfList) {
 358       if (![selfList->object isEqual:otherList->object])
 359         return NO;
 360
 361       selfList = selfList->next;
 362       otherList = otherList->next;
 363     }
 364   }
 365   return YES;
 366 }
 367
 368
 369 - (id)objectForKey:(id)_key {
 370   LList *list;
 371
 372   if (!(list = __structForKey(self, _key)))
 373     return nil;
 374
 375   if (list->next) {
 376     NSLog(@"WARNING[%s] more than one element for key %@ objects: %@, "
 377           @"return first object", __PRETTY_FUNCTION__, _key,
 378           [self objectsForKey:_key]);
 379   }
 380   return list->object;
 381 }
 382
 383 - (NSArray *)objectsForKey:(id)_key {
 384   NSArray         *array      = nil;
 385   NSEnumerator    *objectEnum = nil;
 386   id              object      = nil;
 387   id              *objects    = NULL;
 388   unsigned int    i           = 0;
 389
 390   if ((objectEnum = [self objectEnumeratorForKey:_key]) == nil)
 391     return nil;
 392
 393   objects = calloc(__countObjectsForKey(self, _key) + 1, sizeof(id));
 394   for (i = 0; (object = [objectEnum nextObject]); i++)
 395     objects[i] = object;
 396
 397   array = [NSArrayClass arrayWithObjects:objects count:i];
 398   if (objects) free(objects);
 399   return array;
 400 }
 401
 402 - (id)objectAtIndex:(unsigned int)_index forKey:(id)_key {
 403   LList *list = NULL;
 404
 405   if (!(list = __structForKey(self, _key)))
 406     return nil;
 407
 408   if ((_index < list->count) == 0) {
 409     [NSException raise:NSRangeException
 410                  format:@"index %d out of range for key %@ of length %d",
 411                    _index, _key, list->count];
 412     return nil;
 413   }
 414
 415   while (_index--)
 416     list = list->next;
 417
 418   return list->object;
 419 }
 420
 421 - (NSArray *)allKeys {
 422   NSArray      *array   = nil;
 423   NSEnumerator *keys;
 424   id           *objects;
 425   id           object;
 426   int          i;
 427
 428   objects = calloc([self count] + 1, sizeof(id));
 429   keys    = [self keyEnumerator];
 430   for(i = 0; (object = [keys nextObject]); i++)
 431     objects[i] = object;
 432
 433   array = [[NSArrayClass alloc] initWithObjects:objects count:i];
 434   if (objects) free (objects);
 435   return [array autorelease];
 436 }
 437
 438 - (NSArray *)allObjects {
 439   NSEnumerator   *keys   = nil;
 440   id             object  = nil;
 441   NSMutableArray *mArray = nil;
 442   NSArray        *result = nil;
 443
 444   mArray = [[NSMutableArray alloc] init];
 445   keys   = [self keyEnumerator];
 446   while ((object = [keys nextObject]))
 447     [mArray addObjectsFromArray:[self objectsForKey:object]];
 448
 449   result = [mArray copy];
 450   [mArray release]; mArray = nil;
 451   return [result autorelease];
 452 }
 453
 454 - (unsigned int)countObjectsForKey:(id)_key {
 455   return __countObjectsForKey(self, _key);
 456 }
 457
 458 - (NSEnumerator *)keyEnumerator {
 459   return [[[_NGHashMapKeyEnumerator alloc] initWithHashMap:self] autorelease];
 460 }
 461
 462 - (NSEnumerator *)objectEnumerator {
 463   return [[[_NGHashMapObjectEnumerator alloc]
 464             initWithHashMap:self] autorelease];
 465 }
 466
 467 - (NSEnumerator *)objectEnumeratorForKey:(id)_key {
 468   if (_key == nil)
 469     raiseInvalidArgumentExceptionForNilKey(self);
 470
 471   return [[[_NGHashMapObjectForKeyEnumerator alloc]
 472               initWithHashMap:self andKey:_key] autorelease];
 473 }
 474
 475 - (NSDictionary *)asDictionaryWithArraysForValues:(BOOL)arraysOnly {
 476   NSDictionary  *dict    = nil;
 477   NSEnumerator  *keys;
 478   id            key;
 479   id            *dicObj;
 480   id            *dicKeys;
 481   int           cntKey;
 482
 483   keys    = [self keyEnumerator];
 484   cntKey  = [self count];
 485   dicObj  = calloc(cntKey + 1, sizeof(id));
 486   dicKeys = calloc(cntKey + 1, sizeof(id));
 487
 488   for (cntKey = 0; (key = [keys nextObject]); ) {
 489     id     object   = nil;
 490     LList  *list;
 491
 492     if ((list = __structForKey(self, key)) == NULL) {
 493       NSLog(@"ERROR(%s): did not find key '%@' in hashmap: %@",
 494             __PRETTY_FUNCTION__, key, self);
 495       continue;
 496     }
 497
 498     if (list->next) {
 499       id   *objects = NULL;
 500       int  cntObj   = 0;
 501
 502       objects = calloc(list->count + 1, sizeof(id));
 503       {
 504         cntObj  = 0;
 505         while (list) {
 506           objects[cntObj++] = list->object;
 507           list = list->next;
 508         }
 509
 510                 object = [NSArray arrayWithObjects:objects count:cntObj];
 511       }
 512       if (objects) free(objects); objects = NULL;
 513     }
 514     else {
 515                 if (arraysOnly) {
 516           object = [NSArray arrayWithObject:list->object ];
 517                 } else {
 518                   object = list->object;
 519                 }
 520         }
 521
 522     dicObj[cntKey]    = object;
 523     dicKeys[cntKey++] = key;
 524   }
 525
 526   dict = [[NSDictionary alloc]
 527                         initWithObjects:dicObj forKeys:dicKeys count:cntKey];
 528
 529   if (dicObj)  free(dicObj);  dicObj  = NULL;
 530   if (dicKeys) free(dicKeys); dicKeys = NULL;
 531   return [dict autorelease];
 532 }
 533
 534 - (NSDictionary *)asDictionary {
 535         return [ self asDictionaryWithArraysForValues: NO ];
 536 }
 537
 538 - (NSDictionary *)asDictionaryWithArraysForValues {
 539         return [ self asDictionaryWithArraysForValues: YES ];
 540 }
 541
 542
 543 - (id)propertyList {
 544   NSDictionary  *dict    = nil;
 545   NSEnumerator  *keys    = nil;
 546   id            key;
 547   id            *dicObj  = NULL;
 548   id            *dicKeys = NULL;
 549   int           cntKey   = 0;
 550
 551   keys    = [self keyEnumerator];
 552   cntKey  = [self count];
 553   dicObj  = calloc(cntKey + 1, sizeof(id));
 554   dicKeys = calloc(cntKey + 1, sizeof(id));
 555
 556   for (cntKey = 0; (key = [keys nextObject]); ) {
 557     id            object   = nil;
 558     LList  *list    = NULL;
 559
 560     list = __structForKey(self, key);
 561     if (list->next) {
 562       id   *objects = NULL;
 563       int  cntObj   = 0;
 564
 565       objects = calloc(list->count + 1, sizeof(id));
 566       {
 567         cntObj  = 0;
 568         while (list) {
 569           objects[cntObj++] = list->object;
 570           list = list->next;
 571         }
 572         object = [NSArrayClass arrayWithObjects:objects count:cntObj];
 573       }
 574       if (objects) free(objects); objects = NULL;
 575     }
 576     else
 577       object = list->object;
 578
 579     dicObj[cntKey]  = object;
 580     dicKeys[cntKey] = key;
 581     cntKey++;
 582   }
 583   dict = [[[NSDictionary alloc] initWithObjects:dicObj forKeys:dicKeys
 584                                 count:cntKey] autorelease];
 585   if (dicObj)  free(dicObj);  dicObj  = NULL;
 586   if (dicKeys) free(dicKeys); dicKeys = NULL;
 587   return dict;
 588 }
 589
 590 /* description */
 591
 592 - (NSString *)description {
 593   return [[self propertyList] description];
 594 }
 595
 596 - (unsigned int)count {
 597   return self->table ? NSCountMapTable(table) : 0;
 598 }
 599
 600 /* NSCopying */
 601
 602 - (id)copyWithZone:(NSZone *)_zone {
 603   return [[NGHashMap allocWithZone:_zone] initWithHashMap:self];
 604 }
 605
 606 - (id)mutableCopyWithZone:(NSZone *)_zone {
 607   return [[NGMutableHashMap allocWithZone:_zone] initWithHashMap:self];
 608 }
 609
 610 /* */
 611
 612 - (NSMapEnumerator)__keyEnumerator {
 613   return NSEnumerateMapTable(table);
 614 }
 615
 616 - (LList *)__structForKey:(id)_key {
 617   return __structForKey(self, _key);
 618 }
 619
 620 /* NSCoding */
 621
 622 - (void)encodeWithCoder:(NSCoder *)_encoder {
 623   unsigned        keyCount = [self count];
 624   NSMapEnumerator mapenum  = [self __keyEnumerator];
 625   id              key      = nil;
 626   LList           *value   = NULL;
 627
 628   [_encoder encodeValueOfObjCType:@encode(unsigned) at:&keyCount];
 629
 630   while (NSNextMapEnumeratorPair(&mapenum, (void **)&key, (void **)&value)) {
 631     unsigned valueCount = value ? value->count : 0;
 632     unsigned outCount   = 0; // debugging
 633
 634     [_encoder encodeObject:key];
 635     [_encoder encodeValueOfObjCType:@encode(unsigned) at:&valueCount];
 636
 637     while (value) {
 638       [_encoder encodeObject:value->object];
 639       value = value->next;
 640       outCount++;
 641     }
 642
 643     NSAssert(valueCount == outCount, @"didn't encode enough value objects");
 644   }
 645 }
 646
 647 - (id)initWithCoder:(NSCoder *)_decoder {
 648   NGMutableHashMap *map = [[NGMutableHashMap alloc] init];
 649   unsigned keyCount;
 650   unsigned cnt;
 651
 652   [_decoder decodeValueOfObjCType:@encode(unsigned) at:&keyCount];
 653   for (cnt = 0; cnt < keyCount; cnt++) {
 654     unsigned valueCount = 0, cnt2 = 0;
 655     id       key        = nil;
 656
 657     key = [_decoder decodeObject];
 658     [_decoder decodeValueOfObjCType:@encode(unsigned) at:&valueCount];
 659
 660     for (cnt2 = 0; cnt2 < valueCount; cnt2++) {
 661       id value = [_decoder decodeObject];
 662       [map addObject:value forKey:key];
 663     }
 664   }
 665
 666   self = [self initWithHashMap:map];
 667   [map release]; map = nil;
 668
 669   return self;
 670 }
 671
 672 @end /* NGHashMap */
 673
 674 // ************************* NGMutableHashMap ******************
 675
 676 @implementation NGMutableHashMap
 677
 678 + (id)hashMapWithCapacity:(unsigned int)_numItems {
 679   return [[[self alloc] initWithCapacity:_numItems] autorelease];
 680 }
 681
 682 - (id)init {
 683   return [self initWithCapacity:0];
 684 }
 685
 686 /* inserting objects */
 687
 688 - (void)insertObject:(id)_object atIndex:(unsigned int)_index forKey:(id)_key {
 689   [self insertObjects:&_object count:1 atIndex:_index forKey:_key];
 690 }
 691
 692 - (void)insertObjects:(NSArray *)_objects atIndex:(unsigned int)_index
 693   forKey:(id)_key
 694 {
 695   id  *objects = NULL;
 696   int i        = 0;
 697   int cntI     = 0;
 698
 699   cntI    = [_objects count];
 700   objects = calloc(cntI + 1, sizeof(id));
 701   for (i = 0 ; i < cntI; i++)
 702     objects[i] = [_objects objectAtIndex:i];
 703
 704   [self insertObjects:objects count:cntI atIndex:_index forKey:_key];
 705   if (objects) free(objects);
 706 }
 707
 708 - (void)insertObjects:(id*)_objects count:(unsigned int)_count
 709   atIndex:(unsigned int)_index forKey:(id)_key
 710 {
 711   id            object  = nil;
 712   LList *root    = NULL;
 713   LList *element = NULL;
 714   unsigned i = 0;
 715
 716   if (_count == 0)
 717     return;
 718
 719   checkForAddErrorMessage(self, _objects[0],_key);
 720   if ((root = [self __structForKey:_key]) == NULL) {
 721     if (_index > 0) {
 722       [NSException raise:NSRangeException
 723                    format:@"index %d out of range in map 0x%08X",
 724                     _index, self];
 725       return;
 726     }
 727
 728     root        = initLListElement(_objects[0], NULL);
 729     root->count = _count;
 730     NSMapInsert(self->table, _key, root);
 731   }
 732   else {
 733     if (!(_index < root->count)) {
 734       [NSException raise:NSRangeException
 735                    format:@"index %d out of range in map 0x%08X length %d",
 736                     _index, self, root->count];
 737       return;
 738     }
 739
 740     root->count += _count;
 741     if (_index == 0) {
 742       element         = initLListElement(_objects[0],NULL);
 743       object          = element->object;
 744       element->next   = root->next;
 745       element->object = root->object;
 746       root->object    = object;
 747       root->next      = element;
 748     }
 749     else {
 750       while (--_index)
 751         root = root->next;
 752
 753       element       = initLListElement(_objects[0], NULL);
 754       element->next = root->next;
 755       root->next    = element;
 756       root          = root->next;
 757     }
 758   }
 759   for (i = 1; i < _count; i++) {
 760     checkForAddErrorMessage(self, _objects[i], _key);
 761     element       = initLListElement(_objects[i], NULL);
 762     element->next = root->next;
 763     root->next    = element;
 764     root          = element;
 765   }
 766 }
 767
 768 /* adding objects */
 769
 770 - (void)addObjects:(id*)_objects count:(unsigned int)_count forKey:(id)_key {
 771   LList *root     = NULL;
 772   LList *element  = NULL;
 773   unsigned i      = 0;
 774
 775   if (_count == 0)
 776     return;
 777
 778   checkForAddErrorMessage(self, _objects[0],_key);
 779   if ((root = [self __structForKey:_key]) == NULL) {
 780     root        = initLListElement(_objects[0], NULL);
 781     root->count = _count;
 782     NSMapInsert(self->table, _key, root);
 783   }
 784   else {
 785     root->count += _count;
 786     while (root->next)
 787       root = root->next;
 788
 789     element    = initLListElement(_objects[0], NULL);
 790     root->next = element;
 791     root       = root->next;
 792   }
 793   for (i = 1; i < _count; i++) {
 794     checkForAddErrorMessage(self, _objects[i], _key);
 795     element    = initLListElement(_objects[i], NULL);
 796     root->next = element;
 797     root       = element;
 798   }
 799 }
 800
 801 - (void)addObject:(id)_object forKey:(id)_key {
 802   checkForAddErrorMessage(self, _object,_key);
 803   [self addObjects:&_object count:1 forKey:_key];
 804 }
 805
 806 - (void)addObjects:(NSArray *)_objects forKey:(id)_key {
 807   id  *objects = NULL;
 808   int i        = 0;
 809   int cntI     = 0;
 810
 811   cntI    = [_objects count];
 812   objects = calloc(cntI + 1, sizeof(id));
 813   for (i = 0 ; i < cntI; i++)
 814     objects[i] = [_objects objectAtIndex:i];
 815
 816   [self addObjects:objects count:cntI forKey:_key];
 817   if (objects) free(objects);
 818 }
 819
 820 /* setting objects */
 821
 822 - (void)setObject:(id)_object forKey:(id)_key {
 823   checkForAddErrorMessage(self, _object, _key);
 824   [self removeAllObjectsForKey:_key];
 825   [self addObjects:&_object count:1 forKey:_key];
 826 }
 827
 828 - (void)setObjects:(NSArray *)_objects forKey:(id)_key {
 829   checkForAddErrorMessage(self, _objects, _key);
 830   [self removeAllObjectsForKey:_key];
 831   [self addObjects:_objects forKey:_key];
 832 }
 833
 834 /* removing objects */
 835
 836 - (void)removeAllObjects {
 837   [self __removeAllObjects];
 838 }
 839
 840 - (void)removeAllObjectsForKey:(id)_key {
 841   [self __removeAllObjectsForKey:_key];
 842 }
 843
 844 - (void)removeAllObjects:(id)_object forKey:(id)_key {
 845   LList  *list    = NULL;
 846   LList  *root    = NULL;
 847   LList  *oldList = NULL;
 848   unsigned int  cnt      = 0;
 849
 850   checkForRemoveErrorMessage(self, _object, _key);
 851   if (!(root = [self __structForKey:_key]))
 852     return;
 853
 854   while ([root->object isEqual:_object]) {
 855     [root->object release];
 856     if (root->next == NULL) {
 857       if (root) free(root);
 858       root = NULL;
 859       NSMapRemove(self->table,_key);
 860       break;
 861     }
 862     else {
 863       list         = root->next;
 864       root->next   = list->next;
 865       root->object = list->object;
 866       root->count--;
 867       if (list) free(list);
 868       list = NULL;
 869     }
 870   }
 871   if (root) {
 872     list = root;
 873     while (list->next) {
 874       oldList = list;
 875       list    = list->next;
 876       if ([list->object isEqual:_object]) {
 877         cnt++;
 878         oldList->next = list->next;
 879         if (list) free(list);
 880         list = oldList;
 881       }
 882     }
 883     root->count -= cnt;
 884   }
 885 }
 886
 887 - (void)removeAllObjectsForKeys:(NSArray *)_keyArray {
 888   register int index  = 0;
 889   for (index = [_keyArray count]; index > 0;)
 890     [self removeAllObjectsForKey:[_keyArray objectAtIndex:--index]];
 891 }
 892
 893 @end /* NGMutableHashMap */
 894
 895 // ************************* Enumerators ******************
 896
 897 @implementation _NGHashMapKeyEnumerator
 898
 899 - (id)initWithHashMap:(NGHashMap *)_hashMap {
 900   self->map        = [_hashMap retain];
 901   self->enumerator = [_hashMap __keyEnumerator];
 902   return self;
 903 }
 904 - (void)dealloc {
 905   [self->map release];
 906   [super dealloc];
 907 }
 908
 909 - (id)nextObject {
 910   id key, value;
 911   return NSNextMapEnumeratorPair(&self->enumerator,(void**)&key, (void**)&value) ?
 912          key : nil;
 913 }
 914
 915 @end /* _NGHashMapKeyEnumerator */
 916
 917 @implementation _NGHashMapObjectEnumerator
 918
 919 - (id)initWithHashMap:(NGHashMap *)_hashMap {
 920   self->keys     = [[_hashMap keyEnumerator] retain];
 921   self->hashMap  = [_hashMap retain];
 922   self->elements = nil;
 923   return self;
 924 }
 925
 926 - (void)dealloc {
 927   [self->keys     release];
 928   [self->hashMap  release];
 929   [self->elements release];
 930   [super dealloc];
 931 }
 932
 933 - (id)nextObject {
 934   id object;
 935   id key;
 936
 937   if ((object = [self->elements nextObject]))
 938     return object;
 939
 940   if ((key = [self->keys nextObject])) {
 941     ASSIGN(self->elements, [self->hashMap objectEnumeratorForKey:key]);
 942     object = [self->elements nextObject];
 943   }
 944   return object;
 945 }
 946
 947 @end /* _NGHashMapObjectEnumerator */
 948
 949 @implementation _NGHashMapObjectForKeyEnumerator
 950
 951 - (id)initWithHashMap:(NGHashMap *)_hashMap andKey:(id)_key {
 952   element = [_hashMap __structForKey:_key];
 953   self->map = [_hashMap retain];
 954   return self;
 955 }
 956 - (void)dealloc {
 957   [self->map release];
 958   [super dealloc];
 959 }
 960
 961 - (id)nextObject {
 962   id object;
 963
 964   if (element == NULL)
 965     return nil;
 966
 967   object  = element->object;
 968   element = element->next;
 969   return object;
 970 }
 971
 972 @end /* _NGHashMapObjectForKeyEnumerator */