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

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

45
46
47
48
49
50
51
52

53
54
55
56
57
58
59
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);


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

	if (cats != NULL) {
		struct objc_abi_category **ncats;
		size_t i;







|
>







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(
		    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
objc_unregister_all_categories(void)
{
	uint32_t i;

	if (categories == NULL)
		return;

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

	objc_hashtable_free(categories);
	categories = NULL;
}







|






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


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

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

	cls->dtable = empty_dtable;







|
>







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

	if (buf == NULL)
		return classes_cnt;

	if (classes_cnt < count)
		count = classes_cnt;

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

		if (j >= count) {
			objc_global_mutex_unlock();
			return j;
		}








|







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->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
objc_unregister_all_classes(void)
{
	uint_fast32_t i;

	if (classes == NULL)
		return;

	for (i = 0; i <= classes->last_idx; 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);







|







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->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
#include <stdint.h>
#include <string.h>

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

uint32_t
objc_hash_string(const char *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;
}







struct objc_hashtable*
objc_hashtable_new(uint32_t size)

{
	struct objc_hashtable *h;
	uint32_t i;

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




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

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

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

	return h;
}

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

	hash = objc_hash_string(key);

	if (h->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 (nsize == 0)
			OBJC_ERROR("Integer overflow!");




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

		for (i = 0; i < nsize; i++)
			ndata[i] = NULL;

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

				last = nsize;

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

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


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

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

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

		free(h->data);
		h->data = ndata;
		h->last_idx = nsize - 1;
	}

	last = h->last_idx + 1;


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

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

		for (i = 0; i < last && h->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++;
}

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

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

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

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

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

	return -1;
}

void
objc_hashtable_set(struct objc_hashtable *h, const char *key, const void *obj)

{
	int64_t idx = index_for_key(h, key);

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

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

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

	if (idx < 0)
		return NULL;

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

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

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

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







|

>
















>
>
>
>
>
>

|
>

|
<

|


>
>
>
|
|
|

|


<
<
<
|



|




|

|


|
|
|

|


>
>
>
|
<



|
<
<
<
|


|

|
|


|
>


|





|



|
|
|


|

>
|


|

|












|
|



|



|

|
|


|


|
|






|
>

|


|



|



|

|




|



|



|
|
|

|
|

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 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 (*hash)(const void*),
    bool (*equal)(const void*, const void*), uint32_t size)
{
	struct objc_hashtable *table;


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

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

	table->count = 0;
	table->size = size;
	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);
}

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
	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;
	uint32_t hash;
};

struct objc_hashtable {
	uint32_t count;

	uint32_t last_idx;
	struct objc_hashtable_bucket **data;
};

struct objc_sparsearray {
	struct objc_sparsearray_level2 *buckets[256];
};








<
|




|
>
|







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 void *key, *obj;
	uint32_t hash;
};

struct objc_hashtable {
	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
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*,
    const void*);
extern void* objc_hashtable_get(struct objc_hashtable*, const char*);
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*);







|
>
|
>
|

|







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

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

43
44
45
46
47
48
49
50

51
52
53
54
55
56
57
	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);

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







|
>







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