1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
/* Sparse Arrays for Objective C dispatch tables
Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc.
Contributed by Kresten Krab Thorup.
This file is part of GNU CC.
GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA. */
/* As a special exception, if you link this library with files
compiled with GCC to produce an executable, this does not cause
the resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why
the executable file might be covered by the GNU General Public License. */
#ifndef __sarray_INCLUDE_GNU
#define __sarray_INCLUDE_GNU
#include "objc/objc-decls.h"
objc_EXPORT const char* __objc_sparse2_id;
#include <stddef.h>
#include "objc/thr.h"
objc_EXPORT int nbuckets; /* for stats */
objc_EXPORT int nindices;
objc_EXPORT int narrays;
objc_EXPORT int idxsize;
#include <assert.h>
/* Buckets are 32 words each */
#define BUCKET_SIZE (1 << 6)
typedef size_t sidx;
union sversion {
int version;
void *next_free;
};
struct sbucket {
void* elems[BUCKET_SIZE]; /* elements stored in array */
union sversion version; /* used for copy-on-write */
};
struct sarray {
struct sbucket** buckets;
struct sbucket* empty_bucket;
union sversion version; /* used for copy-on-write */
short ref_count;
struct sarray *is_copy_of;
size_t capacity;
};
struct sarray* sarray_new (int size);
void sarray_free (struct sarray *array);
struct sarray* sarray_lazy_copy (struct sarray *array);
void sarray_realloc (struct sarray *array, int new_size);
void sarray_at_put_safe(struct sarray *array, sidx index, void* elem);
void sarray_remove_garbage(void);
/* implementation */
/* Get element from the Sparse array `array' at offset `index' */
static inline void* sarray_get_safe(struct sarray* array, sidx index)
{
return (index < array->capacity)
? array->buckets[index / BUCKET_SIZE]->elems[index % BUCKET_SIZE]
: array->empty_bucket->elems[0];
}
#endif /* __sarray_INCLUDE_GNU */
|
