Mercurial > hg > CbC > CbC_gcc

comparison libiberty/fibheap.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* A Fibonacci heap datatype.
2 Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
4
5 This file is part of GNU CC.
6
7 GNU CC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GNU CC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20 Boston, MA 02110-1301, USA. */
21
22 #ifdef HAVE_CONFIG_H
23 #include "config.h"
24 #endif
25 #ifdef HAVE_LIMITS_H
26 #include <limits.h>
27 #endif
28 #ifdef HAVE_STDLIB_H
29 #include <stdlib.h>
30 #endif
31 #ifdef HAVE_STRING_H
32 #include <string.h>
33 #endif
34 #include "libiberty.h"
35 #include "fibheap.h"
36
37
38 #define FIBHEAPKEY_MIN LONG_MIN
39
40 static void fibheap_ins_root (fibheap_t, fibnode_t);
41 static void fibheap_rem_root (fibheap_t, fibnode_t);
42 static void fibheap_consolidate (fibheap_t);
43 static void fibheap_link (fibheap_t, fibnode_t, fibnode_t);
44 static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t);
45 static void fibheap_cascading_cut (fibheap_t, fibnode_t);
46 static fibnode_t fibheap_extr_min_node (fibheap_t);
47 static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t);
48 static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t);
49 static fibnode_t fibnode_new (void);
50 static void fibnode_insert_after (fibnode_t, fibnode_t);
51 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
52 static fibnode_t fibnode_remove (fibnode_t);
53
54
55 /* Create a new fibonacci heap. */
56 fibheap_t
57 fibheap_new (void)
58 {
59 return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
60 }
61
62 /* Create a new fibonacci heap node. */
63 static fibnode_t
64 fibnode_new (void)
65 {
66 fibnode_t node;
67
68 node = (fibnode_t) xcalloc (1, sizeof *node);
69 node->left = node;
70 node->right = node;
71
72 return node;
73 }
74
75 static inline int
76 fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
77 {
78 if (a->key < b->key)
79 return -1;
80 if (a->key > b->key)
81 return 1;
82 return 0;
83 }
84
85 static inline int
86 fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b)
87 {
88 struct fibnode a;
89
90 a.key = key;
91 a.data = data;
92
93 return fibheap_compare (heap, &a, b);
94 }
95
96 /* Insert DATA, with priority KEY, into HEAP. */
97 fibnode_t
98 fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data)
99 {
100 fibnode_t node;
101
102 /* Create the new node. */
103 node = fibnode_new ();
104
105 /* Set the node's data. */
106 node->data = data;
107 node->key = key;
108
109 /* Insert it into the root list. */
110 fibheap_ins_root (heap, node);
111
112 /* If their was no minimum, or this key is less than the min,
113 it's the new min. */
114 if (heap->min == NULL || node->key < heap->min->key)
115 heap->min = node;
116
117 heap->nodes++;
118
119 return node;
120 }
121
122 /* Return the data of the minimum node (if we know it). */
123 void *
124 fibheap_min (fibheap_t heap)
125 {
126 /* If there is no min, we can't easily return it. */
127 if (heap->min == NULL)
128 return NULL;
129 return heap->min->data;
130 }
131
132 /* Return the key of the minimum node (if we know it). */
133 fibheapkey_t
134 fibheap_min_key (fibheap_t heap)
135 {
136 /* If there is no min, we can't easily return it. */
137 if (heap->min == NULL)
138 return 0;
139 return heap->min->key;
140 }
141
142 /* Union HEAPA and HEAPB into a new heap. */
143 fibheap_t
144 fibheap_union (fibheap_t heapa, fibheap_t heapb)
145 {
146 fibnode_t a_root, b_root, temp;
147
148 /* If one of the heaps is empty, the union is just the other heap. */
149 if ((a_root = heapa->root) == NULL)
150 {
151 free (heapa);
152 return heapb;
153 }
154 if ((b_root = heapb->root) == NULL)
155 {
156 free (heapb);
157 return heapa;
158 }
159
160 /* Merge them to the next nodes on the opposite chain. */
161 a_root->left->right = b_root;
162 b_root->left->right = a_root;
163 temp = a_root->left;
164 a_root->left = b_root->left;
165 b_root->left = temp;
166 heapa->nodes += heapb->nodes;
167
168 /* And set the new minimum, if it's changed. */
169 if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
170 heapa->min = heapb->min;
171
172 free (heapb);
173 return heapa;
174 }
175
176 /* Extract the data of the minimum node from HEAP. */
177 void *
178 fibheap_extract_min (fibheap_t heap)
179 {
180 fibnode_t z;
181 void *ret = NULL;
182
183 /* If we don't have a min set, it means we have no nodes. */
184 if (heap->min != NULL)
185 {
186 /* Otherwise, extract the min node, free the node, and return the
187 node's data. */
188 z = fibheap_extr_min_node (heap);
189 ret = z->data;
190 free (z);
191 }
192
193 return ret;
194 }
195
196 /* Replace both the KEY and the DATA associated with NODE. */
197 void *
198 fibheap_replace_key_data (fibheap_t heap, fibnode_t node,
199 fibheapkey_t key, void *data)
200 {
201 void *odata;
202 fibheapkey_t okey;
203 fibnode_t y;
204
205 /* If we wanted to, we could actually do a real increase by redeleting and
206 inserting. However, this would require O (log n) time. So just bail out
207 for now. */
208 if (fibheap_comp_data (heap, key, data, node) > 0)
209 return NULL;
210
211 odata = node->data;
212 okey = node->key;
213 node->data = data;
214 node->key = key;
215 y = node->parent;
216
217 if (okey == key)
218 return odata;
219
220 /* These two compares are specifically <= 0 to make sure that in the case
221 of equality, a node we replaced the data on, becomes the new min. This
222 is needed so that delete's call to extractmin gets the right node. */
223 if (y != NULL && fibheap_compare (heap, node, y) <= 0)
224 {
225 fibheap_cut (heap, node, y);
226 fibheap_cascading_cut (heap, y);
227 }
228
229 if (fibheap_compare (heap, node, heap->min) <= 0)
230 heap->min = node;
231
232 return odata;
233 }
234
235 /* Replace the DATA associated with NODE. */
236 void *
237 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
238 {
239 return fibheap_replace_key_data (heap, node, node->key, data);
240 }
241
242 /* Replace the KEY associated with NODE. */
243 fibheapkey_t
244 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
245 {
246 int okey = node->key;
247 fibheap_replace_key_data (heap, node, key, node->data);
248 return okey;
249 }
250
251 /* Delete NODE from HEAP. */
252 void *
253 fibheap_delete_node (fibheap_t heap, fibnode_t node)
254 {
255 void *ret = node->data;
256
257 /* To perform delete, we just make it the min key, and extract. */
258 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
259 fibheap_extract_min (heap);
260
261 return ret;
262 }
263
264 /* Delete HEAP. */
265 void
266 fibheap_delete (fibheap_t heap)
267 {
268 while (heap->min != NULL)
269 free (fibheap_extr_min_node (heap));
270
271 free (heap);
272 }
273
274 /* Determine if HEAP is empty. */
275 int
276 fibheap_empty (fibheap_t heap)
277 {
278 return heap->nodes == 0;
279 }
280
281 /* Extract the minimum node of the heap. */
282 static fibnode_t
283 fibheap_extr_min_node (fibheap_t heap)
284 {
285 fibnode_t ret = heap->min;
286 fibnode_t x, y, orig;
287
288 /* Attach the child list of the minimum node to the root list of the heap.
289 If there is no child list, we don't do squat. */
290 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
291 {
292 if (orig == NULL)
293 orig = x;
294 y = x->right;
295 x->parent = NULL;
296 fibheap_ins_root (heap, x);
297 }
298
299 /* Remove the old root. */
300 fibheap_rem_root (heap, ret);
301 heap->nodes--;
302
303 /* If we are left with no nodes, then the min is NULL. */
304 if (heap->nodes == 0)
305 heap->min = NULL;
306 else
307 {
308 /* Otherwise, consolidate to find new minimum, as well as do the reorg
309 work that needs to be done. */
310 heap->min = ret->right;
311 fibheap_consolidate (heap);
312 }
313
314 return ret;
315 }
316
317 /* Insert NODE into the root list of HEAP. */
318 static void
319 fibheap_ins_root (fibheap_t heap, fibnode_t node)
320 {
321 /* If the heap is currently empty, the new node becomes the singleton
322 circular root list. */
323 if (heap->root == NULL)
324 {
325 heap->root = node;
326 node->left = node;
327 node->right = node;
328 return;
329 }
330
331 /* Otherwise, insert it in the circular root list between the root
332 and it's right node. */
333 fibnode_insert_after (heap->root, node);
334 }
335
336 /* Remove NODE from the rootlist of HEAP. */
337 static void
338 fibheap_rem_root (fibheap_t heap, fibnode_t node)
339 {
340 if (node->left == node)
341 heap->root = NULL;
342 else
343 heap->root = fibnode_remove (node);
344 }
345
346 /* Consolidate the heap. */
347 static void
348 fibheap_consolidate (fibheap_t heap)
349 {
350 fibnode_t a[1 + 8 * sizeof (long)];
351 fibnode_t w;
352 fibnode_t y;
353 fibnode_t x;
354 int i;
355 int d;
356 int D;
357
358 D = 1 + 8 * sizeof (long);
359
360 memset (a, 0, sizeof (fibnode_t) * D);
361
362 while ((w = heap->root) != NULL)
363 {
364 x = w;
365 fibheap_rem_root (heap, w);
366 d = x->degree;
367 while (a[d] != NULL)
368 {
369 y = a[d];
370 if (fibheap_compare (heap, x, y) > 0)
371 {
372 fibnode_t temp;
373 temp = x;
374 x = y;
375 y = temp;
376 }
377 fibheap_link (heap, y, x);
378 a[d] = NULL;
379 d++;
380 }
381 a[d] = x;
382 }
383 heap->min = NULL;
384 for (i = 0; i < D; i++)
385 if (a[i] != NULL)
386 {
387 fibheap_ins_root (heap, a[i]);
388 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
389 heap->min = a[i];
390 }
391 }
392
393 /* Make NODE a child of PARENT. */
394 static void
395 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
396 fibnode_t node, fibnode_t parent)
397 {
398 if (parent->child == NULL)
399 parent->child = node;
400 else
401 fibnode_insert_before (parent->child, node);
402 node->parent = parent;
403 parent->degree++;
404 node->mark = 0;
405 }
406
407 /* Remove NODE from PARENT's child list. */
408 static void
409 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
410 {
411 fibnode_remove (node);
412 parent->degree--;
413 fibheap_ins_root (heap, node);
414 node->parent = NULL;
415 node->mark = 0;
416 }
417
418 static void
419 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
420 {
421 fibnode_t z;
422
423 while ((z = y->parent) != NULL)
424 {
425 if (y->mark == 0)
426 {
427 y->mark = 1;
428 return;
429 }
430 else
431 {
432 fibheap_cut (heap, y, z);
433 y = z;
434 }
435 }
436 }
437
438 static void
439 fibnode_insert_after (fibnode_t a, fibnode_t b)
440 {
441 if (a == a->right)
442 {
443 a->right = b;
444 a->left = b;
445 b->right = a;
446 b->left = a;
447 }
448 else
449 {
450 b->right = a->right;
451 a->right->left = b;
452 a->right = b;
453 b->left = a;
454 }
455 }
456
457 static fibnode_t
458 fibnode_remove (fibnode_t node)
459 {
460 fibnode_t ret;
461
462 if (node == node->left)
463 ret = NULL;
464 else
465 ret = node->left;
466
467 if (node->parent != NULL && node->parent->child == node)
468 node->parent->child = ret;
469
470 node->right->left = node->left;
471 node->left->right = node->right;
472
473 node->parent = NULL;
474 node->left = node;
475 node->right = node;
476
477 return ret;
478 }