OSDN Git Service

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