ObjFW  Diff

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


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

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

static struct objc_sparsearray_level2 *empty_level2 = NULL;
#ifdef OF_SELUID24
static struct objc_sparsearray_level3 *empty_level3 = NULL;
#endif

static void
init(void)

{
	uint_fast16_t i;

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

#ifdef OF_SELUID24
	empty_level3 = malloc(sizeof(struct objc_sparsearray_level3));
	if (empty_level3 == NULL)
		OBJC_ERROR("Not enough memory to allocate sparse array!");
#endif

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

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

struct objc_sparsearray*

objc_sparsearray_new(void)
{
	struct objc_sparsearray *s;
	uint_fast16_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;

	return s;
}

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;

	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;

				obj = src->buckets[i]->buckets[j]->buckets[k];

				if (obj == NULL)
					continue;

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

			obj = src->buckets[i]->buckets[j];

			if (obj == NULL)
				continue;

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

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;
	uint8_t k = idx;
#else
	uint8_t i = idx >> 8;
	uint8_t j = idx;
#endif

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

		t = malloc(sizeof(struct objc_sparsearray_level2));

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

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

		s->buckets[i] = t;
	}

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

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

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

		free(s->buckets[i]);
	}

	free(s);
}

void
objc_sparsearray_cleanup(void)
{
	if (empty_level2 != NULL)
		free(empty_level2);
#ifdef OF_SELUID24
	if (empty_level3 != NULL)
		free(empty_level3);
#endif

	empty_level2 = NULL;
#ifdef OF_SELUID24
	empty_level3 = NULL;
#endif
}








|
<
|
<
|
<
<
>
|
<
|
<
<
|

<
|
<
|
<

<
<
<
<
>
|
|
<
<
<


<
>
|

|
|

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

<
<
|
<
|
<
<

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

|
<
<
|
|
|
<
<
|

<
<
<
<
<
<
|
<


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

<
<
<
<
<
<
<
<
<
|
|


<
<
<

<
|
|

<
|
<
<
<
|
<
|
<
|



|

<
|
<
<
<
<
|
<
<
<
<


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"

struct objc_sparsearray*

objc_sparsearray_new(uint_fast8_t index_size)

{


	struct objc_sparsearray *sparsearray;


	if ((sparsearray = calloc(1, sizeof(*sparsearray))) == NULL)


		OBJC_ERROR("Failed to allocate memory for sparse array!");


	if ((sparsearray->data = calloc(1, sizeof(*sparsearray->data))) == NULL)

		OBJC_ERROR("Failed to allocate memory for sparse array!");






	sparsearray->index_size = index_size;

	return sparsearray;



}


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












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


		if ((iter = iter->next[j]) == NULL)









			return NULL;



	}







	return iter->next[idx & 0xFF];

}



void

objc_sparsearray_set(struct objc_sparsearray *sparsearray, uintptr_t idx,




    void *value)
{

	struct objc_sparsearray_data *iter = sparsearray->data;


	uint_fast8_t i;






	for (i = 0; i < sparsearray->index_size - 1; i++) {





		uintptr_t j =


		    (idx >> ((sparsearray->index_size - i - 1) * 8)) & 0xFF;



		if (iter->next[j] == NULL)


			if ((iter->next[j] = calloc(1,
			    sizeof(struct objc_sparsearray_data))) == NULL)
				OBJC_ERROR("Failed to allocate memory for "


				    "sparse array!");







		iter = iter->next[j];

	}





	iter->next[idx & 0xFF] = value;

}
















static void
free_sparsearray_data(struct objc_sparsearray_data *data, uint_fast8_t depth)
{
	uint_fast16_t i;





	if (data == NULL || depth == 0)
		return;


	for (i = 0; i < 256; i++)



		free_sparsearray_data(data->next[i], depth - 1);



	free(data);
}

void
objc_sparsearray_free(struct objc_sparsearray *sparsearray)
{

	free_sparsearray_data(sparsearray->data, sparsearray->index_size);




	free(sparsearray);




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