ObjFW  Check-in [b9015dbc75]

Overview
Comment:Due to a 32 bit hash, a dictionary can never be bigger than UINT32_MAX.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: b9015dbc75f5996210422ef982bce700b0aa01f7053665b5b38e842401ae14a8
User & Date: js on 2010-04-17 10:48:05
Other Links: manifest | tags
Context
2010-04-17
11:12
Rewrite OFDictionary code to make it more readable. check-in: 9f260d5f50 user: js tags: trunk
10:48
Due to a 32 bit hash, a dictionary can never be bigger than UINT32_MAX. check-in: b9015dbc75 user: js tags: trunk
10:35
Make resizing a private method instead of inlining. check-in: e870ea71ac user: js tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified src/OFDictionary.h from [507b931699] to [06ef929ac6].

︙︙
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


@class OFArray;

/// \cond internal
struct of_dictionary_bucket
{
	OFObject <OFCopying> *key;
	OFObject	     *object;
	uint32_t	     hash;
};
/// \endcond

/**
 * \brief A class for storing objects in a hash table.
 */
@interface OFDictionary: OFObject <OFCopying, OFMutableCopying,
    OFFastEnumeration>
{
	struct of_dictionary_bucket *data;
	size_t			    size;
	size_t			    count;
}

/**
 * Creates a new OFDictionary.
 *
 * \return A new autoreleased OFDictionary
 */








|
|










|
|








16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


@class OFArray;

/// \cond internal
struct of_dictionary_bucket
{
	OFObject <OFCopying> *key;
	OFObject *object;
	uint32_t hash;
};
/// \endcond

/**
 * \brief A class for storing objects in a hash table.
 */
@interface OFDictionary: OFObject <OFCopying, OFMutableCopying,
    OFFastEnumeration>
{
	struct of_dictionary_bucket *data;
	uint32_t size;
	size_t count;
}

/**
 * Creates a new OFDictionary.
 *
 * \return A new autoreleased OFDictionary
 */
︙︙
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

- (OFEnumerator*)keyEnumerator;
@end

/// \cond internal
@interface OFDictionaryEnumerator: OFEnumerator
{
	struct of_dictionary_bucket *data;
	size_t			    size;
	unsigned long		    mutations;
	unsigned long		    *mutations_ptr;
	size_t			    pos;
}

-     initWithData: (struct of_dictionary_bucket*)data
	      size: (size_t)size
  mutationsPointer: (unsigned long*)mutations_ptr;
@end

@interface OFDictionaryObjectEnumerator: OFDictionaryEnumerator
@end

@interface OFDictionaryKeyEnumerator: OFDictionaryEnumerator
@end
/// \endcond

#import "OFMutableDictionary.h"

extern const int of_dictionary_deleted_bucket;








|
|
|
|



|














159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

- (OFEnumerator*)keyEnumerator;
@end

/// \cond internal
@interface OFDictionaryEnumerator: OFEnumerator
{
	struct of_dictionary_bucket *data;
	uint32_t size;
	unsigned long mutations;
	unsigned long *mutations_ptr;
	uint32_t pos;
}

-     initWithData: (struct of_dictionary_bucket*)data
	      size: (uint32_t)size
  mutationsPointer: (unsigned long*)mutations_ptr;
@end

@interface OFDictionaryObjectEnumerator: OFDictionaryEnumerator
@end

@interface OFDictionaryKeyEnumerator: OFDictionaryEnumerator
@end
/// \endcond

#import "OFMutableDictionary.h"

extern const int of_dictionary_deleted_bucket;

Modified src/OFDictionary.m from [ce38252c5d] to [f856f20ee2].

︙︙
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

	data[0].key = nil;

	return self;
}

