ObjFW  Diff

Annotate Patch Side-by-side Diff

Differences From Artifact [48a81d9fea]:

To Artifact [436bcef63e]:

  • File src/OFMutableDictionary.m — part of check-in [bbf1f79b8f] at 2009-09-08 16:06:10 on branch trunk — New OFDictionary implementation and removal of a hack in OFList.

    The new implementation is easier to use as it does automatic resizing,
    but therefore it's not realtime-capable anymore. The new implementation
    should also be a little bit faster.

    I decided to change the implementation as only very few need a
    realtime-capable dictionary and those few will most likely write their
    own implementation for their specific case anyway.

    As the new implementation no longer uses OFList, this also made it
    possible to remove a hack from OFList. (user: js, size: 3431) [annotate] [blame] [check-ins using]

︙
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

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









+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+




-
+
-





-
+
-

-
-
+
+
-

+
+
-
+
-
-
+
-
-
-

-
-
-
+
+
+
+
+
+
+
+
+
+
+
+

-
+
+
+
+

-
+
-
-
+
-
-
-
-
-
-
-
+
+
+
+






-
+
-





-
+

-
-
-
+
-
-
-
+
-
-

-
-
-
-
-
+
-
-
-
-
+
-
-
-
+
-
-
-
-
-
-
+
-
-
-

-
-
-
-
-
+
-
-
+
-
-
+
-
-
-
-

-
+
-
-
-
-
+
-
-
-
+
-
-
-
+
+
-
-
-
+
-
-
-










#include "config.h"

#include <string.h>

#import "OFMutableDictionary.h"
#import "OFExceptions.h"
#import "OFMacros.h"

#define BUCKET_SIZE sizeof(struct of_dictionary_bucket)

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

	/*
	 * FIXME:
	 *
	 * Throw an OFOutOfRangeException if it would overflow (unlikely to
	 * happen).
	 */
	if (fill > 0.75)
		newsize = *size * 2;
	else if (fill < 0.25)
		newsize = *size / 2;
	else
		return;

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

	for (i = 0; i < *size; i++) {
		if ((*data)[i].key != nil) {
			uint32_t j = (*data)[i].hash & (newsize - 1);
			for (; j < newsize && newdata[j].key != nil; j++);

			/* In case the last bucket is already used */
			if (j >= newsize)
				for (j = 0; j < newsize &&
				    newdata[j].key != nil; i++);
			if (j >= newsize)
				@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 fullhash, hash;
	uint32_t i, hash;
	of_dictionary_list_object_t *iter;

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

	fullhash = [key hash];
	hash = [key hash];
	hash = fullhash & (size - 1);

	if (data[hash] == nil)
		data[hash] = [[OFList alloc] initWithListObjectSize:
	for (i = hash & (size - 1); i < size && data[i].key != nil &&
	    ![data[i].key isEqual: key]; i++);
		    sizeof(of_dictionary_list_object_t)];

	/* In case the last bucket is already used */
	if (i >= size)
	for (iter = (of_dictionary_list_object_t*)[data[hash] first];
		for (i = 0; i < size && data[i].key != nil &&
	    iter != NULL; iter = iter->next) {
		if ([iter->key isEqual: key]) {
		    ![data[i].key isEqual: key]; i++);
			[obj retain];
			[iter->object release];
			iter->object = obj;

			return self;
		}
	}
	/* Key not in dictionary */
	if (i >= size || data[i].key == nil) {
		resize(self, count + 1, &data, &size);

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

		/* In case the last bucket is already used */
		if (i >= size)
			for (i = 0; i < size && data[i].key != nil; i++);
		if (i >= size)
			@throw [OFOutOfRangeException newWithClass: isa];

	key = [key copy];
		data[i].key = [key copy];
		data[i].object = [obj retain];
		data[i].hash = hash;
		count++;

	@try {
		return self;
		of_dictionary_list_object_t *o;

	}
		o = (of_dictionary_list_object_t*)[data[hash] append: obj];
		o->key = key;
		o->hash = fullhash;
	} @catch (OFException *e) {
		[key release];
		@throw e;
	}

	[obj retain];
	[data[i].object release];
	data[i].object = obj;

	return self;
}

- removeObjectForKey: (OFObject*)key
{
	uint32_t hash;
	uint32_t i, hash;
	of_dictionary_list_object_t *iter;

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

	hash = [key hash] & (size - 1);
	hash = [key hash];

	if (data[hash] == nil)
		return self;

	for (i = hash & (size - 1); i < size && data[i].key != nil &&
	for (iter = (of_dictionary_list_object_t*)[data[hash] first];
	    iter != NULL; iter = iter->next) {
		if ([iter->object isEqual: key]) {
	    ![data[i].key isEqual: key]; i++);
			[iter->key release];
			[data[hash] remove: (of_list_object_t*)iter];

			if ([data[hash] first] == NULL) {
				[data[hash] release];
				data[hash] = nil;
			}

	/* In case the last bucket is already used */
			return self;
		}
	}

	if (i >= size)
	return self;
}

		for (i = 0; i < size && data[i].key != nil &&
- changeHashSize: (int)hashsize
{
	OFList **newdata;
	size_t newsize, i;
	of_dictionary_list_object_t *iter;

		    ![data[i].key isEqual: key]; i++);
	if (hashsize < 8 || hashsize >= 28)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	newsize = (size_t)1 << hashsize;
	newdata = [self allocMemoryForNItems: newsize
				    withSize: sizeof(OFList*)];
	memset(newdata, 0, newsize * sizeof(OFList*));

	/* Key not in dictionary */
	for (i = 0; i < size; i++) {
		if (OF_LIKELY(data[i] == nil))
	if (i >= size || data[i].key == nil)
			continue;

		return self;
		for (iter = (of_dictionary_list_object_t*)[data[i] first];
		    iter != NULL; iter = iter->next) {
			uint32_t hash = iter->hash & (newsize - 1);
			of_dictionary_list_object_t *o;

			if (newdata[hash] == nil)
	[data[i].key release];
				newdata[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

	[data[i].object release];
			o = (of_dictionary_list_object_t*)
			    [newdata[hash] append: iter->object];
			o->key = iter->key;
	data[i].key = nil;
			o->hash = iter->hash;
		}


	count--;
		[data[i] release];
	}

	resize(self, count, &data, &size);
	[self freeMemory: data];
	data = newdata;
	size = newsize;

	return self;
}

- (id)copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
}
@end
Fossil 2.23 [47362306a7] 2023-11-01 18:56:47
This page was generated in about 0.016s