xref: /dragonfly/contrib/gcc-4.7/libobjc/sarray.c (revision 25a2db75)
1 /* Sparse Arrays for Objective C dispatch tables
2    Copyright (C) 1993, 1995, 1996, 2002, 2004, 2009, 2010
3    Free Software Foundation, Inc.
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11 
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16 
17 Under Section 7 of GPL version 3, you are granted additional
18 permissions described in the GCC Runtime Library Exception, version
19 3.1, as published by the Free Software Foundation.
20 
21 You should have received a copy of the GNU General Public License and
22 a copy of the GCC Runtime Library Exception along with this program;
23 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 <http://www.gnu.org/licenses/>.  */
25 
26 #include "objc-private/common.h"
27 #include "objc-private/sarray.h"
28 #include "objc/runtime.h" /* For objc_malloc */
29 #include "objc/thr.h"     /* For objc_mutex_lock */
30 #include "objc-private/module-abi-8.h"
31 #include "objc-private/runtime.h"
32 #include <stdio.h>
33 #include <string.h> /* For memset */
34 #include <assert.h> /* For assert */
35 
36 int nbuckets = 0;					/* !T:MUTEX */
37 int nindices = 0;					/* !T:MUTEX */
38 int narrays = 0;					/* !T:MUTEX */
39 int idxsize = 0;					/* !T:MUTEX */
40 
41 static void *first_free_data = NULL;			/* !T:MUTEX */
42 
43 #ifdef OBJC_SPARSE2
44 const char *__objc_sparse2_id = "2 level sparse indices";
45 #endif
46 
47 #ifdef OBJC_SPARSE3
48 const char *__objc_sparse3_id = "3 level sparse indices";
49 #endif
50 
51 /* This function removes any structures left over from free operations
52    that were not safe in a multi-threaded environment. */
53 void
54 sarray_remove_garbage (void)
55 {
56   void **vp;
57   void *np;
58 
59   objc_mutex_lock (__objc_runtime_mutex);
60 
61   vp = first_free_data;
62   first_free_data = NULL;
63 
64   while (vp)
65     {
66       np = *vp;
67       objc_free (vp);
68       vp = np;
69     }
70 
71   objc_mutex_unlock (__objc_runtime_mutex);
72 }
73 
74 /* Free a block of dynamically allocated memory.  If we are in
75    multi-threaded mode, it is ok to free it.  If not, we add it to the
76    garbage heap to be freed later. */
77 static void
78 sarray_free_garbage (void *vp)
79 {
80   objc_mutex_lock (__objc_runtime_mutex);
81 
82   if (__objc_runtime_threads_alive == 1)
83     {
84       objc_free (vp);
85       if (first_free_data)
86 	sarray_remove_garbage ();
87     }
88   else
89     {
90       *(void **)vp = first_free_data;
91       first_free_data = vp;
92     }
93 
94   objc_mutex_unlock (__objc_runtime_mutex);
95 }
96 
97 /* sarray_at_put copies data in such a way as to be thread reader
98    safe.  */
99 void
100 sarray_at_put (struct sarray *array, sidx index, void *element)
101 {
102 #ifdef OBJC_SPARSE3
103   struct sindex **the_index;
104   struct sindex *new_index;
105 #endif
106   struct sbucket **the_bucket;
107   struct sbucket *new_bucket;
108 #ifdef OBJC_SPARSE3
109   size_t ioffset;
110 #endif
111   size_t boffset;
112   size_t eoffset;
113 #ifdef PRECOMPUTE_SELECTORS
114   union sofftype xx;
115   xx.idx = index;
116 #ifdef OBJC_SPARSE3
117   ioffset = xx.off.ioffset;
118 #endif
119   boffset = xx.off.boffset;
120   eoffset = xx.off.eoffset;
121 #else /* not PRECOMPUTE_SELECTORS */
122 #ifdef OBJC_SPARSE3
123   ioffset = index/INDEX_CAPACITY;
124   boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
125   eoffset = index%BUCKET_SIZE;
126 #else
127   boffset = index/BUCKET_SIZE;
128   eoffset = index%BUCKET_SIZE;
129 #endif
130 #endif /* not PRECOMPUTE_SELECTORS */
131 
132   assert (soffset_decode (index) < array->capacity); /* Range check */
133 
134 #ifdef OBJC_SPARSE3
135   the_index = &(array->indices[ioffset]);
136   the_bucket = &((*the_index)->buckets[boffset]);
137 #else
138   the_bucket = &(array->buckets[boffset]);
139 #endif
140 
141   if ((*the_bucket)->elems[eoffset] == element)
142     return;		/* Great! we just avoided a lazy copy.  */
143 
144 #ifdef OBJC_SPARSE3
145 
146   /* First, perform lazy copy/allocation of index if needed.  */
147 
148   if ((*the_index) == array->empty_index)
149     {
150       /* The index was previously empty, allocate a new.  */
151       new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
152       memcpy (new_index, array->empty_index, sizeof (struct sindex));
153       new_index->version.version = array->version.version;
154       *the_index = new_index;                     /* Prepared for install. */
155       the_bucket = &((*the_index)->buckets[boffset]);
156 
157       nindices += 1;
158     }
159   else if ((*the_index)->version.version != array->version.version)
160     {
161       /* This index must be lazy copied.  */
162       struct sindex *old_index = *the_index;
163       new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
164       memcpy (new_index, old_index, sizeof (struct sindex));
165       new_index->version.version = array->version.version;
166       *the_index = new_index;                     /* Prepared for install. */
167       the_bucket = &((*the_index)->buckets[boffset]);
168 
169       nindices += 1;
170     }
171 
172 #endif /* OBJC_SPARSE3 */
173 
174   /* Next, perform lazy allocation/copy of the bucket if needed.  */
175   if ((*the_bucket) == array->empty_bucket)
176     {
177       /* The bucket was previously empty (or something like that),
178 	 allocate a new.  This is the effect of `lazy' allocation.  */
179       new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
180       memcpy ((void *) new_bucket, (const void *) array->empty_bucket,
181 	      sizeof (struct sbucket));
182       new_bucket->version.version = array->version.version;
183       *the_bucket = new_bucket;                   /* Prepared for install. */
184 
185       nbuckets += 1;
186 
187     }
188   else if ((*the_bucket)->version.version != array->version.version)
189     {
190       /* Perform lazy copy.  */
191       struct sbucket *old_bucket = *the_bucket;
192       new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
193       memcpy (new_bucket, old_bucket, sizeof (struct sbucket));
194       new_bucket->version.version = array->version.version;
195       *the_bucket = new_bucket;                   /* Prepared for install. */
196 
197       nbuckets += 1;
198     }
199   (*the_bucket)->elems[eoffset] = element;
200 }
201 
202 void
203 sarray_at_put_safe (struct sarray *array, sidx index, void *element)
204 {
205   if (soffset_decode (index) >= array->capacity)
206     sarray_realloc (array, soffset_decode (index) + 1);
207   sarray_at_put (array, index, element);
208 }
209 
210 struct sarray *
211 sarray_new (int size, void *default_element)
212 {
213   struct sarray *arr;
214 #ifdef OBJC_SPARSE3
215   size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1;
216   struct sindex **new_indices;
217 #else /* OBJC_SPARSE2 */
218   size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1;
219   struct sbucket **new_buckets;
220 #endif
221   size_t counter;
222 
223   assert (size > 0);
224 
225   /* Allocate core array.  */
226   arr = (struct sarray *) objc_malloc (sizeof (struct sarray));
227   arr->version.version = 0;
228 
229   /* Initialize members.  */
230 #ifdef OBJC_SPARSE3
231   arr->capacity = num_indices*INDEX_CAPACITY;
232   new_indices = (struct sindex **)
233     objc_malloc (sizeof (struct sindex *) * num_indices);
234 
235   arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
236   arr->empty_index->version.version = 0;
237 
238   narrays  += 1;
239   idxsize  += num_indices;
240   nindices += 1;
241 
242 #else /* OBJC_SPARSE2 */
243   arr->capacity = num_indices*BUCKET_SIZE;
244   new_buckets = (struct sbucket **)
245     objc_malloc (sizeof (struct sbucket *) * num_indices);
246 
247   narrays  += 1;
248   idxsize  += num_indices;
249 
250 #endif
251 
252   arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
253   arr->empty_bucket->version.version = 0;
254 
255   nbuckets += 1;
256 
257   arr->ref_count = 1;
258   arr->is_copy_of = (struct sarray *) 0;
259 
260   for (counter = 0; counter < BUCKET_SIZE; counter++)
261     arr->empty_bucket->elems[counter] = default_element;
262 
263 #ifdef OBJC_SPARSE3
264   for (counter = 0; counter < INDEX_SIZE; counter++)
265     arr->empty_index->buckets[counter] = arr->empty_bucket;
266 
267   for (counter = 0; counter < num_indices; counter++)
268     new_indices[counter] = arr->empty_index;
269 
270 #else /* OBJC_SPARSE2 */
271 
272   for (counter = 0; counter < num_indices; counter++)
273     new_buckets[counter] = arr->empty_bucket;
274 
275 #endif
276 
277 #ifdef OBJC_SPARSE3
278   arr->indices = new_indices;
279 #else /* OBJC_SPARSE2 */
280   arr->buckets = new_buckets;
281 #endif
282 
283   return arr;
284 }
285 
286 
287 /* Reallocate the sparse array to hold `newsize' entries Note: We
288    really allocate and then free.  We have to do this to ensure that
289    any concurrent readers notice the update.  */
290 void
291 sarray_realloc (struct sarray *array, int newsize)
292 {
293 #ifdef OBJC_SPARSE3
294   size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
295   size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY);
296   size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
297 
298   struct sindex **new_indices;
299   struct sindex **old_indices;
300 
301 #else /* OBJC_SPARSE2 */
302   size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
303   size_t new_max_index = ((newsize - 1)/BUCKET_SIZE);
304   size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE;
305 
306   struct sbucket **new_buckets;
307   struct sbucket **old_buckets;
308 
309 #endif
310 
311   size_t counter;
312 
313   assert (newsize > 0);
314 
315   /* The size is the same, just ignore the request.  */
316   if (rounded_size <= array->capacity)
317     return;
318 
319   assert (array->ref_count == 1);	/* stop if lazy copied... */
320 
321   /* We are asked to extend the array -- allocate new bucket table,
322      and insert empty_bucket in newly allocated places.  */
323   if (rounded_size > array->capacity)
324     {
325 #ifdef OBJC_SPARSE3
326       new_max_index += 4;
327       rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
328 #else /* OBJC_SPARSE2 */
329       new_max_index += 4;
330       rounded_size = (new_max_index + 1) * BUCKET_SIZE;
331 #endif
332 
333       /* Update capacity.  */
334       array->capacity = rounded_size;
335 
336 #ifdef OBJC_SPARSE3
337       /* Alloc to force re-read by any concurrent readers.  */
338       old_indices = array->indices;
339       new_indices = (struct sindex **)
340 	objc_malloc ((new_max_index + 1) * sizeof (struct sindex *));
341 #else /* OBJC_SPARSE2 */
342       old_buckets = array->buckets;
343       new_buckets = (struct sbucket **)
344 	objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *));
345 #endif
346 
347       /* Copy buckets below old_max_index (they are still valid).  */
348       for (counter = 0; counter <= old_max_index; counter++ )
349 	{
350 #ifdef OBJC_SPARSE3
351 	  new_indices[counter] = old_indices[counter];
352 #else /* OBJC_SPARSE2 */
353 	  new_buckets[counter] = old_buckets[counter];
354 #endif
355 	}
356 
357 #ifdef OBJC_SPARSE3
358       /* Reset entries above old_max_index to empty_bucket.  */
359       for (counter = old_max_index + 1; counter <= new_max_index; counter++)
360 	new_indices[counter] = array->empty_index;
361 #else /* OBJC_SPARSE2 */
362       /* Reset entries above old_max_index to empty_bucket.  */
363       for (counter = old_max_index + 1; counter <= new_max_index; counter++)
364 	new_buckets[counter] = array->empty_bucket;
365 #endif
366 
367 #ifdef OBJC_SPARSE3
368       /* Install the new indices.  */
369       array->indices = new_indices;
370 #else /* OBJC_SPARSE2 */
371       array->buckets = new_buckets;
372 #endif
373 
374 #ifdef OBJC_SPARSE3
375       /* Free the old indices.  */
376       sarray_free_garbage (old_indices);
377 #else /* OBJC_SPARSE2 */
378       sarray_free_garbage (old_buckets);
379 #endif
380 
381       idxsize += (new_max_index-old_max_index);
382       return;
383     }
384 }
385 
386 
387 /* Free a sparse array allocated with sarray_new */
388 void
389 sarray_free (struct sarray *array) {
390 #ifdef OBJC_SPARSE3
391   size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
392   struct sindex **old_indices;
393 #else
394   size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
395   struct sbucket **old_buckets;
396 #endif
397   size_t counter = 0;
398 
399   assert (array->ref_count != 0);	/* Freed multiple times!!! */
400 
401   if (--(array->ref_count) != 0)	/* There exists copies of me */
402     return;
403 
404 #ifdef OBJC_SPARSE3
405   old_indices = array->indices;
406 #else
407   old_buckets = array->buckets;
408 #endif
409 
410   /* Free all entries that do not point to empty_bucket.  */
411   for (counter = 0; counter <= old_max_index; counter++ )
412     {
413 #ifdef OBJC_SPARSE3
414       struct sindex *idx = old_indices[counter];
415       if ((idx != array->empty_index)
416 	  && (idx->version.version == array->version.version))
417 	{
418 	  int c2;
419 	  for (c2 = 0; c2 < INDEX_SIZE; c2++)
420 	    {
421 	      struct sbucket *bkt = idx->buckets[c2];
422 	      if ((bkt != array->empty_bucket)
423 		  && (bkt->version.version == array->version.version))
424 		{
425 		  sarray_free_garbage (bkt);
426 		  nbuckets -= 1;
427 		}
428 	    }
429 	  sarray_free_garbage (idx);
430 	  nindices -= 1;
431 	}
432 #else /* OBJC_SPARSE2 */
433       struct sbucket *bkt = old_buckets[counter];
434       if ((bkt != array->empty_bucket)
435 	  && (bkt->version.version == array->version.version))
436 	{
437 	  sarray_free_garbage (bkt);
438 	  nbuckets -= 1;
439 	}
440 #endif
441     }
442 
443 #ifdef OBJC_SPARSE3
444   /* Free empty_index.  */
445   if (array->empty_index->version.version == array->version.version)
446     {
447       sarray_free_garbage (array->empty_index);
448       nindices -= 1;
449     }
450 #endif
451 
452   /* Free empty_bucket.  */
453   if (array->empty_bucket->version.version == array->version.version)
454     {
455       sarray_free_garbage (array->empty_bucket);
456       nbuckets -= 1;
457     }
458   idxsize -= (old_max_index + 1);
459   narrays -= 1;
460 
461 #ifdef OBJC_SPARSE3
462   /* Free bucket table.  */
463   sarray_free_garbage (array->indices);
464 #else
465   /* Free bucket table.  */
466   sarray_free_garbage (array->buckets);
467 #endif
468 
469   /* If this is a copy of another array, we free it (which might just
470      decrement its reference count so it will be freed when no longer
471      in use).  */
472   if (array->is_copy_of)
473     sarray_free (array->is_copy_of);
474 
475   /* Free array.  */
476   sarray_free_garbage (array);
477 }
478 
479 /* This is a lazy copy.  Only the core of the structure is actually
480    copied.  */
481 struct sarray *
482 sarray_lazy_copy (struct sarray *oarr)
483 {
484   struct sarray *arr;
485 
486 #ifdef OBJC_SPARSE3
487   size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1;
488   struct sindex **new_indices;
489 #else /* OBJC_SPARSE2 */
490   size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1;
491   struct sbucket **new_buckets;
492 #endif
493 
494   /* Allocate core array.  */
495   arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */
496   arr->version.version = oarr->version.version + 1;
497 #ifdef OBJC_SPARSE3
498   arr->empty_index = oarr->empty_index;
499 #endif
500   arr->empty_bucket = oarr->empty_bucket;
501   arr->ref_count = 1;
502   oarr->ref_count += 1;
503   arr->is_copy_of = oarr;
504   arr->capacity = oarr->capacity;
505 
506 #ifdef OBJC_SPARSE3
507   /* Copy bucket table.  */
508   new_indices = (struct sindex **)
509     objc_malloc (sizeof (struct sindex *) * num_indices);
510   memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices);
511   arr->indices = new_indices;
512 #else
513   /* Copy bucket table.  */
514   new_buckets = (struct sbucket **)
515     objc_malloc (sizeof (struct sbucket *) * num_indices);
516   memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices);
517   arr->buckets = new_buckets;
518 #endif
519 
520   idxsize += num_indices;
521   narrays += 1;
522 
523   return arr;
524 }
525