- initWithDictionary: (OFDictionary*)dict
{
	size_t i;

	self = [super init];

	if (dict == nil) {
		Class c = isa;
		size = 0;
		[self dealloc];








|








83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

	data[0].key = nil;

	return self;
}

- initWithDictionary: (OFDictionary*)dict
{
	uint32_t i;

	self = [super init];

	if (dict == nil) {
		Class c = isa;
		size = 0;
		[self dealloc];
︙︙
202
203
204
205
206
207
208
209
210
211
212
213



214
215
216
217
218
219
220

	self = [super init];

	@try {
		keys_carray = [keys cArray];
		objs_carray = [objs cArray];
		count = [keys count];

		if (count > SIZE_MAX / 8)
			@throw [OFOutOfRangeException newWithClass: isa];

		for (size = 1; size < count; size <<= 1);




		data = [self allocMemoryForNItems: size
					 withSize: BUCKET_SIZE];
	} @catch (OFException *e) {
		/*
		 * We can't use [super dealloc] on OS X here. Compiler bug?
		 * Anyway, set size to 0 so that [self dealloc] works.
		 */








|




>
>
>








202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

	self = [super init];

	@try {
		keys_carray = [keys cArray];
		objs_carray = [objs cArray];
		count = [keys count];

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException newWithClass: isa];

		for (size = 1; size < count; size <<= 1);

		if (size == 0)
			@throw [OFOutOfRangeException newWithClass: isa];

		data = [self allocMemoryForNItems: size
					 withSize: BUCKET_SIZE];
	} @catch (OFException *e) {
		/*
		 * We can't use [super dealloc] on OS X here. Compiler bug?
		 * Anyway, set size to 0 so that [self dealloc] works.
		 */
︙︙
335
336
337
338
339
340
341
342
343
344
345
346
347
348






349
350
351
352
353
354
355


	self = [super init];

	count = 1;
	for (va_copy(args2, args); va_arg(args2, OFObject*) != nil; count++);
	count >>= 1;

	if (count > SIZE_MAX / 8) {
		Class c = isa;
		[self dealloc];
		@throw [OFOutOfRangeException newWithClass: c];
	}

	for (size = 1; size < count; size <<= 1);







	@try {
		data = [self allocMemoryForNItems: size
					 withSize: BUCKET_SIZE];
	} @catch (OFException *e) {
		/*
		 * We can't use [super dealloc] on OS X here. Compiler bug?








|






>
>
>
>
>
>








338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364


	self = [super init];

	count = 1;
	for (va_copy(args2, args); va_arg(args2, OFObject*) != nil; count++);
	count >>= 1;

	if (count > UINT32_MAX) {
		Class c = isa;
		[self dealloc];
		@throw [OFOutOfRangeException newWithClass: c];
	}

	for (size = 1; size < count; size <<= 1);

	if (size == 0) {
		Class c = isa;
		[self dealloc];
		@throw [OFOutOfRangeException newWithClass: c];
	}

	@try {
		data = [self allocMemoryForNItems: size
					 withSize: BUCKET_SIZE];
	} @catch (OFException *e) {
		/*
		 * We can't use [super dealloc] on OS X here. Compiler bug?
︙︙
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405

	}

	data[j].key = key;
	data[j].object = obj;
	data[j].hash = hash;

	for (i = 1; i < count; i++) {
		size_t last;

		key = va_arg(args, OFObject <OFCopying>*);
		obj = va_arg(args, OFObject*);

		if (key == nil || obj == nil) {
			Class c = isa;
			[self dealloc];








|








400
401
402
403
404
405
406
407
408
409
410
411
412
413
414

	}

	data[j].key = key;
	data[j].object = obj;
	data[j].hash = hash;

	for (i = 1; i < count; i++) {
		uint32_t last;

		key = va_arg(args, OFObject <OFCopying>*);
		obj = va_arg(args, OFObject*);

		if (key == nil || obj == nil) {
			Class c = isa;
			[self dealloc];
︙︙
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568

- (id)mutableCopy
{
	return [[OFMutableDictionary alloc] initWithDictionary: self];
}

- (BOOL)isEqual: (OFDictionary*)dict
{
	size_t i;

	if ([dict count] != count)
		return NO;

	for (i = 0; i < size; i++)
		if (data[i].key != nil && data[i].key != DELETED &&
		    ![[dict objectForKey: data[i].key] isEqual: data[i].object])
			return NO;

	return YES;
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	size_t i;

	for (i = 0; i < count_; i++) {
		for (; state->state < size && (data[state->state].key == nil ||
		    data[state->state].key == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state].key;








|
















|








546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577

- (id)mutableCopy
{
	return [[OFMutableDictionary alloc] initWithDictionary: self];
}

- (BOOL)isEqual: (OFDictionary*)dict
{
	uint32_t i;

	if ([dict count] != count)
		return NO;

	for (i = 0; i < size; i++)
		if (data[i].key != nil && data[i].key != DELETED &&
		    ![[dict objectForKey: data[i].key] isEqual: data[i].object])
			return NO;

	return YES;
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	int i;

	for (i = 0; i < count_; i++) {
		for (; state->state < size && (data[state->state].key == nil ||
		    data[state->state].key == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state].key;
︙︙
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619

		initWithData: data
			size: size
	    mutationsPointer: NULL] autorelease];
}

- (void)dealloc
{
	size_t i;

	for (i = 0; i < size; i++) {
		if (data[i].key != nil && data[i].key != DELETED) {
			[data[i].key release];
			[data[i].object release];
		}
	}

	[super dealloc];
}

- (uint32_t)hash
{
	size_t i;
	uint32_t hash;

	OF_HASH_INIT(hash);

	for (i = 0; i < size; i++) {
		if (data[i].key != nil && data[i].key != DELETED) {
			uint32_t kh = [data[i].key hash];








|













|








600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628

		initWithData: data
			size: size
	    mutationsPointer: NULL] autorelease];
}

- (void)dealloc
{
	uint32_t i;

	for (i = 0; i < size; i++) {
		if (data[i].key != nil && data[i].key != DELETED) {
			[data[i].key release];
			[data[i].object release];
		}
	}

	[super dealloc];
}

- (uint32_t)hash
{
	uint32_t i;
	uint32_t hash;

	OF_HASH_INIT(hash);

	for (i = 0; i < size; i++) {
		if (data[i].key != nil && data[i].key != DELETED) {
			uint32_t kh = [data[i].key hash];
︙︙
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649

	return hash;
}
@end

/// \cond internal
@implementation OFDictionaryEnumerator
-     initWithData: (struct of_dictionary_bucket*)data_
	      size: (size_t)size_
  mutationsPointer: (unsigned long*)mutations_ptr_
{
	self = [super init];

	data = data_;
	size = size_;
	mutations = *mutations_ptr_;








|








644
645
646
647
648
649
650
651
652
653
654
655
656
657
658

	return hash;
}
@end

/// \cond internal
@implementation OFDictionaryEnumerator
-     initWithData: (struct of_dictionary_bucket*)data_
	      size: (uint32_t)size_
  mutationsPointer: (unsigned long*)mutations_ptr_
{
	self = [super init];

	data = data_;
	size = size_;
	mutations = *mutations_ptr_;
︙︙

Modified src/OFMutableDictionary.m from [f91e7929a8] to [74e169c6cb].

︙︙
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

- (void)_resizeForCount: (size_t)newcount
{
	size_t fill = newcount * 4 / size;
	size_t newsize;
	struct of_dictionary_bucket *newdata;
	uint32_t i;

	if (newcount > SIZE_MAX / 4)
		@throw [OFOutOfRangeException newWithClass: isa];

	if (fill >= 3)
		newsize = size << 1;
	else if (fill <= 1)
		newsize = size >> 1;
	else








|








24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

- (void)_resizeForCount: (size_t)newcount
{
	size_t fill = newcount * 4 / size;
	size_t newsize;
	struct of_dictionary_bucket *newdata;
	uint32_t i;

	if (newcount > UINT32_MAX)
		@throw [OFOutOfRangeException newWithClass: isa];

	if (fill >= 3)
		newsize = size << 1;
	else if (fill <= 1)
		newsize = size >> 1;
	else
︙︙
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

	return [[OFDictionary alloc] initWithDictionary: self];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	size_t i;

	for (i = 0; i < count_; i++) {
		for (; state->state < size && (data[state->state].key == nil ||
		    data[state->state].key == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state].key;








|








196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

	return [[OFDictionary alloc] initWithDictionary: self];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	int i;

	for (i = 0; i < count_; i++) {
		for (; state->state < size && (data[state->state].key == nil ||
		    data[state->state].key == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state].key;
︙︙