2 * Copyright 2001-2003 Ximian, Inc
3 * Copyright 2003-2010 Novell, Inc.
5 * Permission is hereby granted, free of charge, to any person obtaining
6 * a copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sublicense, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
20 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
21 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
22 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 #define GRAY_QUEUE_SECTION_SIZE (128 - 3)
25 #define GRAY_QUEUE_LENGTH_LIMIT 64
28 * This is a stack now instead of a queue, so the most recently added items are removed
29 * first, improving cache locality, and keeping the stack size manageable.
31 typedef struct _GrayQueueSection GrayQueueSection;
32 struct _GrayQueueSection {
34 GrayQueueSection *next, *prev;
35 char *objects [GRAY_QUEUE_SECTION_SIZE];
38 static GrayQueueSection *gray_queue_start = NULL;
39 static GrayQueueSection *gray_queue_end = NULL;
41 static int gray_queue_balance = 0;
42 static int num_gray_queue_sections = 0;
45 gray_object_alloc_queue_section (void)
47 GrayQueueSection *section;
49 /* Use the previously allocated queue sections if possible */
50 if (!gray_queue_end && gray_queue_start) {
51 gray_queue_end = gray_queue_start;
52 gray_queue_end->end = 0;
55 if (gray_queue_end && gray_queue_end->next) {
56 gray_queue_end = gray_queue_end->next;
57 gray_queue_end->end = 0;
61 /* Allocate a new section */
62 section = get_internal_mem (sizeof (GrayQueueSection), INTERNAL_MEM_GRAY_QUEUE);
63 ++num_gray_queue_sections;
69 /* Link it with the others */
71 gray_queue_end->next = section;
72 section->prev = gray_queue_end;
74 g_assert (!gray_queue_start);
75 gray_queue_start = section;
77 gray_queue_end = section;
81 gray_object_free_queue_section (GrayQueueSection *section)
83 free_internal_mem (section, INTERNAL_MEM_GRAY_QUEUE);
84 --num_gray_queue_sections;
87 static inline gboolean
88 gray_object_queue_is_empty (void)
90 return gray_queue_end == NULL;
94 * The following two functions are called in the inner loops of the
95 * collector, so they need to be as fast as possible. We have macros
100 gray_object_enqueue (char *obj)
102 DEBUG (9, g_assert (obj));
103 if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE))
104 gray_object_alloc_queue_section ();
105 DEBUG (9, g_assert (gray_queue_end && gray_queue_end->end < GRAY_QUEUE_SECTION_SIZE));
106 gray_queue_end->objects [gray_queue_end->end++] = obj;
108 DEBUG (9, ++gray_queue_balance);
112 gray_object_dequeue (void)
116 if (gray_object_queue_is_empty ())
119 DEBUG (9, g_assert (gray_queue_end->end));
121 obj = gray_queue_end->objects [--gray_queue_end->end];
123 if (G_UNLIKELY (gray_queue_end->end == 0))
124 gray_queue_end = gray_queue_end->prev;
126 DEBUG (9, --gray_queue_balance);
131 #if MAX_DEBUG_LEVEL >= 9
132 #define GRAY_OBJECT_ENQUEUE gray_object_enqueue
133 #define GRAY_OBJECT_DEQUEUE(o) ((o) = gray_object_dequeue ())
135 #define GRAY_OBJECT_ENQUEUE(o) do { \
136 if (G_UNLIKELY (!gray_queue_end || gray_queue_end->end == GRAY_QUEUE_SECTION_SIZE)) \
137 gray_object_alloc_queue_section (); \
138 gray_queue_end->objects [gray_queue_end->end++] = (o); \
140 #define GRAY_OBJECT_DEQUEUE(o) do { \
141 if (!gray_queue_end) { \
144 (o) = gray_queue_end->objects [--gray_queue_end->end]; \
145 if (G_UNLIKELY (gray_queue_end->end == 0)) \
146 gray_queue_end = gray_queue_end->prev; \
152 gray_object_queue_init (void)
154 GrayQueueSection *section, *next;
157 g_assert (gray_object_queue_is_empty ());
158 g_assert (sizeof (GrayQueueSection) < MAX_FREELIST_SIZE);
159 DEBUG (9, g_assert (gray_queue_balance == 0));
161 /* Free the extra sections allocated during the last collection */
163 for (section = gray_queue_start; section && i < GRAY_QUEUE_LENGTH_LIMIT; section = section->next)
167 section->prev->next = NULL;
168 for (; section; section = next) {
169 next = section->next;
170 gray_object_free_queue_section (section);