ObjFW  Diff

Annotate Patch Side-by-side Diff

Differences From Artifact [a445e7d9ad]:

To Artifact [8658c862e5]:

  • File src/runtime/sparsearray.m — part of check-in [1ebb9eb7b3] at 2014-05-15 15:32:35 on branch trunk — Multiple dtable / sparse array improvements

    * dtable.m is now the old sparse array, using IMP as type for values and
    thus not violating the C standard anymore (functions may not be stored
    in void*)
    * New sparsearray.m which can work with any size, based on the sparse
    array from the fast path of class.m
    * Fast path of class.m now uses the new sparsearray.m (user: js, size: 2465) [annotate] [blame] [check-ins using]

︙
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

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

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








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

-
-
+
-
-
+
-

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


-
-
+
+

-
-
+
+

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

-
-
-
+
-
-
+
-
-

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

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

-
-
-
-
-
-
-
+
-


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

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


-
-
-

-
-
-
+
+

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



-
+

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



#include <stdio.h>
#include <stdlib.h>

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

static struct objc_sparsearray_level2 *empty_level2 = NULL;
struct objc_sparsearray*
#ifdef OF_SELUID24
static struct objc_sparsearray_level3 *empty_level3 = NULL;
objc_sparsearray_new(uint_fast8_t index_size)
#endif

{
static void
init(void)
{
	struct objc_sparsearray *sparsearray;

	uint_fast16_t i;

	if ((sparsearray = calloc(1, sizeof(*sparsearray))) == NULL)
	empty_level2 = malloc(sizeof(struct objc_sparsearray_level2));
	if (empty_level2 == NULL)
		OBJC_ERROR("Not enough memory to allocate sparse array!");
		OBJC_ERROR("Failed to allocate memory for sparse array!");

#ifdef OF_SELUID24
	empty_level3 = malloc(sizeof(struct objc_sparsearray_level3));
	if ((sparsearray->data = calloc(1, sizeof(*sparsearray->data))) == NULL)
	if (empty_level3 == NULL)
		OBJC_ERROR("Not enough memory to allocate sparse array!");
		OBJC_ERROR("Failed to allocate memory for sparse array!");
#endif

#ifdef OF_SELUID24
	for (i = 0; i < 256; i++) {
		empty_level2->buckets[i] = empty_level3;
		empty_level3->buckets[i] = NULL;
	}
#else
	sparsearray->index_size = index_size;

	return sparsearray;
	for (i = 0; i < 256; i++)
		empty_level2->buckets[i] = NULL;
#endif
}

struct objc_sparsearray*
objc_sparsearray_new(void)
void*
objc_sparsearray_get(struct objc_sparsearray *sparsearray, uintptr_t idx)
{
	struct objc_sparsearray *s;
	uint_fast16_t i;
	struct objc_sparsearray_data *iter = sparsearray->data;
	uint_fast8_t i;

#ifdef OF_SELUID24
	if (empty_level2 == NULL || empty_level3 == NULL)
		init();
#else
	if (empty_level2 == NULL)
		init();
#endif

	if ((s = malloc(sizeof(struct objc_sparsearray))) == NULL)
		OBJC_ERROR("Not enough memory to allocate sparse array!");

	for (i = 0; i < 256; i++)
		s->buckets[i] = empty_level2;

	for (i = 0; i < sparsearray->index_size - 1; i++) {
		uintptr_t j =
		    (idx >> ((sparsearray->index_size - i - 1) * 8)) & 0xFF;
	return s;
}


		if ((iter = iter->next[j]) == NULL)
void
objc_sparsearray_copy(struct objc_sparsearray *dst,
    struct objc_sparsearray *src)
{
	uint_fast16_t i, j;
#ifdef OF_SELUID24
	uint_fast16_t k;
#endif
	uint32_t idx;

			return NULL;
	for (i = 0; i < 256; i++) {
		if (src->buckets[i] == empty_level2)
			continue;

	}
#ifdef OF_SELUID24
		for (j = 0; j < 256; j++) {
			if (src->buckets[i]->buckets[j] == empty_level3)
				continue;

			for (k = 0; k < 256; k++) {
				const void *obj;

	return iter->next[idx & 0xFF];
				obj = src->buckets[i]->buckets[j]->buckets[k];

}
				if (obj == NULL)
					continue;

				idx = (uint32_t)
void
				    (((uint32_t)i << 16) | (j << 8) | k);
				objc_sparsearray_set(dst, idx, obj);
objc_sparsearray_set(struct objc_sparsearray *sparsearray, uintptr_t idx,
			}
		}
#else
		for (j = 0; j < 256; j++) {
			const void *obj;

    void *value)
{
			obj = src->buckets[i]->buckets[j];

	struct objc_sparsearray_data *iter = sparsearray->data;
			if (obj == NULL)
				continue;

	uint_fast8_t i;
			idx = (uint32_t)((i << 8) | j);
			objc_sparsearray_set(dst, idx, obj);
		}

#endif
	}
}

	for (i = 0; i < sparsearray->index_size - 1; i++) {
void
objc_sparsearray_set(struct objc_sparsearray *s, uint32_t idx, const void *obj)
{
#ifdef OF_SELUID24
	uint8_t i = idx >> 16;
	uint8_t j = idx >> 8;
		uintptr_t j =
	uint8_t k = idx;
#else
	uint8_t i = idx >> 8;
		    (idx >> ((sparsearray->index_size - i - 1) * 8)) & 0xFF;
	uint8_t j = idx;
#endif

	if (s->buckets[i] == empty_level2) {
		if (iter->next[j] == NULL)
		struct objc_sparsearray_level2 *t;
		uint_fast16_t l;

		t = malloc(sizeof(struct objc_sparsearray_level2));

			if ((iter->next[j] = calloc(1,
			    sizeof(struct objc_sparsearray_data))) == NULL)
				OBJC_ERROR("Failed to allocate memory for "
		if (t == NULL)
			OBJC_ERROR("Not enough memory to insert into sparse "
			    "array!");
				    "sparse array!");

		for (l = 0; l < 256; l++)
#ifdef OF_SELUID24
			t->buckets[l] = empty_level3;
#else
			t->buckets[l] = NULL;
#endif

		iter = iter->next[j];
		s->buckets[i] = t;
	}

#ifdef OF_SELUID24
	if (s->buckets[i]->buckets[j] == empty_level3) {
		struct objc_sparsearray_level3 *t;
		uint_fast16_t l;

	iter->next[idx & 0xFF] = value;
		t = malloc(sizeof(struct objc_sparsearray_level3));

}
		if (t == NULL)
			OBJC_ERROR("Not enough memory to insert into sparse "
			    "array!");

		for (l = 0; l < 256; l++)
			t->buckets[l] = NULL;

		s->buckets[i]->buckets[j] = t;
	}

	s->buckets[i]->buckets[j]->buckets[k] = obj;
#else
	s->buckets[i]->buckets[j] = obj;
#endif
}

void
objc_sparsearray_free(struct objc_sparsearray *s)
static void
free_sparsearray_data(struct objc_sparsearray_data *data, uint_fast8_t depth)
{
	uint_fast16_t i;
#ifdef OF_SELUID24
	uint_fast16_t j;
#endif

	for (i = 0; i < 256; i++) {
		if (s->buckets[i] == empty_level2)
			continue;
	if (data == NULL || depth == 0)
		return;

#ifdef OF_SELUID24
		for (j = 0; j < 256; j++)
	for (i = 0; i < 256; i++)
			if (s->buckets[i]->buckets[j] != empty_level3)
				free(s->buckets[i]->buckets[j]);
#endif

		free_sparsearray_data(data->next[i], depth - 1);
		free(s->buckets[i]);
	}


	free(s);
	free(data);
}

void
objc_sparsearray_cleanup(void)
objc_sparsearray_free(struct objc_sparsearray *sparsearray)
{
	if (empty_level2 != NULL)
		free(empty_level2);
	free_sparsearray_data(sparsearray->data, sparsearray->index_size);
#ifdef OF_SELUID24
	if (empty_level3 != NULL)
		free(empty_level3);
#endif

	free(sparsearray);
	empty_level2 = NULL;
#ifdef OF_SELUID24
	empty_level3 = NULL;
#endif
}
Fossil 2.23 [47362306a7] 2023-11-01 18:56:47
This page was generated in about 0.016s