ObjFW  Check-in [c0098f89fe]

Overview
Comment:Make OFDictionary an abstract class.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: c0098f89fe0ecb846c86ee319568c4c81efa44bec43a1eedcc7b7736ffba526f
User & Date: js on 2011-08-21 11:03:21
Other Links: manifest | tags
Context
2011-08-21
21:11
Don't install headers for implementations of abstract classes. check-in: b9191c784b user: js tags: trunk
11:03
Make OFDictionary an abstract class. check-in: c0098f89fe user: js tags: trunk
2011-08-13
10:16
Introduce a naming scheme for placeholder classes. check-in: bfee66b3ec user: js tags: trunk
Changes

Modified src/Makefile from [fcce85d9ef] to [c5ddd1ebd2].

14
15
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
       OFBlock.m			\
       OFConstantString.m		\
       OFCountedSet.m			\
       OFDataArray.m			\
       OFDataArray+Hashing.m		\
       OFDate.m				\
       OFDictionary.m			\

       OFDoubleMatrix.m			\
       OFDoubleVector.m			\
       OFEnumerator.m			\
       OFFile.m				\
       OFFloatMatrix.m			\
       OFFloatVector.m			\
       OFHash.m				\
       OFHTTPRequest.m			\
       OFIntrospection.m		\
       OFList.m				\
       OFMD5Hash.m			\
       OFMutableArray.m			\
       OFMutableArray_adjacent.m	\
       OFMutableDictionary.m		\

       OFMutableSet.m			\
       OFMutableString.m		\
       OFNull.m				\
       OFNumber.m			\
       OFObject.m			\
       OFObject+Serialization.m		\
       ${OFPLUGIN_M}			\







>














>







14
15
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
       OFBlock.m			\
       OFConstantString.m		\
       OFCountedSet.m			\
       OFDataArray.m			\
       OFDataArray+Hashing.m		\
       OFDate.m				\
       OFDictionary.m			\
       OFDictionary_hashtable.m		\
       OFDoubleMatrix.m			\
       OFDoubleVector.m			\
       OFEnumerator.m			\
       OFFile.m				\
       OFFloatMatrix.m			\
       OFFloatVector.m			\
       OFHash.m				\
       OFHTTPRequest.m			\
       OFIntrospection.m		\
       OFList.m				\
       OFMD5Hash.m			\
       OFMutableArray.m			\
       OFMutableArray_adjacent.m	\
       OFMutableDictionary.m		\
       OFMutableDictionary_hashtable.m	\
       OFMutableSet.m			\
       OFMutableString.m		\
       OFNull.m				\
       OFNumber.m			\
       OFObject.m			\
       OFObject+Serialization.m		\
       ${OFPLUGIN_M}			\

Modified src/OFArray.h from [0e8f7a98da] to [21ee9eae42].

28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
    BOOL *stop);
typedef BOOL (^of_array_filter_block_t)(id odject, size_t index);
typedef id (^of_array_map_block_t)(id object, size_t index);
typedef id (^of_array_fold_block_t)(id left, id right);
#endif

/**
 * \brief A class for storing objects in an array.
 */
@interface OFArray: OFObject <OFCopying, OFMutableCopying, OFCollection,
    OFSerialization>
/**
 * \brief Creates a new OFArray.
 *
 * \return A new autoreleased OFArray







|







28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
    BOOL *stop);
typedef BOOL (^of_array_filter_block_t)(id odject, size_t index);
typedef id (^of_array_map_block_t)(id object, size_t index);
typedef id (^of_array_fold_block_t)(id left, id right);
#endif

/**
 * \brief An abstract class for storing objects in an array.
 */
@interface OFArray: OFObject <OFCopying, OFMutableCopying, OFCollection,
    OFSerialization>
/**
 * \brief Creates a new OFArray.
 *
 * \return A new autoreleased OFArray

Modified src/OFArray.m from [e560d96eaf] to [3f04bd66a0].

160
161
162
163
164
165
166













167
168
169
170
171
172
173

+ arrayWithCArray: (id*)objects
	   length: (size_t)length
{
	return [[[self alloc] initWithCArray: objects
				      length: length] autorelease];
}














- initWithObject: (id)object
{
	return [self initWithObjects: object, nil];
}

- initWithObjects: (id)firstObject, ...







>
>
>
>
>
>
>
>
>
>
>
>
>







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

+ arrayWithCArray: (id*)objects
	   length: (size_t)length
{
	return [[[self alloc] initWithCArray: objects
				      length: length] autorelease];
}

- init
{
	if ([self class] == [OFArray class] ||
	    [self class] == [OFMutableArray class]) {
		Class c = isa;
		[self release];
		@throw [OFNotImplementedException newWithClass: c
						      selector: _cmd];
	}

	return [super init];
}

- initWithObject: (id)object
{
	return [self initWithObjects: object, nil];
}

- initWithObjects: (id)firstObject, ...

Modified src/OFCountedSet.m from [01afd72625] to [306e7a046d].

15
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
 */

#include "config.h"

#define OF_COUNTED_SET_M

#import "OFCountedSet.h"
#import "OFDictionary.h"
#import "OFNumber.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFAutoreleasePool.h"

