1 /*
2 Copyright (C) 2010-2012, Parrot Foundation.
3
4 =head1 NAME
5
6 include/parrot/pointer_array.h - Storage of pointers.
7
8 =head1 DESCRIPTION
9
10 Storage for pointers used in GC implementation.
11
12 Storage organized in 4KB chunks. Every cell in chunk either real pointer
13 or pointer to next free cell.
14
15 Lower bit in cell masked to indicate pointer-to-free-cell.
16
17 */
18
19 #ifndef PARROT_POINTER_ARRAY_H_GUARD
20 #define PARROT_POINTER_ARRAY_H_GUARD
21
22 #include <parrot/memory.h>
23
24 /* Calculate size of chunk data "header" */
25 #define CHUNK_SIZE 4096
26 #define CELL_PER_CHUNK ((CHUNK_SIZE - 2 * sizeof(size_t)) / sizeof (void *))
27
28 typedef struct Parrot_Pointer_Array_Chunk {
29 size_t num_free;
30 size_t next_free; /* Index of next free element within chunk */
31 void *data[CELL_PER_CHUNK];
32 } Parrot_Pointer_Array_Chunk;
33
34 typedef struct Parrot_Pointer_Array {
35 /* Next free cell (used after freeing some cells) */
36 /* "Look, ma! Pointer to pointer to void!!!" */
37 void **next_free;
38 /* Index of last used chunk */
39 size_t current_chunk;
40 /* Total number of allocated chunks */
41 size_t total_chunks;
42
43 Parrot_Pointer_Array_Chunk **chunks;
44 } Parrot_Pointer_Array;
45
46 /* Poor man C++ templating... */
47 #define POINTER_ARRAY_ITER(_array, _code) \
48 do { \
49 size_t _i; \
50 for (_i = 0; _i < (_array)->total_chunks; _i++) { \
51 Parrot_Pointer_Array_Chunk *chunk = (_array)->chunks[_i]; \
52 size_t _j; \
53 \
54 for (_j = 0; _j < CELL_PER_CHUNK - chunk->num_free; _j++) { \
55 void *ptr = chunk->data[_j]; \
56 if ((ptrcast_t)(ptr) & 1) \
57 continue; \
58 \
59 { _code } \
60 } \
61 } \
62 } while (0);
63
64 /*
65
66 Inline functions for faster access.
67
68 */
69
70
71 /*
72
73 =over 4
74
75 =item C<static void * Parrot_pa_insert(Parrot_Pointer_Array *self, void *ptr)>
76
77 Insert pointer into the array.
78
79 =cut
80
81 */
82
83 static
84 PARROT_INLINE
85 void *
Parrot_pa_insert(ARGMOD (Parrot_Pointer_Array * self),ARGIN (void * ptr))86 Parrot_pa_insert(ARGMOD(Parrot_Pointer_Array *self), ARGIN(void *ptr))
87 {
88 void *ret;
89
90 /* Reuse removed cell */
91 if (self->next_free) {
92 void **next = (void**)((ptrcast_t)*self->next_free & ~1);
93 ret = self->next_free;
94 *self->next_free = ptr;
95 self->next_free = next;
96 }
97 else {
98 Parrot_Pointer_Array_Chunk *chunk;
99
100 /* If there is no free chunks */
101 if (self->current_chunk >= self->total_chunks
102 || !self->chunks[self->current_chunk]->num_free) {
103 self->current_chunk = self->total_chunks++;
104 mem_internal_realloc_n_typed(self->chunks,
105 self->total_chunks,
106 Parrot_Pointer_Array_Chunk*);
107 self->chunks[self->current_chunk] =
108 mem_internal_allocate_typed(Parrot_Pointer_Array_Chunk);
109 self->chunks[self->current_chunk]->num_free = CELL_PER_CHUNK;
110 self->chunks[self->current_chunk]->next_free = 0;
111 }
112
113 chunk = self->chunks[self->current_chunk];
114 --chunk->num_free;
115 /* Invariant: all chunks after chunk->next_free are free */
116 /* We handle previously freed chunks early */
117 ret = &chunk->data[chunk->next_free];
118 chunk->data[chunk->next_free++] = ptr;
119 }
120 return ret;
121 }
122
123 /*
124
125 =item C<static void Parrot_pa_remove(PARROT_INTERP, Parrot_Pointer_Array *self,
126 void *ptr)>
127
128 Remove pointer from array.
129
130 =back
131
132 =cut
133
134 */
135
136 static
137 PARROT_INLINE
138 void
Parrot_pa_remove(SHIM_INTERP,ARGIN (Parrot_Pointer_Array * self),ARGIN (void * ptr))139 Parrot_pa_remove(SHIM_INTERP, ARGIN(Parrot_Pointer_Array *self), ARGIN(void *ptr))
140 {
141 /* Mark cell to avoid iterating over */
142 *(void**)ptr = (void*)((ptrcast_t)self->next_free | 1);
143 self->next_free = (void**)ptr;
144 }
145
146
147 /* HEADERIZER BEGIN: src/pointer_array.c */
148 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
149
150 PARROT_EXPORT
151 void Parrot_pa_destroy(PARROT_INTERP, ARGFREE(Parrot_Pointer_Array *self));
152
153 PARROT_EXPORT
154 PARROT_WARN_UNUSED_RESULT
155 int Parrot_pa_is_owned(
156 ARGIN(const Parrot_Pointer_Array *self),
157 ARGIN(const void *orig),
158 ARGIN_NULLOK(const void *ref))
159 __attribute__nonnull__(1)
160 __attribute__nonnull__(2);
161
162 PARROT_EXPORT
163 PARROT_MALLOC
164 PARROT_CANNOT_RETURN_NULL
165 Parrot_Pointer_Array * Parrot_pa_new(PARROT_INTERP);
166
167 PARROT_WARN_UNUSED_RESULT
168 PARROT_PURE_FUNCTION
169 size_t Parrot_pa_count_allocated(PARROT_INTERP,
170 ARGIN(const Parrot_Pointer_Array *self))
171 __attribute__nonnull__(2);
172
173 PARROT_WARN_UNUSED_RESULT
174 size_t Parrot_pa_count_used(PARROT_INTERP,
175 ARGIN(const Parrot_Pointer_Array *self))
176 __attribute__nonnull__(2);
177
178 #define ASSERT_ARGS_Parrot_pa_destroy __attribute__unused__ int _ASSERT_ARGS_CHECK = (0)
179 #define ASSERT_ARGS_Parrot_pa_is_owned __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
180 PARROT_ASSERT_ARG(self) \
181 , PARROT_ASSERT_ARG(orig))
182 #define ASSERT_ARGS_Parrot_pa_new __attribute__unused__ int _ASSERT_ARGS_CHECK = (0)
183 #define ASSERT_ARGS_Parrot_pa_count_allocated __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
184 PARROT_ASSERT_ARG(self))
185 #define ASSERT_ARGS_Parrot_pa_count_used __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
186 PARROT_ASSERT_ARG(self))
187 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
188 /* HEADERIZER END: src/pointer_array.c */
189
190
191
192 #endif /* PARROT_POINTER_ARRAY_H_GUARD */
193
194 /*
195 * Local variables:
196 * c-file-style: "parrot"
197 * End:
198 * vim: expandtab shiftwidth=4 cinoptions='\:2=2' :
199 */
200