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-private/sarray.h"
27 #include "objc/runtime.h" /* For objc_malloc */
28 #include "objc/thr.h" /* For objc_mutex_lock */
29 #include "objc-private/runtime.h"
31 #include <string.h> /* For memset */
32 #include <assert.h> /* For assert */
34 int nbuckets
= 0; /* !T:MUTEX */
35 int nindices
= 0; /* !T:MUTEX */
36 int narrays
= 0; /* !T:MUTEX */
37 int idxsize
= 0; /* !T:MUTEX */
39 static void *first_free_data
= NULL
; /* !T:MUTEX */
42 const char *__objc_sparse2_id
= "2 level sparse indices";
46 const char *__objc_sparse3_id
= "3 level sparse indices";
49 /* This function removes any structures left over from free operations
50 that were not safe in a multi-threaded environment. */
52 sarray_remove_garbage (void)
57 objc_mutex_lock (__objc_runtime_mutex
);
60 first_free_data
= NULL
;
69 objc_mutex_unlock (__objc_runtime_mutex
);
72 /* Free a block of dynamically allocated memory. If we are in
73 multi-threaded mode, it is ok to free it. If not, we add it to the
74 garbage heap to be freed later. */
76 sarray_free_garbage (void *vp
)
78 objc_mutex_lock (__objc_runtime_mutex
);
80 if (__objc_runtime_threads_alive
== 1)
84 sarray_remove_garbage ();
88 *(void **)vp
= first_free_data
;
92 objc_mutex_unlock (__objc_runtime_mutex
);
95 /* sarray_at_put copies data in such a way as to be thread reader
98 sarray_at_put (struct sarray
*array
, sidx index
, void *element
)
101 struct sindex
**the_index
;
102 struct sindex
*new_index
;
104 struct sbucket
**the_bucket
;
105 struct sbucket
*new_bucket
;
111 #ifdef PRECOMPUTE_SELECTORS
115 ioffset
= xx
.off
.ioffset
;
117 boffset
= xx
.off
.boffset
;
118 eoffset
= xx
.off
.eoffset
;
119 #else /* not PRECOMPUTE_SELECTORS */
121 ioffset
= index
/INDEX_CAPACITY
;
122 boffset
= (index
/BUCKET_SIZE
)%INDEX_SIZE
;
123 eoffset
= index
%BUCKET_SIZE
;
125 boffset
= index
/BUCKET_SIZE
;
126 eoffset
= index
%BUCKET_SIZE
;
128 #endif /* not PRECOMPUTE_SELECTORS */
130 assert (soffset_decode (index
) < array
->capacity
); /* Range check */
133 the_index
= &(array
->indices
[ioffset
]);
134 the_bucket
= &((*the_index
)->buckets
[boffset
]);
136 the_bucket
= &(array
->buckets
[boffset
]);
139 if ((*the_bucket
)->elems
[eoffset
] == element
)
140 return; /* Great! we just avoided a lazy copy. */
144 /* First, perform lazy copy/allocation of index if needed. */
146 if ((*the_index
) == array
->empty_index
)
148 /* The index was previously empty, allocate a new. */
149 new_index
= (struct sindex
*) objc_malloc (sizeof (struct sindex
));
150 memcpy (new_index
, array
->empty_index
, sizeof (struct sindex
));
151 new_index
->version
.version
= array
->version
.version
;
152 *the_index
= new_index
; /* Prepared for install. */
153 the_bucket
= &((*the_index
)->buckets
[boffset
]);
157 else if ((*the_index
)->version
.version
!= array
->version
.version
)
159 /* This index must be lazy copied. */
160 struct sindex
*old_index
= *the_index
;
161 new_index
= (struct sindex
*) objc_malloc (sizeof (struct sindex
));
162 memcpy (new_index
, old_index
, sizeof (struct sindex
));
163 new_index
->version
.version
= array
->version
.version
;
164 *the_index
= new_index
; /* Prepared for install. */
165 the_bucket
= &((*the_index
)->buckets
[boffset
]);
170 #endif /* OBJC_SPARSE3 */
172 /* Next, perform lazy allocation/copy of the bucket if needed. */
173 if ((*the_bucket
) == array
->empty_bucket
)
175 /* The bucket was previously empty (or something like that),
176 allocate a new. This is the effect of `lazy' allocation. */
177 new_bucket
= (struct sbucket
*) objc_malloc (sizeof (struct sbucket
));
178 memcpy ((void *) new_bucket
, (const void *) array
->empty_bucket
,
179 sizeof (struct sbucket
));
180 new_bucket
->version
.version
= array
->version
.version
;
181 *the_bucket
= new_bucket
; /* Prepared for install. */
186 else if ((*the_bucket
)->version
.version
!= array
->version
.version
)
188 /* Perform lazy copy. */
189 struct sbucket
*old_bucket
= *the_bucket
;
190 new_bucket
= (struct sbucket
*) objc_malloc (sizeof (struct sbucket
));
191 memcpy (new_bucket
, old_bucket
, sizeof (struct sbucket
));
192 new_bucket
->version
.version
= array
->version
.version
;
193 *the_bucket
= new_bucket
; /* Prepared for install. */
197 (*the_bucket
)->elems
[eoffset
] = element
;
201 sarray_at_put_safe (struct sarray
*array
, sidx index
, void *element
)
203 if (soffset_decode (index
) >= array
->capacity
)
204 sarray_realloc (array
, soffset_decode (index
) + 1);
205 sarray_at_put (array
, index
, element
);
209 sarray_new (int size
, void *default_element
)
213 size_t num_indices
= ((size
- 1)/(INDEX_CAPACITY
)) + 1;
214 struct sindex
**new_indices
;
215 #else /* OBJC_SPARSE2 */
216 size_t num_indices
= ((size
- 1)/BUCKET_SIZE
) + 1;
217 struct sbucket
**new_buckets
;
223 /* Allocate core array. */
224 arr
= (struct sarray
*) objc_malloc (sizeof (struct sarray
));
225 arr
->version
.version
= 0;
227 /* Initialize members. */
229 arr
->capacity
= num_indices
*INDEX_CAPACITY
;
230 new_indices
= (struct sindex
**)
231 objc_malloc (sizeof (struct sindex
*) * num_indices
);
233 arr
->empty_index
= (struct sindex
*) objc_malloc (sizeof (struct sindex
));
234 arr
->empty_index
->version
.version
= 0;
237 idxsize
+= num_indices
;
240 #else /* OBJC_SPARSE2 */
241 arr
->capacity
= num_indices
*BUCKET_SIZE
;
242 new_buckets
= (struct sbucket
**)
243 objc_malloc (sizeof (struct sbucket
*) * num_indices
);
246 idxsize
+= num_indices
;
250 arr
->empty_bucket
= (struct sbucket
*) objc_malloc (sizeof (struct sbucket
));
251 arr
->empty_bucket
->version
.version
= 0;
256 arr
->is_copy_of
= (struct sarray
*) 0;
258 for (counter
= 0; counter
< BUCKET_SIZE
; counter
++)
259 arr
->empty_bucket
->elems
[counter
] = default_element
;
262 for (counter
= 0; counter
< INDEX_SIZE
; counter
++)
263 arr
->empty_index
->buckets
[counter
] = arr
->empty_bucket
;
265 for (counter
= 0; counter
< num_indices
; counter
++)
266 new_indices
[counter
] = arr
->empty_index
;
268 #else /* OBJC_SPARSE2 */
270 for (counter
= 0; counter
< num_indices
; counter
++)
271 new_buckets
[counter
] = arr
->empty_bucket
;
276 arr
->indices
= new_indices
;
277 #else /* OBJC_SPARSE2 */
278 arr
->buckets
= new_buckets
;
285 /* Reallocate the sparse array to hold `newsize' entries Note: We
286 really allocate and then free. We have to do this to ensure that
287 any concurrent readers notice the update. */
289 sarray_realloc (struct sarray
*array
, int newsize
)
292 size_t old_max_index
= (array
->capacity
- 1)/INDEX_CAPACITY
;
293 size_t new_max_index
= ((newsize
- 1)/INDEX_CAPACITY
);
294 size_t rounded_size
= (new_max_index
+ 1) * INDEX_CAPACITY
;
296 struct sindex
**new_indices
;
297 struct sindex
**old_indices
;
299 #else /* OBJC_SPARSE2 */
300 size_t old_max_index
= (array
->capacity
- 1)/BUCKET_SIZE
;
301 size_t new_max_index
= ((newsize
- 1)/BUCKET_SIZE
);
302 size_t rounded_size
= (new_max_index
+ 1) * BUCKET_SIZE
;
304 struct sbucket
**new_buckets
;
305 struct sbucket
**old_buckets
;
311 assert (newsize
> 0);
313 /* The size is the same, just ignore the request. */
314 if (rounded_size
<= array
->capacity
)
317 assert (array
->ref_count
== 1); /* stop if lazy copied... */
319 /* We are asked to extend the array -- allocate new bucket table,
320 and insert empty_bucket in newly allocated places. */
321 if (rounded_size
> array
->capacity
)
325 rounded_size
= (new_max_index
+ 1) * INDEX_CAPACITY
;
326 #else /* OBJC_SPARSE2 */
328 rounded_size
= (new_max_index
+ 1) * BUCKET_SIZE
;
331 /* Update capacity. */
332 array
->capacity
= rounded_size
;
335 /* Alloc to force re-read by any concurrent readers. */
336 old_indices
= array
->indices
;
337 new_indices
= (struct sindex
**)
338 objc_malloc ((new_max_index
+ 1) * sizeof (struct sindex
*));
339 #else /* OBJC_SPARSE2 */
340 old_buckets
= array
->buckets
;
341 new_buckets
= (struct sbucket
**)
342 objc_malloc ((new_max_index
+ 1) * sizeof (struct sbucket
*));
345 /* Copy buckets below old_max_index (they are still valid). */
346 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 */
387 sarray_free (struct sarray
*array
) {
389 size_t old_max_index
= (array
->capacity
- 1)/INDEX_CAPACITY
;
390 struct sindex
**old_indices
;
392 size_t old_max_index
= (array
->capacity
- 1)/BUCKET_SIZE
;
393 struct sbucket
**old_buckets
;
397 assert (array
->ref_count
!= 0); /* Freed multiple times!!! */
399 if (--(array
->ref_count
) != 0) /* There exists copies of me */
403 old_indices
= array
->indices
;
405 old_buckets
= array
->buckets
;
408 /* Free all entries that do not point to empty_bucket. */
409 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
))
417 for (c2
= 0; c2
< INDEX_SIZE
; c2
++)
419 struct sbucket
*bkt
= idx
->buckets
[c2
];
420 if ((bkt
!= array
->empty_bucket
)
421 && (bkt
->version
.version
== array
->version
.version
))
423 sarray_free_garbage (bkt
);
427 sarray_free_garbage (idx
);
430 #else /* OBJC_SPARSE2 */
431 struct sbucket
*bkt
= old_buckets
[counter
];
432 if ((bkt
!= array
->empty_bucket
)
433 && (bkt
->version
.version
== array
->version
.version
))
435 sarray_free_garbage (bkt
);
442 /* Free empty_index. */
443 if (array
->empty_index
->version
.version
== array
->version
.version
)
445 sarray_free_garbage (array
->empty_index
);
450 /* Free empty_bucket. */
451 if (array
->empty_bucket
->version
.version
== array
->version
.version
)
453 sarray_free_garbage (array
->empty_bucket
);
456 idxsize
-= (old_max_index
+ 1);
460 /* Free bucket table. */
461 sarray_free_garbage (array
->indices
);
463 /* Free bucket table. */
464 sarray_free_garbage (array
->buckets
);
467 /* If this is a copy of another array, we free it (which might just
468 decrement its reference count so it will be freed when no longer
470 if (array
->is_copy_of
)
471 sarray_free (array
->is_copy_of
);
474 sarray_free_garbage (array
);
477 /* This is a lazy copy. Only the core of the structure is actually
480 sarray_lazy_copy (struct sarray
*oarr
)
485 size_t num_indices
= ((oarr
->capacity
- 1)/INDEX_CAPACITY
) + 1;
486 struct sindex
**new_indices
;
487 #else /* OBJC_SPARSE2 */
488 size_t num_indices
= ((oarr
->capacity
- 1)/BUCKET_SIZE
) + 1;
489 struct sbucket
**new_buckets
;
492 /* Allocate core array. */
493 arr
= (struct sarray
*) objc_malloc (sizeof (struct sarray
)); /* !!! */
494 arr
->version
.version
= oarr
->version
.version
+ 1;
496 arr
->empty_index
= oarr
->empty_index
;
498 arr
->empty_bucket
= oarr
->empty_bucket
;
500 oarr
->ref_count
+= 1;
501 arr
->is_copy_of
= oarr
;
502 arr
->capacity
= oarr
->capacity
;
505 /* Copy bucket table. */
506 new_indices
= (struct sindex
**)
507 objc_malloc (sizeof (struct sindex
*) * num_indices
);
508 memcpy (new_indices
, oarr
->indices
, sizeof (struct sindex
*) * num_indices
);
509 arr
->indices
= new_indices
;
511 /* Copy bucket table. */
512 new_buckets
= (struct sbucket
**)
513 objc_malloc (sizeof (struct sbucket
*) * num_indices
);
514 memcpy (new_buckets
, oarr
->buckets
, sizeof (struct sbucket
*) * num_indices
);
515 arr
->buckets
= new_buckets
;
518 idxsize
+= num_indices
;