@implementation OFCountedSet
- initWithSet: (OFSet*)set
{
	self = [super init];

	@try {
		[dictionary release];
		dictionary = nil;
		dictionary = [[OFMutableDictionary alloc]
			_initWithDictionary: set->dictionary
				   copyKeys: NO];
	} @catch (id e) {
		[self release];
		@throw e;
	}








|













|







15
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
 */

#include "config.h"

#define OF_COUNTED_SET_M

#import "OFCountedSet.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFNumber.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFAutoreleasePool.h"

@implementation OFCountedSet
- initWithSet: (OFSet*)set
{
	self = [super init];

	@try {
		[dictionary release];
		dictionary = nil;
		dictionary = [[OFMutableDictionary_hashtable alloc]
			_initWithDictionary: set->dictionary
				   copyKeys: NO];
	} @catch (id e) {
		[self release];
		@throw e;
	}

Modified src/OFDictionary.h from [49e5b8dc83] to [661b980566].

26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#ifdef OF_HAVE_BLOCKS
typedef void (^of_dictionary_enumeration_block_t)(id key, id object,
     BOOL *stop);
typedef BOOL (^of_dictionary_filter_block_t)(id key, id object);
typedef id (^of_dictionary_map_block_t)(id key, id object);
#endif

struct of_dictionary_bucket
{
	id <OFCopying> key;
	id object;
	uint32_t hash;
};

/**
 * \brief A class for storing objects in a hash table.
 *
 * Note: Fast enumeration on a dictionary enumerates through the keys of the
 * dictionary.
 */
@interface OFDictionary: OFObject <OFCopying, OFMutableCopying, OFCollection,
    OFSerialization>
{
	struct of_dictionary_bucket **data;
	uint32_t size;
	size_t count;
}

/**
 * \brief Creates a new OFDictionary.
 *
 * \return A new autoreleased OFDictionary
 */
+ dictionary;








<
<
<
<
<
<
<

|






<
<
<
<
<
<







26
27
28
29
30
31
32







33
34
35
36
37
38
39
40






41
42
43
44
45
46
47
#ifdef OF_HAVE_BLOCKS
typedef void (^of_dictionary_enumeration_block_t)(id key, id object,
     BOOL *stop);
typedef BOOL (^of_dictionary_filter_block_t)(id key, id object);
typedef id (^of_dictionary_map_block_t)(id key, id object);
#endif








/**
 * \brief An abstract class for storing objects in a dictionary.
 *
 * Note: Fast enumeration on a dictionary enumerates through the keys of the
 * dictionary.
 */
@interface OFDictionary: OFObject <OFCopying, OFMutableCopying, OFCollection,
    OFSerialization>






/**
 * \brief Creates a new OFDictionary.
 *
 * \return A new autoreleased OFDictionary
 */
+ dictionary;

226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M)
- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys;
#endif
@end

@interface OFDictionaryEnumerator: OFEnumerator
{
	OFDictionary *dictionary;
	struct of_dictionary_bucket **data;
	uint32_t size;
	unsigned long mutations;
	unsigned long *mutationsPtr;
	uint32_t pos;
}

- initWithDictionary: (OFDictionary*)dictionary
		data: (struct of_dictionary_bucket**)data
		size: (uint32_t)size
    mutationsPointer: (unsigned long*)mutationsPtr;
@end

@interface OFDictionaryObjectEnumerator: OFDictionaryEnumerator
@end

@interface OFDictionaryKeyEnumerator: OFDictionaryEnumerator
@end

#import "OFMutableDictionary.h"

#ifdef __cplusplus
extern "C" {
#endif
extern struct of_dictionary_bucket of_dictionary_deleted_bucket;
#ifdef __cplusplus
}
#endif







|
<
<
<
<
<
<
<
<
<
<
<
<
<


<
<
<
<
<
<

<
<
<
<
<
<
<
<
213
214
215
216
217
218
219
220













221
222






223









#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M)
- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys;
#endif
@end

@interface OFDictionary_placeholder: OFDictionary













@end







#import "OFMutableDictionary.h"








Modified src/OFDictionary.m from [45afb75ecd] to [cb8d68b6da].

12
13
14
15
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
44
45
46
47
48
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#include <string.h>

#include <assert.h>

#import "OFDictionary.h"
#import "OFEnumerator.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFXMLElement.h"
#import "OFAutoreleasePool.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFInvalidFormatException.h"
#import "OFOutOfRangeException.h"

#import "macros.h"




struct of_dictionary_bucket of_dictionary_deleted_bucket = {};





#define DELETED &of_dictionary_deleted_bucket




































































@implementation OFDictionary














+ dictionary
{
	return [[[self alloc] init] autorelease];
}

+ dictionaryWithDictionary: (OFDictionary*)dictionary
{







<
<



|





<
<
|
<



>
>
>
|
>
>
|
>
>
|
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>







12
13
14
15
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"



#include <assert.h>

#import "OFDictionary.h"
#import "OFDictionary_hashtable.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFXMLElement.h"
#import "OFAutoreleasePool.h"



#import "OFNotImplementedException.h"


#import "macros.h"

static struct {
	Class isa;
} placeholder;

@implementation OFDictionary_placeholder
- init
{
	return (id)[[OFDictionary_hashtable alloc] init];
}

- initWithDictionary: (OFDictionary*)dictionary
{
	return (id)[[OFDictionary_hashtable alloc]
	    initWithDictionary: dictionary];
}

- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	return (id)[[OFDictionary_hashtable alloc] initWithObject: object
							   forKey: key];
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	return (id)[[OFDictionary_hashtable alloc] initWithObjects: objects
							   forKeys: keys];
}

- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list arguments;

	va_start(arguments, firstKey);
	ret = [[OFDictionary_hashtable alloc] initWithKey: firstKey
						arguments: arguments];
	va_end(arguments);

	return ret;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	return (id)[[OFDictionary_hashtable alloc] initWithKey: firstKey
						     arguments: arguments];
}

- initWithSerialization: (OFXMLElement*)element
{
	return (id)[[OFDictionary_hashtable alloc]
	    initWithSerialization: element];
}

- retain
{
	return self;
}

- autorelease
{
	return self;
}

- (void)release
{
}

- (void)dealloc
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
	[super dealloc];	/* Get rid of a stupid warning */
}
@end

@implementation OFDictionary
+ (void)initialize
{
	if (self == [OFDictionary class])
		placeholder.isa = [OFDictionary_placeholder class];
}

+ alloc
{
	if (self == [OFDictionary class])
		return (id)&placeholder;

	return [super alloc];
}

+ dictionary
{
	return [[[self alloc] init] autorelease];
}

+ dictionaryWithDictionary: (OFDictionary*)dictionary
{
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
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
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
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
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587

588
589
590
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

620

621
622

623
624
625
626
627
628
629
630
631
632


633
634

635

636
637

638
639
640
641
642
643
644
645
646
647
648
649
650



651
652


653
654

655
656

657

658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673



674
675


676
677

678
679

680

681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737


738
739
740

741
742

743
744
745
746
747
748
749
	va_end(arguments);

	return ret;
}

