2 Copyright (C) 2000-2005 SKYRIX Software AG
4 This file is part of SOPE.
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
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.
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
22 #include "NGHashMap.h"
25 #if !LIB_FOUNDATION_LIBRARY
26 @interface NSException(SetUI) /* allowed on Jaguar ? */
27 - (void)setUserInfo:(NSDictionary *)_ui;
31 typedef struct _LList {
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;
46 static inline void checkForAddErrorMessage(id _self, id _object, id _key) {
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:
57 _key ? _key : (id)@"<nil>", @"key",
58 _object ? _object : (id)@"<nil>", @"object",
60 exc = [NSException exceptionWithName:NSInvalidArgumentException
61 reason:r userInfo:ui];
63 [ui release]; ui = 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:
72 _key ? _key : (id)@"<nil>", @"key",
73 _object ? _object : (id)@"<nil>", @"object",
75 exc = [NSException exceptionWithName:NSInvalidArgumentException
76 reason:r userInfo:ui];
78 [ui release]; ui = nil;
83 static inline void checkForRemoveErrorMessage(id _self, id _object, id _key) {
88 if (_object != nil && _key != nil)
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:
96 _key ? _key : (id)@"<nil>", @"key",
97 _object ? _object : (id)@"<nil>", @"object",
99 exc = [NSException exceptionWithName:NSInvalidArgumentException
100 reason:r userInfo:ui];
101 [ui release]; ui = nil;
102 [r release]; r = nil;
106 static inline void raiseInvalidArgumentExceptionForNilKey(id _self) {
107 NSException *exc = nil;
108 exc = [NSException exceptionWithName:NSInvalidArgumentException
110 userInfo:[NSDictionary dictionaryWithObject:_self forKey:@"map"]];
114 @interface _NGHashMapObjectEnumerator : NSEnumerator
117 NSEnumerator *elements;
120 - (id)initWithHashMap:(NGHashMap *)_hashMap;
124 @interface _NGHashMapObjectForKeyEnumerator : NSEnumerator
129 - (id)initWithHashMap:(NGHashMap *)_hashMap andKey:(id)_key;
133 @interface _NGHashMapKeyEnumerator : NSEnumerator
135 NSMapEnumerator enumerator;
138 - (id)initWithHashMap:(NGHashMap *)_hashMap;
142 // ************************* NGHashMap *************************
144 @interface NGHashMap(private)
145 - (LList *)__structForKey:(id)_key;
146 - (NSMapEnumerator)__keyEnumerator;
147 - (void)__removeAllObjectsForKey:(id)_key;
148 - (void)__removeAllObjects;
151 static Class NSArrayClass = Nil;
153 @implementation NGHashMap
156 NSArrayClass = [NSArray class];
161 static inline void _removeAllObjectsInList(LList *list) {
163 register LList *element;
165 [list->object release];
168 if (element) free(element);
172 static inline LList *__structForKey(NGHashMap *self, id _key) {
173 if (_key == nil) raiseInvalidArgumentExceptionForNilKey(self);
175 NSCAssert(self->table, @"missing table ..");
177 return (LList *)NSMapGet(self->table, (void *)_key);
180 static inline unsigned __countObjectsForKey(NGHashMap *self, id _key) {
182 return (list = __structForKey(self, _key)) ? list->count : 0;
188 return [[[self alloc] init] autorelease];
190 + (id)hashMapWithHashMap:(NGHashMap *)_hashMap {
191 return [[[self alloc] initWithHashMap:_hashMap] autorelease];
193 + (id)hashMapWithObjects:(NSArray *)_objects forKey:(id)_key {
194 return [[[self alloc] initWithObjects:_objects forKey:_key] autorelease];
196 + (id)hashMapWithDictionary:(NSDictionary *)_dict {
197 return [[[self alloc] initWithDictionary:_dict] autorelease];
201 return [self initWithCapacity:0];
204 - (id)initWithCapacity:(unsigned int)_size {
205 if ((self = [super init])) {
206 self->table = NSCreateMapTableWithZone(NSObjectMapKeyCallBacks,
207 NSNonOwnedPointerMapValueCallBacks,
209 NSAssert1(self->table, @"missing table for hashmap of size %d ..", _size);
214 - (id)initWithHashMap:(NGHashMap *)_hashMap {
215 NSEnumerator *keys = nil;
218 LList *newList = NULL;
219 LList *oldList = NULL;
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);
231 newList = initLListElement(list->object,NULL);
232 oldList->next = newList;
239 - (id)initWithObjects:(NSArray *)_objects forKey:(id)_key {
241 LList *element = NULL;
246 if (( self = [self initWithCapacity:1])) {
247 count = [_objects count];
251 root = initLListElement([_objects objectAtIndex:0], NULL);
253 for (i = 1; i < count; i++) {
254 element = initLListElement([_objects objectAtIndex:i], NULL);
255 pred->next = element;
259 NSMapInsert(self->table,_key, root);
261 NSAssert(self->table, @"missing table for hashmap ..");
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]];
272 self = [self initWithCapacity:[_dictionary count]];
278 keys = [_dictionary keyEnumerator];
279 while ((key = [keys nextObject])) {
280 [(NGMutableHashMap *)self
281 setObject:[_dictionary objectForKey:key]
285 NSAssert(self->table, @"missing table for hashmap ..");
291 NSMapEnumerator mapenum;
292 id key = nil, value = nil;
294 mapenum = [self __keyEnumerator];
296 while (NSNextMapEnumeratorPair(&mapenum, (void **)&key, (void **)&value))
297 _removeAllObjectsInList((LList *)value);
299 NSFreeMapTable(self->table);
307 - (void)__removeAllObjectsForKey:(id)_key {
308 _removeAllObjectsInList(__structForKey(self, _key));
309 NSMapRemove(self->table, _key);
312 - (void)__removeAllObjects {
313 NSEnumerator *keys = nil;
316 keys = [self keyEnumerator];
317 while ((key = [keys nextObject]))
318 _removeAllObjectsInList(__structForKey(self, key));
320 NSResetMapTable(self->table);
325 - (unsigned int)hash {
329 - (BOOL)isEqual:(id)anObject {
330 if (self == anObject)
333 if (![anObject isKindOfClass:[NGHashMap class]])
336 return [self isEqualToHashMap:anObject];
339 - (BOOL)isEqualToHashMap:(NGHashMap *)_other {
340 NSEnumerator *keyEnumerator = nil;
342 LList *selfList = NULL;
343 LList *otherList = NULL;
348 if ([self count] != [_other count])
351 keyEnumerator = [self keyEnumerator];
352 while ((key = [keyEnumerator nextObject])) {
353 if (__countObjectsForKey(self, key) != [_other countObjectsForKey:key])
356 selfList = __structForKey(self, key);
357 otherList = [_other __structForKey:key];
359 if (![selfList->object isEqual:otherList->object])
362 selfList = selfList->next;
363 otherList = otherList->next;
370 - (id)objectForKey:(id)_key {
373 if (!(list = __structForKey(self, _key)))
377 NSLog(@"WARNING[%s] more than one element for key %@ objects: %@, "
378 @"return first object", __PRETTY_FUNCTION__, _key,
379 [self objectsForKey:_key]);
384 - (NSArray *)objectsForKey:(id)_key {
385 NSArray *array = nil;
386 NSEnumerator *objectEnum = nil;
391 if ((objectEnum = [self objectEnumeratorForKey:_key]) == nil)
394 objects = calloc(__countObjectsForKey(self, _key) + 1, sizeof(id));
395 for (i = 0; (object = [objectEnum nextObject]); i++)
398 array = [NSArrayClass arrayWithObjects:objects count:i];
399 if (objects) free(objects);
403 - (id)objectAtIndex:(unsigned int)_index forKey:(id)_key {
406 if (!(list = __structForKey(self, _key)))
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];
422 - (NSArray *)allKeys {
423 NSArray *array = nil;
429 objects = calloc([self count] + 1, sizeof(id));
430 keys = [self keyEnumerator];
431 for(i = 0; (object = [keys nextObject]); i++)
434 array = [[NSArrayClass alloc] initWithObjects:objects count:i];
435 if (objects) free (objects);
436 return [array autorelease];
439 - (NSArray *)allObjects {
440 NSEnumerator *keys = nil;
442 NSMutableArray *mArray = nil;
443 NSArray *result = nil;
445 mArray = [[NSMutableArray alloc] init];
446 keys = [self keyEnumerator];
447 while ((object = [keys nextObject]))
448 [mArray addObjectsFromArray:[self objectsForKey:object]];
450 result = [mArray copy];
451 [mArray release]; mArray = nil;
452 return [result autorelease];
455 - (unsigned int)countObjectsForKey:(id)_key {
456 return __countObjectsForKey(self, _key);
459 - (NSEnumerator *)keyEnumerator {
460 return [[[_NGHashMapKeyEnumerator alloc] initWithHashMap:self] autorelease];
463 - (NSEnumerator *)objectEnumerator {
464 return [[[_NGHashMapObjectEnumerator alloc]
465 initWithHashMap:self] autorelease];
468 - (NSEnumerator *)objectEnumeratorForKey:(id)_key {
470 raiseInvalidArgumentExceptionForNilKey(self);
472 return [[[_NGHashMapObjectForKeyEnumerator alloc]
473 initWithHashMap:self andKey:_key] autorelease];
476 - (NSDictionary *)asDictionaryWithArraysForValues:(BOOL)arraysOnly {
477 NSDictionary *dict = nil;
484 keys = [self keyEnumerator];
485 cntKey = [self count];
486 dicObj = calloc(cntKey + 1, sizeof(id));
487 dicKeys = calloc(cntKey + 1, sizeof(id));
489 for (cntKey = 0; (key = [keys nextObject]); ) {
493 if ((list = __structForKey(self, key)) == NULL) {
494 NSLog(@"ERROR(%s): did not find key '%@' in hashmap: %@",
495 __PRETTY_FUNCTION__, key, self);
503 objects = calloc(list->count + 1, sizeof(id));
507 objects[cntObj++] = list->object;
511 object = [NSArray arrayWithObjects:objects count:cntObj];
513 if (objects) free(objects); objects = NULL;
517 object = [NSArray arrayWithObject:list->object ];
519 object = list->object;
523 dicObj[cntKey] = object;
524 dicKeys[cntKey++] = key;
527 dict = [[NSDictionary alloc]
528 initWithObjects:dicObj forKeys:dicKeys count:cntKey];
530 if (dicObj) free(dicObj); dicObj = NULL;
531 if (dicKeys) free(dicKeys); dicKeys = NULL;
532 return [dict autorelease];
535 - (NSDictionary *)asDictionary {
536 return [ self asDictionaryWithArraysForValues: NO ];
539 - (NSDictionary *)asDictionaryWithArraysForValues {
540 return [ self asDictionaryWithArraysForValues: YES ];
545 NSDictionary *dict = nil;
546 NSEnumerator *keys = nil;
552 keys = [self keyEnumerator];
553 cntKey = [self count];
554 dicObj = calloc(cntKey + 1, sizeof(id));
555 dicKeys = calloc(cntKey + 1, sizeof(id));
557 for (cntKey = 0; (key = [keys nextObject]); ) {
561 list = __structForKey(self, key);
566 objects = calloc(list->count + 1, sizeof(id));
570 objects[cntObj++] = list->object;
573 object = [NSArrayClass arrayWithObjects:objects count:cntObj];
575 if (objects) free(objects); objects = NULL;
578 object = list->object;
580 dicObj[cntKey] = object;
581 dicKeys[cntKey] = key;
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;
593 - (NSString *)description {
594 return [[self propertyList] description];
597 - (unsigned int)count {
598 return self->table ? NSCountMapTable(table) : 0;
603 - (id)copyWithZone:(NSZone *)_zone {
604 return [[NGHashMap allocWithZone:_zone] initWithHashMap:self];
607 - (id)mutableCopyWithZone:(NSZone *)_zone {
608 return [[NGMutableHashMap allocWithZone:_zone] initWithHashMap:self];
613 - (NSMapEnumerator)__keyEnumerator {
614 return NSEnumerateMapTable(table);
617 - (LList *)__structForKey:(id)_key {
618 return __structForKey(self, _key);
623 - (void)encodeWithCoder:(NSCoder *)_encoder {
624 unsigned keyCount = [self count];
625 NSMapEnumerator mapenum = [self __keyEnumerator];
629 [_encoder encodeValueOfObjCType:@encode(unsigned) at:&keyCount];
631 while (NSNextMapEnumeratorPair(&mapenum, (void **)&key, (void **)&value)) {
632 unsigned valueCount = value ? value->count : 0;
633 unsigned outCount = 0; // debugging
635 [_encoder encodeObject:key];
636 [_encoder encodeValueOfObjCType:@encode(unsigned) at:&valueCount];
639 [_encoder encodeObject:value->object];
644 NSAssert(valueCount == outCount, @"didn't encode enough value objects");
648 - (id)initWithCoder:(NSCoder *)_decoder {
649 NGMutableHashMap *map = [[NGMutableHashMap alloc] init];
653 [_decoder decodeValueOfObjCType:@encode(unsigned) at:&keyCount];
654 for (cnt = 0; cnt < keyCount; cnt++) {
655 unsigned valueCount = 0, cnt2 = 0;
658 key = [_decoder decodeObject];
659 [_decoder decodeValueOfObjCType:@encode(unsigned) at:&valueCount];
661 for (cnt2 = 0; cnt2 < valueCount; cnt2++) {
662 id value = [_decoder decodeObject];
663 [map addObject:value forKey:key];
667 self = [self initWithHashMap:map];
668 [map release]; map = nil;
675 // ************************* NGMutableHashMap ******************
677 @implementation NGMutableHashMap
679 + (id)hashMapWithCapacity:(unsigned int)_numItems {
680 return [[[self alloc] initWithCapacity:_numItems] autorelease];
684 return [self initWithCapacity:0];
687 /* inserting objects */
689 - (void)insertObject:(id)_object atIndex:(unsigned int)_index forKey:(id)_key {
690 [self insertObjects:&_object count:1 atIndex:_index forKey:_key];
693 - (void)insertObjects:(NSArray *)_objects atIndex:(unsigned int)_index
700 cntI = [_objects count];
701 objects = calloc(cntI + 1, sizeof(id));
702 for (i = 0 ; i < cntI; i++)
703 objects[i] = [_objects objectAtIndex:i];
705 [self insertObjects:objects count:cntI atIndex:_index forKey:_key];
706 if (objects) free(objects);
709 - (void)insertObjects:(id*)_objects count:(unsigned int)_count
710 atIndex:(unsigned int)_index forKey:(id)_key
714 LList *element = NULL;
720 checkForAddErrorMessage(self, _objects[0],_key);
721 if ((root = [self __structForKey:_key]) == NULL) {
723 [NSException raise:NSRangeException
724 format:@"index %d out of range in map 0x%p",
729 root = initLListElement(_objects[0], NULL);
730 root->count = _count;
731 NSMapInsert(self->table, _key, root);
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];
741 root->count += _count;
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;
754 element = initLListElement(_objects[0], NULL);
755 element->next = root->next;
756 root->next = element;
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;
771 - (void)addObjects:(id*)_objects count:(unsigned int)_count forKey:(id)_key {
773 LList *element = NULL;
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);
786 root->count += _count;
790 element = initLListElement(_objects[0], NULL);
791 root->next = element;
794 for (i = 1; i < _count; i++) {
795 checkForAddErrorMessage(self, _objects[i], _key);
796 element = initLListElement(_objects[i], NULL);
797 root->next = element;
802 - (void)addObject:(id)_object forKey:(id)_key {
803 checkForAddErrorMessage(self, _object,_key);
804 [self addObjects:&_object count:1 forKey:_key];
807 - (void)addObjects:(NSArray *)_objects forKey:(id)_key {
812 cntI = [_objects count];
813 objects = calloc(cntI + 1, sizeof(id));
814 for (i = 0 ; i < cntI; i++)
815 objects[i] = [_objects objectAtIndex:i];
817 [self addObjects:objects count:cntI forKey:_key];
818 if (objects) free(objects);
821 /* setting objects */
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];
829 - (void)setObjects:(NSArray *)_objects forKey:(id)_key {
830 checkForAddErrorMessage(self, _objects, _key);
831 [self removeAllObjectsForKey:_key];
832 [self addObjects:_objects forKey:_key];
835 /* removing objects */
837 - (void)removeAllObjects {
838 [self __removeAllObjects];
841 - (void)removeAllObjectsForKey:(id)_key {
842 [self __removeAllObjectsForKey:_key];
845 - (void)removeAllObjects:(id)_object forKey:(id)_key {
848 LList *oldList = NULL;
849 unsigned int cnt = 0;
851 checkForRemoveErrorMessage(self, _object, _key);
852 if (!(root = [self __structForKey:_key]))
855 while ([root->object isEqual:_object]) {
856 [root->object release];
857 if (root->next == NULL) {
858 if (root) free(root);
860 NSMapRemove(self->table,_key);
865 root->next = list->next;
866 root->object = list->object;
868 if (list) free(list);
877 if ([list->object isEqual:_object]) {
879 oldList->next = list->next;
880 if (list) free(list);
888 - (void)removeAllObjectsForKeys:(NSArray *)_keyArray {
889 register int index = 0;
890 for (index = [_keyArray count]; index > 0;)
891 [self removeAllObjectsForKey:[_keyArray objectAtIndex:--index]];
894 @end /* NGMutableHashMap */
896 // ************************* Enumerators ******************
898 @implementation _NGHashMapKeyEnumerator
900 - (id)initWithHashMap:(NGHashMap *)_hashMap {
901 self->map = [_hashMap retain];
902 self->enumerator = [_hashMap __keyEnumerator];
912 return NSNextMapEnumeratorPair(&self->enumerator,(void**)&key, (void**)&value) ?
916 @end /* _NGHashMapKeyEnumerator */
918 @implementation _NGHashMapObjectEnumerator
920 - (id)initWithHashMap:(NGHashMap *)_hashMap {
921 self->keys = [[_hashMap keyEnumerator] retain];
922 self->hashMap = [_hashMap retain];
923 self->elements = nil;
928 [self->keys release];
929 [self->hashMap release];
930 [self->elements release];
938 if ((object = [self->elements nextObject]))
941 if ((key = [self->keys nextObject])) {
942 ASSIGN(self->elements, [self->hashMap objectEnumeratorForKey:key]);
943 object = [self->elements nextObject];
948 @end /* _NGHashMapObjectEnumerator */
950 @implementation _NGHashMapObjectForKeyEnumerator
952 - (id)initWithHashMap:(NGHashMap *)_hashMap andKey:(id)_key {
953 element = [_hashMap __structForKey:_key];
954 self->map = [_hashMap retain];
968 object = element->object;
969 element = element->next;
973 @end /* _NGHashMapObjectForKeyEnumerator */