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