- init
{
	self = [super init];

	@try {
		data = [self allocMemoryWithSize:
		    sizeof(struct of_dictionary_bucket)];
		size = 1;
		data[0] = NULL;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys
{
	self = [super init];

	@try {
		uint32_t i;

		if (dictionary == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		data = [self allocMemoryForNItems: dictionary->size
					 withSize: sizeof(*data)];

		for (i = 0; i < dictionary->size; i++)
			data[i] = NULL;

		size = dictionary->size;
		count = dictionary->count;

		for (i = 0; i < size; i++) {
			id key;
			struct of_dictionary_bucket *bucket;

			if (dictionary->data[i] == NULL ||
			    dictionary->data[i] == DELETED)
				continue;

			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
			key = (copyKeys
			    ? [dictionary->data[i]->key copy]
			    : [dictionary->data[i]->key retain]);

			@try {
				[dictionary->data[i]->object retain];
			} @catch (id e) {
				[key release];
				@throw e;
			}

			bucket->key = key;
			bucket->object = dictionary->data[i]->object;
			bucket->hash = dictionary->data[i]->hash;

			data[i] = bucket;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithDictionary: (OFDictionary*)dictionary
{
	return [self _initWithDictionary: dictionary
				copyKeys: YES];
}

- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	self = [super init];

	@try {
		uint32_t i;
		struct of_dictionary_bucket *bucket;

		if (key == nil || object == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		data = [self allocMemoryForNItems: 2
					 withSize: sizeof(*data)];

		size = 2;
		for (i = 0; i < size; i++)
			data[i] = NULL;

		i = [key hash] & 1;
		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

		@try {
			[object retain];
		} @catch (id e) {
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = [key hash];

		data[i] = bucket;
		count = 1;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	self = [super init];

	@try {
		id *objectsCArray, *keysCArray;
		uint32_t i, j, newSize;

		keysCArray = [keys cArray];
		objectsCArray = [objects cArray];
		count = [keys count];

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

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

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

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		for (i = 0; i < count; i++) {
			uint32_t hash, last;

			hash = [keysCArray[i] hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: keysCArray[i]])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key
					    isEqual: keysCArray[i]])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: keysCArray[i]]) {
				struct of_dictionary_bucket *bucket;
				id <OFCopying> key;

				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [keysCArray[i] copy];

				@try {
					[objectsCArray[i] retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = objectsCArray[i];
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[objectsCArray[i] retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[objectsCArray[i] release];
				@throw e;
			}

			data[j]->object = objectsCArray[i];
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list arguments;

	va_start(arguments, firstKey);
	ret = [self initWithKey: firstKey
		      arguments: arguments];
	va_end(arguments);

	return ret;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	self = [super init];

	@try {
		id key, object;
		uint32_t i, j, hash, newSize;
		va_list argumentsCopy;
		struct of_dictionary_bucket *bucket;

		va_copy(argumentsCopy, arguments);

		if (firstKey == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		key = firstKey;

		if ((object = va_arg(arguments, id)) == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		count = 1;
		for (; va_arg(argumentsCopy, id) != nil; count++);
		count >>= 1;

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

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

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

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		/* Add first key / object pair */
		hash = [key hash];
		j = hash & (size - 1);

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

		@try {
			[object retain];
		} @catch (id e) {
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;

		data[j] = bucket;

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

			key = va_arg(arguments, id <OFCopying>);
			object = va_arg(arguments, id);

			if (key == nil || object == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];

			hash = [key hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: key])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key isEqual: key])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: key]) {
				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [key copy];

				@try {
					[object retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = object;
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[object retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[object release];
				@throw e;
			}

			data[j]->object = object;
			count--;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithSerialization: (OFXMLElement*)element
{
	@try {
		OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
		OFAutoreleasePool *pool2;
		OFMutableDictionary *dictionary;
		OFArray *keys, *objects;
		OFEnumerator *keyEnumerator, *objectEnumerator;
		OFXMLElement *keyElement, *objectElement;

		if (![[element name] isEqual: [self className]] ||
		    ![[element namespace] isEqual: OF_SERIALIZATION_NS])
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		dictionary = [OFMutableDictionary dictionary];

		keys = [element elementsForName: @"key"
				      namespace: OF_SERIALIZATION_NS];
		objects = [element elementsForName: @"object"
					 namespace: OF_SERIALIZATION_NS];

		if ([keys count] != [objects count])
			@throw [OFInvalidFormatException newWithClass: isa];

		keyEnumerator = [keys objectEnumerator];
		objectEnumerator = [objects objectEnumerator];
		pool2 = [[OFAutoreleasePool alloc] init];

		while ((keyElement = [keyEnumerator nextObject]) != nil &&
		    (objectElement = [objectEnumerator nextObject]) != nil) {
			OFXMLElement *key, *object;

			key = [[keyElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];
			object = [[objectElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];

			if (key == nil || object == nil)
				@throw [OFInvalidFormatException
				    newWithClass: isa];

			[dictionary setObject: [object objectByDeserializing]
				       forKey: [key objectByDeserializing]];

			[pool2 releaseObjects];
		}

		self = [self initWithDictionary: dictionary];

		[pool release];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- (id)objectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	if (i < last)
		return nil;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	return nil;
}

- (size_t)count
{
	return count;

}

- copy
{
	return [self retain];
}

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

- (BOOL)isEqual: (id)dict
{


	uint32_t i;

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


	for (i = 0; i < size; i++)



		if (data[i] != NULL && data[i] != DELETED &&
		    ![[dict objectForKey: data[i]->key]
		    isEqual: data[i]->object])

			return NO;





	return YES;
}

- (BOOL)containsObject: (id)object
{


	uint32_t i;


	if (count == 0)

		return NO;


	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    [data[i]->object isEqual: object])
			return YES;

	return NO;
}

- (BOOL)containsObjectIdenticalTo: (id)object
{


	uint32_t i;


	if (count == 0)

		return NO;


	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    data[i]->object == object)
			return YES;

	return NO;
}

- (OFArray*)allKeys
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
				       withSize: sizeof(id)];



	size_t i, j;



	for (i = j = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)

			cArray[j++] = data[i]->key;


	assert(j == count);


	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFArray*)allObjects
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
				       withSize: sizeof(id)];



	size_t i, j;



	for (i = j = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)

			cArray[j++] = data[i]->object;


	assert(j == count);


	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator alloc]
	    initWithDictionary: self
			  data: data
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator alloc]
	    initWithDictionary: self
			  data: data
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (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] == NULL ||
		    data[state->state] == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state]->key;
			state->state++;
		} else
			break;
	}

	state->itemsPtr = objects;
	state->mutationsPtr = (unsigned long*)self;

	return i;
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;


	BOOL stop = NO;

	for (i = 0; i < size && !stop; i++)

		if (data[i] != NULL && data[i] != DELETED)
			block(data[i]->key, data[i]->object, &stop);

}

- (OFDictionary*)mappedDictionaryUsingBlock: (of_dictionary_map_block_t)block
{
	OFMutableDictionary *new = [OFMutableDictionary dictionary];

	[self enumerateKeysAndObjectsUsingBlock: ^ (id key, id object,







<
|
<
<
|
|
<
<

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
|
|
<
<

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|




<
<
<
|
<
<
<
<
|
<
<
<
<
<
|
|
|
<
<

<
<
<
|
<
<
<
|
<
<
<
<
<
<
|
<
<
<
|
<
<
<
<
<
<
<
<





<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
|
<
|
<


















<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<




<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
|
<
|
<




<
<
<
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<




|
>












|

>
>
|

|


>
|
>
>
>
|
|
|
>

>
>
>
>






>
>
|

>
|
>
|
|
>
|
<
<
|






>
>
|

>
|
>
|
|
>
|
<
<
|






|
|

>
>
>
|

>
>
|
<
>
|

>
|
>



|









|
|

>
>
>
|

>
>
|
<
>
|

>
|
>



|









<
|
|
<
<




<
|
|
<
<






<
|
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<






|
>
>


|
>
|
<
>







157
158
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








187
188
189
190
191

192










































































































193
194

195

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

214
















































215

















216
217


















































































218
219
220
221







222










































223
224

225

226
227
228
229



230
231



























232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289


290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307


308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325

326
327
328
329
330
331
332
333
334
335
336
337
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
365
366
367
368
369
370
371
372
373
374

375
376


377
378
379
380

381
382


383
384
385
386
387
388

389



390











391
392
393
394
395
396
397
398
399
400
401
402
403
404

405
406
407
408
409
410
411
412
	va_end(arguments);

	return ret;
}

- init
{

	if ([self class] == [OFDictionary class] ||


	    [self class] == [OFMutableDictionary class]) {
		Class c = isa;


		[self release];















		@throw [OFNotImplementedException newWithClass: c
						      selector: _cmd];
	}








































	return [super init];
}

- initWithDictionary: (OFDictionary*)dictionary
{



	Class c = isa;




	[self release];





	@throw [OFNotImplementedException newWithClass: c
					      selector: _cmd];
}






- initWithObject: (id)object



	  forKey: (id <OFCopying>)key






{



	return [self initWithKeysAndObjects: key, object, nil];








}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{

	Class c = isa;










































































































	[self release];
	@throw [OFNotImplementedException newWithClass: c

					      selector: _cmd];

}

- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list arguments;

	va_start(arguments, firstKey);
	ret = [self initWithKey: firstKey
		      arguments: arguments];
	va_end(arguments);

	return ret;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{

	Class c = isa;
















































	[self release];

















	@throw [OFNotImplementedException newWithClass: c
					      selector: _cmd];


















































































}

- initWithSerialization: (OFXMLElement*)element
{







	Class c = isa;










































	[self release];
	@throw [OFNotImplementedException newWithClass: c

					      selector: _cmd];

}

- (id)objectForKey: (id <OFCopying>)key
{



	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];



























}

- (size_t)count
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
}

- copy
{
	return [self retain];
}

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

- (BOOL)isEqual: (id)dictionary
{
	OFAutoreleasePool *pool;
	OFEnumerator *enumerator;
	id <OFCopying> key;

	if ([dictionary count] != [self count])
		return NO;

	pool = [[OFAutoreleasePool alloc] init];

	enumerator = [self keyEnumerator];
	while ((key = [enumerator nextObject]) != nil) {
		id object = [dictionary objectForKey: key];

		if (object == nil ||
		    ![object isEqual: [self objectForKey: key]]) {
			[pool release];
			return NO;
		}
	}

	[pool release];

	return YES;
}

- (BOOL)containsObject: (id)object
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFEnumerator *enumerator = [self objectEnumerator];
	id currentObject;

	while ((currentObject = [enumerator nextObject]) != nil) {
		if ([currentObject isEqual: object]) {
			[pool release];
			return YES;
		}
	}



	[pool release];

	return NO;
}

- (BOOL)containsObjectIdenticalTo: (id)object
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFEnumerator *enumerator = [self objectEnumerator];
	id currentObject;

	while ((currentObject = [enumerator nextObject]) != nil) {
		if (currentObject == object) {
			[pool release];
			return YES;
		}
	}



	[pool release];

	return NO;
}

- (OFArray*)allKeys
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	id *cArray = [self allocMemoryForNItems: [self count]
				       withSize: sizeof(id)];
	OFEnumerator *enumerator;
	id <OFCopying> key;
	OFArray *ret;
	size_t i = 0;

	pool = [[OFAutoreleasePool alloc] init];
	enumerator = [self keyEnumerator];


	while ((key = [enumerator nextObject]) != nil)
		cArray[i++] = key;

	assert(i == [self count]);

	[pool release];

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: [self count]];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFArray*)allObjects
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	id *cArray = [self allocMemoryForNItems: [self count]
				       withSize: sizeof(id)];
	OFEnumerator *enumerator;
	id object;
	OFArray *ret;
	size_t i = 0;

	pool = [[OFAutoreleasePool alloc] init];
	enumerator = [self objectEnumerator];


	while ((object = [enumerator nextObject]) != nil)
		cArray[i++] = object;

	assert(i == [self count]);

	[pool release];

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: [self count]];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFEnumerator*)objectEnumerator
{

	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];


}

