OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libobjc/] [sarray.c] - Blame information for rev 772

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 739 jeremybenn
/* 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
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.