ObjFW  Check-in [8d930f2067]

Overview
Comment:Generalize runtime/hashtable.m
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 8d930f2067244ad088ee6958a5f79246fa11bb15d0712ec0ed4a316d4f9fd8f1
User & Date: js on 2014-03-22 17:56:09
Other Links: manifest | tags
Context
2014-03-23
00:15
Remove -Wno-deprecated-objc-pointer-introspection check-in: f3154a74aa user: js tags: trunk
2014-03-22
17:56
Generalize runtime/hashtable.m check-in: 8d930f2067 user: js tags: trunk
2014-03-19
18:05
macros.h: Never define static_assert to assert check-in: 61369b9d26 user: js tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Modified src/runtime/category.m from [b9b6c831df] to [cc568b9dbb].

︙
45
46
47
48
49
50
51
52


53
54
55
56
57
58
59

45
46
47
48
49
50
51

52
53
54
55
56
57
58
59
60








-
+
+








static void
register_category(struct objc_abi_category *cat)
{
	struct objc_abi_category **cats;
	Class cls = objc_classname_to_class(cat->class_name, false);

	if (categories == NULL)
		categories = objc_hashtable_new(2);
		categories = objc_hashtable_new(
		    objc_hash_string, objc_equal_string, 2);

	cats = (struct objc_abi_category**)objc_hashtable_get(categories,
	    cat->class_name);

	if (cats != NULL) {
		struct objc_abi_category **ncats;
		size_t i;
︙
119
120
121
122
123
124
125
126

127
128
129
130
131
132

120
121
122
123
124
125
126

127
128
129
130
131
132
133








-
+







objc_unregister_all_categories(void)
{
	uint32_t i;

	if (categories == NULL)
		return;

	for (i = 0; i <= categories->last_idx; i++)
	for (i = 0; i < categories->size; i++)
		if (categories->data[i] != NULL)
			free((void*)categories->data[i]->obj);

	objc_hashtable_free(categories);
	categories = NULL;
}

Modified src/runtime/class.m from [e32de8ba86] to [cb99b9ea3b].

︙
37
38
39
40
41
42
43
44


45
46
47
48
49
50
51

37
38
39
40
41
42
43

44
45
46
47
48
49
50
51
52








-
+
+








static unsigned lookups_till_fast_path = 128;
static struct sparsearray *sparsearray = NULL;

static void
register_class(struct objc_abi_class *cls)
{
	if (classes == NULL)
		classes = objc_hashtable_new(2);
		classes = objc_hashtable_new(
		    objc_hash_string, objc_equal_string, 2);

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

	if (empty_dtable == NULL)
		empty_dtable = objc_sparsearray_new();

	cls->dtable = empty_dtable;
︙
520
521
522
523
524
525
526
527

528
529
530
531
532
533
534

521
522
523
524
525
526
527

528
529
530
531
532
533
534
535








-
+









	if (buf == NULL)
		return classes_cnt;

	if (classes_cnt < count)
		count = classes_cnt;

	for (i = j = 0; i <= classes->last_idx; i++) {
	for (i = j = 0; i < classes->size; i++) {
		Class cls;

		if (j >= count) {
			objc_global_mutex_unlock();
			return j;
		}
︙
854
855
856
857
858
859
860
861

862
863
864
865
866
867
868

855
856
857
858
859
860
861

862
863
864
865
866
867
868
869








-
+








objc_unregister_all_classes(void)
{
	uint_fast32_t i;

	if (classes == NULL)
		return;

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

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

			objc_unregister_class(cls);
︙

Modified src/runtime/hashtable.m from [7dd989f99f] to [2de01382c7].

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

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








-
+

+
















+
+
+
+
+
+

-
+
+

-
+
-

-
+


+
+
+
-
-
-
+
+
+

-
+


-
-
-
-
+



-
+




-
+

-
+


-
-
-
+
+
+

-
+


+
+
+
-
+
-



-
+
-
-
-
-
+


-
+

-
-
+
+


-
+
+


-
+





-
+



-
-
-
+
+
+


-
+

+
-
+


-
+

-
+












-
-
+
+



-
+



-
+

-
-
+
+


-
+


-
-
+
+






-
+
+

-
+


-
+



-
+



-
+

-
+




-
+



-
+



-
-
-
+
+
+

-
-
+
+


#include <stdint.h>
#include <string.h>

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

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

	while (*str != 0) {
		hash += *str;
		hash += (hash << 10);
		hash ^= (hash >> 6);
		str++;
	}

	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);

	return hash;
}

bool
objc_equal_string(const void *obj1, const void *obj2)
{
	return !strcmp(obj1, obj2);
}

struct objc_hashtable*
objc_hashtable_new(uint32_t size)
objc_hashtable_new(uint32_t (*hash)(const void*),
    bool (*equal)(const void*, const void*), uint32_t size)
{
	struct objc_hashtable *h;
	struct objc_hashtable *table;
	uint32_t i;

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

	table->hash = hash;
	table->equal = equal;

	h->count = 0;
	h->last_idx = size - 1;
	h->data = malloc(size * sizeof(struct objc_hashtable_bucket*));
	table->count = 0;
	table->size = size;
	table->data = calloc(size, sizeof(struct objc_hashtable_bucket*));

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

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

	return h;
	return table;
}

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

	hash = objc_hash_string(key);
	hash = table->hash(key);

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

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

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

		newSize = table->size * 2;

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

		for (i = 0; i < nsize; i++)
		for (i = 0; i < table->size; i++) {
			ndata[i] = NULL;

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

				last = nsize;
				last = newSize;

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

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

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

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

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

		free(h->data);
		h->data = ndata;
		h->last_idx = nsize - 1;
		free(table->data);
		table->data = newData;
		table->size = newSize;
	}

	last = h->last_idx + 1;
	last = table->size;

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

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

		for (i = 0; i < last && h->data[i] != NULL; i++);
		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;

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

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

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

	for (i = hash; i <= h->last_idx && h->data[i] != NULL; i++)
		if (!strcmp(h->data[i]->key, key))
	for (i = hash; i < table->size && table->data[i] != NULL; i++)
		if (table->equal(table->data[i]->key, key))
			return i;

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

	for (i = 0; i < hash && h->data[i] != NULL; i++)
		if (!strcmp(h->data[i]->key, key))
	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 *h, const char *key, const void *obj)
objc_hashtable_set(struct objc_hashtable *table, const void *key,
    const void *obj)
{
	int64_t idx = index_for_key(h, key);
	int64_t idx = index_for_key(table, key);

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

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

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

	if (idx < 0)
		return NULL;

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

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

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

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

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

︙
87
88
89
90
91
92
93
94
95

96
97
98
99
100
101



102
103
104
105
106
107
108

87
88
89
90
91
92
93


94
95
96
97
98


99
100
101
102
103
104
105
106
107
108








-
-
+




-
-
+
+
+








	unsigned long version;	/* 9 = non-fragile */
	unsigned long size;
	const char *name;
	struct objc_abi_symtab *symtab;
};

struct objc_hashtable_bucket {
	const char *key;
	const void *obj;
	const void *key, *obj;
	uint32_t hash;
};

struct objc_hashtable {
	uint32_t count;
	uint32_t last_idx;
	uint32_t (*hash)(const void *key);
	bool (*equal)(const void *key1, const void *key2);
	uint32_t count, size;
	struct objc_hashtable_bucket **data;
};

struct objc_sparsearray {
	struct objc_sparsearray_level2 *buckets[256];
};
︙
125
126
127
128
129
130
131
132
133
134





135
136

137
138
139
140
141
142
143

125
126
127
128
129
130
131



132
133
134
135
136
137

138
139
140
141
142
143
144
145








-
-
-
+
+
+
+
+

-
+








extern void objc_unregister_all_categories(void);
extern void objc_initialize_class(Class);
extern void objc_update_dtable(Class);
extern void objc_register_all_classes(struct objc_abi_symtab*);
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 char*);
extern struct objc_hashtable* objc_hashtable_new(uint32_t);
extern void objc_hashtable_set(struct objc_hashtable*, const char*,
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 char*);
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*);
︙

Modified src/runtime/selector.m from [915bbfe8d7] to [c556b01892].

︙
43
44
45
46
47
48
49
50


51
52
53
54
55
56
57

43
44
45
46
47
48
49

50
51
52
53
54
55
56
57
58








-
+
+








	struct objc_selector *rsel;
	const char *name;

	if (selectors_cnt > SEL_MAX)
		OBJC_ERROR("Out of selector slots!");

	if (selectors == NULL)
		selectors = objc_hashtable_new(2);
		selectors = objc_hashtable_new(
		    objc_hash_string, objc_equal_string, 2);
	else if ((rsel = objc_hashtable_get(selectors, sel->name)) != NULL) {
		((struct objc_selector*)sel)->uid = rsel->uid;
		return;
	}

	if (selector_names == NULL)
		selector_names = objc_sparsearray_new();
︙

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