- (OFEnumerator*)keyEnumerator
{

	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];


}

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

	@throw [OFNotImplementedException newWithClass: isa



					      selector: _cmd];











}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFEnumerator *enumerator = [self keyEnumerator];
	id <OFCopying> key;
	BOOL stop = NO;

	while (!stop && (key = [enumerator nextObject]) != nil)
		block(key, [self objectForKey: key], &stop);


	[pool release];
}

- (OFDictionary*)mappedDictionaryUsingBlock: (of_dictionary_map_block_t)block
{
	OFMutableDictionary *new = [OFMutableDictionary dictionary];

	[self enumerateKeysAndObjectsUsingBlock: ^ (id key, id object,
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833

	[new makeImmutable];

	return new;
}
#endif

- (void)dealloc
{
	uint32_t i;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != 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] != NULL && data[i] != DELETED) {
			uint32_t h = [data[i]->object hash];

			OF_HASH_ADD(hash, data[i]->hash >> 24);
			OF_HASH_ADD(hash, (data[i]->hash >> 16) & 0xFF);
			OF_HASH_ADD(hash, (data[i]->hash >> 8) & 0xFF);
			OF_HASH_ADD(hash, data[i]->hash & 0xFF);

			OF_HASH_ADD(hash, h >> 24);
			OF_HASH_ADD(hash, (h >> 16) & 0xFF);
			OF_HASH_ADD(hash, (h >> 8) & 0xFF);
			OF_HASH_ADD(hash, h & 0xFF);
		}
	}

	OF_HASH_FINALIZE(hash);

	return hash;
}

- (OFString*)description
{
	OFMutableString *ret;
	OFAutoreleasePool *pool, *pool2;
	OFEnumerator *keyEnumerator, *objectEnumerator;
	id key, object;
	size_t i;

	if (count == 0)
		return @"{()}";

	ret = [OFMutableString stringWithString: @"{\n"];
	pool = [[OFAutoreleasePool alloc] init];
	keyEnumerator = [self keyEnumerator];







<
<
|
|
<
<
|
<
<
<
|
<
<
|
<
<
<
|

<
|
<
<
<
|
<
<
<
<
|
<
<
<
<
|
|
|
<










|







434
435
436
437
438
439
440


441
442


443



444


445



446
447

448



449




450




451
452
453

454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471

	[new makeImmutable];

	return new;
}
#endif



- (uint32_t)hash
{


	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];



	OFEnumerator *enumerator = [self keyEnumerator];


	id <OFCopying> key;



	uint32_t hash = 0;


	while ((key = [enumerator nextObject]) != nil) {



		hash += [key hash];




		hash += [[self objectForKey: key] hash];




	}

	[pool release];


	return hash;
}

- (OFString*)description
{
	OFMutableString *ret;
	OFAutoreleasePool *pool, *pool2;
	OFEnumerator *keyEnumerator, *objectEnumerator;
	id key, object;
	size_t i, count = [self count];

	if (count == 0)
		return @"{()}";

	ret = [OFMutableString stringWithString: @"{\n"];
	pool = [[OFAutoreleasePool alloc] init];
	keyEnumerator = [self keyEnumerator];
862
863
864
865
866
867
868

869
870



871
872
873
874
875
876
877
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFAutoreleasePool *pool2;
	OFXMLElement *element;
	OFEnumerator *keyEnumerator, *objectEnumerator;
	id <OFSerialization> key, object;


	element = [OFXMLElement elementWithName: [self className]
				      namespace: OF_SERIALIZATION_NS];




	keyEnumerator = [self keyEnumerator];
	objectEnumerator = [self objectEnumerator];
	pool2 = [[OFAutoreleasePool alloc] init];

	while ((key = [keyEnumerator nextObject]) != nil &&
	       (object = [objectEnumerator nextObject]) != nil) {







>
|
|
>
>
>







500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFAutoreleasePool *pool2;
	OFXMLElement *element;
	OFEnumerator *keyEnumerator, *objectEnumerator;
	id <OFSerialization> key, object;

	if ([self isKindOfClass: [OFMutableDictionary class]])
		element = [OFXMLElement elementWithName: @"OFMutableDictionary"
					      namespace: OF_SERIALIZATION_NS];
	else
		element = [OFXMLElement elementWithName: @"OFDictionary"
					      namespace: OF_SERIALIZATION_NS];

	keyEnumerator = [self keyEnumerator];
	objectEnumerator = [self objectEnumerator];
	pool2 = [[OFAutoreleasePool alloc] init];

	while ((key = [keyEnumerator nextObject]) != nil &&
	       (object = [objectEnumerator nextObject]) != nil) {
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
		[pool release];
	} @finally {
		[element autorelease];
	}

	return element;
}
@end

@implementation OFDictionaryEnumerator
- initWithDictionary: (OFDictionary*)dictionary_
		data: (struct of_dictionary_bucket**)data_
		size: (uint32_t)size_
    mutationsPointer: (unsigned long*)mutationsPtr_
{
	self = [super init];

	dictionary = [dictionary_ retain];
	data = data_;
	size = size_;
	mutations = (mutationsPtr_ != NULL ? *mutationsPtr_ : 0);
	mutationsPtr = mutationsPtr_;

	return self;
}

- (void)dealloc
{
	[dictionary release];

	[super dealloc];
}

- (void)reset
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	pos = 0;
}
@end

@implementation OFDictionaryObjectEnumerator
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->object;
	else
		return nil;
}
@end

@implementation OFDictionaryKeyEnumerator
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->key;
	else
		return nil;
}
@end








<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
540
541
542
543
544
545
546
547







































































		[pool release];
	} @finally {
		[element autorelease];
	}

	return element;
}
@end







































































Added src/OFDictionary_hashtable.h version [bc1f7945d5].











































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#import "OFDictionary.h"

struct of_dictionary_hashtable_bucket
{
	id <OFCopying> key;
	id object;
	uint32_t hash;
};

@interface OFDictionary_hashtable: OFDictionary
{
	struct of_dictionary_hashtable_bucket **data;
	uint32_t size;
	size_t count;
}

#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M)
- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys;
#endif
@end

