ObjFW  Diff

Annotate Patch Unified 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

#include "config.h"

#include <string.h>

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




















































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

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

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

	if (data[hash] == nil)
		data[hash] = [[OFList alloc] initWithListObjectSize:
		    sizeof(of_dictionary_list_object_t)];



	for (iter = (of_dictionary_list_object_t*)[data[hash] first];
	    iter != NULL; iter = iter->next) {
		if ([iter->key isEqual: key]) {
			[obj retain];
			[iter->object release];
			iter->object = obj;

			return self;


		}


	}






	key = [key copy];




	@try {
		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;
	}




	return self;
}

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

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

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

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

	for (iter = (of_dictionary_list_object_t*)[data[hash] first];
	    iter != NULL; iter = iter->next) {
		if ([iter->object isEqual: key]) {
			[iter->key release];
			[data[hash] remove: (of_list_object_t*)iter];

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

			return self;
		}
	}

	return self;
}

- changeHashSize: (int)hashsize
{
	OFList **newdata;
	size_t newsize, i;
	of_dictionary_list_object_t *iter;

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

	for (i = 0; i < size; i++) {
		if (OF_LIKELY(data[i] == nil))
			continue;

		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)
				newdata[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

			o = (of_dictionary_list_object_t*)
			    [newdata[hash] append: iter->object];
			o->key = iter->key;
			o->hash = iter->hash;
		}

		[data[i] release];
	}

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

	return self;
}

- (id)copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
}
@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
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 i, hash;


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

	hash = [key hash];


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


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

		    ![data[i].key isEqual: key]; i++);




	/* 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];

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

		return self;

	}







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

	return self;
}

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


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

	hash = [key hash];



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


	    ![data[i].key isEqual: key]; i++);







	/* In case the last bucket is already used */



	if (i >= size)


		for (i = 0; i < size && data[i].key != nil &&





		    ![data[i].key isEqual: key]; i++);








	/* Key not in dictionary */

	if (i >= size || data[i].key == nil)

		return self;





	[data[i].key release];



	[data[i].object release];


	data[i].key = nil;


	count--;


	resize(self, count, &data, &size);




	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.015s