3 * A pointer array list that doesn't require reallocs
5 * Copyright (C) 2016 Xamarin Inc
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Library General Public
9 * License 2.0 as published by the Free Software Foundation;
11 * This library 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 GNU
14 * Library General Public License for more details.
16 * You should have received a copy of the GNU Library General Public
17 * License 2.0 along with this library; if not, write to the Free
18 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
25 #include "mono/sgen/sgen-gc.h"
26 #include "mono/sgen/sgen-array-list.h"
29 sgen_array_list_grow (SgenArrayList *array, guint32 old_capacity)
31 const guint32 new_bucket = sgen_array_list_index_bucket (old_capacity);
32 const guint32 growth = sgen_array_list_bucket_size (new_bucket);
33 const guint32 new_capacity = old_capacity + growth;
34 const guint32 new_bucket_size = sizeof (**array->entries) * growth;
36 if (array->capacity >= new_capacity)
38 if (array->mem_type != -1)
39 entries = (gpointer*) sgen_alloc_internal_dynamic (new_bucket_size, array->mem_type, TRUE);
41 entries = (gpointer*) g_malloc0 (new_bucket_size);
42 if (array->bucket_alloc_callback)
43 array->bucket_alloc_callback (entries, new_bucket_size, TRUE);
45 * The zeroing of the newly allocated bucket must be complete before storing
46 * the new bucket pointer.
48 mono_memory_write_barrier ();
49 if (InterlockedCompareExchangePointer ((volatile gpointer *)&array->entries [new_bucket], entries, NULL) == NULL) {
51 * It must not be the case that we succeeded in setting the bucket
52 * pointer, while someone else succeeded in changing the capacity.
54 if (InterlockedCompareExchange ((volatile gint32 *)&array->capacity, new_capacity, old_capacity) != old_capacity)
55 g_assert_not_reached ();
56 array->slot_hint = old_capacity;
59 /* Someone beat us to the allocation. */
60 if (array->bucket_alloc_callback)
61 array->bucket_alloc_callback (entries, new_bucket_size, FALSE);
62 if (array->mem_type != -1)
63 sgen_free_internal_dynamic (entries, new_bucket_size, array->mem_type);
69 sgen_array_list_find_unset (SgenArrayList *array, guint32 capacity)
71 if (!array->is_slot_set_func) {
72 guint32 next_slot = array->next_slot;
73 /* We can't lookup empty slots, use next_slot */
74 if (next_slot < capacity)
77 guint32 slot_hint = array->slot_hint;
79 volatile gpointer *slot;
81 SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE(array, slot_hint, capacity, slot, index) {
82 if (!array->is_slot_set_func (slot))
84 } SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE;
86 SGEN_ARRAY_LIST_FOREACH_SLOT_RANGE (array, 0, slot_hint, slot, index) {
87 if (!array->is_slot_set_func (slot))
89 } SGEN_ARRAY_LIST_END_FOREACH_SLOT_RANGE;
96 sgen_array_list_update_next_slot (SgenArrayList *array, guint32 new_index)
98 if (!array->set_slot_func) {
100 * If we don't have a custom setter it means we don't have thread
101 * safety requirements.
103 if (new_index >= array->next_slot)
104 array->next_slot = new_index + 1;
106 guint32 old_next_slot;
107 /* Thread safe update */
109 old_next_slot = array->next_slot;
110 if (new_index < old_next_slot)
112 } while (InterlockedCompareExchange ((volatile gint32 *)&array->next_slot, new_index + 1, old_next_slot) != old_next_slot);
117 * Extension for the array list that allows fast allocation and index based fetching
118 * of long lived memory of various sizes, without the need of realloc. Not thread safe.
121 sgen_array_list_alloc_block (SgenArrayList *array, guint32 slots_to_add)
123 guint32 new_index = array->next_slot;
124 guint32 old_capacity = array->capacity;
126 /* FIXME Don't allocate arrays that will be skipped */
127 /* There are no empty arrays between next_slot and capacity because we allocate incrementally */
128 while ((old_capacity - new_index) < slots_to_add) {
129 sgen_array_list_grow (array, old_capacity);
130 new_index = old_capacity;
131 old_capacity = array->capacity;
134 SGEN_ASSERT (0, sgen_array_list_index_bucket (new_index) == sgen_array_list_index_bucket (new_index + slots_to_add - 1),
135 "We failed to allocate a continuous block of slots");
137 array->next_slot = new_index + slots_to_add;
138 /* The slot address will point to the allocated memory */
143 sgen_array_list_add (SgenArrayList *array, gpointer ptr, int data, gboolean increase_size_before_set)
145 guint32 index, capacity;
146 volatile gpointer *slot;
148 if (!array->capacity)
149 sgen_array_list_grow (array, 0);
151 capacity = array->capacity;
152 index = sgen_array_list_find_unset (array, capacity);
154 sgen_array_list_grow (array, capacity);
157 array->slot_hint = index;
159 if (increase_size_before_set) {
160 sgen_array_list_update_next_slot (array, index);
161 mono_memory_write_barrier ();
164 slot = sgen_array_list_get_slot (array, index);
165 if (array->set_slot_func) {
166 if (!array->set_slot_func (slot, ptr, data))
172 if (!increase_size_before_set) {
173 mono_memory_write_barrier ();
174 sgen_array_list_update_next_slot (array, index);
181 * Does a linear search through the pointer array to find `ptr`. Returns the index if
182 * found, otherwise (guint32)-1.
185 sgen_array_list_find (SgenArrayList *array, gpointer ptr)
187 volatile gpointer *slot;
189 SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
192 } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
197 sgen_array_list_default_cas_setter (volatile gpointer *slot, gpointer ptr, int data)
199 if (InterlockedCompareExchangePointer (slot, ptr, NULL) == NULL)
205 sgen_array_list_default_is_slot_set (volatile gpointer *slot)
207 return *slot != NULL;
210 /* Removes all NULL pointers from the array. Not thread safe */
212 sgen_array_list_remove_nulls (SgenArrayList *array)
215 volatile gpointer *slot;
216 gboolean skipped = FALSE;
218 SGEN_ARRAY_LIST_FOREACH_SLOT (array, slot) {
220 *sgen_array_list_get_slot (array, start++) = *slot;
226 } SGEN_ARRAY_LIST_END_FOREACH_SLOT;
228 mono_memory_write_barrier ();
229 array->next_slot = start;
230 array->slot_hint = start;