@interface OFDictionaryEnumerator_hashtable: OFEnumerator
{
	OFDictionary_hashtable *dictionary;
	struct of_dictionary_hashtable_bucket **data;
	uint32_t size;
	unsigned long mutations;
	unsigned long *mutationsPtr;
	uint32_t pos;
}

- initWithDictionary: (OFDictionary_hashtable*)dictionary
		data: (struct of_dictionary_hashtable_bucket**)data
		size: (uint32_t)size
    mutationsPointer: (unsigned long*)mutationsPtr;
@end

@interface OFDictionaryKeyEnumerator_hashtable: OFDictionaryEnumerator_hashtable
@end

@interface OFDictionaryObjectEnumerator_hashtable:
    OFDictionaryEnumerator_hashtable
@end

#ifdef __cplusplus
extern "C" {
#endif
extern struct of_dictionary_hashtable_bucket
    of_dictionary_hashtable_deleted_bucket;
#ifdef __cplusplus
}
#endif

Added src/OFDictionary_hashtable.m version [2ec4537eb9].





















































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
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
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
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
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
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
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#include <string.h>

#include <assert.h>

#import "OFDictionary_hashtable.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFEnumerator.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFXMLElement.h"
#import "OFAutoreleasePool.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFInvalidFormatException.h"
#import "OFNotImplementedException.h"
#import "OFOutOfRangeException.h"

#import "macros.h"

struct of_dictionary_hashtable_bucket
    of_dictionary_hashtable_deleted_bucket = {};
#define DELETED &of_dictionary_hashtable_deleted_bucket

@implementation OFDictionary_hashtable
- init
{
	self = [super init];

	@try {
		data = [self allocMemoryWithSize: sizeof(*data)];
		size = 1;
		data[0] = NULL;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys
{
	self = [super init];

	@try {
		uint32_t i;
		OFDictionary_hashtable *hashtable;

		if (dictionary == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		if (![dictionary isKindOfClass:
		    [OFDictionary_hashtable class]] &&
		    ![dictionary isKindOfClass:
		    [OFMutableDictionary_hashtable class]])
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		hashtable = (OFDictionary_hashtable*)dictionary;

		data = [self allocMemoryForNItems: hashtable->size
					 withSize: sizeof(*data)];

		for (i = 0; i < hashtable->size; i++)
			data[i] = NULL;

		size = hashtable->size;
		count = hashtable->count;

		for (i = 0; i < size; i++) {
			id key;
			struct of_dictionary_hashtable_bucket *bucket;

			if (hashtable->data[i] == NULL ||
			    hashtable->data[i] == DELETED)
				continue;

			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
			key = (copyKeys
			    ? [hashtable->data[i]->key copy]
			    : [hashtable->data[i]->key retain]);

			@try {
				[hashtable->data[i]->object retain];
			} @catch (id e) {
				[key release];
				@throw e;
			}

			bucket->key = key;
			bucket->object = hashtable->data[i]->object;
			bucket->hash = hashtable->data[i]->hash;

			data[i] = bucket;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithDictionary: (OFDictionary*)dictionary
{
	self = [super init];

	@try {
		OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
		OFEnumerator *enumerator;
		id <OFCopying> key;
		uint32_t i, newSize;

		count = [dictionary count];

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

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

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

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (i = 0; i < newSize; i++)
			data[i] = NULL;

		size = newSize;

		pool = [[OFAutoreleasePool alloc] init];
		enumerator = [dictionary keyEnumerator];

		while ((key = [enumerator nextObject]) != nil) {
			uint32_t hash, last;
			struct of_dictionary_hashtable_bucket *bucket;
			id object;

			hash = [key hash];
			last = size;

			for (i = hash & (size - 1); i < last && data[i] != NULL;
			    i++);

			/* In case the last bucket is already used */
			if (i >= last) {
				last = hash & (size - 1);

				for (i = 0; i < last && data[i] != NULL; i++);
			}

			if (data[i] != NULL)
				@throw [OFOutOfRangeException
				    newWithClass: isa];

			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
			key = [key copy];

			@try {
				object = [dictionary objectForKey: key];
				[object retain];
			} @catch (id e) {
				[key release];
				@throw e;
			}

			bucket->key = key;
			bucket->object = object;
			bucket->hash = hash;

			data[i] = bucket;
		}

		[pool release];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	self = [super init];

	@try {
		uint32_t i;
		struct of_dictionary_hashtable_bucket *bucket;

		if (key == nil || object == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		data = [self allocMemoryForNItems: 2
					 withSize: sizeof(*data)];

		size = 2;
		for (i = 0; i < size; i++)
			data[i] = NULL;

		i = [key hash] & 1;
		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

		@try {
			[object retain];
		} @catch (id e) {
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = [key hash];

		data[i] = bucket;
		count = 1;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	self = [super init];

	@try {
		id *objectsCArray, *keysCArray;
		uint32_t i, j, newSize;

		keysCArray = [keys cArray];
		objectsCArray = [objects cArray];
		count = [keys count];

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

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

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

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		for (i = 0; i < count; i++) {
			uint32_t hash, last;

			hash = [keysCArray[i] hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: keysCArray[i]])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key
					    isEqual: keysCArray[i]])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: keysCArray[i]]) {
				struct of_dictionary_hashtable_bucket *bucket;
				id <OFCopying> key;

				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [keysCArray[i] copy];

				@try {
					[objectsCArray[i] retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = objectsCArray[i];
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[objectsCArray[i] retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[objectsCArray[i] release];
				@throw e;
			}

			data[j]->object = objectsCArray[i];
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	self = [super init];

	@try {
		id key, object;
		uint32_t i, j, hash, newSize;
		va_list argumentsCopy;
		struct of_dictionary_hashtable_bucket *bucket;

		va_copy(argumentsCopy, arguments);

		if (firstKey == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		key = firstKey;

		if ((object = va_arg(arguments, id)) == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		count = 1;
		for (; va_arg(argumentsCopy, id) != nil; count++);
		count >>= 1;

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

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

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

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		/* Add first key / object pair */
		hash = [key hash];
		j = hash & (size - 1);

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

		@try {
			[object retain];
		} @catch (id e) {
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;

		data[j] = bucket;

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

			key = va_arg(arguments, id <OFCopying>);
			object = va_arg(arguments, id);

			if (key == nil || object == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];

			hash = [key hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: key])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key isEqual: key])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: key]) {
				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [key copy];

				@try {
					[object retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = object;
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[object retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[object release];
				@throw e;
			}

			data[j]->object = object;
			count--;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithSerialization: (OFXMLElement*)element
{
	@try {
		OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
		OFAutoreleasePool *pool2;
		OFMutableDictionary *dictionary;
		OFArray *keys, *objects;
		OFEnumerator *keyEnumerator, *objectEnumerator;
		OFXMLElement *keyElement, *objectElement;

		if ((![[element name] isEqual: @"OFDictionary"] &&
		    ![[element name] isEqual: @"OFMutableDictionary"]) ||
		    ![[element namespace] isEqual: OF_SERIALIZATION_NS])
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		dictionary = [OFMutableDictionary dictionary];

		keys = [element elementsForName: @"key"
				      namespace: OF_SERIALIZATION_NS];
		objects = [element elementsForName: @"object"
					 namespace: OF_SERIALIZATION_NS];

		if ([keys count] != [objects count])
			@throw [OFInvalidFormatException newWithClass: isa];

		keyEnumerator = [keys objectEnumerator];
		objectEnumerator = [objects objectEnumerator];
		pool2 = [[OFAutoreleasePool alloc] init];

		while ((keyElement = [keyEnumerator nextObject]) != nil &&
		    (objectElement = [objectEnumerator nextObject]) != nil) {
			OFXMLElement *key, *object;

			key = [[keyElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];
			object = [[objectElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];

			if (key == nil || object == nil)
				@throw [OFInvalidFormatException
				    newWithClass: isa];

			[dictionary setObject: [object objectByDeserializing]
				       forKey: [key objectByDeserializing]];

			[pool2 releaseObjects];
		}

		self = [self initWithDictionary: dictionary];

		[pool release];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- (id)objectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	if (i < last)
		return nil;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	return nil;
}

- (size_t)count
{
	return count;
}

- (BOOL)isEqual: (id)dictionary
{
	uint32_t i;

	if ([self class] != [OFDictionary_hashtable class] &&
	    [self class] != [OFMutableDictionary_hashtable class])
		return [super isEqual: dictionary];

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

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    ![[dictionary objectForKey: data[i]->key]
		    isEqual: data[i]->object])
			return NO;

	return YES;
}

- (BOOL)containsObject: (id)object
{
	uint32_t i;

	if (count == 0)
		return NO;

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    [data[i]->object isEqual: object])
			return YES;

	return NO;
}

- (BOOL)containsObjectIdenticalTo: (id)object
{
	uint32_t i;

	if (count == 0)
		return NO;

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    data[i]->object == object)
			return YES;

	return NO;
}

- (OFArray*)allKeys
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
				       withSize: sizeof(id)];
	size_t i, j;

	for (i = j = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)
			cArray[j++] = data[i]->key;

	assert(j == count);

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFArray*)allObjects
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
				       withSize: sizeof(id)];
	size_t i, j;

	for (i = j = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)
			cArray[j++] = data[i]->object;

	assert(j == count);

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator_hashtable alloc]
	    initWithDictionary: self
			  data: data
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator_hashtable alloc]
	    initWithDictionary: self
			  data: data
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (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] == NULL ||
		    data[state->state] == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state]->key;
			state->state++;
		} else
			break;
	}

	state->itemsPtr = objects;
	state->mutationsPtr = (unsigned long*)self;

	return i;
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;
	BOOL stop = NO;

	for (i = 0; i < size && !stop; i++)
		if (data[i] != NULL && data[i] != DELETED)
			block(data[i]->key, data[i]->object, &stop);
}
#endif

- (void)dealloc
{
	uint32_t i;

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

	[super dealloc];
}

- (uint32_t)hash
{
	uint32_t i, hash = 0;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			hash += data[i]->hash;
			hash += [data[i]->object hash];
		}
	}

	return hash;
}
@end

@implementation OFDictionaryEnumerator_hashtable
- initWithDictionary: (OFDictionary_hashtable*)dictionary_
		data: (struct of_dictionary_hashtable_bucket**)data_
		size: (uint32_t)size_
    mutationsPointer: (unsigned long*)mutationsPtr_
{
	self = [super init];

	dictionary = [dictionary_ retain];
	data = data_;
	size = size_;
	mutations = (mutationsPtr_ != NULL ? *mutationsPtr_ : 0);
	mutationsPtr = mutationsPtr_;

	return self;
}

- (void)dealloc
{
	[dictionary release];

	[super dealloc];
}

- (void)reset
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	pos = 0;
}
@end

@implementation OFDictionaryObjectEnumerator_hashtable
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->object;
	else
		return nil;
}
@end

