2 Copyright (C) 2000-2004 SKYRIX Software AG
4 This file is part of OpenGroupware.org.
6 OGo 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 OGo 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 OGo; 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 stringWithFormat:@"nil key to be added in HashMap with object %@",
53 _object ? _object : @"<nil>"];
54 ui = [NSDictionary dictionaryWithObjectsAndKeys:
56 _key ? _key : @"<nil>",
58 _object ? _object : @"<nil>",
61 exc = [NSException exceptionWithName:NSInvalidArgumentException
62 reason:r userInfo:ui];
66 r = [NSString stringWithFormat:
67 @"nil object to be added in HashMap for key %@",
68 _key ? _key : @"<nil>"];
69 ui = [NSDictionary dictionaryWithObjectsAndKeys:
71 _key ? _key : @"<nil>",
73 _object ? _object : @"<nil>",
76 exc = [NSException exceptionWithName:NSInvalidArgumentException
77 reason:r userInfo:ui];
82 static inline void checkForRemoveErrorMessage(id _self, id _object, id _key) {
87 if (_object != nil && _key != nil)
90 r = [NSString stringWithFormat:
91 @"nil object to be removed in HashMap for key %@",
92 _key ? _key : @"<nil>"];
93 ui = [NSDictionary dictionaryWithObjectsAndKeys:
95 _key ? _key : @"<nil>",
97 _object ? _object : @"<nil>",
100 exc = [NSException exceptionWithName:NSInvalidArgumentException
101 reason:r userInfo:ui];
105 static inline void raiseInvalidArgumentExceptionForNilKey(id _self) {
106 NSException *exc = nil;
107 exc = [NSException exceptionWithName:NSInvalidArgumentException
109 userInfo:[NSDictionary dictionaryWithObject:_self forKey:@"map"]];
113 @interface _NGHashMapObjectEnumerator : NSEnumerator
116 NSEnumerator *elements;
119 - (id)initWithHashMap:(NGHashMap *)_hashMap;
123 @interface _NGHashMapObjectForKeyEnumerator : NSEnumerator
128 - (id)initWithHashMap:(NGHashMap *)_hashMap andKey:(id)_key;
132 @interface _NGHashMapKeyEnumerator : NSEnumerator
134 NSMapEnumerator enumerator;
137 - (id)initWithHashMap:(NGHashMap *)_hashMap;
141 // ************************* NGHashMap *************************
143 @interface NGHashMap(private)
144 - (LList *)__structForKey:(id)_key;
145 - (NSMapEnumerator)__keyEnumerator;
146 - (void)__removeAllObjectsForKey:(id)_key;
147 - (void)__removeAllObjects;
150 static Class NSArrayClass = Nil;
152 @implementation NGHashMap
155 NSArrayClass = [NSArray class];
160 static inline void _removeAllObjectsInList(LList *list) {
162 register LList *element;
164 [list->object release];
167 if (element) free(element);
171 static inline LList *__structForKey(NGHashMap *self, id _key) {
172 if (_key == nil) raiseInvalidArgumentExceptionForNilKey(self);
174 NSCAssert(self->table, @"missing table ..");
176 return (LList *)NSMapGet(self->table, (void *)_key);
179 static inline unsigned __countObjectsForKey(NGHashMap *self, id _key) {
181 return (list = __structForKey(self, _key)) ? list->count : 0;
187 return [[[self alloc] init] autorelease];
189 + (id)hashMapWithHashMap:(NGHashMap *)_hashMap {
190 return [[[self alloc] initWithHashMap:_hashMap] autorelease];
192 + (id)hashMapWithObjects:(NSArray *)_objects forKey:(id)_key {
193 return [[[self alloc] initWithObjects:_objects forKey:_key] autorelease];
195 + (id)hashMapWithDictionary:(NSDictionary *)_dict {
196 return [[[self alloc] initWithDictionary:_dict] autorelease];
200 return [self initWithCapacity:0];
203 - (id)initWithCapacity:(unsigned int)_size {
204 if ((self = [super init])) {
205 self->table = NSCreateMapTableWithZone(NSObjectMapKeyCallBacks,
206 NSNonOwnedPointerMapValueCallBacks,
208 NSAssert1(self->table, @"missing table for hashmap of size %d ..", _size);
213 - (id)initWithHashMap:(NGHashMap *)_hashMap {
214 NSEnumerator *keys = nil;
217 LList *newList = NULL;
218 LList *oldList = NULL;
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);
230 newList = initLListElement(list->object,NULL);
231 oldList->next = newList;
238 - (id)initWithObjects:(NSArray *)_objects forKey:(id)_key {
240 LList *element = NULL;
245 if (( self = [self initWithCapacity:1])) {
246 count = [_objects count];
250 root = initLListElement([_objects objectAtIndex:0], NULL);
252 for (i = 1; i < count; i++) {
253 element = initLListElement([_objects objectAtIndex:i], NULL);
254 pred->next = element;
258 NSMapInsert(self->table,_key, root);
260 NSAssert(self->table, @"missing table for hashmap ..");
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]];
271 self = [self initWithCapacity:[_dictionary count]];
277 keys = [_dictionary keyEnumerator];
278 while ((key = [keys nextObject])) {
279 [(NGMutableHashMap *)self
280 setObject:[_dictionary objectForKey:key]
284 NSAssert(self->table, @"missing table for hashmap ..");
290 NSMapEnumerator mapenum;
291 id key = nil, value = nil;
293 mapenum = [self __keyEnumerator];
295 while (NSNextMapEnumeratorPair(&mapenum, (void **)&key, (void **)&value))
296 _removeAllObjectsInList((LList *)value);
298 NSFreeMapTable(self->table);
306 - (void)__removeAllObjectsForKey:(id)_key {
307 _removeAllObjectsInList(__structForKey(self, _key));
308 NSMapRemove(self->table, _key);
311 - (void)__removeAllObjects {
312 NSEnumerator *keys = nil;
315 keys = [self keyEnumerator];
316 while ((key = [keys nextObject]))
317 _removeAllObjectsInList(__structForKey(self, key));
319 NSResetMapTable(self->table);
324 - (unsigned int)hash {
328 - (BOOL)isEqual:(id)anObject {
329 if (self == anObject)
332 if (![anObject isKindOfClass:[NGHashMap class]])
335 return [self isEqualToHashMap:anObject];
338 - (BOOL)isEqualToHashMap:(NGHashMap *)_other {
339 NSEnumerator *keyEnumerator = nil;
341 LList *selfList = NULL;
342 LList *otherList = NULL;
347 if ([self count] != [_other count])
350 keyEnumerator = [self keyEnumerator];
351 while ((key = [keyEnumerator nextObject])) {
352 if (__countObjectsForKey(self, key) != [_other countObjectsForKey:key])
355 selfList = __structForKey(self, key);
356 otherList = [_other __structForKey:key];
358 if (![selfList->object isEqual:otherList->object])
361 selfList = selfList->next;
362 otherList = otherList->next;
369 - (id)objectForKey:(id)_key {
372 if (!(list = __structForKey(self, _key)))
376 NSLog(@"WARNING[%s] more than one element for key %@ objects: %@, "
377 @"return first object", __PRETTY_FUNCTION__, _key,
378 [self objectsForKey:_key]);
383 - (NSArray *)objectsForKey:(id)_key {
384 NSArray *array = nil;
385 NSEnumerator *objectEnum = nil;
390 if ((objectEnum = [self objectEnumeratorForKey:_key]) == nil)
393 objects = calloc(__countObjectsForKey(self, _key) + 1, sizeof(id));
394 for (i = 0; (object = [objectEnum nextObject]); i++)
397 array = [NSArrayClass arrayWithObjects:objects count:i];
398 if (objects) free(objects);
402 - (id)objectAtIndex:(unsigned int)_index forKey:(id)_key {
405 if (!(list = __structForKey(self, _key)))
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];
421 - (NSArray *)allKeys {
422 NSArray *array = nil;
428 objects = calloc([self count] + 1, sizeof(id));
429 keys = [self keyEnumerator];
430 for(i = 0; (object = [keys nextObject]); i++)
433 array = [[NSArrayClass alloc] initWithObjects:objects count:i];
434 if (objects) free (objects);
435 return [array autorelease];
438 - (NSArray *)allObjects {
439 NSEnumerator *keys = nil;
441 NSMutableArray *mArray = nil;
442 NSArray *result = nil;
444 mArray = [[NSMutableArray alloc] init];
445 keys = [self keyEnumerator];
446 while ((object = [keys nextObject]))
447 [mArray addObjectsFromArray:[self objectsForKey:object]];
449 result = [mArray copy];
450 [mArray release]; mArray = nil;
451 return [result autorelease];
454 - (unsigned int)countObjectsForKey:(id)_key {
455 return __countObjectsForKey(self, _key);
458 - (NSEnumerator *)keyEnumerator {
459 return [[[_NGHashMapKeyEnumerator alloc] initWithHashMap:self] autorelease];
462 - (NSEnumerator *)objectEnumerator {
463 return [[[_NGHashMapObjectEnumerator alloc]
464 initWithHashMap:self] autorelease];
467 - (NSEnumerator *)objectEnumeratorForKey:(id)_key {
469 raiseInvalidArgumentExceptionForNilKey(self);
471 return [[[_NGHashMapObjectForKeyEnumerator alloc]
472 initWithHashMap:self andKey:_key] autorelease];
475 - (NSDictionary *)asDictionaryWithArraysForValues:(BOOL)arraysOnly {
476 NSDictionary *dict = nil;
483 keys = [self keyEnumerator];
484 cntKey = [self count];
485 dicObj = calloc(cntKey + 1, sizeof(id));
486 dicKeys = calloc(cntKey + 1, sizeof(id));
488 for (cntKey = 0; (key = [keys nextObject]); ) {
492 if ((list = __structForKey(self, key)) == NULL) {
493 NSLog(@"ERROR(%s): did not find key '%@' in hashmap: %@",
494 __PRETTY_FUNCTION__, key, self);
502 objects = calloc(list->count + 1, sizeof(id));
506 objects[cntObj++] = list->object;
510 object = [NSArray arrayWithObjects:objects count:cntObj];
512 if (objects) free(objects); objects = NULL;
516 object = [NSArray arrayWithObject:list->object ];
518 object = list->object;
522 dicObj[cntKey] = object;
523 dicKeys[cntKey++] = key;
526 dict = [[NSDictionary alloc]
527 initWithObjects:dicObj forKeys:dicKeys count:cntKey];
529 if (dicObj) free(dicObj); dicObj = NULL;
530 if (dicKeys) free(dicKeys); dicKeys = NULL;
531 return [dict autorelease];
534 - (NSDictionary *)asDictionary {
535 return [ self asDictionaryWithArraysForValues: NO ];
538 - (NSDictionary *)asDictionaryWithArraysForValues {
539 return [ self asDictionaryWithArraysForValues: YES ];
544 NSDictionary *dict = nil;
545 NSEnumerator *keys = nil;
551 keys = [self keyEnumerator];
552 cntKey = [self count];
553 dicObj = calloc(cntKey + 1, sizeof(id));
554 dicKeys = calloc(cntKey + 1, sizeof(id));
556 for (cntKey = 0; (key = [keys nextObject]); ) {
560 list = __structForKey(self, key);
565 objects = calloc(list->count + 1, sizeof(id));
569 objects[cntObj++] = list->object;
572 object = [NSArrayClass arrayWithObjects:objects count:cntObj];
574 if (objects) free(objects); objects = NULL;
577 object = list->object;
579 dicObj[cntKey] = object;
580 dicKeys[cntKey] = key;
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;
592 - (NSString *)description {
593 return [[self propertyList] description];
596 - (unsigned int)count {
597 return self->table ? NSCountMapTable(table) : 0;
602 - (id)copyWithZone:(NSZone *)_zone {
603 return [[NGHashMap allocWithZone:_zone] initWithHashMap:self];
606 - (id)mutableCopyWithZone:(NSZone *)_zone {
607 return [[NGMutableHashMap allocWithZone:_zone] initWithHashMap:self];
612 - (NSMapEnumerator)__keyEnumerator {
613 return NSEnumerateMapTable(table);
616 - (LList *)__structForKey:(id)_key {
617 return __structForKey(self, _key);
622 - (void)encodeWithCoder:(NSCoder *)_encoder {
623 unsigned keyCount = [self count];
624 NSMapEnumerator mapenum = [self __keyEnumerator];
628 [_encoder encodeValueOfObjCType:@encode(unsigned) at:&keyCount];
630 while (NSNextMapEnumeratorPair(&mapenum, (void **)&key, (void **)&value)) {
631 unsigned valueCount = value ? value->count : 0;
632 unsigned outCount = 0; // debugging
634 [_encoder encodeObject:key];
635 [_encoder encodeValueOfObjCType:@encode(unsigned) at:&valueCount];
638 [_encoder encodeObject:value->object];
643 NSAssert(valueCount == outCount, @"didn't encode enough value objects");
647 - (id)initWithCoder:(NSCoder *)_decoder {
648 NGMutableHashMap *map = [[NGMutableHashMap alloc] init];
652 [_decoder decodeValueOfObjCType:@encode(unsigned) at:&keyCount];
653 for (cnt = 0; cnt < keyCount; cnt++) {
654 unsigned valueCount = 0, cnt2 = 0;
657 key = [_decoder decodeObject];
658 [_decoder decodeValueOfObjCType:@encode(unsigned) at:&valueCount];
660 for (cnt2 = 0; cnt2 < valueCount; cnt2++) {
661 id value = [_decoder decodeObject];
662 [map addObject:value forKey:key];
666 self = [self initWithHashMap:map];
667 [map release]; map = nil;
674 // ************************* NGMutableHashMap ******************
676 @implementation NGMutableHashMap
678 + (id)hashMapWithCapacity:(unsigned int)_numItems {
679 return [[[self alloc] initWithCapacity:_numItems] autorelease];
683 return [self initWithCapacity:0];
686 /* inserting objects */
688 - (void)insertObject:(id)_object atIndex:(unsigned int)_index forKey:(id)_key {
689 [self insertObjects:&_object count:1 atIndex:_index forKey:_key];
692 - (void)insertObjects:(NSArray *)_objects atIndex:(unsigned int)_index
699 cntI = [_objects count];
700 objects = calloc(cntI + 1, sizeof(id));
701 for (i = 0 ; i < cntI; i++)
702 objects[i] = [_objects objectAtIndex:i];
704 [self insertObjects:objects count:cntI atIndex:_index forKey:_key];
705 if (objects) free(objects);
708 - (void)insertObjects:(id*)_objects count:(unsigned int)_count
709 atIndex:(unsigned int)_index forKey:(id)_key
713 LList *element = NULL;
719 checkForAddErrorMessage(self, _objects[0],_key);
720 if ((root = [self __structForKey:_key]) == NULL) {
722 [NSException raise:NSRangeException
723 format:@"index %d out of range in map 0x%08X",
728 root = initLListElement(_objects[0], NULL);
729 root->count = _count;
730 NSMapInsert(self->table, _key, root);
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];
740 root->count += _count;
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;
753 element = initLListElement(_objects[0], NULL);
754 element->next = root->next;
755 root->next = element;
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;
770 - (void)addObjects:(id*)_objects count:(unsigned int)_count forKey:(id)_key {
772 LList *element = NULL;
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);
785 root->count += _count;
789 element = initLListElement(_objects[0], NULL);
790 root->next = element;
793 for (i = 1; i < _count; i++) {
794 checkForAddErrorMessage(self, _objects[i], _key);
795 element = initLListElement(_objects[i], NULL);
796 root->next = element;
801 - (void)addObject:(id)_object forKey:(id)_key {
802 checkForAddErrorMessage(self, _object,_key);
803 [self addObjects:&_object count:1 forKey:_key];
806 - (void)addObjects:(NSArray *)_objects forKey:(id)_key {
811 cntI = [_objects count];
812 objects = calloc(cntI + 1, sizeof(id));
813 for (i = 0 ; i < cntI; i++)
814 objects[i] = [_objects objectAtIndex:i];
816 [self addObjects:objects count:cntI forKey:_key];
817 if (objects) free(objects);
820 /* setting objects */
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];
828 - (void)setObjects:(NSArray *)_objects forKey:(id)_key {
829 checkForAddErrorMessage(self, _objects, _key);
830 [self removeAllObjectsForKey:_key];
831 [self addObjects:_objects forKey:_key];
834 /* removing objects */
836 - (void)removeAllObjects {
837 [self __removeAllObjects];
840 - (void)removeAllObjectsForKey:(id)_key {
841 [self __removeAllObjectsForKey:_key];
844 - (void)removeAllObjects:(id)_object forKey:(id)_key {
847 LList *oldList = NULL;
848 unsigned int cnt = 0;
850 checkForRemoveErrorMessage(self, _object, _key);
851 if (!(root = [self __structForKey:_key]))
854 while ([root->object isEqual:_object]) {
855 [root->object release];
856 if (root->next == NULL) {
857 if (root) free(root);
859 NSMapRemove(self->table,_key);
864 root->next = list->next;
865 root->object = list->object;
867 if (list) free(list);
876 if ([list->object isEqual:_object]) {
878 oldList->next = list->next;
879 if (list) free(list);
887 - (void)removeAllObjectsForKeys:(NSArray *)_keyArray {
888 register int index = 0;
889 for (index = [_keyArray count]; index > 0;)
890 [self removeAllObjectsForKey:[_keyArray objectAtIndex:--index]];
893 @end /* NGMutableHashMap */
895 // ************************* Enumerators ******************
897 @implementation _NGHashMapKeyEnumerator
899 - (id)initWithHashMap:(NGHashMap *)_hashMap {
900 self->map = [_hashMap retain];
901 self->enumerator = [_hashMap __keyEnumerator];
911 return NSNextMapEnumeratorPair(&self->enumerator,(void**)&key, (void**)&value) ?
915 @end /* _NGHashMapKeyEnumerator */
917 @implementation _NGHashMapObjectEnumerator
919 - (id)initWithHashMap:(NGHashMap *)_hashMap {
920 self->keys = [[_hashMap keyEnumerator] retain];
921 self->hashMap = [_hashMap retain];
922 self->elements = nil;
927 [self->keys release];
928 [self->hashMap release];
929 [self->elements release];
937 if ((object = [self->elements nextObject]))
940 if ((key = [self->keys nextObject])) {
941 ASSIGN(self->elements, [self->hashMap objectEnumeratorForKey:key]);
942 object = [self->elements nextObject];
947 @end /* _NGHashMapObjectEnumerator */
949 @implementation _NGHashMapObjectForKeyEnumerator
951 - (id)initWithHashMap:(NGHashMap *)_hashMap andKey:(id)_key {
952 element = [_hashMap __structForKey:_key];
953 self->map = [_hashMap retain];
967 object = element->object;
968 element = element->next;
972 @end /* _NGHashMapObjectForKeyEnumerator */