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
|
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 fill = newcount * 4 / size;
size_t newsize;
struct of_dictionary_bucket *newdata;
uint32_t i;
if (count > SIZE_MAX / 4)
if (newcount > SIZE_MAX / 4)
@throw [OFOutOfRangeException newWithClass: isa];
if (fill >= 3)
newsize = *size << 1;
newsize = size << 1;
else if (fill <= 1)
newsize = *size >> 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) {
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);
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);
last = data[i].hash & (newsize - 1);
for (j = 0; j < last &&
newdata[j].key != nil; i++);
}
if (j >= last)
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;
}
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;
[self freeMemory: data];
data = newdata;
size = newsize;
}
@implementation OFMutableDictionary
|
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
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);
[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
|
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);
[self _resizeForCount: count];
return self;
}
- (id)copy
{
return [[OFDictionary alloc] initWithDictionary: self];
|