ObjFW  Check-in [e870ea71ac]

Overview
Comment:Make resizing a private method instead of inlining.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: e870ea71ac878563a9b70e3a22d9dd164137fc9897c3434df0cd0e1eaf2ba7c0
User & Date: js on 2010-04-17 10:35:04
Other Links: manifest | tags
Context
2010-04-17
10:48
Due to a 32 bit hash, a dictionary can never be bigger than UINT32_MAX. check-in: b9015dbc75 user: js tags: trunk
10:35
Make resizing a private method instead of inlining. check-in: e870ea71ac user: js tags: trunk
2010-04-15
17:19
Win32 version of OFFile's +[filesInDirectoryAtPath:]. check-in: c4f5d6f491 user: js tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified src/OFMutableDictionary.m from [d4b94495f4] to [f91e7929a8].

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

#import "OFMutableDictionary.h"
#import "OFExceptions.h"
#import "macros.h"

#define BUCKET_SIZE sizeof(struct of_dictionary_bucket)
#define DELETED (id)&of_dictionary_deleted_bucket

static OF_INLINE void
resize(id self, Class isa, size_t count, struct of_dictionary_bucket **data,
    size_t *size)
{
	size_t fill = count * 4 / *size;
	size_t newsize;
	struct of_dictionary_bucket *newdata;
	uint32_t i;

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

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

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

	newdata = [self allocMemoryForNItems: newsize
				    withSize: BUCKET_SIZE];
	memset(newdata, 0, newsize * BUCKET_SIZE);

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

			last = newsize;

			j = (*data)[i].hash & (newsize - 1);
			for (; j < last && newdata[j].key != nil; 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].key != nil; i++);
			}

			if (j >= last)

				@throw [OFOutOfRangeException
				    newWithClass: [self class]];


			newdata[j].key = (*data)[i].key;
			newdata[j].object = (*data)[i].object;
			newdata[j].hash = (*data)[i].hash;
		}
	}

	[self freeMemory: *data];
	*data = newdata;
	*size = newsize;
}

@implementation OFMutableDictionary
- setObject: (OFObject*)obj
     forKey: (OFObject <OFCopying>*)key
{
	uint32_t i, hash, last;

	if (key == nil || obj == nil)
		@throw [OFInvalidArgumentException newWithClass: isa








|
<
|

|




|



|

|










|
|




|




|





|
>


|
>
|
|
|



|
|
|


<








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

#import "OFMutableDictionary.h"
#import "OFExceptions.h"
#import "macros.h"

#define BUCKET_SIZE sizeof(struct of_dictionary_bucket)
#define DELETED (id)&of_dictionary_deleted_bucket

@implementation OFMutableDictionary

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

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

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

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

	newdata = [self allocMemoryForNItems: newsize
				    withSize: BUCKET_SIZE];
	memset(newdata, 0, newsize * BUCKET_SIZE);

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

			last = newsize;

			j = data[i].hash & (newsize - 1);
			for (; j < last && newdata[j].key != nil; 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].key != nil; i++);
			}

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

			newdata[j].key = data[i].key;
			newdata[j].object = data[i].object;
			newdata[j].hash = data[i].hash;
		}
	}

	[self freeMemory: data];
	data = newdata;
	size = newsize;
}


- setObject: (OFObject*)obj
     forKey: (OFObject <OFCopying>*)key
{
	uint32_t i, hash, last;

	if (key == nil || obj == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
︙︙
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

		    (data[i].key == DELETED || ![data[i].key isEqual: key]);
		    i++);
	}

	/* Key not in dictionary */
	if (i >= last || data[i].key == nil || data[i].key == DELETED ||
	    ![data[i].key isEqual: key]) {
		resize(self, isa, count + 1, &data, &size);

		mutations++;
		last = size;

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









|








102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

		    (data[i].key == DELETED || ![data[i].key isEqual: key]);
		    i++);
	}

	/* Key not in dictionary */
	if (i >= last || data[i].key == nil || data[i].key == DELETED ||
	    ![data[i].key isEqual: key]) {
		[self _resizeForCount: count + 1];

		mutations++;
		last = size;

		for (i = hash & (size - 1); i < last && data[i].key != nil &&
		    data[i].key != DELETED; i++);
︙︙
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196


	[data[i].key release];
	[data[i].object release];
	data[i].key = DELETED;

	count--;
	mutations++;
	resize(self, isa, count, &data, &size);

	return self;
}

- (id)copy
{
	return [[OFDictionary alloc] initWithDictionary: self];








|








182
183
184
185
186
187
188
189
190
191
192
193
194
195
196


	[data[i].key release];
	[data[i].object release];
	data[i].key = DELETED;

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

	return self;
}

- (id)copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
︙︙

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