No issues found
1 /*
2 * Copyright (C) 2011, Nokia <ivan.frade@nokia.com>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 *
19 * Author: Carlos Garnacho <carlos@lanedo.com>
20 */
21
22 #include "config.h"
23
24 #include "tracker-priority-queue.h"
25
26 typedef struct PrioritySegment PrioritySegment;
27
28 struct PrioritySegment
29 {
30 gint priority;
31 GList *first_elem;
32 GList *last_elem;
33 };
34
35 struct _TrackerPriorityQueue
36 {
37 GQueue queue;
38 GArray *segments;
39
40 gint ref_count;
41 };
42
43 TrackerPriorityQueue *
44 tracker_priority_queue_new (void)
45 {
46 TrackerPriorityQueue *queue;
47
48 queue = g_slice_new (TrackerPriorityQueue);
49 g_queue_init (&queue->queue);
50 queue->segments = g_array_new (FALSE, FALSE,
51 sizeof (PrioritySegment));
52
53 queue->ref_count = 1;
54
55 return queue;
56 }
57
58 TrackerPriorityQueue *
59 tracker_priority_queue_ref (TrackerPriorityQueue *queue)
60 {
61 g_atomic_int_inc (&queue->ref_count);
62 return queue;
63 }
64
65 void
66 tracker_priority_queue_unref (TrackerPriorityQueue *queue)
67 {
68 if (g_atomic_int_dec_and_test (&queue->ref_count)) {
69 g_queue_clear (&queue->queue);
70 g_array_free (queue->segments, TRUE);
71 g_slice_free (TrackerPriorityQueue, queue);
72 }
73 }
74
75 static GList *
76 priority_segment_alloc_node (TrackerPriorityQueue *queue,
77 gint priority)
78 {
79 PrioritySegment *segment = NULL;
80 gboolean found = FALSE;
81 gint l, r, c;
82 GList *node;
83
84 /* Perform binary search to find out the segment for
85 * the given priority, create one if it isn't found.
86 */
87 l = 0;
88 r = queue->segments->len - 1;
89
90 while (queue->segments->len > 0 && !found) {
91 c = (r + l) / 2;
92 segment = &g_array_index (queue->segments, PrioritySegment, c);
93
94 if (segment->priority == priority) {
95 found = TRUE;
96 break;
97 } else if (segment->priority > priority) {
98 r = c - 1;
99 } else if (segment->priority < priority) {
100 l = c + 1;
101 }
102
103 if (l > r) {
104 break;
105 }
106 }
107
108 if (found) {
109 /* Element found, append at the end of segment */
110 g_assert (segment != NULL);
111 g_assert (segment->priority == priority);
112
113 g_queue_insert_after (&queue->queue, segment->last_elem, NULL);
114 node = segment->last_elem = segment->last_elem->next;
115 } else {
116 PrioritySegment new_segment = { 0 };
117
118 new_segment.priority = priority;
119
120 if (segment) {
121 g_assert (segment->priority != priority);
122
123 /* Binary search got to one of the closest results,
124 * but we may have come from either of both sides,
125 * so check whether we have to insert after the
126 * segment we got.
127 */
128 if (segment->priority > priority) {
129 /* We have to insert to the left of this element */
130 g_queue_insert_before (&queue->queue, segment->first_elem, NULL);
131 node = segment->first_elem->prev;
132 } else {
133 /* We have to insert to the right of this element */
134 g_queue_insert_after (&queue->queue, segment->last_elem, NULL);
135 node = segment->last_elem->next;
136 c++;
137 }
138
139 new_segment.first_elem = new_segment.last_elem = node;
140 g_array_insert_val (queue->segments, c, new_segment);
141 } else {
142 /* Segments list has 0 elements */
143 g_assert (queue->segments->len == 0);
144 g_assert (g_queue_get_length (&queue->queue) == 0);
145
146 node = g_list_alloc ();
147 g_queue_push_head_link (&queue->queue, node);
148 new_segment.first_elem = new_segment.last_elem = node;
149
150 g_array_append_val (queue->segments, new_segment);
151 }
152 }
153
154 return node;
155 }
156
157 void
158 tracker_priority_queue_foreach (TrackerPriorityQueue *queue,
159 GFunc func,
160 gpointer user_data)
161 {
162 g_return_if_fail (queue != NULL);
163 g_return_if_fail (func != NULL);
164
165 g_queue_foreach (&queue->queue, func, user_data);
166 }
167
168 gboolean
169 tracker_priority_queue_foreach_remove (TrackerPriorityQueue *queue,
170 GEqualFunc compare_func,
171 gpointer compare_user_data,
172 GDestroyNotify destroy_notify)
173 {
174 PrioritySegment *segment;
175 gint n_segment = 0;
176 gboolean updated = FALSE;
177 GList *list;
178
179 g_return_val_if_fail (queue != NULL, FALSE);
180 g_return_val_if_fail (compare_func != NULL, FALSE);
181
182 list = queue->queue.head;
183
184 if (!list) {
185 return FALSE;
186 }
187
188 segment = &g_array_index (queue->segments, PrioritySegment, n_segment);
189
190 while (list) {
191 GList *elem;
192
193 elem = list;
194 list = list->next;
195
196 if ((compare_func) (elem->data, compare_user_data)) {
197 /* Update segment limits */
198 if (elem == segment->first_elem &&
199 elem == segment->last_elem) {
200 /* Last element of segment, remove it */
201 g_array_remove_index (queue->segments,
202 n_segment);
203
204 if (list) {
205 /* Fetch the next one */
206 segment = &g_array_index (queue->segments,
207 PrioritySegment,
208 n_segment);
209 }
210 } else if (elem == segment->first_elem) {
211 /* First elemen in segment */
212 segment->first_elem = elem->next;
213 } else if (elem == segment->last_elem) {
214 segment->last_elem = elem->prev;
215 }
216
217 if (destroy_notify) {
218 (destroy_notify) (elem->data);
219 }
220
221 g_queue_delete_link (&queue->queue, elem);
222 updated = TRUE;
223 } else {
224 if (list != NULL &&
225 elem == segment->last_elem) {
226 /* Move on to the next segment */
227 n_segment++;
228 g_assert (n_segment < queue->segments->len);
229
230 segment = &g_array_index (queue->segments,
231 PrioritySegment,
232 n_segment);
233 }
234 }
235 }
236
237 return updated;
238 }
239
240 gboolean
241 tracker_priority_queue_is_empty (TrackerPriorityQueue *queue)
242 {
243 g_return_val_if_fail (queue != NULL, FALSE);
244
245 return g_queue_is_empty (&queue->queue);
246 }
247
248 guint
249 tracker_priority_queue_get_length (TrackerPriorityQueue *queue)
250 {
251 g_return_val_if_fail (queue != NULL, 0);
252
253 return g_queue_get_length (&queue->queue);
254 }
255
256 void
257 tracker_priority_queue_add (TrackerPriorityQueue *queue,
258 gpointer data,
259 gint priority)
260 {
261 GList *node;
262
263 g_return_if_fail (queue != NULL);
264 g_return_if_fail (data != NULL);
265
266 node = priority_segment_alloc_node (queue, priority);
267 g_assert (node != NULL);
268
269 node->data = data;
270 }
271
272 gpointer
273 tracker_priority_queue_find (TrackerPriorityQueue *queue,
274 gint *priority_out,
275 GEqualFunc compare_func,
276 gpointer user_data)
277 {
278 PrioritySegment *segment;
279 gint n_segment = 0;
280 GList *list;
281
282 g_return_val_if_fail (queue != NULL, NULL);
283 g_return_val_if_fail (compare_func != NULL, NULL);
284
285 list = queue->queue.head;
286 segment = &g_array_index (queue->segments, PrioritySegment, n_segment);
287
288 while (list) {
289 if ((compare_func) (list->data, user_data)) {
290 if (priority_out) {
291 *priority_out = segment->priority;
292 }
293
294 return list->data;
295 }
296
297 if (list->next != NULL &&
298 list == segment->last_elem) {
299 /* Move on to the next segment */
300 n_segment++;
301 g_assert (n_segment < queue->segments->len);
302 segment = &g_array_index (queue->segments,
303 PrioritySegment,
304 n_segment);
305 }
306
307 list = list->next;
308 }
309
310 return NULL;
311 }
312
313 gpointer
314 tracker_priority_queue_peek (TrackerPriorityQueue *queue,
315 gint *priority_out)
316 {
317 g_return_val_if_fail (queue != NULL, NULL);
318
319 if (priority_out) {
320 PrioritySegment *segment;
321
322 segment = &g_array_index (queue->segments, PrioritySegment, 0);
323 *priority_out = segment->priority;
324 }
325
326 return g_queue_peek_head (&queue->queue);
327 }
328
329 gpointer
330 tracker_priority_queue_pop (TrackerPriorityQueue *queue,
331 gint *priority_out)
332 {
333 PrioritySegment *segment;
334 GList *node;
335
336 g_return_val_if_fail (queue != NULL, NULL);
337
338 node = g_queue_peek_head_link (&queue->queue);
339
340 if (!node) {
341 /* No elements in queue */
342 return NULL;
343 }
344
345 segment = &g_array_index (queue->segments, PrioritySegment, 0);
346 g_assert (segment->first_elem == node);
347
348 if (priority_out) {
349 *priority_out = segment->priority;
350 }
351
352 if (segment->last_elem == node) {
353 /* It is the last element of the first
354 * segment, remove segment as well.
355 */
356 g_array_remove_index (queue->segments, 0);
357 } else {
358
359 /* Move segments first element forward */
360 segment->first_elem = segment->first_elem->next;
361 }
362
363 return g_queue_pop_head (&queue->queue);
364 }