ObjFW  Check-in [c2d9134d88]

Overview
Comment:runtime/hashtable.m: Add support for deletion
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: c2d9134d8809759a9b97441c521affa619ff0ca7454459e910ddf11d94a89dd8
User & Date: js on 2014-04-06 14:40:52
Other Links: manifest | tags
Context
2014-04-08
16:38
runtime/hashtable.m: Move some code around check-in: f447af977a user: js tags: trunk
2014-04-06
14:40
runtime/hashtable.m: Add support for deletion check-in: c2d9134d88 user: js tags: trunk
2014-03-30
00:30
ObjFW-RT: Call +[unload] on class unregister check-in: 1ecef2d7f6 user: js tags: trunk
Changes

Modified src/OFMapTable.m from [dffae0d500] to [8840bb8cc2].

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

	for (i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
			uint32_t j, last;

			last = capacity;

			j = _buckets[i]->hash & (capacity - 1);
			for (; j < last && buckets[j] != NULL; j++);

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

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




			buckets[j] = _buckets[i];
		}
	}

	[self freeMemory: _buckets];
	_buckets = buckets;
	_capacity = capacity;







|
|









>
>
>







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

	for (i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
			uint32_t j, last;

			last = capacity;

			for (j = _buckets[i]->hash & (capacity - 1);
			    j < last && buckets[j] != NULL; j++);

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

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

			if (j >= last)
				@throw [OFOutOfRangeException exception];

			buckets[j] = _buckets[i];
		}
	}

	[self freeMemory: _buckets];
	_buckets = buckets;
	_capacity = capacity;

Modified src/runtime/class.m from [6289471667] to [0fb0e5fd5b].

860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
{
	while (cls->subclass_list != NULL && cls->subclass_list[0] != Nil)
		objc_unregister_class(cls->subclass_list[0]);

	if (cls->info & OBJC_CLASS_INFO_LOADED)
		call_method(cls, "unload");

	objc_hashtable_set(classes, cls->name, NULL);

	if (strcmp(class_getName(cls), "Protocol"))
		classes_cnt--;

	unregister_class(cls);
	unregister_class(cls->isa);
}







|







860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
{
	while (cls->subclass_list != NULL && cls->subclass_list[0] != Nil)
		objc_unregister_class(cls->subclass_list[0]);

	if (cls->info & OBJC_CLASS_INFO_LOADED)
		call_method(cls, "unload");

	objc_hashtable_delete(classes, cls->name);

	if (strcmp(class_getName(cls), "Protocol"))
		classes_cnt--;

	unregister_class(cls);
	unregister_class(cls->isa);
}
892
893
894
895
896
897
898
899

900
901
902
903
904
905



