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 Side-by-Side 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

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;
	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;
	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

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;
	uint32_t size;
	unsigned long mutations;
	unsigned long *mutations_ptr;
	uint32_t pos;
}

-     initWithData: (struct of_dictionary_bucket*)data
	      size: (size_t)size
	      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

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;
	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

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 > SIZE_MAX / 8)
		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

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 > SIZE_MAX / 8) {
	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

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++) {
		size_t last;
		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

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
{
	size_t i;
	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_
{
	size_t i;
	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

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
{
	size_t i;
	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
{
	size_t i;
	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

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: (size_t)size_
	      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

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)
	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

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;
	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;
︙

Fossil 2.23 [47362306a7] 2023-11-01 18:56:47
This page was generated in about 0.018s