@implementation OFDictionaryKeyEnumerator_hashtable
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->key;
	else
		return nil;
}
@end

Modified src/OFMutableDictionary.h from [29972e06f6] to [0667a7eb0a].

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#import "OFDictionary.h"

#ifdef OF_HAVE_BLOCKS
typedef id (^of_dictionary_replace_block_t)(id key, id object, BOOL *stop);
#endif

/**
 * \brief A class for using mutable hash tables.
 */
@interface OFMutableDictionary: OFDictionary
{
	unsigned long mutations;
}

/**
 * \brief Sets an object for a key.
 *
 * A key can be any object that conforms to the OFCopying protocol.
 *
 * \param key The key to set
 * \param object The object to set the key to







|


<
<
<
<







17
18
19
20
21
22
23
24
25
26




27
28
29
30
31
32
33
#import "OFDictionary.h"

#ifdef OF_HAVE_BLOCKS
typedef id (^of_dictionary_replace_block_t)(id key, id object, BOOL *stop);
#endif

/**
 * \brief An abstract class for using mutable dictionaries.
 */
@interface OFMutableDictionary: OFDictionary




/**
 * \brief Sets an object for a key.
 *
 * A key can be any object that conforms to the OFCopying protocol.
 *
 * \param key The key to set
 * \param object The object to set the key to
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68



 * \brief Replaces each object with the object returned by the block.
 *
 * \param block The block which returns a new object for each object
 */
- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block;
#endif

#if defined(OF_SET_M) || defined(OF_MUTABLE_SET_M) || defined(OF_COUNTED_SET_M)
- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey;
#endif

/**
 * \brief Converts the mutable dictionary to an immutable dictionary.
 */
- (void)makeImmutable;
@end










<
<
<
<
<
<





>
>
>
47
48
49
50
51
52
53






54
55
56
57
58
59
60
61
 * \brief Replaces each object with the object returned by the block.
 *
 * \param block The block which returns a new object for each object
 */
- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block;
#endif







/**
 * \brief Converts the mutable dictionary to an immutable dictionary.
 */
- (void)makeImmutable;
@end

@interface OFMutableDictionary_placeholder: OFDictionary
@end

Modified src/OFMutableDictionary.m from [6cae7254e5] to [0c649f32e0].

12
13
14
15
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"



#include <string.h>








#import "OFMutableDictionary.h"




#import "OFAutoreleasePool.h"





#import "OFEnumerationMutationException.h"






#import "OFInvalidArgumentException.h"







#import "OFOutOfRangeException.h"




#import "macros.h"








#define DELETED &of_dictionary_deleted_bucket




































@implementation OFMutableDictionary
- (void)_resizeForCount: (size_t)newCount
{
	size_t fullness = newCount * 4 / size;
	struct of_dictionary_bucket **newData;
	uint32_t i, newSize;

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

	if (fullness >= 3)
		newSize = size << 1;
	else if (fullness <= 1)
		newSize = size >> 1;
	else
		return;

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

	newData = [self allocMemoryForNItems: newSize
				    withSize: sizeof(*newData)];

	for (i = 0; i < newSize; i++)
		newData[i] = NULL;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			uint32_t j, last;

			last = newSize;

			j = data[i]->hash & (newSize - 1);
			for (; j < last && newData[j] != NULL; j++);

			/* In case the last bucket is already used */
			if (j >= last) {
				last = data[i]->hash & (newSize - 1);

				for (j = 0; j < last &&
				    newData[j] != NULL; j++);
			}

			if (j >= last) {
				[self freeMemory: newData];
				@throw [OFOutOfRangeException
				    newWithClass: isa];
			}

			newData[j] = data[i];
		}
	}

	[self freeMemory: data];
	data = newData;
	size = newSize;
}

- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey
{
	uint32_t i, hash, last;
	id old;

	if (key == nil || object == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			break;
	}

	/* In case the last bucket is already used */
	if (i >= last) {
		last = hash & (size - 1);

		for (i = 0; i < last && data[i] != NULL; i++) {
			if (data[i] == DELETED)
				continue;

			if ([data[i]->key isEqual: key])
				break;
		}
	}

	/* Key not in dictionary */
	if (i >= last || data[i] == NULL || data[i] == DELETED ||
	    ![data[i]->key isEqual: key]) {
		struct of_dictionary_bucket *bucket;

		[self _resizeForCount: count + 1];

		mutations++;
		last = size;

		for (i = hash & (size - 1); i < last && data[i] != NULL &&
		    data[i] != DELETED; i++);

		/* In case the last bucket is already used */
		if (i >= last) {
			last = hash & (size - 1);

			for (i = 0; i < last && data[i] != NULL &&
			    data[i] != DELETED; i++);
		}

		if (i >= last)
			@throw [OFOutOfRangeException newWithClass: isa];

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];

		@try {
			key = (copyKey ? [key copy] : [key retain]);
		} @catch (id e) {
			[self freeMemory: bucket];
			@throw e;
		}

		@try {
			[object retain];
		} @catch (id e) {
			[self freeMemory: bucket];
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;
		data[i] = bucket;
		count++;

		return;
	}

	old = data[i]->object;
	data[i]->object = [object retain];
	[old release];
}

- (void)setObject: (id)object
	   forKey: (id <OFCopying>)key
{
	[self _setObject: object
		  forKey: key
		 copyKey: YES];
}

- (void)removeObjectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}

	if (i < last)
		return;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}
}

- copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	int ret = [super countByEnumeratingWithState: state
					     objects: objects
					       count: count_];

	state->mutationsPtr = &mutations;

	return ret;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator alloc]
	    initWithDictionary: self
			 data: data
			 size: size
	     mutationsPointer: &mutations] autorelease];
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator alloc]
	    initWithDictionary: self
			 data: data
			 size: size
	     mutationsPointer: &mutations] autorelease];
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

		if (data[i] != NULL && data[i] != DELETED)
			block(data[i]->key, data[i]->object, &stop);
	}
}

- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

		if (data[i] != NULL && data[i] != DELETED) {
			id new = block(data[i]->key, data[i]->object, &stop);

			if (new == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];

			[new retain];
			[data[i]->object release];
			data[i]->object = new;
		}
	}
}
#endif

- (void)makeImmutable
{
	isa = [OFDictionary class];
}
@end







>
>
|
>

>
>
>
>
>
>
|
>
>
>
>
|
>
|
>
>
>
|
>
>
>
>
>
>
|
>
>
>
>
>
>
>
|
>
|
>
>
|
>
>
>
>
>

>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


<
<
<
<
<
|
<
<
|
<
<
<
<
<
<
|
<
<
|
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<

<
<
<
|
<
<
<
|
<
<
<
|
<
<
<
<
|
<
<
<
<

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<





|
|
<




<
<
<
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<


<
<
<
|
<
<
<
<
<
|
<
<
|
<
<
<
<
|
<
<
<
|
<





<


12
13
14
15
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107





108


109






110


111


112




















































113



114



115



116




117




118










































119





120
121
122
123
124
125
126

127
128
129
130



131
132













































133
134
135
136
137
138
139































140


















141
142



143





144


145




146



147

148
149
150
151
152

153
154
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#import "OFMutableDictionary_hashtable.h"
#import "OFAutoreleasePool.h"

#import "OFNotImplementedException.h"

#import "macros.h"

static struct {
	Class isa;
} placeholder;

@implementation OFMutableDictionary_placeholder
- init
{
	return (id)[[OFMutableDictionary_hashtable alloc] init];
}

- initWithDictionary: (OFDictionary*)dictionary
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithDictionary: dictionary];
}

- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	return (id)[[OFMutableDictionary_hashtable alloc] initWithObject: object
								  forKey: key];
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithObjects: objects
		    forKeys: keys];
}

- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list arguments;

	va_start(arguments, firstKey);
	ret = (id)[[OFMutableDictionary_hashtable alloc]
	    initWithKey: firstKey
	      arguments: arguments];
	va_end(arguments);

	return ret;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithKey: firstKey
	      arguments: arguments];
}

- initWithSerialization: (OFXMLElement*)element
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithSerialization: element];
}

- retain
{
	return self;
}

- autorelease
{
	return self;
}

- (void)release
{
}

- (void)dealloc
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
	[super dealloc];	/* Get rid of a stupid warning */
}
@end

@implementation OFMutableDictionary





+ (void)initialize


{






	if (self == [OFMutableDictionary class])


		placeholder.isa = [OFMutableDictionary_placeholder class];


}
























































+ alloc



{



	if (self == [OFMutableDictionary class])




		return (id)&placeholder;















































	return [super alloc];





}

- (void)setObject: (id)object
	   forKey: (id <OFCopying>)key
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];

}

- (void)removeObjectForKey: (id <OFCopying>)key
{



	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];













































}

- copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
}
































#ifdef OF_HAVE_BLOCKS


















- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block
{



	[self enumerateKeysAndObjectsUsingBlock: ^ (id key, id object,





	    BOOL *stop) {


		[self setObject: block(key, object, stop)




			 forKey: key];



	}];

}
#endif

- (void)makeImmutable
{

}
@end

Added src/OFMutableDictionary_hashtable.h version [459e55ec05].











































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#import "OFDictionary.h"

@interface OFMutableDictionary_hashtable: OFMutableDictionary
{
	struct of_dictionary_hashtable_bucket **data;
	uint32_t size;
	size_t count;
	unsigned long mutations;
}

#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M)
- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys;
#endif

#if defined(OF_SET_M) || defined(OF_MUTABLE_SET_M) || defined(OF_COUNTED_SET_M)
- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey;
#endif
@end

Added src/OFMutableDictionary_hashtable.m version [c6660be1ea].







































































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#include <string.h>

#import "OFMutableDictionary_hashtable.h"
#import "OFDictionary_hashtable.h"
#import "OFAutoreleasePool.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFOutOfRangeException.h"

#import "macros.h"

#define DELETED &of_dictionary_hashtable_deleted_bucket

static Class dictionary = Nil;

@implementation OFMutableDictionary_hashtable
+ (void)initialize
{
	if (self == [OFMutableDictionary_hashtable class]) {
		dictionary = [OFDictionary_hashtable class];
		[self inheritMethodsFromClass: dictionary];
	}
}

- (void)_resizeForCount: (size_t)newCount
{
	size_t fullness = newCount * 4 / size;
	struct of_dictionary_hashtable_bucket **newData;
	uint32_t i, newSize;

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

	if (fullness >= 3)
		newSize = size << 1;
	else if (fullness <= 1)
		newSize = size >> 1;
	else
		return;

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

	newData = [self allocMemoryForNItems: newSize
				    withSize: sizeof(*newData)];

	for (i = 0; i < newSize; i++)
		newData[i] = NULL;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			uint32_t j, last;

			last = newSize;

			j = data[i]->hash & (newSize - 1);
			for (; j < last && newData[j] != NULL; j++);

			/* In case the last bucket is already used */
			if (j >= last) {
				last = data[i]->hash & (newSize - 1);

				for (j = 0; j < last &&
				    newData[j] != NULL; j++);
			}

			if (j >= last) {
				[self freeMemory: newData];
				@throw [OFOutOfRangeException
				    newWithClass: isa];
			}

			newData[j] = data[i];
		}
	}

	[self freeMemory: data];
	data = newData;
	size = newSize;
}

- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey
{
	uint32_t i, hash, last;
	id old;

	if (key == nil || object == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			break;
	}

	/* In case the last bucket is already used */
	if (i >= last) {
		last = hash & (size - 1);

		for (i = 0; i < last && data[i] != NULL; i++) {
			if (data[i] == DELETED)
				continue;

			if ([data[i]->key isEqual: key])
				break;
		}
	}

	/* Key not in dictionary */
	if (i >= last || data[i] == NULL || data[i] == DELETED ||
	    ![data[i]->key isEqual: key]) {
		struct of_dictionary_hashtable_bucket *bucket;

		[self _resizeForCount: count + 1];

		mutations++;
		last = size;

		for (i = hash & (size - 1); i < last && data[i] != NULL &&
		    data[i] != DELETED; i++);

		/* In case the last bucket is already used */
		if (i >= last) {
			last = hash & (size - 1);

			for (i = 0; i < last && data[i] != NULL &&
			    data[i] != DELETED; i++);
		}

		if (i >= last)
			@throw [OFOutOfRangeException newWithClass: isa];

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];

		@try {
			key = (copyKey ? [key copy] : [key retain]);
		} @catch (id e) {
			[self freeMemory: bucket];
			@throw e;
		}

		@try {
			[object retain];
		} @catch (id e) {
			[self freeMemory: bucket];
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;
		data[i] = bucket;
		count++;

		return;
	}

	old = data[i]->object;
	data[i]->object = [object retain];
	[old release];
}

- (void)setObject: (id)object
	   forKey: (id <OFCopying>)key
{
	[self _setObject: object
		  forKey: key
		 copyKey: YES];
}

- (void)removeObjectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}

	if (i < last)
		return;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	const SEL selector =
	    @selector(countByEnumeratingWithState:objects:count:);
	int (*imp)(id, SEL, of_fast_enumeration_state_t*, id*, int) =
	    (int(*)(id, SEL, of_fast_enumeration_state_t*, id*, int))
	    [dictionary instanceMethodForSelector: selector];

	int ret = imp(self, selector, state, objects, count_);

	state->mutationsPtr = &mutations;

	return ret;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator_hashtable alloc]
	    initWithDictionary: (OFDictionary_hashtable*)self
			  data: data
			  size: size
	      mutationsPointer: &mutations] autorelease];
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator_hashtable alloc]
	    initWithDictionary: (OFDictionary_hashtable*)self
			  data: data
			  size: size
	      mutationsPointer: &mutations] autorelease];
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

		if (data[i] != NULL && data[i] != DELETED)
			block(data[i]->key, data[i]->object, &stop);
	}
}

- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

		if (data[i] != NULL && data[i] != DELETED) {
			id new = block(data[i]->key, data[i]->object, &stop);

			if (new == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];

			[new retain];
			[data[i]->object release];
			data[i]->object = new;
		}
	}
}
#endif

- (void)makeImmutable
{
	isa = [OFDictionary_hashtable class];
}
@end

Modified src/OFMutableSet.m from [54d40938db] to [27d68fc0e7].

15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 */

#include "config.h"

#define OF_MUTABLE_SET_M

#import "OFMutableSet.h"
#import "OFDictionary.h"
#import "OFArray.h"
#import "OFNumber.h"
#import "OFAutoreleasePool.h"

@implementation OFMutableSet
- (void)addObject: (id)object
{







|







15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 */

#include "config.h"

#define OF_MUTABLE_SET_M

#import "OFMutableSet.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFArray.h"
#import "OFNumber.h"
#import "OFAutoreleasePool.h"

@implementation OFMutableSet
- (void)addObject: (id)object
{

Modified src/OFSet.h from [d4e9745629] to [ed184131ea].

15
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
 */

#include <stdarg.h>

#import "OFObject.h"
#import "OFCollection.h"

@class OFMutableDictionary;
@class OFArray;

#ifdef OF_HAVE_BLOCKS
typedef void (^of_set_enumeration_block_t)(id object, BOOL *stop);
typedef BOOL (^of_set_filter_block_t)(id object);
#endif

/**
 * \brief An unordered set of unique objects.
 */
@interface OFSet: OFObject <OFCollection, OFCopying, OFMutableCopying>
{
	OFMutableDictionary *dictionary;
}

/**
 * \brief Returns a new, autoreleased set.
 *
 * \return A new, autoreleased set
 */







|












|







15
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
 */

#include <stdarg.h>

#import "OFObject.h"
#import "OFCollection.h"

@class OFMutableDictionary_hashtable;
@class OFArray;

#ifdef OF_HAVE_BLOCKS
typedef void (^of_set_enumeration_block_t)(id object, BOOL *stop);
typedef BOOL (^of_set_filter_block_t)(id object);
#endif

/**
 * \brief An unordered set of unique objects.
 */
@interface OFSet: OFObject <OFCollection, OFCopying, OFMutableCopying>
{
	OFMutableDictionary_hashtable *dictionary;
}

/**
 * \brief Returns a new, autoreleased set.
 *
 * \return A new, autoreleased set
 */

Modified src/OFSet.m from [ac40594a2c] to [69cf3066e2].

15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 */

#include "config.h"

#define OF_SET_M

#import "OFSet.h"
#import "OFDictionary.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFNumber.h"
#import "OFAutoreleasePool.h"

@implementation OFSet
+ set







|







15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 */

#include "config.h"

#define OF_SET_M

#import "OFSet.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFNumber.h"
#import "OFAutoreleasePool.h"

@implementation OFSet
+ set
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
}

- init
{
	self = [super init];

	@try {
		dictionary = [[OFMutableDictionary alloc] init];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}







|







55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
}

- init
{
	self = [super init];

	@try {
		dictionary = [[OFMutableDictionary_hashtable alloc] init];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

Modified tests/serialization.xml from [e609429c3c] to [50caace6dd].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?xml version='1.0' encoding='UTF-8'?>
<serialization xmlns='https://webkeks.org/objfw/serialization' version='0'>
  <OFMutableDictionary>
    <key>
      <OFArray>
        <OFString>Qu&quot;xbar
test</OFString>
        <OFNumber type='signed'>1234</OFNumber>
        <OFMutableString>asd</OFMutableString>
        <OFDate seconds='1234' microseconds='5678'/>
      </OFArray>
    </key>
    <object>
      <OFString>Hello</OFString>
    </object>
    <key>
      <OFList>
        <OFString>Hello</OFString>
        <OFString>Wo&#xD;ld!
How are you?</OFString>
        <OFURL>https://webkeks.org/</OFURL>
        <OFXMLElement name='x'>
          <namespaces>




<
<
<
<
<
<
<
<
<
<
<
<







1
2
3
4












5
6
7
8
9
10
11
<?xml version='1.0' encoding='UTF-8'?>
<serialization xmlns='https://webkeks.org/objfw/serialization' version='0'>
  <OFMutableDictionary>
    <key>












      <OFList>
        <OFString>Hello</OFString>
        <OFString>Wo&#xD;ld!
How are you?</OFString>
        <OFURL>https://webkeks.org/</OFURL>
        <OFXMLElement name='x'>
          <namespaces>
63
64
65
66
67
68
69












70
71
72
73
74
75
76
          </children>
        </OFXMLElement>
      </OFList>
    </key>
    <object>
      <OFString>list</OFString>
    </object>












    <key>
      <OFString>Blub</OFString>
    </key>
    <object>
      <OFString>B&quot;la</OFString>
    </object>
    <key>







>
>
>
>
>
>
>
>
>
>
>
>







51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
          </children>
        </OFXMLElement>
      </OFList>
    </key>
    <object>
      <OFString>list</OFString>
    </object>
    <key>
      <OFArray>
        <OFString>Qu&quot;xbar
test</OFString>
        <OFNumber type='signed'>1234</OFNumber>
        <OFMutableString>asd</OFMutableString>
        <OFDate seconds='1234' microseconds='5678'/>
      </OFArray>
    </key>
    <object>
      <OFString>Hello</OFString>
    </object>
    <key>
      <OFString>Blub</OFString>
    </key>
    <object>
      <OFString>B&quot;la</OFString>
    </object>
    <key>