906
907
908
909
910
911
912
{
	uint_fast32_t i;

	if (classes == NULL)
		return;

	for (i = 0; i < classes->size; i++) {
		if (classes->data[i] != NULL) {

			void *cls = (Class)classes->data[i]->obj;

			if (cls == Nil || (uintptr_t)cls & 1)
				continue;

			objc_unregister_class(cls);



		}
	}

	assert(classes_cnt == 0);

	if (empty_dtable != NULL) {
		objc_sparsearray_free(empty_dtable);







|
>






>
>
>







892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
{
	uint_fast32_t i;

	if (classes == NULL)
		return;

	for (i = 0; i < classes->size; i++) {
		if (classes->data[i] != NULL &&
		    classes->data[i] != &objc_deleted_bucket) {
			void *cls = (Class)classes->data[i]->obj;

			if (cls == Nil || (uintptr_t)cls & 1)
				continue;

			objc_unregister_class(cls);

			/* The table might have been resized, so start again */
			i = 0;
		}
	}

	assert(classes_cnt == 0);

	if (empty_dtable != NULL) {
		objc_sparsearray_free(empty_dtable);

Modified src/runtime/hashtable.m from [2de01382c7] to [4dfb42e01c].

20
21
22
23
24
25
26


27
28
29
30
31
32
33
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#import "runtime.h"
#import "runtime-private.h"



uint32_t
objc_hash_string(const void *str_)
{
	const char *str = str_;
	uint32_t hash = 0;

	while (*str != 0) {







>
>







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#import "runtime.h"
#import "runtime-private.h"

struct objc_hashtable_bucket objc_deleted_bucket;

uint32_t
objc_hash_string(const void *str_)
{
	const char *str = str_;
	uint32_t hash = 0;

	while (*str != 0) {
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
	table->data = calloc(size, sizeof(struct objc_hashtable_bucket*));

	if (table->data == NULL)
		OBJC_ERROR("Not enough memory to allocate hash table!");

	return table;
}






















































static void
insert(struct objc_hashtable *table, const void *key, const void *obj)
{
	uint32_t i, hash, last;
	struct objc_hashtable_bucket *bucket;

	hash = table->hash(key);

	if (table->count + 1 > UINT32_MAX / 4)
		OBJC_ERROR("Integer overflow!");

	if ((table->count + 1) * 4 / table->size >= 3) {
		struct objc_hashtable_bucket **newData;
		uint32_t newSize;

		if (table->size > UINT32_MAX / 2)
			OBJC_ERROR("Integer overflow!");

		newSize = table->size * 2;

		if ((newData = calloc(newSize,
		    sizeof(struct objc_hashtable_bucket*))) == NULL)
			OBJC_ERROR("Not enough memory to insert into hash "
			    "table!");

		for (i = 0; i < table->size; i++) {
			if (table->data[i] != NULL) {
				uint32_t j;

				last = newSize;

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

				if (j >= last) {
					last = table->data[i]->hash &
					    (newSize - 1);

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

				if (j >= last)
					OBJC_ERROR("No free bucket!");

				newData[j] = table->data[i];
			}
		}

		free(table->data);
		table->data = newData;
		table->size = newSize;
	}

	last = table->size;

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

	if (i >= last) {
		last = hash & (table->size - 1);

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

	}

	if (i >= last)
		OBJC_ERROR("No free bucket!");

	if ((bucket = malloc(sizeof(struct objc_hashtable_bucket))) == NULL)
		OBJC_ERROR("Not enough memory to allocate hash table bucket!");

	bucket->key = key;
	bucket->hash = hash;
	bucket->obj = obj;

	table->data[i] = bucket;
	table->count++;
}

static inline int64_t
index_for_key(struct objc_hashtable *table, const void *key)
{
	uint32_t i, hash;

	hash = table->hash(key) & (table->size - 1);

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



		if (table->equal(table->data[i]->key, key))

			return i;



	if (i < table->size)
		return -1;

	for (i = 0; i < hash && table->data[i] != NULL; i++)



		if (table->equal(table->data[i]->key, key))

			return i;



	return -1;
}

void
objc_hashtable_set(struct objc_hashtable *table, const void *key,
    const void *obj)
{
	int64_t idx = index_for_key(table, key);

	if (idx < 0) {
		insert(table, key, obj);
		return;
	}

	table->data[idx]->obj = obj;
}

void*
objc_hashtable_get(struct objc_hashtable *table, const void *key)
{
	int64_t idx = index_for_key(table, key);

	if (idx < 0)
		return NULL;

	return (void*)table->data[idx]->obj;
}
















void
objc_hashtable_free(struct objc_hashtable *table)
{
	uint32_t i;

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

			free(table->data[i]);

	free(table->data);
	free(table);
}







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







<
|
<
<

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


|
|




|
>
















|
|





|
>
>
>
|
>
|
|
>
>

|

|
>
>
>
|
>
|
|
>
>
|






|

|










|

|




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







|
>





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
	table->data = calloc(size, sizeof(struct objc_hashtable_bucket*));

	if (table->data == NULL)
		OBJC_ERROR("Not enough memory to allocate hash table!");

	return table;
}

static void
resize(struct objc_hashtable *table, uint32_t count)
{
	uint32_t i, fullness, nsize;
	struct objc_hashtable_bucket **ndata;

	if (count > UINT32_MAX / sizeof(*table->data) || count > UINT32_MAX / 8)
		OBJC_ERROR("Integer overflow!");

	fullness = count * 8 / table->size;

	if (fullness >= 6) {
		if (table->size > UINT32_MAX / 2)
			nsize = table->size;

		nsize = table->size * 2;
	} else if (fullness <= 1)
		nsize = table->size / 2;
	else
		return;

	if ((ndata = calloc(nsize,
	    sizeof(struct objc_hashtable_bucket*))) == NULL)
		OBJC_ERROR("Not enough memory to insert into hash table!");

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

			last = nsize;

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

			if (j >= last) {
				last = table->data[i]->hash & (nsize - 1);

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

			if (j >= last)
				OBJC_ERROR("No free bucket!");

			ndata[j] = table->data[i];
		}
	}

	free(table->data);
	table->data = ndata;
	table->size = nsize;
}

static void
insert(struct objc_hashtable *table, const void *key, const void *obj)
{
	uint32_t i, hash, last;
	struct objc_hashtable_bucket *bucket;


	resize(table, table->count + 1);










	hash = table->hash(key);



































	last = table->size;

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

	if (i >= last) {
		last = hash & (table->size - 1);

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

	if (i >= last)
		OBJC_ERROR("No free bucket!");

	if ((bucket = malloc(sizeof(struct objc_hashtable_bucket))) == NULL)
		OBJC_ERROR("Not enough memory to allocate hash table bucket!");

	bucket->key = key;
	bucket->hash = hash;
	bucket->obj = obj;

	table->data[i] = bucket;
	table->count++;
}

static inline bool
index_for_key(struct objc_hashtable *table, const void *key, uint32_t *index)
{
	uint32_t i, hash;

	hash = table->hash(key) & (table->size - 1);

	for (i = hash; i < table->size && table->data[i] != NULL; i++) {
		if (table->data[i] == &objc_deleted_bucket)
			continue;

		if (table->equal(table->data[i]->key, key)) {
			*index = i;
			return true;
		}
	}

	if (i < table->size)
		return false;

	for (i = 0; i < hash && table->data[i] != NULL; i++) {
		if (table->data[i] == &objc_deleted_bucket)
			continue;

		if (table->equal(table->data[i]->key, key)) {
			*index = i;
			return true;
		}
	}

	return false;
}

void
objc_hashtable_set(struct objc_hashtable *table, const void *key,
    const void *obj)
{
	uint32_t idx;

	if (!index_for_key(table, key, &idx)) {
		insert(table, key, obj);
		return;
	}

	table->data[idx]->obj = obj;
}

void*
objc_hashtable_get(struct objc_hashtable *table, const void *key)
{
	uint32_t idx;

	if (!index_for_key(table, key, &idx))
		return NULL;

	return (void*)table->data[idx]->obj;
}

void
objc_hashtable_delete(struct objc_hashtable *table, const void *key)
{
	uint32_t idx;

	if (!index_for_key(table, key, &idx))
		return;

	free(table->data[idx]);
	table->data[idx] = &objc_deleted_bucket;

	table->count--;
	resize(table, table->count);
}

void
objc_hashtable_free(struct objc_hashtable *table)
{
	uint32_t i;

	for (i = 0; i < table->size; i++)
		if (table->data[i] != NULL &&
		    table->data[i] != &objc_deleted_bucket)
			free(table->data[i]);

	free(table->data);
	free(table);
}

Modified src/runtime/runtime-private.h from [75ef745292] to [0c1f32cf47].

129
130
131
132
133
134
135

136
137
138

139
140
141
142
143
144
145
extern Class objc_classname_to_class(const char*, bool);
extern void objc_unregister_class(Class);
extern void objc_unregister_all_classes(void);
extern uint32_t objc_hash_string(const void*);
extern bool objc_equal_string(const void*, const void*);
extern struct objc_hashtable* objc_hashtable_new(uint32_t (*)(const void*),
    bool (*)(const void*, const void*), uint32_t);

extern void objc_hashtable_set(struct objc_hashtable*, const void*,
    const void*);
extern void* objc_hashtable_get(struct objc_hashtable*, const void*);

extern void objc_hashtable_free(struct objc_hashtable *h);
extern void objc_register_selector(struct objc_abi_selector*);
extern void objc_register_all_selectors(struct objc_abi_symtab*);
extern void objc_unregister_all_selectors(void);
extern struct objc_sparsearray* objc_sparsearray_new(void);
extern void objc_sparsearray_copy(struct objc_sparsearray*,
    struct objc_sparsearray*);







>



>







129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
extern Class objc_classname_to_class(const char*, bool);
extern void objc_unregister_class(Class);
extern void objc_unregister_all_classes(void);
extern uint32_t objc_hash_string(const void*);
extern bool objc_equal_string(const void*, const void*);
extern struct objc_hashtable* objc_hashtable_new(uint32_t (*)(const void*),
    bool (*)(const void*, const void*), uint32_t);
extern struct objc_hashtable_bucket objc_deleted_bucket;
extern void objc_hashtable_set(struct objc_hashtable*, const void*,
    const void*);
extern void* objc_hashtable_get(struct objc_hashtable*, const void*);
extern void objc_hashtable_delete(struct objc_hashtable*, const void*);
extern void objc_hashtable_free(struct objc_hashtable *h);
extern void objc_register_selector(struct objc_abi_selector*);
extern void objc_register_all_selectors(struct objc_abi_symtab*);
extern void objc_unregister_all_selectors(void);
extern struct objc_sparsearray* objc_sparsearray_new(void);
extern void objc_sparsearray_copy(struct objc_sparsearray*,
    struct objc_sparsearray*);