2 * sgen-pointer-queue.c: A pointer queue that can be sorted.
4 * Copyright (C) 2014 Xamarin Inc
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License 2.0 as published by the Free Software Foundation;
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
15 * You should have received a copy of the GNU Library General Public
16 * License 2.0 along with this library; if not, write to the Free
17 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 #include "utils/mono-compiler.h"
21 #include "metadata/sgen-gc.h"
22 #include "metadata/sgen-pointer-queue.h"
27 sgen_pointer_queue_clear (SgenPointerQueue
*queue
)
33 sgen_pointer_queue_init (SgenPointerQueue
*queue
, int mem_type
)
38 queue
->mem_type
= mem_type
;
42 realloc_queue (SgenPointerQueue
*queue
)
44 size_t new_size
= queue
->size
? queue
->size
+ queue
->size
/2 : 1024;
45 void **new_data
= sgen_alloc_internal_dynamic (sizeof (void*) * new_size
, queue
->mem_type
, TRUE
);
47 memcpy (new_data
, queue
->data
, sizeof (void*) * queue
->next_slot
);
48 sgen_free_internal_dynamic (queue
->data
, sizeof (void*) * queue
->size
, queue
->mem_type
);
49 queue
->data
= new_data
;
50 queue
->size
= new_size
;
51 SGEN_LOG (4, "Reallocated pointer queue to size: %lu", new_size
);
55 sgen_pointer_queue_add (SgenPointerQueue
*queue
, void *ptr
)
57 if (queue
->next_slot
>= queue
->size
)
58 realloc_queue (queue
);
60 queue
->data
[queue
->next_slot
++] = ptr
;
64 sgen_pointer_queue_pop (SgenPointerQueue
*queue
)
66 g_assert (queue
->next_slot
);
68 return queue
->data
[--queue
->next_slot
];
72 sgen_pointer_queue_search (SgenPointerQueue
*queue
, void *addr
)
74 size_t first
= 0, last
= queue
->next_slot
;
75 while (first
< last
) {
76 size_t middle
= first
+ ((last
- first
) >> 1);
77 if (addr
<= queue
->data
[middle
])
82 g_assert (first
== last
);
87 * Removes all NULL pointers from the queue.
90 sgen_pointer_queue_remove_nulls (SgenPointerQueue
*queue
)
92 void **start
, **cur
, **end
;
93 start
= cur
= queue
->data
;
94 end
= queue
->data
+ queue
->next_slot
;
101 queue
->next_slot
= start
- queue
->data
;
105 * Sorts the pointers in the queue, then removes duplicates.
108 sgen_pointer_queue_sort_uniq (SgenPointerQueue
*queue
)
110 void **start
, **cur
, **end
;
111 /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
112 /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
113 SGEN_LOG (5, "Sorting pointer queue, size: %lu", queue
->next_slot
);
114 if (queue
->next_slot
> 1)
115 sgen_sort_addresses (queue
->data
, queue
->next_slot
);
116 start
= cur
= queue
->data
;
117 end
= queue
->data
+ queue
->next_slot
;
120 while (cur
< end
&& *start
== *cur
)
124 queue
->next_slot
= start
- queue
->data
;
125 SGEN_LOG (5, "Pointer queue reduced to size: %lu", queue
->next_slot
);
129 * Does a linear search through the pointer queue to find `ptr`. Returns the index if
130 * found, otherwise (size_t)-1.
133 sgen_pointer_queue_find (SgenPointerQueue
*queue
, void *ptr
)
136 for (i
= 0; i
< queue
->next_slot
; ++i
)
137 if (queue
->data
[i
] == ptr
)
143 sgen_pointer_queue_is_empty (SgenPointerQueue
*queue
)
145 return !queue
->next_slot
;
149 sgen_pointer_queue_free (SgenPointerQueue
*queue
)
151 sgen_free_internal_dynamic (queue
->data
, sizeof (void*) * queue
->size
, queue
->mem_type
);