1 /* Sparse Arrays for Objective C dispatch tables
2 Copyright (C) 1993, 1995, 1996, 2002, 2004, 2009 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 Under Section 7 of GPL version 3, you are granted additional
17 permissions described in the GCC Runtime Library Exception, version
18 3.1, as published by the Free Software Foundation.
20 You should have received a copy of the GNU General Public License and
21 a copy of the GCC Runtime Library Exception along with this program;
22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 <http://www.gnu.org/licenses/>. */
25 #include "objc-private/common.h"
26 #include "objc/sarray.h"
27 #include "objc/objc.h"
28 #include "objc/objc-api.h"
30 #include "objc-private/runtime.h"
32 #include <string.h> /* For memset */
35 int nbuckets
= 0; /* !T:MUTEX */
36 int nindices
= 0; /* !T:MUTEX */
37 int narrays
= 0; /* !T:MUTEX */
38 int idxsize
= 0; /* !T:MUTEX */
40 static void *first_free_data
= NULL
; /* !T:MUTEX */
43 const char *__objc_sparse2_id
= "2 level sparse indices";
47 const char *__objc_sparse3_id
= "3 level sparse indices";
50 /* This function removes any structures left over from free operations
51 that were not safe in a multi-threaded environment. */
53 sarray_remove_garbage (void)
58 objc_mutex_lock (__objc_runtime_mutex
);
61 first_free_data
= NULL
;
69 objc_mutex_unlock (__objc_runtime_mutex
);
72 /* Free a block of dynamically allocated memory. If we are in multi-threaded
73 mode, it is ok to free it. If not, we add it to the garbage heap to be
77 sarray_free_garbage (void *vp
)
79 objc_mutex_lock (__objc_runtime_mutex
);
81 if (__objc_runtime_threads_alive
== 1) {
84 sarray_remove_garbage ();
87 *(void **)vp
= first_free_data
;
91 objc_mutex_unlock (__objc_runtime_mutex
);
94 /* sarray_at_put : copies data in such a way as to be thread reader safe. */
96 sarray_at_put (struct sarray
*array
, sidx index
, void *element
)
99 struct sindex
**the_index
;
100 struct sindex
*new_index
;
102 struct sbucket
**the_bucket
;
103 struct sbucket
*new_bucket
;
109 #ifdef PRECOMPUTE_SELECTORS
113 ioffset
= xx
.off
.ioffset
;
115 boffset
= xx
.off
.boffset
;
116 eoffset
= xx
.off
.eoffset
;
117 #else /* not PRECOMPUTE_SELECTORS */
119 ioffset
= index
/INDEX_CAPACITY
;
120 boffset
= (index
/BUCKET_SIZE
)%INDEX_SIZE
;
121 eoffset
= index
%BUCKET_SIZE
;
123 boffset
= index
/BUCKET_SIZE
;
124 eoffset
= index
%BUCKET_SIZE
;
126 #endif /* not PRECOMPUTE_SELECTORS */
128 assert (soffset_decode (index
) < array
->capacity
); /* Range check */
131 the_index
= &(array
->indices
[ioffset
]);
132 the_bucket
= &((*the_index
)->buckets
[boffset
]);
134 the_bucket
= &(array
->buckets
[boffset
]);
137 if ((*the_bucket
)->elems
[eoffset
] == element
)
138 return; /* great! we just avoided a lazy copy */
142 /* First, perform lazy copy/allocation of index if needed */
144 if ((*the_index
) == array
->empty_index
) {
146 /* The index was previously empty, allocate a new */
147 new_index
= (struct sindex
*) objc_malloc (sizeof (struct sindex
));
148 memcpy (new_index
, array
->empty_index
, sizeof (struct sindex
));
149 new_index
->version
.version
= array
->version
.version
;
150 *the_index
= new_index
; /* Prepared for install. */
151 the_bucket
= &((*the_index
)->buckets
[boffset
]);
154 } else if ((*the_index
)->version
.version
!= array
->version
.version
) {
156 /* This index must be lazy copied */
157 struct sindex
*old_index
= *the_index
;
158 new_index
= (struct sindex
*) objc_malloc (sizeof (struct sindex
));
159 memcpy (new_index
, old_index
, sizeof (struct sindex
));
160 new_index
->version
.version
= array
->version
.version
;
161 *the_index
= new_index
; /* Prepared for install. */
162 the_bucket
= &((*the_index
)->buckets
[boffset
]);
167 #endif /* OBJC_SPARSE3 */
169 /* next, perform lazy allocation/copy of the bucket if needed */
171 if ((*the_bucket
) == array
->empty_bucket
) {
173 /* The bucket was previously empty (or something like that), */
174 /* allocate a new. This is the effect of `lazy' allocation */
175 new_bucket
= (struct sbucket
*) objc_malloc (sizeof (struct sbucket
));
176 memcpy ((void *) new_bucket
, (const void *) array
->empty_bucket
,
177 sizeof (struct sbucket
));
178 new_bucket
->version
.version
= array
->version
.version
;
179 *the_bucket
= new_bucket
; /* Prepared for install. */
183 } else if ((*the_bucket
)->version
.version
!= array
->version
.version
) {
185 /* Perform lazy copy. */
186 struct sbucket
*old_bucket
= *the_bucket
;
187 new_bucket
= (struct sbucket
*) objc_malloc (sizeof (struct sbucket
));
188 memcpy (new_bucket
, old_bucket
, sizeof (struct sbucket
));
189 new_bucket
->version
.version
= array
->version
.version
;
190 *the_bucket
= new_bucket
; /* Prepared for install. */
195 (*the_bucket
)->elems
[eoffset
] = element
;
199 sarray_at_put_safe (struct sarray
*array
, sidx index
, void *element
)
201 if (soffset_decode (index
) >= array
->capacity
)
202 sarray_realloc (array
, soffset_decode (index
) + 1);
203 sarray_at_put (array
, index
, element
);
207 sarray_new (int size
, void *default_element
)
211 size_t num_indices
= ((size
- 1)/(INDEX_CAPACITY
)) + 1;
212 struct sindex
**new_indices
;
213 #else /* OBJC_SPARSE2 */
214 size_t num_indices
= ((size
- 1)/BUCKET_SIZE
) + 1;
215 struct sbucket
**new_buckets
;
221 /* Allocate core array */
222 arr
= (struct sarray
*) objc_malloc (sizeof (struct sarray
));
223 arr
->version
.version
= 0;
225 /* Initialize members */
227 arr
->capacity
= num_indices
*INDEX_CAPACITY
;
228 new_indices
= (struct sindex
**)
229 objc_malloc (sizeof (struct sindex
*) * num_indices
);
231 arr
->empty_index
= (struct sindex
*) objc_malloc (sizeof (struct sindex
));
232 arr
->empty_index
->version
.version
= 0;
235 idxsize
+= num_indices
;
238 #else /* OBJC_SPARSE2 */
239 arr
->capacity
= num_indices
*BUCKET_SIZE
;
240 new_buckets
= (struct sbucket
**)
241 objc_malloc (sizeof (struct sbucket
*) * num_indices
);
244 idxsize
+= num_indices
;
248 arr
->empty_bucket
= (struct sbucket
*) objc_malloc (sizeof (struct sbucket
));
249 arr
->empty_bucket
->version
.version
= 0;
254 arr
->is_copy_of
= (struct sarray
*) 0;
256 for (counter
= 0; counter
< BUCKET_SIZE
; counter
++)
257 arr
->empty_bucket
->elems
[counter
] = default_element
;
260 for (counter
= 0; counter
< INDEX_SIZE
; counter
++)
261 arr
->empty_index
->buckets
[counter
] = arr
->empty_bucket
;
263 for (counter
= 0; counter
< num_indices
; counter
++)
264 new_indices
[counter
] = arr
->empty_index
;
266 #else /* OBJC_SPARSE2 */
268 for (counter
= 0; counter
< num_indices
; counter
++)
269 new_buckets
[counter
] = arr
->empty_bucket
;
274 arr
->indices
= new_indices
;
275 #else /* OBJC_SPARSE2 */
276 arr
->buckets
= new_buckets
;
283 /* Reallocate the sparse array to hold `newsize' entries
284 Note: We really allocate and then free. We have to do this to ensure that
285 any concurrent readers notice the update. */
288 sarray_realloc (struct sarray
*array
, int newsize
)
291 size_t old_max_index
= (array
->capacity
- 1)/INDEX_CAPACITY
;
292 size_t new_max_index
= ((newsize
- 1)/INDEX_CAPACITY
);
293 size_t rounded_size
= (new_max_index
+ 1) * INDEX_CAPACITY
;
295 struct sindex
**new_indices
;
296 struct sindex
**old_indices
;
298 #else /* OBJC_SPARSE2 */
299 size_t old_max_index
= (array
->capacity
- 1)/BUCKET_SIZE
;
300 size_t new_max_index
= ((newsize
- 1)/BUCKET_SIZE
);
301 size_t rounded_size
= (new_max_index
+ 1) * BUCKET_SIZE
;
303 struct sbucket
**new_buckets
;
304 struct sbucket
**old_buckets
;
310 assert (newsize
> 0);
312 /* The size is the same, just ignore the request */
313 if (rounded_size
<= array
->capacity
)
316 assert (array
->ref_count
== 1); /* stop if lazy copied... */
318 /* We are asked to extend the array -- allocate new bucket table, */
319 /* and insert empty_bucket in newly allocated places. */
320 if (rounded_size
> array
->capacity
)
325 rounded_size
= (new_max_index
+ 1) * INDEX_CAPACITY
;
327 #else /* OBJC_SPARSE2 */
329 rounded_size
= (new_max_index
+ 1) * BUCKET_SIZE
;
332 /* update capacity */
333 array
->capacity
= rounded_size
;
336 /* alloc to force re-read by any concurrent readers. */
337 old_indices
= array
->indices
;
338 new_indices
= (struct sindex
**)
339 objc_malloc ((new_max_index
+ 1) * sizeof (struct sindex
*));
340 #else /* OBJC_SPARSE2 */
341 old_buckets
= array
->buckets
;
342 new_buckets
= (struct sbucket
**)
343 objc_malloc ((new_max_index
+ 1) * sizeof (struct sbucket
*));
346 /* copy buckets below old_max_index (they are still valid) */
347 for (counter
= 0; counter
<= old_max_index
; counter
++ ) {
349 new_indices
[counter
] = old_indices
[counter
];
350 #else /* OBJC_SPARSE2 */
351 new_buckets
[counter
] = old_buckets
[counter
];
356 /* reset entries above old_max_index to empty_bucket */
357 for (counter
= old_max_index
+ 1; counter
<= new_max_index
; counter
++)
358 new_indices
[counter
] = array
->empty_index
;
359 #else /* OBJC_SPARSE2 */
360 /* reset entries above old_max_index to empty_bucket */
361 for (counter
= old_max_index
+ 1; counter
<= new_max_index
; counter
++)
362 new_buckets
[counter
] = array
->empty_bucket
;
366 /* install the new indices */
367 array
->indices
= new_indices
;
368 #else /* OBJC_SPARSE2 */
369 array
->buckets
= new_buckets
;
373 /* free the old indices */
374 sarray_free_garbage (old_indices
);
375 #else /* OBJC_SPARSE2 */
376 sarray_free_garbage (old_buckets
);
379 idxsize
+= (new_max_index
-old_max_index
);
385 /* Free a sparse array allocated with sarray_new */
388 sarray_free (struct sarray
*array
) {
390 size_t old_max_index
= (array
->capacity
- 1)/INDEX_CAPACITY
;
391 struct sindex
**old_indices
;
393 size_t old_max_index
= (array
->capacity
- 1)/BUCKET_SIZE
;
394 struct sbucket
**old_buckets
;
398 assert (array
->ref_count
!= 0); /* Freed multiple times!!! */
400 if (--(array
->ref_count
) != 0) /* There exists copies of me */
404 old_indices
= array
->indices
;
406 old_buckets
= array
->buckets
;
409 /* Free all entries that do not point to empty_bucket */
410 for (counter
= 0; counter
<= old_max_index
; counter
++ ) {
412 struct sindex
*idx
= old_indices
[counter
];
413 if ((idx
!= array
->empty_index
) &&
414 (idx
->version
.version
== array
->version
.version
)) {
416 for (c2
= 0; c2
< INDEX_SIZE
; c2
++) {
417 struct sbucket
*bkt
= idx
->buckets
[c2
];
418 if ((bkt
!= array
->empty_bucket
) &&
419 (bkt
->version
.version
== array
->version
.version
))
421 sarray_free_garbage (bkt
);
425 sarray_free_garbage (idx
);
428 #else /* OBJC_SPARSE2 */
429 struct sbucket
*bkt
= old_buckets
[counter
];
430 if ((bkt
!= array
->empty_bucket
) &&
431 (bkt
->version
.version
== array
->version
.version
))
433 sarray_free_garbage (bkt
);
440 /* free empty_index */
441 if (array
->empty_index
->version
.version
== array
->version
.version
) {
442 sarray_free_garbage (array
->empty_index
);
447 /* free empty_bucket */
448 if (array
->empty_bucket
->version
.version
== array
->version
.version
) {
449 sarray_free_garbage (array
->empty_bucket
);
452 idxsize
-= (old_max_index
+ 1);
456 /* free bucket table */
457 sarray_free_garbage (array
->indices
);
460 /* free bucket table */
461 sarray_free_garbage (array
->buckets
);
465 /* If this is a copy of another array, we free it (which might just
466 * decrement its reference count so it will be freed when no longer in use).
468 if (array
->is_copy_of
)
469 sarray_free (array
->is_copy_of
);
472 sarray_free_garbage (array
);
475 /* This is a lazy copy. Only the core of the structure is actually */
479 sarray_lazy_copy (struct sarray
*oarr
)
484 size_t num_indices
= ((oarr
->capacity
- 1)/INDEX_CAPACITY
) + 1;
485 struct sindex
**new_indices
;
486 #else /* OBJC_SPARSE2 */
487 size_t num_indices
= ((oarr
->capacity
- 1)/BUCKET_SIZE
) + 1;
488 struct sbucket
**new_buckets
;
491 /* Allocate core array */
492 arr
= (struct sarray
*) objc_malloc (sizeof (struct sarray
)); /* !!! */
493 arr
->version
.version
= oarr
->version
.version
+ 1;
495 arr
->empty_index
= oarr
->empty_index
;
497 arr
->empty_bucket
= oarr
->empty_bucket
;
499 oarr
->ref_count
+= 1;
500 arr
->is_copy_of
= oarr
;
501 arr
->capacity
= oarr
->capacity
;
504 /* Copy bucket table */
505 new_indices
= (struct sindex
**)
506 objc_malloc (sizeof (struct sindex
*) * num_indices
);
507 memcpy (new_indices
, oarr
->indices
, sizeof (struct sindex
*) * num_indices
);
508 arr
->indices
= new_indices
;
510 /* Copy bucket table */
511 new_buckets
= (struct sbucket
**)
512 objc_malloc (sizeof (struct sbucket
*) * num_indices
);
513 memcpy (new_buckets
, oarr
->buckets
, sizeof (struct sbucket
*) * num_indices
);
514 arr
->buckets
= new_buckets
;
517 idxsize
+= num_indices
;