3 * Copyright (C) 2002-2008, Parrot Foundation.
4 * License: Artistic 2.0, see README and LICENSE for details
8 * list aka array routines for Parrot
12 #include "parrot/parrot.h"
14 #ifndef PARROT_LIST_H_GUARD
15 #define PARROT_LIST_H_GUARD
17 typedef struct List_chunk
{
18 Buffer data
; /* item store, Buffer must be first element in struct*/
19 struct List_chunk
*next
;
20 struct List_chunk
*prev
;
21 UINTVAL flags
; /* chunk flags */
22 UINTVAL items
; /* items in this chunk */
23 UINTVAL n_chunks
; /* # of chunks with grow policy in flags */
24 UINTVAL n_items
; /* # of items with grow policy in flags */
27 #define sparse PObj_private0_FLAG
28 #define no_power_2 PObj_private1_FLAG
29 #define fixed_items PObj_private2_FLAG
30 #define grow_items PObj_private3_FLAG
33 Buffer chunk_list
; /* pointers to chunks */
34 PMC
*container
; /* the Array PMC */
35 List_chunk
*first
; /* first chunk holding data */
36 List_chunk
*last
; /* last chunk */
37 UINTVAL length
; /* number of items in list */
38 UINTVAL start
; /* offset, where array[0] is */
39 PARROT_DATA_TYPE item_type
; /* item type */
40 UINTVAL cap
; /* list capacity in items */
41 UINTVAL collect_runs
; /* counter, when chunklist was built */
42 UINTVAL n_chunks
; /* number of chunks */
43 int grow_policy
; /* fixed / variable len */
44 int items_per_chunk
; /* override defaults */
45 int item_size
; /* item size */
49 enum_grow_unknown
, /* at beginning, or after emptying list */
50 enum_grow_mixed
= 1, /* other */
51 enum_grow_fixed
= fixed_items
, /* fixed maximum size */
52 enum_grow_growing
= grow_items
/* growing at begin of list */
56 enum_add_at_start
, /* don't swap these */
62 # define MIN_ITEMS 4 /* smallest chunk can hold */
63 # define LD_MAX 4 /* log2(MAX_ITEMS) */
64 # define MAX_ITEMS 16 /* biggest chunk can hold */
66 # define MIN_ITEMS 16 /* smallest chunk can hold */
67 # define LD_MAX 10 /* log2(MAX_ITEMS) */
68 # define MAX_ITEMS 1024 /* biggest chunk can hold */
69 #endif /* LIST_TEST */
70 #define MAX_MASK (MAX_ITEMS-1)
73 * bigger MAX_ITEMS didn't improve much in my tests
74 * 10^6 list_get, MAX_ITEMS 1024: 0.34s, 2048: 0.33s
78 /* HEADERIZER BEGIN: src/list.c */
79 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
83 PARROT_WARN_UNUSED_RESULT
84 UINTVAL
ld(UINTVAL x
);
87 void Parrot_pmc_array_assign(PARROT_INTERP
,
90 ARGIN_NULLOK(void *item
),
92 __attribute__nonnull__(1)
93 __attribute__nonnull__(2)
97 PARROT_WARN_UNUSED_RESULT
98 PARROT_CANNOT_RETURN_NULL
99 List
* Parrot_pmc_array_clone(PARROT_INTERP
, ARGIN(const List
*other
))
100 __attribute__nonnull__(1)
101 __attribute__nonnull__(2);
104 void Parrot_pmc_array_delete(PARROT_INTERP
,
108 __attribute__nonnull__(1)
109 __attribute__nonnull__(2)
110 FUNC_MODIFIES(*list
);
113 PARROT_CAN_RETURN_NULL
114 PARROT_WARN_UNUSED_RESULT
115 void * Parrot_pmc_array_get(PARROT_INTERP
,
119 __attribute__nonnull__(1)
120 __attribute__nonnull__(2)
121 FUNC_MODIFIES(*list
);
124 void Parrot_pmc_array_insert(PARROT_INTERP
,
128 __attribute__nonnull__(1)
129 __attribute__nonnull__(2)
130 FUNC_MODIFIES(*list
);
133 void Parrot_pmc_array_mark(PARROT_INTERP
, ARGMOD(List
*list
))
134 __attribute__nonnull__(1)
135 __attribute__nonnull__(2)
136 FUNC_MODIFIES(*list
);
139 PARROT_WARN_UNUSED_RESULT
140 PARROT_CANNOT_RETURN_NULL
141 List
* Parrot_pmc_array_new(PARROT_INTERP
, PARROT_DATA_TYPE type
)
142 __attribute__nonnull__(1);
145 PARROT_WARN_UNUSED_RESULT
146 PARROT_CANNOT_RETURN_NULL
147 List
* Parrot_pmc_array_new_init(PARROT_INTERP
,
148 PARROT_DATA_TYPE type
,
150 __attribute__nonnull__(1)
151 __attribute__nonnull__(3);
154 void Parrot_pmc_array_pmc_new(PARROT_INTERP
, ARGMOD(PMC
*container
))
155 __attribute__nonnull__(1)
156 __attribute__nonnull__(2)
157 FUNC_MODIFIES(*container
);
160 void Parrot_pmc_array_pmc_new_init(PARROT_INTERP
,
161 ARGMOD(PMC
*container
),
163 __attribute__nonnull__(1)
164 __attribute__nonnull__(2)
165 __attribute__nonnull__(3)
166 FUNC_MODIFIES(*container
);
169 PARROT_CAN_RETURN_NULL
170 void * Parrot_pmc_array_pop(PARROT_INTERP
, ARGMOD(List
*list
), int type
)
171 __attribute__nonnull__(1)
172 __attribute__nonnull__(2)
173 FUNC_MODIFIES(*list
);
176 void Parrot_pmc_array_push(PARROT_INTERP
,
178 ARGIN_NULLOK(void *item
),
180 __attribute__nonnull__(1)
181 __attribute__nonnull__(2)
182 FUNC_MODIFIES(*list
);
185 void Parrot_pmc_array_set_length(PARROT_INTERP
,
188 __attribute__nonnull__(1)
189 __attribute__nonnull__(2)
190 FUNC_MODIFIES(*list
);
193 PARROT_CAN_RETURN_NULL
194 void * Parrot_pmc_array_shift(PARROT_INTERP
, ARGMOD(List
*list
), int type
)
195 __attribute__nonnull__(1)
196 __attribute__nonnull__(2)
197 FUNC_MODIFIES(*list
);
200 void Parrot_pmc_array_splice(PARROT_INTERP
,
202 ARGMOD_NULLOK(List
*value_list
),
205 __attribute__nonnull__(1)
206 __attribute__nonnull__(2)
208 FUNC_MODIFIES(*value_list
);
211 void Parrot_pmc_array_unshift(PARROT_INTERP
,
215 __attribute__nonnull__(1)
216 __attribute__nonnull__(2)
217 __attribute__nonnull__(3)
218 FUNC_MODIFIES(*list
);
221 void Parrot_pmc_array_visit(PARROT_INTERP
,
224 __attribute__nonnull__(1)
225 __attribute__nonnull__(2)
226 __attribute__nonnull__(3)
227 FUNC_MODIFIES(*pinfo
);
229 PARROT_WARN_UNUSED_RESULT
231 INTVAL
Parrot_pmc_array_length(SHIM_INTERP
, ARGIN(const List
*list
))
232 __attribute__nonnull__(2);
234 #define ASSERT_ARGS_ld __attribute__unused__ int _ASSERT_ARGS_CHECK = (0)
235 #define ASSERT_ARGS_Parrot_pmc_array_assign __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
236 PARROT_ASSERT_ARG(interp) \
237 , PARROT_ASSERT_ARG(list))
238 #define ASSERT_ARGS_Parrot_pmc_array_clone __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
239 PARROT_ASSERT_ARG(interp) \
240 , PARROT_ASSERT_ARG(other))
241 #define ASSERT_ARGS_Parrot_pmc_array_delete __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
242 PARROT_ASSERT_ARG(interp) \
243 , PARROT_ASSERT_ARG(list))
244 #define ASSERT_ARGS_Parrot_pmc_array_get __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
245 PARROT_ASSERT_ARG(interp) \
246 , PARROT_ASSERT_ARG(list))
247 #define ASSERT_ARGS_Parrot_pmc_array_insert __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
248 PARROT_ASSERT_ARG(interp) \
249 , PARROT_ASSERT_ARG(list))
250 #define ASSERT_ARGS_Parrot_pmc_array_mark __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
251 PARROT_ASSERT_ARG(interp) \
252 , PARROT_ASSERT_ARG(list))
253 #define ASSERT_ARGS_Parrot_pmc_array_new __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
254 PARROT_ASSERT_ARG(interp))
255 #define ASSERT_ARGS_Parrot_pmc_array_new_init __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
256 PARROT_ASSERT_ARG(interp) \
257 , PARROT_ASSERT_ARG(init))
258 #define ASSERT_ARGS_Parrot_pmc_array_pmc_new __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
259 PARROT_ASSERT_ARG(interp) \
260 , PARROT_ASSERT_ARG(container))
261 #define ASSERT_ARGS_Parrot_pmc_array_pmc_new_init __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
262 PARROT_ASSERT_ARG(interp) \
263 , PARROT_ASSERT_ARG(container) \
264 , PARROT_ASSERT_ARG(init))
265 #define ASSERT_ARGS_Parrot_pmc_array_pop __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
266 PARROT_ASSERT_ARG(interp) \
267 , PARROT_ASSERT_ARG(list))
268 #define ASSERT_ARGS_Parrot_pmc_array_push __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
269 PARROT_ASSERT_ARG(interp) \
270 , PARROT_ASSERT_ARG(list))
271 #define ASSERT_ARGS_Parrot_pmc_array_set_length __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
272 PARROT_ASSERT_ARG(interp) \
273 , PARROT_ASSERT_ARG(list))
274 #define ASSERT_ARGS_Parrot_pmc_array_shift __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
275 PARROT_ASSERT_ARG(interp) \
276 , PARROT_ASSERT_ARG(list))
277 #define ASSERT_ARGS_Parrot_pmc_array_splice __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
278 PARROT_ASSERT_ARG(interp) \
279 , PARROT_ASSERT_ARG(list))
280 #define ASSERT_ARGS_Parrot_pmc_array_unshift __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
281 PARROT_ASSERT_ARG(interp) \
282 , PARROT_ASSERT_ARG(list) \
283 , PARROT_ASSERT_ARG(item))
284 #define ASSERT_ARGS_Parrot_pmc_array_visit __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
285 PARROT_ASSERT_ARG(interp) \
286 , PARROT_ASSERT_ARG(list) \
287 , PARROT_ASSERT_ARG(pinfo))
288 #define ASSERT_ARGS_Parrot_pmc_array_length __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
289 PARROT_ASSERT_ARG(list))
290 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
291 /* HEADERIZER END: src/list.c */
293 #endif /* PARROT_LIST_H_GUARD */
298 * c-file-style: "parrot"
300 * vim: expandtab shiftwidth=4: